TRABAJO DISCRETA

Matematica Discreta

MAPAS
DE
KARNAUGH

.

Matematica Discreta

.

1. CONCEPTOS
Es la representación gráfica de una función booleana, ha sido utilizada desde 1953. Permite
entender los principales conceptos sobre minimización de funciones, pero su uso práctico está
limitado a un número relativamente bajo de variables, no más de 5 o 6.
Existe una relación uno a uno entre un mapa y una tabla deverdad. Una tabla tiene un renglón
por cada mintérmino, y un mapa, como se verá, tiene un casillero o cuadro asociado a cada
mintérmino.
El mapa también puede ser considerado una extensión de los diagramas de Venn. Consideremos
un diagrama de Venn para dos variables A y B:
Fig. 1.1 Mintérminos de dos variables
en un diagrama de Venn.

Si el orden de las variables para la asignación del código demintérminos es AB, se puede rotular el
diagrama con el número decimal asociado al mintérmino, queda:

Fig. 1.2 Códigos decimales de
Mintérminos en un diagrama de
Venn.

Puede observarse que resultan áreas desiguales para cada mintérmino; y que el gráfico refleja las
adyacencias entre mintérminos, pero no tan claramente como un 2-cubo, el cual se muestra en la
Figura 1.3

Fig. 1.3 Mintérminos de dosvariables en un 2-cubo.

En un mapa de Karnaugh para cada mintérmino se adopta un área de igual tamaño y forma cuadrada;
y además, estos cuadrados se disponen de tal forma que reflejen las adyacencias. En la Figura 5.4, se
ha superpuesto el 2-cubo, con un mapa de dos variables.

Matematica Discreta

.

Fig. 1.4 Mintérminos de dos variables
en un mapa de Karnaugh

La identificación de los cuadroscon el número del mintérmino, depende de la elección del orden de las
variables que se haya elegido para la representación decimal equivalente. Por ejemplo, para dos
variables A y B:

Fig. 1.5 Número decimal de los mintérminos y el orden de las variables.

La representación de funciones mediante mapas, se logra marcando los mintérminos presentes con un
"1"; los ceros suelen omitirse. Por ejemplo,las funciones AND y OR, de dos variables, se representan
en mapas según:

Fig. 1.6 Representación de funciones de dos variables en un mapa.

Nótese que:

y que;

MAPA PARA TRES VARIABLES.
Para tres variables, en orden: A, B y C, se ilustran los mintérminos en un diagrama de Venn y en un
3-cubo:

Matematica Discreta

.

Fig. 1.7 Diagrama de Venn para tres variables y un 3-cubo.

Los códigos de losmintérminos quedan ordenados según código Gray. El 3-cubo muestra también la
propiedad del código Gray de ser reflejado, la cara 0231 y la cara 4675 son 2-cubos con A=0 y
A=1 respectivamente.

Fig. 1.8 Del 3-cubo al mapa de Karnaugh de tres variables.

Desarrollo de un 3-cubo sobre el mapa de Karnaugh de tres variables:

Fig. 1.9 Mapa de Karnaugh de tres variables y un 3-cubo.

MatematicaDiscreta

.

2. FORMAS DE MAPAS
A continuación se ilustran mapas, para 3, 4 y 5 variables. Los valores de columnas y renglones se
ordenan empleando código Gray, para reflejar mejor las adyacencias. El orden de las variables, para
la representación decimal equivalente del mintérmino, figura en la base de cada mapa.

Fig. 2.1 Mapas de Karnaugh para tres y cuatro variables

Una forma alternativa deidentificar los mintérminos, indicando las zonas donde las variables toman
valor uno.

Fig. 2.2 Mapa de Karnaugh para tres variables

Nótese que el mapa de 5 variables se obtiene a partir de dos mapas de cuatro variables. A uno se le
antecede un cero en la codificación de las columnas y al otro un 1.

Fig. 2.3 Mapa de Karnaugh de cinco variables, codificado en Gray.

Matematica Discreta

.

Sin embargoesta forma de generar mapas, no refleja bien las adyacencias.
En un mapa de cinco variables cada mintérmino tiene cinco adyacentes, pero sólo pueden dibujarse
cuatro cuadrados adyacentes en un lado a un cuadrado. Por ejemplo, en la Figura 5.13, se visualiza
bien que el mintérmino 5 tiene adyacentes los mintérminos: 1, 4, 7 y 13; pero no tan claramente
que también es adyacente al 21.
Otra forma es...