Ejercicio Velleman 1.5.7a

Question

He estado intentando resolver el ejercicio 7(a) de "Cómo demostrarlo" de Velleman y no lo he conseguido. Se pide la verificación de la siguiente equivalencia:

$$ (P \to Q) \land (Q \to R) = (P \to R) \land ((P \leftrightarrow Q) \lor (R \leftrightarrow Q)) $$

Revisando la web en busca de ayuda, encontré una pregunta planteada por el usuario "yamad", que a pesar de su preocupación por un paso más en la resolución, llegó a esta posible forma reducida:

$$(\lnot P \lor Q) \land (\lnot Q \lor R) \land (\lnot P \lor R)$$

El problema es que no he podido llegar a este paso ni a ninguna otra forma simplificada. Agradecería que alguien me diera una pista.

Answer 1

Tomemos la RHS y simplifiquémosla un poco:

$$ (P \to R) \land ((P \leftrightarrow Q) \color{red}{\lor} (R \leftrightarrow Q)) \tag{1} $$ Distribuir $(P \to R)$ en el paréntesis: $$(P \to R) \land (P \leftrightarrow Q) \quad \color{red}{\lor} \quad (P \to R) \land (R \leftrightarrow Q) \tag{2} $$ Utilice la definición de $A \leftrightarrow B \vdash (A \to B) \land (B \to A):$ $$ \color{blue}{(P \to R)} \land (P \to Q) \land \color{blue}{(Q \to P)} \quad \color{red}{\lor} \quad \color{green}{(P \to R)} \land \color{green}{(R \to Q)} \land (Q \to R) \tag{3} $$ En este punto tenemos que asumir el resultado $(A \to B) \land (B \to C) \vdash (A \to C):$ $$ (P \to Q) \land \color{blue}{(Q \to R)} \quad \color{red}{\lor} \quad \color{green}{(P \to Q)} \land (Q \to R) \tag{4} $$ Sabemos que $A \lor A \vdash A:$ $$ (P \to Q) \land (Q \to R) \tag{5} $$

---

Ahora tenemos que demostrar que $$(A \to B) \land (B \to C) \vdash (A \to C)$$ lo que podríamos verificar usando una tabla de verdad. Pero la prueba correcta necesita utilizar los axiomas y teoremas de su sistema de pruebas.

Answer 2

La forma más fácil de verificar la identidad es "volarlo con una tabla de verdad de ocho filas" como dijo ncmathsadist.

Alternativamente, puedes razonar esto de manera informal. Si te tomas el tiempo, puedes formalizarlo todo a continuación:

Supongamos que $(P \rightarrow Q) \wedge (Q \rightarrow R)$ . Entonces tienes $P \rightarrow R$ . Supongamos ahora que $\neg((P \leftrightarrow Q) \vee (Q \leftrightarrow R))$ . Entonces (sin pérdida de generalidad) $P = T$ , $Q = F$ y $R = T$ . Pero entonces $(P \rightarrow Q) \wedge (Q \rightarrow R)$ es falso. Puedes comprobar los otros casos.

Supongamos ahora que $(P \rightarrow R) \wedge ((P \leftrightarrow Q) \vee (Q \leftrightarrow R))$ . Así que suponga que tiene $(P \rightarrow R)$ y $P \equiv Q$ . Entonces usted tiene automáticamente $P \rightarrow Q$ . También tiene $Q \rightarrow P$ y $P \rightarrow Q$ . Así que tienes $Q \rightarrow R$ . Así que tienes $(P \rightarrow Q) \wedge (Q \rightarrow R)$ . El otro caso se hace de forma similar.