# Tautology Proof without truth table

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

• What are the rules in the proof system you're supposed to use? 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.

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!