Prueba $[(p\leftrightarrow q)\land(q\leftrightarrow r)]\to(p\leftrightarrow r)$ es una tautología sin una tabla de verdad

Question

Me encontré con el siguiente problema en un libro:

Mostrar que si $p, q$, e $r$ está compuesto de proposiciones tal que $p$ $q$ son lógicamente equivalentes y $q$ $r$ son lógicamente equivalentes, a continuación, $p$ $r$ son lógicamente equivalentes.

El libro de la solución, sin duda, hace sentido:

Decir que $p$ $q$ son lógicamente equivalentes, es decir que las tablas de verdad para $p$ $q$ son idénticas; del mismo modo, decir que el $q$ $r$ son lógicamente equivalentes, es decir que las tablas de verdad para $q$ $r$ son idénticas. Claramente si las tablas de verdad para $p$ $q$ son idénticas, y las tablas de verdad para $q$ $r$ son idénticos, entonces las tablas de verdad para $p$ $r$ son idénticas. Por lo tanto, $p$ $r$ son lógicamente equivalentes.

Me decidí a "traducir simbólicamente" el problema en el libro:

Mostrar que $[(p\leftrightarrow q)\land(q\leftrightarrow r)]\to(p\leftrightarrow r)$ es una tautología.

Yo escribí una tabla de verdad y todo sale bien, como era de esperar (y como se menciona en el libro de la solución). Mi pregunta es si hay o no una más "algebraica" solución usando equivalencias (no recurrir a la CNF o DNF).

Alguna idea?

Answer 1

He conseguido que funcione hacia fuera una solución, y he pensado que compartir aunque sea algo horrible (Publicada para hacer mucho más agradable leer el formato de imagen).

Answer 2

Aquí es una prueba de que es ligeramente más algebraicas que el "sólo hay que ver las tablas de verdad" mientras no la aerostación en algo largo y potencialmente ilegible:

\begin{array}l (p \leftrightarrow q) \land (q \leftrightarrow r) \\ = \{\mbox{definition of %#%#%}\} \\ (p \rightarrow q) \land (q \rightarrow p) \land (q \rightarrow r) \land (r \rightarrow q) \\ = \{\mbox{commutativity of %#%#%}\} \\ (p \rightarrow q) \land (q \rightarrow r) \land (r \rightarrow q) \land (q \rightarrow p) \\ \implies \{\mbox{transitivity of %#%#%}\} \\ (p \rightarrow r) \land (r \rightarrow p) \\ = \{\mbox{definition of %#%#%}\} \\ p \leftrightarrow r \end{array}

El único paso en esta cadena que usted puede considerar infundada es la "transitividad de la $\leftrightarrow$" paso; pero podemos muy fácilmente demostrar que por separado si se pretende:

\begin{array}l (p \rightarrow q) \land (q \rightarrow r) \\ = \{\mbox{definition of %#%#%}\} \\ (\lnot p \lor q) \land (\lnot q \lor r) \\ = \{\mbox{distributivity}\} \\ (\lnot p \land \lnot q) \lor (\lnot p \land r) \lor (q \land \lnot q) \lor (q \land r) \\ \implies \{\mbox{weakening}\} \\ \lnot p \lor \lnot p \lor (q \land \lnot q) \lor r \\ = \{\mbox{simplification}\} \\ \lnot p \lor r \\ = \{\mbox{definition of %#%#%}\} \\ p \rightarrow r \end{array}

La línea marcada con una "simplificación" de hecho utiliza un número algebraico de los hechos --, pero creo que son lo suficientemente claros para el lector humano.

Answer 3

Supongo que aceptas que $a\Rightarrow b$ es equivalente a $\tilde{} a \vee b$

y equivale a que $c \Leftrightarrow d$ $(c\Rightarrow d) \wedge (d\Rightarrow c)$.

Entonces es equivalente a $x \Leftrightarrow y$ $(\tilde{} x \vee y) \wedge (\tilde{} y\vee x )$.

Es distributiva y, por lo tanto es equivalente a $x \Leftrightarrow y$ $((\tilde{} x \vee y) \wedge \tilde{} y) \vee ((\tilde{} x \vee y) \wedge x )$.

Por lo tanto es equivalente a $x \Leftrightarrow y$ $(((\tilde{} x \wedge \tilde{} y)\vee(y \wedge \tilde{}y)) \vee ((\tilde{} x \wedge x)\vee(y \wedge x)))$.

Esto nos da $(((\tilde{} x \wedge \tilde{} y)\vee 0) \vee (0\vee(y \wedge x)))$.

Esto nos da $((\tilde{} x \wedge \tilde{} y) \vee (y \wedge x))$.

Trate de usar esto como una partida puntiagudos para su $p$, $q$ y $r$ declaración.