4.3.1 Definición. Una expresión booleana es una sucesión de símbolos que incluye 0,1, algunas variables y las operaciones booleanas.

Para ser más precisos definamos una expresión boolena en n variables x₁, x₂..., x_n recursivamente como:

• Los símbolos 0 y 1 y x₁, x₂,..., x_n son expresiones booleanas en x₁, x₂,... x_n.
• Si E₁ y E₂ son expresiones booleanas en x₁, x₂,... x_n también lo son E₁ + E₂; E₁ E₂ y E₁’.

Ejemplo 1.

Las siguientes son cuatro expresiones booleanas en las tres variables x, y, z:

• (x + y)(x + z).1.             x + y.
• x’z + x’y + z’.                 z.

Es obvio que las expresiones del lado izquierdo involucran las tres variables, las del lado derecho dos y una variable respectivamente. Las expresiones booleanas 0 y 1 pueden verse como expresiones en cualquier número de variables.

 
El número de variables de una expresión booleana es el número de letras distintas que aparezcan en la expresión, sin tener en cuenta si están o no complementadas.

4.3.2 Forma normal disyuntiva. Una expresión booleana está en forma normal disyuntiva en n variables x₁, x₂,... x_n, si la expresión es una suma de términos del tipo E₁ (x₁) x E₂( x₂) x ... x E_n(x_n), donde E_i(x_i) = x_i o x_i’ para i = 1, 2,..., n, y ningún par de términos son idénticos. Además se dice que 0 y 1 están en F.N.D en una variable para todo n ³ 0.

4.3.2.1 Teorema. Toda expresión booleana que no contiene constantes es igual a una función en forma normal disyuntiva.

La manera de realizar esa transformación la ilustra el siguiente ejemplo.

Ejemplo 2

Escribir (xy’ + xz)’ + x' en F.N.D

Solución:

( xy’ + xz)’ + x' = (xy’)’(xz)’ + x'

= (x’ + y)(x’ + z’) + x’

= (x’ + y)x’ + (x’ + y)z’ + x’

= x’ + x’y + x’z’ + yz’ + x’

= x’ + yz’

= x’(y + y’)(z + z’) + yz’(x + x’)

= x’ y z + x’ y z’ + x’ y’ z + x’ y’ z’ + x y z’

Cualquier expresión booleana puede colocarse en forma normal disyuntiva en más de una forma. Basta cambiar el número de variables.

Ejemplo 3.

f = x y es una expresión booleana en dos variables en F.N.D. Si la multiplicamos por z + z’ (que es 1), obtenemos f = x y z + x y z’ la cual es una expresión booleana en tres variables escrita en F.N.D.

Se considerará, a menos que se diga otra cosa, que la F.N.D se refiere a aquella forma que contiene el menor número posible de variables. Con esta excepción, se puede demostrar que la F.N.D de una función está determinada unívocamente por la función.

Si se desea escoger sólo uno de los términos posibles en una F.N.D en n variables, es decir, escoger a x o a x’ para cada una de las n variables x_i, i = 1,2,...,n; hay exactamente 2ⁿ términos distintos que pueden aparecer.

4.3.2.2 Definición. La forma normal disyuntiva en n variables, que contiene 2ⁿ términos se llama forma normal disyuntiva completa en n variables.

4.3.2.3 Teorema. Si a cada una de las n variables de una expresión booleana en la F.N.D se le asigna el valor 0 o 1 de una forma arbitraria pero fija, entonces exactamente un término de la F.N.D completa tendrá el valor 1, todos los demás términos tendrán el valor 0.

Demostración. Suponga que a₁, a₂,... a_n, representan los valores asignados a x₁, x₂,... x_n, en ese orden, donde cada a_i es 0 o 1. Escoja un término de la forma normal completa como sigue: Use x_i si a_i = 1, y use x_i’ si a_i = 0 para cada x_i, i = 1,2,...,n. El término así escogido es un producto de n unos, y por lo tanto, es 1. Todos los otros términos contendrán por lo menos un factor 0, y en consecuencia, serán 0.

Una consecuencia de este teorema, es que la F.N.D completa sea identica a 1.

f(x,y) = 1.1 + 1.0 + 0.1 + 0.0

= 1 + 0 + 0 + 0 = 1.

4.3.2.4 Teorema. Dos expresiones booleanas son iguales si y sólo si sus respectivas F.N.D son iguales.

4.3.2.5 Teorema. Para establecer cualquier Identidad en álgebra booleana, es suficiente verificar el valor de cada función para todas las combinaciones de 0 y 1 que pueden asignarse a las variables.

Se concluye entonces, que una expresión booleana está completamente determinada por los valores que toma para cada asignación posible de 0 y 1 a las variables respectivas. Luego las funciones se pueden especificar completamente dando una tabla que represente estas propiedades.

En el diseño de circuitos, esta es precisamente la manera como las expresiones booleanas son construidas. Si tal tabla ha sido dada, entonces la expresión booleana en F.N.D puede escribirse por inspección. A cada conjunto de condiciones para los cuales la expresión booleana sea 1, corresponderá un término en la F.N.D escogida. La suma de estos términos da la función aunque no necesariamente en la forma más simple.

Ejemplo 5.
Encuentre y simplifique la expresión booleana especificada por la siguiente tabla.

La expresión booleana tendrá dos términos que se obtienen de las filas 5 y 7 donde la expresión booleana vale 1.

f(x,y,z) = x y' z' + x y z'

= x z' (y + y')

= x z’.

Ejemplo 6.

Hallar el complemento de la expresión booleana del ejemplo 5, en F.N.D.

Solución. El complemento de cualquier expresión booleana en la F.N.D contiene los términos de la forma normal disyuntiva completa que faltan en la función dada.

El complemento será entonces la siguiente expresión booleana.

Se puede demostrar fácilmente que f'(x,y,z) = x' + z que es el resultado obtenido si hubiéramos utilizado las leyes de morgan en la expresión f(x,y,z) = x z'.

4.3.3 Forma normal conjuntiva. En esta forma cada función se representa como un producto de sumas, en lugar de una suma de productos.

4.3.3.1 Definición. Una función booleana está en F.N.C en n variables x₁, x₂,... x_n, para n ³ 0, si la función en un producto de factores del tipo E₁ (x₁) + E₂( x₂) + ... + E_n(x_n), donde E_i(x_i) = x_i o x_i’ para i = 1, 2, ..., n, y ningún par de factores son idénticos. Se dice también que 0 y 1 están en F.N.C en n variables para n ³ 0.

4.3.3.2 Teorema. Toda función en un álgebra booleana que no contiene constantes es igual a una función en forma normal conjuntiva.

Escribir la función (x y' + x z)' + x' en F.N.C.

Solución:

(x y' + xz)' + x'

= (x' + y) (x' + z') + x'

= (x' + x' + y) (x' + x' + z' )

= (x' + y) (x' + z' )

= (x' + y + z z' ) (x' + z' + yy' )

= (x' + y + z ) (x' + y + z' ) (x' + y' + z ) (x' + y' + z' )

4.3.3.3 Definición. La forma normal conjuntiva en n variables que contienen 2ⁿ factores se llama forma normal conjuntiva completa en n variables.

4.3.3.4 Teorema. Si a cada una de las n variables de una F.N.C se le asigna el 0 o 1 de una manera arbitraria, pero fija, entonces exactamente un factor de la F.N.C en las n variables tendrá el valor 0 y todos los demás factores tendrán el valor 1.

Acá se asignará a las variables sin prima el valor de 0 y las variables con prima el valor de 1. El factor adecuado es entonces la suma de estas letras, cada una de las cuales tiene el valor 0. Todos los demás factores tienen el valor 1.

4.3.3.5 Teorema. Dos funciones, cada una expresada en la forma normal conjuntiva en n variables, son iguales si y sólo si contienen idénticos factores.

Ejemplo 8.

Encuentre y simplifique la función f(x,y,z) dada por la siguiente tabla.

La F.N.C tendrá 2 términos o factores y serán los correspondientes a las filas segunda y sexta las cuales la función es 0.

Esto es:
 

Generalmente la F.N.C es usada cuando el número de ceros es menor que el número de unos en la columna F; y la F.N.D es usada cuando el número de unos es menor que el número de ceros en la columna f.

El complemento de una función booleana escrito en F.N.C está constituido por los factores de la F.N.C completa que faltan en la función dada.

Ejemplo 9.

El complemento de ( x + y')( x’ + y) es ( x + y)( x’ + y’).

Ejercicios 4.3

1. Exprese cada una de las siguientes funciones en F.N.D en el menor número posible de variables.

• (u + v + w)(uv + u’w)’
• (x + y)(x + y’)( x’ + z’)
• xyz + (x + y)(x + z)

2. Escriba los términos de la F.N.D completa en x,y,z. Determine que término es igual a 1 si x = 1 Ù y = z = 0.

3. Encuentre el complemento de las siguientes funciones:

4. Escriba la función de las tres variables x, y, z que vale 1 si x = y = 1 y z = 0 o si x = z = 1 Ù y = 0 y que vale 0 para los demás casos en F.N.D y F.N.C.

5. A partir de la siguiente tabla de verificación, encuentre la expresión booleana correspondiente en F.N.D y en F.N.C.

6. Hallar el complemento de la F.N.D del ejemplo anterior. Y simplifique si es posible.

7. Exprese en F.N.D y F.N.C en el menor número de variables.

8. Encuentre el complemento de las siguientes funciones.

• ( x + y + z)(x’ + y’ + z’)
• xy + x’y + x’y’

9. Simplifique las siguientes expresiones usando teoremas del álgebra booleana.

• xy + (x + y)z’ + y
• x + y + (x’ + y + z)’
• yz + wx + z + wz(xy + wz)
• xyz + x’yz + x’y’z’ + x’y’z + xy’z + xy’z’.

10. Halle los complementos de las expresiones booleanas del ejercicio número 9.