How to Prove It

How To Prove It

3 Proofs

3.2 Proofs Involving Negations and Contradictions

1. This problem could be solved by using truth tables, but don’t do it that way. Instead, use the methods for writing proofs discussed so far in this chapter. (See Example 3.2.4.)

(a) Suppose andare both true. Prove that is true.

(Solution)

Givens / Goal

Proof.

Suppose

Sinceandit follows that Then, sinceandit follows that Therefore,

(b) Suppose and are both true. Prove thatis true.

(Solution)

Givens / Goal

Proof.

Suppose

Sinceandit follows that But then, sincewe can conclude Therefore,

(cf) Example 3.2.4.

(Solution)

By contrapositive law, is equivalent toSo instead of showing the original statement, we will show the modified statement.

Givens / Goal

Proof.

Suppose Suppose

Sinceandit follows Then sinceand it follows that Thus, Therefore,which is equivalent to

2. Suppose andandare disjoint. Prove that if then

(Solution)

Givens / Goal
andare disjoint.

Proof.

Suppose

Sinceit follows that

Now, since andare disjoint, it implies that

Therefore, we can conclude that if

Thus, if

3. Use the method of proof by contradiction to prove the theorem in Example 3.2.1.

(Solution)

Example 3.2.1. Suppose andProve that

is equivalent to (definition of ),

which is equivalent to(definition of ).

Therefore, the negation of the above statement would be which is equivalent to and (double negation law),

which is equivalent to (definition of).

(Proof by contradiction)

Supposeand

Sinceifthen

But then sinceit follows that which contradicts the fact that

Therefore, ifandthen

4. In Example 3.2.5, it was suggested that the proof of the theorem in that example could have been done by the method of proof by contradiction. Do it that way.

(Solution)

Example 3.2.5. Suppose andandare not both elements ofProve that

(Proof by contradiction)

Suppose

Since andit follows that But this contradicts the fact that andare not both elements ofTherefore, Thus, if andandare not both elements ofthen

5. Consider the following incorrect theorem:
Incorrect Theorem. Suppose and are real numbers and Thenand

(a) What’s wrong with the following proof of the theorem?
Proof. Suppose the conclusion of the theorem is false. Then andBut then which contradicts the given information that Therefore the conclusion must be true.

(Solution)

The negation of the conclusion is ornotand

(b) Show that the theorem is incorrect by finding a counterexample.

(Solution)

Suppose Since which leads to the conclusion

6. Use truth tables to show that modus tollens is a valid rule of inference.

(Solution)

Modus tollens: If you know that bothandare true, you can conclude thatmust also be true.

is equivalent to(conditional law).

(Truth Table:, Compact Version)

T / F / T / F
T / F / T / T
F / T / F / F
F / T / T / T

Applicable line is highlighted.

7. Use truth tables to check the correctness of the theorem in Example 3.2.4 and the statement in exercise 1.

(Solution)

(1) Example 3.2.4. SupposeProve that

is equivalent to (conditional law).

is equivalent to(conditional law).

(Truth Table: Compact Version)

T / F / T / T / F / T / F
T / F / T / T / F / T / T
T / F / T / F / T / F / F
T / F / T / F / T / T / T
F / T / T / T / F / T / F
F / T / T / T / F / T / T
F / T / F / F / T / F / F
F / T / T / F / T / T / T

(Truth Table: Compact Version)

F / T / T / F / T / T / F
T / T / T / F / T / T / F
F / T / T / F / T / F / T
T / T / T / F / T / F / T
F / T / F / T / T / T / F
T / T / F / T / T / T / F
F / F / F / T / F / F / T
T / T / F / T / F / F / T

Applicable rows and the corresponding rows have been highlighted.

(2) Exercise 1 (a) Suppose andare both true. Prove that is true.

is equivalent to(conditional law).

(Truth Table: Compact Version)

T / F / T / F / T / F / T / F / T / F / T / F
T / F / T / F / T / F / T / T / T / F / T / T
T / F / T / T / F / T / F / F / T / F / T / F
T / F / T / T / F / T / T / T / T / F / T / T
F / T / F / F / T / F / T / F / F / T / F / F
F / T / F / F / T / F / T / T / F / T / T / T
F / T / T / T / F / T / F / F / F / T / F / F
F / T / T / T / F / T / T / T / F / T / T / T

Applicable rows have been highlighted.

(3) Example 1 (b) Suppose and are both true. Prove thatis true.

is equivalent to(conditional law).

is equivalent to (conditional law).

is equivalent to(conditional law).

(Truth Table: Compact Version)

T / F / T / F / T / F / T / T / F / T / F / T / T / F
T / F / T / F / F / T / T / T / F / T / F / T / F / T
T / F / T / T / T / F / T / F / T / T / F / T / T / F
T / F / T / T / F / T / F / F / T / T / F / T / F / T
F / T / F / F / T / F / T / T / F / F / T / T / T / F
F / T / F / F / F / T / T / T / F / F / T / F / F / T
F / T / T / T / T / F / T / F / T / F / T / T / T / F
F / T / T / T / F / T / F / F / T / F / T / F / F / T

Applicable rows have been highlighted.

(4) Example 1 (c) Suppose is true. Prove that is true.

is equivalent to(conditional law).

is equivalent to (conditional law).

(Truth Table: Compact Version)

Applicable rows and their corresponding rows have been highlighted.

8. Can the proof in Example 3.2.2 be modified to prove that ifandthenExplain.

(Solution)

Sinceand will both have the values of the contradiction will not be met.

Proof?

Suppose Then which implies Taking the square root of both sides, we get or Since is given,but then this will not contradict the fact that Therefore, we have failed to prove that ifandthen