Ingeniería informática con énfasis en desarrollo de software

...

- Teorema(2): 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 a1, a2,... an, representan los valores asignados a x1, x2,... xn, en ese orden, donde cada ai es 0 o 1. Escoja un término de la forma normal completa como sigue: Use xi si ai = 1, y use xií si ai = 0 para cada xi, 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.

Ejemplo 4.

Sea f(x,y) = xí y + xí yí + x y + x yí. Si se asigna a x el valor de 0 y a y el valor 1 entonces se tendrá:

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

= 1 + 0 + 0 + 0 = 1.

- Teorema(3): Dos expresiones booleanas son iguales si y sólo si sus respectivas F.N.D son iguales.

- Teorema(4): 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.

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

Definición. Una función booleana está en F.N.C en n variables x1, x2,... xn, para n ≥ 0, si la función en un producto de factores del tipo E1 (x1) + E2( x2) + ... + En(xn), donde Ei(xi) = xi o xií 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.

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

Ejemplo 7.

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' )

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

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.

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.

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.

- Formas normales perfectas

Las formas normales perfectas se basan en el método de resolver un teorema a través de la inducción perfecta.

[pic 2]

- Métodos de minimización de funciones booleanas

Métodos de simplificación

Por simplificación de una función lógica se entiende la obtención de su mínima expresión. A la hora de implementar físicamente una función lógica se suele simplificar para reducir así la complejidad del circuito.

A continuación, se indican los modos más usuales de simplificar una función lógica.

Algebraico

Artículo principal: Álgebra de Boole

Para la simplificación por este método no sólo bastará con conocer todas las propiedades y teoremas del álgebra de Boole, además se debe desarrollar una cierta habilidad lógico-matemática que se adquiere fundamentalmente con la experiencia.

Como ejemplo se simplificará la siguiente función:

F = A’C’ + ABC + BC’ + A’B’C + A’BC

Observando cada uno de los sumando podemos ver que hay factores comunes en los sumandos 2º con 5º y 4º con 5º que conllevan simplificación:

F = A’C’ + BC’ + BC(A + A’) + A’C(B + B’)

Note que el término 5º se ha tomado dos veces, de acuerdo con la propiedad que dice que A + A = A. Aplicando las propiedades del álgebra de Boole (A + A' = 1 y A . 1 = A), queda

F = A’C’ + BC’ + BC + A’C

Repitiendo nuevamente el proceso,