How would I go about proving this without a truth table?

$[(p \lor q) \implies r ] \implies [ \neg r \implies (\neg p \land \neg q)]$

  • 5
    $\begingroup$ What are the rules in the proof system you're supposed to use? $\endgroup$ Oct 4 '12 at 15:08
  • $\begingroup$ I understand how (p or q)→r = (~p AND ~q) → ~r due to De Morgan's Law How do you prove that the reverse of an implication is true? So that the reduction equals what I am trying to prove. $\endgroup$
    – TJZ
    Oct 4 '12 at 15:12

It's not that straightforward, what inference rules or other things are allowed to do..

I would use $(a\to b) = \lnot a\lor b$ for both members in the [bracket], and at last I would find that they are equal.


If you were using a tree system this would be pretty trivial, so I assume you wouldn't be asking. So let's take the question is about a strategy in a standard sort of natural deduction system (which I'll lay out Fitch-style).

In fact, if you think about it, the proof straightforwardly writes itself if you think strategically :-) The target is to prove the conditional

$[(p \lor q) \to r] \to [\neg r \to (\neg p \land \neg q)]$

You want, in effect to show that from the temporary assumption

$\quad|\quad(p \lor q) \to r$

you can derive a certain consequent $C$: and then you discharge the assumption to derive the desired tautology $((p \lor q) \to r) \to C$. So how do you prove a consequent $C$? It is another conditional. So you know you next need to assume the antecedent of $C$ and aim to derive its consequent. So, next step, assume

$\quad|\quad|\quad \neg r$

(We've made a new assumption, so we indent the line of proof again in a Fitch-style system). Your target now is $\neg p \land \neg q$, so you need to prove (i) $\neg p$ and prove (ii) $\neg q$.

So (i) you want to prove a negative. So again you know what you need to do next. Assume the positive and aim for a contradiction. So, next step

$\quad|\quad|\quad|\quad p$

So far that's more or less automatic. And ahah! You can now see how to use the original premiss (the only way forward now), by just going

$\quad|\quad|\quad|\quad (p \lor q)$

by $\lor$-introduction, and now modus ponens gets you

$\quad|\quad|\quad|\quad r$

And you arrive at a contradiction immediately. So you can discharge that assumption $p$ to get

$\quad|\quad|\quad \neg p$.

And now you do a similar routine to get

$\quad|\quad|\quad \neg q$.

The end is now in sight, and you should be able to finish up, by using $\land$-introduction, and then conditional proof ($\to$-introduction) twice.

Moral? Think strategically and these sorts of proof (at least, the ones you'll encounter in elementary texts/class worksheets) fall out easily!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.