PDF de programación - tema 2 - representación y tratamiento de los sistemas digitales

Tema 2

REPRESENTACI ÓN Y
TRATAMIENTO DE LOS
SISTEMAS DIGITALES

2.1.

ÁLGEBRA DE BOOLE

En el diseño de los sistemas digitales se hace un uso extensivo de la teoría lógica. Es
preciso pues conocer detalladamente las propiedades matemáticas de las funciones lógicas.
Estas se incluyen en la teoría matemática de las Álgebras de Boole.

Definición 2.1 Un ÁLGEBRA DE BOOLE es un conjunto A = {a, b, c, ...} que verifica
los siguientes postulados:

1. Existen dos operaciones binarias internas (+ y ·) definidas sobre el conjunto, es de-
cir, el resultado de estas dos operaciones se encontrará siempre dentro del conjunto.

2. Estas operaciones son conmutativas: a + b = b + a y ab = ba

3. Ambas son distributivas una con respecto a la otra:

· distributiva respecto a +: a(b + c) = ab + ac
+ distributiva respecto a · : a + bc = (a + b)(a + c)

(Esta última propiedad no la verifican los números reales)

4. Existen elementos neutros para ambas operaciones, 0 para + y 1 para ·: a + 0 = a

y a · 1 = a

5. Todo elemento del álgebra tiene su complementario. Se denota por a y ha de verificar

las dos condiciones siguientes: a + a = 1 y aa = 0.

17

18TEMA 2. REPRESENTACI ÓN Y TRATAMIENTO DE LOS SISTEMAS DIGITALES

El Álgebra de Boole más sencilla es aquella formada por los elementos {0,1} con las

operaciones AND y OR definidas en el primer tema.

Una propiedad importante de un Álgebra de Boole es el principio de Dualidad.
Este principio establece que las expresiones algebraicas deducidas a partir de un Álgebra
de Boole permanecen válidas si se intercambian los operadores (+ por ·) y los elementos
neutros (0 por 1).

Otras propiedades importantes de un Álgebra de Boole son las siguientes:

1. Asociativa: a + b + c = (a + b) + c = a + (b + c) y abc = (ab)c = a(bc)

2. Idempotencia: a + a = a y aa = a
3. Absorción del neutro: a + 1 = 1 y a · 0 = 0

4. Involución: (a) = a

5. Absorción: a + ab = a

6. a + ab = a + b

7. Leyes de De Morgan:

a + b = a b
a + b + ··· + n = a b··· n

ab = a + b
ab··· n = a + b + ··· + n

Todas estas propiedades pueden demostrarse directamente a partir de los postulados
del Álgreba de Boole. Como ejemplo vamos a verificar dos de ellas, quedando las demás
como ejercicios para los alumnos:

Propiedad 2: a + a = a

a + a = (a + a) · 1

Elemento neutro 1

= (a + a)(a + a) Complementario
= a + aa
= a + 0
= a

Distributiva
Complementario
Elemento neutro 0

Propiedad 6: a + ab = a + b

a + ab = (a + a)(a + b) Distributiva

= 1 · (a + b)
= a + b

Complementario
Elemento neutro 1

2.1. ÁLGEBRA DE BOOLE

19

Figura 2.1: Interpretación física de algunas propiedades del Álgebra de Boole.

a 1 = aa a = aa ( b + c ) = a b + a ca + b c = ( a + b ) ( a + c )a + a b = aa + 0 = aa + 1 = 1a 0 = 0a + a = aacbabacabcaabcaabaaaaaaaaaaaaa 20TEMA 2. REPRESENTACI ÓN Y TRATAMIENTO DE LOS SISTEMAS DIGITALES

Figura 2.2: Implementación de la función f del ejemplo

2.2. FUNCIONES DE BOOLE

Una función f de n variables sobre un Álgebra de Boole A es una aplicación


A × A × ··· × A −→ A



n

f :

Si A = {0, 1} son 2n las posibles combinaciones de entrada (xn−1,··· , x1, x0), donde

xi ∈ {0, 1}.

Una Función de Boole puede definirse mediante expresiones del Álgebra de Boole o

bien dando su Tabla de Verdad (tabla de valores).

Ejemplo: f (a, b, c) = a + abc

f (0, 0, 0) = 1 + 1 · 0 · 1 = 1
f (0, 0, 1) = 1 + 1 · 0 · 0 = 1
f (0, 1, 0) = 1 + 1 · 1 · 1 = 1
f (0, 1, 1) = 1 + 1 · 1 · 0 = 1
f (1, 0, 0) = 0 + 0 · 0 · 1 = 0
f (1, 0, 1) = 0 + 0 · 0 · 0 = 0
f (1, 1, 0) = 0 + 0 · 1 · 1 = 0
f (1, 1, 1) = 0 + 0 · 1 · 0 = 0

a
0
0
0
0
1
1
1
1

b
0
0
1
1
0
0
1
1

c
0
1
0
1
0
1
0
1

f
1
1
1
1
0
0
0
0

Dos funciones se dicen iguales si sus Tablas de Verdad son iguales. Por ejemplo, la
función anterior f es igual a la siguiente función f1(a, b, c) = a. A esta conclusión se
podría haber llegado simplificando f mediante las propiedades del Álgebra de Boole:

f (a, b, c) = a + abc = a(1 + bc) = a

fbac 2.3. EXPRESIONES CAN ÓNICAS DE UNA FUNCI ÓN DE BOOLE

21

Funciones de Boole son también las funciones AND y OR, que para tres variables

tienen la siguiente Tabla de Verdad:

a
0
0
0
0
1
1
1
1

b
0
0
1
1
0
0
1
1

c
0
1
0
1
0
1
0
1

abc a + b + c
0
0
0
0
0
0
0
1

0
1
1
1
1
1
1
1

En general la función AND de n variables es 1 cuando todas las variables toman el

valor 1. La función OR de n variables es 1 cuando alguna de las n variables es 1.

2.3. EXPRESIONES CAN ÓNICAS DE UNA FUN-

CI ÓN DE BOOLE

En primer lugar vamos a definir dos conceptos muy importantes:

Definición 2.2 Para funciones de n variables, llamamos minterm a un término produc-
to que contiene cada una de las n variables, o bien negadas o bien sin negar, sin repetirse
ninguna.

Ejemplo: Para funciones de tres variables serían minterms: abc, abc, abc. Y no serían

minterms: ab, aabc.

Los minterms se denotan de forma simplificada tomando un 1 por cada variable sin

negar. Los posibles minterms para funciones de 3 variables son los siguientes:

Minterm Variables Notación

abc
abc
abc
abc
abc
abc
abc
abc

000
001
010
011
100
101
110
111

0
1
2
3
4
5
6
7

22TEMA 2. REPRESENTACI ÓN Y TRATAMIENTO DE LOS SISTEMAS DIGITALES

Definición 2.3 Para funciones de n variables, llamamos maxterm a un término suma
que contiene cada una de las n variables, o bien negadas o bien sin negar, sin repetirse
ninguna.

Ejemplo: Para funciones de tres variables serían maxterms: a + b + c, a + b + c, a + b + c.

Y no serían maxterms: a + b, a + a + b + c.

Los maxterms se denotan de forma simplificada tomando un 0 por cada variable sin

negar. Los posibles maxterms para funciones de 3 variables son los siguientes:

Maxterm Variables Notación
a + b + c
a + b + c
a + b + c
a + b + c
a + b + c
a + b + c
a + b + c
a + b + c

111
110
101
100
011
010
001
000

7
6
5
4
3
2
1
0

Vamos a enunciar un teorema muy importante relacionado con los maxterms y min-

terms:

Teorema 2.1 (Teorema de expansión de Shannon) Cualquier función binaria pue-
de expresarse en forma de suma de minterms o en forma de producto de maxterms. Estas
expresiones, que son únicas, reciben el nombre de representaciones canónicas de la
función.

Demostración: Queremos expresar una función cualquiera f (xn,··· , x1) en forma de

suma de minterms. Podemos poner la función de la siguiente forma:
f (xn,··· , x1) = x1f (xn,··· , 0) + x1f (xn,··· , 1)

Esta expresión se verifica para los dos valores posibles de x1. Si x1 = 0 quedará:

f (xn,··· , x1) = 1 · f (xn,··· , 0) + 0 · f (xn,··· , 1),

y si x1 = 1 tendremos:

f (xn,··· , x1) = 0 · f (xn,··· , 0) + 1 · f (xn,··· , 1).

Repitiendo el proceso para x2:

f (xn,··· , x2, x1) = x2 x1f (xn,··· , 0, 0) + x2x1f (xn,··· , 0, 1)
+ x2x1f (xn,··· , 1, 0) + x2x1f (xn,··· , 1, 1)

2.3. EXPRESIONES CAN ÓNICAS DE UNA FUNCI ÓN DE BOOLE

23

Y repitiendo el proceso para las n variables:

f (xn,··· , x2, x1) = xn ··· x2 x1f (0,··· , 0, 0) + xn ··· x2x1f (0,··· , 0, 1)
+ xn ··· x2x1f (0,··· , 1, 0) + xn ··· x2x1f (0,··· , 1, 1)
+ ··· + xn ··· x2 x1f (1,··· , 0, 0) + xn ··· x2x1f (1,··· , 0, 1)
+ xn ··· x2x1f (1,··· , 1, 0) + xn ··· x2x1f (1,··· , 1, 1)

Por tanto, en la expresión de la función van a aparecer aquellos minterms que repre-
sentan combinaciones de entradas para las cuales la función vale 1, los demás desaparecen.

De forma similar se haría la demostración para expresar una función en forma de
producto de maxterms. En este caso van aparecer aquellos maxterms que representan
combinaciones de entrada para los cuales la función vale 0, los demás maxterms desapa-
recen.

Conclusión: El Teorema de expansión de Shannon demuestra que existe una relación
sencilla entre la Tabla de Verdad de una función de Boole y su representación canónica:
la función presentará un minterm para las combinaciones de entradas en las cuales la
función vale 1 y presentará un maxterm para las combinaciones de entradas en las cuales
la función es 0.

Ejemplo: vamos a expresar en forma de suma de minterms y en forma de producto de

maxterms la siguiente función f :

a
0
0
0
0
1
1
1
1

b
0
0
1
1
0
0
1
1

c
0
1
0
1
0
1
0
1

0
1
2
3
4
5
6
7

f Minterm Maxterm
a + b + c
0
0
a + b + c
1
0
0
1
0
1

a + b + c
a + b + c

a + b + c

abc

abc

abc

Donde hemos añadido a la Tabla de Verdad de la función los minterms que correspon-
den a las combinaciones de entradas para las cuales la función vale 1 y los maxterms que
corresponden a las combinaciones de entradas para las cuales la función vale 0. Así tene-
mos las siguientes representaciones canónicas (en la notación simplificada vamos a indicar
los minterms con una “m” y los maxterms con “M ”):



f (a, b, c) =

f (a, b, c) =

m(2, 5, 7) = abc + abc + abc

M (0, 1, 3, 4, 6) = (a + b + c)(a + b + c)(a + b + c)(a + b + c)(a + b + c)

Este desarrollo se generaliza sin dificultad para funciones de cualquier número de

variables.

24TEMA 2. REPRESENTACI ÓN Y TRATAMIENTO DE LOS SISTEMAS DIGITALES

Definición 2.4 Aquellas combinaciones de entradas para las cuales no nos interesa el
valor que pueda tomar la salida se llaman indiferencias y se dice que las funciones que
incluyen indiferencias están incompletamente especificadas.

Esto ocurre en algunas ocasiones cuando el circuito que se diseña forma parte de un
sistema mayor en el que ciertas entradas se producen sólo en circunstancias tales que la
salida del circuito no influirá en el sistema general. Siempre que la salida no tenga ningún
efecto, es evidente que no importa si la salida es un 0 ó un 1. Otra posibilidad es que
ciertas combinaciones de entrada no ocurran jamás debido a varias resctricciones externas.
El circuito responderá de alguna forma a cualquier entrada, pero como esas entradas no
se producirán nunca no importa si el circuito final responde con una salida de 0 ó 1.

Las indiferencias se indican en la tabla de verdad anotando un “−” como valor fun-
cional, en vez de un 0 ó un 1. No es