Mapa de Karnaugh
El mapa de Karnaugh ( KM o K-map ) es un método para simplificar expresiones de álgebra booleana . Maurice Karnaugh lo introdujo en 1953 [1] [2] como un refinamiento del gráfico de Veitch de 1952 de Edward W. Veitch , [3] [4] que fue un redescubrimiento del diagrama lógico de Allan Marquand de 1881 [5] también conocido como diagrama de Marquand [4] pero con un enfoque ahora puesto en su utilidad para cambiar circuitos. [4] Por lo tanto, los gráficos de Veitch también se conocen como diagramas de Marquand-Veitch ,[4] y los mapas de Karnaugh como mapas de Karnaugh-Veitch ( mapas KV ).
El mapa de Karnaugh reduce la necesidad de cálculos extensos al aprovechar la capacidad de reconocimiento de patrones de los humanos. [1] También permite la rápida identificación y eliminación de posibles condiciones de carrera .
Los resultados booleanos requeridos se transfieren de una tabla de verdad a una cuadrícula bidimensional donde, en los mapas de Karnaugh, las celdas se ordenan en código Gray , [6] [4] y cada posición de celda representa una combinación de condiciones de entrada. Las celdas también se conocen como minitérminos, mientras que cada valor de celda representa el valor de salida correspondiente de la función booleana. Se identifican grupos óptimos de 1 o 0, que representan los términos de una forma canónica de la lógica en la tabla de verdad original. [7] Estos términos se pueden usar para escribir una expresión booleana mínima que represente la lógica requerida.
Los mapas de Karnaugh se utilizan para simplificar los requisitos lógicos del mundo real para que puedan implementarse utilizando un número mínimo de puertas lógicas. Una expresión de suma de productos (SOP) siempre se puede implementar usando puertas AND que alimentan una puerta OR , y una expresión de producto de sumas (POS) conduce a puertas OR que alimentan una puerta AND. La expresión POS da un complemento de la función (si F es la función entonces su complemento será F'). [8] Los mapas de Karnaugh también se pueden utilizar para simplificar expresiones lógicas en el diseño de software. Condiciones booleanas, como se usa, por ejemplo, en declaraciones condicionales, puede volverse muy complicado, lo que hace que el código sea difícil de leer y mantener. Una vez minimizadas, las expresiones canónicas de suma de productos y producto de sumas se pueden implementar directamente mediante operadores lógicos AND y OR. [9]
Los mapas de Karnaugh se utilizan para facilitar la simplificación de las funciones del álgebra booleana . Por ejemplo, considere la función booleana descrita por la siguiente tabla de verdad .
A continuación se presentan dos notaciones diferentes que describen la misma función en álgebra booleana no simplificada, utilizando las variables booleanas A , B , C , D y sus inversas.
