Material para el curso de Arquitectura

Algebra de boole
1 ALGEBRA DE BOOLE

1.1 Introducción.

El álgebra de Boole es una herramienta de fundamental importancia en el mundo de la

computació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 casi
totalidad de las computadoras de uso corriente.

Desde ya adelantemos que 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 y calidad de los axiomas. Aquí en particular
tomaremos uno: el propuesto por Huntington en 1904 que tiene la ventaja de ser
consistente e independiente.

1.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 tanto a como 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 para cada 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) a + (b c) = (a + b) (a + c)

R.C Página 1
 Material para el curso de Arquitectura
Algebra de boole

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

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

La 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 forma fundamental esta álgebra de la común.

1.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 axioma 3 :

De acuerdo al axioma 4 0 0 0 0 1 0 (a 0)
1 0 1 11 1 (a 1)

y teniendo presente el axioma 5 : 0 1 1 1 0 0

1 (1 0) (1 1) (1 0) (5a con a 1, b 1, c 0)
1 0 (1 1) 1
1 1 1 (por axioma 3)

0 (0 1) 0 0 0 1 (5b con a 0, b 0, c 1)
0 1 0 0 0
0 0 0 (por axioma 3)

Por lo tanto las reglas completas son:

0 0 0 0 0 0
0 1 1 0 1 0
1 0 1 1 0 0
1 1 1 11 1

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

R.C Página 2
 Material para el curso de Arquitectura
Algebra de boole
1.4 Propiedades.

 Dualidad

Si analizamos los postulados veremos que los mismos se presentan de a pares y en tal
forma que uno de la pareja se obtiene de otro cambiando "0" por "1" junto con "+" por
" " (y viceversa). Esto asegura que cada propiedad que se demuestre en esta
Álgebra tiene una "dual" que también es cierta (para demostrar la dual bastaría con
repetir la demostración realizada sustituyendo cada postulado o propiedad utilizada
por su dual).

 Asociativa

a) a (b c) (a b) c
b) a (b c) (a b) c

Si bien las leyes asociativas son muchas veces incluidas dentro del cuerpo axiomático,
de hecho son demostrables a partir de los axiomas aquí presentados, (demostración que
no haremos) por lo cual las presentamos como propiedades.

 Idempotencia

Para todo elemento en G se cumple:

a a a
a a a

Demostración:

a a (a a) 1 (3b)
a a (a a) (a a ) (6)
a a a (a a ) (5a)
a a a 0 (6)
a a a

a a a (Dualidad)

 Neutros Cruzados

Para todo elemento en G se cumple

a 1 1
a 0 0

Demostración:

R.C Página 3
 Material para el curso de Arquitectura
Algebra de boole

a 1 a (a a ) (6)
a 1 (a a) a (asociativa)
a 1 a a (idempotencia)
a 1 1

a 0 0 (Dualidad)

Entonces los axiomas 1, 2, 3, 4, 5 y 7 se satisfacen por definición y es fácil verificar

que el G (complemento) también es cierto.

Construimos por lo tanto un modelo "aritmético" de álgebra de Boole que podemos

denominar "binario" y es en definitiva con la que trabajaremos.

Muchas veces las reglas de combinación se presentan como tablas (como las funciones
booleanas más generales que veremos más tarde)

a b a+b a b ab
0 0 0 0 0 0
0 1 1 0 1 0
1 0 1 1 0 0
1 1 1 1 1 1

En general notaremos a b como ab, además la operación tendráá mayor precedencia

que la operación +.

 Complemento de complemento

Para cada elemento de G se cumple : a a

Para todo par de elementos de G se cumple :

a ab a
a ( a b) a

Para todo par de elementos de G se cumple :

a ab a b
a ( a b) ab

 Ley de De Morgan

R.C Página 4
 Material para el curso de Arquitectura
Algebra de boole
Para todo par de elementos de G se cumple :

( a b) ab
(ab) a b

Estas reglas de De Morgan pueden generarse para cualquier número de variables.

(a1 a2 ... a n ) a1 a 2 ...a n

(a1 a 2 ...a n ) a1 a2 ... a n

1.5 Modelo lógico.

Los valores que pueden asignarse a un juicio, desde el punto de vista

lógico, son dos: verdadero (V) o falso (F).

Un juicio al cual se le aplica el operador lógico no (negación) forma un nuevo juicio.

Dos juicios pueden combinarse para formar un tercero mediante los operadores lógicos
"o" e "y".

Si vinculamos los valores booleanos 0 y 1 con los valores lógicos F y V

respectivamente, encontramos que las operaciones del álgebra de Boole "binaria"
asigna correctamente los valores lógicos del juicio combinación. Esto se comprueba
observando que:

verdadero o verdadero es verdadero

verdadero o falso es verdadero
falso o verdadero es verdadero
falso o falso es falso

verdadero y verdadero es verdadero

verdadero y falso es falso
falso y verdadero es falso
falso y falso es falso

Por lo cual se puede concluir que el modelo "lógico" es isomorfo con el "aritmético"
(binario) realizando la correspondencia.

F 0
V 1

Es posiblemente consecuencia de este isomorfismo que las reglas de

R.C Página 5
 Material para el curso de Arquitectura
Algebra de boole
combinación "+" y "." del álgebra de Boole reciban los nombres de OR ("o" en
inglés) y AND ("y" en inglés) respectivamente.

1.6 Modelo circuital.

Otro modelo posible es el que surge de considerar llaves eléctricas y

asociar el valor A a la llave abierta (no pasa corriente, circuito abierto) y el valor
C con la llave cerrada (pasa corriente, circuito cerrado).

Es fácil comprobar que la combinación de llaves en paralelo o en serie cumplen las

mismas reglas definidas en el modelo aritmético para "+" y "." respectivamente.

LL1 LL2 Circuito PQ LL1 LL2 Circuito PQ

“+” “”
A A A A A A
A C C A C A
C A C C A A
C C C C C C

Entonces existe también un isomorfismo entre el modelo "circuital" y el "aritmético" si

hacemos la asociación

A 0
C 1
paralelo
serie

Este isomorfismo es de fundamental importancia para la construcción práctica de las

computadoras binarias.

1.7 Expresiones booleanas.

Llamamos constante a todo elemento del conjunto G que define al

álgebra. Las variables podrán tomar como valor cualquier elemento de G ( 0 " 1
en el caso en que trabajamos).
Una expresión la podemos definir recursivamente como

1) las constantes y las variables

2) el complemento de una expresión booleana
3) el OR (+) o el AND ( ) de dos expresiones booleanas.

1.8 Funciones booleanas.

Una función "F" de n variables x1 ... x n booleanas ser una aplicación del espacio Gn
sobre el espacio G de tal forma que para cada valor posible de la n-upla x 1 ... x n, donde
cada variable puede tomar cualquier valor del conjunto (en nuestro caso {0, 1} ), se
asocia un valor del recorrido G.

R.C Página 6
 Material para el curso de Arquitectura
Algebra de boole

Una de las formas de expresar F es a través de las denominadas tablas de verdad

que indican el resultado de F para cada valor posible de la n-upla; por ejemplo :

a b c F
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 1

Otras formas de representar F incluyen el método de indicar sólo los puntos en los
cuales F vale 1 o sólo los puntos en los cuales vale 0 (representaciones d y c
respectivamente)
Por ejemplo, la función anterior se puede expresar :

f (a, b, c) d (1,4,5,7) f (a, b, c) c(0,2,3,6)

Otra forma de expresar las funciones es a través de expresiones; ejemplo, la función

anterior sería:

f ac ab abc

1.9 Conectivas binarias.

Un caso interesante de estudiar es el de las funciones booleanas de 2 variables. Por

ser dos variables las combinaciones posibles son 4, es decir "F" tiene 4 duplas (4
puntos) por tanto existen 16 funciones booleanas de dos variables posibles. Algunas de
ellas no interesan, veamos las tablas de verdad de las más útiles.

a b or and xor nor nand Equiv Idemp Tautol

. .
0 0 0 0 0 1 1 1 0 1
0 1 1 0 1 0 1 0 0 1
1 0 1 0 1 0 1 0 0 1
1 1 1 1 0 0 0 1 0 1

Nota :
la NOR es el complemento de la OR
la NAND es el complemento de AND
la XOR ("O" exclusivo) puede definirse como: a b ab ab

R.C Página 7
 Material para el curso de Arquitectura
Algebra de boole
1.9.1 OR exclusivo.

El XOR es una función muy importante (es la suma aritmética binaria

módulo 2) y cumple las propiedades :
1) Asociativa
2) Conmutativa
3) Distributiva: a(b c) ab ac
4) a 0 a
5) a 1 a
6) a a 0
7) a b ab a b
8) Cancelativa: a b a c b c

1.9.2 Suma de productos canónicos.

Desarrollaremos a continuación un método sistemático para encontrar

una expresión algebraica para una función cualquiera dada.
Definamos producto canónico de n variables x1 ... xn al producto de todas ellas en el
cual cada variable aparece una y sólo una vez, en forma simple o complementada.
Una suma de productos canónicos es una expresión formada sumando productos
canónicos.
Existe un teorema (que no demostraremos) que afirma que toda función f de n variables
puede expresarse como:
f x1 , x 2 ,...., x n x1 x 2 x3 ... x n f (1,1,1,...,1)
x1 x 2 x3 ... x n f (0,1,1,...,1)
x1 x 2 x3 ... x n f (1,0,1,...,1)
..............
x1 x 2 x3 ... xn f (0,0,0,...,0)

Es decir toda función de n variables puede expresarse como la suma de todos sus
productos canónicos afectado cada producto canónico por un coeficiente. Este
coeficiente es el valor de la función evaluado en el punto tal que las variables que en el
producto canónico asociado aparecen simples tengan el valor 1 y las que aparecen
complementadas el valor 0.

Este teorema, de fundamental importancia nos permite enunciar un método de

construcción de una expresión que represente una función dada. El método es el
siguiente: se tienen en cuenta solo los puntos en los que la función vale 1 (por el
teorema los productos asociados con los puntos en los que la función vale 0
desaparecen por estar afectados por un coeficiente nulo: el propio valor de la función);
en esos puntos se busca el producto canónico asociado que es aquel donde la variable
aparece simple si en el punto vale 1 o complementada si vale 0. De esta manera la
función puede expresarse como suma de los productos canónicos así elegidos.

Por ejemplo sea la función de tres variables

R.C Página 8
 Material para el curso de Arquitectura
Algebra de boole

a b c f
0 0 0 0
0 0 1 1 a bc
0 1 0 0
0 1 1 1 abc
1 0 0 1 abc
1 0 1 0
1 1 0 0
1 1 1 0

Entonces f puede expresarse como f (a, b, c) a b c a b c a b c

1.9.3 Productos de sumas canónicas.

Como todo en el álgebra de Boole, existe un método dual del anterior: el

producto de sumas canónicas. En este caso deben considerarse los puntos en
los que la función vale 0 y buscar las sumas canónicas asociadas que son
aquellas en las que la variable aparece simple si tiene valor 0 y complementada
si tiene valor 1.

1.10 Operadores lógicamente completos.

Un conjunto de operadores se llama lógicamente completo si cualquier función

booleana puede expresarse mediante los mismos.

Del teorema de los productos canónicos, ya enunciado, se extrae una conclusión

fundamental tanto del punto de vista lógico como del circuital: el conjunto de
operadores +, . y ' es lógicamente completo.

Otra consecuencia es que para probar que un cierto conjunto de operadores es

lógicamente completo, alcanza con probar que con ellos se pueden implementar el OR,
el AND y el NOT (complemento).

Es fácil probar que el conjunto OR, NOT es lógicamente completo notando que el
AND se puede construir como:

(ab) a b (por De Morgan) a b (a b)

R.C Página 9
 Material para el curso de Arquitectura
Algebra de boole
Más interesante aún es mostrar que un solo operador, como el NAND, es lógicamente
completo. Debemos ver como implementar el NOT y el AND y el OR (representaremos
con # el NAND):

a# a (a.a) a (complemento)
(a # b)# (a # b) ( a # b) (a.b) a.b (AND)
(a # a)# (b# b) (a.b) (a b) a b (OR) por De Morgan

Por lo cual el NAND es lógicamente completo.

1.11 Simplificación.

Hasta ahora hemos visto un método sistemático de expresar las funciones booleanas
como expresión de sus variables. Pero este método no asegura que la expresión lograda
sea la más simple posible. El hecho que la expresión de una función sea lo más simple
posible no es algo trivial o caprichoso, es de fundamental importancia en la
construcción práctica de circuitos lógicos, por eso analizaremos algunos métodos para
simplificar expresiones booleanas, de manera de aplicarlos a las expresiones obtenidas
como sumas de productos canónicos.

1.11.1 Método algebraico.

El método consiste en la aplicación, más o menos ingeniosa, de

transformaciones algebraicas de manera de lograr expresiones más sencillas.
Por supuesto que este no es un método sistemático, pero es la base, al fin, de
los métodos sistemáticos.

Resumamos aquí algunas propiedades vistas del álgebra que serán de utilidad en la tarea
de simplificar:

1) f f 0
2) f f 1
3) g f gf f
4) g f f f
5) f f g f g

Veamos un par de ejemplos de como se aplican estas propiedades para reducir

expresiones:

a) Sea f 1 abc abc abc

Por la aplicación de la propiedad 3 a los primeros dos términos y a los dos últimos
queda

f1 ab ab

R.C Página 10
 Material para el curso de Arquitectura
Algebra de boole

Y aplicando la propiedad 3 queda su expresión más sencilla

f1 b

b) Sea f 2 abc abc abc abc

Aplicando la propiedad 3 a los dos primeros términos queda

f2 bc abc abc

por la propiedad distributiva

f2 b (c a c) abc

por la propiedad 5 al paréntesis

f2 b(c a ) abc

por distributiva aplicada dos veces

f2 c(b ab) ab

por propiedad 5 al paréntesis

f2 c ( a b) ab

Entonces la expresión de f2 a la que llegamos es:

f2 ab ac bc

Esta sin embargo no es la expresión más reducida de f2. Vemos como hubiera quedado
aplicando la propiedad 3 al primer y cuarto miembro y al segundo y tercero

f2 ac ab

siendo esta sí, la expresión más reducida.

Como vemos entonces el procedimiento descrito no asegura reducir la expresión a un
mínimo ya que depende de como se elijan las propiedades a aplicar y los términos sobre los
que se aplican.

1.11.2 Métodos sistemáticos.

Los modelos sistemáticos se basan en la propiedad 3 g f g f f y

son básicamente uno "gráfico" (Diagrama de Karnaugh) y otro "algorítmico" o
"numérico" (Método de Quine-McKlusky)

R.C Página 11
 Material para el curso de Arquitectura
Algebra de boole

A continuación veremos una introducción al método gráfico

1.11.2.1 Diagrama de Karnaugh.

Este método consiste en representar en forma gráfica una función como

suma de productos canónicos y hacerlo de tal forma que sea sencillo
establecer procedimientos sistemáticos para hallar las agrupaciones de
términos más convenientes para simplificar la expresión. Esto se logra
utilizando una cuadrícula en la cual a cada cuadrado elemental corresponde un
producto canónico posible y tal que al pasar de uno a otro cualquiera de sus
cuatro adyacentes solo cambie el valor de una de las variables en juego. Por
ejemplo para tres variables la cuadrícula es:

ab 00 01 11 10
0
1

Para cuatro variables:

ab/cd 00 01 11 10
00
01
11
10

En esta cuadrícula se marcan con "1" los lugares para los cuales la
combinación de valores de las variables hace que la función valga 1 y el
método consiste en buscar agrupar los "unos" formando los rectángulos más
grandes posibles ( que tengan todos 1 en su interior), repitiendo este proceso
hasta que todos los puntos donde la función vale "1" estén comprendidos en
algún rectángulo ( siendo la cantidad total de rectángulos utilizados la menor
posible)

Nota: el diagrama es circular (los de cada borde son adyacentes con los del borde
simétrico)

Ejemplos:

ab/cd 00 01 11 10
00 1 1
01 1 1 1
11
10

ab/cd 00 01 11 10
00 1 1 1

R.C Página 12
 Material para el curso de Arquitectura
Algebra de boole
01 1 1
11
10 1 1

Una vez realizado el proceso anterior la mínima expresión de la función

se obtiene sumando los términos asociados a cada rectángulo los cuales son el
producto de las variables (simples o complementadas) cuyo valor no cambia en
él.

Por ejemplo en los diagramas anteriores sería

1) f 3 ac bcd
2) f 4 ad abc a cd

Para finalizar veamos como se aplica el método al caso ya visto de la función:

f2 abc abc abc abc

El diagrama de Karnaugh correspondiente es

ab 00 01 11 10
0 1
1 1 1 1

Entonces la función queda f 2 ac ab la cual coincide, como era de esperar, con la

expresión más reducida hallada por el método "algebraico".

La primer expresión de f2 hallada con dicho método tenía además el término bc que
corresponde al rectángulo formado por los dos extremos inferiores del diagrama que
aquí queda evidente que no era necesario puesto que con los otros dos términos
cubrimos todos los puntos donde la función vale "1".

R.C Página 13