Expresiones booleanas minimales
Considérese una expresión E en un álgebra de Boole B. Como E puede representar un circuito lógico, es posible que pretendamos obtener una expresión F que, siendo equivalente a la expresión original, sea en algún sentido mínima; de esta forma, lograríamos minimizar la cantidad de compuertas lógicas utilizadas para implementar la operación buscada, con la consiguiente economía de recursos. Aquí nos concentraremos en la forma minimal de las expresiones booleanas que están en forma de suma de productos.
Si E es una expresión booleana en forma de suma de productos, EL denota el número de literales en E (contados con sus repeticiones) y ES denota el número de sumandos en E.
Por ejemplo, si E es la siguiente expresión:
abc abd abcd abcd
entonces EL=14 y ES=4.
Sea ahora F una expresión booleana de suma de productos equivalente a E. Decimos que E es más simple que F si se cumple que:
EL ≤FL y ES ≤FS
y por lo menos una de las relaciones es una desigualdad estricta.
Una expresión booleana E está en forma minimal de suma de productos si está en forma de suma de productos y no hay ninguna otra expresión equivalente en forma de suma de productos que sea más simple que E.
Mapas de Karnaugh
El método de los mapas de Karnaugh es un método gráfico para encontrar las formas minimales de sumas de productos para expresiones booleanas que involucran un máximo de seis variables. Aquí sólo trataremos los casos de dos, tres y cuatro variables.
Dado un conjunto de variables {A1, A2, …, AN}, pueden con ellas formarse los
productos fundamentales Pi que contienen todas las variables, o bien en su forma
complementada o bien en su forma no complementada. De tales productos fundamentales, se dice que P1 y P2 son adyacentes si difieren exactamente en un literal, el cual tiene que ser una variable complementada en uno de los productos y no complementada en el otro.
Por ejemplo, si el conjunto de variables es {A, B, C, D}:
• Entre los productos fundamentales ABC , ABC , ACD no puede predicarse la relación de adyacencia, porque tales productos no contienen todas las variables.
• Los pares de productos ABCD y ABCD , o ABCD y ABCD, o ABCD y ABCD no
son adyacentes porque difieren en más de un literal.
• Los pares de productos ABCD y ABCD, o ABCD y ABCD , o ABCD y ABCD son adyacentes, porque difieren exactamente en un literal, que es una variable
complementada en uno de los productos y no complementada en el otro.
En un mapa de Karnaugh, cada uno de los productos fundamentales Pi que contienen todas las variables es representado gráficamente por un cuadrado, y la relación de adyacencia entre tales productos es representada por la adyacencia geométrica.
Mapas de Karnaugh de dos variables
Sean las variables A y B. Con ellas pueden formarse cuatro productos fundamentales Pi que contienen todas las variables:
AB AB AB AB
Cada uno de estos productos será representado por un cuadrado en la siguiente gráfica, respetando la relación de adyacencia:
En esta gráfica, todos los productos fundamentales se representan mediante grupos de 2n (20 o 21) cuadrados adyacentes:
Mapas de Karnaugh de tres variables
Sean las variables A, B y C. Con ellas pueden formarse ocho productos fundamentales Pi que contienen todas las variables:
ABC ABC ABC ABC ABC ABC ABC ABC
Cada uno de estos productos será representado por un cuadrado en la siguiente gráfica, respetando la relación de adyacencia:
Nótese que, en este caso, los cuadrados de los extremos izquierdo y derecho también se consideran adyacentes entre sí, como si la gráfica fuera un cilindro unido por ambos extremos.
En esta gráfica, todos los productos fundamentales se representan mediante grupos de 2n (20 o 21 o 22) cuadrados adyacentes.
Mapas de Karnaugh de cuatro variables
Sean las variables A, B, C y D. Con ellas pueden formarse dieciséis productos fundamentales Pi que contienen todas las variables:
ABCD ABCD ABCD ABCD ABCD ABCD ABCD ABCD
ABCD ABCD ABCD ABCD ABCD ABCD ABCD ABCD
Cada uno de estos productos será representado por un cuadrado en la siguiente gráfica, respetando la relación de adyacencia:
Análogamente al caso de tres variables, en este caso los cuadrados de los extremos izquierdo y derecho también se consideran adyacentes entre sí, y los cuadrados de los extremos superior e inferior también se consideran adyacentes entre sí.
En esta gráfica, todos los productos fundamentales se representan mediante grupos de 2n (20 o 21 o 22 o 23) cuadrados adyacentes. Dada la cantidad de productos fundamentales, sólo presentaremos algunos casos.
Minimización de circuitos mediante mapas de Karnaugh
Considérese una expresión booleana E en forma de suma de productos. A fin de
encontrar la expresión booleana F equivalente a E en forma minimal de suma de productos, se siguen los siguientes pasos:
• Se construye la gráfica de Karnaugh, de acuerdo con el número de variables de E.
• En dicha gráfica se representan todos los productos fundamentales de E mediante cruces.
• Se encierran todas las cruces mediante óvalos que contengan 2n cruces adyacentes.
Cada óvalo debe encerrar la mayor cantidad posible de cruces.
• Se escribe la expresión F como suma de los productos fundamentales representados por los óvalos resultantes.
Veamos cómo funciona este método mediante ejemplos.
Ejemplos Nº1: Sea la siguiente expresión E, encuentre su forma mínima de suma de productos F y dibuje el circuito correspondiente.
1.a) E = AB + AB + B
b) E = ABC + ABC + AB + AB
No hay comentarios.:
Publicar un comentario