Cómo demostrar que $[(p \to q) \land (q \to r)] \to (p \to r)$ es una tautología sin usar la tabla de verdad?

Question

Estoy buscando una manera de demostrar que la declaración, $[(p \to q) \land (q \to r)] \to (p \to r)$ es una tautología sin la ayuda de la tabla de verdad. Utilizando sólo Leyes y Teoremas como la Ley de De Morgan, la Ley de Dominación, etc. Además, no puedo usar las reglas de inferencia. Por favor, ayuda, gracias.

Answer 1

Como sugiere correctamente Wuestenfux , primero hay que descomponer $\to$ . A continuación, debes aplicar varias equivalencias lógicas para simplificar tu fórmula a $\top$ (una fórmula que siempre es verdadera). Una simplificación completa de su fórmula, utilizando las equivalencias lógicas enumeradas aquí es la siguiente:

\begin {align} & \big ((p \to q) \land (q \to r) \big ) \to (p \to r) \\ \equiv \ & \lnot \big ( ( \lnot p \lor q) \land ( \lnot q \lor r) \big ) \lor ( \lnot p \lor r) & \text {descomposición de } \to \\ \equiv \ & \lnot ( \lnot p \lor q) \lor \lnot ( \lnot q \lor r) \lor \lnot p \lor r& \text {De Morgan} \\ \equiv \ & ( \lnot\lnot p \land \lnot q) \lor ( \lnot\lnot q \land \lnot r) \lor \lnot p \lor r & \text {De Morgan} \\ \equiv \ & \lnot p \lor ( \lnot\lnot p \land \lnot q) \lor ( \lnot\lnot q \land \lnot r) \lor r & \text {comutatividad} \\ \equiv \ & \big (( \lnot p \lor \lnot\lnot p) \land ( \lnot p \lor \lnot q) \big ) \lor \big (( \lnot\lnot q \lor r) \land ( \lnot r \lor r) \big ) & \text {distribución} \\ \equiv \ & \big ( \top \land ( \lnot p \lor \lnot q) \big ) \lor \big (( \lnot\lnot q \lor r) \land \top \big ) & \text {ley de la negación} \\ \equiv \ & ( \lnot p \lor \lnot q) \lor ( \lnot\lnot q \lor r) & \text {ley de la identidad} \\ \equiv \ & \lnot p \lor ( \lnot q \lor \lnot\lnot q) \lor r & \text {asociación} \\ \equiv \ & \lnot p \lor \top \lor r & \text {ley de la negación} \\ \equiv \ & \top & \text {ley de dominación} \\ \end {align}

Answer 2

A la hora de simplificar los enunciados, una regla de equivalencia muy útil es:

Reducción

$p \land (\neg p \lor q) \equiv p \land q$

$p \lor (\neg p \land q) \equiv p \lor q$

Si tienes esta regla, puedes empezar haciendo lo que hace @Taroccoesbrocco, pero terminar más rápido:

\begin {align} & \big ((p \to q) \land (q \to r) \big ) \to (p \to r) \\ \equiv \ & \lnot \big ( ( \lnot p \lor q) \land ( \lnot q \lor r) \big ) \lor ( \lnot p \lor r) & \text {ley de aplicación} \\ \equiv \ & \lnot ( \lnot p \lor q) \lor \lnot ( \lnot q \lor r) \lor \lnot p \lor r& \text {De Morgan} \\ \equiv \ & ( \lnot\lnot p \land \lnot q) \lor ( \lnot\lnot q \land \lnot r) \lor \lnot p \lor r & \text {De Morgan} \\ \equiv \ & \lnot p \lor ( \lnot\lnot p \land \lnot q) \lor ( \lnot\lnot q \land \lnot r) \lor r & \text {comutatividad} \\ \equiv \ & \lnot p \lor \lnot q \lor \lnot\lnot q \lor r & \text {reducción} \\ \equiv \ & \lnot p \lor \top \lor r & \text {complemento} \\ \equiv \ & \top & \text {ley de dominación} \\ \end {align}

Tampoco es necesario hacer una conmutación explícita si tiene conjunciones o disyunciones generalizadas, aunque hacerlo ayuda al lector

Answer 3

Una pista: $p\rightarrow q$ equivale a $\neg p\vee q$ .