How to prove a logical implication?

Question

Question:

Using the Laws of Logic and Rules of Inference, prove that $$(\neg(\neg p \lor q) \lor r) \Rightarrow (\neg p \lor (\neg q \lor r)).$$

I just don't know how to apply the Rules of Inference. I know how to use the Laws of Logic to prove logical equivalent, but have no idea about logical implication.

I'm not quite understand the Rules of Inference. But rules are listed in wikipedia, List of Rules of Inference. You can use all of them, i think. It looks like my text.

And I also typed the table of Laws of Logic:

Law of Double Negation: $\neg\neg p \Leftrightarrow p$

DeMorgan's Laws: $\neg(p \lor q) \Leftrightarrow \neg p \land \neg q,\neg(p \land q) \Leftrightarrow \neg p \lor \neg q$

Commutative Laws: $p \lor q \Leftrightarrow q \lor p,p \land q \Leftrightarrow q \land p$

Associative Laws: $p \lor (q \lor r) \Leftrightarrow (p \lor q) \lor r,p \land (q \land r) \Leftrightarrow (p \land q) \land r$

Distributive Laws: $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)$

Idempotent Laws: $p \lor p \Leftrightarrow p,\quad p \land p \Leftrightarrow p$

Identity Laws: $p \lor F \Leftrightarrow p,p \land T \Leftrightarrow p$

Inverse Laws: $p \lor \neg p \Leftrightarrow T,p \land \neg p \Leftrightarrow F$

Domination Laws: $p \lor T \Leftrightarrow T,p \land F \Leftrightarrow F$

Absorption Laws: $p \lor (p \land q) \Leftrightarrow p,p \land (p \lor q) \Leftrightarrow p$

Answer 1

You should start supposing the contrary of the conclusion, that is, $$\neg(\neg p \vee (\neg q\vee r)))$$ Now, apply twice the De Morgan's law for $\neg(X\vee Y)$: $$p\wedge q \wedge\neg r$$ Eliminate $\wedge$ to obtain $\neg r$. Now, use the premise and eliminate $\vee$: $$\neg(\neg p\vee q)$$ Apply again De Morgan's law: $$p\wedge \neg q$$ Now, eleminate $\wedge$ in two previous formulae to get $q$ and $\neg q$. Insert $\wedge$ and you have the contradiction.

Answer 2

In the referenced List of rules of inferfence, you have the rule for Conditional Introduction (or Conditional proof), that is fundamental to prove a formula with a conditional :

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

2) $(¬p∨q) \to r$ --- from 1) by Material implication : $(\lnot \varphi \lor \psi) \Leftrightarrow (\varphi \to \psi)$ [with : $\lnot p \lor q$ as $\varphi$ and $r$ as $\psi$ ] and 1) and Biconditional Elimination (see again Wikipedia's List)

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

4) $\lnot p \lor q$ --- from 3) by addition

5) $r$ --- from 2) and 4) by Modus Ponens (or Conditional Elimination)

6) $q \to r$ --- from 3) and 5) by Conditional Introduction, discharging [a]

7) $\lnot p \lor (q \to r)$ --- from 6) by Addition

8) $\lnot p \lor (\lnot q \lor r)$ --- from 7) by Material Implication and Biconditional Elimination

$[¬(¬p∨q)∨r] \to [\lnot p \lor (\lnot q \lor r)]$ --- from 1) and 8) by Conditional Introduction.

Answer 3

First note that $$ (\neg p \lor q)\equiv p\rightarrow q $$ So now we have $$(\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{tautology} $$