Sistemas Digitales 2

Álgebra Booleana

Ö La herramienta fundamental para el análisis y diseño de circuitos digitales es el Álgebra Booleana.

Esta álgebra es un conjunto de reglas matemáticas (similares en algunos aspectos al álgebra

convencional), pero que tienen la virtud de corresponder al comportamiento de circuitos basados en

dispositivos de conmutación (interruptores, relevadores, transistores, etc). En este capítulo se

presentan los postulados que definen el álgebra booleana, se presentan en forma de teoremas los

resultados más importantes, se presentan también los tres ejemplos clásicos de álgebras boolenas

(lógica proposicional, álgebra de conjuntos, álgebra de switches) y herramientas básicas como tablas

de verdad y diagramas de Venn.

4.1.- POSTULADOS DEL ÁLGEBRA BOOLEANA

El Álgebra de Boole, fue presentada originalmente por el inglés George Boole, en el año de 1854 en su

artículo "An Investigation of the Laws of Thoght ... ", sin embargo, las primeras aplicaciones a circuitos de

conmutación fueron desarrolladas por Claude Shannon en su tesis doctoral "Análisis simbólico de los

circuitos de conmutación y relés" hasta 1938. A continuación se presentan los postulados fundamentales

del álgebra de Boole

POSTULADOS DEL ÁLGEBRA DE BOOLE

O Postulado 1. Definición. El álgebra booleana es un sistema algebraico definido en un conjunto

B, el cual contiene dos o más elementos y entre los cuales se definen dos operaciones

denominadas "suma u operación OR" ( + ) y "producto o multiplicación u operación AND" ( ), las

cuales cumplen con las siguientes propiedades:

Postulado 2. Existencia de Neutros. Existen en B el elemento neutro de la suma, denominado

O y el neutro de la multiplicación, denominado 1, tales que para cualquier elemento x de s:

(a) x + O = x (b) x. 1 = x

Postulado 3. Conmutatividad. Para cada x, y en B:

(a) x+y = y+x (b) x y =y x

Postulado 4. Asociatividad. Para cada x, y, z en B:

(a) x + (y + z) = (x + y) + z (b) x (y z) = (x y)  z

Postulado 5. Distributividad. Para cada x, y, z en B:

(a) x+(y z)=(x+y)   (x+z) (b) x (y+z)=(x y)+(x z)

Postulado 6. Existencia de Complementos. Para cada x en B existe un elemento único

denotado x (también denotado x’), llamado complemento de x tal que

(a) x+x = 1 (b) x   x = O

Capítulo 4 Álgebra Booleana

30

4.2.- EJEMPLOS DE ÁLGEBRAS DE BOOLE

En un principio algunos de los postulados anteriores pueden parecer extraños, especialmente aquellos

que son diferentes al álgebra con número reales (como el 5a, el 6a y el 6b), y puede ser difícil encontrar

situaciones de interés que cumplan al pie de la letra con cada uno de ellos, sin embargo, existen varios

ejemplos, de los cuales se presentan los siguientes tres clásicos, en los cuales se verifica que se trata de

álgebras de Boole, es decir, que se cumple postulado por postulado.

4.2.1.- ÁLGEBRA DE CONJUNTOS

1.- Para este ejemplo el conjunto B es el conjunto de todos los conjuntos a tratar. La suma es la

unión de conjuntos (U) y la multiplicación es la intersección (Ç) de conjuntos.

2.- Existencia de neutros. El neutro de la unión es el conjunto vacío F , mientras que el neutro de la

intersección es el conjunto universo U, ya que para cualquier conjunto arbitrario A, A U F = A y A Ç U

= A.

3.- Conmutatividad. La unión y la intersección son conmutativas, ya que para cualquier par de

conjuntos A, B: A U B = B U A y A ÇB = B ÇA

4.- Asociatividad. La unión y la intersección de conjuntos son asociativas, ya que para cualesquiera

tres conjuntos A, B, C: A U (B U C) = (A U B) U C y A Ç (B Ç C) = (A Ç B) Ç C

5.- Distributividad. La unión de conjuntos es distributiva sobre la intersección, y viceversa, la

intersección es distributiva sobre la unión, ya que para cualesquiera tres conjuntos A, B, C: A U (B Ç

C) = (A U B) Ç (A U C) y A Ç (B U C) = (A Ç B) U (A Ç C)

6.- Existencia de complementos. El conjunto complemento Ac cumple con las propiedades deseadas:

A U Ac = U y A Ç Ac = F

Algunos de los enunciados anteriores pueden ser difíciles de obtener, o recordar, especialmente la

distributividad, por ello, es conveniente tener en cuenta una herramienta gráfica en la cual estos

enunciados se vuelven evidentes casi a simple vista:

4.2.1.1.- DIAGRAMAS DE VENN

En la siguiente figura se muestran diagramas de Venn para los conjuntos A, B, A U B y A Ç B

Conjunto A

A B

Conjunto B

A B

Conjunto A U B

A B

Conjunto A Ç B

A B

Capítulo 4 Álgebra Booleana

31

A continuación se muestra el conjunto A y su complemento Ac.

Conjunto A

A

Conjunto Ac

A Ac

Ejemplo.- En los siguientes diagramas de Venn se ilustra la manera como pueden usarse los diagramas

de Venn para ilustrar cada uno de los postulados y propiedades del álgebra de conjuntos. En este caso

se usan para ilustrar la propiedad de distributividad de la unión sobre la intersección

C B

A

C B

A

C B

A

C B

A B Ç C A U (B Ç C)

A U B A U C (A U B) Ç (A U C)

A A

C B

A

C B

Distributividad de la Unión sobre la Intersección

4.2.2.- CIRCUITOS DE CONMUTACIÓN

1.- Para este ejemplo de álgebra de Boole, el conjunto B es el conjunto de todos los switches o

interruptores. La operación suma de switches es la conexión en paralelo y la multiplicación de switches

es la conexión en serie, como se muestra en la siguiente figura. Los valores que pueden tomar los

switches son sólo dos: {ON, OFF} o bien, {1,0}.

Switches A, B Suma (A+B)

A

B

A

B

A B

Producto (A Ÿ B)

Capítulo 4 Álgebra Booleana

32

2.- Existencia de neutros. El neutro de la suma, es un circuito abierto (un switch que siempre está

abierto), mientras que el neutro del producto es un corto circuito (un switch que siempre está cerrado)

3.- Conmutatividad. Evidentemente las conexiones en serie y en paralelo funcionan de la misma manera

independientemente del orden de colocación de los switches que interconectan.

4.- Asociatividad. Las conexiones en serie y en paralelo son asociativas, es decir, al conectar tres

switches en paralelo, no importa cual par se conecte primero. En forma similar pasa con la conexión de

tres switches en serie.

5.- Distributividad. La conexión serie es distributiva sobre la conexión en paralelo y la conexión paralelo

es distributiva sobre la conexión en serie, en el sentido que se ilustra en la figura siguiente

A Ÿ (B+C)

=

A

B

AŸB + AŸC

C

A B

A C

A + BŸC

=

A

B

(A + B) Ÿ (A +C)

C

A

B C

A

Observación 1: Nótese que en la figura anterior se está suponiendo que el switch A se puede usar en

dos lugares diferentes, esto es posible físicamente simplemente construyendo dos switches acoplados

mecánicamente de manera que cuando uno esté abierto el otro también lo esté y cuando uno esté

cerrado, el otro también se cierre.

Observación 2: Jerarquía de operaciones.- En adelante, se utilizará la notación algebraica utilizada en

la figura anterior, en la cual se supone que cuando en una misma expresión aparecen sumas y productos

sin usar paréntesis se realiza primero el producto y luego la suma. Cuando se quiere alterar este orden

de jerarquía de operaciones se usan paréntesis para indicar que la operación que está entre paréntesis

se debe realizar primero.

6.- Existencia de complementos. Se puede fabricar un switch A complemento de otro switch A

simplemente acoplando mecánicamente ambos, para que cuando uno se abra el otro se cierre y

viceversa.

4.2.3.- LÓGICA PROPOSICIONAL

1.- Para este ejemplo de álgebra de Boole el conjunto B es el conjunto de todos los enunciados

gramaticales. La operación suma (+) es la conjunción gramatical “o” (OR), la multiplicación es la

conjunción gramatical “y” (AND) y los valores que puede tomar un enunciado gramatical son

{falso,verdadero} = {F,V}.

En la siguiente figura se muestra un ejemplo en donde se aclara de manera precisa el sentido de las

operaciones OR y AND (ya que puede ser diferente de la interpretación gramatical cotidiana), para ello se

introduce el concepto de tabla de verdad, la cual es simplemente una tabulación de los enunciados y

todas las posibles combinaciones de sus correspondientes valores de verdad o falsedad.

Capítulo 4 Álgebra Booleana

33

2.- Existencia de neutros. El neutro de la suma, es un enunciado que evidentemente siempre es falso,

(ver ejemplo). en forma similar, el neutro de la multiplicación es un enunciado que evidentemente siempre

es verdadero.

3.- Conmutatividad. Evidentemente las conjunciones “y”, “o” no alteran el sentido del enunciado total,

independientemente del orden en que son tomados.

...