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 P Q and Q R are both true. Prove that P R is true. (Solution) Givens PQ QR P Goal R Proof. Suppose P. Since P , and P Q, it follows that Q . Then, since Q and Q R, it follows that R. Therefore, P R. (b) Suppose P Q and R Q are both true. Prove that P R is true. (Solution) Givens PQ R Q P Goal R Proof. Suppose P. Since P and P Q, it follows that Q . But then, since R Q, we can conclude R. Therefore, P R. (c) Suppose R ( P Q) is true. Prove that P (Q R) is true. (cf) Example 3.2.4. (Solution) By contrapositive law, P (Q R) is equivalent to P (R Q). So instead of showing the original statement, we will show the modified statement. Givens R ( P Q ) P R Goal Q Proof. Suppose P. Suppose R. Since R and R ( P Q), it follows P Q. Then since P and P Q, it follows that Q. Thus, R Q. Therefore, P (R Q), which is equivalent to P (Q R ). 2. Suppose A C , and B and C are disjoint. Prove that if x A then x B. (Solution) Givens AC B and C are disjoint. x A Goal xB Proof. Suppose x A. Since A C , it follows that x C. Now, since B and C are disjoint, it implies that B C . Therefore, we can conclude that if x C , x B. Thus, if x A, x B. 3. Use the method of proof by contradiction to prove the theorem in Example 3.2.1. (Solution) Example 3.2.1. Suppose A C B and a C. Prove that a A \ B. a A \ B is equivalent to (a A \ B) (definition of ), which is equivalent to (a A a B) (definition of \ ). Therefore, the negation of the above statement would be (a A a B), which is equivalent to a A and a B (double negation law), which is equivalent to a A \ B (definition of \ ). (Proof by contradiction) Suppose a A and a B. Since A C B, if a B then a A C. But then since a A, it follows that a C , which contradicts the fact that a C. Therefore, if A C B and a C , then a A \ B. 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 A B, a A, and a and b are not both elements of B. Prove that b B. (Proof by contradiction) Suppose b B. Since a A and A B, it follows that a B. But this contradicts the fact that a and b are not both elements of B. Therefore, b B. Thus, if A B, a A, and a and b are not both elements of B , then b B. 5. Consider the following incorrect theorem: Incorrect Theorem. Suppose x and y are real numbers and x y 10. Then x 3 and y 8. (a) What’s wrong with the following proof of the theorem? Proof. Suppose the conclusion of the theorem is false. Then x 3 and y 8. But then x y 11, which contradicts the given information that x y 10. Therefore the conclusion must be true. (Solution) The negation of the conclusion is x 3 or y 8, not x 3 and y 8. (b) Show that the theorem is incorrect by finding a counterexample. (Solution) Suppose y 7. Since x y 10, x 7 10, which leads to the conclusion x 3. Suppose x 2. Since x y 10, 2 y 10, which leads to the conclusion y 8. 6. Use truth tables to show that modus tollens is a valid rule of inference. (Solution) Modus tollens: If you know that both P and P Q are true, you can conclude that Q must also be true. P Q is equivalent to P Q (conditional law). (Truth Table: P Q , Compact Version) P T F T F F T F T T T F T Q F T F 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. Suppose P (Q R). Prove that R ( P Q). P (Q R) is equivalent to P (Q R) (conditional law). R ( P Q) is equivalent to R (P Q) (conditional law). (Truth Table: P (Q R ), Compact Version) ( P T F T T T F T T T F F T T F F T F T T T F T T T F T F F F T F T Q F F T T F F T T T T F T T T F T R) F T F T F T F T (Truth Table: R (P Q), Compact Version) ( R P F T F T T T F T F T F T T T F T F F T T T F T T T T T T T T T T F F T T Q) F F T T F F F T F T F F T T F F F F T T Applicable rows and the corresponding rows have been highlighted. (2) Exercise 1 (a) Suppose P Q and Q R are both true. Prove that P R is true. P Q is equivalent to P Q (conditional law). Q R is equivalent to Q R (conditional law). P R is equivalent to P R (conditional law). (Truth Table: P T F T F T F T F F T F T F T F T P Q, Q R, P R, Compact Version) Q Q R F T F F T T F T F T T T T F T F T F T F T T T T F T F F F T F T F T F T T F T F T F T F T T T T T T T T F F F F T T T T F T F T P F F F F T T T T R F T F T F T F T Applicable rows have been highlighted. (3) Example 1 (b) Suppose P Q and R Q are both true. Prove that P R is true. P Q is equivalent to P Q (conditional law). R Q is equivalent to R Q (conditional law). P R is equivalent to P R (conditional law). (Truth Table: P Q, R Q, P R, Compact Version) Q Q P R T F F T F T F T T T T F F F T T F T T T T F T T F F T T T T T F T F T F T T T F F T F T F T F F F T F T F F T T F F F T F T T T F F T F T T F T T F T F T F T F Applicable rows have been highlighted. P F F F F T T T T T T T T T F T F T F T F T F T F R F T F T F T F T (4) Example 1 (c) Suppose R ( P Q) is true. Prove that P (Q R) is true. R ( P Q) is equivalent to R (P Q) (conditional law). P (Q R) is equivalent to P (Q R) (conditional law). (Truth Table: R (P Q), Compact Version) ( R P F T F T T T F T F T F T T T F T F F T T T F T T F F T F T F T T T T T T T T F F T T F F T T F F Q) F F T T F F T T (Truth Table: P (Q R ), Compact Version) ( P T F T T T F T T T F F T T F F T F T T T F T T T F T F F F T F T Q F F T T F F T T T T F T T T F T R) F T F T F T F T Applicable rows and their corresponding rows have been highlighted. 8. Can the proof in Example 3.2.2 be modified to prove that if x 2 y 13 and x 3 then y 4 ? Explain. (Solution) Since x 3 and x 3 will both have the values of x 2 9, the contradiction will not be met. Proof? Suppose y 4. Then x 2 y x 2 4 13, which implies x 2 9. Taking the square root of both sides, we get x 3 or x 3. Since x 3 is given, x 3, but then this will not contradict the fact that x 3. Therefore, we have failed to prove that if x 2 y 13 and x 3 then y 4.

© Copyright 2018