UNIVERSIDAD DE SAN BUENAVENTURA - CALI

PROGRAMA DE INGENIERIA DE SISTEMAS

MATEMÁTICAS DISCRETAS
GUÍA DE TRABAJO No 1
TEMA: ÁLGEBRAS BOOLEANAS Y CIRCUITOS LÓGICOS
Profesor: Walter G. Magaña S.

CAPITULO 1
ALGEBRAS BOOLEANAS Y
CIRCUITOS LÓGICOS

Objetivos:

1. Aplicar adecuadamente las propiedades del Álgebra Booleana en la

estructuración y simplificación de circuitos lógicos.

2. Usar correctamente las compuertas lógicas en el diseño y elaboración

de circuitos lógicos.

Las Algebras de Boole corresponden al área del conocimiento matemático

sobre las cuales se sustentó el diseño y construcción de circuitos lógicos y
digitales, que se constituyeron en el avance tecnológico revolucionario tanto
para la ingeniería electrónica como para la ingeniería de sistemas o informática.
En esta sección se inicia con los axiomas del Algebra de Boole, su aplicación a

Walter G. Magaña S. 1
los circuitos de conmutación para finalizar con las compuertas lógicas,
diseñando circuitos con ellas mediante el uso de las álgebras de Boole.

Walter G. Magaña S. 2
5.1. AXIOMAS DEL ALGEBRA DE BOOLE

Sea B un conjunto en el cual se han definido dos operaciones binarias, + y *

(En algunos casos se definen en términos de  y  respectivamente), y una
operación unaria, denotada '. Entonces a la terna B, +, * se le denomina
Algebra Booleana si se cumplen los siguientes axiomas o leyes:

B1) Leyes Conmutativas. Las dos operaciones son conmutativas:

Para todos los elementos x, y  B, se cumple que:
1A) x + y = y + x 1B) x * y = y * x

B2) Leyes Distributivas. Cada operación es distributiva con respecto a la otra:

Para todos los elementos x, y, z  B, se cumple que:
2A) x + (y * z) = (x + y) * (x + z) 2B) x * (y + z) = (x * y) + (x * z)

B3) Leyes Modulativas. Cada operación binaria es modulativa y los módulos son
diferentes:
Para todo x  B, existen dos elementos diferentes 0 y 1 en B tales que:
3A) x + 0 = 0 + x = x 3B) x * 1 = 1 * x = x

B4) Leyes de Complemento.

Para todo elemento x  B existe un elemento x'  B tal que:
4A) x + x' = 1 4B) x * x' = 0

5.1.1. Ejemplos de estructuras booleanas

Ejemplo 1. La siguiente es una de las Álgebras Booleanas con aplicación directa

a los circuitos de distribución. Para futuras referencias se denominará Álgebra
Binaria de Boole.
Sea el conjunto B = {0, 1} en el cual se definen las operaciones + y * de acuerdo
a las siguientes tablas:

+ 0 1 * 0 1
0 0 1 0 0 0
1 1 1 1 0 1

Supongamos que los complementos se definen por 1' ≡ 0 y 0' ≡ 1.

(Observe la relación de estas tablas con la disyunción () y la conjunción ()
respectivamente, y la relación de los complementos con la negación de una
proposición)
Demostrar que B, +, *, ' es un álgebra booleana, mostrando que se satisfacen los
axiomas B1 a B4.

Solución:

Walter G. Magaña S. 3
B1) Las leyes conmutativas de las operaciones + y * se evidencian en la
simetría de la matriz de resultados en ambas tablas.

B2) Establecer la distributividad de cada una de las operaciones con respecto a la

otra exige calcular el resultado de ocho combinaciones posibles en cada caso.
Para 2A) x + (y * z) = (x + y) * (x + z):

A B
x y z y*z x + (y * z) x+y x+z (x + y) * (x + z)
1 1 1 1 1 1 1 1
1 1 0 0 1 1 1 1
1 0 1 0 1 1 1 1
1 0 0 0 1 1 1 1
0 1 1 1 1 1 1 1
0 1 0 0 0 1 0 0
0 0 1 0 0 0 1 0
0 0 0 0 0 0 0 0

Observe que las columnas A y B son iguales

Para la forma 2B) x * (y + z) = (x * y) + (x * z)

A B
x y z y+z x * (y + z) x*y x*z (x * y) + (x * z)
1 1 1 1 1 1 1 1
1 1 0 1 1 1 0 1
1 0 1 1 1 0 1 1
1 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0

Observe que las columnas A y B son iguales

B3) En la tabla de la operación + es fácil observar que 0 es el módulo de esta

operación y en la tabla de * análogamente se puede ver que 1 es el módulo; en
efecto:
0 + 0 = 0; 1+0=1 y 0 * 1 = 0; 1 * 1 = 1.

B4) Se han definido 1' = 0 y 0' = 1, de esta manera se puede observar que para
cada elemento de B existe un complemento tal que:

0 + 0' = 0 + 1 = 1 y 1 + 1' = 1 + 0 = 1

Walter G. Magaña S. 4
 0 * 0' = 0 * 1 = 0 y 1 * 1' = 1 * 0 = 0

De esta manera se ha demostrado que B, +, *, ' es una Algebra Booleana.

Ejemplo 2. Sea la familia P(U) de conjuntos de U, demostrar que P(U), , , '

es un Álgebra de Boole para cada conjunto U.
Sugerencia: B  P(U), +  , *  , 0   y 1  U

Solución: A continuación se verifican los cuatro axiomas de las álgebras

booleanas:

B1) Las dos operaciones unión () e intersección () son conmutativas para todo
A, B  P(U):
1A) A  B = B  A 1B) A  B = B  A

B2) La unión es distributiva con respecto a la intersección para todos los

conjuntos A, B, C  P(U), y recíprocamente:
2A) A  (B  C) = (A  B)  (A  C) 2B) A  (B  C) = (A  B)  (A  C)

B3) Para todo A  P(U) existen   P(U) y U  P(U) tal que

3A) A   = A 3A) A  U = A

B4) Para cada A  P(U), existe el complemento de A, esto es A' = U – A, con A'
 P(U), tal que satisface las siguientes relaciones:
4A) A  A' = U 4B) A  A' = 

Así queda demostrado que P(U), , , ' es un Álgebra de Boole.

Ejemplo 3. Sean D15 = {1, 3, 5, 15}, los divisores enteros positivos de 15. Se
definen +, * y ' de la siguiente manera:
x + y  MCM (x, y): mínimo común múltiplo de x y y;
x * y  MCD (x, y): máximo común divisor de x y y, y
x'  15/x.
Demuestre que esta estructura así definida  D15, +, *, ' es un Álgebra Booleana.

Solución: Verifiquemos los axiomas del álgebra booleana:

B1) La conmutatividad de las operaciones se evidencia, pues x + y = y + x,
equivale a MCM (x, y) = MCM (y, x) y x * y = y * x, significa que MCD (x, y) =
MCD (y, x). Es decir, no importa el orden al obtener los resultados de un par de
elementos del conjunto D15 para el MCM y el MCD. Esto se muestra en la
simetría de la matriz de resultados en cada una de las siguientes tablas:

+ 1 3 5 15 * 1 3 5 15

Walter G. Magaña S. 5
 1 1 3 5 15 1 1 1 1 1
3 3 3 15 15 3 1 3 1 3
5 5 15 5 15 5 1 1 5 5
15 15 15 15 15 15 1 3 5 15

B2) Examinemos la distributividad de una operación respecto a la otra:

2A) Para la forma x + (y * z) = (x + y) * (x + z) es equivalente a tener
MCM [x, (y * z)] = MCD [(x + y), (x + z)]
MCM [x, MCD (y, z)] = MCD [MCM (x, y), MCM (x, z)]
veamos algunos ejemplos que se condensan en la siguiente tabla:

A B
y*z x + (y * z) x+y x+z (x + y) * (x + z)
x y z MCD (y, z) MCM [x, MCD (y, MCM (x, y) MCM (x, MCD [MCM (x, y), MCM (x, z)]
z)] z)
1 3 5 1 1 3 5 1
3 5 15 5 15 15 15 15
5 15 3 3 15 15 15 15
15 1 3 1 15 15 15 15

Observe que las columnas A y B son iguales

2B) Para la forma x * (y + z) = (x * y) + (x * z) es equivalente a tener

MCD [x, (y + z)] = MCM [(x * y), (x * z)]
MCD [x, MCM(y, z)] = MCM [MCD (x, y), MCD (x, z)]
veamos algunos casos en la siguiente tabla:

A B
y+z x * (y + z) x*y x*z (x * y) + (x * z)
x y z MCM (y, z) MCD [x, MCM (y, z)] MCD (x, MCD (x, MCM [MCD (x, y), MCD (x, z)]
y) z)
1 3 5 15 1 1 1 1
3 5 3 15 3 1 3 3
5 5 1 5 5 5 1 5
15 1 3 3 3 1 3 3
Observe que las columnas A y B son iguales
Por lo tanto, cada operación es distributiva con respecto a la otra.

B3) Sean 0  1, 1  D15 es el módulo de +, y 1  15, 15  D15 es el módulo de *.

3A) Así x + 0 = 0 + x = x; esto es, para todo x  D15,
MCM (x, 1) = MCM (1, x) = x.
3B) x * 1 = 1 * x = x, es decir, para todo x  D15,
MCD (x, 15) = MCD (15, x) = x.
Por lo tanto, las dos operaciones son modulativas.

Walter G. Magaña S. 6
B4) Para cada x  D15 existe x'  D15 tal que x + x' = 1 y x * x' = 0. Esto es:
4A) Para x + x'  MCM (x, x') = MCM (x, 15/x) = 15;
veamos un caso, 5 + 5'  MCM (5, 5') = MCM (5, 3) = 15.
4B) Para x * x'  MCD (x, x') = MCD (x, 15/x) = 1,
un caso es 3 * 3'  MCD (3, 3') = MCD (3, 15/3) = MCD (3, 5) = 1.

Esto demuestra que D15 con las operaciones MCM y MCD es un Algebra
Booleana.

5.2. RESULTADOS QUE SE DERIVAN DE LOS AXIOMAS DE LAS ALGEBRAS

DE BOOLE

5.2.1. EXPRESIONES BOOLEANAS.

Definición. Sea B = {x1, x2, . . . xn} un conjunto de n símbolos o variables.

Una expresión booleana E(x1, x2, . . . xn) o un polinomio booleano en x1, x2,
. . . xn se define recursivamente como sigue:
1. Los símbolos o variables x1, x2, . . . xn son expresiones booleanas.
2. Los símbolos 0 y 1 son expresiones booleanas.
3. Si E1(x1, x2, . . . xn) y E2(x1, x2, . . . xn) son expresiones booleanas en x1,
x2, . . . xn entonces también los son E 1(x1, x2, . . . xn) + E2(x1, x2, . . . xn),
E1(x1, x2, . . . xn) * E2(x1, x2, . . . xn), y [E1(x1, x2, . . . xn)]'.

Observación: De acuerdo al uso en el álgebra clásica, se abrevia x * y como xy.

Igualmente se asume que * se evalúa antes que +; esto permite en algunos casos
eliminar ciertos paréntesis. Por ejemplo, se puede escribir xy + z en lugar de (x
* y) + z.

B5) TEOREMA 1. Leyes de Idempotencia. Todo elemento de un Álgebra

Booleana es idempotente. Para todo elemento x  B; se cumple que:
5A) x + x = x y 5B) x * x = x.

Demostración:

Demostración de 5A:
x + x = (x + x) * 1 B3 (Ley modulativa)
= (x + x) * (x + x') B4 (Ley de complemento)
= x + (x * x') B2 (Ley distributiva)
=x+0 B4 (Ley de complemento)
=x B3 (Ley modulativa)

Walter G. Magaña S. 7
Demostración de 5B:
x * x = (x * x) + 0 B3 (Ley modulativa)
= (x * x) + (x * x') B4 (Ley de complemento)
= x * (x + x') B2 (Ley distributiva)
=x*1 B4 (Ley de complemento)
=x B3 (Ley modulativa)

DEFINICION DE DUAL. El dual de una expresión E de un Álgebra Booleana, es

la expresión que resulta a partir de E intercambiando + por * y 0 por 1 y
recíprocamente, en cada operación de estos símbolos.

Ejemplo ilustrativo:
1. Sea la expresión E1 = x + y * (z + 1),
el dual es la expresión E1d = x * (y + z* 0).
2. Dada la ecuación E2 = x + xz' = x,
su dual es la ecuación E2d = x * (x + z') = x

PRINCIPIO DE LA DUALIDAD. Si el teorema T es deducible de los axiomas de un

Algebra de Boole, entonces el dual de T, que se denota por T d, es también
deducible y para deducirlo basta cambiar cada expresión surgida en la
demostración de T, por su dual.

Observe la demostración del Teorema 1, realizada anteriormente, la demostración

de 5B se obtiene a partir de 5A, realizando los cambios respectivos previstos +
por * y 1 por 0, y recíprocamente. 5B es el Td de 5A.

B6) TEOREMA 2. Leyes de acotamiento. Para todo x  B, se verifica que:

6A) x + 1 = 1 y 6B) x * 0 = 0.

Demostración:
Demostración de 6A:
x + 1 = 1 * (x + 1) B3 (Ley modulativa)
= (x + x') * (x + 1) B4 (Ley de complemento)
= x + (x' * 1) B2 (Ley distributiva)
= x + x' B3 (Ley modulativa)
=1 B4 (Ley de complemento)

La demostración de 6B x * 0 = 0 se omite, ya que por el principio de la dualidad

se puede deducir de manera análoga tomando el dual en cada paso de la
demostración de 6A (el lector puede demostrarlo).

B7) TEOREMA 3. Leyes de absorción. Para todo x, y  B, se verifica que:

7A) x + (x * y) = x y 7B) x * (x + y) = x.

Walter G. Magaña S. 8
Demostración:
Demostración de 7A:
x + (x * y) = x * 1 + (x * y) B3 (Ley modulativa)
= x * (1 + y) B2 (Ley distributiva)
= x * (y + 1) B1 (Ley conmutativa)
=x*1 B6 (Teorema 2: Ley de acotamiento)
=x B3 (Ley modulativa)

La parte 7B se da por demostrada por el principio del dualismo (el lector puede
demostrarlo)

B8) TEOREMA 4. Unicidad del complemento. Para cada x  B, siendo B un

Algebra de Boole, el complemento de x, denotado por x', es único.

Demostración: La demostración se hará por contradicción.

Supongamos que x  B tiene dos complementos diferentes y y z, es decir, con y
 z, entonces satisfacen las condiciones del axioma B4: por 4A) x + y = 1 (2) y x
+ z = 1 (3), y por 4B) x * y = 0 (4) y x * z = 0 (1)

y=y+0 B3
y = y + (x * z) Sustitución de (1) en 0
y = (y + x) * (y + z) B2
= (x + y) * (y + z) B1
= 1 * (y + z) Sustitución de (2)
= (x + z) * (y + z) Sustitución de (3)
= (x * y) + z B2
=0+z Sustitución de (4)
=z B3
Entoncesy = z. Lo cual es una contradicción (contradice la condición de la
hipótesis y  z).

B9) TEOREMA 5. Leyes de D’Morgan. Para todo x, y  B, se verifica que:

8A) (x + y)' = x' * y' y 8B) (x * y)' = x' + y'.

Demostración:
Demostración de 8A): Mostraremos que x' * y' satisface las condiciones que
caracterizan el complemento de (x + y), que es único.
1º) (x + y) + (x' * y') = (x + y + x') * (x + y + y') B2
= (x + x' + y) * (x + y + y') B1
= (1 + y) * (x + 1) B4
=1*1 B6: Teorema 2
=1 B3

Walter G. Magaña S. 9
2º) (x + y) * (x' * y') = x * (x' * y') + y * (x' * y') B2
= (x * x') y' + (y * y') x' B1 y Propiedad asociativa
= 0 * y' + 0 * x' B4
=0+0 B6: Teorema 2
=0 B3
En conclusión (x + y)' = x' * y'.
Por el principio del dualismo 8B se da por demostrado (el lector puede
comprobarlo).

B10) TEOREMA 6. Leyes asociativas. Para todo x, y, z  B, se verifica que:

9A) (x + y) + z = x + (y + z) y 9B) (x * y) * z = x * (y * z)

Demostración:
Demostraremos 9B): Sea L = (x * y) * z y R = x * (y * z); entonces tenemos que
demostrar que L = R. Primero demostraremos que x + L = x + R.
x + L = x + [(x * y) * z]
= [x + (x * y)] * (x + z)
= x * (x + x)
=x
x + R = x + [x * (y * z)]
= ( x + x) * (x + (y * z)]
= x * [x + (y * z)
=x
Así, x + L = x + R.

Ahora demostremos que x' + L = x' + R.

x' + L = x' + [(x * y) * z]
= [x' + (x * y) * (x' + z)
= [(x' + x) * (x' + y') * (x' + z)]
=[1 * (x' + y) * (x' + z)
=(x' + y) * (x' + z)
= x' + (y * z)
x' + R = x' + [x * (y * z)]
= (x' + x) * [x' + (y * z)]
= 1 * [x' + (y * z)]
= x' + (y * z)

De donde x' + L = x' + R. En consecuencia,

L = L + 0 = L + (x * x')
= (L + x) * (L + x')
= (x + L) * (x' + L)
= (x + R) * (x' + R)
= (R + x) * (R + x')
= R + (x * x') = R + 0 = R

Walter G. Magaña S. 10
Por el principio de dualismo 9A se da por demostrado.

B11) TEOREMA 7. Ley de involución. Para cada x  B, (x')' = x.

B12) TEOREMA 8. Leyes para el 0 y el 1. 0' = 1 y 1' = 0.

EJERCICIOS 5.1

1. Demuestre que B, +, *, ' es un Álgebra Booleana, donde B = {1, 2, 3, 5, 6,

10, 15, 30} es el conjunto de divisores enteros positivos de 30, en el que se
definen las operaciones x + y  MCM(x, y), x y  MCD(x, y) y x'  30/x.

2. Sea B = {1, 2, 4, 8} el conjunto de divisores enteros positivos de 8, en el cual

se definen las operaciones + y * como en el ejercicio 1 y x'  8/x.
Demuestre que B, +, *, ' no es un Álgebra Booleana.

3. Escriba el dual de cada una de las siguientes expresiones:

3.1. (x + y)(x + 1) = x + xy + y.
3.2. (x' + y')' = xy.
3.3. Si x + y = x + z y x' + y = x' + z, entonces y = z.
3.4. xy' = 0 si y sólo si xy = x.
3.5. x + x(y + 1) = x.
3.6. Si x + y = 0, entonces x = 0 o y = 0.
3.7. a (a' + b) = ab.
3.8. (x + 1) (x + 0) = x.
3.9. (x + y) (y + z) = xz + y.
3.10. b {a + [a' (b + b')]} = b.

4. Verifique cada uno de los enunciados del ejercicio 3.

5. Verifique las siguientes ecuaciones:

5.1. xy' = (x' + y)' 5.2. x (yz)' = xy' + xz'.
5.3. (x + y) (z + w) = zx + zy + wx + wy.

6. Pruebe o dé un contraejemplo, si las ecuaciones siguientes son o no

verdaderas:
6.1. x'y' = x + y 6.2. x' (yz + xyz) = yz.
6.3. (x'y + xz')' = (x + y') (x + z') 6.4. (x + y) (z' + w)' (zy') = 0.

Walter G. Magaña S. 11
5.3. CIRCUITOS LOGICOS

5.3.1. FUNCIONES DEL ÁLGEBRA BOOLEANA BINARIA

Sea B = {0, 1} y sea Bn = {(x1, x2, . . . xn) / xi  B para i = 1, 2, . . . , n}, entonces
se definen funciones f de Bn en B, que se denotan f : Bn  B, como funciones
en las que para cualquier n-upla (x1, x2, . . . xn)  Bn, f(x1, x2, . . . xn) es 1 o 0.
Estas funciones se pueden considerar como funciones de n “variables”, donde
cada una de ellas toma sólo los valores 1 o 0. Es frecuente enlistarlas en tablas
dando cada n-upla posible (x1, x2, . . . xn) y el valor correspondiente de la
función f.

Ejemplo ilustrativo: La tabla que se muestra a continuación representa una

función f particular de tres variables; esto es, f : B3  B

x1 x2 x3 f(x1, x2, x3)

1 1 1 1
1 1 0 0
1 0 1 0
1 0 0 0
0 1 1 1
0 1 0 1
0 0 1 1
0 0 0 1

El número de combinaciones posibles de ceros y unos de las n-upla (x1, x2, . . .

xn) es de 2n, donde n es el número de variables diferentes. A menudo estas
tablas se denominan tablas de verdad de f, debido a la analogía con la lógica
proposicional.

Entrada
s Salid
x1 a

x2 f(x1, x2, . . . xn)

f
.
.
.

xn

La importancia de estas funciones es que pueden usarse para representar los

requerimientos de salida de un circuito para todos los posibles valores de las
entradas. Por lo tanto, cada xi representa una entrada al circuito capaz de
transportar dos voltajes indicadores (un voltaje para el 0 y otro diferente para el

Walter G. Magaña S. 12
1). La función f representa la respuesta de salida en todos los casos. Tales
requerimientos se presentan al diseñar los pasos de todas las combinaciones y
secuencias de los circuitos para los computadores. Cabe anotar que la
especificación de una función f : B  B es sólo una lista de los requerimientos
n

del circuito. Esto no nos da indicación alguna de cómo estos requerimientos se

satisfacen.

5.3.2. CIRCUITOS DE CONMUTACION (O DE CONMUTADORES)

Un circuito eléctrico de interruptores normalmente contiene alguna fuente de
energía (una pila o batería), un dispositivo de salida (por ejemplo una bombillo), y
uno o más interruptores o “switches”, todos ellos conectados por alambres. Sólo
se considerarán los interruptores que permiten o impiden el paso de la corriente
eléctrica que fluye por el circuito, y cuyo funcionamiento es de dos estados
cerrado (encendido), on, y abierto (apagado), off.

Cuando un interruptor x está en la posición cerrado (on) permite el paso de la

corriente, se escribe x = 1, y cuando está en la posición abierto (off), no hay paso
de corriente, se escribe x = 0.

INTERRUPTOR CERRADO (ON) INTERRUPTOR ABIERTO (OFF)

x=1 x=0

Existen dos formas básicas para interconectar interruptores: conexión en serie y

conexión en paralelo.

5.3.3. CIRCUITO EN SERIE (CIRCUITO AND).

Se caracteriza porque hay paso de corriente a z si, y solo si, los dos interruptores
x e y se encuentran cerrados. Es decir, la salida del circuito es 1 si, y solo si x
= 1 y y = 1. Esta configuración se denota por z = xy. La tabla de conmutación
que presenta las salidas del circuito en serie (AND) es:

x y z=xy
1 1 1
1 0 0
0 1 0
0 0 0

Puesto que estamos interesados solamente en la posición de los interruptores,

entonces usaremos la representación simplificada del circuito:

Walter G. Magaña S. 13
 x y

x y
z
Circuito simplificado

+ –

Circuito en serie

5.3.4. CIRCUITO EN PARALELO (CIRCUITO OR).

Se caracteriza porque hay paso de corriente a z si, y solo si uno de los
interruptores del circuito, x o bien y, o ambos está(n) cerrado(s). Es decir, la
salida del circuito es 1 si, y solo si x = 1 o y = 1, o ambos x = y = 1. Esta
configuración se denota por z = x + y. La tabla de conmutación del circuito en
paralelo es:

x y z=x+y
1 1 1
1 0 1
0 1 1
0 0 0

Al igual que en el circuito en serie, usaremos la representación simplificada del

circuito:
x
x

z
y

+ – Circuito simplificado

Circuito en paralelo

Si en un circuito hay varios interruptores que coinciden en su estado (1 o 0) los

designaremos con la misma variable. El símbolo x' (o x) representa un
interruptor que presenta el estado opuesto al que presenta un interruptor
denotado por x, se denomina el inversor de x. En un circuito junto con

Walter G. Magaña S. 14
cualquier interruptor x podemos incluir cualquier interruptor x' que está abierto
cuando x está cerrado, y está cerrado cuando x está abierto:

x x'
1 0
0 1

Ejemplo 1: Determine una expresión de Boole para el siguiente circuito de

interruptores y elabore su correspondiente tabla conmutadora

x y

x'

y z

Solución: Se procede por niveles de arriba a abajo: 1) xy, 2) x', 3) yz.

Al final obtenemos la expresión: xy + x' + yz que corresponde a la expresión de
Boole del circuito, donde los niveles son de un circuito en paralelo.

La tabla conmutadora correspondiente es:

x y z xy x' yz xy + x' + yz
1 1 1 1 0 1 1
1 1 0 1 0 0 1
1 0 1 0 0 0 0
1 0 0 0 0 0 0
0 1 1 0 1 1 1
0 1 0 0 1 0 1
0 0 1 0 1 0 1
0 0 0 0 1 0 1

Ejemplo 2: Determine una expresión booleana para el circuito de la figura y halle

un circuito equivalente “más sencillo”.

Solución: Procediendo por niveles de arriba hacia abajo obtenemos la expresión

x'y + (x' + xy) z + x (y + y'z + z).

Walter G. Magaña S. 15
 x' y

x'
z

x y y

x y' z

Simplificando la expresión por las leyes del álgebra de Boole se obtiene la

expresión y + z (verifíquelo). El circuito que se obtiene realiza las mismas
funciones que el anterior:
x

Ejercicio en clase: Represente la función f(a, b, c, d) = a [(b + d') + c (a + d + c')]b

como un circuito conmutador y elabore la correspondiente tabla conmutadora.

EJERCICIOS 5.2

1. Exprese cada circuito en forma simbólica y construya su correspondiente tabla conmutadora:

1.1. 1.2.
y y

x
x z
z
x'

w
1.3.

Walter G. Magaña S. 16
 z

x
y'

y z'

2. Represente las expresiones de los siguientes ejercicios como circuitos

conmutadores y escriba las correspondientes tablas conmutadoras:
2.1. (x + y) x 2.2. x + (y' z)
2.3. (a' b) + (c a) 2.4. {a [(b c') + (b' c)]} + (a' b c)

Walter G. Magaña S. 17
5.4. COMPUERTAS LOGICAS
En los sistemas digitales se utilizan, empaquetados como circuitos integrados,
ciertos circuitos electrónicos llamados compuertas lógicas, denominados también
dispositivos de estado sólido. En ellos no hay interruptores sino entradas al
circuito, en forma de alto voltaje (1) y de bajo voltaje (0), esto es exactamente un
bit de información, estos datos son procesados por el circuito para obtener una
salida que depende de la combinación de las entradas, es decir un bit de salida,
o sea, un 0 ó un 1.

Los circuitos lógicos se construyen a partir de ciertas compuertas lógicas básicas,

se comenzará estudiando tres tipos de compuertas: compuerta AND, compuerta
OR y compuerta NOT (o inversor).

5.4.1. COMPUERTA AND.

Una compuerta AND acepta x y y como datos de entrada, en donde x y y son
bits, y produce un dato de salida z, que se denota z = xy. El valor de z está
determinado por la tabla de valor que aparece a continuación. Es decir, z = xy = 1
si, y solo si x = 1 y y = 1, 0 en otro caso.

Entrada Salida
x y z = xy
1 1 1
1 0 0
0 1 0
0 0 0

Una compuerta AND se representa con la figura siguiente:

x
xy
y

5.4.2. COMPUERTA OR.

Una compuerta OR acepta x y y como datos de entrada, en donde x y y son bits,
y produce un dato de salida z, que se denota z = x + y. El valor de verdad de z
está determinado por la tabla de valor que aparece a continuación; en donde z = x
+ y = 1 si, y solo si x = 1 o bien y = 1, 0 solo si x = 0 y y = 0.

Entrada Salida
x y z=x+y
1 1 1
1 0 1
0 1 1
0 0 0

Walter G. Magaña S. 18
Una compuerta OR se representa como se muestra en la figura:
x x+y
y

5.4.3. COMPUERTA NOT.

Una compuerta NOT (o inversor) acepta a x como dato de entrada (tiene
solamente una entrada), en donde x es un bit, y produce un dato de salida que
se denota por x' (o x). El valor de salida x' es el opuesto (complemento a unos)
del valor de entrada x; esto es, x' = 1 sí x = 0 y x' = 0 sí x = 1.

La tabla de verdad de la compuerta NOT es la siguiente:

Entrada Salida
x x'
1 0
0 1

Una compuerta NOT se representa como aparece en la figura siguiente:

x x
'
Ejemplo 1. Determine la expresión booleana correspondiente al circuito lógico
de la figura y encuentre la tabla lógica de este circuito:
x (1)
y
(2) (3) w

Solución:
Se han enumerado las salidas de cada compuerta para indicar el seguimiento:
1) Se aplica AND a x y y y se obtiene xy.
2) Luego al aplicar OR a (xy) y z se obtiene (xy) + z.
3) Entonces el dato de salida se escribe como [(xy) + z]'.
La tabla de verdad es la siguiente:
Entradas Salida
x y z xy (xy) + z [(xy) + z]'
1 1 1 1 1 0
1 1 0 1 1 0
1 0 1 0 1 0
1 0 0 0 0 1
0 1 1 0 1 0
0 1 0 0 0 1
0 0 1 0 1 0
0 0 0 0 0 1

Walter G. Magaña S. 19
Ejercicio en clase. Determine la expresión booleana correspondiente al circuito
lógico de la figura: (Sugerencia: proceda por niveles de acuerdo a la numeración
de las salidas en cada compuerta)

x 1
4

y 8
2
5
6 7

3
z

5.4.4. OTRAS COMPUERTAS LOGICAS

Las tres compuertas fundamentales anteriormente presentadas (AND, OR y NOT)
son suficientes para describir cualquier ecuación booleana. Toda función lógica
puede expresarse con la combinación de estas tres compuertas. Sin embargo, se
utilizan otras cuatro compuertas lógicas como simplificación de combinaciones
muy usuales de las fundamentales: NAND, NOR, XOR y XNOR.

COMPUERTA NAND.
La compuerta NAND (NOT AND), denominada también operación de Sheffer, se
obtiene cuando a la salida de una compuerta AND se conecta un inversor (NOT);
es decir, es la negación de una compuerta AND y acepta x y y como datos de
entrada, en donde x y y son bits, y produce un dato de salida z, que se denota
como z = (xy)'.
La tabla de verdad de la compuerta NAND es la siguiente:

Salida
Entrada
AND NAND
x y xy z = (xy)'
1 1 1 0
1 0 0 1
0 1 0 1
0 0 0 1

Una compuerta NAND se representa con la figura siguiente:

x x x
(xy) (xy)
y y y
' '
Compuerta NAND Compuerta NAND simplificada

Walter G. Magaña S. 20
COMPUERTA NOR.
La compuerta NOR (NOT OR), denominada también operación de Pierce, se
consigue cuando a la salida de una compuerta OR se conecta un inversor (NOT);
es decir, es la negación de una compuerta OR y acepta x y y como datos de
entrada, en donde x y y son bits, y produce un dato de salida z, que se denota
como z = (x + y)'.
La tabla de verdad de la compuerta NOR es la siguiente:

Salida
Entrada
OR NOR
x y x+y z = (x + y)'
1 1 1 0
1 0 1 0
0 1 1 0
0 0 0 1

Una compuerta NOR se representa con la figura siguiente:

x x
(x + (x +
y y y)'
y)'
Compuerta NOR Compuerta NOR simplificada

COMPUERTA XOR (OR Exclusiva).

La compuerta XOR, corresponde a la operación lógica disyunción exclusiva. Por
lo tanto, la salida es 1 si, y sólo si, exactamente una de las entradas es 1.
Realiza la función lógica de salida de la forma z = xy' + x'y. Para denotar esta
disyunción exclusiva o suma exclusiva se emplea el símbolo ; y la función se
escribe simplificadamente como x  y, así: f(x, y) = x  y = xy' + x'y.

La tabla de verdad de la compuerta XOR es la siguiente:

Salida
Entrada
XOR
x y xy' x'y. z=xy
1 1 0 0 0
1 0 1 0 1
0 1 0 1 1
0 0 0 0 0

Una compuerta XOR se representa con la figura siguiente:

x
z
y

Walter G. Magaña S. 21
COMPUERTA XNOR.
La compuerta XNOR, se forma conectando a la salida de la compuerta XOR un
inversor. Por lo tanto, la función de salida es z = f(x, y) = (x  y)'.

La tabla de verdad de la compuerta XNOR es la siguiente:

Salida
Entrada
XOR XNOR
x y xy z = (x  y)'
1 1 0 1
1 0 1 0
0 1 1 0
0 0 0 1

Observe que la tabla de verdad de la compuerta XNOR es exactamente igual a la

tabla de verdad de la equivalencia (o bicondicional); por esta razón, esta
compuerta recibe el nombre de comparador.

Una compuerta XNOR se representa con la figura siguiente:

x x z = (x  y)´
z = (x  y)´
y y
Compuerta XNOR Compuerta XNOR simplificada

Si aplicamos las leyes del álgebra booleana a la expresión (x  y)' se obtiene el

siguiente resultado:
(x  y)' = (xy' + x'y)' Definición de la compuerta XOR
= (xy')' (x'y)' Leyes de D’ Morgan, B9
= (x' + y) (x + y') Leyes de D’ Morgan, B9
= (x' + y) x + (x' + y) y' Leyes Distributivas, B2
= xx' + xy + x'y' + yy' Leyes Distributivas, B2
= 0 + xy + x'y' + 0 Leyes de Complemento, B4
= xy + x'y' Leyes Modulativas, B3

Esta última expresión es la función booleana que establece la equivalencia entre

x y y, por lo tanto: (x  y)  (x  y)'.

Ejemplo 2. Diseñe un circuito lógico de tres entradas x, y y z cuya salida es 1

cuando, y sólo cuando, exactamente dos de las entradas tienen el valor 1.

Solución: Es conveniente diseñar una tabla con tres entradas y una salida f(x, y,
z) evaluando esta con 1 si, y sólo si, dos de las entradas tienen el valor 1, de
acuerdo al requerimiento del problema.

Walter G. Magaña S. 22
 Entradas Salida
x y z f(x, y, z)
1 1 1 0
1 1 0 1
1 0 1 1
1 0 0 0
0 1 1 1
0 1 0 0
0 0 1 0
0 0 0 0

La segunda fila de la tabla que tiene salida 1 origina la combinación xyz', observe
que si x = y = 1 y z = 0 origina la salida 1, de acuerdo a la condición del problema.
Así mismo es posible tomar la combinación xy'z para la tercera fila y x'yz para la
quinta fila. A continuación se hace la suma de los términos para obtener la
expresión booleana: f(x, y, z) = xyz' + xy'z + x'yz. Un posible diseño del circuito es el
siguiente:

Ejemplo 3. Construir un circuito lógico combinatorio, de acuerdo a la siguiente

tabla lógica, usando compuertas AND, OR y NOT.

Entradas Salida
x y z f(x, y, z)
1 1 1 1
1 1 0 1
1 0 1 0
1 0 0 1
0 1 1 0
0 1 0 0
0 0 1 0
0 0 0 0

Solución:
La forma suma de productos ( o forma normal disyuntiva) de f es:

Walter G. Magaña S. 23
 f(x, y, z) = xyz + xyz' + xy'z'.
El circuito lógico correspondiente aparece en la siguiente figura:
x

El circuito de la figura tiene seis compuertas; es posible diseñar un circuito

equivalente que desempeñe la misma función con menos compuertas. El
problema de encontrar el “mejor” circuito se llama problema de minimización.
Para determinar un circuito lógico más simple y equivalente al de la figura se
simplificará la expresión booleana que lo representa, como sigue:

xyz + xyz' + xy'z' = xy (z + z') + xy'z'

= xy (1) + xy'z'
= xy (1+z') + xy'z'
= xy + xyz' + xy'z'
= xy + xz' (y + y')
= xy + xz' (1)
= xy + xz'
= x (y + z')

El circuito lógico correspondiente a la expresión x (y + z'), solo requiere tres

compuertas, como se ilustra en la figura:
x

Ejercicio en clase: De acuerdo al circuito lógico dado a continuación:

x

Walter G. Magaña S. 24
 a) Escriba la expresión booleana que representa la salida del circuito.
b) Simplifique la expresión de Boole y diseñe el circuito combinatorio que
utilice el menor número de compuertas.

EJERCICIOS 5.3

1. En los siguientes ejercicios escriba las expresiones Booleanas que representan

los circuitos combinatorios y elabore la tabla lógica correspondiente:

1.1. 1.2.
x
x
y
E y
W

z z

1.3.

z
W

1.4.
x
W1

y W2

Walter G. Magaña S. 25
 1.5.
x

W
y

1.6.
x
y
E
z
w

2. Encuentre el circuito combinatorio correspondiente para cada una de las

expresiones Booleanas de los siguientes ejercicios y elabore la tabla lógica
correspondiente:
2.1. xy' + xyz' 2.2. (x + yz)' + y
2.3. (a'b)' + (a + c)' 2.4. x + x'z
2.5. x (y + xy') + (xy' + (xz')') 2.6. xy' + y (x' + y)

3. Determine la expresión de Boole en forma de suma de productos de cada uno

de los siguientes ejercicios y trace el circuito combinatorio correspondiente:
3.1.
Entradas Salida
x y f(x, y)
1 1 1
1 0 0
0 1 1
0 0 1

3.2.
Entradas Salida
x y f(x, y)
1 1 0
1 0 1
0 1 0
0 0 1

Walter G. Magaña S. 26
 3.3.
Entradas Salida
x y z f(x, y, z)
1 1 1 1
1 1 0 1
1 0 1 0
1 0 0 1
0 1 1 0
0 1 0 0
0 0 1 1
0 0 0 1

3.4.
Entradas Salida
x y z f(x, y, z)
1 1 1 1
1 1 0 0
1 0 1 0
1 0 0 1
0 1 1 0
0 1 0 0
0 0 1 0
0 0 0 1

4. Escriba cada expresión de Boole f(x, y, z) en forma suma de productos (o

forma normal disyuntiva), y luego en forma completa de suma de productos:
4.1. x (xy' + x'y + y'z) 4.2. (x + y) (x' + y')
4.3. (x' + y)' + y'z 4.4. x + y (x + z')
4.5. (yz + xz') (xy' + z)' 4.6. (x' y)' (x' + xyz')
4.7. x + [y' + (xy' + xz')] 4.8. (x + x'y + x'yz') (xy + (xz)') (y + xyz')

BIBLIOGRAFIA

 KOLMAN, Bernard, BUSBY, Robert C. y ROSS, Sharon. Estructuras de

matemáticas discretas para la computación. Tercera edición. Prentice
Hall Hispanoamericana, S.A. México,D. F., 1988.
 LIPSCHUTZ, Seymour. Matemáticas para computación. Editorial Mc.
Graw-Hill. México,D. F., 1985.
 ROSS, Kenneth A. y WRIGHT, Charles R.B. Matemáticas discretas.
Segunda Edición. Prentice Hall Hispanoamericana, S.A.
 JOHNSONBAUGH, Richard. Matemáticas discretas. Grupo Editorial
Iberoamérica. México,D. F., 1988.

Walter G. Magaña S. 27
 BUSTAMANTE, Alfonso. Elementos de Álgebra en Ciencias de la
Computación. Serie Textos Universitarios del ICESI. N6. Cali, Valle del
Cauca, Colombia, junio de 1988.
 GRIMALDI, Ralph P. Matemáticas discretas y combinatoria. Editorial
Educativa. Addison Wesley Iberoamericana.
 BARCO G., Carlos; BARCO G., Germán y ARISTIZABAL B., William.
Matemática Digital. Editorial Mc. Graw-Hill. Santa Fé de Bogotá,
Colombia, abril de 1998.

Walter G. Magaña S. 28