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)]$
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.Sign up to join this community
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
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
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!