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.
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.
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
