Encontrar la forma mínima -- Velleman ejercicio 1.5.7a

Question

Estoy estudiando por mi cuenta la obra de Velleman "How to Prove It", y estoy intentando resolver el ejercicio 7, parte a de la sección 1.5. El problema consiste en demostrar que

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

Convirtiendo el lado derecho en las sentencias AND/OR equivalentes pude simplificar la expresión a

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

que es equivalente al lado izquierdo (confirmado mediante tablas de verdad, diagramas de Venn y Wolfram Alpha), pero tengo problemas para mostrarlo analíticamente. Está claro que la primera parte de esta afirmación es idéntica al lado izquierdo. Pero no puedo averiguar los pasos analíticos para demostrar que $\lnot P \lor R$ anula la declaración. He intentado distribuir las declaraciones entre sí por completo, pero sigo terminando de nuevo en la expresión anterior.

Al convertir de nuevo a sentencias condicionales, el hecho de que $\lnot P \lor R$ es prescindible me resulta intuitivo. Es decir, tiene sentido que $P \to Q$ y $Q \to R$ ya implica que $P \to R$ . Sin embargo, quiero poder mostrarlo analíticamente basándome en las leyes booleanas y ahí me he dado contra un muro. Estoy seguro de que me estoy perdiendo algo simple, pero me está volviendo loco. ¿Alguna pista?

Answer 1

Para ampliar ligeramente la sugerencia de pedja: El quid de la cuestión es mostrar primero $$\left((\lnot P \lor Q) \land (\lnot Q \lor R)\right) \rightarrow (\lnot P \lor R)$$ y luego que $$\left((A\land B)\land (A\rightarrow B)\right) \rightarrow A.$$

Anexo : También se puede observar que $A\land(A\rightarrow B) = A\land B$ . Así, si $A\rightarrow B$ , $A = A\land B$ .

Answer 2

He aquí una solución de cálculo completa, en la que utilizaremos varias veces ese $\;p \lor q \leftrightarrow q\;$ es una forma alternativa de escribir $\;p \rightarrow q\;$ . También utilizaremos el hecho de que $\;\leftrightarrow\;$ es asociativo, por lo que no necesitamos escribir paréntesis en, por ejemplo, la "regla de oro": $$ p \;\leftrightarrow\; q \;\leftrightarrow\; p \land q \;\leftrightarrow\; p \lor q $$

Empezando por el lado más complejo, calculamos \begin{align} & (P \to R) \;\land\; \big((P \leftrightarrow Q) \lor (R \leftrightarrow Q)\big) \\ = & \;\;\;\;\;\text{"$\;\lor\;$ distributes over $\;\leftrightarrow\;$, three times"} \\ & (P \to R) \;\land\; (P \lor R \;\leftrightarrow\; P \lor Q \;\leftrightarrow\; Q \lor R \;\leftrightarrow\; Q \lor Q) \\ = & \;\;\;\;\;\text{"use $\;P \rightarrow R\;$ rewritten as $\;P \lor R \leftrightarrow R\;$ in second part; simplify $\;Q \lor Q\;$"} \\ & (P \to R) \;\land\; (R \;\leftrightarrow\; P \lor Q \;\leftrightarrow\; Q \lor R \;\leftrightarrow\; Q) \\ = & \;\;\;\;\;\text{"reorder equivalents by symmetry of $\;\leftrightarrow\;$ -- this lets us introduce $\;\rightarrow\;$"} \\ & (P \to R) \;\land\; \big((P \lor Q \;\leftrightarrow\; Q) \;\leftrightarrow\; (Q \lor R \;\leftrightarrow\; R)\big) \\ = & \;\;\;\;\;\text{"rewrite $\;p \lor q \leftrightarrow q\;$ to $\;p \rightarrow q\;$, twice"} \\ & (P \to R) \;\land\; \big((P \rightarrow Q) \;\leftrightarrow\; (Q \rightarrow R)\big) \\ = & \;\;\;\;\;\text{"the golden rule -- to introduce our goal $\;(P \rightarrow Q) \land (Q \rightarrow R)\;$"} \\ & (P \to R) \;\land\; \big((P \rightarrow Q) \land (Q \rightarrow R) \;\leftrightarrow\; (P \rightarrow Q) \lor (Q \rightarrow R)\big) \\ = & \;\;\;\;\;\text{"$\;(P \rightarrow Q) \lor (Q \rightarrow R)\;$ is a tautology, see below"} \\ & (P \to R) \;\land\; (P \rightarrow Q) \;\land\; (Q \rightarrow R) \\ = & \;\;\;\;\;\text{"the leftmost conjunct is implied by the rest, by transitivity of $\;\rightarrow\;$"} \\ & (P \rightarrow Q) \;\land\; (Q \rightarrow R) \\ \end{align}

Arriba utilizamos \begin{align} & (P \rightarrow Q) \lor (Q \rightarrow R) \\ = & \;\;\;\;\;\text{"write $\;p \rightarrow q\;$ as $\;\lnot p \lor q \;$, twice"} \\ & \lnot P \lor Q \lor \lnot Q \lor R \\ = & \;\;\;\;\;\text{"excluded middle"} \\ & \lnot P \lor \text{true} \lor R \\ = & \;\;\;\;\;\text{"excluded middle; simplify"} \\ & \text{true} \\ \end{align}

Esto completa la prueba.

Answer 3

Sugerencia :

$(P \rightarrow Q) \land (Q \rightarrow R) \rightarrow (P \rightarrow R)$