4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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$

$\endgroup$
  • 4
    $\begingroup$ Any reason for the downvote? $\endgroup$ – Hagen von Eitzen May 19 '13 at 12:17
  • $\begingroup$ "you can prove" and "you can for example prove." Are there really other options? Also, in the first case, since "A or B" is true iff at least one of the two constituent parts is true, why prove both $A\implies C$ and $B\implies C$? $\endgroup$ – sasha Jun 2 '13 at 20:40
  • $\begingroup$ I'm not sure that this is accurate. For the second case, you would have to prove both $(A \land \lnot B) \Rightarrow C$ and $(A \land \lnot C) \Rightarrow B$, would you not? $\endgroup$ – Awn Jan 1 '18 at 3:22
  • $\begingroup$ I suppose an easier option (for $A \Rightarrow (B \lor C)$) would be to suppose $A \land (\lnot B \land \lnot C)$, and derive a contradiction. Or even a similar argument by contrapositive. $\endgroup$ – Awn Jan 1 '18 at 3:28
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I would add for the sake of completeness that from your second step you can obtain different third steps, because the disjunction is commutative (e.g. $A \wedge \neg C \Longrightarrow B$). $\endgroup$ – Kolmin Jun 1 '13 at 12:33
  • $\begingroup$ @Kolmin Thanks! I've added that to the answer more explicitly. $\endgroup$ – MarnixKlooster ReinstateMonica Jun 1 '13 at 17:08
2
$\begingroup$

I'll handle a different kind of goal statement first, namely: $P\implies Q$.

To prove this kind of statement you can opt between:

  1. Assume $P$ is true, $(\cdots)$, conclude $Q$.
  2. 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$.
  3. 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$.
  4. 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:

  1. Assume $\neg P$ to be true, $(\cdots)$, conclude $Q$ or assume $\neg Q$, $(\cdots)$, conclude $P$.
  2. 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:

  1. Suppose $P$ is true, $(\cdots)$, conclude $R$.
  2. 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.

$\endgroup$
  • 3
    $\begingroup$ Comment, downvoter? $\endgroup$ – Git Gud May 19 '13 at 11:40
  • $\begingroup$ Not too long ago I had difficulties proving a statement with $A \implies B \lor C$ (math.stackexchange.com/questions/71872/…) so this question is coming in real handy for me. I understand Hagen's method, but I don't understand your method. I can intuitively understand that assuming $A$ and $\neg B$ and then showing C makes sense as I must show this is the only result I can have if its $\neg B$. But I don't "see it" with yours. Care to elaborate more somehow? $\endgroup$ – user70962 May 19 '13 at 13:56
  • $\begingroup$ Btw, I've upvoted both answers as they just don't deserve to have downvotes. $\endgroup$ – user70962 May 19 '13 at 13:57
  • $\begingroup$ @BryanUrízar I'm not sure what you have problems with. Is it method $1$ or method $2$ (for the $P\lor Q$ goal)? I think it's $2$ you're having an issue with. That's simply a direct proof. $\endgroup$ – Git Gud May 19 '13 at 14:05
  • $\begingroup$ I don't understand both actually :( For 1, I don't see how it is enough to simply assume $P$ and show $Q$ or vice versa. To me it feels like I'm contradicting Hagen's way of doing so? As he'd assume $\neg P$ and using the premises deduce $Q$. For 2, I feel like I wouldn't have proved it completely. I realize that for example the statement $4$ is greater than $3$ or $5$ is true as $4 > 3$ and the later never holds but not assuming one to be false (like Hagen) I feel like it isn't exhaustive enough as it could very well be $P \lor Q \lor T \lor$..it's like only proving $A \implies P$, no? $\endgroup$ – user70962 May 19 '13 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.