# Disjunction elimination proof

I'm having trouble making assumptions in this exercise. Can someone point me in the right direction?

premise: P OR Q
conclusion: R → (P OR Q) AND R

My attempt so far:

1. P OR Q                 premise
___________________________________
2.  |  R                  assumption   |
3.  |  (P OR Q) AND R     assumption   |
|   _____________________________  |
4.  |  | P                assumption | |
5.  |  | (P OR Q) AND R   →e 2,3     | |
|  ______________________________| |
6.  |  | Q                assumption | |
7.  |  |

This does not seem right and guidance is much appreciated.

• The first assumption is the premise: p OR q. The second one will be: r; we need it in order to conclude with →e. – Mauro ALLEGRANZA Sep 1 '17 at 6:03
• Having p OR q and r, we can use Conjunction (-intro) to get: (p OR q) AND r. – Mauro ALLEGRANZA Sep 1 '17 at 6:05
• For three variables, you could just use a truth table. Or, you could convert x -> y to -x V y and then use DeMorgan's law and a series or combining rules to reduce the statement p V q -> (r -> ( (p V q) /\ r)) to truth. – barrycarter Sep 2 '17 at 1:44

I believe the following are tautologies:

• A → A
• B → (A → B)
• (A → B) → ((A → C) → (A → (B AND C)))

If you can cite those as general tautologies, then you can substitute "R" for A, "P OR Q" for B, and "R" for C. Then modus ponens will get you to your conclusion.

• You gave me the idea to reconsider how parenthesis are placed. +1 – Frank Hubeny Nov 20 '18 at 20:14

There is a valuation for the atomic sentences, "P" is true, "Q" is true, and "R" is false, that makes the premise, "P OR Q", true, but the conclusion, "R → (P OR Q) AND R", false.

One should not be able to find a proof for this.

To help see why this is the case, consider the opposite direction of the implication to see what would happen when one can prove a result. Suppose we were trying to show "R → (P OR Q) AND R" implied "P OR Q". This would be modus ponens and one could prove it by using conditional elimination as follows:

A truth table would also show this:

Note that every valuation of the three atomic sentences in the first three columns where the Premise column is "T" or true, the Conclusion column is not "F" or not false. It does not matter what happens to the Conclusion column if the Premise column is "F" or false. The Argument column shows that for all valuations the result is "T" or true.

Now consider the other direction. Given only "P OR Q" as the premise, we are expected to derive something about "R" which has nothing to do with either "P" or "Q".

Consider the truth table for this:

There are three different valuations of the atomic sentences where the premise, "P ∨ Q", is true, but the conclusion "[R → (P ∨ Q)] ∧ R" is false. We only need one to claim that we should not be able to prove this result.

This could be viewed as a tautology if one interprets the sentence as

(P ∨ Q) → (R → ((P ∨ Q) ∧ R))

Here is the truth table:

References

Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/

Stanford Truth Table Tool http://web.stanford.edu/class/cs103/tools/truth-table-tool/

Wikipedia, "Modus ponens" https://en.wikipedia.org/wiki/Modus_ponens

• I thought that if A is false, then "A implies B" is always true. – user3294068 Nov 20 '18 at 18:44
• @user3294068 Yes, that is how I understand it as well. Look at the final truth table with the highlighted rows. Those three highlighted rows have true premises but false conclusions. The "A" in those cases would be true but the "B" false. That would make "A implies B" false for those valuations. – Frank Hubeny Nov 20 '18 at 19:08