# How to prove a logical implication?

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$

• Are you allowed to use De Morgan's laws? – ajotatxe Jul 6 '15 at 10:53
• Of course. @ajotatxe – PHPIsTheBestLanguage Jul 6 '15 at 10:57
• You need to tell us which "laws of logic and rules of inference" you can use in the proof. There are many different systems which take different kinds of laws and rules as primitive, and there's nothing "of course" about which one you're using. – hmakholm left over Monica Jul 6 '15 at 10:59
• Sorry, I read this for a whole hour and still have no idea. Can you write them down with more detail? @MauroALLEGRANZA – PHPIsTheBestLanguage Jul 6 '15 at 12:50
• The answer is the same as in your new post, exploiting the equivalence between $\lnot p \lor q$ and $p \to q$, that is expressed by the Material implication rule of inference. – Mauro ALLEGRANZA Jul 6 '15 at 13:13

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.

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.

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}$$