Un mapa de Karnaugh — abreviado como mapa K — es un método gráfico para simplificar funciones booleanas. Ordena los minterms de modo que las celdas vecinas difieran en un bit de entrada, haciendo visibles las combinaciones útiles. Agrupar los 1 produce una forma de suma de productos (SOP); agrupar los 0 produce una forma de producto de sumas (POS). El mapa ayuda a encontrar una forma mínima de dos niveles según un criterio de coste definido; por sí solo no determina el circuito de menor coste para toda tecnología o modelo de puertas.
Fue presentado por Maurice Karnaugh en 1953, basándose en una cuadrícula similar que Edward Veitch había propuesto un año antes — por eso algunos libros de texto todavía lo llaman diagrama de Veitch. Ambos nombres describen la misma herramienta.
¿Por qué minimizar una expresión Booleana?
Cada AND, OR y NOT de una expresión Booleana se convierte en una puerta lógica física cuando se construye el circuito. Menos términos y menos literales por término significa menos puertas.
Combinar minterms adyacentes puede reducir la cantidad de literales y términos producto de una expresión de dos niveles. A menudo da una implementación más simple que escribir un minterm por cada fila de la tabla. El área física, el retardo y el consumo siguen dependiendo de las puertas disponibles, la cantidad de entradas por puerta, la carga y la estructura del circuito; una expresión factorizada de varios niveles puede tener otro coste. Consulta la comparación entre lógica de dos y varios niveles (en inglés).
De la tabla de verdad al mapa
Una tabla de verdad enumera cada combinación de entradas y su salida. Un mapa K reorganiza esas mismas filas en una cuadrícula, con una diferencia crucial: las celdas adyacentes en la cuadrícula siempre difieren en exactamente un bit de entrada.
Por qué importa el orden en código Gray
Esa propiedad de diferencia de un solo bit proviene del orden en código Gray (00, 01, 11, 10) en lugar del conteo binario normal (00, 01, 10, 11) en cada eje.
Leer un mapa K: ejemplos resueltos por tamaño
La mecánica se mantiene idéntica en cualquier tamaño — solo cambian las dimensiones de la cuadrícula. Tres tamaños, resueltos completamente a continuación.
2 variables
Toma una función que da como salida 1 siempre que B es 1, sin importar A — minterms 1 y 3.
| A\B | 0 | 1 |
|---|---|---|
| 0 | 00 | 11 |
| 1 | 20 | 31 |
Los dos 1 están en la misma columna, lo que significa que B es 1 en ambos y A no influye en ninguno de los dos.
Agruparlos da directamente la expresión mínima: F = B. Sin necesidad de álgebra — la adyacencia hizo el trabajo.
3 variables
Con tres variables el mapa todavía cabe en una sola cuadrícula — dos filas (para A) por cuatro columnas (para B, C en orden de código Gray 00, 01, 11, 10).
Considera los minterms 0, 2, 4, 6 — cada caso donde C es 0. Cada 1 en este mapa tiene C = 0, y cada 0 tiene C = 1, así que la función completa se reduce a F = C′ — un solo literal, sin importar lo que hagan A y B.
Cómo resolver un mapa de Karnaugh de 4 variables: ejemplo completo
Este es el tamaño que más cursos usan para enseñar la agrupación correctamente — suficientemente grande para requerir decisiones reales de agrupación, pero aún cabe en una sola cuadrícula.
Configurando la cuadrícula
Toma F(A,B,C,D) = Σm(0,1,2,5,6,7,8,9,10,14):
| AB\CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 01 | 11 | 30 | 21 |
| 01 | 40 | 51 | 71 | 61 |
| 11 | 120 | 130 | 150 | 141 |
| 10 | 81 | 91 | 110 | 101 |
Agrupando las celdas
- B′C′ — un grupo envolvente de cuatro esquinas que cubre {0,1,8,9}
- CD′ — una columna completa de cuatro celdas que cubre {2,6,10,14}
- A′BD — un par que cubre las dos celdas restantes {5,7}
Tres grupos cubren cada 1 exactamente una vez entre todos ellos, sin que sea posible ninguna agrupación más pequeña para ninguno de los tres.
Escribiendo la expresión final
Las reglas de agrupación, con precisión
- El tamaño del grupo debe ser una potencia de 2 — 1, 2, 4, 8, 16 celdas. Nunca 3, 5, 6 o 7.
- Los grupos deben ser rectangulares (incluyendo rectángulos envolventes — ver más abajo), nunca una forma irregular.
- El mapa se envuelve sobre sus propios bordes. La columna más a la izquierda y la más a la derecha son adyacentes, y la fila superior e inferior son adyacentes, porque el orden en código Gray hace que la primera y última entrada también difieran en solo un bit. Esto es lo que más comúnmente se pasa por alto.
- Cada 1 requerido debe estar cubierto por al menos un grupo, pero los grupos pueden superponerse.
- Usa los grupos maximales como candidatos. Un grupo mayor reduce los literales de su término, pero elegir por separado el grupo mayor para cada celda no siempre produce la cobertura más pequeña.
Cómo elegir una cobertura mínima
Primero identifica los implicantes primos: todos los grupos maximales válidos que no pueden ampliarse sin incluir un 0 especificado. Después selecciona cada implicante primo esencial, porque es el único candidato que cubre al menos un 1 requerido. Si quedan 1 sin cubrir, compara combinaciones de los implicantes restantes hasta cubrirlos todos. No hagas esa elección celda por celda: los grupos se superponen y un candidato puede cubrir varias celdas pendientes a la vez.
El criterio de coste importa. Un grupo mayor tiene menos literales en su término individual, pero una expresión completa es un conjunto de términos; una elección local de grupo máximo puede dejar celdas que necesiten términos adicionales. Este solucionador minimiza primero la cantidad de términos y, entre las coberturas con esa cantidad, el total de literales. Sigue el criterio indicado en tu ejercicio. Si ningún implicante primo es esencial, el método de Petrick evalúa sistemáticamente las opciones de cobertura; consulta también la explicación de implicantes primos esenciales y no esenciales (en inglés).
Condiciones de indiferencia
Algunas combinaciones de entrada nunca ocurren realmente en un sistema real, o su salida genuinamente no importa. Marcadas como X en el mapa, una indiferencia puede tratarse como 0 o como 1 — lo que ayude a formar un grupo más grande.
Nunca es obligatorio cubrirlas, solo se usan de manera oportunista. Guía completa: Handling Don't-Care Conditions in K-Maps (en inglés).
Más allá de 4 variables
Una sola cuadrícula plana deja de ser práctica más allá de 4 variables — una cuadrícula 2D no puede mantener cada celda adyacente a cada celda que difiere en un bit una vez que hay más de 4 bits que rastrear.
La solución estándar: dividir las variables adicionales en mosaicos de mapa separados. Una función de 5 variables se convierte en dos mapas de 4 variables; una función de 6 variables se convierte en cuatro. La adyacencia entre celdas correspondientes en distintos mosaicos sigue contando. Recorrido completo: mapas de Karnaugh de 5 y 6 variables con varios mosaicos.
Puntos clave
- Un mapa K convierte la adyacencia de una tabla de verdad en algo visible, usando el orden en código Gray para que cada celda vecina difiera en exactamente un bit.
- Los grupos válidos siempre tienen un tamaño potencia de 2 (1, 2, 4, 8...) y siempre son rectangulares, incluyendo rectángulos envolventes a través de los bordes del mapa.
- Usa los grupos maximales como candidatos y luego elige una cobertura mínima para todo el mapa; escoger primero el grupo mayor en cada celda no basta.
- Las indiferencias pueden incorporarse a un grupo de manera oportunista, pero nunca es obligatorio cubrirlas.
- Más allá de 4 variables, los diseños de múltiples mosaicos mantienen las mismas reglas funcionando en 5 y 6 variables.
A dónde ir después
Agrupar a simple vista funciona bien para aprender y para mapas pequeños. El mismo problema de implicantes primos y selección de cobertura puede resolverse sistemáticamente con Quine-McCluskey (en inglés), mientras que el método de Petrick resuelve las opciones restantes cuando los grupos esenciales no bastan.