Estructuras Discretas - 1er.

cuatrimestre 2025
Guı́a 6: Lógica proposicional

Semántica de los operadores lógicos

1. Definı́ la función impl :: Bool -> Bool -> Bool, que implementa la implicación lógica, tomando como
base su tabla de verdad, y utilizando pattern matching.
2. Definı́ la función impl’ :: Bool -> Bool -> Bool, que también implementa la implicación lógica, pero
en base a los operadores lógicos || y not, utilizando una única ecuación.
3. Definı́ la función xor :: Bool -> Bool -> Bool, que implementa la disyunción exclusiva, haciendo pat-
tern matching sobre los cuatro casos posibles.

4. Definı́ la función xor’ :: Bool -> Bool -> Bool, que también implementa la disyunción exclusiva, pero
en base a los operadores lógicos ||, not y &&, utilizando una única ecuación.
5. Evaluá las siguientes fórmulas proposicionales, suponiendo que la variable p tiene valor “verdadero”, q
“falso”, y r “falso”. Verificá tus resultados evaluando las expresiones en Haskell.

a) p ⇒ (q ≡ r)
b) ¬p ≡ (¬q ∨ (q ∨ r))
c) (q ⇒ (p ≡ ¬r)) ⇒ ((p ∧ q) ⇒ (r ≡ r))
d ) ¬(p ∨ ¬q) ⇒ (¬(r ≡ (p ∧ q)) ⇒ ¬(p ∨ ¬q))

6. Representá con una fórmula proposicional las siguientes frases coloquiales, usando las siguientes variables
proposicionales:

p : “a < b”
q : “b < c”
r : “a < c”

a) a < b < c
b) Si a < b entonces no es el caso que (a ≥ c)
c) (a ≥ b y b < c) o (a ≥ c)
d ) No es el caso que (a < b y a < c)
e) (No es el caso que (a < b y (a < c ó b < c))) ó (a ≥ b y a < c)

7. Escribı́ una fórmula proposicional para cada una de las siguientes frases, utilizando una variable proposi-
cional para cada sentencia atómica, aclarando siempre el significado escogido para cada variable. A veces
es conveniente reescribir las frases para hacer más claro su sentido.
Por ejemplo, la frase

Hoy es martes o jueves

puede pensarse como dos oraciones unidas por una disyunción, pudiendo reescribirse como:

Hoy es martes u hoy es jueves

Entonces podemos formalizarla con la fórmula p ∨ q, utilizando p para la primer sentencia y q para la segunda, es
decir, definiendo:
.
p = hoy es martes
.
q = hoy es jueves

1
 En lo posible utilizá un mismo sı́mbolo de proposición para la misma sentencia atómica a lo largo de todo el
ejercicio, para poder comparar las fórmulas.

a) Hoy es martes y hay sol.

b) Hoy es martes y no hay sol.
c) Hoy no es ni miércoles ni viernes.
d ) Mañana, lloverá o no lloverá.
e) Mañana será jueves y no será jueves.
f ) Hoy es lunes, pero tengo clases de Estructuras Discretas.
g) Si hace frı́o y llueve, puedo concluir que hace frı́o.
h) Yo no voy de vacaciones y Juan y Pedro tampoco.
i ) Juan vendrá a clase, y seguro que vendrán también Marı́a o Pedro.
j ) Si no me gusta la sopa ni la ensalada, no me conviene pedir el menú completo.
k ) No es verdad que si tienes menos de 16 años y consentimiento paterno te puedas casar.

Validez y satisfactibilidad

8. Decidı́ si cada una de las siguientes fórmulas proposicionales es válida o no. En caso que una fórmula no
sea válida, decidı́ si es satisfactible o no. En todos los casos justificá con una tabla de verdad, un ejemplo
o un contraejemplo, según corresponda.

a) p
b) p ≡ p
c) p ≡ p ≡ p
d) p ⇒ q ≡ q ⇒ p
e) p ∨ q ⇒ p
f) p∧q ⇒ p
g) p ⇒ q ∧ p
h) p ⇒ q ∨ p
i) p ⇒ q
j ) p ⇒ (q ⇒ p)
k ) p ≡ p ≡ True
l ) True ∨ p
m) True ∧ p
n) False ∨ p
ñ) False ∧ p

Ayuda: En las tablas de verdad, las constantes True y False, siempre tienen el valor “verdadero” y “falso”
respectivamente.

Análisis semántico de razonamientos

9. Formalizá los siguientes razonamientos en la lógica proposicional. Decidı́ si son correctos o no, justificando
con una tabla de verdad.

a) Soy fea, sucia y mala. Por lo tanto soy mala.

b) Soy fea, sucia o mala. Por lo tanto soy mala.

2
 c) El cı́rculo está pintado de rojo, azul o amarillo. Por lo tanto está pintado de amarillo.
d ) Llueve. Por lo tanto llueve y hace frı́o.
e) Llueve. Por lo tanto llueve o hace frı́o.
f ) Si gano la loterı́a, pago un asado. Gané la loterı́a. Por lo tanto, pagaré el asado.
g) Si gano la loterı́a, pago un asado. Pagué el asado. Por lo tanto, gané la loterı́a.
h) Si gano la loterı́a, pago un asado. No gané la loterı́a. Por lo tanto, no pagaré el asado.
i ) Si gano la loterı́a, pago un asado. No pagué el asado. Por lo tanto, no gané la loterı́a.

10. Modelá los siguientes razonamientos y demostrá que son correctos.

a) Los martes y viernes tengo Matemática y Lógica. Hoy es martes; por lo tanto tengo Matemática y
Lógica.
b) Si el gobernador quiere mejorar su imagen entonces mejora su polı́tica social. El gobernador no mejora
su polı́tica social por lo tanto no quiere mejorar su imagen.
c) Si el gobernador quiere mejorar su imagen, o mejora su polı́tica social o gasta más en publicidad. El
gobernador no mejora su polı́tica social. Luego, si el gobernador quiere mejorar su imagen, entonces
deberá gastar más en publicidad.

Cálculo proposicional

11. Descubrı́ qué axioma de la equivalencia y la negación se puede utilizar para justificar cada uno de
los siguientes pasos de demostración:

a) q ≡ T rue
≡{ }
q

b) ((q ≡ ¬r) ≡ p ∨ q)
≡{ }
(q ≡ (¬r ≡ p ∨ q))

c) F alse ≡ p ∧ ¬s ≡ p ∧ ¬s
≡{ }
F alse

d) ¬q ≡ p
≡{ }
¬(q ≡ p)

e) ¬r
≡{ }
¬q ≡ ¬(r ≡ ¬q)

12. Demostrá que las siguientes fórmulas son teoremas, es decir, son fórmulas válidas, utilizando únicamen-
te las reglas (axiomas y teoremas) de la equivalencia y la negación. Realizá la demostración
justificando cada paso.
Por ejemplo, demostramos (p ≡ ¬p) ≡ F alse:

(p ≡ ¬p) ≡ False
≡ { Conmutatividad del equivalente }
(¬p ≡ p) ≡ False
≡ { Asociatividad del equivalente }
¬p ≡ (p ≡ False)
≡ { Equivalencia y negación }
True

3
 a) ¬False ≡ True
b) r ≡ s ∧ t ≡ s ∧ t ≡ r
c) ¬p ≡ q ≡ p ≡ ¬q

13. Decidı́ si son válidas o no las siguientes fórmulas. Justificá apropiadamente con una demostración o un contra-
ejemplo. Solo podés usar las reglas de la equivalencia y la negación.

a) p ≡ p ≡ p ≡ True
b) (p ≡ q) ≡ (¬p ≡ ¬q)
c) ¬p ≡ False

14. Descubrı́ qué axioma de la disyunción se puede utilizar para justificar cada uno de los siguientes pasos de
demostración:

a) r ∨ (p ∨ (p ⇒ r))
≡{ }
(r ∨ p) ∨ (p ⇒ s)

b) 3x ⩽ 2y
≡{ }
(3x ⩽ 2y) ∨ (3x ⩽ 2y)

c) T rue
≡{ }
T rue ∨ ¬T rue

15. Demostrá los siguientes teoremas de la disyunción utilizando únicamente las reglas de la equivalencia y la
negación y los axiomas de la disyunción. Justificá cada cada paso.

a) Elemento absorbente de la disyunción: p ∨ True ≡ True

Ayuda: Podés comenzar la demostración de la siguiente manera

p ∨ True ≡ True
≡ { Reflexividad de la equivalencia }
p ∨ (p ≡ p) ≡ True
≡ { ... }

b) Elemento neutro de la disyunción: p ∨ False ≡ p

Ayuda: Podés comenzar la demostración de la siguiente manera

p ∨ False ≡ p
≡ { Definición de False }
p ∨ ¬True ≡ p
≡ { Reflexividad de la equivalencia }
p ∨ ¬(p ≡ p) ≡ p
≡ { ... }

c) p ∨ q ≡ p ∨ ¬q ≡ p
Ayuda: Podés utilizar la distributividad del ∨ con el ≡.

16. Demostrá los siguientes teoremas de la conjunción utilizando únicamente las reglas de la equivalencia, la
negación, la disyunción y el único axioma de la conjunción.

a) Idempotencia de la conjunción: p ∧ p ≡ p
b) Elemento absorbente de la conjunción: p ∧ False ≡ False
c) Elemento neutro de la conjunción: p ∧ True ≡ p

17. Decidı́ si es válida la siguiente fórmula. En otras palablas ¿distribuye la conjunción con la equivalencia? Justificá.

p ∧ (q ≡ r) ≡ (p ∧ q) ≡ (p ∧ r)

4
 18. Demostrá los siguientes teoremas. En ningún caso podés utilizar en la demostración la propiedad que se está
demostrando.

a) Ley de absorción: p ∧ (p ∨ q) ≡ p
b) Ley de absorción (bis): p ∨ (p ∧ q) ≡ p
c) Distributividad de la disyunción con la conjunción: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
d ) Doble implicación: (p ⇒ q) ∧ (q ⇒ p) ≡ p ≡ q.
e) De Morgan para la disyunción: ¬(p ∨ q) ≡ ¬p ∧ ¬q
f ) De Morgan para la conjunción: ¬(p ∧ q) ≡ ¬p ∨ ¬p
g) Caracterización de implicación: p ⇒ q ≡ ¬p ∨ q
h) Absurdo: p ⇒ False ≡ ¬p.
i) Modus ponendo ponens (con equivalencia): (p ⇒ q) ∧ p ≡ p ∧ q.
j ) Modus tollendo tollens (con equivalencia): (p ⇒ q) ∧ ¬q ≡ ¬p ∧ ¬q.

19. Usando cálculo proposicional, demostrá la validez de cada uno de los razonamientos formalizados en el ejercicio
10.

20. El modus ponendo ponens es un teorema de la lógica proposicional que se puede caracterizar con la fórmula
(p ⇒ q) ∧ p ⇒ q. Escribı́ dos razonamientos que sigan esta estructura.

21. El modus tollendo tollens es un teorema de la lógica proposicional que se puede caracterizar con la fórmula
(p ⇒ q) ∧ ¬q ⇒ ¬p. Escribı́ dos razonamientos que sigan esta estructura.

22. Un poco mas difı́cil. ¿Es correcto el siguiente razonamiento? Da un contraejemplo, o hacé una demostración
usando el cálculo proposicional según corresponda.

Si la ciudadanı́a romana hubiera sido una garantı́a de los derechos civiles, los romanos habrı́an gozado de libertad
religiosa. Si los romanos hubieran gozado de libertad religiosa, entonces no se habrı́a perseguido a los primeros
cristianos. Pero los primeros cristianos fueron perseguidos. Por consiguiente, la ciudadanı́a romana no puede
haber sido una garantı́a de los derechos civiles.

Diseño de circuitos

23. Sintentizá un circuito que implemente la siguiente tabla de verdad:

a b c fabc
0 0 0 1
1 0 0 0
0 1 0 0
1 1 0 1
0 0 1 1
1 0 1 1
0 1 1 0
1 1 1 1

¿Podés encontrar una especificación funcional mas simple?

24. Un multiplexor es el equivalente en hardware a una expresión if ... then ... else de un lenguaje de
programación. Toma tres entradas: una entrada de control a, y dos entradas de datos x e y. Tiene una
sola salida: si a es 0, entonces la salida es el valor de x, y en caso contrario, la salida es el valor de y.

a) Escribı́ la tabla de verdad que especifica el comportamiento de un multiplexor.

b) Usá la tabla para sintetizar un circuito, obteniendo una especificación funcional.

5
25. La siguiente imagen representa un circuito optimizado que implementa un multiplexor :

a) Escribı́ una especificación funcional de este multiplexor a partir del diagrama.

b) Demostrá que esta especificación es equivalente a la que encontraste en el ejercicio 24b, usando cálculo
proposicional.