Using natural deduction to prove $p \rightarrow (q \wedge r)\vdash (q\rightarrow r) \vee \neg (p \vee r)$.

I'm having trouble proving this with natural deduction:

$$p \to (q \land r) ~\vdash~ (q\to r) \lor \lnot (p \lor r)$$

I understand that I only need to prove one side to introduce an disjunction. I also think I should start from an hypothesis of either $¬p$ to get $p$, or $(p ∨ r)$ to get $¬(p ∨ r)$ but I can't seem to be able to get a contradiction out of the premise.

I'm really stuck, so help would be great, thanks.

• Maybe faster with semantic tableaux. Natural deduction is more usable with first order logic – Filburt Nov 21 '17 at 2:55
• I would use something else but the problem asks i solve it with natural deduction, using only introduction and elimination laws – user505193 Nov 21 '17 at 18:53

I assume you are using classical logic. Assume $\lnot (p \lor r)\lor (p \lor r)$. Let's work by elimination of $\lor$. If $\lnot (p \lor r)$ then $(q\to r) \lor \lnot (p \lor r)$, else if $p \lor r$ we have to introduce $\to$. In the first case: $p$ we use the hypothesis to conclude $q\land r$ and hence $q\to r$ (easy introduction of $\to$), in the second case: $r$ we can introduce $\to$, getting - again - $q\to r$. So in both the cases of $p\lor r$ we obtain $q\to r$ and obviously $(q\to r) \lor \lnot (p \lor r)$. So we can conclude having proved that in both cases $\lnot (p \lor r)$ and $p \lor r$, under the assumption $p \to (q \land r)$ it holds also $(q\to r) \lor \lnot (p \lor r)$.

Tancredi suggests a neat trick. Here's how to do the proof by "brute force".

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

There's the premiss and (temporarily assumed) the negation of the conclusion -- you are going to aim for a reductio!

Now we have something of the form $\neg(A \lor B)$. So you should know how to use natural deduction to get to $\neg A$ and to $\neg B$ -- that's a routine exercise of proving one of De Morgan's Laws (something any student of natural deduction must learn!). Fill in the argument. So you have

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

Now again, getting from $\neg(A \to B)$ to $A$ and to $\neg B$ is another routine exercise that you should know how to do. Also you know how to kill double negations, so you can now get to

$\quad\quad | \quad \vdots\\ \quad\quad | \quad q\\ \quad\quad | \quad \neg r\\ \quad\quad | \quad (p \lor r)$

Now things are looking happier! Do a simple argument by cases using that last disjunction:

$\quad\quad | \quad \quad | \quad p\\ \quad\quad | \quad \quad |\quad q \land r\\ \quad\quad | \quad \quad |\quad r\\ \quad \quad | \quad \quad / \\ \quad\quad | \quad \quad |\quad r\\ \quad \quad | \quad r$

Both disjuncts yield $r$ (the first by invoking our premiss, at last!). But now we have our contradiction as we already have $\neg r$.

So we can finish

$\quad\quad | \quad \text{Contradiction!}\\ \neg\neg((q \to r) \lor \neg(p \lor r))\\ ((q \to r) \lor \neg(p \lor r))$

You can now see that we didn't need to prove $q$ so that cuts down some work. But I wasn't trying to produce the shortest proof, but to show how "brute force" (as often) will work -- i.e., assume the negation of what you need to show; and then watch out for standard pattens of argument, De Morgan's Laws, the inference from a negated conditional to its antecedent and negated consequent, etc.

• I would truly be saved if I could use De Morgan's Law, but I can only use Introduction and Elimination, which is why I'm a bit stuck... – user505193 Nov 21 '17 at 18:48
• I didn't mean invoke De Morgan's Law as a primitive --- I meant use the usual proofs using Introduction and Elimination from the negated disjunction to both of the negated disjuncts (which, as I said, is a routine exercise). – Peter Smith Nov 21 '17 at 18:56
• okay sorry, i am not an english speaker so the vocabulary is a bit harder for me to understand – user505193 Nov 21 '17 at 18:56

There are typically 3 strategies to prove a disjunction:

1. See if you can prove one of the disjuncts by itself. This typically only works somewhere in the middle of the proof though; if the ultimate conclusion could be just that disjunct, then most likely they would have that the conclusion.

2. Try a proof by contradiction.

3. See if you can work with a disjunction: Often, one of the disjuncts you have will lead toone of the disjuncts you want, while the other one you have will get you the other one you want. Also, if you don't have a disjunction to work with, you can always get any $P \lor \neg P$ by Law of Excluded Middle (another pattern that any beginner should learn!)

Since Peter Smith used strategy 2, let me show you how strategy 3 would work.

First, since both disjunctions of the goal contain $r$ ... I am immediately thinking: start by showing $r \lor \neg r$

Once you have that:

Subproof on $r$: This should give you $q \rightarrow r$ very quickly

Subproof on $\neg r$: Now you want to get $\neg (p \lor r)$ ... so do a proof by contradiction: Assume $p \lor r$. So again a proof by cases: assume $p$. That gives you $q \land r$, and thus $r$, and thus a contradiction with $\neg r$. Assuming $r$ will give that same contradiction immediately, and so we get the contradiction to finish the proof by contradiction, meaning we have $\neg (p \lor r)$

And so yes, the one disjunct we have gives us the one we want, and the other one we have gives us the other we want! This is a very common pattern, so remember this strategy as well.