1

ALGEBRA BOOLEANA (ALGEBRA DE BOOLE)

1.- Introduccin.

La descripcin bsica de la formulacin del lgebra booleana se basa en conceptos de la teora de conjuntos, donde se define formalmente un lgebra booleana como un conjunto matemtico distributivo y complementado. Esta definicin se resume mediante el uso de los siguientes postulados que sintetizan los elementos y propiedades bsicas.

2.- Postulados.

Postulado 1. Definicin. El lgebra Booleana o lgebra de Boole, es un sistema algebraico, cerrado formado por un conjunto )(K de dos o ms elementos y los dos operadores (.)AND y )(+OR ; de manera alternativa, para cada )(A , )(B y un conjunto )(K , ).( BA pertenece a )(K y )( BA + pertenece a )(K . Con lgica de contactos o interruptores, (.) indica interruptores en serie y )(+ indica interruptores en paralelo.

Postulado 2. Existencia de los elementos (1) y (0). En el conjunto )(K existen los elementos uno )1( , interruptor cerrado, y cero )0( , interruptor abierto, nicos, tales que para todo )(A en )(K se cumple que:

Figura No. 1. Representacin grfica del postulado 2 del lgebra Booleana.

A . 1 = A

A 1 A . 1 0 1 0 1 1 1

A + 0 = A

A 0 A+0 0 0 0 1 0 1

2

Postulado 3. Conmutatividad de las operaciones (+) y (.) Para todo )(A y )(B en )(K .

Figura No. 2. Representacin grfica del postulado 3 del lgebra Booleana.

Postulado 4. Asociatividad de las operaciones (+) y (.) Para todo )(A , )(B y )(C en )(K .

Figura No. 3. Representacin grfica del postulado 4 del lgebra Booleana.

A . B = B . A

A B A B B A 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1

A + B = B + A

A B A+B B+A 0 0 0 0 0 1 1 1 1 0 1 1 1 1 1 1

A+ (B + C ) = (A + B) +C

A . (B . C) = (A . B ) . C

3

Postulado 5. Distributividad de (+) sobre (.) y de (.) sobre (+). Para todo )(A , )(B y )(C en )(K .

Figura No. 4. Representacin grfica del postulado 5 del lgebra Booleana.

Postulado 6. Existencia del complemento. Para toda )(A en )(K existe un nico elemento llamado )'(A o )(A o complemento de

)(A en )(K tal que:

Figura No. 5. Representacin grfica del postulado 6 del lgebra Booleana.

A + ( B.C ) = ( A+B) ( A+C)

A B C A+B.C (A+B)(A+C) 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1

A (B+C) = (A . B) + (A . C)

A + A = 1

A A A +A 0 1 1 1 0 1

A A = 0

A A A A 0 1 0 1 0 0

4

3.- Principio de Dualidad.

El principio de dualidad establece que si una expresin lgica es vlida, su expresin dual tambin es vlida en el lgebra Booleana.

La expresin dual se determina reemplazando todos los operadores (.) por )(+ y viceversa, adems reemplazando los unos )1( por ceros )0( y viceversa y teniendo en cuenta de conservar la posicin de los parntesis existentes.

Ejemplo 1.

Expresin Dual

)).(().( CABACBA ++=+ ).().().( CABACBA +=+ 11 =+A 00. =A

BB =1. 00 =+B CBACBA ++=+ ).( CBACBA ..)(. =+

4.- Teoremas fundamentales del algebra Booleana.

En estos teoremas, las letras )(A , )(B y )(C representan los elementos del lgebra booleana.

Teorema 1.- Idempotencia. Expresin Dual AAA =+ AAA =.

Teorema 2.- Elementos neutros para los operadores (+) y (.) Expresin Dual 11 =+A 00. =A

Teorema 3.- Involucin. Expresin

AA =

Teorema 4.- Absorcin. Expresin Dual ABAA =+ ).( ABAA =+ )(.

Teorema 5.- Expresin Dual BABAA +=+ ).( BABAA .)(. =+

5

Teorema 6.- Expresin Dual ABABA =+ ).().( ABABA =++ )(.)(

Teorema 7.- Expresin Dual

).().()..().( CABACBABA +=+ )(.)()(.)( CABACBABA ++=+++

Teorema 8.- Teorema de DE MORGAN. Expresin Dual BABA .)( =+ BABA +=).(

Se puede generalizar el teorema de DE MORGAN, como sigue: Expresin Dual NCBANCBA ........)......( =++++ NCBANCBA ++++= ......).........(

La regla para complementar una expresin es utilizar cualquiera de las dos relaciones anteriores, reemplazando cada operador (+) por un operador (.) y viceversa y adems reemplazando cada variable por su complemento.

Se debe tener cuidado al aplicar el teorema de DE MORGAN respetando la precedencia de los operadores, as: (.) tiene precedencia sobre (+), cuando no se indican los parntesis.

Ejemplo 2.

CBACBAqueObserve

CABACBACABACBA

CABACBACBACBA

CBACBASolucin

CBAHallar

++

++=+

+++=+

+=+

+=+

=+

+

.).(

)(.)().()()().(

).().().()(.).(

).(.).(:

).(

Teorema 9.- Consenso. Expresin Dual

CABACBCABA ..... +=++ )).(()).().(( CABACBCABA ++=+++