2
$\begingroup$

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$

$\endgroup$
6
  • $\begingroup$ Are you allowed to use De Morgan's laws? $\endgroup$
    – ajotatxe
    Jul 6, 2015 at 10:53
  • 1
    $\begingroup$ Of course. @ajotatxe $\endgroup$ Jul 6, 2015 at 10:57
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 6, 2015 at 10:59
  • $\begingroup$ Sorry, I read this for a whole hour and still have no idea. Can you write them down with more detail? @MauroALLEGRANZA $\endgroup$ Jul 6, 2015 at 12:50
  • $\begingroup$ 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. $\endgroup$ Jul 6, 2015 at 13:13

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .