How to prove or statements
How do I prove statements of the following types:
$A \text{ or } B \implies$ C
$A \implies B \text{ or } C$
I don't know how to go about proving statements like this when they have "or". Can someone tell me different ways to prove such statements? And maybe give me some basic examples to help?
Thank-you.
For the first, you can prove both $A\Rightarrow C$ and $B\Rightarrow C$.
Example. If $x=1$ or $x=2$ then $x^2-3x+2=0$.
Proof: First assume $x=1$. Then $x^2-3x+2=1^2-3\cdot 1+2=1-3+2=0$ as was to be shown. Next assume $x=2$. Then $x^2-3x+2=4-3\cdot 2+2=4-6+2=0$ as was to be shown. Since both cases $x=1$ and $x=2$ lead to $x^2-3x+2$, we are done. $_\square$
For the second, you can for example prove $(A\land \neg B)\Rightarrow C$.
Example. If $a\cdot b=0$ then $a=0$ or $b=0$.
Proof: Assume $ab=0$ and $a\ne 0$. Since $a\ne 0$, we are allowed to divide both sides of $ab=0$ by $a$. By this we obtain $b=0$ as was to be shown. $_\square$
A more formal version of another answer (#396261): For the first, \begin{align} & A \lor B \implies C \\ \iff & \;\;\;\;\;\text{"expand $\implies$"} \\ & \lnot (A \lor B) \lor C \\ \iff & \;\;\;\;\;\text{"De Morgan"} \\ & (\lnot A \land \lnot B) \lor C \\ \iff & \;\;\;\;\;\text{"distribute $\lor$ over $\land$"} \\ & (\lnot A \lor C) \land (\lnot B \lor C) \\ \iff & \;\;\;\;\;\text{"reintroduce $\implies$, twice"} \\ & (A \implies C) \land (B \implies C) \\ \end{align} For the second, rewriting can be done in a number of different ways: one is \begin{align} & A \implies B \lor C \\ \iff & \;\;\;\;\;\text{"expand $\implies$"} \\ (*)\;\phantom\iff & \lnot A \lor B \lor C \\ \iff & \;\;\;\;\;\text{"reintroduce $\implies$ in a different way"} \\ & \lnot (\lnot A \lor B) \implies C \\ \iff & \;\;\;\;\;\text{"De Morgan"} \\ & A \land \lnot B \implies C \\ \end{align}
Update. As a comment rightly indicates, from $(*)$ you have many alternatives. Apart from the first and last expression in the last calculation, we have the following equivalents:
- $\lnot B \implies \lnot A \lor C$
- $\lnot C \implies \lnot A \lor B$
- $A \land \lnot C \implies B$
- $\lnot B \land \lnot C \implies \lnot A$
- $A \land \lnot B \land \lnot C \implies \textrm{false}$
(That last one is essentially a proof by contradition.) All of these follow by the fact that $\lor$ is commutative (symmetric) and associative.
I'll handle a different kind of goal statement first, namely: $P\implies Q$.
To prove this kind of statement you can opt between:
- Assume $P$ is true, $(\cdots)$, conclude $Q$.
- Prove the logically equivalent statement $\neg Q\implies \neg P$, by using the same technique as above: assume $\neg Q$ is true, $(\cdots)$, conclude $\neg P$.
- Assume $P$ is true. Now assume, hoping to find a contradiction, that $Q$ is false. Find a contradiction and conclude that the last assumption you've made ($\neg Q$) is false and conclude $Q$.
- Consider the tautology $\neg P\lor P$ and do a proof by cases. If $\neg P$ is true, that $P\implies Q$ is logically true. If $P$ is true, you're back to 1.
To prove a goal statement that looks like $P\lor Q$ you can try:
- Assume $\neg P$ to be true, $(\cdots)$, conclude $Q$ or assume $\neg Q$, $(\cdots)$, conclude $P$.
- From whatever assumptions you have try to get $P$, from where $P\lor Q$ follows or try to get $Q$, from where $P\lor Q$ follows.
Now there's something you should note. First and foremost the statements $\color{grey}(A\lor B\color{grey})\implies C$ and $A\implies \color{grey}(B\lor C\color{grey})$ are statements of the kind $P\implies Q$. Only at a later stage does the disjunction come into play. Notice the ghost parentheses.
Now note that they are very, very distinct. One of them will eventually have a goal which is a disjunction while the other has the disjuction as an hypothesis. Above I handled the case where the goal is a disjunction.
When you're hypothesis is a disjuction $P\lor Q$ and you want to prove $R$. You can try proof by cases: sinse you're hypothesis is true then either $P$ is true or $Q$ is true:
- Suppose $P$ is true, $(\cdots)$, conclude $R$.
- Suppose $Q$ is true, $(\cdots)$, conclude $R$.
Finally conclude that $\color{grey}(P\lor Q\color{grey})\implies R$.
You can find lots of examples and a more detailed explanation in this amazing book: How to Prove It: A Structured Approach, by D.J. Velleman.