unidad 7. álgebra de boole introducción · pdf fileelementos de...

ELEMENTOS DE PROGRAMACIÓN Año 2.010 ________________________________________________________________________________________

____________________________________________________________________________________ Lic. Marcia Mac Gaul de Jorge – Lic. Patricia Mac Gaul Página 38

UNIDAD 7. ÁLGEBRA DE BOOLE INTRODUCCIÓN George Boole (1.815-1.864), fue el creador de un sistema algebraico para el estudio sistemático de la lógica, que hoy en día se usa en campos tales como las técnicas digitales, el Álgebra de Conjuntos y la Teoría de las Probabilidades. En los últimos cien años hay pocas obras de matemática que hayan tenido mayor impacto. El Álgebra de Boole constituye una formalización apropiada para representar información digital, y proporciona un modelo matemático para determinar la respuesta de los circuitos lógicos, independientemente del tipo de dispositivo que constituyen sus correspondientes circuitos físicos.

Entre las aplicaciones de esta Álgebra pueden contarse: formulación algebraica de los requerimientos que debe cumplir un circuito lógico, análisis y síntesis de los circuitos combinacionales, comparación de distintas realizaciones circuitales, minimización del número de cables y dispositivos de los circuitos, codificación de información digital. CONCEPTOS PREVIOS Definición: una operación Θ es binaria o cerrada en un conjunto M si es una regla que asigna a cada par ordenado ( a , b ) de elementos de M un elemento único c = aΘ b tal que c ∈ M. Por ejemplo, la operación resta es una operación cerrada en el conjunto de los números racionales pero no es operación cerrada en el conjunto de los enteros positivos. Para dos números racionales cualesquiera

sr By

qp A ==

la diferencia A – B se define unívocamente como el número racional

qsrq-ps

por lo tanto la operación resta es una operación cerrada en el conjunto de los números racionales. Sin embargo, la diferencia entre dos enteros positivos no siempre es un número entero positivo, por lo tanto, la resta no es una operación cerrada en el conjunto de los números enteros positivos.



Definición: Una operación Θ es asociativa en un conjunto M si y solo sí ∀ a, b, c ∈ M; c ) b a ( ) c b ( a ΘΘ=ΘΘ

Definición: una operación Θ es conmutativa en un conjunto M si y solo si, M b , a ∈∀ ;

a b b a Θ=Θ Definición: si Θ y & son dos operaciones cerradas en el mismo conjunto M, Θ es distributiva respecto a & si y solo si ∀ a, b, c ∈ M;

) c a ( & ) b a ( ) c& b ( a ΘΘ=Θ Como ejemplos, tenemos las operaciones de unión e intersección que son conmutativas y asociativas en el Álgebra de Conjuntos y cada una es también distributiva respecto a la otra. ÁLGEBRA DE BOOLE. DEFINICIÓN AXIOMÁTICA Dado un conjunto B ≠ ∅ y las operaciones # y ∗ , cerradas en B, decimos que la estructura (B , # , ∗ ) es un Álgebra de Boole si y solo si B c , b , a ∈∀ se verifican los siguientes postulados : Postulado 1: Las operaciones # y ∗ son conmutativas. ∀a, b ∈ B ( a # b = b # a ) ∧ ( a ∗ b = b ∗ a ) Postulado2: Cada operación tiene elemento neutro. ∀ a ∈ B; B , ∈µϕ∃ , llamados elementos neutros de las operaciones # y * respectivamente, tal que: (a # ϕ = a ) ∧ (a * µ = a) Postulado3: Cada operación es distributiva con respecto a la otra. ∀a, b, c ∈ B; ( a # ( b∗ c ) = ( a # b ) ∗ ( a # c ) ) ∧ ( a # ( b∗ c ) = ( a ∗ b ) # ( a ∗ c ) ) Postulado 4: Cada elemento de B posee su correspondiente complemento.

∀ a ∈ B, ∃ _a ∈ B, llamado complemento de a, tal que ( a # a

_

= µ) ∧ ( a * ϕ= a_

) Ejemplo: Sea B = {X, Y, Z, . . . , U, ∅} el conjunto de partes de un conjunto U y las operaciones unión e intersección, cerradas en B. Como sabemos:

:B ZY, X, ∈∀ (X ∪ Y = Y ∪ X) ∧ (X ∩ Y = Y ∩ X), ambas operaciones son conmutativas.



( X ∪ ∅ = X ) ∧ ( X ∩ U = X ), de modo que ∅ es el elemento neutro de la operación unión y U lo es de la operación intersección. (X ∪ (Y ∩ Z) = (X ∪ Y) ∩ (X ∪ Z)) ∧ (X ∩ (Y ∪ Z) = (X ∩ Y) ∪ (X ∩ Z)), es decir, cada una de las operaciones es distributiva con respecto a la otra.

( X ∪_

X = U ) ∧ ( X ∩ _

X = ∅ ), donde _

X es el conjunto complemento de X con respecto al conjunto universal dado. Conclusión: como B y las operaciones unión e intersección cumplen los cuatro postulados, la estructura ( B, ∪, ∩) es un Álgebra de Boole.

TEOREMAS Teorema 1: Principio de Dualidad Tesis: Dada una identidad deducible de los postulados de un álgebra booleana, por lo tanto válida, se obtiene otra identidad igualmente válida reemplazando en la primera la operación # por la operación * y viceversa, y el elemento neutro ϕ por el elemento neutro µ y viceversa. La demostración de este teorema se obtiene de inmediato observando la simetría de los postulados con respecto a las dos operaciones y a los dos elementos neutros. Si una proposición o una expresión algebraica se obtiene de otra por la sola aplicación del principio de dualidad, la segunda se llama dual de la primera. En este caso, es claro que la primera es también dual de la segunda. Teorema 2: Ley de Idempotencia para la operación #

a a # a : B a =∈∀ Demostración: a # a = ( a # a ) ∗ µ por el Postulado 2

= ( a # a ) ∗ ( a # _a ) por el Postulado 4

= a # ( a ∗_a ) por el Postulado 3

= a # ϕ por el Postulado 4 = a por el Postulado 2 Teorema 3: Ley de Idempotencia para la operación ∗

a a a : B a =∗∈∀ Dual del Teorema 2. Demostración: Al ser esta propiedad dual de la del Teorema 2, la demostración se obtiene también por dualidad. En este caso desarrollaremos el proceso completo de demostración a modo de ejemplo, aunque sabemos que la veracidad de la propiedad está garantizada por la veracidad de la idempotencia para la operación #



a ∗ a = ( a ∗ a ) # ϕ por el Postulado 2

= ( a ∗ a ) # ( a ∗_

a ) por el Postulado 4

= a ∗ ( a #_

a ) por el Postulado 3 = a ∗ µ por el Postulado 4 = a por el Postulado 2 Teorema 4: Ley de Absorción para la operación #

µ=µ∈∀ # a : B a Demostración :

µ = a #_

a por el Postulado 4

= a # (_

a ∗ µ ) por el Postulado 2

= ( a #_

a )∗ ( a # µ ) por el Postulado 3 = µ ∗ ( a # µ ) = ( a # µ ) * µ por el Postulado 1 = a # µ por el Postulado 2 Teorema 5: Ley de Absorción para la operación *

ϕ=ϕ∗∈∀ a : B a Dual del teorema 4. Demostración: dual de la del teorema 4. Teorema 6: Una ley de Redundancia para la operación #

a b)a (# a : B ba, =∗∈∀ Demostración: a = a ∗ µ por el Postulado 2 = a ∗ (b # µ ) por el Teorema 4 = (a ∗ b) # (a∗ µ ) por el Postulado 3 = (a ∗ b) # a por el Postulado 2 = a # ( a∗ b ) por el Postulado 1 Teorema 7 : Una ley de Redundancia para la operación ∗

a b)# a ( a : B ba, =∗∈∀ Dual del teorema anterior.



Demostración: dual de la del teorema 6. Teorema 8: Ley de Unicidad del Complemento

_a: B a ∈∀ es único.

Demostración: Supondremos que B a ∈ tiene dos complementos que llamaremos x e y, o sea: _

a = x ^ _

a = y para finalizar demostrando que y = x.

Si _

a = x ∧ _

a = y entonces, por el Postulado 4, podemos formular la siguiente Hipótesis:

( a ∗_

a = a ∗ x = a ∗ y =ϕ ) ^ ( a #_

a = a # x = a # y =µ ). x = x∗ µ por el Postulado 2 = x ∗ ( a # y ) por Hipótesis = ( x∗ a ) # ( x∗ y ) por el Postulado 3 = ( a∗ x ) # ( x ∗ y ) por el Postulado 1 = ϕ # ( x∗ y ) por Hipótesis = ( a∗ y ) # ( x∗ y ) por Hipótesis = ( a # x ) ∗ y por el Postulado 3 = µ ∗ y por Hipótesis = y por el Postulado 2 Teorema 9: Ley de Involución

a a B; a =∈∀ Demostración: Sea el cambio de variables z = a . Entonces, la tesis se expresa como: z = a, por lo tanto, debe cumplirse el Postulado 4, entendiendo que el complemento de z es a, o sea, a # z = µ a * z = ϕ Reemplazando nuevamente z por a , resulta: a # a = µ a * a = ϕ que es, justamente, el enunciado del Postulado 4. Teorema 10: Ley Asociativa

: B c b,a, ∈∀ ( a # ( b # c) = ( a # b ) # c) ^ ( a∗ ( b∗ c) = ( a∗ b ) ∗ c) Demostración:



Demostraremos la Ley Asociativa de la operación∗ , siendo dual la de la demostración en el caso de la operación # Primero demostraremos que a # ( a ∗ ( b∗ c)) = a # (( a∗ b ) ∗ c) a # ( a ∗ ( b∗ c)) = a por el Teorema 6 = a ∗ ( a # c) por el Teorema 7 = (a # ( a∗ b)) ∗ ( a # c) por el Teorema 6 = a # (( a∗ b)) ∗ c) por el Postulado 3

Ahora demostraremos que _

a # ( a∗ ( b∗ c)) = _

a # (( a∗ b )∗ c) _

a # ( a∗ ( b∗ c)) = (_

a # a ) ∗ (_

a # ( b∗ c)) por el Postulado 3

= µ ∗ (_

a # ( b∗ c)) por el Postulado 4

= _

a # ( b∗ c) por el Postulado 2

= (_

a # b ) ∗ (_

a # c) por el Postulado 3

= µ ∗ (_

a # b) ∗ (_


= (_

a # a ) ∗ (_

a # b ) ∗ (_

a # c) por los Postulados 4 y 1

= (_

a # (a∗ b)) ∗ (_


= _

a # ((a∗ b)∗ c) por el Postulado 3 Ahora efectuando la operación ∗ entre estas dos expresiones, formamos la siguiente expresión:

( a # ( a∗ ( b∗ c)))∗ (_

a # ( a∗ ( b∗ c))) = ( a # (( a∗ b )∗ c))∗ (_

a # ((a∗ b )∗ c)) I) El miembro de la izquierda puede simplificarse como sigue:

( a # ( a∗ ( b∗ c)))∗ (_

a # ( a∗ ( b∗ c))) =

= (( a∗ ( b∗ c)) # a) ∗ (( a∗ ( b∗ c )) #_


= ( a∗ ( b∗ c)) # ( a∗_

a ) por el Postulado 3 = (a∗ (b∗ c)) #ϕ por el Postulado 4 = a∗ ( b∗ c) por el Postulado 2 II) El miembro de la derecha puede simplificarse como sigue :

( a # (( a∗ b)∗ c)) ∗ (_

a # ((a∗ b)∗ c)) =

= ((( a∗ b )∗ c) # a) ∗ ((( a∗ b )∗ c ) #_


= (( a∗ b)∗ c) # ( a∗_

a ) por el Postulado 3 = (( a∗ b)∗ c) #ϕ por el Postulado 4 = ( a∗b ) ∗ c por el Postulado 2 Por lo tanto, de I) y II): a ∗ ( b∗ c ) = ( a∗ b ) ∗ c y esta proposición es la Ley Asociativa de la operación ∗ que queríamos demostrar.



Teorema 11: Primera Ley de Morgan

:B b a, ∈∀ ba# = __ba∗

Demostración:

Si ba# = __

ba∗ , entonces, a # b es el complemento de __

ba∗ por lo tanto, por el Postulado 4, deberá cumplirse:

(( a # b ) # (__

ba∗ ) =µ ) ^ ((a # b) ∗ (__

ba∗ ) =ϕ ) proposiciones cuya verdad demostraremos. En efecto:

( a # b ) # (__

ba∗ ) = (( a # b ) #_

a ) ∗ ((a # b) #_

b ) por el Postulado 3

= (( a #_a ) # b ) ∗ (( b∗

_b ) # a) por el Teorema 10 y el Postulado 1

= (µ # b )∗ (µ # a ) por el Postulado 4 = µ ∗ µ por el Teorema 4 = µ por el Teorema 3 o Postulado 2 Por otra parte:

( a # b ) ∗ (__ba∗ ) = (( a # b) ∗

_a )∗

_b por el Teorema 10

= (( a∗_a ) # ( b∗

_a ))∗

_

b por el Postulado 3

= (ϕ # ( b∗_a ))∗

_

b por el Postulado 4

= ( b∗_a )∗

_b por el Postulado 2

= ( b∗_

b )∗_

a por el Teorema 10

= ϕ ∗_

a por el Postulado 4 = ϕ por el Teorema 5 Teorema 12: Segunda ley de Morgan

:B b a, ∈∀ ba * = __

b#a Dual del teorema 11. Demostración: dual de la del Teorema 11. Teorema 13: Ley de Complementación de los Elementos Neutros.

)()^(__

ϕ=µµ=ϕ Demostración:

Por el Postulado 4 , _

a a ∗=ϕ entonces, aplicando complemento a ambos miembros:

aa *=ϕ



= _

a #_

a por el Teorema 12

= _

a # a por el Teorema 9 = µ por el Postulado 4

La demostración de que ϕ=µ_

es dual de la demostración anterior. Teorema 14: Una ley de Redundancia para la operación #

:B b a, ∈∀ a # (_

a ∗ b ) = a # b Demostración :

a # (_

a ∗ b ) = ( a #_

a )∗ ( a # b ) por el Postulado 3 = µ ∗ ( a # b ) por el Postulado 4 = a # b por los Postulados 2 y 1 Teorema 15: Una ley de Redundancia para la operación ∗

:B b a, ∈∀ a ∗ (_

a # b ) = a ∗ b Dual del Teorema 14. Demostración: dual de la del teorema 14 ÁLGEBRA DE BOOLE PARA EL CONJUNTO B = {0,1} Y LAS OPERACIONES + Y . En lo que sigue, nos dedicaremos a un Álgebra de Boole en particular. Por ello, como primera medida demostraremos que efectivamente la estructura es un Álgebra de Boole.

Sea B = {0,1} y las operaciones +, llamada reunión o suma lógica y . llamada intersección o producto lógico, ambas cerradas en B, definidas por las siguientes tablas:

+ 0 1 . 0 1 0 0 1 0 0 0 1 1 1 1 0 1

Verifiquemos el cumplimiento de los cuatro postulados: Postulado 1: es evidente, con una sola observación de las tablas que definen las operaciones, que:

) b.a a.b ( ^ ) a b b a ( : B b a, =+=+∈∀



Postulado 2: de las tablas que definen las operaciones se observa: B ,1 0 ∈∃ llamados elementos neutros de las operaciones + y . respectivamente, tal que:

) a 1a ( ^ ) a 0 a ( : B b a, =∗=+∈∀ Postulado 3: Demostraremos utilizando una prueba de casos:

a b c b+c a.( b+c) a.b a.c ( a.b )+( a.c ) 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1

Por lo tanto: ) a.c () a.b ( ) c b a.( : B c b, a, +=+∈∀ , que es la Ley Distributiva del producto lógico respecto de la suma lógica. La Ley distributiva de la suma lógica respecto del producto lógico se enuncia:

) ca ).( ba ( ) c . b (a : B c b, a, ++=+∈∀ y se demuestra en forma análoga. Postulado 4: caben las siguientes posibilidades:

Primera: ) 0 1 ( ^ 0 0 (__

== )

Pero entonces tendríamos: ( 0 + 0 = 0 + 0 = 0 ), lo que ya no estaría verificando el Postulado 4. Segunda: ( 0 = 1 ) ∧ ( 1 = 1 ) Pero entonces tendríamos: ( 0 + 0 = 0 + 1 = 1 ) ∧ ( 1 + 1 = 1 + 1 = 1 ) ∧ ( 0 * 0 = 0 * 1 = 0 ) ∧ ( 1 * 1 = 1 * 1 = 1 ) y esta última no estaría verificando el Postulado 4. Tercera: ( 0 = 0 ) ∧ ( 1 = 1) Pero entonces tendríamos: ( 0 + 0 = 0 + 0 = 0 ), lo que ya no estaría verificando el Postulado 4.

Cuarta: ) 0 1 ( ^ ) 10 (__==

Entonces: )01.0 11. ( ^ ) 01.000. (^ ) 101 11 ( ^ ) 1100 0 (____

=====+=+=+=+ lo que verifica el Postulado 4.

En consecuencia: ( { 0 , 1 } , + , . ) es un Álgebra de Boole.



Propiedades Antes de enunciar las propiedades, que no son más que los teoremas demostrados en la definición axiomática, estableceremos las siguientes convenciones: 1) Si entre dos elementos no hubiere ningún símbolo de operación, se supondrá un

producto lógico, por lo tanto: ab = a.b

2) Como ninguna de las operaciones + y . es prioritaria una con respecto a la otra, toda expresión debe resolverse de izquierda a derecha. Por ejemplo, para resolver a + bc en el Álgebra de Boole, debe efectuarse primero la suma entre a y b, posteriormente, ese resultado se multiplica con c. Esto no nos resulta muy familiar dado que estamos acostumbrados a operar teniendo en cuenta la prioridad del producto con respecto a la suma. Si se hubiese deseado efectuar primero el producto de b por c, se debería haber indicado esta prioridad mediante el uso de paréntesis, es decir: a + (bc). Sin embargo, por razones de practicidad, adoptaremos la convención de omitir el paréntesis cuando se desea priorizar el producto. Reservaremos el uso del paréntesis sólo para cuando la operación a efectuar prioritariamente sea la suma lógica.

Ejemplos: • Cuando se expresa: a + bc se resolverá primero el producto lógico b por c y a ese

resultado se le sumará a. • Cuando se expresa: (a + b)c se resolverá primero la suma lógica de a con b y a ese

resultado se lo multiplicará por c. Habiendo ya demostrado que la estructura ({0 , 1} , + , . ) es un Álgebra de Boole, enunciaremos los teoremas cuya validez hemos demostrado axiomáticamente: 1) Vale el Principio de Dualidad. 2) Ley de Idempotencia para la operación + : a + a = a. 3) Ley de Idempotencia para la operación . : a . a = a. 4) Ley de Absorción para la operación + : a + 1 = 1. 5) Ley de Absorción para la operación + : a . 0 = 0. 6) Una Ley de Redundancia para la operación + : a + a b = a. 7) Una Ley de Redundancia para la operación . : a . ( a + b ) = a. 8) Vale la Ley de unicidad del complemento. 9) Ley de Involución : a = a. 10) Ley asociativa (a + (b + c) = (a + b) + c) ^ (a(bc) = (ab)c). 11) Primera ley de Morgan ba + = b a . 12) Segunda ley de Morgan bab a += . 13) Ley de Complementación de elementos neutros : ( 0 = 1 ) ^ ( 1 = 0 ). 14) Una Ley de Redundancia para la operación + : a + a b = a + b. 15) Una Ley de Redundancia para la operación + : a ( a + b ) = a b.



La operación disyunción o suma binaria Aparte de las operaciones suma lógica y producto lógico, llamadas operaciones primitivas, se define, como operación secundaria o derivada de las primitivas, la operación disyunción o suma binaria, que se simboliza con ⊕ , del siguiente modo : B b a, ∈∀ ;

a ⊕ b = a b + a b

conforme a la definición anterior, la operación tiene la siguiente tabla:

⊕ 0 1 0 0 1 1 1 0

Como es una operación derivada de las primitivas, se puede expresar solamente en función de una de ellas. En efecto: a ⊕ b = a b + a b = a b + 0 + a b + 0 = a b + a a + a b + b b = a ( b + a ) + b ( b + a ) = ( a + b ) ( b + a ) = ( a + b ) ( ab )

= ( b a ) ( ab ) que expresa la disyunción en función del producto lógico solamente, y:

a ⊕ b = )b a ( ) b a ( ) b a )( b a ( ) b a )( b a (__

+++=++=++ que expresa la disyunción en función de la suma lógica solamente. En adelante, llamaremos suma a la operación reunión o suma lógica, producto a la operación reunión o producto lógico y disyunción a la operación suma binaria. LOGIGRAMAS O CIRCUITOS LÓGICOS

Un circuito lógico es un esquema gráfico que representa la relación entre las variables booleanas intervinientes.

Tal como lo hemos señalado en nuestra introducción, el Álgebra de Boole proporciona un modelo matemático para determinar la respuesta de los circuitos lógicos, independientemente del tipo de dispositivo que constituyen dichos circuitos. Nuestro objetivo es entonces ver de que manera podemos construir circuitos lógicos que simbolicen a aquellos que deberán representar operaciones.

Supongamos el caso más sencillo: un circuito eléctrico en donde se produce una entrada de corriente ( T0 ), con un interruptor ( x ) al medio. Se desea saber si se produce salida de la corriente que entró ( T1 ). Supongamos también que vamos a asignar x = 0 si el interruptor se encuentra abierto y x = 1 en caso contrario. Un circuito eléctrico de estas características se



esquematiza como sigue :

Supongamos ahora que tenemos un circuito con los interruptores x e y conectados en serie, las mismas condiciones que las expuestas anteriormente y que simbolizaremos con T1 = 1 la presencia de corriente en la salida y con T1 = 0 su ausencia: La tabla que representa el comportamiento de la conexión en serie es:

Interruptor x Interruptor y Valor de T1 0 0 0 0 1 0 1 0 0 1 1 1

Si comparamos sus valores con los que definen las operaciones para el Álgebra de Boole ({0,1} , + , . ), vemos que son los mismos que los de la operación producto. Tomemos ahora el caso de un circuito con los dos interruptores conectados en paralelo: La tabla que representa el comportamiento de la conexión en paralelo es:

Interruptor x Interruptor y Valor de T1 0 0 1 0 1 1 1 0 1 1 1 0

Cuyos valores coinciden con los correspondientes a la operación suma para ({0,1} , + , . ). De igual manera, se pueden construir circuitos eléctricos que simbolicen la complementación y la disyunción. Pero el caso que nos ocupa no es el de los circuitos eléctricos sino su símil, los circuitos lógicos, que representan lo mismo que los primeros pero que serán analizados por nosotros desde el punto de vista de las operaciones que simbolizan. Para esto, definiremos

T0 T1

x=0

T0 T1

x=1

T0

x y

T1

T0 T1

x

y



un elemento de estos circuitos lógicos llamado compuerta, cada una de las cuales representa una de las operaciones de esta Álgebra de Boole que estamos analizando en particular. Como reglas para la construcción de los circuitos lógicos, debemos observar las siguientes: 1) Los valores de las variables ingresan una sola vez. 2) Si es necesario el uso de los valores de una o mas variables en más de una compuerta,

estos se toman de un mismo ingreso. 3) El ingreso de los valores de las variables es por ellos mismos, no por su complemento. Ejemplos:

1) El circuito lógico que representa ba es:

2) El circuito lógico que representa ba + es:

3) El circuito que representa (a + b)( ba + ) es: Hasta ahora, hemos trabajado con tres formas diferentes: la primera, con expresiones analíticas que relacionan a variables entre sí, la segunda con tablas de verdad o de prueba de casos que indican resultados de las operaciones que relacionan a las variables y la tercera, con

Compuerta de Suma Compuerta de Producto

Compuerta de Complementación Compuerta de Disyunción

a b

a b

a b



expresiones gráficas de esas relaciones y resultados: los circuitos lógicos. Ahora, continuando con nuestro estudio de esta particular Álgebra de Boole ({0 , 1}, + , . ), definiremos qué es una función booleana de variables booleanas. FUNCIONES BOOLEANAS Definición: una variable es booleana si solamente puede tomar como valores 0 ó 1. Definición: una función booleana es una función que relaciona variables booleanas y cuyo valor 0 ó 1, viene dado por una expresión algebraica constituida por dichas variables booleanas relacionadas entre sí por las operaciones suma, producto o complemento. Observación: la definición anterior no implica que en una expresión algebraica de una función booleana no pueda aparecer la operación disyunción pues, como es sabido, la misma no es más que una derivación de las otras dos. Funciones booleanas de una variable booleana Dado que tenemos sólo dos posibilidades de valor de las funciones: 0 ó 1 y 21 = 2 combinaciones posibles entre los dos valores, 0 ó 1, que puede tomar la única variable,

tendremos : 122 = 4 funciones booleanas de una variable booleana

a) Tabla

a f0 f1 f2 f3 0 0 0 1 1 1 0 1 0 1

b) Expresión analítica De la lectura de la tabla anterior, obviamente:

f0 (a) = 0 ; f1(a) = a ; f2 (a) = _

a ; f3 (a) = 1 c) Circuitos lógicos

f3(a) f2(a)

f1(a)

a a

a a

f0(a)



Funciones booleanas de dos variables booleanas Dado que tenemos dos posibilidades de valor de las funciones: 0 ó 1 y 22 = 4 combinaciones posibles entre los dos valores, 0 ó 1, que puede tomar cada una de las variables,

tendremos:222 = 16 funciones boolenas de dos variables booleanas.

a) Tabla

A b f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

b) Expresión analítica Ahora no es posible, con la sola vista de la tabla, obtener la expresión analítica de fi (a,b), salvo en los casos en que esta es obvia como f0(a,b) = 0 o f15(a,b) =1. Veremos entonces dos procedimientos que nos permitirán obtenerlas, con la aclaración de que tal expresión analítica de fi(a,b) es única, independientemente del método que se utilice para su obtención. b-1) Obtención de la expresión analítica de fi (a,b) como suma de productos Dado que deseamos que la función se exprese analíticamente como suma de productos y considerando que 0 es el elemento neutro de la suma, no tiene sentido que consideremos aquellas salidas que valen precisamente 0. Por ejemplo, tomemos f10(a,b) y f14(a,b) f10(a,b) = 1 ⇔ ( a = 0 ^ b = 0 ) v ( a = 1 ^ b = 0 ) f14(a,b) = 1 ⇔ ( a = 0 ^ b = 0 ) v ( a = 0 ^ b = 1 ) v ( a = 1 ^ b = 0 ) Pero, para que efectivamente los productos parciales tengan a 1 por resultado, ambas variables deben valer 1. Entonces: Para f10(a,b)

Si a = 0 ^ b = 0 ⇒ ab = 0.0 = 0 . Por lo tanto debemos tomar: 11.10.0b.a____

===

Si a = 1 ^ b = 0 ⇒ ab = 1.0 = 0 . Por lo tanto debemos tomar: 11.10.1b.a__

=== Para f14(a,b)

Si a = 0 ^ b = 0 ⇒ ab = 0.0 = 0 . Por lo tanto debemos tomar: 11.10.0b.a____

===

Si a = 0 ^ b = 1 ⇒ ab = 0.1 = 0 . Por lo tanto debemos tomar: 11.11.0b.a__

===

Si a = 1 ^ b = 0 ⇒ ab = 1.0 = 0 . Por lo tanto debemos tomar: 11.10.1ba__

=== Ahora podemos formar la suma de los productos obtenidos anteriormente:



f10(a,b) = ___

baba +

f14(a,b) = ____bababa ++

Aplicando los postulados y propiedades sobre las expresiones obtenidas, finalmente nos queda:

f10(a,b) = ______ba)a(bbaba =+=+

f14(a,b) = _________________babaaba1.abab)b(abab)aba(bababa +=+=+=++=++=++

b-2) Obtención de la expresión analítica de fi(a,b) como producto de sumas Como el procedimiento es dual del anterior, no es necesaria la especificación de los detalles, pero su desarrollo para las mismas funciones booleanas utilizadas en el procedimiento anterior, nos servirá para verificar la obtención de la misma expresión analítica para la función booleana. f10(a,b) = 0 ⇔ ( a = 0 ^ b = 1 ) v ( a = 1 ^ b = 1 ) f14(a,b) = 0 ⇔ a = 1 ^ b = 1 Para f10(a,b)

Si a = 0 ^ b = 1 ⇒ a+b = 0 +1= 1 . Por lo tanto debemos tomar: 00010ba__

=+=+=+

Si a = 1 ^ b = 1 ⇒ a+b = 1 +1= 1 . Por lo tanto debemos tomar: 00011ba____

=+=+=+ Para f14(a,b)

Si a = 1 ^ b = 1 ⇒ a+b = 1 +1= 1 . Por lo tanto debemos tomar: 00011ba____

=+=+=+ Entonces:

f10(a,b) = _______b0b)aa.(b)ba)(ba( =+=+=++

f14(a,b) = __ba+

c) Circuitos lógicos: Notemos que f0(a,b) no puede expresarse como suma de productos ni f15(a,b) puede expresarse como producto de sumas. Funciones booleanas de n variables booleanas

Para n variables booleanas tendremos n22 funciones booleanas diferentes. Tomemos el caso

de n = 3 y de las 256 funciones booleanas de tres variables booleanas consideremos la que

b

a f14(a,b) f10(a,b) b



tiene por salida la dada por la siguiente: a) Tabla

a b c f 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 1

b) Expresión analítica b-1) Obtención de la expresión analítica de f(a,b,c) como suma de productos

f(a,b,c) = abccabcbabcacbacba________+++++ =

= =+++++=+++++ )cab(ccba)cb(cacba abc)cab(cbabc)acba(cba_______________

= =+++=+++ )()( bcbabcbaabcbabacba

= bcacaaabcacaabcabacabcabca ++=+++=+++=+++ )()()( b-2) Obtención de la expresión analítica de f(a,b,c) como producto de sumas f(a,b,c) = ))(( cbacba ++++ c) Circuito lógico Hemos visto como dada la expresión analítica de una función booleana podemos hallar su tabla y construir su circuito lógico y también como, dada la tabla, podemos obtener la expresión analítica y el circuito lógico. Ahora veremos como dado el circuito lógico, obtendremos la expresión analítica de la función booleana con la cual podemos construir su tabla.

a c

b



f(a,b,c) = =+=+++ bc)a)(cb() ba)(cab( bcacb bacab________

= )cba)(c(bb)a)(cba(______

+++++++ =__________

ccbca cb ab bccababaa +++++++++ =

= =+++++++++ )ccbca cb( ab bcc)ababaa(__________

c ab bca__

+++

= )c(bcab)a(__

+++ = ____

c ba c b ba ++=+++ Con lo cual, la tabla de verdad de f(a,b,c) es la siguiente:

a b c a c f 0 0 0 1 1 1 0 0 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 1 1 1 1 1 0 0 1

Por otra parte, ahora que hemos obtenido la expresión analítica de la función y la hemos simplificado utilizando los postulados y propiedades, podemos construir el circuito lógico de la misma. Este nuevo circuito lógico, obviamente, es equivalente al dado:

f(a,b,c)

a b c

a b c

bacab + cab

_

ba

bca_

f(a,b,c)

cb bcacb +



FORMAS NORMALES O FORMAS CANÓNICAS DE UNA FUNCIÓN BOOLEANA Forma Normal Disyuntiva Definición: sean a1, a2, a3, . . . , an n variables booleanas tales que ai B∈ ={0, 1}. Un término obtenido multiplicando las n variables entre sí, complementadas o no, se denomina minitérmino y lo simbolizamos mi . Las n variables dan lugar a 2n productos diferentes. En particular:

para n = 1 tenemos dos minitérminos _a y a,

para n = 2 tenemos cuatro minitérminos : _

a_

b , _

a b, a_

b , ab ,

para n = 3 tenemos ocho minitérminos _

a_

b_

c , _

a_

b c , _

a b_

c , abcy cab , cba , cba , bca_____

Para tres variables, el término a_

b no es minitérmino pues no aparece ni c ni _

c . El término abc tampoco es minitérmino pues los complementos deben ser individuales, de otro modo, por aplicación de la segunda Ley de Morgan, el producto se transforma en suma y ya no se verificaría una de las condiciones de la definición. Definición: decimos que una función booleana f, de n variables booleanas a1,a2 ,a3, . . . ,an, está expresada en FORMA NORMAL DISYUNTIVA, que simbolizamos: FNDf(a1, a2, a3, . . . ,an ) si está expresada como suma de minitérminos. Por ejemplo, las siguientes funciones están expresadas en Forma Normal Disyuntiva:

FNDf(a,b,c) = abc +___cba cab +

FNDf(a,b) = ab Obtención de la Forma Normal Disyuntiva La obtención de la Forma Normal Disyuntiva se hace a través de una técnica que será

aplicada a la siguiente función de ejemplo: )(),,( cabacabcbaf ++= Como primer paso, llevamos f(a,b,c) a su expresión como suma de productos:

cbabcacabcabacabcabacabcabacabcbaf +++=+++=+=++= ))(()()()(),,( Ahora multiplicamos cada término que no sea minitérmino por el valor 1 dado por el Postulado 4, escrito en forma conveniente, tal es, como la suma de la variable que le falta a ese término con su complemento. Entonces:

)()(),,(___________

aacb)cab(cbbcacabcbabcacab cbaf ++++++=+++=



Efectuando las operaciones que se indican, obtenemos: __________

cbacabcababc cba cba cabcbaf ++++++=),,( expresión que, por la ley de Idempotencia para la operación suma, nos queda:

FND abc cba cba cabcbaf______

+++=),,( que es la Forma Normal Disyuntiva de f (a,b,c) Es de destacar la ventaja que nos proporciona la definición de una función booleana por medio de su tabla de verdad cuando deseamos obtener su Forma Normal Disyuntiva. En efecto, teniendo en cuenta la definición de minitérmino y de Forma Normal Disyuntiva, podemos leer de la tabla solamente aquellas salidas 1 y de esta manera la obtención es inmediata. Tomemos el ejemplo de la función anterior, cuya tabla es la siguiente:

a b c f (a,b,c) 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1

de donde, la Forma Normal Disyuntiva de f (a,b,c) es:

abccabcbacbacbaFNDf_

+++=),,( Forma Normal Disyuntiva Completa Se denomina Forma Normal Disyuntiva Completa de una función booleana f de n variables booleanas a1, a2, ..., an que simbolizaremos como FNDCf(a1, a2, ..., an) a aquella Forma Normal Disyuntiva que contiene los 2n minitérminos. Por ejemplo:

abbabababaFNDCf +++=),(

Teorema: la suma de los 2n minitérminos de la FNDC vale 1: ∑−

=

=12

0ii

n

1m

Forma Normal Conjuntiva Nótese la dualidad en las definiciones, teoremas y obtenciones de la Forma Normal Conjuntiva con respecto a la Forma Normal Disyuntiva. Definición: sean a1, a2, a3, . . . , an n variables booleanas tales que ai B∈ ={0, 1}. Un término obtenido sumando las n variables entre sí, complementadas o no, se denomina maxitérmino y lo simbolizamos Mi .



Las n variables dan lugar a 2n sumas diferentes. En particular:

para n = 1 tenemos dos maxitérminos _

a y a, para n = 2 tenemos cuatro maxitérminos )(),(),(),( babababa ++++ para n = 3 tenemos ocho maxiérminos:

)(),(),(),(),(),(),(),( cbacbacbacbacbacbacbacba ++++++++++++++++

Para tres variables, el a +_

b no es maxitérmino pues no aparece ni c ni _

c . El término cba ++ tampoco es maxitérmino pues los complementos deben ser individuales, de otro

modo, por aplicación de la primera Ley de Morgan, la suma se transforma en producto y ya no se verificaría una de las condiciones de la definición. Definición: decimos que una función booleana f, de n variables booleanas a1,a2 ,a3, . . . ,an, está expresada en FORMA NORMAL CONJUNTIVA, que simbolizamos: FNCf(a1, a2, a3, . . . ,an ) si está expresada como producto de maxitérminos. Por ejemplo, las siguientes funciones están expresadas en Forma Normal Conjuntiva: FNCf(a,b,c) = ))()(( cbacbacba ++++++ FNCf(a,b) = a + b Obtención de la Forma Normal Conjuntiva La obtención de la Forma Normal Conjuntiva se hace a través de una técnica que será

aplicada a la siguiente función de ejemplo: )(),,( cabacabcbaf ++= Como primer paso, llevamos f(a,b,c) a su expresión como producto de sumas:

=++++=+++=+=++= ))())((())(()()()(),,( cacabbacabcabacabcabacabcabacabcbaf

))(())(( cabacacabbacab ++=++++= Ahora a cada factor que no sea maxitérmino le sumamos el 1 dado por el Postulado 4, escrito en forma conveniente, tal es, como el producto de la variable que le falta a ese factor con su complemento. Entonces:

)))(()((),,( bbcaccba cbaf ++++= Efectuando las operaciones que se indican y aplicando propiedades, obtenemos:

FNC ))()()(),,( cbacbacbacba(cbaf__

++++++++=



Es de destacar la ventaja que nos proporciona la definición de una función booleana por medio de su tabla de verdad cuando deseamos obtener su Forma Normal Conjuntiva. En efecto, teniendo en cuenta la definición de maxitérmino y de Forma Normal Conjuntiva, podemos leer de la tabla solamente aquellas salidas 0 y de esta manera la obtención es inmediata. Tomemos el ejemplo anterior: leyendo los ceros de la tabla dada, la Forma Normal Conjuntiva de f(a,b,c) es: FNCf(a,b,c) = ))()()(( cbacbacbacba ++++++++ Forma Normal Conjuntiva Completa Se denomina Forma Normal Conjuntiva Completa de una función booleana f de n variables booleanas a1, a2, ..., an, que simbolizaremos: FNCCf(a1, a2, ..., an) a aquella Forma Normal Conjuntiva que contiene los 2n maxitérminos. Por ejemplo: FNCCf(a,b) = ))()()(( babababa ++++ es una Forma Normal Conjuntiva Completa para una función f en las variables boolenas a y b.

Teorema: El producto de los 2n maxitérminos vale 0: ∏−

=

=12

0ii

n

0M

Transposición de Formas Normales Basándonos en el hecho de que una función booleana puede tener como salida solamente los valores 0 ó 1 y recordando lo precedente sobre la obtención de cualquiera de las formas normales a partir de una tabla de verdad dada, es evidente que cada una de las salidas representa o un minitérmino o un maxitérmino. Ahora bien, cuando obtenemos la Forma Normal Disyuntiva, los minitérminos que no aparecen en ella serán los maxitérminos que aparecerán en la Forma Normal Conjuntiva de la misma función. Esto es, si la Forma Normal Disyuntiva de f(a1, a2, ..., an) contiene C minitérminos, la Forma Normal Conjuntiva de la misma función contendrá (2n - C) maxitérminos y viceversa. Definición: Sea FNDf(a1, a2, ..., an) una función booleana de n variables booleanas expresada en Forma Normal Disyuntiva. Se define como función complementaria de FNDf(a1, a2, ..., an) y se simboliza FNDf*(a1, a2, ..., an) a aquella Forma Normal Disyuntiva que contiene los minitérminos que le faltan a FNDf(a1, a2, ..., an) para ser una Forma Normal Disyuntiva Completa.



Utilizando la definición anterior, podemos hallar la Forma Normal Conjuntiva de una función booleana en forma inmediata, contando con su Forma Normal Disyuntiva. En efecto, bastará encontrar la expresión de la función complementaria y expresarla como producto de sumas. Ejemplo: Sea FNDf(a,b,c) = cabcbabcacbacba ++++ Como la Forma Normal Disyuntiva contiene cinco de los minitérminos, la función complementaria y, por ende, la Forma Normal Conjuntiva, contendrá tres términos. En efecto, como: FNDCf(a,b,c)= abccabcbacbabcacbacbacba +++++++ entonces: FNDf*(a,b,c)= abccbacba ++ Para transformar las sumas en productos, debemos complementar FNDf*(a,b,c) y el resultado de esta complementación será la Forma Normal Conjuntiva de f(a,b,c):

==++= )()()(),,(* abccbacbaabccbacbacbaFNDf

= ),,())()(( cbaFNCfcbacbacba =++++++ Aplicando el Principio de Dualidad, podemos transponer una Forma Normal Conjuntiva a su equivalente Forma Normal Disyuntiva para una misma función booleana. Equivalencia de funciones booleanas Teorema: dos funciones boolenas son equivalentes sí y solo sí sus respectivas formas normales contienen los mismos términos. Este teorema debe interpretarse referido a cualquiera, pero a una sola de las formas normales de una función booleana y, por ello, diremos: dos funciones booleanas son equivalentes sí y solo sí sus respectivas formas normales disyuntivas tienen los mismos minitérminos. O, por dualidad: dos funciones booleanas son equivalentes sí y solo sí sus respectivas formas normales conjuntivas tienen los mismos maxitérminos. Demostración: Dos funciones con los mismos términos son, obviamente, iguales. Recíprocamente, si dos funciones son iguales deben tener el mismo valor para cada selección de valores de las variables. En particular, toman el mismo valor para cada conjunto de valores 0 y 1 que puedan asignarse a las variables. Como el valor de la Forma Normal Disyuntiva Completa es 1, las combinaciones de valores 0 y 1 determinan unívocamente los términos presentes en la forma normal de la función. Por lo tanto, ambas formas normales tienen los mismos minitérminos. Ejemplo: Decidir si Z(a,b,c) = a + bc es equivalente a F(a,b,c) = bcacabaabc +++ Llevando a ambas funciones a su Forma Normal Disyuntiva:



FNDZ(a,b,c) = bcacbacbacababc ++++ FNDF(a,b,c) = bcacbacbacababc ++++ Entonces: FNDZ(a,b,c) = FNDF(a,b,c) ⇒ Z(a,b,c) ≡ F(a,b,c) MINIMIZACIÓN DE FUNCIONES BOOLEANAS Una de las principales aplicaciones del Álgebra de Boole es el diseño de circuitos. Para ello, se plantea el circuito lógico que lo simboliza y se pretende encontrar un circuito equivalente al dado pero que se construya al menor costo posible. Frecuentemente, casos específicos de este problema se resuelven por tanteo. A veces, un ingeniero hábil puede hacer simplificaciones notables usando su intuición y experiencia con circuitos similares. Sin embargo, en circuitos complicados, tales como los usados en modernas computadoras digitales, un método sistemático es extremadamente útil. El procedimiento que se utiliza es simplificar la función booleana que representa un determinado circuito lógico, hasta que la expresión no admita más simplificaciones, esto es, hasta obtener la mínima expresión. El circuito lógico que se construye para representar esa forma mínima es, obviamente, equivalente al dado. Como hemos visto, la expresión analítica de una función booleana adquiere dos representaciones distintas: como suma de productos o como producto de sumas. También sabemos que una misma función booleana admite dos formas normales, equivalentes entre sí: una forma normal disyuntiva y otra conjuntiva. Esto vale también para la forma mínima de una función booleana. Definición: Minimizar una función booleana significa expresarla analíticamente con la menor cantidad de términos posibles o, a igual cantidad de términos, con la menor cantidad de variables posible en cada uno de ellos. La definición nos indica que debemos expresar analíticamente la función con la menor cantidad de términos posible, pero no nos dice nada acerca de cómo deben estar expresados esos términos. Así, si expresamos estos términos como suma de productos, obtendremos una función booleana expresada analíticamente como suma de productos con la menor cantidad posible de términos y, a igual cantidad de términos, con la menor cantidad posible de variables de cada uno de ellos. Esta forma mínima de denomina mínima como suma de productos y la simbolizaremos fminSP. Pero también es cierto que si expresamos los términos como producto de sumas, obtendremos una función booleana expresada analíticamente como producto de sumas con la menor cantidad posible de términos y, a igual cantidad de términos, con la menor cantidad posible de variables de cada uno de ellos. Esta forma mínima de denomina mínima como producto de sumas y la simbolizaremos fminPS. Ejemplo:



Encontrar cada una de las formas mínimas de f(a,b,c) = cbacbacbaabba ++++ F(a,b,c) = cbbaacbcaaabcbacbacbaabba +=++++=++++ )()( de donde: fminSP = cbcbb +=+ fminPS = cbcbbbcbb +=++=+ ))(( Logigrama mínimo Definición: un logigrama es mínimo cuando representa la función booleana utilizando la menor cantidad de compuertas AND u OR y, a igual cantidad de compuertas, menor cantidad de entradas en alguna una de ellas. Pero las compuertas representan operaciones de producto lógico o de suma lógica y las variables de entrada a cada compuerta son variables booleanas. Así, podemos ver que un logigrama mínimo se obtiene de una forma mínima. Pero hay que tener un poco de cuidado, tenemos dos formas mínimas y un solo logigrama mínimo. ¿el logigrama mínimo es la representación gráfica de cualquiera de las formas mínimas de una función booleana?. Examinemos esto con cuidado. Si deseamos representar el logigrama mínimo de la función del ejemplo anterior, nos da igual tomar para ello la expresión de la forma mínima de la función booleana como suma de productos o como producto de sumas, porque son iguales. Así, cualquiera de estas formas mínimas provee el logigrama mínimo. Ahora expresemos cada una de las formas mínimas de la función booleana definida por la siguiente tabla:

a b c f0 0 0 10 0 1 00 1 0 10 1 1 11 0 0 01 0 1 11 1 0 11 1 1 1

Operando obtenemos:

b

c



fminSP (a,b,c) = accab ++ fminPS(a,b,c) = ))(( cbacba ++++ Para construir el circuito lógico que representa fminSP, necesitamos tres compuertas, dos de producto y una de suma. Las dos compuertas de producto reciben dos entradas cada una y la de suma recibe tres. Para construir el circuito lógico que representa fminPS, necesitamos también tres compuertas, dos de suma y una de producto. Las dos compuertas de suma reciben tres entradas cada una y la de producto recibe dos. En definitiva: ambos logigramas requieren igual cantidad de compuertas pero el correspondiente a fminSP tiene, en una de ellas, una entrada menos que una de las compuertas del logigrama correspondiente a fminPS. Por lo tanto, el logigrama mínimo es el que proviene de la forma mínima expresada como suma de productos.

unidad 7. álgebra de boole introducción · pdf fileelementos de...

Documents