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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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 (e.g. inside a subproof), because if the ultimate conclusion could be just that disjunct, then most likely the creator of the problem would have made that disjunction as the very 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.