Álgebra Computacional

Grado en Ing. Informática - Universidad de Salamanca - Curso 2010/11

Problemas
Tema 4: Álgebras de Boole

Álgebras de Boole, funciones booleanas y diagramas de Karnaugh

100. Dado un conjunto X, considera P (X) = {subconjuntos de X}, el conjunto de las partes de
X. Demuestra que P (X) es un álgebra de Boole con las operaciones unión ∪, intersección
∩ y complementario.
101. Demuestra que el conjunto D30 ⊂ N de todos los divisores naturales del número 30
forma un álgebra de Boole con las operaciones suma ∨, producto ∧ y complementario a
siguientes:
a ∨ b = m.c.m{a, b} (mı́nimo común múltiplo),
a ∧ b = m.c.d{a, b} (máximo común divisor),
30
a= .
a
Demuestra de modo similar que Dq es álgebra de Boole siendo q un número natural
cuya descomposición en primos tiene sólo factores con exponente 1. ¿Qué ocurre si alguno
de los factores tiene exponente mayor que 1?
102. Simplifica las siguientes expresiones de elementos de un álgebra de Boole:
a) (a + b)(a + b + c).
b) (1 + a)(1 + b)(1 + c).
c) (1 + a)(a + b + c)(a + b).
d ) (a + b)(a + c)(b + c).
e) ((ac)0 b0 )(a + b).
f ) a0 bc + a0 bc0 + ab0 c + abc.
g) (ab0 c)0 + a0 b0 + a0 c.
h) (ab0 )0 + c0 )(c + a0 )0 .
103. Sea X un conjunto y P (X) el conjunto de todos los subconjuntos de X. Para A, B, C ∈
P (X), simplifica las expresiones:
a) [A ∩ (B ∪ C)] ∩ [B ∪ (A ∪ C)]
b) A ∪ [B ∩ [C ∪ (A ∩ B)]]
c) [(A ∪ C) ∩ B] ∪ [[(B ∩ D) ∪ D] ∩ B]
d) (A ∩ B ∩ C) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C)
e) [(A ∩ B) ∩ C] ∩ (A ∪ B)
f) (A ∩ B ∩ C) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C) ∪ (A ∩ B ∩ C)
g) [(A ∩ B ∩ C)] ∩ (A ∪ B) ∩ (A ∪ C)
h) [(A ∩ B) ∪ C] ∩ (C ∪ A)
104. Demuestra la siguiente igualdad en un álgebra de Boole: xy + yz + xz = xy + yz + xz.
105. Determina las funciones booleanas F y G que representan la siguiente tabla de valores:
14
 Hoja 4. Álgebra computacional. Curso 2010-11 15

x y z F G
0 0 0 0 0
0 0 1 0 0
0 1 0 0 1
0 1 1 0 0
1 0 0 0 0
1 0 1 1 0
1 1 0 0 1
1 1 1 0 0
106. Simplifica las siguientes funciones booleanas:
a) f (a, b, c) = a + bc + bc.
b) f (a, b, c, d) = ab + bc + ac + acd + abd + abc.
c) f (a, b, c, d) = a(c + b + d) + abc + abc + c(a + bd) + acd.
107. Dibuja los diagramas de Karnaugh y simplifica las expresiones siguientes:
a) xy + xy.
b) xy + xy.
c) xy + xy + x y.
108. Utiliza los diagramas de Karnaugh para simplificar las expresiones:
a) xyz + xy z + xyz + xyz + x y z.
b) xyz + xyz + xyz + xy z + xyz + x yz + x y z.
c) xy zt + xyzt + xyzt + x y zt + xy z t + xyz t + x y z t.
109. Considera el siguiente subconjunto de {0, 1}4 :
© ª
S = (1, 1, 0, 0), (1, 1, 1, 1), (1, 0, 1, 1), (1, 0, 0, 0), (0, 0, 0, 1), (0, 1, 0, 0), (0, 0, 0, 0), (0, 1, 0, 1) .

Simplifica la expresión booleana de la función f que toma valor 1 en el conjunto S y cero

en el resto.
110. Simplifica por Karnaugh la función f cuya tabla de valores es:
a b c d f
0 0 0 0 1
0 0 0 1 1
1 0 0 0 1
0 1 0 0 0
0 0 1 0 0
1 0 1 0 0
0 1 1 0 1
0 0 1 1 1
1 0 0 1 0
0 1 0 1 1
1 1 0 0 0
1 1 1 0 1
1 1 0 1 1
0 1 1 1 1
1 0 1 1 0
1 1 1 1 1
 16 Hoja 4. Álgebra computacional. Curso 2010-11

111. Sea la función booleana f : {0, 1}4 −→ {0, 1} dada por:

f (x, y, z, t) = xyzt + xyzt + xyzt + xyzt + x y z t + xyzt + x y zt + xyzt.
a) Utiliza las propiedades de un álgebra de Boole para demostrar que f (x, y, z, t) =
xz + x z.
b) Verifica el resultado anterior utilizando los diagramas de Karnaugh.

Aplicaciones: lógica proposicional

112. Construye la tabla de verdad de las proposiciones:
a) (a ∧ b) → c.
b) (a → b) ∧ (c → b)0 .
c) a0 → (b ∨ c)0 .
113. Halla la tabla de la verdad de la expresión (x ∧ ¬y) ∨ (y ∧ (¬x ∨ y)) y simplifı́cala.
114. Demuestra que la siguiente proposición es una tautologı́a (es decir, que siempre es cierta):
³ ¡ ¢ ´ ¡ ¢
(a → (b ∨ d)) ∧ (c → d) ∨ e ∧ ¬d ⇒ (¬b ∧ ¬e) → (¬a ∧ ¬c) .

¿Y qué puede decirse de

¡ ¢ ³³¡ ¢ ´ ¡ ¢´
a → (b ∨ d) ∧ (c → d) ∨ e ∧ ¬d ⇒ (¬b ∧ ¬e) → (¬a ∧ ¬c) ?
115. La proposición (a ∧ b ∧ c) ∧ (c → a) ∧ ((b ∨ c) → a)0 , ¿es un absurdo?
116. Estudia la validez de las siguientes proposiciones:
a) (p ∧ q) ∧ (r ↔ s) ∧ (r → q) ⇒ (p ∨ (q → s)).
b) (¬p ↔ q) ∧ (r ∧ p) ∧ (¬r → s) ⇒ q ∧ s.
c) (p → q) ∧ (r ∨ s) ∧ (s → ¬q) ∧ (r → ¬q) ⇒ p.
117. Analiza la veracidad de las expresiones:
a) (b + c) + bc = 1 ⇔ ab + abc = 0.
b) ab + ac + cd + acd = 0 ⇔ abcd + acb + bcd = 1.
118. Demuestra la validez ó invalidez del razonamiento siguiente:
(P ∧ Q) ∧ (M → (R ∧ S)) ∧ (S → (T ∧ ¬Q)) ⇒ ¬(P ∧ M ).
119. Averigua si (¬P ↔ Q) ∧ (Q → ¬R) ∧ R ⇒ P ∧ ¬Q.
120. Aurora, Beatriz y Claudia van con frecuencia a la cafeterı́a de la facultad después de sus
clases y cada una de ellas pide siempre café o té. Si Aurora pide café, entonces Beatriz
pide lo mismo que Claudia. Si Beatriz pide café, Aurora pide lo contrario que Claudia.
Si Claudia pide té, Aurora pide lo mismo que Beatriz. Mediante una tabla de verdad
descubrir cuál de ellas toma siempre lo mismo y qué es. Simplificar lo más posible la
expresión que permite al camarero servir a las tres estudiantes.
121. Demostrar la validez del siguiente argumento:
Si hoy es jueves, entonces tengo un test de computación o un test de eco-
nomı́a. Si mi profesor de economı́a está enfermo, entonces no tendré test
de economı́a. Hoy es jueves y mi profesor de economı́a está enfermo. Por lo
tanto, tengo un test de computación.
122. A partir del siguiente razonamiento:
 Hoja 4. Álgebra computacional. Curso 2010-11 17

Los ricos y las personas con buen corazón ayudan a los pobres. Los ladrones
que no tienen buen corazón son ricos. Joaquina es pobre, Enrique es un
ladrón y Nieves tiene buen corazón.
¿Que se puede deducir?
123. Se ha cometido un crimen y hay cuatro sospechosos: Ana, Bárbara, Carlos y David. Ana
dice que “Carlos lo hizo”, Bárbara que “Yo no lo hice”, Carlos dice que “Ana miente” y
David dice que “Ana lo hizo”.
Si exactamente uno de los cuatro enunciados es verdad. ¿Quien es el culpable? Si
exactamente uno de los cuatro enunciados es falso, ¿quien es el culpable?
124. En la ciudad de la ilusión hay dos bancos BCR (Banco de Crédito Regalado) y BAR
(Banco de Ahorro Remunerado) propiedad de los señores Crediticio y Ahorricio. El Sr.
Ahorricio sabe que si el señor Crediticio desea retirarse del mundo de los negocios nom-
brará presidente del banco a su hijo o venderá el banco. También sabe que si Creditico
necesita dinero vende el banco o lo pide prestado. Al Sr. Ahorricio le consta que Crediticio
no vendió el banco ni nombró presidente del banco a su hijo ni pidió dinero prestado. Por
tanto sacó la conclusión de que Crediticio no desea retirarse del mundo de los negocios ni
necesita dinero. ¿Es cierta la conclusión sacada por el Sr. Ahorricio?
125. Analizar la coherencia lógica - no teológica - del siguiente razonamiento:
Si Dios existe es todo amor y omnipotencia. Si Dios es incapaz de erradicar
el sufrimiento del mundo entonces no es omnipotente. Dios no es amor o
es capaz de erradicar el sufrimiento del mundo. Dios es capaz de erradi-
car el sufrimiento del mundo si no existe sufrimiento en el mundo. Existe
sufrimiento en el mundo. Por tanto: Dios no existe.
126. Formalizar y demostrar:
Duermo o navego por internet o no tengo hambre; cuando como, tengo sed
y no tengo frı́o; cuando tengo hambre, no duermo y no navego por internet;
cuando no duermo, como; por tanto, cuando tengo hambre y no navego por
internet, tengo sed.
127. Formalizar y demostrar:
Cuando me deprimo, como nı́scalos y arenques; cuando como arenques,
tengo sed y frı́o; tanto si tengo frı́o como si tengo sed, en ambos casos,
como galletas; cuando como galletas, si tengo sed, no como arenques; por
tanto, cuando como arenques, no como galletas y no me deprimo.

Aplicaciones: circuitos
128. Simplifica los circuitos:
a) a b
b) a Ä b0
ÄÄ ÄÄ Ä ÄÄ
ÄÄ ÄÄ ÄÄ ÄÄ

a0 b Ä c Ä
ÄÄ Ä Ä
ÄÄ ÄÄ ÄÄ

a Ä
ÄÄÄ
Ä

b Ä c Ä
Ä Ä
ÄÄ ÄÄ
 18 Hoja 4. Álgebra computacional. Curso 2010-11

129. Para los circuitos siguientes: da su expresión algebraica; simplifı́cala y diseña el nuevo
circuito.
i) a0 a0 a
ÄÄ ÄÄ ÄÄ
ÄÄ ÄÄ ÄÄ

b0 b Ä b Ä
ÄÄ Ä Ä
ÄÄ ÄÄ ÄÄ
ii) d Ä
Ä
ÄÄ f Ä
c Ä
Ä Ä
c Ä
ÄÄ ÄÄ
Ä
ÄÄ
b Ä c Ä
Ä Ä
a
ÄÄ ÄÄ
d0 a0 f0
ÄÄ ÄÄ ÄÄ ÄÄ
ÄÄ a0
ÄÄ ÄÄ ÄÄ
ÄÄ
ÄÄ b f0
ÄÄ ÄÄ
ÄÄ ÄÄ
iii) a Ä a Ä
Ä Ä
ÄÄ ÄÄ

a Ä b Ä b Ä
Ä Ä Ä
ÄÄ ÄÄ ÄÄ

a Ä b Ä c Ä c Ä
Ä Ä Ä Ä
ÄÄ ÄÄ ÄÄ ÄÄ
iv) a ÄÄ
Ä
ÄÄ c Ä
Ä
c0
ÄÄ
ÄÄ
ÄÄ Ä
b0
ÄÄ
b Ä
ÄÄ
Ä
ÄÄ

a0
ÄÄ
ÄÄ

a Ä b Ä
Ä Ä
ÄÄ ÄÄ

c0 b0
ÄÄ ÄÄ
ÄÄ ÄÄ
130. Diseñar un circuito cuyas entradas representen los números enteros del 0 al 7 en binario
y por cuya salida pasa corriente si el número es par o múltiplo de 3.
131. En un edificio de tres plantas (más la planta baja) van a poner un ascensor que tiene
una pantalla que indica en qué piso está la cabina. Diseña un circuito con 4 entradas que
permita visualizar el número de planta donde se encuentra el ascensor bajo el formato
usual:
 Hoja 4. Álgebra computacional. Curso 2010-11 19

132. Para evitar errores de transmisión en ciertos mensajes codificados, es frecuente añadir un
bit, llamado de control, a un bloque de bits. Ası́, por ejemplo, en la representación de
cifras decimales mediante un código binario,
0 se representa como a4 a3 a2 a1 a0 = 00001;
1 se representa como a4 a3 a2 a1 a0 = 00010;
2 se representa como a4 a3 a2 a1 a0 = 00100;
3 se representa como a4 a3 a2 a1 a0 = 00111, etc.
El bit de paridad c vale 1 si el número de unos del bloque es par y vale 0 en caso contrario.
Definir una expresión c que verifique lo anterior para los dı́gitos del 0 al 9 de manera que
sea lo más simplificada posible.
133. Un estudiante tiene que responder verdadero o falso a tres cuestiones. El estudiante dispo-
ne de tres interruptores; uno para cada cuestión. Diseñar un circuito con 4 salidas n0 , n1 ,
n2 y n3 de modo que para cada i, 0 < i < 3, por ni pasa corriente si solo si el estudiante
responde exactamente i de las cuestiones correctamente.
Con las mismas condiciones. Diseñar un circuito con dos salidas, a y b, de modo que ab
sea el número de cuestiones que el estudiante ha acertado en notación binaria.
134. Codificar los meses del año en expresiones binarias y diseñar un circuito cuya entrada
será alguna de estas expresiones y cuya salida será 0 si el mes correspondiente tiene 28
ó 31 dı́as, y 1 si tiene 30 dı́as.
135. Sean a2 a1 a0 y b2 b1 b0 dos números naturales escritos en notación binaria. Diseñar un cir-
cuito con 6 interruptores a2 , a1 , a0 , b2 , b1 y b0 y tres salidas A, B y C de modo que: por A
pasa corriente si y solo si a2 a1 a0 > b2 b1 b0 ; por B pasa corriente si solo si a2 a1 a0 < b2 b1 b0
y por C pasa corriente si y solo si a2 a1 a0 = b2 b1 b0 .
136. Un examen de tipo test consta de 4 preguntas. Las respuestas correctas son:
Pregunta 1: Sı́ Pregunta 2: No Pregunta 3: Sı́ Pregunta 4: Sı́
Construir una expresión booleana que analice cada examen y distinga los aprobados de
los suspensos. Se considera aprobado si al menos tres son correctas.
137. En un comité formado por cuatro personas, cada uno manifiesta su voto a través de un
interruptor. Cada persona cierra el interruptor si vota a favor y lo abre si vota en contra.
Diseñar un circuito cuya señal es 1 si y sólo si al realizar una votación en el comité el
resultado es positivo (basta mayorı́a simple).
Supongamos ahora que en caso de empate decide el voto del presidente. Diseñar el
nuevo circuito
¿Cuál es el circuito si el segundo consejero siempre vota lo contrario que el tercero?
138. Una compañı́a posee 100 acciones. Cada acción da derecho a un voto. Supongamos que
dichas acciones están en posesión de cinco personas en cantidades de 45, 25, 20 y 10,
respectivamente. Para adoptar una decisión en la compañı́a, debe ser votada a favor por
al menos 1/2 del número total de votos. Diseñar un circuito cuya señal es 1 si y sólo si la
votación es positiva.
139. Se considera un ascensor en el que se dota un dispositivo de seguridad para que no puedan
viajar niños pequeños ni pesos excesivos. Queremos que el ascensor se ponga en marcha
cuando esté vacı́o o con pesos entre 25 y 300 kilos, dotamos al ascensor de tres sensores:
A sensible a cualquier peso, B sensible a pesos mayores de 25 kilos y C sensible a pesos
superiores a 300 kilos. Diseñar el circuito más sencillo posible que describa cuándo se
mueve el ascensor.
 20 Hoja 4. Álgebra computacional. Curso 2010-11

140. La luz de un recibidor funciona desde un interruptor situado al lado de la puerta, otro
situado al lado de la escalera y otro situado en el piso de arriba. Diseñar el circuito
apropiado para su funcionamiento.
141. Una alarma para coche posee un interruptor central y dos más en las puertas delanteras.
La alarma sonará si se abre alguna de las puertas delanteras cuando el interruptor central
esté conectado. Dar la tabla de verdad y la expresión booleana. Dibujar el circuito lógico
correspondientes al funcionamiento de la alarma.
142. Una empresa quı́mica consta de una planta de producción donde se elaboran 8 productos
diferentes {P1 , P2 , . . . , P8 }. La dirección de la empresa desea abrir una nueva planta de
producción de pequeño tamaño en la que se fabriquen sólo algunos de los productos.
Considerando que:
los productos P1 y P3 deben elaborarse conjuntamente,
los productos P5 , P6 y P8 deben elaborarse conjuntamente,
los productos P2 y P7 deben elaborarse conjuntamente, y
los beneficios previstos por la elaboración de cada uno de los productos son:
Producto P1 P2 P3 P4 P5 P6 P7 P8
Beneficio 6 4 2 2 4 2 3 3
Diseñar una estrategia para obtener un beneficio de, al menos, 15 unidades, construyen-
do una función booleana que represente el problema, definida por su expresión mı́nima.
143. Una empresa quiere vender un producto a uno de entre dos posibles clientes. No quiere
que los dos queden descontentos ni tampoco que les guste a los dos, porque entonces
aquel al que no le vende el producto queda descontento. Las condiciones que ponen estos
clientes dependen del precio neto, la disponibilidad en almacén, el beneficio, el color y el
tamaño. En función de estos datos:
El cliente 1 acepta el producto si el precio neto es bueno y se dan las últimas tres
condiciones.
El cliente 2 no tiene preferencias respecto a color y tamaño. A cambio de eso quiere
que se den al menos dos de las otras tres condiciones.
Escribe la función que nos dice qué tipo de condiciones debe cumplir el producto para
ser aceptado exactamente por uno sólo de los clientes.
144. Los cuatro hijos de una familia, de 9, 8, 7 y 6 años de edad, reciben como regalo de Reyes
un ordenador. Para que puedan jugar, el padre les da las siguientes normas:
Es necesario que la suma de las edades de los que quieren jugar sea mayor que la de
los que no quieren.
En caso de que la suma sea igual, se hará lo que quiere el de mayor edad.
Es imposible que quiera jugar sólo uno de los hijos.
Es imposible que quieran jugar sólo los hijos de edades pares.
Dando un interruptor a cada hijo, diseñar el circuito más sencillo que ponga en marcha
el ordenador, cumpliendo las condiciones anteriores.
145. Un tribunal de selección para el ingreso en una facultad universitaria debe examinar los
expedientes de un gran número de candidatos. El criterio de admisión es el siguiente:
Un alumno es admitido si y solamente si el candidato alcanza la nota mı́nima
exigida en matemáticas y en un mı́nimo de dos de las siguientes disciplinas:
lengua, primer idioma extranjero y fı́sica.
Escribe una expresión booleana que efectúe la selección, simplifı́cala y construye un
circuito que efectúe automáticamente dicha selección.
 Hoja 4. Álgebra computacional. Curso 2010-11 21

146. Para efectuar una primera selección para un puesto de trabajo, la empresa Boolean S.A.
tiene en cuenta las siguientes cualidades de los candidatos: A=Tener un titulo universita-
rio, B=Saber informática, C=Saber inglés, D=Disponibilidad de viajar y E=Tener menos
de 30 años.
La comisión de recursos humanos ha decidido que para que un aspirante sea admitido,
debe cumplir:
f (A, B, C, D, E) = A + BCD + BCE + BDE + CDE + ABCDE.
Se pide: simplifica f ; explica el criterio de selección; construye un circuito que simule f .
147. La iluminación de una discoteca está constituida por la combinación de luces de tres
colores: rojo, azul y verde. El sistema además, tiene una llave general E, que activa el
funcionamiento. Las tres luces están controladas por cuatro conmutadores A, B, C y D
de forma que: La luz roja se enciende siempre que este pulsado A o si está pulsado B, no
lo está C. La luz azul se enciende cuando no está pulsado B o cuando estándolo D, no lo
está A. La luz verde se enciende si no está pulsado C, si no están pulsados ni A ni B, ó si
está pulsado D.
a) Calcular la tabla de verdad que indique el funcionamiento de todo el circuito (cuando
están encendidas cada una de las luces).
b) Dibujar el circuito simplificado para la luz verde.
148. En una casa rural con cuatro habitaciones, existe un pulsador en cada una de ellas para,
en caso de emergencias nocturnas, reclamar la presencia del personal del servicio. Diseñar
un sistema que, a partir de las lı́neas de los pulsadores que llegan de cada habitación, se
muestre en binario el número de la habitación desde la que se ha realizado la petición de
servicio. En caso de que más de una habitación solicite el servicio, se dará mayor prioridad
a la más cara, que se corresponde con un número de habitación mayor.
149. Encontrar la expresión más sencilla que detecte dentro del conjunto {0, 1, 2, . . . , 11} los
números del conjunto tales que:
A=múltiplos de dos, B=múltiplos de tres y C=ninguna de las anteriores.