¿Cómo demostrar una implicación lógica?

Question

Pregunta:

Usando las Leyes de la Lógica y las Reglas de Inferencia, prueba que $$(\neg(\neg p \lor q) \lor r) \Rightarrow (\neg p \lor (\neg q \lor r)).$$

Simplemente no sé cómo aplicar las Reglas de Inferencia. Sé cómo usar las Leyes de la Lógica para probar equivalentes lógicos, pero no tengo idea sobre la implicación lógica.

No comprendo del todo las Reglas de Inferencia. Pero las reglas están listadas en wikipedia, Lista de Reglas de Inferencia. Puedes usar todas ellas, creo. Se ve como mi texto.

Y también escribí la tabla de las Leyes de la Lógica:

Ley de la Doble Negación: $\neg\neg p \Leftrightarrow p$

Leyes de DeMorgan: $\neg(p \lor q) \Leftrightarrow \neg p \land \neg q,\neg(p \land q) \Leftrightarrow \neg p \lor \neg q$

Leyes Conmutativas: $p \lor q \Leftrightarrow q \lor p,p \land q \Leftrightarrow q \land p$

Leyes Asociativas: $p \lor (q \lor r) \Leftrightarrow (p \lor q) \lor r,p \land (q \land r) \Leftrightarrow (p \land q) \land r$

Leyes Distributivas: $p \lor (q \land r) \Leftrightarrow (p \lor q) \land (p \lor r),p \land (q \lor r) \Leftrightarrow (p \land q) \lor (p \land r)$

Leyes Idempotentes: $p \lor p \Leftrightarrow p,\quad p \land p \Leftrightarrow p$

Leyes de Identidad: $p \lor F \Leftrightarrow p,p \land T \Leftrightarrow p$

Leyes Inversas: $p \lor \neg p \Leftrightarrow T,p \land \neg p \Leftrightarrow F$

Leyes de Dominación: $p \lor T \Leftrightarrow T,p \land F \Leftrightarrow F$

Leyes de Absorción: $p \lor (p \land q) \Leftrightarrow p,p \land (p \lor q) \Leftrightarrow p$

Answer 1

Deberías empezar suponiendo lo contrario de la conclusión, es decir, $$\neg(\neg p \vee (\neg q\vee r)))$$ Ahora, aplica dos veces la ley de De Morgan para $\neg(X\vee Y)$: $$p\wedge q \wedge\neg r$$ Elimina $\wedge$ para obtener $\neg r$. Ahora, utiliza la premisa y elimina $\vee$: $$\neg(\neg p\vee q)$$ Aplica nuevamente la ley de De Morgan: $$p\wedge \neg q$$ Ahora, elimina $\wedge$ en las dos fórmulas anteriores para obtener $q$ y $\neg q$. Inserta $\wedge$ y tendrás la contradicción.

Answer 2

En la lista de reglas de inferencia referenciada, tienes la regla de Introducción condicional (o Demostración condicional), que es fundamental para demostrar una fórmula con un condicional :

1) $¬(¬p∨q)∨r$ --- premisa

2) $(¬p∨q) \to r$ --- de 1) por Implicación material : $(\lnot \varphi \lor \psi) \Leftrightarrow (\varphi \to \psi)$ [con : $\lnot p \lor q$ como $\varphi$ y $r$ como $\psi$ ] y 1) y Eliminación Bicondicional (ver nuevamente la Lista de Wikipedia)

3) $q$ --- supuesto [a]

4) $\lnot p \lor q$ --- de 3) por adición

5) $r$ --- de 2) y 4) por Modus Ponens (o Eliminación Condicional)

6) $q \to r$ --- de 3) y 5) por Introducción Condicional, descargando [a]

7) $\lnot p \lor (q \to r)$ --- de 6) por Adición

8) $\lnot p \lor (\lnot q \lor r)$ --- de 7) por Implicación Material y Eliminación Bicondicional

$[¬(¬p∨q)∨r] \to [\lnot p \lor (\lnot q \lor r)]$ --- de 1) y 8) por Introducción Condicional.

Answer 3

Primero nota que $$ (\neg p \lor q)\equiv p\rightarrow q $$ Así que ahora tenemos $$(\neg(\neg p \lor q) \lor r) \rightarrow (\neg p \lor (\neg q \lor r))$$ $$\equiv (\neg(p \rightarrow q) \lor r) \rightarrow (\neg p \lor (q \rightarrow r))$$ $$\equiv ((p \rightarrow q) \rightarrow r) \rightarrow ( p \rightarrow (q \rightarrow r))$$ $$\equiv \mbox{tautología} $$