8.5: Mapas de Karnaugh, tablas de verdad y expresiones booleanas

¿Quién desarrolló el mapa de Karnaugh?

Maurice Karnaugh, ingeniero de telecomunicaciones, desarrolló el mapa de Karnaugh en Bell Labs en 1953 mientras diseñaba circuitos de conmutación telefónica basados en lógica digital.

El uso de Karnaugh Mapa

Ahora que hemos desarrollado el mapa de Karnaugh con la ayuda de diagramas de Venn, pongámoslo en uso. Los mapas de Karnaugh reducen las funciones lógicas de manera más rápida y sencilla en comparación con el álgebra booleana. Por reducir nos referimos a simplificar, reduciendo el número de puertas y entradas. Nos gusta simplificar la lógica a una forma de menor costo para ahorrar costos mediante la eliminación de componentes. Definimos el costo más bajo como el menor número de puertas con el menor número de entradas por puerta.

Si se les da una opción, la mayoría de los estudiantes hacen simplificación lógica con mapas de Karnaugh en lugar de álgebra booleana una vez que aprenden esta herramienta.

Mostramos cinco elementos individuales anteriores, que son simplemente formas diferentes de representar lo mismo: una función lógica digital arbitraria de 2 entradas. Primero está la lógica de escalera de relés, luego puertas lógicas, una tabla de verdad, un mapa de Karnaugh y una ecuación booleana. El punto es que cualquiera de estos son equivalentes. Dos entradas A y B pueden tomar valores de 0 o 1, alto o bajo, abierto o cerrado, Verdadero o Falso, según sea el caso. Hay 2 ² = 4 combinaciones de entradas que producen una salida. Esto es aplicable a los cinco ejemplos.

Estas cuatro salidas se pueden observar en una lámpara en la lógica de escalera de relés, en una sonda lógica en el diagrama de puerta. Estas salidas se pueden registrar en la tabla de verdad, o en el mapa de Karnaugh. Mira el mapa de Karnaugh como una mesa de verdad reordenada. La salida de la ecuación booleana puede ser calculada por las leyes del álgebra booleana y transferida a la tabla de verdad o mapa de Karnaugh. ¿Cuál de las cinco descripciones lógicas equivalentes deberíamos usar? El que es más útil para la tarea a realizar.

Las salidas de una tabla de verdad corresponden uno a uno a las entradas del mapa de Karnaugh. Comenzando en la parte superior de la tabla de verdad, las entradas A=0, B=0 producen una salida α. Tenga en cuenta que esta misma salida α se encuentra en el mapa de Karnaugh en la dirección de celda A=0, B=0, esquina superior izquierda del mapa K donde se cruzan la fila A=0 y la columna B=0. Las otras salidas de la tabla de verdad β, χ, δ de las entradas AB=01, 10, 11 se encuentran en las ubicaciones correspondientes del mapa K.

A continuación, mostramos las regiones adyacentes de 2 celdas en el mapa K de 2 variables con la ayuda del diagrama rectangular de Venn anterior como regiones booleanas.

Las celdas α y χ son adyacentes en el mapa K como elipses en el mapa K más abajo a la izquierda. Refiriéndose a la tabla anterior de la verdad, no es así. Hay otra entrada de tabla de verdad (β) entre ellos. Lo que nos lleva al punto entero de organizar el mapa K en una matriz cuadrada, las celdas con cualquier variable booleana en común necesitan estar cerca unas de otras para presentar un patrón que nos salte. Para las células α y χ tienen en común la variable booleana B'. Esto lo sabemos porque B=0 (igual que B') para la columna de arriba de las celdas α y χ. Compare esto con el diagrama cuadrado de Venn sobre el mapa K.

Una línea de razonamiento similar muestra que β y δ tienen B booleano (B=1) en común. Entonces, α y β tienen A' booleano A' (A=0) en común. Finalmente, χ y δ tienen A booleana (A=1) en común. Compara los dos últimos mapas con el diagrama de Venn del cuadrado medio.

Para resumir, se busca que las variables booleanas sean comunes entre las celdas. El mapa de Karnaugh está organizado para que podamos ver esa comunalidad. Probemos algunos ejemplos.

Ejemplo:

Transfiere el contenido de la tabla de la verdad al mapa de Karnaugh de arriba.

Solución:

La tabla de verdad contiene dos 1 s. el mapa K- debe tener ambos. ubicar el primero 1 en la 2da fila de la tabla de verdad anterior.

• anotar la verdad tabla AB dirección
• localizar la celda en el mapa K que tiene la misma dirección
• colocar un 1 en esa celda

Repita el proceso para el 1 en la última línea de la tabla de verdad.

Ejemplo:

Para el mapa de Karnaugh en el problema anterior, escriba la expresión booleana. La solución está abajo.

Solución:

Busque celdas adyacentes, es decir, arriba o al costado de una celda. Las celdas diagonales no son adyacentes. Las celdas adyacentes tendrán una o más variables booleanas en común.

• Agrupar (círculo) los dos 1 s en la columna
• Encuentra la (s) variable (s) superior y/o lateral que son las mismas para el grupo, Escribe esto como el resultado booleano. Es B en nuestro caso.
• Ignorar las variables que no son las mismas para un grupo de celdas. En nuestro caso A varía, es tanto 1 como 0, ignora A booleana.
• Ignora cualquier variable que no esté asociada con celdas que contengan 1s. B' no tiene a nadie debajo. Ignorar B'
• Resultado fuera = B

Esto podría ser más fácil de ver comparando con los diagramas de Venn a la derecha, específicamente la columna B.

Ejemplo:

Escribe a continuación la expresión booleana para el mapa de Karnaugh.

Solución: (arriba)

• Agrupar (círculo) los dos 1 en la fila
• Encuentra la (s) variable (s) que son iguales para el grupo, Out = A'

Ejemplo:

Para la tabla Verdad a continuación, transfiera las salidas al Karnaugh, luego escriba la expresión booleana para el resultado.

Solución:

Transfiera los 1 s de las ubicaciones en la tabla Verdad a las ubicaciones correspondientes en el mapa K.

• Agrupar (círculo) los dos 1 en la columna bajo B=1
• Agrupar (círculo) los dos 1 en la fila derecha de A=1
• Escribir término del producto para el primer grupo = B
• Escribir término del producto para el segundo grupo = A
• Escribir Suma-de-Productos de los dos términos anteriores Salida = A+B

La solución del K-map en el medio es la solución más simple o de menor costo. Una solución menos deseable está en el extremo derecho. Después de agrupar los dos 1 s, cometemos el error de formar un grupo de 1 celda. La razón por la que esto no es deseable es que:

• La celda única tiene un término de producto de AB'
• La solución correspondiente es Output = AB' + B
• Esta no es la solución más simple

La forma de recoger este sencillo 1 es formar un grupo de dos con el 1 a la derecha del mismo como se muestra en la línea inferior del mapa K medio, a pesar de que este 1 ya ha sido incluido en el grupo de columnas (B ). Se nos permite reutilizar las células para formar grupos más grandes. De hecho, es deseable porque lleva a un resultado más sencillo.

Debemos señalar que cualquiera de las soluciones anteriores, Salida o Salida Incorrecta, son lógicamente correctas. Ambos circuitos producen la misma salida. Se trata de que el circuito anterior sea la solución de menor costo.

Ejemplo:

Rellene el mapa de Karnaugh para la expresión booleana a continuación, luego escriba la expresión booleana para el resultado.

Solución: (arriba)

La expresión booleana tiene tres términos de producto. Habrá un 1 ingresado por cada término del producto. Aunque, en general, el número de 1 s por término de producto varía con el número de variables en el término del producto en comparación con el tamaño del K-map. El término del producto es la dirección de la celda donde se ingresa el 1. El primer término del producto, A'B, corresponde a la celda 01 del mapa. En esta celda se ingresa un 1. Los otros dos términos P se ingresan por un total de tres 1s

A continuación, se procede a agrupar y extraer el resultado simplificado como en el problema de tabla de verdad anterior.

Ejemplo:

Simplifique el diagrama lógico a continuación.

Solución: (Figura abajo)

• Escribe la expresión booleana para el diagrama lógico original como se muestra a continuación
• Transfiere los términos del producto al mapa de Karnaugh
• Formar grupos de celdas como en ejemplos anteriores
• Escribir expresión booleana para grupos como en ejemplos anteriores
• Dibujar diagrama lógico simplificado

Ejemplo:

Simplifique el diagrama lógico a continuación.

Solución:

• Escribe la expresión booleana para el diagrama lógico original que se muestra arriba
• Transfiere los términos del producto al mapa de Karnaugh.
• No es posible formar grupos.
• No es posible simplificar; déjalo como está.

No es posible simplificar la lógica para el diagrama anterior. Esto a veces sucede. Ni los métodos de los mapas de Karnaugh ni el álgebra booleana pueden simplificar aún más esta lógica. Mostramos arriba un símbolo esquemático de O exclusivo; sin embargo, esto no es una simplificación lógica. Simplemente hace que un diagrama esquemático se vea mejor. Dado que no es posible simplificar la lógica Exclusive-OR y es ampliamente utilizada, es proporcionada por los fabricantes como circuito integrado básico (7486).