First, let’s consider a conditional statement with a disjunction on the hypothesis side. To prove a statement of the form \((P_1 \lgcor P_2) \lgcimplies Q\text{,}\) we can use Fact 6.4.1 to decompose into two conditionals:
Appealing to the properties of conjunction, as in our discussion of reduction to cases, we see that we can prove \(P_1 \lgcimplies Q\) and \(P_2 \lgcimplies Q\) by separate proofs.
What about a conditional with a disjunction on the conclusion side? To prove a statement of the form \(P \lgcimplies (Q_1 \lgcor Q_2)\text{,}\) we can again reduce to cases, but in a sort of tricky way. For any statement, there are only two possibilities — either the statement is true or it is false. (See Basic Tautology 3 in Example 1.4.1. Apply this fact to one of the statements we are trying to prove.
Procedure6.5.1.Proof of conditional involving disjunction.
To prove a statement of the form \(P \lgcimplies (Q_1 \lgcor Q_2)\text{,}\) start by assuming that \(P\) is true and \(Q_1\) is false. Try to show that these assumptions lead to \(Q_2\) being true.
Idea6.5.2.
There are only two possibilities for \(Q_1\text{:}\) either it is true or it is false. If \(Q_1\) is true, then \(Q_1 \lgcor Q_2\) is already true, regardless of the truth values of \(P\) and \(Q_2\text{,}\) so there is nothing to prove in this case. On the other hand, if \(Q_1\) is false, the only way \(Q_1 \lgcor Q_2\) could be true is if \(Q_2\) is true.
Of course, you can swap the roles of \(Q_1\) and \(Q_2\) above: you could also start by assuming that \(P\) is true and \(Q_2\) is false, then try to show that this leads to \(Q_1\) being true.
Another strategy is to attempt a proof by contradiction (discussed in Section 6.9 below). By DeMorgan, \(\lgcnot(Q_1 \lgcor Q_2) \lgcequiv \lgcnot Q_1 \lgcand \lgcnot Q_2\text{,}\) so for this strategy, you should start by assuming that \(P\) is true and both\(Q_1\) and \(Q_2\) are false. Then, try to arrive at a contradiction.
Worked Example6.5.4.
Prove: Every odd number is either \(1\) more or \(3\) more than a multiple of \(4\text{.}\)
Let \(P(n)\) represent the predicate “\(n\) is odd”, let \(Q_1(n)\) represent the predicate “\(n\) is \(1\) more than a multiple of \(4\)”, and let \(Q_2(n)\) represent the predicate “\(n\) is \(3\) more than a multiple of \(4\)”, each with domain the integers.
Start by assuming that \(n\) is an odd number that is not\(1\) more than a multiple of \(4\text{.}\) We must now try to show that \(n\)is\(3\) more than a multiple of \(4\text{.}\) We know that \(n\) is odd, so there exists a number \(m\) such that \(n = 2m + 1\text{.}\) However, since \(n\) is not\(1\) more than a multiple of \(4\text{,}\)\(2m\) cannot be a multiple of \(4\text{,}\) and so \(m\) cannot be a multiple of \(2\text{.}\) Therefore, \(m\) is also odd, and so there exists another number \(\ell\) such that \(m = 2\ell + 1\text{.}\) Then
