Mostrando $(P\to Q)\land (Q\to R)\equiv (P\to R)\land[(P\leftrightarrow Q)\lor (R\leftrightarrow Q)]$ {sin tabla de verdad}

Question

Problema: Mostrar $(P\to Q)\land (Q\to R)\equiv (P\to R)\land[(P\leftrightarrow Q)\lor (R\leftrightarrow Q)]$

---

Fuente: Como se observó en el post original, este problema es de Daniel J. Velleman del libro Cómo demostrarlo. El ejercicio puede ser encontrado como problema 7 (a) en la página 54 (segunda edición). Tengo una copia de este libro, y vi que algunos de los ejercicios que tienen soluciones en el libro. El ejercicio directamente antes de que éste tenía la solución, "hacer una tabla de verdad o la razón de la siguiente manera: [...]". Esto me hace pensar que el autor tenía una tabla de verdad de la solución en mente para este ejercicio, como puramente prueba directa, mediante el uso de una cadena lógica de equivalencias ha demostrado ser extremadamente difícil. Estoy muy interesado en la obtención de una solución que utiliza una cadena lógica de equivalencias similares a mi respuesta a este problema. He pasado varias horas trabajando en este problema ahora, pero no he tenido éxito en todo ... me parece no puede "tirar de la mano derecha de la mano izquierda", ya que este parece ser el enfoque más natural. Para cualquier persona interesada, he presentado una tabla de verdad, sin la pelusa de debajo.

---

Tabla de verdad de la solución:

$$ \boxed{ \begin{array}{c|c|c|c} P & Q & R & (P\to Q)\land (Q\to R) & (P\to R)\land[(P\leftrightarrow Q)\lor (R\leftrightarrow Q)] \\ \hline T & T & T & T & T \\ T & T & F & F & F \\ T & F & T & F & F \\ T & F & F & F & F \\ F & T & T & T & T \\ F & T & F & F & F \\ F & F & T & T & T \\ F & F & F & T & T \end{array}} $$

---

Cadena de equivalencias de la prueba: parece que el principal problema es la "persuasión" la mano derecha de la mano izquierda. Por ejemplo, usando la distributividad, puedo ver que de alguna manera $(P\to Q)\land(Q\to R)$ es equivalente a $$ [(P\I)\de la tierra(P\Q)\de la tierra(Q\a-P)]\lor[(P\I)\de la tierra(R\Q)\de la tierra(Q\a R)].\la etiqueta{1} $$ He intentado numerosas veces tratando de manipular a la izquierda en la expresión dada en $(1)$, pero no he conseguido hasta el momento, todo lo que es un enorme lío. Quizás hay algo de estrategia en el uso de equivalencias (en términos de facilidad de manipulación); por ejemplo, en caso de un uso $$ P\leftrightarrow Q\equiv (P\de la tierra Q)\lor(\neg P\de la tierra\neg P) $$ o $$ P\leftrightarrow Q\equiv (P\Q)\de la tierra (Q\P) $$

Answer 1

Existen varios algoritmos para convertir clásica proposicional oraciones en forma normal. Yo voy a pretender ser tan tonto como un equipo y convertir las dos frases que en su forma normal disyuntiva en una forma sistemática.

\begin{align} & {(P \to R) \wedge [(P \leftrightarrow Q) \vee (R \leftrightarrow Q)]}\\ & = (\neg P \vee R) \wedge [(P \wedge Q) \vee (\neg P \wedge \neg Q) \vee (R \wedge Q) \vee (\neg R \wedge \neg Q)] \\ & = [(\neg P \vee R) \wedge P \wedge Q] \vee [(\neg P \vee R) \wedge \neg P \wedge \neg Q] \vee \\ & \phantom{{} = {}} [(\neg P \vee R) \wedge R \wedge Q] \vee [(\neg P \vee R) \wedge \neg R \wedge \neg Q] \\ & = [P \wedge Q \wedge R] \vee [(\neg P \wedge \neg Q) \vee (\neg P \wedge \neg Q \wedge R)] \\ & \phantom{{} = {}} \vee [(\neg P \wedge Q \wedge R) \vee (Q \wedge R)] \vee [\neg P \wedge \neg Q \wedge \neg R] \\ & = (P \wedge Q \wedge R) \vee [(\neg P \wedge \neg Q \wedge \neg R) \vee (\neg P \wedge \neg Q \wedge R)] \vee\\ & \phantom{{}={}} [(\neg P \wedge Q \wedge R) \vee (P \wedge Q \wedge R)] \vee [\neg P \wedge \neg Q \wedge \neg R] \\ & = (P \wedge Q \wedge R) \vee (\neg P \wedge \neg Q \wedge R) \vee (\neg P \wedge \neg Q \wedge \neg R) \vee (\neg P \wedge Q \wedge R). \end{align} \begin{align} & (P \to Q) \land (Q \to R) \\ & = (\lnot P \lor Q) \land (\lnot Q \lor R) \\ & = [\lnot P \land \lnot Q] \lor [\lnot P \land R] \lor [Q \land R] \\ & = [(\lnot P \land \lnot Q \land R) \lor (\lnot P \land \lnot Q \land \lnot R)] \lor [(\lnot P \land Q \land R) \lor (\lnot P \land \lnot Q \land R)] \lor \\ & \phantom{{}={}} [(P \land Q \land R) \lor (\lnot P \land Q \land R)] \\ & = (\lnot P \land \lnot Q \land R) \lor (\lnot P \land \lnot Q \land \lnot R) \lor (\lnot P \land Q \land R) \lor (P \land Q \land R). \end{align}

Ahora usted debería ver cómo el método general de las obras. Si desea rehacer sin pretender ser tan tonto como un equipo, algunos de los pasos pueden ser omitidos. De hecho, la forma final no tiene que ser ampliado en su totalidad. Usted puede tratar de que ambas expresiones se parecen a este:

$$ (Q \de la tierra R) \vee (\lnot P \de la tierra \lnot Q). $$

Answer 2

Es bastante accesible si se puede dividir de acuerdo a si $Q$ es verdadera o falsa.

Para la concisión, la llamada de las dos fórmulas ser$\Phi$$\Psi$. Podemos mostrar que cada uno de ellos es equivalente a $(R\land Q) \lor (\neg P\land \neg Q)$, y por lo tanto son equivalentes entre sí.

Más precisamente, voy a demostrar que $\Xi\land Q \equiv \neg R\land Q$$\Xi\land \neg Q\equiv \neg P\land \neg Q$$\Xi\in\{\Phi,\Psi\}$. Entonces tenemos $$ \begin{align} \Xi \equiv{}& \Xi\land (Q\lor \neg Q) \\ \equiv{}& (\Xi\land Q) \lor (\Xi\land \neg Q) \\ \equiv{}& (R\land Q) \lor (\neg P\land \neg Q) \end{align} $$

Por lo tanto, hay cuatro cálculos a hacer: $$ \begin{align} \Phi\land Q \equiv{}& (P\to Q)\land (Q\to R)\land Q \\ \equiv{}& (P\to Q)\land Q \land R \\ \equiv{}& Q\land R \end{align} $$

$$ \begin{align} \Phi\land \neg Q \equiv{}& (P\to Q)\land (Q\to R)\land \neg Q \\ \equiv{}& (P\to Q)\land (\neg Q\lor R)\land \neg Q \\ \equiv{}& (P\to Q)\land \neg Q \\ \equiv{}& (\neg Q\to \neg P)\land \neg Q\\ \equiv{}& \neg P \land \neg Q \end{align} $$

$$ \begin{align} \Psi\land Q \equiv{}& (P\to R)\land (P\leftrightarrow Q \lor R\leftrightarrow Q) \land Q \\ \equiv{}& (P\to R)\land ((P\leftrightarrow Q \land Q) \lor (R\leftrightarrow Q)\land Q)) \\ \equiv{}& (P\to R)\land ((P\land Q) \lor (R\land Q)) \\ \equiv{}& (P\to R)\land (P\lor R) \land Q\\ \equiv{}& (\neg P \lor R)\land (P\lor R) \land Q \\ \equiv{}& ((\neg P \land P) \lor R) \land Q \\ \equiv{}& (\bot \lor R) \land Q \\ \equiv{}& R \land Q \end{align} $$

$$ \begin{align} \Psi\land \neg Q \equiv{}& (P\to R)\land (P\leftrightarrow Q \lor R\leftrightarrow Q) \land \neg Q \\ \equiv{}& (P\to R)\land ((P\leftrightarrow Q \land \neg Q) \lor (R\leftrightarrow Q)\land \neg Q)) \\ \equiv{}& (P\to R)\land ((\neg P\land \neg Q) \lor (\neg R\land \neg Q)) \\ \equiv{}& (P\to R)\land (\neg P\lor \neg R) \land \neg Q\\ \equiv{}& (\neg P \lor R)\land (\neg P\lor \neg R) \land \neg Q \\ \equiv{}& (\neg P \lor (R \land \neg R)) \land \neg Q \\ \equiv{}& (\neg P \lor \bot) \land \neg Q \\ \equiv{}& \neg P \land \neg Q \end{align} $$

Aquí he utilizado la distribución de un montón de veces, así como de las reglas, tales como

• $(A\to B)\land A \equiv A\land B$
• $(A\to B)\land B \equiv B$
• $(A\lor B)\land A \equiv A$
• $(A\leftrightarrow B)\land A\equiv A\land B$

Answer 3

Si desea más intuitivo prueba de la dirección hacia adelante (la más difícil) que muestra la esencia, probablemente lo mejor es mostrar primero la regla de que $\vdash (Q \rightarrow P) \vee (R \rightarrow Q)$. Esta desconexión tiene porque

• $Q \rightarrow \bot$ implica $Q \rightarrow P$ ($Q \rightarrow \_$ se considera como una función conserva vinculación, y $\bot \vdash P$),
• $Q$ conlleva $R \rightarrow Q$,
• $\vdash (Q \rightarrow \bot) \vee Q$ (la ley de medio excluido de la lógica clásica).

Dada la regla, es inmediato que

$(P \rightarrow Q) \wedge (Q \rightarrow R) \vdash ((P \rightarrow Q) \wedge (Q \rightarrow R)) \wedge ((Q \rightarrow P) \vee (R \rightarrow Q))$.

De ello se deduce simplemente de la distributividad de que el lado derecho (y por lo tanto el lado izquierdo) de esta vinculación implica $(P \leftrightarrow Q) \vee (R \leftrightarrow Q)$. Y es fácil demostrar que

$(P \rightarrow Q) \wedge (Q \rightarrow R) \vdash P \rightarrow R$.

Desde una conjunción que se suponía que si (y sólo si) ambos conjuntos se suponía, ya está hecho (con la dirección de avance).

Answer 4

Aquí es una alternativa de la cadena de equivalencias de la prueba, que utiliza algunas de las leyes de la lógica, que no puede ser conocido.

$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}} \newcommand{\equiv}{\leftrightarrow} \newcommand {\, a continuación,} {\,} \newcommand{\followsfrom}{\obtiene} \newcommand{\verdadero}{\text{true}} \newcommand{\false}{\text{false}} $Below, I will use the fact that $\;\equiv\;$ is associative; and to reduce the number of parentheses, I will just write, e.g., $\;\phi \equiv \psi \equiv \chi\;$. Also, I will use the fact that $\;\lor\;$ distributes over $\;\equiv\;$.

Comenzamos en la mayoría de los complejos de lado, y reescribir $\;(P \equiv Q) \;\lor\; (R \equiv Q)\;$ hacia el lado izquierdo, bajo el supuesto de que $\;P \then R\;$:

$$\calc (P \equiv Q) \;\lor\ R \equiv Q) \op=\sugerencia{$\;\lor\;$ distribuye más de $\;\equiv\;$} P \lor (R \equiv Q) \;\equiv\; Q \lor (R \equiv Q) \op=\sugerencia{$\;\lor\;$ distribuye más de $\;\equiv\;$, dos veces} P \lor R \;\equiv\; P \lor Q \;\equiv\; Q \lor R \;\equiv\; Q \lor P \op=\sugerencias{suposición $\;P \then R\;$$\;P \lor R \equiv R\;$;} \sugerencia{simplificar $\;Q \lor Q\;$; reordenar las equivalencias} P \lor Q \;\equiv\; Q \;\equiv\; Q \lor R \;\equiv\; R \op=\sugerencia{write $\;\phi \lor \chi \equiv \chi\;$$\;\phi \then \chi\;$, dos veces} (P \entonces Q) \;\equiv\; (Q \, a continuación, R) \op= \sugerencias{write $\;\phi \equiv \psi\;$$\;(\phi \land \psi) \lor (\lnot\phi \land \lnot\psi)\;$} \sugerencia{-- introducir nuestra meta $\;(P \then Q) \land (Q \then R)\;$} \big((P \entonces Q) \de la tierra (Q \, a continuación, R)\big) \;\lor\; \big(\lnot (P \entonces Q) \de la tierra \lnot (Q \, a continuación, R)\big) \op=\sugerencia{write $\;\phi \then \chi\;$$\;\lnot \phi \lor \chi\;$, y DeMorgan, dos veces} \big((P \entonces Q) \de la tierra (Q \, a continuación, R)\big) \;\lor\; (P \de la tierra \lnot Q \de la tierra Q \de la tierra \lnot R) \op=\sugerencia{contradicción: $\;\lnot Q \land Q \;\equiv\; \false\;$; simplificar} (P \entonces Q) \;\de la tierra\; (Q \, a continuación, R) \endcalc$$

Ahora podemos terminar la prueba:

$$\calc (P \, a continuación, R) \;\de la tierra\; \big((P \equiv Q) \lor (R \equiv Q)\big) \op=\sugerencia{el cálculo anterior} (P \, a continuación, R) \;\de la tierra\; (P \entonces Q) \;\de la tierra\; (Q \, a continuación, R) \op=\sugerencia{$\;\then\;$ es transitiva} (P \entonces Q) \;\de la tierra\; (Q \, a continuación, R) \endcalc$$