CAPITULO II

ALGEBRA DE BOOLE

CONTENIDOS:

2.1 El Algebra de Boole.

2.2 Operaciones del Algebra de Boole.

2.3 Postulados y Teoremas del Algebra de Boole.

2.4 Funciones booleanas.

2.5 Formas canónicas.

2.6 Simplificación de funciones booleanas.

2.7 Ejercicios.

OBJETIVOS:

Al finalizar el presente capítulo, el lector estará capacitado para:

1. Comprender claramente lo que representa al Algebra de Boole.

2. Aplicar las propiedades y Teoremas del Algebra de Boole.

3. Caracterizar las funciones Booleanas y sus formas de representar.

4. Aplicar métodos algebraicos de simplificación de funciones booleanas.

5. Aplicar el Método de Karnaugh para simplificar funciones booleanas.

2.1 EL ALGEBRA DE BOOLE

Como en muchos otros aspectos de ingeniería, los modelos matemáticos son

fundamentales para representar sistemas, en este caso, digitales. Dado que los

sistemas digitales utilizan el sistema de numeración binario, los modelos matemáticos

utilizados para este tipo de circuitos deben manejar recursos matemáticos soportados

por el sistema de numeración binario, es decir, que utilicen como dígitos sólo al 0 y al

1 y como operaciones la suma binaria (+), el producto binario (.) y el complemento o

inversión ( ).

A este conjunto de dígitos y relaciones entre ellos se denomina álgebra. En el caso

específico de los circuitos digitales, esta es el álgebra binaria o álgebra de Boole, en

honor al científico que estudió la misma.

Originalmente, el álgebra de Boole estaba destinada al estudio del carácter de verdad

o falsedad de proposiciones y al mismo en el caso de las relaciones entre ellas, dado

que este análisis comprendía una característica binaria de las proposiciones, pudo

fácilmente adaptarse al análisis de los números binarios y posteriormente al de los

sistemas digitales, ambos binarios por naturaleza.

El álgebra de Boole, como la convencional que conocemos, tiene una serie de

postulados y teoremas en los cueles basa sus procedimientos y operaciones

algebraicas, a continuación haremos una reseña de los principales. Al conjunto de

elementos del álgebra de Boole (dígitos 0 y 1 y operaciones +, . y ) lo llamaremos

conjunto B.
2.2 OPERACIONES DEL ALGREBRA DE BOOLE

En el Álgebra de Boole hay dos operaciones, denotadas con los símbolos + y ., pero

se debe resaltar que no tienen nada que ver con las operaciones que todos

conocemos de suma y producto. No hay que confundirlas. El + y el . del Algebra de

Boole se aplican a bits, es decir, a números que sólo pueden ser el ’0’ ó el ’1’.

LA OPERACION +

Esta operación se define de la siguiente manera:

0+0=0

0+1=1

1+0=1

1+1=1

Las tres primeras operaciones nos resultan obvias, son iguales que la suma que

conocemos, sin embargo la expresión 1 + 1 = 1 nos puede resultar extraña. Pero hay

que recordar que aquí estamos utilizando otra operación que no es la suma

convencional, la denotamos con el mismo símbolo ’+’, pero no es una suma normal.

Si nos fijamos en esta nueva operación, notamos lo siguiente: El resultado siempre

es igual a ’1’ cuando alguno de los bits sumandos es igual a ’1’. O lo que es lo mismo,
el resultado de esta suma sólo da ’0’ si los dos bits que estamos sumando son iguales

a cero. En caso contrario valdrá ’1’.

LA OPERACION .

Esta operación se define así:

0.0=0

0.1=0

1.0=0

1.1=1

En este caso, la operación es más intutitiva, puesto que es igual que el producto de

números Reales. Si nos fijamos, vemos que el resultado sólo vale ’1’ cuando los dos

bits están a ’1’, o visto de otra manera, el resultado es ’0’ cuando alguno de los dos

bits es ’0’.

LA NEGACION

La operación de negación nos permite obtener el estado complementario del bit o

variable booleana al que se lo aplicamos. Se define de la siguiente manera:

 1 0
0 1

Es decir, que si se lo aplicamos a ’0’ obtenemos ’1’ y si se lo aplicamos al ’1’

obtenemos ’0’.

Esta operación nos permite cambiar el estado de una variable o de una función

booleana. Si a es una variable boolena, a tiene el estado contrario.

2.3 POSTULADOS Y TEOREMAS DEL ALGEBRA DE BOOLE

POSTULADOS: Aceptados como verdaderos y absolutos.

1.- El conjunto B es cerrado con respecto a las dos operaciones.

 a, b, a  b 
a. b 

2.- Elemento identidad.

 a, b, a0 a
a.1  a
3.- Propiedad conmutativa.

 a, b, ab  ba

a. b  b. a

4.- Propiedad distributiva.

 a, b, c  : a.(b  c)  (a. b)  (a. c)

a  (b. c)  (a  b).(a  c)

5.- Complemento

 a, b , a  a 1
a. a  0

TEOREMAS: Demostrables en base a los postulados.

1.- Principio de dualidad: Sea E una igualdad entre dos expresiones booleanas y ED

otra igualdad obtenida a partir de E intercambiando los operandos + y ., y los

elementos de identidad 0 y 1. Toda expresión booleana tiene su expresión dual

igualmente válida.

2.- Idempotencia:
 aa a
a. a  a

3.- Elemento identidad

a 1  1
a.0  0

4.- Involución

aa

5.- Absorción

a  a. b  a
a.(a  b)  a

6.- Simplificación

a  a. b  a  b
a.(a  b)  a. b

7.- Asociatividad
 a  (b  c)  (a  b)  c
a.(a. b)  (a. b). c

8.- Leyes de De Morgan

a  b  c  d  ...  a. b. c. d ...
a. b. c. d ...  a  b  c  d  ...

9.- Complemento de una función

f (a, b, c, d , ,.)  f (a, b, c, d ,., )

Es pertinente recordar en este momento que el álgebra de Bolle se aplica al sistema

de numeración binario, con sus propios elementos y reglas y no es igual (aunque si

similar) al álgebra convencional que conocemos; las operaciones, aunque tienen

nombres similares y símbolos iguales, tienen sus connotaciones particulares y por lo

tanto son diferentes a la suma y producto convencional que usamos en el día a día.

Debemos estar siempre conscientes de esto para poder aplicar las propiedades y

teoremas de manera adecuada y efectiva.

Como en cualquier tipo de álgebra, en el álgebra de Boole existe un orden de prelación

para las propiedades u operaciones que es el siguiente: , ., +, teniendo en cuenta

los símbolos de agrupación como ( ), [ ], etc., en sus diferentes niveles.

2.4 FUNCIONES BOOLEANAS

Se sabe que una variable booleana es un elemento del conjunto B que puede tomar

valores 0 o 1, y se representa generalmente por una letra minúscula.

Una función booleana es una expresión algebraica definida sobre variables lógicas,

en base a operaciones lógicas. Una función booleana o lógica puede tomar valor 0 o

1 según su estructura. Se denota generalmente con una letra minúscula seguida entre

paréntesis de las variables que la forman: f(a, b, c)= ….

El valor final de una función lógica combinacional depende exclusivamente de la

combinación de los valores de sus variables. Una herramienta fundamental para el

análisis de una función lógica es la denominada Tabla de Verdad, que es un arreglo

tabular en el que se incluyen las variables que forman la función y sus posibles

combinaciones, la función y su valor para cada una de estas combinaciones. La tabla

de verdad es una herramienta fundamental para el análisis y la síntesis de sistemas

digitales en general. La estructura general de una tabla de verdad es la que se muestra

a continuación:
 Variables
Función
(n)

Todas las
posibles Resultados parciales o
combinaciones finales de la función
(2n)

Fig. 2.1.- Tabla de verdad.

Cuanto mayor número de variables, mayor cantidad de filas tendrá la tabla de verdad.

La regla que se cumple es la siguiente: “Si la función tienen n variables, la tabla de

verdad tendrá 2n filas”. Veamos algunos ejemplos:

- Si una función tiene 2 variables, su tabla de verdad tendrá 4 filas.

- Si la función tiene 3 variables, la tabla tendrá 23 = 8 filas.

- Si la función tiene 4 variables, la tabla tendrá 24 = 16 filas.

- .....

OBTENCION DE UNA TABLA DE VERDAD A PARTIR DE UNA EXPRESION

Esto es bastante sencillo. Lo primero que hay que hacer es identificar el número de

variables de la función, para conocer el tamaño de la tabla de verdad. A continuación

escribimos números en binario en la parte de las variables. Finalmente vamos fila por

fila obteniendo el valor de la función, utilizando la expresión.

Ejemplo: Construir la tabla de verdad para la función definida por la expresión:

f  a. b

1. La función tiene 2 variables, luego la tabla de verdad tendrá 22 = 4 filas.

2. Dibujamos una tabla de verdad con 4 filas, y ponemos en la parte de la izquierda

el número de fila en binario natural, comenzando por la fila 0.

a b f
0 0
0 1
1 0
1 1

3. Aplicando la expresión, vamos calculando el valor de f. La primera fila se

corresponde con f(0,0), la segunda con f(0,1), la tercera con f(1,0) y la última con

f(1,1).

f (0, 0)  0.0  1.0  0

f (0,1)  0.1  1.1  1
f (1, 0)  1.0  0.0  0
f (1,1)  1.1  0.1  0

4. Ya podemos rellenar la tabla de verdad:

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

FUNCIONES INCOMPLETAMENTE ESPECIFICADAS

Son funciones en las que algunas de sus combinaciones no tienen un valor de

salida claramente especificado ya sea porque esa combinación de valores de

entrada no se va a dar nunca o porque no importa el valor que tenga la salida en

esas circunstancias.

Estas salidas se denotan con X en la tabla de verdad y para efectos de

simplificación pueden ser asumidos como 1 o 0 según convenga al diseñador, de

manera indistinta y no necesariamente todas iguales.

2.5 FORMAS CANONICAS

Una función lógica puede ser expresada como:

- Suma de productos: la función está dada como la suma de productos de

variables.

Ejemplo:

f  f (a, b, c)  ba  abc  abc  c

- Producto de sumas: la función está dada como el producto de sumas de

variables.

g  g ( x, y, z)  ( x  y  z ).( x  y  z ).( x  y  z ).( x  y  z )

La forma canónica de una función lógica es aquella que está expresada como los

términos anteriores pero en cada uno están presentes todas las variables de la

función, en su forma negada o no negada.

Ejemplo 1: Para suma de productos:

f  f (a, b, c)  abc  abc  abc  abc

A esta forma canónica se le llama también producto canónico o minitérminos

(minterms). Se puede denotar también usando el símbolo de sumatoria seguido entre

paréntesis de los números decimales de cada combinación que forma cada uno de

los productos, para el ejemplo anterior se tendrá:

 f   (7,3,1, 4)
3

Nótese que como índice inferior de la sumatoria se coloca el número de variables,

para consignar el número decimal de cada uno de los productos se considerará 1 si

la variable está sin negar y 0 si está negada, la combinación binaria final denotará el

número decimal.

Ejemplo 2: Para producto de sumas:

g  g ( x, y, z)  ( x  y  z ).( x  y  z ).( x  y  z ).( x  y  z )

A esta forma canónica se le llama también suma canónica o maxitérminos (maxterms).

Se puede denotar también usando el símbolo de productoria seguido entre paréntesis

de los números decimales de cada combinación que forma cada una de las sumas,

considerando la variable negada como uno y como cero si es sin negar, para el

ejemplo anterior se tendrá:

g  (1, 2,7,3)
3

Una función en su forma canónica puede tener un máximo de 2n términos.

Las formas canónicas de una función pueden ser obtenidas a partir de la tabla de

verdad de la función, de modo tal que si la función vale 1, esta combinación

corresponde a un producto en el cual las variables con valor 1 se toman sin negar y
las con valor 0 se toman negadas. Si la función toma valor 0, esta combinación genera

una suma, con la variable sin negar cuando toma valor 0 y negada si toma valor 1.

Esto se explica más claramente en la tabla siguiente:

Productos Sumas
a b c f
canónicos canónicas

0 0 0 0 abc
0 0 1 1 abc
0 1 0 1 abc
0 1 1 0 abc
1 0 0 1 abc
1 0 1 0 abc
1 1 0 1 abc
1 1 1 1 abc

Entonces las expresiones canónicas serán:

f  abc  abc  abc  abc  abc

g  (a  b  c).(a  b  c).(a  b  c)

Nótese que ambas expresiones canónicas son complementarias.