Karnaugh

Funciones Canonicas

Las funciones booleanas se representan de formas canónicas, es decir Suma de productos (SOP) y Productos de Suma (POS).

En otras palabas, los Minitérminos son sumas de productos (se toma las salidas 1) y los Maxitérminos son productos de sumas (se toman las salidas 0).

A los Minitérminos, se le niegan los 0 de la función y a los Maxitérminos los 1 de la función.

Karnaugh

Un mapa de Karnaugh proporciona un método sistemático de simplificación de expresiones booleanas y, si se aplica adecuadamente, genera las expresiones suma de productos y producto de sumas más simples posibles, conocidas como expresiones mínimas. Un mapa de Karnaugh es similar a una tabla de verdad, ya que muestra todos los valores posibles de las variables de entrada y la salida resultante para cada valor.

En lugar de organizar en filas y columnas como una tabla de verdad, el mapa de Karnaugh es una matriz de celdas en la que cada celda representa un valor binario de las variables de entrada. Las celdas se organizan de manera que la simplificación de una determinada expresión consiste en agrupar adecuadamente las celdas. El número de celdas de un mapa de Karnaugh es igual al número total de posibles combinaciones de las variables de entrada, al igual que el número de filas de una tabla de verdad. Para tres variables, el número de celdas necesarias es de 2^3 = 8. Para cuatro variables, el número de celdas es de 2^4 = 16.

Imaginemos el mapa de Karnaugh como si fuera una "rosca" en donde las adyacencias de las puntas se comunican entre ellas, siendo así que en forma de "tubo" se pueden hacer la minimizaciones de los términos

Construcción de mapas de Karnaugh

Mapa de 3 variables

Mapa de 4 variables

Numeración de las celdas

El número de cada casilla es el número de minitérmino, el mismo que aparece en la tabla de verdad. Se arma con los bits de la fila como parte alta y los de la columna como parte baja, porque la variable de las filas (A) es la de más peso.

En un mapa de 3 variables las filas valen 4 y las columnas 2 y 1: la fila 1 con la columna 01 es el minitérmino 4 + 1 = 5. En uno de 4 variables las filas valen 8 y 4, y las columnas 2 y 1: la fila 10 con la columna 01 es el minitérmino 8 + 1 = 9.

El mapa de Karnaugh invierte los dos últimos bits en la secuencia de combinaciones de variables (por ejemplo, 00, 01, 11, 10) por una razón fundamental:

1. Garantizar que solo un bit cambie entre celdas adyacentes

• En un mapa de Karnaugh, cada celda debe diferir en un solo bit con sus vecinas (horizontal o verticalmente). Esto se debe al código Gray (o código reflejado), que evita discontinuidades al pasar de una combinación a otra.
• Si se usara el orden binario estándar (00, 01, 10, 11), al pasar de 01 a 10, cambiarían dos bits simultáneamente (el primero y el segundo), lo que rompería la adyacencia lógica y complicaría la simplificación de términos.

2. Ejemplo práctico

• Orden binario normal:00 → 01 (cambia el bit menos significativo).01 → 10 (cambian ambos bits ❌).
• Orden del mapa de Karnaugh (código Gray):00 → 01 (cambia el segundo bit).01 → 11 (cambia el primer bit).11 → 10 (cambia el segundo bit).Resultado: Cada transición modifica solo un bit (✔️ ideal para agrupar términos adyacentes).

3. Importancia en la simplificación

• Los grupos de celdas adyacentes en el mapa de Karnaugh representan términos lógicos simplificables.
• Si dos celdas difieren en más de un bit, no pueden combinarse para eliminar variables (ejemplo: 01 y 10 no comparten literales comunes).

Las reglas de un grupo

Un grupo de celdas es válido cuando cumple todo esto:

• Sus celdas forman un rectángulo (o un cuadrado).
• La cantidad de celdas es una potencia de 2: 1, 2, 4, 8 o 16. Por eso un grupo de 3 celdas no existe, ni uno de 3 filas.
• Todas sus celdas valen lo mismo: todo 1 (para la suma de productos) o todo 0 (para el producto de sumas). Se pueden mezclar con X, que son justamente las que permiten agrandar el grupo.
• Un grupo de puras X no sirve: no aporta nada.

Los grupos se pueden solapar: una misma celda puede estar en dos grupos, y eso suele ser necesario.

Redundancias (las X)

Con n entradas son posibles 2ⁿ combinaciones de variables. Pero en muchas aplicaciones algunas de esas combinaciones no existen o no tienen sentido: nunca van a aparecer en las entradas del circuito. Por ejemplo, en una aplicación decimal se usan solo los 10 dígitos, así que de las 16 combinaciones posibles con 4 variables, 6 quedan sin uso (de la 1010 a la 1111). A esas combinaciones se las llama redundancias, y como se asume que nunca se van a presentar, se pueden usar a favor para simplificar el circuito.

En el mapa de Karnaugh las redundancias se marcan con una X en la celda. Al agrupar los 1, cada X se puede tomar como un 1, para agrandar el grupo, o como un 0, si no da ninguna ventaja. La regla es simple: la X se usa solo si con ella el grupo queda más grande, porque cuanto mayor es el grupo, más simple es el término resultante.

Ejemplo con un mapa de 3 variables (filas A, columnas BC) y la función Σm(0, 1), con redundancias en las celdas 2 y 3:

• Sin usar las X: los dos 1 forman un grupo de 2 (celdas 0 y 1), que da AB.
• Usando las X como 1: las cuatro celdas de la fila A = 0 (0, 1, 3 y 2) forman un grupo de 4, que da A: una variable menos, un circuito más simple.

El ejemplo dibujado con el Resolvedor de mapas de Karnaugh: las celdas 0 y 1 valen 1, las celdas 3 y 2 son redundancias (X), y las cuatro juntas forman el grupo de 4.

Las X no obligan a nada: si una X no ayuda, se la deja afuera (equivale a un 0), y una X que queda sin cubrir no es un error. Lo único que no sirve es armar un grupo de puras X, porque no aporta ningún 1 a la función. En el Resolvedor de mapas de Karnaugh las celdas giran entre vacío, 1, 0 y X (no importa), que es otro nombre para las redundancias.

Solución mapa de Karnaugh

SOP

1 -> A

0 -> ~A

Se usan los 1 de la función

⅀ (...)+(...)

POS

1 -> ~A

0 -> A

Se usan los 0 de la función

∏ (+++).(+++)

Los mapas de Karnaugh se resuelven uniendo términos (en el ejemplo los 1) y realizando la minimización de los términos dependiendo si es SOP o POS.

Ejemplo:

En este caso la función vale 1 en las celdas 3 (011), 7 (111), 4 (100) y 5 (101), y se agrupan de a dos:

• En el grupo vertical (3 y 7) la variable A cambia (se descarta), mientras que B y C no cambian y valen 1: queda B · C.
• En el grupo horizontal (4 y 5) la que cambia es C (se descarta); A vale 1 y B vale 0, así que va B negado: queda A · B.

El resultado es F = A · B + B · C.

Acá se busca la función por los 0 (producto de sumas). Los 0 están en las celdas 0 (000), 1 (001), 2 (010) y 6 (110), y se agrupan de a dos igual que antes:

• En el grupo 0 y 1, A y B valen 0 y C cambia (se descarta): queda A · B.
• En el grupo 2 y 6, B vale 1 y C vale 0, y A cambia (se descarta): queda B · C.

Agrupar los 0 da la función negada: F = AB + BC. Para volver a F se niega todo y se aplica De Morgan:

Resultado: F = (A + B) · (B + C).

Ejemplo con 4 variables

Con 4 variables el mapa tiene 16 celdas (filas AB, columnas CD), pero el método es el mismo. Sea F = Σm(0, 1, 4, 5, 6, 7, 12, 14, 15), con tres grupos de distinto tamaño:

• Grupo 1 (0, 1, 4 y 5): bloque de 4 arriba a la izquierda. B y D cambian (se descartan); A y C se mantienen en 0: queda A · C.
• Grupo 2 (6, 7, 14 y 15): bloque de 4 al medio. A y D cambian; B y C se mantienen en 1: queda B · C.
• Grupo 3 (12 y 14): par en la fila de abajo. La celda 14 ya estaba en el grupo 2, pero la 12 es exclusiva de este grupo, así que el solapamiento vale. C cambia; A, B y D se mantienen (1, 1 y 0): queda A · B · D.

Resultado: F = AC + BC + ABD.

Ejemplo con 5 variables

La mejor forma de entender el mapa de 5 variables es mirar el de 4: son dos hojas iguales a la del ejemplo anterior (grilla de 4×4, filas AB, columnas CD), una al lado de la otra. La hoja de la izquierda es para A = 0 y lleva los minitérminos 0 a 15; la de la derecha es para A = 1 y lleva las mismas celdas numeradas de 16 a 31 (misma celda, +16). Todo lo que vale para 4 variables sigue valiendo adentro de cada hoja.

La única regla nueva es la de los grupos que cruzan de hoja: para que un grupo elimine la variable A, tiene que ser el mismo rectángulo en las dos hojas (mismas filas y mismas columnas). Si el grupo vive en una sola hoja, se resuelve exactamente como en 4 variables y A queda en el término. Sea F = Σm(0, 2, 4, 6, 9, 11, 16, 18, 19, 20, 22):

• Grupo 1: el bloque (0, 2, 4, 6) de la hoja A = 0 repetido en la hoja A = 1 como (16, 18, 20, 22): el mismo rectángulo en las dos. Dentro del bloque C y D cambian; B y E se mantienen en 0, y A se elimina por estar el grupo en las dos hojas: queda B · E.
• Grupo 2 (9 y 11, solo en la hoja A = 0): D cambia; B, C y E se mantienen (1, 0 y 1): queda B · C · E. Como no está en la otra hoja, A no se puede eliminar.
• Grupo 3 (18 y 19, solo en la hoja A = 1): D cambia; B, C y E se mantienen (0, 0 y 1), y A va porque el grupo no cruza de hoja: queda A · B · C · E.

Resultado: F = BE + BCE + ABCE.