Formas de Funciones Booleanas

Forma canónica de funciones booleanas La importancia de la forma canónica estriba en el hecho de ser UNICA. Como vimos anteriormente una función puede tener infinidad de representaciones, pero solo una representación en forma canónica. Existen dos formas canónicas de una función: Suma De Productos o Producto de Sumas. (También de una manera mas formal Suma de minterminos o Producto de maxterminos) Para obtener algebraicamente la forma canónica de una función podemos utilizar los teoremas de expansión canónica: Teorema 1: Para obtener la forma canónica de una función suma de productos se multiplicará por un termino de la forma (X +  ) donde falte un literal para que el termino sea canónico. Teorema 2: Para obtener la forma canónica de una función   producto de sumas se sumará  un termino de la forma X ·   donde falte un literal para que el termino sea canónico. Forma canónica suma de productos: Es aquella constituida exclusivamente por términos canónicos productos (minterminos) sumados que aparecen una sola vez. _ _ _ _ _ _ Por ejemplo:  F(X,Y,Z)  = X Y Z + X Y Z + X Y Z + X Y Z + X Y Z Para simplificar la escritura en forma de suma canónica de productos, se utiliza una notación especial. A cada mintermino se le asocia un numero binario de n bits resultante de considerar como 0 las variables complementadas y como 1 las variables no complementadas.  Así por ejemplo  el mintermino Z   corresponde a combinación X=0, Y=0, Z=1 que representa el numero binario 001, cuyo valor decimal es 1. A este mintermino lo identificaremos entonces como m1. _ _ _ _ _ _ De esta forma, la función : F(X,Y,Z) = X Y Z + X Y Z + X Y Z + X Y Z + X Y Z se puede expresar como: F(X,YZ) = m(1, 4,5,6,7)   que quiere decir la sumatoria de los minterminos 1,4,5,6,7 Forma canónica producto de sumas: Es aquella constituida exclusivamente por términos canónicos sumas (maxterminos) multiplicados que aparecen una sola vez. _ _ _ Por ejemplo  F(X,Y,Z) = ( X + Y + Z ) ( X + Y + Z ) ( X + Y + Z ) Análogamente al caso anterior, podemos simplificar la expresión de la función, indicando los maxterminos. Sin embargo, en este caso se hace al contrario de antes. A cada maxtermino se le asocia un numero binario de n bits resultante de considerar como 1 las variables complementadas y como 0 las variables no complementadas. Así por ejemplo  el maxtermino ' + Y + Z  corresponde a combinación X=1, Y=0, Z=0 que representa el numero binario 100, cuyo valor decimal es 4. A este maxtermino lo identificaremos entonces como M4. _ _ _ De esta forma, la función: F(X,Y,Z) = ( X + Y + Z ) ( X + Y + Z ) ( X + Y + Z ) se puede expresar como: F(X,YZ) =  M(0,2,3)  que quiere decir el producto de los maxterminos 0,2,3 En resumen, cada mintermino se asocia con la combinación de entrada para la que la función produciría un 1, y cada maxtérmino con la combinación para la que produciría un 0. En la tabla de la derecha se muestran los minterminos y los maxterminos asociados con cada combinación en una tabla de verdad de 3 variables. De acuerdo con esta tabla para determinar  el termino producto o suma se hace lo siguiente: para los minterminos cada variable no complementada se asocia con un 1 y cada variable complementada se asocia con 0. Para los maxtérminos la regla es la inversa. Valor decimal X Y Z Mintermino Maxtermino 0 0 0 0 X Y Z = m0 X + Y + Z = M0 1 0 0 1 X Y Z = m1 X + Y + Z = M1 2 0 1 0 X Y Z = m2 X + Y + Z = M2 3 0 1 1 X Y Z = m3 X + Y + Z = M3 4 1 0 0 X Y Z = m4 X + Y + Z = M4 5 1 0 1 X Y Z = m5 X + Y + Z = M5 6 1 1 0 X Y Z = m6 X + Y + Z = M6 7 1 1 1 X Y Z = m7 X + Y + Z = M7 Ejemplo 1. Exprese la siguiente función como una suma de minterminos: _ F = X + Y Z Hay dos formas de resolver este problema. Forma 1. Se puede obtener la tabla de verdad de la expresión y entonces tomar los minterminos. X Y Z F = X + Y Z minterminos 0 0 0 0 0 0 1 1 X Y Z 0 1 0 0 0 1 1 0 1 0 0 1 X Y Z 1 0 1 1 X Y Z 1 1 0 1 X Y Z 1 1 1 1 X Y Z Se evalúa la función para todas las combinaciones y se toman los minterminos de la tabla para los cuales la función vale 1. _ _ _ _ _ _ La respuesta es :F = X Y Z + X Y Z + X Y Z + X Y Z + X Y Z Otra notación que podemos utilizar es: F = m(1, 4,5,6,7)   que quiere decir la sumatoria de los minterminos 1,4,5,6,7 Forma 2. Aplicando los teoremas de expansión canónica para  las variables faltantes. _ X + Y Z _ _ _ _ X ( Y + Y ) ( Z + Z ) + Y Z ( X + X ) _ _ _ _ _ ( X Y + X Y ) ( Z + Z ) + Y Z X + Y Z X _ _ _ _ _ _ _ X Y Z + X Y Z + X Y Z + X Y Z + X Y Z + X Y Z _ _ _ _ _ _ X Y Z + X Y Z + X Y Z + X Y Z + X Y Z Ejemplo 2. Exprese la siguiente función como un producto de maxitérminos: _ F = X + Y Z De nuevo, se puede resolver construyendo una tabla de verdad o con manipulación algebraica. Forma 1. Se obtiene la tabla de verdad de la función. Tomando los maxterminos desde la tabla de verdad, la respuesta es: X Y Z F = X + Y Z maxterminos 0 0 0 0 ( X + Y + Z ) 0 0 1 1 0 1 0 0 ( X + Y + Z ) 0 1 1 0 ( X + Y + Z ) 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 Se evalúa la función para todas las combinaciones y se toman los maxtermino de la tabla para los cuales la función vale 0. _ _ _ La respuesta es: F = ( X + Y + Z ) ( X + Y + Z ) ( X + Y + Z ) Otra notación que podemos utilizar es: F = M(0,2,3)   que quiere decir el producto de los maxterminos 0,2,3 Forma 2. Aplicando el teorema de expansión canónica. _ X + Y Z _ ( X + Y ) ( X + Z ) _ _ _ ( X + Y + Z Z ) (X + Z + Y Y ) _ _ _ _ ( X + Y + Z ) ( X + Y + Z ) ( X + Z + Y ) ( X + Z + Y ) _ _ _ _ ( X + Y + Z ) ( X + Y + Z ) ( X + Y + Z ) ( X + Y + Z ) _ _ _ ( X + Y + Z ) ( X + Y + Z ) ( X + Y + Z ) _ _ _ ( X + Y + Z ) ( X + Y + Z ) ( X + Y + Z ) Note la simetría que existe entre la suma de productos y el producto de sumas de una expresión. Si mi es el minitérmino para la combinación  i, y Mi es el maxitérmino. mi = Mi Para convertir de una forma canónica a otra se intercambian los signos (Sumatoria) y (Productoria) y se remplazan los números correspondientes a las combinaciones no incluidas el la forma original. Por ejemplo: M(2,4,6) = m(0,1,3,5,7)  Forma normal de funciones booleanas Otra manera importante de expresar expresiones booleanas es la forma normal. Tiene la misma estructura básica suma de productos o producto de sumas, pero no se requiere que los términos sean miniterminos o maxiterminos. Por ejemplo:La siguiente es una forma normal suma de productos: _ _ X Y + X Y Z La siguiente es una forma normal producto de sumas: _ ( Y + X ) ( X + Z ) ( Y )