Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)]$

share|cite|improve this question
What are the rules in the proof system you're supposed to use? – Henning Makholm Oct 4 '12 at 15:08
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. – 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.

share|cite|improve this answer

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!

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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