hola mundo

Departamento de Arquitectura

Instituto de Computación

Universidad de la República
Montevideo - Uruguay

Notas de Teórico
Álgebra de Boole

Arquitectura de Computadoras
(Versión 4.3 - 2013)

Arquitectura de Computadoras

3

Notas de Teórico

ALGEBRA DE BOOLE

3.1

Introducción.

El álgebra de Boole es una herramienta de fundamental importancia en el mundo de
lacomputación. Las propiedades que se verifican en ella sirven de base al diseño y la
construcción de las computadoras que trabajan con objetos cuyos valores son discretos,
es decir las computadoras digitales, en particular las binarias (en las cuales los objetos
básicos tienen solo 2 valores posibles) las que son, en definitiva, la totalidad de las
computadoras de uso corriente.
Desde ya adelantemosque no se verán aquí detalles formales de la construcción
algebraica, ni todas las propiedades que se verifican, así como tampoco todos los métodos
de síntesis de funciones booleanas que habitualmente se incluyen en este tema en cursos
de lógica y/o diseño lógico.
Como toda álgebra, la de Boole parte de un cuerpo axiomático, el cual puede
adquirir diversas formas, variando la cantidad ycalidad de los axiomas. Aquí en particular
tomaremos uno: el propuesto por Huntington en 1904 que tiene la ventaja de ser
consistente e independiente.

3.2

Axiomas.
1. Existe un conjunto G de objetos, sujetos a una relación de equivalencia, denotada
por "=" que satisface el principio de sustitución.
Esto significa que si a = b, b puede sustituir a a en cualquier expresión que la
contenga,sin alterar la validez de la expresión.
2. (a) Se define una regla de combinación "+" en tal forma que

a + b está en G siempre

que al menos a o b lo estén.
(b) Se define una regla de combinación "⋅" en tal forma que a ⋅ b está en G siempre
que tanto a como b lo estén.
3. Neutros.
(a) Existe un elemento 0 en G tal que para cada a de G: a + 0 = a
(b) Existe un elemento 1 en G tal que paracada a de G: a ⋅ 1 = a
4. Conmutativos.
Para todo par de elementos a y b pertenecientes a G se cumple:

(a) a + b = b + a
(b) a ⋅ b = b ⋅ a
5. Distributivos.
Para toda terna de elementos a, b, c pertenecientes a G se cumple:
a
b

(a) a + (b ⋅ c) = (a + b) ⋅ (a + c)
(b) a ⋅ (b + c) = a . b + a ⋅ c

Instituto de Computación - Facultad de Ingeniería - UDELAR

2

Arquitectura deComputadoras

Notas de Teórico

6. Complemento.
Para cada elemento a de G existe un elemento a tal que:

a⋅ a = 0
a+ a = 1

7. Existen por lo menos dos elementos x,

y en G tal que x y

Existe similitud de muchos de estos postulados con los del álgebra común. Sin
embargo, la primera de las reglas distributivas (sobre la suma) y la existencia del
complemento diferencian en formafundamental esta álgebra de la común.

3.3

Modelo aritmético.

El ejemplo más simple del álgebra de Boole se compone de un conjunto G de 2
elementos: "0" y "1". Como es natural estos dos elementos deben coincidir con los neutros
de las reglas de combinación para satisfacer el axioma 3. Las reglas de combinación
debemos definirlas de manera de satisfacer los axiomas.
Así de acuerdo al axioma3 :

0+ 0 = 0
1+ 0 = 1

0⋅1= 0
1⋅ 1 = 1

(a = 0)
(a = 1)

de acuerdo al axioma 4

0+ 1= 1

1⋅ 0 = 0

y teniendo presente el axioma 5 :

1 + (1 ⋅ 0) = (1 + 1) ⋅ (1 + 0)
1 + 0 = (1 + 1) ⋅ 1
1 = 1+ 1

(5a con a = 1, b = 1, c = 0)

0 ⋅ (0 + 1) = 0 ⋅ 0 + 0 ⋅ 1
0⋅1= 0⋅ 0+ 0
0 = 0⋅ 0

(5b con a = 0, b = 0, c = 1)

(por axioma 3)

(por axioma 3)

Por lo tanto las reglascompletas son:

0+
0+
1+
1+

0=
1=
0=
1=

0
1
1
1

0⋅ 0 =
0⋅ 1 =
1⋅ 0 =
1⋅ 1 =

0
0
0
1

Nosotros usaremos esta versión "binaria" del álgebra de Boole.

Instituto de Computación - Facultad de Ingeniería - UDELAR

3

Arquitectura de Computadoras

3.4

Notas de Teórico

Propiedades.


Dualidad

Si analizamos los postulados veremos que los mismos se...