¿Cuál de las siguientes es una tautología?

Question

¿Cuál de las siguientes lógicas es una tautología?

• $S1: (P (Q R)) (P (Q ¬R)) P Q$
• $S2: (P Q) ((Q R) S) (P R) S$

---

¿Cómo resolver sin usar la tabla de verdad?

Answer 1

En primer lugar, permítanme añadir algunos paréntesis desambiguadores donde sospecho que tienen que ir (corríjanme si me equivoco):

$S1: ((P \rightarrow (Q \lor R)) \land (P \rightarrow (Q \lor \neg R))) \rightarrow (P \rightarrow Q)$ $S2: ((P \rightarrow Q) \land ((Q \land R) \rightarrow S)) \rightarrow ((P \land R) \rightarrow S)$

La primera es bastante fácil de demostrar que es una tautología:

$((P \rightarrow (Q \lor R)) \land (P \rightarrow (Q \lor \neg R))) \rightarrow (P \rightarrow Q) \Leftrightarrow$ (Distribución $\rightarrow$ en $\land$ )

$(P \rightarrow ((Q \lor R) \land (Q \lor \neg R))) \rightarrow (P \rightarrow Q) \Leftrightarrow$ (Adyacencia)

$(P \rightarrow Q) \rightarrow (P \rightarrow Q) \Leftrightarrow$

$\top$

La segunda es un poco más difícil:

$((P \rightarrow Q) \land ((Q \land R) \rightarrow S)) \rightarrow ((P \land R) \rightarrow S) \Leftrightarrow$ (Implicación)

$\neg ((P \rightarrow Q) \land ((Q \land R) \rightarrow S)) \lor (\neg (P \land R) \lor S) \Leftrightarrow$ (DeMorgan)

$\neg (P \rightarrow Q) \lor \neg (Q \land R) \rightarrow S) \lor (\neg P \lor \neg R \lor S) \Leftrightarrow$ (Implicación)

$(P \land \neg Q) \lor (Q \land R \land \neg S) \lor \neg P \lor \neg R \lor S \Leftrightarrow$ (DeMorgan)

$(P \land \neg Q) \lor (Q \land \neg(\neg R \lor S)) \lor \neg P \lor \neg R \lor S \Leftrightarrow$ (Reducción)

$\neg Q \lor Q \lor \neg P \lor \neg R \lor S \Leftrightarrow$

$\top \lor \neg P \lor \neg R \lor S \Leftrightarrow$

$\top$

Answer 2

Pistas:

$S1$ : Esto será una tautología si, dado $P \to (Q \lor R)$ , $P \to (Q \lor \lnot R)$ y $P$ se puede concluir que $Q$ . Ahora, bajo cualquier asignación, uno de $R$ y $\lnot R$ es falso, por lo que uno de $P \to (Q \lor R)$ y $P \to (Q \lor \lnot R)$ equivale a $P \to Q$ . Como se le da $P$ , usted tiene $Q$ .

$S2$ : Razona de forma similar utilizando el hecho de que si $P \to Q$ entonces $P \land R \to Q \land R$ .