Lógica - cómo probar la $\;[(p \rightarrow q) \land (q \rightarrow r)] \rightarrow (p \rightarrow r) \equiv T\;$?

Question

Eso es lo que tengo hasta ahora... parece como un mal enfoque. He probado otros y terminan en el mismo lugar.

Answer 1

Lo que he hecho en los primeros pasos es del todo correcta. Voy a empezar donde lo dejó. Tenemos que utilizar una gran cantidad de la distribución. Y se ensucia antes de que se vuelva más claro!

Para demostrar $$[(p \rightarrow q) \land (q\rightarrow r)] \rightarrow (p\rightarrow r) \equiv T$$ $$\vdots$$ $$\vdots$$

$$\equiv (p\land \lnot q) \lor (q \land \lnot r) \lor (\lnot p \lor r)\tag{picking up...}$$ $$\equiv [[(p\land \lnot q) \lor q] \land [(p \land \lnot q) \lor \lnot r]] \lor (\lnot p \lor r)\quad \tag{distributivity x 2}$$

$$\equiv [[(p\lor q) \land (\lnot q \lor q)] \land [(p\lor \lnot r)\land (\lnot q \lor \lnot r)]] \lor(\lnot p \lor r)\quad \quad\quad \quad\tag{distributivity x 2}$$

$$\equiv [(p \lor q) \land T \land (p \lor \lnot r) \land (\lnot q \lor \lnot r)] \lor (\lnot p \lor r)\quad \tag{$\lnot q \lor p \equiv T$}$$

$$\equiv [(p \lor q) \land (p \lor \lnot r) \land (\lnot q \lor \lnot r)] \lor (\lnot p \lor r)\quad \quad \quad \quad \tag{$(p \lor q) \de la tierra T \equiv (p \lor p)$}$$

---

Se puede ver cómo la distribución (como se explica en la respuesta a su pregunta anterior) ayuda aquí? Hemos eliminado una expresión de ( $\lnot q \lor q \equiv T$ ) y, en caso de continuar con la expansión de la salida, utilizando la distribución, en la expresión a la izquierda (en paréntesis), usted será capaz de eliminar otros términos...finalizando con una evaluación final de la $T$.

¿Por qué no trabajar en él un poco para ver lo que hay que llegar, y después de una pregunta de seguimiento en un comentario abajo, o como una edición a esta pregunta si usted se encuentra en problemas.

---

Edit: continúa desde donde nos quedamos...

Para probar:

$$[(p \rightarrow q) \land (q\rightarrow r)] \rightarrow (p\rightarrow r) \equiv T$$ $$\vdots$$ $$\vdots$$

$$\equiv [(p \lor q) \land (p \lor \lnot r) \land (\lnot q \lor \lnot r)] \lor (\lnot p \lor r)\quad \quad \quad \quad \tag{$(p \lor q) \de la tierra T \equiv (p \lor p)$}$$ $$\equiv [(p \lor q) \land (\lnot q \lor \lnot r) \land (p\lor \lnot r)] \lor (\lnot p \lor r)\quad\quad\quad\quad \tag{Commutative property}$$

$$\equiv[[(p \lor q) \land \lnot q] \lor [(p \lor q) \land \lnot r] \land (p \lor \lnot r)] \lor (\lnot p \lor r)\quad\quad\quad\quad \tag{distributivity x 2}$$

$$\equiv[[(p\land \lnot q) \lor (q \land \lnot q) \lor (p \land \lnot r) \lor (q \land \lnot r)] \land (p \land \lnot r)] \lor (\lnot p \lor r) \quad\quad\quad\quad\quad \tag{distributivity}$$

$$\equiv [[(p \land \lnot q) \lor F \lor (p\land \lnot r) \lor (q \land \lnot r)] \land (p \land \lnot r)] \lor (\lnot p \lor r)\quad\quad\quad\quad\quad\quad\tag{$q \de la tierra \lnot q \equiv F$}$$

$$\equiv [[(p \land \lnot q) \lor \color{red}{\bf{(p\land \lnot r)}}\lor (q \land \lnot r)] \land \color{red}{\bf{(p \land \lnot r)}}] \lor (\lnot p \lor r) \quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad \tag{$(p \de la tierra \lnot r) \lor F \equiv p \de la tierra \lnot r)$}$$

$$\equiv \color{red}{\bf{(p \land \lnot r)}} \lor (\lnot p \lor r)\quad\quad\quad\quad \tag{?}$$

$$\equiv (\lnot \lnot p \land \lnot r) \lor (\lnot p \lor r)\quad\quad\quad\quad\tag{Double negation}$$

$$\equiv \lnot( \lnot p \lor r) \lor (\lnot p \lor r) \quad\quad\quad \tag{DeMorgan's Law}$$

$$\quad \equiv T \quad\quad\quad\quad \tag{$\lnot un \lor a \equiv T$}$$

Por lo tanto, $$[(p \rightarrow q) \land (q\rightarrow r)] \rightarrow (p\rightarrow r) \equiv T$$

---

Tarea: Lo que queda es para que usted pueda justificar/entender por qué el paso seguido por "$\,(?)\,$" sostiene.

---

Answer 2

Supongamos que (1)$[(p \rightarrow q) \land (q \rightarrow r)] \rightarrow (p \rightarrow r)$ es falso para algunos de asignación de $p$, $q$, y $r$. A partir de la tabla de verdad para la implicación, esto significa que (2)$(p \rightarrow q) \land (q \rightarrow r)$ debe ser verdaderas al mismo tiempo (3)$p \rightarrow r$ es falso. En (2) vemos que (4)$p \rightarrow q$ y (5)$(q \rightarrow r)$ debe ser cierto y de (3) tenemos (6)$p$ debe ser verdaderas al mismo tiempo (7)$r$ es falso. Así que a partir de (4) y (6), $q$ debe de ser verdad. Pero ahora tenemos una contradicción con (5) y (7). Por lo tanto no otorgamiento de $p$, $q$, y $r$, lo que hará que el original de la declaración falsa.

Answer 3

Aquí hay otra prueba: $$\begin{align} & ((p \rightarrow q) \land (q \rightarrow r)) \rightarrow (p \rightarrow r) \\ \equiv & \;\;\;\;\;\text{"expand all occurrences of %#%#%"} \\ & \lnot((\lnot p \lor q) \land (\lnot q \lor r)) \lor \lnot p \lor r \\ \equiv & \;\;\;\;\;\text{"in the first disjunct we may assume the negation of the others (%#%#% and %#%#%)"} \\ & \lnot((\text{false} \lor q) \land (\lnot q \lor \text{false})) \lor \lnot p \lor r \\ \equiv & \;\;\;\;\;\text{"simplify"} \\ & \lnot(q \land \lnot q) \lor \lnot p \lor r \\ \equiv & \;\;\;\;\;\text{"excluded middle"} \\ & \lnot \text{false} \lor \lnot p \lor r \\ \equiv & \;\;\;\;\;\text{"simplify"} \\ & \text{true} \\ \end{align}$$