EF Statements involving disjunction

Section 6.5 Statements involving disjunction

First, let’s consider a conditional statement with a disjunction on the hypothesis side. To prove a statement of the form

(P_{1} \lor P_{2}) \Rightarrow Q,

we can use Fact 6.4.1 to decompose into two conditionals:

(P_{1} \lor P_{2}) \to Q \Leftrightarrow (P_{1} \to Q) \land (P_{2} \to Q) .

🔗

Appealing to the properties of conjunction, as in our discussion of reduction to cases, we see that we can prove

P_{1} \Rightarrow Q

and

P_{2} \Rightarrow Q

by separate proofs.

🔗

What about a conditional with a disjunction on the conclusion side? To prove a statement of the form

P \Rightarrow (Q_{1} \lor Q_{2}),

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.

🔗

Procedure 6.5.1. Proof of conditional involving disjunction.

🔗

To prove a statement of the form

P \Rightarrow (Q_{1} \lor Q_{2}),

start by assuming that

P

is true and

Q_{1}

is false. Try to show that these assumptions lead to

Q_{2}

being true.

🔗

Idea 6.5.2.

🔗

There are only two possibilities for

Q_{1} :

either it is true or it is false. If

Q_{1}

is true, then

Q_{1} \lor Q_{2}

is already true, regardless of the truth values of

P

and

Q_{2},

so there is nothing to prove in this case. On the other hand, if

Q_{1}

is false, the only way

Q_{1} \lor Q_{2}

could be true is if

Q_{2}

is true.

🔗

Note 6.5.3.

🔗

🔗
Also see Exercise 2.5.3.
🔗
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, $\neg (Q_{1} \lor Q_{2}) \Leftrightarrow \neg Q_{1} \land \neg Q_{2},$ 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 Example 6.5.4.

🔗

Prove: Every odd number is either

1

more or

3

more than a multiple of

4 .

Solution.

Let

P (n)

represent the predicate “

n

is odd”, let

Q_{1} (n)

represent the predicate “

n

1

more than a multiple of

4

”, and let

Q_{2} (n)

represent the predicate “

n

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 .

We must now try to show that

n

3

more than a multiple of

4 .

We know that

n

is odd, so there exists a number

m

such that

n = 2 m + 1 .

However, since

n

is not

1

more than a multiple of

4,

2 m

cannot be a multiple of

4,

and so

m

cannot be a multiple of

2 .

Therefore,

m

is also odd, and so there exists another number

ℓ

such that

m = 2 ℓ + 1 .

Then

n = 2 m + 1 = 2 (2 ℓ + 1) + 1 = 4 ℓ + 3,

which says that

n

3

more than a multiple of

4,

as desired.

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results:

Section 6.5 Statements involving disjunction

Procedure 6.5.1. Proof of conditional involving disjunction.

Idea 6.5.2.

Note 6.5.3.

Worked Example 6.5.4.