3.3 Mapa de Karnaugh | Introducción a la Automatización Industrial (2024)

Figura 3.1: Descripción del mapa de Karnaugh

3.3.1 Simplificación de una función lógica expresada en DNF

Dada la tabla de Karnaugh correspondiente a una función lógica expresada en DNF, el procedimiento para su simplificación se describe a continuación.

En primer lugar, se agrupan las celdas con valor ‘1’ de la tabla teniendo en cuenta las siguientes reglas:

1. Un grupo está formado por un número variable de celdas con valor ‘1’.
2. El número de celdas con valor ‘1’ dentro de un grupo debe ser potencia de dos: 1, 2, 4, 8, 16.
3. A efectos de la formación de grupos se debe considerar la tabla como toroidal, pues los extremos de la tabla son adyacentes: el extremo derecho es adyacente al izquierdo, y el inferior al superior. Se puede apreciar mejor en la Fig. 3.225.
4. Todas las celdas con valor ‘1’ deben pertenecer al menos a un grupo.
5. Una celda con valor ‘1’ puede pertenecer a varios grupos distintos.
6. El número de grupos debe ser mínimo.
7. Cuanto mayor sea el tamaño del grupo, mayor será la simplificación, tanto en número de términos como en número de literales por cada término.
8. No es necesario que todos los grupos tengan el mismo tamaño.
9. Por último, puede darse el caso de que la función contenga alguna interpretación ‘x’ que no sea posible (por ejemplo, por representar parte de un sistema físico con combinaciones de entradas que son físicamente imposibles). A las celdas correspondientes a esas interpretaciones se les asigna un valor ‘x’. Dichas celdas no tienen por qué pertenecer a ningún grupo, pero pueden emplearse para agrandar grupos ya existentes.

En segundo lugar, cada grupo generará un minitérmino en la función mínima resultante. Ese minterm estará formado por aquellos literales comunes dentro del grupo correspondiente, con signo negativo o positivo si toman el valor ‘0’, o ‘1’ en la codificación Gray. Los literales que aparecen con códigos distintos en el grupo se eliminan.

La función resultante DNF, compuesta por la suma de los minitérminos correspondientes de cada grupo, es mínima.

A modo de ejemplo, se considera la función lógica expresada en la tabla de verdad 3.9:

Al tener 3 variables tendremos 2³ = 8 celdas. Para construir la codificación Gray inicial, las variables se pueden agrupar como se quieran. En este caso representaremos a y b juntas (columnas) frente a c (filas). La tabla de Karnaugh, con dos formas de representar las cabeceras de filas y columnas, aparece en la Fig. 3.3.

En la representación de la izquierda, las cabeceras de las filas y columnas representan con una raya gris los literales positivos (variables con valor ‘1’). Consecuentemente, la ausencia de raya indica los literales negativos (variables con valor ‘0’). En la representación de la derecha aparecen explícitamente los valores de las entradas. En este libro usaremos la notación de la izquierda para las tablas de Karnaugh por su sencillez.

Una vez tenemos la tabla de Karnaugh agrupamos los unos. Como hay 5 celdas con valor ‘1’ no se puede agrupar a todos en un mismo grupo porque no es una potencia de dos. Pero vemos que sí se puede hacer un grupo de 4 unos: el rojo. El ‘1’ que queda suelto podría formar un grupo el sólo, pero si se junta con la celda de valor ‘1’ de la fila inferior se obtiene un grupo más grande: el azul.

El término asociado al grupo rojo sería \(y = c\), ya que dicho literal es el único común a todo el grupo (observe que a y b aparecen con distinto signo -toman valores tanto ‘1’ como ‘0’). El término asociado al grupo azul sería \(y = \overline{a}·b\), porque en este grupo a vale siempre ‘0’ y b siempre ‘1’ mientras que aparecen literales positivos y negativos de la variable c.En consecuencia, la función simplificada sería:

\[y=c+\overline{a}·b\]

3.3.2 Simplificación de una función lógica expresada en CNF

La simplificación de una función en forma canónica CNF es dual con respecto a la metodología vista en la sección anterior para una forma canónica DNF.

Según lo expuesto en la sección 3.2.2, cada fila de ceros de la tabla de verdad produce un maxitérmino de la forma CNF con los signos de los literales opuestos a los valores de las celdas de la tabla. La tabla de Karnaugh, a partir de los maxitérminos, se obtiene de la misma forma que para los minitérminos. La agrupación de las celdas de dicha tabla con valor ‘1’ conduce a los maxitérminos simplificados de la forma canónica CNF original. Se deja al alumno que emplee esta metodología para obtener la simplificación del ejemplo anterior (tabla de la Fig. 3.3).

Como metodología alternativa, y partiendo de la tabla de Karnaugh obtenida para los minitérminos en la sección anterior (Fig. 3.3), se puede obtener la fórmula CNF mínima agrupando las celdas con valor ‘0’ de dicha tabla de acuerdo con las reglas generales ya expuestas (ver Fig. 3.4, agrupaciones violeta y verde). Si se razona de esta forma, cada grupo de celdas con valor ‘0’ produce un maxitérmino siempre y cuando se consideren sus literales con signo opuesto a los que les corresponden en la codificación Gray de la tabla de Karnaugh original.

En el ejemplo, el término asociado al grupo violeta es \(y=(c+b)\), pues c siempre aparece negado (y consideramos el literal con el signo cambiado), b también aparece siempre negado (así que aparece con signo también positivo) y a cambia de signo (con lo que se elimina). Razonando de la misma manera puede verse que el término asociado al grupo verde es \(y=(c+\overline{a})\). La función mínima CNF es, por tanto:

\[y=(c+b)·(c+\overline{a})\]

Ejercicio.-Demuestre que las expresiones canónicas mínimas CNF y DNF obtenidas corresponden a la misma función (tienen exactamente las mismas interpretaciones que las satisfacen).