How do you prove questions of the form: Show that $A\to \text{ B or C or D}$?

Question

How do you prove questions of the form: Show that $A\to \text{ B or C or D}$?

For example, suppose the question was:

$$\text{(x = 10) $\to$($x+1 = 11$) or ($x+2 = 4$) or ($x-1 = 8$)}$$

I don't know how to prove "or"

In "or", only one of the things after the arrow have to be True.

What I think:

Suppose x = 10

Show $x+1 = 11$

Show $x+2 \neq 4$

Show $x-1 \neq 8$

$\therefore$ since one of the $or$ statements in true, the implication is proven.

Is this how it's done?

Answer 1

It is equivalent to assume that $Q$ and $R$ are false and then prove the new theorem

$$\text{[$A$ and (not $Q$) and (not $R$)] $\rightarrow$ $P$.}$$

You can see this by explicitly writing out the truth table for these quantities. You can also negate any two of the three $P,Q,R$ and add it to your premise to deduce the other. The intuitive reason this works is that any "or" statement is true so long as at least one of the components is true, so it doesn't hurt to assume that all but one is false.

To make the writing of the truth table easier, you can rewrite [$P$ or $Q$ or $R$] as [$P$ or ($Q$ or $R$)] and then adding [not ($Q$ or $R$)] to your assumptions. By de Morgan's law, [not ($Q$ or $R$)] $\leftrightarrow$ [(not $Q$) and (not $R$)].

Answer 2

To prove $P $ or $ Q $ or $R $, you just need to prove that one of them is true. for example, if you prove that $Q $ is true, it is ok.

but

to prove $P $ xor $Q $, you must prove that only one is true. if you show that $P $ is true, you should prove that $Q $ is false.

Answer 3

A conditional (if-then statement ) $P\rightarrow Q $is true as long as we don't have $P $ true and $Q $ false. Also, $Q \lor R \lor S $ is true as long as one of $Q, R$ or $S $ is true. Thus we need to avoid $P $ true and $Q,R $ and $S $ false. ..

Answer 4

No, you are right to be troubled by your argument. There are a couple problems with it.

First of all, as Salahamam_Fatima points out, you are proving far more than you need to. Once you have shown that $x+1=11$, one of the statements or'd together is true, so the conclusion must be true no matter the other statements. So you don't need to worry about the other two.

Second of all, in most practical cases where such an or statement arises, there is no clear dichotomy in the hypotheses corresponding to each term in the solution. Here's what I mean: if I write $$(x\in\{10,9\})\Rightarrow(x+1=11)\vee(x-1=8)$$ then you just split into cases. "If $x=10$, then $x+1=11$. If $x=9$, then $x-1=8$. Hence, in either case, a statement from the conclusion holds, so the or statement as a whole holds." But that's an artifact of the simplicity of the problem. What if I asked you to show $$\left(\sqrt{2}=\frac{m}{n}\right)\Rightarrow(m\notin\mathbb{Z})\vee(n\notin\mathbb{Z})$$ How do you decide what values of $m$ and $n$ make the first conclusion true? Or the second? And how do you show that those two cases exhaust all values of $m$ and $n$?

One way to deal with these difficulties is to work by contrapositive: we can prove (via truth tables, or, given a specific axiomatization of logic, formally) that $(P\Rightarrow Q\vee R)\Leftrightarrow({\sim}Q\wedge {\sim}R\Rightarrow {\sim}P)$. So now consider my statement above. The contrapositive is $$(m,n\in\mathbb{Z})\Rightarrow\left(\sqrt{2}\neq\frac{m}{n}\right)$$ Does that feel easier?

But there's a better way yet. Exercise: prove that $(P\Rightarrow Q\vee R)\Leftrightarrow(P\wedge {\sim} Q\Rightarrow R)$.

Answer 5

Proving A→ B can be done in two ways.

1. Assume the opposite and deduce a contradiction. This is called proof by counterexample.

2. Prove every possible case. This is usually done with induction.

Answer 6

If you want to prove a conditional $A \rightarrow (B \lor C \lor D)$, then there are typically two strategies:

C1. Conditional Proof: Assume $A$, and try to show $B \lor C \lor D$

C2. Contrapositive Proof: Assume $\neg(B \lor C \lor D)$ and try to show $\neg A$

Following 1, you would need to show a disjunction $B \lor C \lor D$. To prove disjunctions, there are typically 3 strategies:

D1. If you're lucky, you may be able to prove one of the disjuncts by themselves. In fact, in your particular problem you are lucky, since the assumption $x=10$ quickly gets you to $x+1=11$. But like I said, you have to be lucky to get this. Typically, you are not so lucky and have to use one of the other 2 strategies

D2. If you have a disjunction as a premise (say, you have $E \lor F \lor G$), then you can try to set up a proof by cases on that disjunction that you have, and more often than not, those cases will lead to the cases of the disjunction you want (e.g. case $E$ might lead to $C$, case $F$ might lead to $D$, and case $G$ leads to $B$). If you don't have any disjunction to work with, you can always get one through the Law of Excluded Middle. That is, you can always assume, say, $B \lor \neg B$, and now case $B$ obviously gives you immediately what you want, but with case $\neg B$ you may be able to show $C \lor D$

D3. A third strategy to prove a disjunction is to do a proof by contradiction. So, assume $\neg(B \lor C \lor D)$, and show that that leads to a contradiction. Please note that given that in your particular problem the disjunction was the consequent that you want, you basically end up doing a proof by contrapositive. But for other problems: if you ever want to prove a disjunction (whether the consequent of a conditional or just by itself), a proof by contradiction is often a pretty good strategy (especially if you can't use strategy D1), since by DeMorgan you immedtaiely get some stuff to work with to try and derive your contradiction from.