ALGEBRA DE BOOLE PROBLEMAS RESUELTOS PDF

Share Button

Álgebras booleanas y circuitos combinatorios , Propiedades de los circuitos combinatorios , Rincón de solución de problemas , Funciones booleanas y simplificación de circuitos, Aplicaciones , Autoevaluación del capítulo , Ejercicios para computadora

CLICK AQUI PARA OTRA OPCION DE DESCARGA – VISUALIZACION





CLASES AUDIOVISUALES CLICK AQUI
Varias definiciones honran al matemático del siglo XIX George Boole; álgebra booleana,
funciones booleanas, expresión booleana y anillo booleano, por nombrar unas cuantas.
Boole es una de las personas de una larga cadena histórica que se preocuparon por formalizar
y mecanizar el proceso del pensamiento lógico. De hecho, en 1854 Boole escribió un
libro titulado The Laws of Thought (Las leyes del pensamiento). La contribución de Boole
fue el desarrollo de una teoría de lógica que usa símbolos en lugar de palabras. Un análisis
del trabajo de Boole se encuentra en [Hailperin].
Casi un siglo después del trabajo de Boole, C. E. Shannon observó en 1938 (vea
[Shannon]) que el álgebra booleana se podía usar para analizar circuitos eléctricos. Fue así
como el álgebra booleana se convirtió en una herramienta indispensable para el análisis y
diseño de las computadoras electrónicas en las siguientes décadas. En este capítulo se exploran
las relaciones del álgebra booleana con los circuitos.
ÁLGEBRAS
BOOLEANAS Y
CIRCUITOS
COMBINATORIOS
Él es indigno, deshonesto, egoísta, engañoso, despreciable; pero
él está allá y yo estoy acá. Dicen que él es normal y yo no. Bueno,
si eso es normal, no lo quiero.
DE MILAGRO EN LA CALLE 34
Circuitos combinatorios
En una computadora digital sólo hay dos posibilidades, que se escriben como 0 y 1, para el
objeto indivisible más pequeño. En última instancia, todos los programas y datos se pueden
reducir a combinaciones de bits. A través de los años se ha usado una variedad de dispositivos
en las computadoras digitales para almacenar bits. Los circuitos electrónicos permiten que
estos dispositivos de almacenamiento se comuniquen entre sí. Un bit en una parte del circuito
es trasmitido a otra parte del circuito como un voltaje. Entonces se necesitan dos niveles
de voltaje; por ejemplo, un voltaje alto puede comunicar un 1 y un voltaje bajo, un 0.
En esta sección analizaremos los circuitos combinatorios. La salida de un circuito
combinatorio se define de manera única para cada combinación de entradas. Un circuito de
este tipo carece de memoria; las entradas anteriores y el estado del sistema no afectan su
salida. Los circuitos para los cuales la salida es una función, no sólo de las entradas sino
también del estado del sistema, se llaman circuitos secuenciales y se estudiarán en el capítulo
12.
Los circuitos combinatorios se pueden construir usando dispositivos de estado sólido,
llamados compuertas, que son capaces de cambiar los niveles de voltaje (bits). Se comenzará
por analizar las compuertas AND (y), OR (o) y NOT (no).
Una compuerta AND recibe entradas x1 y x2, donde x1 y x2 son bits, y produce una salida denotada
por x1
∧ x2, donde
Una compuerta AND se dibuja como se indica en la figura 11.1.1.
Una compuerta OR recibe entradas x1 y x2, donde x1 y x2 son bits, y produce una salida denotada
por x1
∨ x2, donde
Una compuerta OR se dibuja como se indica en la figura 11.1.2.
Una compuerta NOT (o inversor) recibe una entrada x, donde x es un bit, y produce una salida
denotada por x, donde
Una compuerta NOT se dibuja como se indica en la figura 11.1.3.
La tabla lógica de un circuito combinatorio lista todas las entradas posibles junto
con las salidas producidas.
A continuación aparecen las tablas lógicas para los circuitos AND, OR y NOT básicos (figuras
11.1.1 a la 11.1.3).
Se observa que realizar la operación AND (OR) es lo mismo que tomar el mínimo (máximo)
de dos bits x1 y x2.
El circuito de la figura 11.1.4 es un ejemplo de un circuito combinatorio, ya que la salida y
se define de manera única para cada combinación de entradas x1, x2 y x3.

x1 ∧ x2 x1 x2 x1 ∨ x2 x x
Definición 11.1.1

x1 ∧ x2 = 1 ifx1 = 1 and x2 = 1
0 otherwise.
si y
de otra manera.
x1 ∨ x2 = 1 ifx1 = 1 or x2 = 1
0 otherwise.
si o
de otra manera.
Figura 11.1.1 Compuerta AND.
Figura 11.1.2 Compuerta OR.
Figura 11.1.3 Compuerta NOT.
▼ Definición 11.1.2

Definición 11.1.3

x x
Ejemplo 11.1.4

Ejemplo 11.1.5


La tabla lógica para este circuito combinatorio es la siguiente.
Observe que se listan todas las combinaciones posibles de los valores de las entradas
x1, x2 y x3. Para un conjunto determinado de entradas, el valor de la salida y se calcula rastreando
el flujo a través del circuito. Por ejemplo, la cuarta línea de la tabla da el valor de
la salida y para los valores de entrada
x1
= 1, x2
= 0, x3
= 0.
Si x1
= 1 y x2
= 0, la salida de la compuerta AND es 0 (vea la figura 11.1.5). Como
x3
= 0, las entradas a la compuerta OR son ambas 0. Por lo tanto, la salida de la compuerta
OR es 0. Como la entrada a la compuerta NOT es 0, se produce una salida y = 1.
El circuito de la figura 11.1.6 no es un circuito combinatorio porque la salida y no es única
para cada combinación de entradas x1 y x2. Por ejemplo, suponga que x1
= 1 y x2
= 0.
Si la salida de la compuerta AND es 0, entonces y = 0. Por otro lado, si la salida de la compuerta
AND es 1, entonces y = 1. Un circuito de este tipo sirve para almacenar un bit.
Los circuitos combinatorios individuales se pueden interconectar. Es posible combinar los
circuitos combinatorios C1, C2 y C3 de la figura 11.1.7, como se muestra, para obtener el
circuito combinatorio C.
x1
y
x2
Figura 11.1.4 Un circuito combinatorio.
Figura 11.1.5 Circuito de la figura 11.1.4 cuando x1
= 1 y
x2
= x3
= 0.
Figura 11.1.6 Un circuito que no es combinatorio.
Ejemplo 11.1.6

Ejemplo 11.1.7

▼ ▼
Un circuito combinatorio con una salida, como el de la figura 11.1.4, se representa mediante
una expresión que usa los símbolos ∧, ∨ y ¬. Se sigue el flujo del circuito simbólicamente.
Primero se aplica AND a x1 y x2 (figura 11.1.8), lo que produce la salida x1
∧ x2. Esta
salida después se une por OR con x3 para producir la salida (x1
∧ x2) ∨ x3. Después se aplica
NOT a esta salida. Entonces la salida y puede ser
(11.1.1)
Las expresiones como (11.1.1) se llaman expresiones booleanas.
Las expresiones booleanas en los símbolos x1, . . . , xn se definen de manera recursiva como
sigue.
0, 1, x1, . . . , xn (11.1.2)
son expresiones booleanas. Si X1 y X2 son expresiones booleanas, entonces
(11.1.3)
son expresiones booleanas.
Si X es una expresión booleana en los símbolos x1, . . . , xn, algunas veces se escribe
Cualquiera de los símbolos x o x se llama literal.
Utilice la definición 11.1.9 para demostrar que el lado derecho de (11.1.1) es una expresión
booleana en x1, x2 y x3.

Figura 11.1.7 El circuito combinatorio C se obtiene interconectando
los circuitos combinatorios C1, C2 y C3.
Figura 11.1.8 Representación de un circuito combinatorio mediante
una expresión booleana.

Ejemplo 11.1.8

y = (x1 ∧ x2) ∨ x3.
a) (X 1), b) X1, c) X1 ∨ X2, d) X1 ∧ X2
X = X(x1, . . . , xn).

Definición 11.1.9

Ejemplo 11.1.10

Por (11.1.2), x1 y x2 son expresiones booleanas. Por (11.1.3d), x1
∧ x2 es una expresión
booleana. Por (11.1.3a), (x1
∧ x2) es una expresión booleana. Por (11.1.2), x3 es una
expresión booleana. Como (x1
∧ x2) y x3 son expresiones booleanas, por (11.1.3c), también
lo es (x1
∧ x2) ∨ x3. Por último, se aplica (11.1.3b) para concluir que
es una expresión booleana.
Si X = X(x1, . . . , xn) es una expresión booleana y se asignan valores a1, . . . , an
en {0, 1} a x1, . . . , xn, se pueden usar las definiciones 11.1.1 a la 11.1.3 para calcular el
valor de X. Este valor se denota por X(a1, . . . , an) o X(xi
= ai).
Para x1
= 1, x2
= 0 y x3
= 0, la expresión booleana X(x1, x2, x3) = de
(11.1.1) se convierte en
Se calculó de nuevo el cuarto renglón de la tabla en el ejemplo 11.1.5.
En una expresión booleana en la que no se usan paréntesis para especificar el orden
de las operaciones, se supone que ∧ es evaluado antes de ∨.
Para x1
= 0, x2
= 0 y x3
= 1, el valor de la expresión booleana x1
∧ x2
∨ x3 es
El ejemplo 11.1.8 mostró cómo se representa un circuito combinatorio con una salida
como una expresión booleana. El siguiente ejemplo muestra cómo se construye un circuito
combinatorio que representa una expresión booleana.
Encuentre el circuito combinatorio correspondiente a la expresión booleana
y escriba la tabla lógica para el circuito obtenido.
Se comienza con la expresión x2
∨ x3 en el paréntesis interior. Esta expresión se convierte
en un circuito combinatorio como el mostrado en la figura 11.1.9.
Se aplica AND a la salida de este circuito y x1 para producir el circuito dibujado en la
figura 11.1.10. Por último, se aplica OR a la salida de este circuito y x2 para dar el circuito
deseado de la figura 11.1.11. La tabla lógica es la que sigue.
▼ ▼
(x1 ∧ x2) ∨ x3

X(1, 0, 0) = (1 ∧ 0) ∨ 0
= 0 ∨ 0 ya que 1 ∧ 0 = 0
= 0 ya que 0 ∨ 0 = 0
= 1 ya que 0 = 1.
x1 ∧ x2 ∨ x3 = 0 ∧ 0 ∨ 1 = 0 ∨ 1 = 1.
(x1 ∧ (x2 ∨ x3)) ∨ x2
(x1 ∧ x2) ∨ x3
Ejemplo 11.1.11

Ejemplo 11.1.12

Ejemplo 11.1.13

Figura 11.1.9 Circuito combinatorio
correspondiente a la expresión booleana
x
2
∨ x3.
Figura 11.1.10 Circuito combinatorio correspondiente a la
expresión booleana x3
∧ (x2
∨ x3)
1. ¿Qué es un circuito combinatorio?
2. ¿Qué es un circuito secuencial?
3. ¿Qué es una compuerta AND?
4. ¿Qué es una compuerta OR?
5. ¿Qué es una compuerta NOT?
6. ¿Qué es un inversor?
7. ¿Qué es una tabla lógica de un circuito combinatorio?
8. ¿Qué es una expresión booleana?
9. ¿Qué es una literal?
x1 x2 x3 (x1 ∧ (x2 ∨ x3)) ∨ x2
1
1
1
1
1
1
0
0
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0
Figura 11.1.11 Circuito combinatorio correspondiente a la expresión
booleana (x1 ∧ (x2 ∨ x3)) ∨ x2.

Sección de ejercicios de repaso
Ejercicios
En los ejercicios 1 al 6, escriba la expresión booleana que representa
el circuito combinatorio, escriba la tabla lógica y escriba la salida de
cada compuerta simbólicamente como en la figura 11.1.8.
1.
2.
3.
4.
5.
6. El circuito inferior de la figura 11.1.7.
Los ejercicios 7 al 9 se refieren al circuito
7. Demuestre que este circuito no es un circuito combinatorio.
8. Demuestre que si x = 0, la salida y está determinada de manera
única.
9. Demuestre que si x = 1, la salida y es indeterminada.
En los ejercicios 10 al 14, encuentre el valor de las expresiones booleanas
para
10.
x1 = 1, x2 = 1, x3 = 0, x4 = 1.
x1 ∧ x2
11.
12.
13.
14.
15. Usando la definición 11.1.9, demuestre que cada expresión en los
ejercicios 10 al 14 es una expresión booleana.
En los ejercicios 16 al 20, determine si la expresión indicada es booleana.
Si lo es, utilice la definición 11.1.9 para demostrarlo.
16.
17.
18.
19.
20.
21. Encuentre el circuito combinatorio correspondiente a cada expresión
booleana en los ejercicios 10 al 14 y escriba la tabla lógica.
Un circuito de conmutación es una red eléctrica que consiste en interruptores
cada uno de los cuales está abierto o cerrado. Un ejemplo
aparece en la figura 11.1.12. Si el interruptor X está abierto (cerrado)
se escribe X = 0 (X = 1). Los interruptores etiquetados con la misma
letra, como B en la figura 11.1.12, están todos abiertos o todos cerrados.
El interruptor X, como A en la figura 11.1.12, está abierto si y sólo
si el interruptor X, como A, está cerrado. Si puede fluir corriente
entre las terminales extremas izquierda y derecha del circuito, se dice
que la salida del circuito es 1; de otra manera, se dice que la salida del
circuito es 0. Una tabla de conmutación da la salida del circuito para
todos los valores de los interruptores. La tabla de conmutación para la
figura 11.1.12 es la siguiente:
22. Dibuje un circuito con dos interruptores A y B que tienen la propiedad
de que la salida del circuito es 1 precisamente cuando ambos,
A y B, están cerrados. Esta configuración se etiqueta A ∧ B y
se llama circuito en serie.
23. Dibuje un circuito con dos interruptores A y B que tienen la propiedad
de que la salida del circuito es 1 justo cuando uno de ellos,
A o B, está cerrado. Esta configuración se etiqueta A ∨ B y se llama
circuito en paralelo.
24. Demuestre que el circuito de la figura 11.1.12 se puede representar
simbólicamente como
Represente cada circuito en los ejercicios 25 al 29 simbólicamente y dé
su tabla de conmutación.
25.
26.
27.
28.
29.
Represente las expresiones en los ejercicios 30 al 34 como circuitos de
conmutación y escriba las tablas de conmutación.

En la sección anterior se definieron dos operadores binarios ∧ y ∨ en Z2
= {0, 1} y un
operador unitario – en Z2. (En el resto de este capítulo Z2 denota el conjunto {0, 1}). Se
vio que estos operadores podían implementarse en los circuitos como compuertas. En esta
sección se analizan algunas propiedades del sistema que consiste en Z2 y los operadores
∧, ∨ y –.
Si ∧, ∨ y – son los operadores de las definiciones 11.1.1 a la 11.1.3, entonces se cumplen
las siguientes propiedades.
a) Leyes asociativas:
para todo a, b, c ∈ Z2.
b) Leyes conmutativas:
para todo a, b ∈ Z2.
c) Leyes distributivas:
para todo a, b, c ∈ Z2.
d) Leyes de identidad:
para todo a ∈ Z2.
e) Leyes de complementos:
para todo a ∈ Z2.
Demostración Las demostraciones son verificaciones directas. Se probará la primera ley
distributiva y las otras ecuaciones se dejan como ejercicios (vea los ejercicios 16 y 17).
Debe demostrarse que
para todo a, b, c ∈ z2. (11.2.1)
Simplemente se evalúan ambos lados de (11.2.1) para todos los valores posibles de a, b
y c en Z2 y se verifica que en cada caso se obtenga el mismo resultado. La tabla proporciona
los detalles.
Utilice el Teorema 11.2.1 para demostrar que los circuitos combinatorios de la figura 11.2.1
tienen salidas idénticas para entradas idénticas dadas.
Las expresiones booleanas que representan los circuitos son, respectivamente,
x1 ∨ (x2 ∧ x3), (x1 ∨ x2) ∧ (x1 ∨ x3).
11.2➜Propiedades de los circuitos combinatorios
WWW
Teorema 11.2.1
(a ∨ b) ∨ c = a ∨ (b ∨ c)
(a ∧ b) ∧ c = a ∧ (b ∧ c)
a ∨ b = b ∨ a, a ∧ b = b ∧ a
a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
a ∨ 0 = a, a ∧ 1 = a
a ∨ a = 1, a ∧ a = 0
a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
a b c a∧
(b ∨ c) (a ∧ b) ∨ (a ∧ c)
1 1 1 1 1
1 1 0 1 1
1 0 1 1 1
1 0 0 0 0
0 1 1 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 0 0
Ejemplo 11.2.2

Por el Teorema 11.2.1c),
para todo a, b, c ∈ Z2 (11.2.2)
Pero (11.2.2) dice que los circuitos combinatorios de la figura 11.2.1 tienen salidas idénticas
para valores idénticos de entrada.
Las expresiones booleanas arbitrarias se definen iguales si tienen los mismos valores
para todas las asignaciones posibles de bits a las literales.
Sean
expresiones booleanas. Se dice que X1 es igual a X2, y se escribe
X1
= X2
si
para todo ai
∈ Z2.
Demuestre que
(11.2.3)
Según la definición 11.2.3, la ecuación (11.2.3) se cumple si es cierta para todas las
opciones de x y y en Z2. Entonces se puede simplemente elaborar una tabla que liste todas
las posibilidades para verificar (11.2.3).
Si se define una relación R en el conjunto de expresiones booleanas mediante la regla
X1 R X2 si X1
= X2, R es una relación de equivalencia. Cada clase de equivalencia consiste
en un conjunto de expresiones booleanas donde cada una es igual a cualquier otra.
Por las leyes asociativas, Teorema 11.2.1a), se puede escribir sin ambigüedad
(11.2.4)
o bien,
(11.2.5)

a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
X1 = X1(x1, . . . , xn) and X2 = X2(x1, . . . , xn)
X1(a1, . . . , an) = X2(a1, . . . , an)
(x ∨ y) = x ∧ y.
x y
1 1
1 0
0 1
0 0
(x ∨ y) x ∧ y
0 0
0 0
0 0
1 1
a1 ∨ a2 ∨ ··· ∨ an
a1 ∧ a2 ∧ ··· ∧ an
Figura 11.2.1 Los circuitos combinatorios a) y b) tienen salidas idénticas para
entradas idénticas dadas y se dice que son equivalentes.
Definición 11.2.3

y

Ejemplo 11.2.4


para ai
∈ Z2. El circuito combinatorio correspondiente a (11.2.4) se dibuja como en la figura
11.2.2 y el circuito combinatorio correspondiente a (11.2.5) se dibuja como en la figura
(11.2.3).
Las propiedades listadas en el Teorema 11.2.1 se cumplen en muchos sistemas. Un
sistema que satisface estas propiedades se llama una álgebra booleana. Las álgebras booleanas
abstractas se examinarán en la sección 11.3.
Una vez definida la igualdad de las expresiones booleanas, se define la equivalencia
de los circuitos combinatorios.
Se dice que dos circuitos combinatorios, cada uno con entradas x1, . . . , xn y una sola salida,
son equivalentes si, siempre que los circuitos reciban las mismas entradas, producen
las mismas salidas.
Los circuitos combinatorios de las figuras 11.2.4 y 11.2.5 son equivalentes ya que, como se
observa, tienen tablas lógicas idénticas.
Si se define una relación R en un conjunto de circuitos combinatorios por la regla C1
R C2 si C1 y C2 son equivalentes (en el sentido de la definición 11.2.5), R es una relación
de equivalencia. Cada clase de equivalencia consiste en un conjunto de circuitos combinatorios
mutuamente equivalentes.
El ejemplo 11.2.6 indica que es posible que los circuitos equivalentes no tengan el
mismo número de compuertas. En general, es deseable emplear el menor número posible
de compuertas para minimizar el costo de las componentes.
Se deduce de inmediato, a partir de las definiciones, que los circuitos combinatorios
son equivalentes si y sólo si las expresiones booleanas que los representan generan tablas
lógicas idénticas.

Figura 11.2.2 Compuerta OR con n entradas. Figura 11.2.3 Compuerta AND con n entradas.
Definición 11.2.5

Ejemplo 11.2.6

Figura 11.2.4 Un circuito
combinatorio y su tabla lógica.
Figura 11.2.5 Circuito
combinatorio y su tabla lógica,
que es idéntica a la tabla lógica
de la figura 11.2.4. Se dice que
los circuitos de las figuras 11.2.4
y 11.2.5 son equivalentes porque
tienen tablas lógicas idénticas.

Sea C1 y C2 circuitos combinatorios representados respectivamente por las expresiones
booleanas X1
= X1(x1, . . . , xn) y X2
= X2(x1, . . . , xn). Entonces C1 y C2 son equivalentes
si y sólo si X1
= X2.
Demostración El valor X1(a1, . . . , an) [respectivamente, X2(a1, . . . , an)] para ai

Z2 es la salida del circuito C1 (respectivamente, C2) para entradas a1, . . . , an.
De acuerdo con la definición 11.2.5, los circuitos C1 y C2 son equivalentes si y sólo
si tienen las mismas salidas X1(a1, . . . , an) y X2(a1, . . . , an) para todas las entradas
posibles a1, . . . , an. Entonces, los circuitos C1 y C2 son equivalentes si y sólo si
X1(a1 ,. . . , an) = X2(a1, . . . , an) para todo a1
∈ Z2. (11.2.6)
Pero por la definición 11.2.3, la ecuación (11.2.6) se cumple si y sólo si X1
= X2.
En el ejemplo 11.2.4 se demostró que
Por el Teorema 11.2.7, los circuitos combinatorios (figuras 11.2.4 y 11.2.5) correspondientes
a estas expresiones son equivalentes.

(x ∨ y) = x ∧ y.
Teorema 11.2.7
Ejemplo 11.2.8

1. Establezca las leyes asociativas para ∧ y ∨.
2. Establezca las leyes conmutativas para ∧ y ∨.
3. Establezca las leyes distributivas para ∧ y ∨.
4. Establezca las leyes de identidad para ∧ y ∨.
5. Establezca las leyes de complementos para ∧, ∨ y
_
.
6. ¿Cuándo son iguales dos expresiones booleanas?
7. ¿Qué son expresiones combinatorias equivalentes?
8. ¿Cuál es la relación entre las expresiones combinatorias y las expresiones
booleanas que las representan?
Sección de ejercicios de repaso
Ejercicios
Demuestre que los circuitos combinatorios de los ejercicios 1 al 5 son
equivalentes.
1.
2.
3.
4.
5.
Verifique las ecuaciones en los ejercicios 6 al 10.
6.
7.
8.
9.
10.
Pruebe o desapruebe las ecuaciones en los ejercicios 11 al 15.
11.
12.
13.
14.
15.
16. Pruebe la segunda afirmación del Teorema 11.2.1c).
17. Pruebe los incisos a), b) y e) del Teorema 11.2.1.
Se dice que dos circuitos de conmutación son equivalentes si las expresiones
booleanas que los representan son iguales.
18. Demuestre que los circuitos de conmutación son equivalentes.
19. Para cada circuito de conmutación en los ejercicios 25 al 29 de la
sección 11.1, encuentre un circuito de conmutación equivalente
usando circuitos en paralelo y en serie que tengan el menor número
posible de interruptores.
20. Para cada expresión booleana en los ejercicios 30 al 34 de la sección
11.1, encuentre un circuito de conmutación usando circuitos
paralelos y en serie con el menor número posible de interruptores.
Un circuito puente es un circuito de conmutación, como el que se ilustra
en seguida, que usa circuitos no paralelos y no en serie.
Para cada circuito de conmutación, encuentre un circuito de conmutación
equivalente usando circuitos puente que tengan el menor número
de interruptores.
21.
22.
23.
24. Para cada expresión booleana en los ejercicios 30 al 34 de la sección
11.1, encuentre un circuito de conmutación usando circuitos
puente con el menor número posible de interruptores.
x1 ∨ x1 = x1
x1 ∨ (x1 ∧ x2) = x1
x1 ∧ x2 = (x1 ∨ x2)
x1 ∧ (x2 ∧ x3) = (x1 ∧ x2) ∨ (x1 ∧ x3)
(x1 ∨ x2) ∧ (x3 ∨ x4) = (x3 ∧ x1) ∨ (x3 ∧ x2) ∨ (x4 ∧ x1)
∨ (x4 ∧ x2)
x = x
x1 ∧ x2 = x1 ∨ x2
x1 ∧ ((x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3)) = x2 ∧ x3
((x1 ∧ x2) ∨ (x1 ∧ x3)) = (x1 ∨ x2) ∧ (x1 ∨ x3)
(x1 ∨ x2) ∧ (x3 ∨ x4) ∧ (x3 ∧ x2) = 0

En esta sección se consideran los sistemas generales que tienen propiedades como las indicadas
en el Teorema 11.2.1. Se verá que, en apariencia, varios sistemas obedecen estas mismas
leyes. Estos sistemas reciben el nombre de álgebras booleanas.
Un álgebra booleana B consiste en un conjunto S que contiene elementos distintos 0 y 1,
operadores binarios + y · en S, y un operador unitario  en S que satisface las siguientes leyes.
a) Leyes asociativas:
para todo x, y, z ∈ S.
b) Leyes conmutativas:
para todo x, y ∈ S.
c) Leyes distributivas:
para todo x, y, z ∈ S.
d) Leyes de identidad:
para todo x ∈ S.
e) Leyes de complementos:
para todo x ∈ S.
Si B es un álgebra booleana, se escribe B = (S, +, ·, , 0, 1).
Las leyes asociativas se pueden omitir de la definición 11.3.1, puesto que se deducen
de las otras leyes (vea el ejercicio 24).
Por el Teorema 11.2.1, (Z2, ∧, ∨, –, 0, 1) es un álgebra booleana. (Se está estableciendo que
Z2 denota el conjunto {0, 1}). Los operadores +, ·,  en la definición 11.3.1 son ∧, ∨, –, respectivamente.
Como es costumbre, suele abreviarse a · b como ab. También se supone que · se evalúa
antes que +. Esto permite eliminar algunos paréntesis. Por ejemplo, (xy) + z se escribe
de manera más sencilla como xy + z.
Es adecuado hacer algunos comentarios respecto a la definición 11.3.1. En primer lugar,
0 y 1 son sólo nombres simbólicos y, en general, no tienen relación con los números 0
y 1. Este mismo comentario se aplica a + y ·, que sólo denotan operadores binarios y, en
general, no tienen relación con la suma y multiplicación comunes.
Sea U un conjunto universal y sea S = P (U) el conjunto potencia de U. Si se definen las
siguientes operaciones
en S, entonces (S, ∪, ∩, –, ∅, U) es un álgebra booleana. El conjunto vacío ∅ asume el papel
de 0 y el conjunto universal U hace el papel de 1. Si X, Y y Z son subconjuntos de S,
las propiedades a) a la e) de la definición 11.3.1 se convierten en las siguientes propiedades
de conjuntos (vea el Teorema 2.1.12):
▼ ▼
(x + y) + z = x + (y + z)
(x · y) · z = x · (y · z)
x + y = y + x, x · y = y · x
x · (y + z) = (x · y) + (x · z)
x + (y · z) = (x + y) · (x + z)
x + 0 = x, x · 1 = x
x + x = 1, x · x = 0
X + Y = X ∪ Y, X · Y = X ∩ Y, X = X

(X ∩ Y ) ∩ Z = X ∩ (Y ∩ Z)
b) X ∪ Y = Y ∪ X, X ∩ Y = Y ∩ X
a ) ( X ∪ Y ) ∪ Z = X ∪ (Y ∪ Z)
11.3➜Álgebras booleanas
Definición 11.3.1

Ejemplo 11.3.2

Ejemplo 11.3.3 ▼
para todo X, Y, Z ∈ (U).
para todo X, Y ∈ P (U).
P
En este punto se derivan algunas otras propiedades de las álgebras booleanas. Primero
se demuestra que el elemento x en la definición 11.3.1e) es único.
En un álgebra booleana, el elemento x de la definición 11.3.1e) es único. Específicamente,
si x + y = 1 y xy = 0, entonces y = x.
Demostración
definición 11.3.1d)
definición 11.3.1e)
definición 11.3.1c)
definición 11.3.1b)
proporcionado
definición 11.3.1e)
definición 11.3.1b)
definición 11.3.1c)
proporcionado
definición 11.3.1d)
En un álgebra booleana, el elemento x recibe el nombre de complemento de x.
Ahora es posible derivar varias propiedades adicionales de las álgebras booleanas.
Sea B = (S, +, ·, , 0, 1) un álgebra booleana. Las siguientes propiedades se cumplen.
a) Leyes de idempotencia:
para todo x ∈ S.
b) Leyes de acotación:
para todo x ∈ S.
c) Leyes de absorción:
para todo x, y ∈ S.
d) Leyes de involución:
para todo x ∈ S.
e) Leyes de 0 y 1:
f) Leyes de De Morgan para álgebras booleanas:
para todo x, y ∈ S.

Como se explicó en el ejemplo 11.3.3, si U es un conjunto, (U) se puede considerar un
álgebra booleana. Por lo tanto, las leyes de De Morgan, que para conjuntos se pueden
enunciar
para todo X, Y ∈ (U),
se cumplen. Estas ecuaciones se verifican de manera directa (vea el Teorema 2.1.12), pero
el Teorema 11.3.6 demuestra que son una consecuencia de otras leyes.
Sin duda el lector ha observado que las ecuaciones que incluyen elementos de un
álgebra booleana vienen en pares. Por ejemplo, las leyes de identidad [definición 11.3.1d)]
son
Se dice que estos pares son duales.
El dual de una afirmación que incluye expresiones booleanas se obtiene sustituyendo 0 por
1, 1 por 0, + por · y · por +.
El dual de
es
Cada condición en la definición de álgebra booleana (definición 11.3.1) incluye su
dual. Por lo tanto, se tiene el siguiente resultado.
El dual de un teorema de álgebras booleanas también es un teorema.
Demostración Suponga que T es un teorema de álgebras booleanas. Entonces existe
una prueba P de T que involucra sólo las definiciones de un álgebra booleana (definición
11.3.1). Sea P la secuencia de afirmaciones obtenidas al sustituir cada enunciado
en P por su dual. Entonces P es una prueba del dual de T.
El dual de
(11.3.3)
es
(11.3.4)
Antes se probó (11.3.3) [vea la prueba del Teorema 11.3.6a)]. Si se escribe el dual de cada
afirmación en la demostración de (11.3.3), se obtiene la siguiente demostración de (11.3.4):
Las demostraciones dadas en el Teorema 11.3.6 de las dos afirmaciones del inciso b) son
duales entre sí.
▼ ▼ ▼ ▼
P
P
Ejemplo 11.3.7

(X ∪ Y ) = X ∩ Y, (X ∩ Y ) = X ∪ Y
x + 0 = x, x1 = x.
(x + y) = x y
(xy) = x + y
.
x + x = x
xx = x.
x = x1
= x(x + x)
= xx + xx
= xx + 0
= xx.
Ejemplo 11.3.9

Ejemplo 11.3.11

Ejemplo 11.3.12

Definición 11.3.8

Teorema 11.3.10

1. Defina álgebra booleana.
2. ¿Qué son las leyes de idempotencia para álgebras booleanas?
3. ¿Qué son las leyes de acotación para álgebras booleanas?
4. ¿Qué son las leyes de absorción para álgebras booleanas?
5. ¿Qué son las leyes de involución para álgebras booleanas?
6. ¿Qué son las leyes 0/1 para álgebras booleanas?
7. ¿Qué son las leyes de De Morgan para álgebras booleanas?
8. ¿Cómo se obtiene el dual de una expresión booleana?
9. ¿Qué puede decirse del dual de un teorema sobre álgebras booleanas?
Sección de ejercicios de repaso
Ejercicios
1. Verifique las propiedades a) a c) del ejemplo 11.3.3.
2. Sea S = {1, 2, 3, 6}. Defina
x + y = mcm(x, y), x · y = mcd(x, y),
para x, y ∈ S (mcm denota el mínimo común múltiplo y mcd el
máximo común divisor). Demuestre que es un
álgebra booleana.
3. S = {1, 2, 4, 8}. Defina + y · como en el ejercicio 2 y defina x = 8/x.
Demuestre que no es un álgebra booleana.
Sea Sn
= {1, 2, . . . , n}. Defina
x + y = máx{x, y}, x · y = mín{x, y}.
4. Demuestre que los incisos a) a c) de la definición 11.3.1 se cumplen
para Sn.
5. Demuestre que es posible definir 0, 1 y  de manera que
es un álgebra booleana si y sólo si n = 2.
6. Rescriba las condiciones del Teorema 11.3.6 para conjuntos como
los del ejemplo 11.3.3.
7. Interprete el Teorema 11.3.6 para conjuntos como los del ejemplo
11.3.3.
Escriba el dual de cada afirmación en los ejercicios 8 al 14.
8.
9.
10. Si y , entonces y = z.
11. xy = 0 si y sólo si xy = x.
12. Si , entonces
13. x = 0 si y sólo si para toda y.
14.
15. Pruebe la afirmación del ejercicio 8 al 14.
16. Pruebe los duales de las afirmaciones de los ejercicios 8 al 14.
17. Escriba el dual del Teorema 11.3.4. ¿Cómo se relaciona el dual
con el Teorema 11.3.4 en sí?
18. Pruebe las segundas afirmaciones de los incisos a), c) y f) del Teorema
11.3.6.
19. Pruebe las segundas afirmaciones de los incisos a), c) y f) del Teorema
11.3.6 obteniendo el dual de las demostraciones de las primeras
afirmaciones.
20. Pruebe el Teorema 11.3.6, incisos d) y e).
21. Deduzca el inciso a) de la definición 11.3.1 a partir de los incisos
b) a e) de la definición 11.3.1.
22. Sea U el conjunto de enteros positivos. Sea S la colección de subconjuntos
X de U con uno de X o X finito. Demuestre que
es un álgebra booleana.
23. Sea n un entero positivo. Sea S el conjunto de todos los divisores
de n, incluyendo 1 y n. Defina + y · como en el ejercicio 2 y defina
x = n/x. ¿Qué condición debe satisfacer n para que
sea un álgebra booleana?
24. Demuestre que las leyes asociativas se deducen de las otras leyes
de la definición 11.3.1.
(S, +, · , , 1, n)
(S, ∪, ∩, , ∅, U)
x + x(y + 1) = x
y = xy + x y
x + y = 0 x = 0 = y.
x + y = xx + y = x + z  + z
(x + y) = xy
(x + y)(x + 1) = x + xy + y
(Sn, +, · , , 0, 1)
(S, +, · , , 1, 8)
(S, +, · , , 1, 6)
x = 6
x
Rincón de solución Álgebras booleanas de problemas
Problema
Sea (S, +, · , , 0, 1) un álgebra booleana y sea A un subconjunto
de S. Demuestre que (A, +, · , , 0, 1) es un álgebra booleana
si y sólo si 1 ∈ A y xy ∈ A para todo x, y ∈ A.
Cómo atacar el problema
Como la afirmación dada es del tipo “si y sólo si”, hay que
probar dos afirmaciones:
Si (A, +, · , , 0, 1) es un álgebra booleana,
entonces 1 ∈ A y xy ∈ A para todo x, y ∈ A. (1)
Si 1 ∈ A y xy ∈ A para todo x, y ∈ A, entonces
(A, +, · , , 0, 1) es un álgebra booleana. (2)
Para probar la afirmación (1), resultan útiles las leyes especificadas
en la definición de “álgebra booleana” (definición
11.3.1) y las leyes derivadas del Teorema 11.3.6 que deben
obedecer los elementos de un álgebra booleana. Para probar
que (A, +, · , , 0, 1) es un álgebra booleana, se verificará que
se satisfacen las leyes especificadas en la definición 11.3.1.
Antes de continuar con la lectura es recomendable repasar la
definición 11.3.1 y el Teorema 11.3.6.
Cómo encontrar una solución
Primero se intentará probar la afirmación (1). Se supone que
(A, +, · , , 0, 1) es un álgebra booleana y se quiere probar
que
■ 1 ∈ A
y
■ xy∈ A para todo x, y ∈ A.



La definición 11.3.1 dice que un álgebra booleana
contiene el 1. Como (A, +, · , , 0, 1) es un álgebra booleana,
1 ∈ A.
Ahora suponga que x, y ∈ A. La definición 11.3.1 dice
que  es un operador unitario en A. Esto significa que y ∈ A.
La definición 11.3.1 también dice que · es un operador binario
en A. Esto quiere decir que xy ∈ A. Esto completa la
prueba de la afirmación (1).
Ahora se intentará probar el enunciado (2). Esta vez se
supone que 1 ∈ A y xy en A para todo x, y ∈ A y se quiere
probar que (A, +, · , , 0, 1) es un álgebra booleana. Según la
definición 11.3.1, se debe probar que
A contiene elementos distintos 0 y 1 (3)
+ y · son operadores binarios en A. (4)
 es un operador unitario en A. (5)
Las leyes asociativas se cumplen. (6)
Las leyes conmutativas se cumplen. (7)
Las leyes distributivas se cumplen. (8)
Las leyes de identidad se cumplen. (9)
Las leyes de complementos se cumplen. (10)
A contiene el 1 por suposición. Para demostrar la afirmación
(3), debe probarse que 0 ∈ A. Se tienen sólo dos suposiciones
acerca de A: 1 ∈ A y si x, y ∈ A, entonces xy ∈ A.
Todo lo que podemos hacer en este punto es combinar estas
suposiciones; es decir, tomar x = y = 1 y examinar la conclusión:
11 ∈ A. Ahora el Teorema 11.3.6e) [aplicado al álgebra
booleana (S, +, · , , 0, 1)] dice que 1 = 0.
Sustituyendo 1 ahora se sabe que 10 ∈ A. Pero el Teorema
11.3.6b) dice que para cualquier x, x 0 = 0. Entonces 10 = 0
está en A. ¡Se tuvo éxito! A contiene el 1 y el 0. 0 y 1 son distintos
porque son elementos del álgebra booleana (S, +, · , ,
0, 1). Por lo tanto, la afirmación (3) queda demostrada.
Para demostrar la aseveración (4), debe probarse que
+ y · son operadores binarios en A; es decir, si x, y ∈ A, entonces
x + y y xy están en A. Considere probar que · es un
operador binario en A. Se sabe que si x, y ∈ A, entonces xy
∈ A, que es muy cercano a lo que se desea probar. Si se pudiera
de alguna manera sustituir y por y en la expresión xy,
se podría concluir que xy ∈ A. Lo que se desea hacer es suponer
que x, y ∈ A, para deducir posteriormente
x, y ∈ A, (11)
y luego concluir
xy = xy ∈ A.
Para deducir la expresión (11), es necesario demostrar que si
y ∈ A, entonces y ∈ A. Pero esto es la afirmación (5). ¡Desviación!
Se trabajará en esta última.
Se supondrá que y ∈ A y se intentará probar que y ∈
A. Si se pudiera eliminar esa molesta x (en la hipótesis x, y ∈
A implica xy ∈ A), se tendría exactamente lo que se quiere.
De hecho se puede eliminar x haciendo x = 1 puesto que 1y
= y. Formalmente, se argumenta lo siguiente. Sea y en A.
Como 1 ∈ A, y = 1y ∈ A. [y = 1y por la definición 11.3.1b)
y 11.3.1d)]. La afirmación (5) queda demostrada.
Ahora de regreso a la aseveración (4). Sean x, y ∈ A.
Por la propiedad (5) que se acaba de probar, y ∈ A. Por la
condición dada, xy = xy ∈ A [y = y por el teorema
11.3.6d)]. Esto demuestra que · es un operador binario en A.
Las leyes de De Morgan [Teorema 11.3.6f)], de hecho,
permiten intercambiar + y ·, para poder usarlos a fin de probar
que si x, y ∈ A, entonces x + y ∈ A. Formalmente, se argumenta
lo siguiente. Suponga que x, y ∈ A. Por la
afirmación (5), se sabe que x y y están ambos en A. Como
ya se probó que · es un operador binario en A, xy ∈ A. Por
la aseveración (5), (xy) ∈ A. Por las leyes de De Morgan
[Teorema 11.3.6f)] y el Teorema 11.3.6d), x + y = x + y
= (xy) ∈ A. Por lo tanto, + es un operador binario en A. Esto
prueba la aseveración (4).
La siguiente afirmación que se debe probar es (6), que
trata de verificar las leyes asociativas.
(x + y) + z = x + (y + z),
(xy)z = x(yz) para todo x, y, z ∈ A.
Ahora bien, (S, +, · , , 0, 1) es un álgebra booleana y por ello
las leyes asociativas se cumplen en S. Como A es un subconjunto
de S, las leyes asociativas sin duda se cumplen en A.
Entonces la afirmación (6) se cumple. Por la misma razón,
las propiedades (7) a (10) también se cumplen en A. Por lo
tanto, (A, +, · , , 0, 1) es un álgebra booleana.
Solución formal
Suponga que (A, +, · , , 0, 1) es un álgebra booleana. Entonces
1 ∈ A. Suponga que x, y ∈ A. Entonces y ∈ A. Por tanto,
xy ∈ A.
Ahora suponga que 1 ∈ A y xy ∈ A para todo x, y ∈ A.
Haciendo x = y = 1, se obtiene 0 = 11 ∈ A. Tomando
x = 1, se obtiene y = 1y ∈ A. Entonces  es un operador unitario
en A. Sustituyendo y por y, se obtiene xy = xy ∈ A.
Así, · es un operador binario en A. Ahora bien, x + y = x +
y = (xy) ∈ A. Entonces + es un operador binario en A. Los
incisos a) a e) de la definición 11.3.1 se cumplen automáticamente
en A, ya que se cumplen en S. Por lo tanto (A, +, ·
, , 0, 1) es un álgebra booleana.
Resumen de las técnicas de solución de problemas
■ Al intentar desarrollar una demostración, escriba con
cuidado las suposiciones y qué se quiere probar.
■ Al intentar desarrollar una demostración, examine
definiciones y teoremas que tengan relación.
■ Para probar que algo es un álgebra booleana, vaya directamente
a la definición (definición 11.3.1).
■ Considere demostrar las afirmaciones en un orden diferente
al dado. En este problema fue más fácil probar
la afirmación (5) antes que la (4).
■ Intente diferentes sustituciones para las variables en
una afirmación cuantificada universalmente. (Después
de todo, “cuantificada universalmente” significa
que la afirmación se cumple para todos los valores).
Al hacer x = y = 1 en la afirmación
xy ∈ A para todo x, y ∈ A,
se pudo demostrar que 0 ∈ A.
Un circuito permite realizar una tarea específica. Si se quiere construir un circuito combinatorio,
el problema puede darse en términos de entradas y salidas. Por ejemplo, suponga
que se desea construir un circuito combinatorio para calcular el OR-exclusivo de x1 y x2. Se
puede establecer el problema haciendo una lista de las entradas y salidas que define el ORexclusivo.
Esto equivale a elaborar la tabla lógica deseada.
El OR-exclusivo de x1 y x2 escrito x1 ⊕ x2 se define en la tabla 11.4.1.
Una tabla lógica, con una salida, es una función. El dominio es el conjunto de entradas
y el recorrido o imagen es el conjunto de salidas. Para la función OR-exclusivo dada
en la tabla 11.4.1, el dominio es el conjunto
y el rango es el conjunto
Si se pudiera desarrollar una fórmula para la función OR-exclusivo de la forma
donde X es un expresión booleana, se podría resolver el problema de la construcción del
circuito combinatorio. Se podría simplemente construir el circuito correspondiente a X.
Las funciones que se pueden representar por expresiones booleanas se llaman funciones
booleanas.
Sea X(x1, . . . , xn) un expresión booleana. Una función f de la forma
se llama función booleana.
La función f: Z 3
2
→ Z2 definida por
es una función booleana. Las entradas y salidas se dan en la siguiente tabla.
En el siguiente ejemplo se muestra cómo una función f: Z n
2
→Z 2 puede interpretarse
como una función booleana.
▼ ▼
{(1, 1), (1, 0), (0, 1), (0, 0)}
Z2 = {0, 1}.
x1 x2 x1 ⊕ x2
0
1
1
0
1 1
1 0
0 1
0 0
x1 ⊕ x2 = X(x1, x2),
f (x1, . . . , xn) = X(x1, . . . , xn)
f (x1, x2, x3) = x1 ∧ (x2 ∨ x3)
x1 x2 x3 f (x1, x2, x3)
1
0
1
1
0
0
0
0
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0
11.4➜Funciones booleanas y simplificación de circuitos
Definición 11.4.1

Ejemplo 11.4.2

Ejemplo 11.4.3


TABLA 11.4.1 ■
OR-exclusivo.
Demuestre que la función f dada por la siguiente tabla es una función booleana.
Considere el primer renglón de la tabla y la combinación
(11.4.1)
Observe que si x1
= x2
= x3
= 1, como se indica en el primer renglón de la tabla, entonces
la expresión (11.4.1) es 1. Los valores de xi dados por cualquier otro renglón de la tabla dan
un valor de 0 a la expresión (11.4.1). De manera similar, para el cuarto renglón de la tabla
se puede construir la combinación
(11.4.2)
La expresión (11.4.2) tiene el valor 1 para los valores de xi dados por el cuarto renglón de
la tabla, mientras que los valores de xi dados por cualquier otro renglón de la tabla dan el
valor 0 para (11.4.2).
El procedimiento es claro. Se considera un renglón R de la tabla cuya salida es 1.
Después se forma la combinación x1
∧ x2
∧ x3 y se coloca una barra sobre cada xi cuyo valor
sea 0 en el renglón R. La combinación formada es 1 si y sólo si las xi tienen los valores
dados en el renglón R. Entonces, para el renglón 6, se obtiene la combinación
(11.4.3)
Después, se aplica OR a los términos de (11.4.1) a (11.4.3) para obtener la expresión
booleana
(11.4.4)
Se asegura que f (x1, x2, x3) y (11.4.4) son iguales. Para verificarlo, primero se supone que
x1, x2 y x3 tienen los valores dados por un renglón de la tabla para el que f (x1, x2, x3) = 1.
Entonces una de las expresiones (11.4.1) a la (11.4.3) es 1, de manera que el valor de
(11.4.4) es 1. Por otro lado, si x1, x2, x3 tienen los valores dados por un renglón de la tabla
para el que f (x1, x2, x3) = 0, todas las combinaciones (11.4.1) a (11.4.3) son 0, de manera
que el valor de (11.4.4) es 0. Entonces f y la expresión booleana (11.4.4) están de acuerdo
en Z 3
2; por lo tanto,
como se aseguró.
Después de una definición más, se mostrará que el método del ejemplo 11.4.4 se puede
usar para representar cualquier f : Z n
2
→ Z2.
Un mintérmino en los símbolos x1, . . . , xn es una expresión booleana de la forma
donde cada yi es ya sea xi o Xi.
▼ ▼
Ejemplo 11.4.4

x1 x2 x3 f (x1, x2, x3)
1
0
0
1
0
1
0
0
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0
x1 ∧ x2 ∧ x3.
x1 ∧ x2 ∧ x3.
x1 ∧ x2 ∧ x3.
(x1 ∧ x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3).
f (x1, x2, x3) = (x1 ∧ x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3),
y1 ∧ y2 ∧ ··· ∧ yn,
Definición 11.4.5

Si f: Z n
2
→Z2, entonces f es una función booleana. Si f no es idénticamente cero, sea
A1, . . . , Ak los elementos Aj de Z n
2 para los cuales f (Ai) = 1. Para cada Ai
= (a1, . . . ,
an), sea
donde
entonces
(11.4.5)
Demostración Si f (x1, . . . , xn) = 0 para todo xi, entonces f es una función booleana,
ya que 0 es una expresión booleana.
Suponga que f no es idénticamente cero. Sea mi(a1, . . . , an) el valor obtenido de
mi al sustituir cada xj por aj. Se deduce de la definición de mi que
Sea A ∈ Z n
2. Si A = Ai para alguna i ∈ {1, . . . , k}, entonces f (A) = 1, mi(A)
= 1 y
Por otro lado, si A ≠ Ai para cualquier i ∈ {1, . . . , k}, entonces f (A) = 0, mi(A) = 0
para i = 1, . . . , k y
Por lo tanto, (11.4.5) se cumple.
La representación (11.4.5) de una función booleana f: Z n
2
→ Z2 se llama forma
disyuntiva normal de la función f.
Diseñe un circuito combinatorio que calcule el OR-exclusivo de x1 y x2.
La tabla lógica para la función OR-exclusivo x1 ⊕ x2 se reproduce en la tabla 11.4.1.
La forma disyuntiva normal de esta función es
(11.4.6)
El circuito combinatorio correspondiente a (11.4.6) se presenta en la figura 11.4.1.

Teorema 11.4.6
mi = y1 ∧ · · ·∧ yn,
yj = x j si aj = 1
x j si aj = 0.
f (x1, . . . , xn) = m1 ∨ m2 ∨ · · ·∨ mk .
mi (A) = 1 siA = Ai
0 siA  Ai .
m1(A) ∨ · · ·∨mk (A) = 1.
m1(A) ∨ · · ·∨mk (A) = 0.
Definición 11.4.7

Ejemplo 11.4.8

x1 ⊕ x2 = (x1 ∧ x2) ∨ (x1 ∧ x2).
Figura 11.4.1 Circuito combinatorio para el ORexclusivo.

Suponga que una función está dada por una expresión booleana como
y se desea encontrar la forma disyuntiva normal de f. Se podría escribir la tabla lógica de f
y después usar el Teorema 11.4.6. De forma alternativa, se puede manejar directamente la
expresión booleana usando las definiciones y resultados de las secciones 11.2 y 11.3. Se comenzará
por distribuir los términos x3 como sigue:
Aunque esto representa la expresión booleana como una combinación de términos de la
forma y ∧ z, no está en la forma disyuntiva normal, ya que cada término no contiene todos
los símbolos x1, x2 y x3. Sin embargo, esto tiene remedio de la siguiente forma:
Esta expresión está en la forma disyuntiva normal de f.
El Teorema 11.4.6 tiene un dual. En este caso la función f se expresa como
(11.4.7)
Cada Mi es de la forma
(11.4.8)
donde yj es ya sea xj o xj. Un término de la forma (11.4.8) se llama maxtérmino y la representación
de f (11.4.7) se llama forma conjuntiva normal. Los ejercicios 24 al 28 exploran
con mayor detalle los maxtérmino y la forma conjuntiva normal .
f (x1, x2, x3) = (x1 ∨ x2) ∧ x3
(x1 ∨ x2) ∧ x3 = (x1 ∧ x3) ∨ (x2 ∧ x3).
(x1 ∧ x3) ∨ (x2 ∧ x3) = (x1 ∧ x3 ∧ 1) ∨ (x2 ∧ x3 ∧ 1)
= (x1 ∧ x3 ∧ (x2 ∨ x2)) ∨ (x2 ∧ x3 ∧ (x1 ∨ x1))
= (x1 ∧ x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3)
∨(x1 ∧ x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3)
= (x1 ∧ x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3)
∨(x1 ∧ x2 ∧ x3).
f (x1, . . . , xn) = M1 ∧ M2 ∧ · · · ∧ Mk .
y1 ∨ ··· ∨ yn,
1. Defina el OR-exclusivo.
2. ¿Qué es una función booleana?
3. ¿Qué es un mintérmino?
4. ¿Qué es la forma disyuntiva normal de una función booleana?
5. ¿Cómo se puede obtener la forma disyuntiva normal de una función
booleana?
6. ¿Qué es un maxtérmino?
7. ¿Qué es la forma conjuntiva normal de una función booleana?
Sección de ejercicios de repaso
Ejercicios
En los ejercicios 1 al 10. encuentre la forma normal disyuntiva de cada
función y dibuje el circuito combinatorio correspondiente a esa forma
normal disyuntiva.

En la sección anterior se mostró cómo diseñar un circuito combinatorio usando las compuertas
AND, OR y NOT que calculan una función arbitraria de Z2
n en Z2, donde Z2
= {0, 1}.
En este sección se considera el uso de otros tipos de compuertas para implementar un
circuito. También se estudia el problema de un diseño eficiente. Se concluye con la revisión
de varios circuito útiles que tienen salidas múltiples. En toda la sección, a ∧ b se
escribe ab.
Antes de considerar alternativas para las compuertas AND, OR y NOT, debe darse una
definición precisa de “compuerta”.
Una compuerta es una función de Z2
n en Z2.
La compuerta AND es la función ∧ de Z2
2 en Z2 definida como en la definición 11.1.1. La
compuerta NOT es la función – de Z2 en Z2 como en la definición 11.1.3.
La atención se centra en las compuertas que permiten construir circuitos combinatorios
arbitrarios.
Se dice que un conjunto de compuertas {g1, . . . , gk} es funcionalmente completo si,
dado cualquier entero positivo n y una función f de Z2
n en Z2, es posible construir un circuito
combinatorio que calcule f usando sólo las compuertas g1, . . . , gk.
El Teorema 11.4.6 demuestra que un conjunto de compuertas {AND, OR, NOT} es funcionalmente
completo.
Un hecho interesante es que se pueda eliminar ya sea AND o bien OR del conjunto
{AND, OR, NOT} y todavía obtener un conjunto de compuertas funcionalmente completo.
Los conjuntos de compuertas
{AND, NOT} {OR, NOT}
son funcionalmente completos.
Demostración Se demostrará que el conjunto de compuertas {AND, NOT} es funcionalmente
completo y se deja para los ejercicios el problema de demostrar que el otro conjunto
es funcionalmente completo (vea el ejercicio 1).
Se tiene
ley de involución
ley de De Morgan.
Por lo tanto, una compuerta OR se puede sustituir por una compuerta AND y tres compuertas
NOT. (El circuito combinatorio se ilustra en la figura 11.5.1).
▼ ▼ ▼ ▼
11.5➜Aplicaciones
WWW
Definición 11.5.1

Definición 11.5.3

Ejemplo 11.5.2

Ejemplo 11.5.4
▼ Teorema 11.5.5
Dada cualquier función f: Zn
2
→Z2, por el Teorema 11.4.6 se puede construir un circuito
combinatorio C usando las compuertas AND, OR y NOT, que calcula f. Pero la figura
11.5.1 muestra que cada compuerta OR se puede sustituir por compuertas AND y NOT.
Por lo tanto, el circuito C se puede modificar de manera que consista sólo de compuertas
AND y NOT. Entonces, el conjunto de compuertas {AND, NOT} es funcionalmente completo.
Aunque ninguno de AND, OR o NOT por sí solos forma un conjunto funcionalmente
completo (vea los ejercicios 2 al 4), es posible definir una nueva compuerta que, por sí misma,
forme un conjunto funcionalmente completo.
Una compuerta NAND recibe entradas x1 y x2, donde x1 y x2 son bits, y produce una salida
denotada por x1
↑x2, donde
Una compuerta NAND se dibuja como se muestra en la figura 11.5.2.
Muchos circuitos básicos usados hoy en las computadoras digitales se construyen a
partir de compuertas NAND.
El conjunto {NAND} es un conjunto de compuertas funcionalmente completo.
Demostración Primero se observa que
Por lo tanto,
(11.5.1)
(11.5.2)
Las ecuaciones (11.5.1) y (11.5.2) muestran que tanto OR como NOT se pueden escribir
en términos de NAND. Por el Teorema 11.5.5, el conjunto {OR, NOT} es funcionalmente
completo. Se concluye que el conjunto {NAND} también es funcionalmente completo.
Diseñe circuitos combinatorios usando compuertas NAND para comparar las funciones
f1(x) = x y f2(x, y) = x ∨ y.
Los circuitos combinatorios, derivados de las ecuaciones (11.5.1) y (11.5.2), se ilustran
en la figura 11.5.3.

x1 ↑ x2 = 0 ifx1 = 1 and x2 = 1
1 otherwise.
Figura 11.5.1 Circuito combinatorio que usa
sólo las compuertas AND y NOT para calcular x ∨ y.
Figura 11.5.2 Compuerta NAND.
x y
x
y
Definición 11.5.6

si x1
y x2
= 1
de otra manera
Teorema 11.5.7
Ejemplo 11.5.8

x1
x2
x1 x2
Considere el problema de diseñar un circuito combinatorio usando compuertas AND,
OR y NOT para calcular la función f.
La forma disyuntiva normal de f es
(11.5.3)
El circuito combinatorio correspondiente a (11.5.3) se presenta en la figura 11.5.4.
El circuito combinatorio de la figura 11.5.4 tiene nueve compuertas. Como se demostrará,
es posible diseñar un circuito con menos compuertas. El problema de encontrar el mejor
circuito se llama problema de minimización. Existen muchas definiciones de “el mejor”.
Para encontrar un circuito más sencillo equivalente al de la figura 11.5.4, se intenta
simplificar la expresión booleana (11.5.3) correspondiente. Las ecuaciones
(11.5.4)
(11.5.5)
donde E representa una expresión booleana arbitraria, son útiles al simplificar expresiones
booleanas.
La ecuación (11.5.4) se deriva como sigue:
Ea ∨ Ea = E
E = E ∨ Ea,
Ea ∨ Ea = E(a ∨ a) = E1 = E
f (x, y, z) = xyz ∨ xyz ∨ x y z.
Figura 11.5.3 Circuitos combinatorios
usando sólo compuertas NAND que calculan
x y x ∨ y.

Figura 11.5.4 Circuito combinatorio que calcula f (x, y, z) = xyz ∨ xyz ∨ x y z.
usando las propiedades de álgebras booleanas. La ecuación (11.5.5) es en esencia la ley de
absorción [Teorema 11.3.6c)].
Mediante las ecuaciones (11.5.4) y (11.5.5), se puede simplificar la ecuación (11.5.3)
como sigue:
por (11.5.4)
por (11.5.5)
por (11.5.4).
Es posible una simplificación más,
(11.5.6)
aplicando la ley distributiva [definición 11.3.1c)]. La figura 11.5.5 muestra el circuito combinatorio
correspondiente a (11.5.6), que requiere sólo tres compuertas.
El circuito combinatorio en la figura 11.4.1 usa cinco compuertas AND, OR y NOT para calcular
el OR-exclusivo, x ⊕ y, de x y y. Diseñe un circuito que calcule x ⊕ y usando menos compuertas
AND, OR y NOT.
Por desgracia, las expresiones (11.5.4) y (11.5.5) no ayudan a simplificar la forma
disyuntiva normal de x ⊕ y. Entonces debemos experimentar con varias reglas
booleanas hasta producir una expresión que requiera menos de cinco compuertas. Una solución
está dada por la expresión
cuya implementación requiere sólo cuatro compuertas. Este circuito combinatorio se muestra
en la figura 11.5.6.
El conjunto de compuertas disponible determina el problema de minimización. Como
el estado de la tecnología determina las compuertas disponibles, el problema de minimización
cambia con el tiempo. En los años 50, el problema típico consistía en minimizar
circuitos considerando compuertas AND, OR y NOT. Se desarrollaron soluciones como el método
de Quine-McCluskey y el método de mapas de Karnaugh. Se recomienda al lector
consultar en [Mendelson] los detalles de estos métodos.
Los avances en la tecnología de estado sólido han hecho posible fabricar componentes
muy pequeños, llamados circuitos integrados, que en sí son circuitos completos.
Actualmente, diseñar un circuito consiste en combinar compuertas básicas como AND, OR,
NOT y NAND y los circuitos integrados para calcular las funciones deseadas. El álgebra booleana
sigue siendo una herramienta esencial, como lo mostraría una hojeada a cualquier
libro de diseño lógico como [McCalla].
x y ∨ x y
xyz ∨ xyz ∨ x y z = xy ∨ x y z
= xy ∨ xyz ∨ x y z
= xy ∨ xz.
xy ∨ xz = x(y ∨ z),
(x ∨ y)xy
Figura 11.5.5 Circuito combinatorio con tres
compuertas equivalente al de la figura 11.5.4.
Figura 11.5.6 Circuito combinatorio de cuatro
compuertas que calcula el OR-exclusivo x ⊕ y de x y y.
Ejemplo 11.5.9


Se concluye esta sección con el análisis de varios circuitos combinatorios útiles que
tienen salidas múltiples. Un circuito con n salidas se puede caracterizar por n expresiones
booleanas, como se aprecia el ejemplo siguiente.
Escriba dos expresiones booleanas para describir el circuito combinatorio de la figura
11.5.7.
La salida y1 se describe por la expresión
y y2 se describe por la expresión
El primer circuito se llama medio sumador (half adder) o semisumador.
Un medio sumador acepta como entrada dos bits x y y para producir como salida la suma
binaria cs de x y y. El término cs es un número binario de dos bits; s es el bit de la suma y
c es el bit de acarreo.
Circuito medio sumador
Diseñe un circuito combinatorio sumador parcial.
La tabla del medio sumador es la siguiente:
Esta función tiene dos salidas, c y s. Se observa que c = xy y s = x ⊕ y. Entonces se obtiene
el circuito medio sumador de la figura 11.5.8. Se usó el circuito de la figura 11.5.6 para
considerar el OR-exclusivo.

Ejemplo 11.5.10

y1 = ab,
y2 = bc ∨ ab.
Figura 11.5.7 Circuito combinatorio con dos salidas.
Definición 11.5.11

Ejemplo 11.5.12

Figura 11.5.8 Circuito medio sumador.
▼ ▼
Un sumador completo suma tres bits y se emplea para sumar dos bits y un tercer bit
de acarreo de una suma anterior.
Un sumador completo acepta como entrada tres bits x, y y z y produce como salida la suma
binaria cs de x, y y z. El término cs es un número binario de dos bits.
Circuito sumador completo
Diseñe un circuito combinatorio sumador completo.
La tabla para el circuito sumador completo es la siguiente:
Al verificar las ocho posibilidades, se observa que
así, se pueden utilizar dos circuitos OR-exclusivo para calcular s.
Para calcular c, primero se encuentra la forma disyuntiva normal
(11.5.7)
de c. Después se utilizan las ecuaciones (11.5.4) y (11.5.5) para simplificar la (11.5.7) como
sigue:
Es posible eliminar las compuertas adicionales si se escribe
Se obtiene el circuito sumador completo de la figura 11.5.9.

s = x ⊕ y ⊕ z;
c = xyz ∨ xyz ∨ x yz ∨ x yz
xyz ∨ xyz ∨ x yz ∨ x yz = xy ∨ x yz ∨ x yz
= xy ∨ xyz ∨ x yz ∨ x yz
= xy ∨ xz ∨ x yz
= xy ∨ xz ∨ xyz ∨ x yz
= xy ∨ xz ∨ yz.
c = xy ∨ z(x ∨ y).
x y z c s
1 1 1 1 1
1 1 0 1 0
1 0 1 1 0
1 0 0 0 1
0 1 1 1 0
0 1 0 0 1
0 0 1 0 1
0 0 0 0 0
Definición 11.5.13

Ejemplo 11.5.14

Figura 11.5.9 Circuito sumador completo.
x
z
y
c
s

El último ejemplo muestra cómo se emplean los circuitos medio sumador y sumador
completo para construir un circuito que sume números binarios.
Circuito para sumar números binarios
Empleando los circuitos sumador parcial y sumador completo, diseñe un circuito combinatorio
que calcule la suma de dos números de tres bits.
Sea M = x3 x2 x1 y N = y3 y2 y1 los números que deben sumarse y sea z4 z3 z2 z1 la suma.
El circuito que calcula la suma de M y N se ilustra en la figura 11.5.10. Se trata de una
implementación del algoritmo estándar para sumar números ya que, de hecho, el “bit de
acarreo” se acarrea a la siguiente suma binaria.
Si se estuvieran utilizando registros de tres bits para la suma, de manera que la suma
de dos números de tres bits fuera cuando mucho de tres bits, se podría usar el bit z4 en el
ejemplo 11.5.15 como una bandera de saturación. Si z4
= 1, ocurrió un desbordamiento; si
z4
= 0, no hubo saturación.
En el siguiente capítulo (ejemplo 12.1.3), se estudia un circuito secuencial que utiliza
un memoria interna primitiva para sumar números binarios.
Medio
sumador
Sumador
completo
Sumador
completo
Ejemplo 11.5.15

Figura 11.5.10 Un circuito combinatorio que calcula
la suma de dos números de tres bits.

1. ¿Qué es una compuerta?
2. ¿Qué es un conjunto de compuertas funcionalmente completo?
3. Dé ejemplos de conjuntos de compuertas funcionalmente completos.
4. ¿Qué es una compuerta NAND?
5. ¿El conjunto {NAND} es funcionalmente completo?
6. ¿Cuál es el problema de minimización?
7. ¿Qué es un circuito integrado?
8. Describa un circuito medio sumador.
9. Describa un circuito sumador completo.
Sección de ejercicios de repaso
Ejercicios
1. Demuestre que el conjunto de compuertas {OR, NOT} es funcionalmente
completo.
Demuestre que cada conjunto de compuertas en los ejercicios 2 al 5 no
es funcionalmente completo.
2. {AND} 3. {OR}
4. {NOT} 5. {AND, OR}
6. Dibuje un circuito con sólo compuertas NAND que calcule xy.
7. Escriba xy usando sólo ↑.
8. Pruebe o desapruebe: para todo
.
Escriba expresiones booleanas para describir los circuitos de salidas
múltiples en los ejercicios 9 al 11.
9.
x, y, z ∈ Z2
x ↑ (y ↑ z) = (x ↑ y) ↑ z,
10.
11.
12. Diseñe circuitos usando sólo compuertas NAND para calcular las
funciones de los ejercicios 1 al 10, sección 11.4.
13. ¿Puede reducir el número de compuertas NAND incluidas en cualquiera
de los circuitos del ejercicio 12?
14. Diseñe circuitos que usen el menor número de compuertas AND,
OR y NOT tanto como sea posible para calcular las funciones de los
ejercicios 1 al 10, sección 11.4.
15. Diseñe un circuito medio sumador usando sólo compuertas NAND.
16. Diseñe un circuito medio sumador usando cinco compuertas NAND.
Una compuerta NOR recibe entradas x1 y x2, donde x1 y x2 son bits, y
produce una salida denotada por x1
↓ x2, donde
17. Escriba xy, x ∨ y, x y x ↑ y en términos de ↓.
18. Escriba x ↓ y en términos de ↑.
19. Escriba la tabla lógica para la función nor.
20. Demuestre que el conjunto de compuertas {NOR} es funcionalmente
completo.
21. Diseñe circuitos usando sólo compuertas NOR para calcular las
funciones de los ejercicios 1 al 10, sección 11.4.
22. ¿Puede reducir el número de compuertas NOR empleadas en cualquiera
de sus circuitos para el ejercicio 21?
23. Diseñe un circuito medio sumador con sólo compuertas NOR.
24. Diseñe un circuito medio sumador con cinco compuertas NOR.
25. Diseñe un circuito con tres entradas que produce 1 justo cuando
dos o tres entradas tienen valor 1.
26. Diseñe un circuito que multiplique los números binarios x2 x1 y y2
y1. La salida será de la forma z4 z3 z2 z1.
27. Un módulo de 2 es un circuito que acepta como entrada dos bits
b y FLAGIN y produce bits c y FLAGOUT. Si FLAGIN = 1, entonces
c = b y FLAGOUT = 1. Si FLAGIN = 0 y b = 1, entonces FLAGOUT
= 1. Si FLAGIN = 0 y b = 0, entonces FLAGOUT = 0. Si FLAGIN
= 0, entonces c = b. Diseñe un circuito para implementar el módulo
de 2.
El complemento de 2 de un número binario se calcula utilizando el siguiente
algoritmo.
Algoritmo 11.5.16
Cómo encontrar el complemento de 2
Este algoritmo calcula el complemento de 2 CNCN − 1
· · · C2C1 del número
binario M = BNBN−1
· · · B2B1. El número M se barre de derecha
a izquierda y los bits se copian hasta que se encuentra 1. En adelante,
si Bi
= 0, se hace Ci
= 1 y si Bi
= 0, se hace Ci
= 0. La bandera F indica
si se encontró un 1 (F = verdadero) o no (F = falso).
Entrada: BNBN−1
· · · B1
Salida: CNCN−1
· · · C1
complemento_dos(B) {
F = falso
i = 1
while (¬F ∧ i ≤ n) {
Ci
= Bi
if (Bi
== 1)
F = verdadero
i = i + 1
}
while (i ≤ n) {
Ci
= Bi ⊕ 1
i = i + 1
}
return C
}
Encuentre el complemento de 2 de los números en los ejercicios 28 al
30 usando el algoritmo 11.15.16.
28. 101100
29. 11011
30. 011010110
31. Utilizando módulos de 2, diseñe un circuito que calcule el complemento
de 2 y3 y2 y1 del número binario de tres bits x3 x2 x1.
32. Sea * un operador binario en un conjunto S que contiene 0 y 1. Escriba
un conjunto de axiomas para *, modelado tomando en cuenta
las reglas que satisface NAND, de manera que si se define
entonces es un álgebra booleana.
33. Sea * un operador binario en S que contiene 0 y 1. Escriba un conjunto
de axiomas para *, modelado tomando en cuenta las reglas
que satisface NOR, y las definiciones de –, ∨ y ∧ de manera que
sea un álgebra booleana.
34. Demuestre que {→} es funcionalmente completo (vea la definición
1.2.3).
35. Sea B(x, y) una expresión booleana en las variables x y y que sólo
usa el operador ↔ (vea la definición 1.2.8).
a) Demuestre que si B contiene un número par de x, los valores
de B( x, y) y B(x, y) son iguales para toda x y y.
b) Demuestre que si B contiene un número impar de x, los valores
de B( x, y) y B(x.y) son iguales para toda x y y.
c) Utilice los incisos a) y b) para demostrar que {↔} no es funcionalmente
completo.
Paul Pluznikov contribuyó con este ejercicio.
(S, ∨, ∧, , 0, 1)
(S, ∨, ∧, , 0, 1)
x1 ↓ x2 = 0 if x1 = 1 or x2 = 1
1 otherwise.
si x1
= 1 o x2
= 1
de otra manera.
x = x ∗ x
x ∨ y = (x ∗ x) ∗ (y ∗ y)
x ∧ y = (x ∗ y) ∗ (x ∗ y),






Algunas referencias generales de álgebras booleanas son [Hohn; y Mendelson]. [Mendelson]
contiene más de 150 referencias de álgebras booleanas y circuitos combinatorios. Los libros de
diseño lógico incluyen [Kohavi; McCalla; y Ward].
[Hailperin] presenta un análisis técnico de las matemáticas de Boole. También proporciona
referencias adicionales. El libro de Boole, The Laws of Thought (Las leyes del pensamiento),
se ha reeditado (vea [Boole]).
A causa de nuestro interés en las aplicaciones del álgebra booleana, la mayor parte del
análisis se limitó al álgebra booleana . Sin embargo, las versiones de la mayoría
de nuestros resultados siguen siendo válidas para álgebras booleanas finitas arbitrarias.
Las expresiones booleanas en símbolos x1, . . . , xn sobre un álgebra booleana arbitraria
se definen de manera recursiva como
■ Para cada s ∈ S, s es una expresión booleana.
■ x1, . . . , xn son expresiones booleanas.
Si X1 y X2 son expresiones booleanas, también lo son
Una función booleana sobre S se define como una función de Sn a S de la forma
donde X es un expresión booleana en los símbolos x1, . . . , xn sobre S. Se puede definir una forma
disyuntiva normal para f. Otro resultado es que si X y Y son expresiones booleanas sobre S y
para todo xi
∈ S, entonces Y se puede derivar de X usando la definición de un álgebra booleana
(definición 11.3.1). Otros resultados son que cualquier álgebra booleana finita tiene 2n elementos
y que si dos álgebras booleanas tienen 2n elementos, en esencia, son la misma. Se concluye
que cualquier álgebra booleana finita es esencialmente el ejemplo 11.3.3, el álgebra booleana de
los subconjuntos de un conjunto universal finito U. Las demostraciones de estos resultados se
encuentran en [Mendelson].
(S, +, · , , 0, 1)
(Z2, ∨, ∧, , 0, 1).
(X1), X
1, X1 + X2, X1 · X2.
f (x1, . . . , xn) = X(x1, . . . , xn),
X(x1, . . . , xn) = Y (x1, . . . , xn)
Notas
Sección 11.1
1. Circuito combinatorio
2. Circuito secuencial
3. Compuerta AND
4. Compuerta OR
5. Compuerta NOT (inversor)
6. Tabla lógica de un circuito combinatorio
7. Expresión booleana
8. Literal
Sección 11.2
9. Propiedades de ∧, ∨ y –: leyes asociativas, conmutativas, distributivas, de identidad, de
complemento (vea el Teorema 11.2.1)
10. Expresiones booleanas iguales
11. Expresiones booleanas equivalentes
12. Las expresiones combinatorias son equivalentes si y sólo si las expresiones booleanas que
las representan generan tablas lógicas idénticas.
Sección 11.3
13. Álgebra booleana
14. x: complemento de x
15. Propiedades de álgebras booleanas: leyes de idempotencia, de acotación, de absorción, de
involución, 0 y 1, y leyes De Morgan
Repaso del capítulo
16. Dual de afirmación que incluye expresiones booleanas
17. El dual de un teorema de álgebras booleanas también es un teorema.
Sección 11.4
18. OR-exclusivo
19. Función booleana
20. Mintérmino: , donde cada yi es xi o xi
21. Forma disyuntiva normal
22. Cómo escribir una función booleana en la forma disyuntiva normal (Teorema 11.4.6)
23. Maxtérmino: , donde cada yi es xi o xi
24. Forma conjuntiva normal
Sección 11.5
25. Compuerta
26. Conjunto de compuertas funcionalmente completo
27. Los conjuntos de compuertas {AND, not} y {OR, NOT} son funcionalmente completos.
28. Compuerta NAND
29. El conjunto {NAND} es un conjunto de compuerta funcionalmente completo.
30. Problema de minimización
31. Circuito integrado
32. Circuito medio sumador
33. Circuito sumador completo
y1 ∨ y2 ∨ · · · ∨ yn,
y1 ∧ y2 ∧ · · · ∧ yn,
Autoevaluación del capítulo
Sección 11.1
1. Escriba una expresión booleana que represente el circuito combinatorio y escriba la tabla
lógica.
2. Encuentre el valor de la expresión booleana
si x1
= x2
= 0 y x3
= 1.
3. Encuentre un circuito combinatorio correspondiente a las expresiones booleanas del ejercicio
2.
4. Demuestre que el siguiente circuito no es combinatorio.
Sección 11.2
¿Son equivalentes los circuitos combinatorios en los ejercicios 5 y 6? Explique.
5.
(x1 ∧ x2) ∨ (x2 ∧ x3)
6.
Pruebe o desapruebe las ecuaciones en los ejercicios 7 y 8.
7.
8.
Sección 11.3
9. Si U es un conjunto universal y S = (U), el conjunto potencia de U, entonces
es un álgebra booleana. Establezca las leyes de frontera y absorción para esta álgebra booleana.
10. Pruebe que en cualquier álgebra booleana, para toda x y y.
11. Escriba el dual de la afirmación del ejercicio 10 y pruébelo.
12. Sea U el conjunto de enteros positivos. Sea S una colección de subconjuntos finitos de U.
¿Por qué no es un álgebra booleana?
Sección 11.4
En los ejercicios 13 al 16, encuentre la forma disyuntiva normal de una expresión booleana que
tiene una tabla lógica igual a la tabla que se incluye y dibuje el circuito correspondiente a la
forma disyuntiva normal.
13.
(S, ∪, ∩, , ∅, U)
(x(x + y · 0)) = x
P
x1 x2 x3 y
0
0
0
1
0
0
0
0
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0
(x ∧ y) ∨ (x ∧ z) ∨ (x ∧ y ∧ z) = y ∨ (x ∧ z)
(x ∧ y ∧ z) ∨ (x ∨ z) = (x ∧ z) ∨ (x ∧ z)
(S, ∪, ∩, , ∅, U)
14.
15.
16.
Sección 11.5
17. Escriba la tabla lógica para el circuito
18. Encuentre una expresión booleana en la forma disyuntiva normal para el circuito del inciso
a) del ejercicio 6. Use métodos algebraicos para simplificar la forma disyuntiva normal.
Dibuje el circuito correspondiente a la expresión simplificada.
19. Diseñe un circuito sólo con compuertas NAND para calcular x ⊕ y.
20. Diseñe un circuito sumador completo que use dos sumadores parciales y una compuerta OR.
1. Escriba un programa que tenga como entrada una expresión booleana en x y y e imprima la
tabla lógica de la expresión.
2. Escriba un programa que reciba como entrada una expresión booleana en x, y y z e imprima
la tabla lógica de la expresión.
Ejercicios para computadora
Capítulo 11 Autoevaluación
1.
2. 1.
3.
4. Suponga que x es 1. Entonces la entrada superior a la compuerta
OR es 0. Si y es 1, entonces la entrada inferior a la compuerta OR
es 0. Como ambas entradas a la compuerta OR son 0, la salida y de
la compuerta OR es 0, lo cual es imposible. Si y es 0, entonces la
entrada inferior a la compuerta OR es 1. Como la entrada a la compuerta
OR es 1, la salida y de la compuerta OR es 1, lo cual es imposible.
Por lo tanto, si la entrada al circuito es 1, la salida no está
determinada de manera única. Entonces el circuito no es un circuito
combinatorio.
5. Los circuitos son equivalentes. La tabla lógica para cualquiera de
los circuitos es
6. Los circuitos no son equivalentes. Si x = 0, y = 1 y z = 0, la salida
del circuito a) es 1, pero la salida del circuito b) es 0.
7. La ecuación es verdadera. La tabla lógica para cualquiera de las
expresiones es
8. La ecuación es falsa. Si x = 1, y = 0 y z = 1, entonces
pero
9. Leyes de acotación:
para toda X ∈ S.
Leyes de absorción:
para toda X, Y ∈ S.
10. (ley de acotación)
(ley de identidad)
(ley de idempotencia)
11. Dual:
(ley de acotación)
(ley de identidad)
(ley de idempotencia)
12.  no es un operador unitario en S. Por ejemplo, .
En los ejercicios 13 al 16, a ∧ b se escribe ab.