1. No category

Mapas de Karnaugh y método
de Quine McCluskey
Ing. Mónica Patricia René_2010
Ing. Mónica P. René_2010
1
Introducción





Vimos como representar funciones de conmutación con tablas de
verdad, implementándolas con compuertas lógicas.
Además mediante el álgebra de Boole, reducimos dichas funciones
de conmutación para que puedan emplearse el mínimo número
posible de compuertas lógicas.
Cuando la función de conmutación depende de muchas entradas, el
método para reducir la función mediante teoremas y postulados
del álgebra booleana se vuelve tedioso.
Además una misma función se puede expresar algebraicamente de
distintas maneras.
Los métodos que veremos a continuación remedian estas
dificultades.
Ing. Mónica P. René_2010
2
Mapas de Karnaugh

Como una tabla de verdad, el mapa de Karnaugh de una función,
especifica el valor de dicha función para todas las combinaciones de
valores de las variables independientes (entradas).

Es un diagrama en forma de matriz de cuadros, donde cada cuadro
corresponde a un minitérmino de la función.

Las expresiones simplificadas, que se generan del mapa, siempre
están en una de las dos formas estándar: suma de minitérminos o
producto de maxitérminos.

La expresión más simple no es única.
Ing. Mónica P. René_2010
3
Mapas de Karnaugh de dos y tres variables

Para dos variables, existen 4
minitérminos, por lo tanto 4
cuadros en la matriz.
Ejemplo
A,B: variables de
entrada

A
A
0
B
1
B
0
A=0, B=0
1
1
A=1, B=1
A=0, B=1
AB
A´ B
A
A
0
1
0
0 m
m2
m1
m3
1
AB´
A´ B´
A
B
0
1
0
0
2
00
10
1
1
3
01
11
B
B
0
1
A
B
0
0
0
1
1
0
1
1
0
1
1
0
A=1, B=0
B
0
A
Ing. Mónica P. René_2010
4
Mapas de Karnaugh de dos y tres variables






Se pueden leer los minitérminos
igual que en una tabla de verdad.
Cada 1 contenido en el mapa
corresponde a un término producto
de F.
Un 1 contenido en la celda 00,
indica que A´B´ es un término
producto de F.
Los términos productos ubicados en
celdas
adyacentes,
pueden
combinarse, dado que solo difieren
en una sola variable.
A´B´ y A´B se combinan para formar
A´.
Lo anterior se indica mediante un
lazo
que
envuelve
a
los
correspondientes unos sobre el
mapa.
Ejemplo
Para la siguiente tabla de verdad
construya el mapa de K.

A
A
B
F
0
0
1
0
0
1
1
1
1
0
0
1
1
0
1
0
B
1
0
1
0
A
1
0
B
0
A´ B´
1
1
0
1
0
A´ B
F= A´ B´+A´B
A
1
0
B
0
A´ B´+A´B=A´ 1
1
0
1
0
F=A´
Ing. Mónica P. René_2010
5
Mapas de Karnaugh de dos y tres variables

Para tres variables:
A
BC
0
1
000
100
A
00
001
101
011
111
11
100 ES
ADYACENTE
A 110
01
11
010
10
NOTACION BINARIA


A
BC
0
4
0 0 0 0
1
5
0 0 1 0
01
3
7
0 1 0 1
11
2
6
0 1 1 1
10
110
10

1
BC
00
01
0
A B C F
NOTACION DECIMAL
00
0
1
0
1
0
0
1
0
1
1
1 0 0 1
1 0 1 0
Los términos productos situados en
celdas adyacentes se pueden combinar
1 1 0 1
utilizando el teorema XY´+XY=X
1 1 1 0
Por ejemplo el término producto 001
(A´B´C) se puede combinar con tres
términos producto como se ve en la fig.
Las filas superiores e inferiores del mapa
también son adyacentes (100 con 110
y 000 con 010)
Ing. Mónica P. René_2010
6
Mapas de Karnaugh de dos y tres variables

Dada la expansión en términos producto de una función, puede
representarse sobre un mapa colocando unos en las celdas que
corresponden a lo minitérminos de la función y ceros en las celdas
restantes.
A
BC
0
1
0
0
1
1
1
0
0
0
00
01
11
10
F(A,B,C)=∑(m1,m3,m5)
Ing. Mónica P. René_2010
7
Mapas de Karnaugh de dos y tres variables
Si una función se especifica en forma algebraica, no es necesario
expandirla en términos producto antes de representarla sobre un
mapa.
 Por ejemplo suponiendo que f(a,b,c,d)=abc´+b´c+a´ construiremos el
mapa como se muestra:
a
 El término abc’ es 1 cuando a=1, y bc=10, por lo que
0
1
bc
colocamos un 1 en la celda que corresponde a la
1
0
00
columna a= 1 y la fila bc=10
1
1
 El término b´c es 1 cuando bc=01,por lo que
01
colocamos un 1 en ambas celdas de la fila bc=01
1
0
11
del mapa.
1
1
10
 El término a´ es 1 cuando a=0, por lo que colocamos
un 1 en todas las celdas de la columna a=0 del mapa.
Nota: dado que hay un 1 en la celda abc=001 no tenemos que colocar
un segundo 1 ahí, ya que x+x=x

Ing. Mónica P. René_2010
8
Mapas de Karnaugh de dos y tres variables

Ejemplo de deducción de una expresión simplificada utilizando un
mapa de Karnaugh.
F(a,b,c)=a´b´c+a´bc+ab´c
a
bc
0
0
a
1
bc
0
00
0
1
0
0
1
1
1
0
0
0
00
1
1
01
01
1
0
11
0
T1= a´b´c+a´bc=a´c
11
0
10
F(a,b,c)=∑(m1,m3,m5)
Inserción de los términos
productos (o minitérminos)
T2= a´b´c+ab´c=b´c
10
F=a´c+b´c
Forma simplificada de F
Rellenamos el mapa con los términos producto correspondientes.
 Agrupamos mediante los lazos.
 Simplificamos.
F(a,b,c)=a´c+b´c

Ing. Mónica P. René_2010
9
Mapas de Karnaugh de dos y tres variables

Si queremos encontrar el complemento de la función mostrada en
el ejemplo anterior, simplemente cambiamos en el mapa los 0 por 1
y los 1 por 0.
F´(a,b,c)=(a´b´c+a´bc+ab´c)´
a
bc
0
1
a
1
bc
1
00
1
1
1
0
0
0
1
1
1
00
0
0
01
01
0
1
T1= b´c´+bc´=c´
11
11
1
1
10
F’(a,b,c)=∑(m0,m2,m4,m6,m7)
Inserción de los términos
productos (o minitérminos)

0
T2= ab
F´=c´+ab
Forma simplificada de F´
Simplificamos como se explicó.
F´(a,b,c)=c´+ab
Ing. Mónica P. René_2010
10
Mapas de Karnaugh de dos y tres variables

Si queremos expresar la función F como un producto de sumas(o
productos de maxitérminos), buscamos el complemento de dicha
función simplificamos y luego aplicamos el teorema de Morgan, para
volver a complementar, y poder expresar F finalmente como un
producto de maxitérminos.

Para el ejemplo anterior donde F(a,b,c)=a´b´c+a´bc+ab´c vimos
como encontrar F´(a,b,c)=c´+ab

Ahora aplicando el teorema de Morgán, para volver a complemetar:
(F’)’= F = c (a’ +b’)
producto de maxitérminos
Ing. Mónica P. René_2010
11
Mapas de Karnaugh de cuatro variables

Las siguientes figuras muestran la distribución de un mapa K de
cuatro variables:
AB
00
01
11
10
0
4
12
8
1
5
13
9
3
7
15
11
2
6
14
10
CD
00
01
11
10

La definición de celdas adyacentes se amplia, no sólo las filas
superior e inferior son adyacentes, sino que también lo son la
primera y la última columna.
Ing. Mónica P. René_2010
12
Ejemplos
Checar concepto de desbordamiento pag. 16
Fundamentos de diseño lógico, Charles H. Roth, Jr., 5ª ed.Thomson
• Problemas 5.3, a),b)c)
• 5.4
• 5.5 (observación la operación EQU (equivalencia)=XNOR)
• 5.6 (solo hallar la suma mínima de productos de cada función)
Ing. Mónica P. René_2010
13
Método de Quine McCluskey

Este método proporciona un procedimiento simplificado y
sistémico que puede programarse en una computadora.

Se utiliza cuando el número de variables es más grande o se tienen
que simplificar varias funciones y ya no es aconsejable utilizar
mapas de K.
Ing. Mónica P. René_2010
14
Método de Quine McCluskey

El procedimiento consta de dos pasos:

Eliminar tantos literales como sea posible de cada término,
aplicando sistemáticamente el teorema XY+XY´=X . Los términos
resultantes se denominan resultantes primos.
Utilizar un gráfico de implicantes primos para seleccionar un
conjunto mínimo de implicantes primos que, combinados mediante
la operación OR, equivalgan a la función que se va a simplificar y
que contenga un número mínimo de literales.

Ing. Mónica P. René_2010
15
Método de Quine McCluskey


Procedimiento:
La función debe estar dada como una suma de minitérminos ( o
suma de productos).

De no estar en la forma anterior, deberá expandirse a una suma de
minitérminos según los procedimientos vistos en temas anteriores.

Se forman sistemáticamente todos los implicantes primos de la
función, combinando los minitérminos.

Los minitérminos se representarán en notación binaria y se
combinarán utilizando el teorema de absorción XY+XY´=X

Donde X representa un producto literal e Y es una sola variable
Ing. Mónica P. René_2010
16
Método de Quine McCluskey

Ej.
AB´CD´  AB´CD
101 0 101 1
 
 
X Y´  X
Y
A´BC´D  A´BCD ´
0 1 0 1 0 1 1 0


AB´C
 101   el guión indica una variable que falta

 X
(no se combinan)
(no se combinan)
Para hallar todos los implicantes primos, deben compararse todos los
pares posibles de producto y combinarse siempre que se pueda.
Veamos mediante un ejemplo como formar la tabla de determinación
de implicantes primos.
Ing. Mónica P. René_2010
17
Método de Quine McCluskey

Veamos un ejemplo, dada la siguiente función encuentre los
implicantes primos
f
a, b, c, d m
0, 1, 2, 5, 6, 7, 8, 9, 10, 14

Dividimos los minitérminos en grupos, numerados según la
cantidad de unos contenidos en dichos minitérminos:
grupo 0
0
0000

grupo 1
1
2
8
0001
0010
1000

grupo 2
5
6
9
10
0101
0110
1001
1010
grupo 3
7
14
0111
1110
Luego, dos términos podrán
combinarse si difieren en
exactamente una variable.
Compararemos los términos
del grupo 0 con los del grupo 1.
Ing. Mónica P. René_2010
18
Método de Quine McCluskey
GRUPO
0
1
COLUMNA 1
COLUMNA 2
COLUMNA 3
0
0000
0,1
000-
0,1,8,9
-00-
1
0001
0,2
00-0
0,2,8,10
-0-0
2
0010
0,8
-000
0,8,1,9
-00-
8
1000
1,5
0-01
0,8,2,10
-0-0
5
0101
1,9
-001
2,6,10,14
--10
6
0110
2,6
0-10
2,10,6,14
--10
9
1001
2,10
-010
10
010
8,9
100-
7
0111
8,10
10-0
14
1110
5,7
01-1
6,7
011-
6,14
-110
10,14
1-10
2
3
Tabla 1
Ing. Mónica P. René_2010
19
Método de Quine McCluskey








Se combinan a´b´c´d´+a´b´c´d=a´b´c´
Se combinan a´b´c´d´+a´b´cd´=a´b´d´
Se combinan a´b´c´d´+ab´c´d´=b´c´d´
Los términos anteriores se combinan para eliminar una variable,
utilizando el teorema de absorción XY+XY´=X
Los términos de la columna 2 se dividen también en grupos según
la cantidad de unos que contienen.
Los términos del primer grupo de la columna 2 solo tienen que
compararse con los términos del segundo grupo que contengan
guiones en las mismas posiciones, a´b´c´+ab´c´=b´c´.
El término resultante se enumera en la columna 3.
Luego repetimos el procedimiento anterior para la columna 3.
Ing. Mónica P. René_2010
20
Método de Quine McCluskey


De la tabla anterior, los términos que no se han combinado con
otros términos, se denominan implicantes primos.
Luego la función es la suma de sus implicantes primos.
f  a c d a bd a bc  b‘ c ‘ 
b´d´ 
cd´

1, 5 
5, 7
6, 7 
0, 1, 8, 9 
0, 2, 8, 10  
2, 6, 10, 14 

Pero la expresión anterior todavía se puede reducir:
f a bd b´c cd´

Vamos a utilizar la segunda parte del método para encontrar un
conjunto mínimo de implicantes primos.
Ing. Mónica P. René_2010
21
Método de Quine McCluskey

La segunda parte del método de Quine McCluskey emplea un
gráfico de implicantes primos para seleccionar un conjunto mínimo
de implicantes primos.

A partir de la tabla anterior (tabla 1), se construye una tabla de
implicantes primos como se muestra a continuación:
(0,1,8,9)
(0,2,8,10)
(2,6,10,14)
(1,5)
(5,7)
(6,7)

b´c´
b´d´
cd´
a´c´d
a´bd
a´bc
0 1 2 3 4 5 6 7
8
x x
x
x
x
x
x
x
9
14
¤
x
x
x
10
x
x
¤
x
x x
Si un término producto está cubierto sólo mediante un implicante
primo, entonces dicho implicante primo se denomina implicante
primo esencial.
Ing. Mónica P. René_2010
22
Método de Quine McCluskey






Los implicantes primos esenciales son fáciles de encontrar y se
deben incluir en la suma mínima de productos de la función.
Si una determinada columna contiene sólo una X, entonces la
correspondiente fila es un implicante primo esencial.
En la tabla anterior, las columnas 9 y 14 contienen una sola X, por
lo que b´c´y cd´ son implicantes primos esenciales.
Cada vez que se selecciona un implicante primo esencial, se debe
tachar la fila correspondiente (ver líneas rojas en tabla siguiente).
Luego, las columnas que corresponden a todos los términos
producto cubiertos por dichos implicantes primos también deben
tacharse (ver líneas negras en tabla siguiente).
Veamos como queda la tabla.
Ing. Mónica P. René_2010
23
Método de Quine McCluskey
(0,1,8,9)
(0,2,8,10)
(2,6,10,14)
(1,5)
(5,7)
(6,7)


b´c´
b´d´
cd´
a´c´d
a´bd
a´bc
0 1 2 3 4 5 6 7
8
x x
x
x
x
x
x
x
x
x
x
9
10
14
¤
x
x
¤
x
x x
Luego se debe elegir un conjunto mínimo de implicantes primos
para cubrir las restantes columnas.
En este ejemplo a´bd cubre las dos columnas restantes.
Ing. Mónica P. René_2010
24
Método de Quine McCluskey

Cubriendo las dos columnas restantes (líneas violetas).
(0,1,8,9)
(0,2,8,10)
(2,6,10,14)
(1,5)
(5,7)
(6,7)

b´c´
b´d´
cd´
a´c´d
a´bd
a´bc
0 1 2 3 4 5 6 7
8
x x
x
x
x
x
x
x
x
x
x
9
10
14
¤
x
x
¤
x
x x
Finalmente la suma mínima de productos resultante es:
f a bd b´c cd´
Ing. Mónica P. René_2010
25
Método de Quine McCluskey






Entonces luego de seleccionar los implicantes primos esenciales,
los términos producto a los que cubren pueden eliminarse del
gráfico de implicantes mínimos, tachando las correspondientes
columnas.
Si los esenciales no cubren todos los términos producto, entonces
son necesarios implicantes primos no esenciales.
En gráficos de implicantes primos más grandes, pueden emplearse
procedimientos adicionales para reducir.
Los mapas K son útiles para funciones con tres a cinco variables.
El método de Quine McCluskey se puede utilizar en computadoras
de alta velocidad para simplificar funciones con hasta 15 variables o
más.
Para problemas con un gran número de variables pero pocos
términos, la simplificación algebraica puede ser el método más
sencillo.
Ing. Mónica P. René_2010
26
Método de Quine McCluskey



En las situaciones en las que no se requiera de una solución mínima
o en las que obtener una solución mínima requiere de una potencia
de cálculo excesiva, pueden utilizarse procedimientos herústicos.
El método Espresso-II es uno de los métodos herústicos más
populares, el cual puede generar soluciones mínimas aproximadas
para una amplia variedad de problemas.
Hasta el momento, sólo consideramos la implementación de una
única función de conmutación.
Ing. Mónica P. René_2010
27
Método de Quine McCluskey
•


•
Problemas Fundamentos de diseño lógico, Charles H. Roth,
Jr.,Thomson, 5a ed.
6.2
6.3
Segundo trabajo práctico de laboratorio
Ing. Mónica P. René_2010
28