Understanding what constitutes a sound mathematical argument—that is, a proof—is essential to understanding written mathematics. This necessitates an understanding of proof-building strategies. The strategies for creating proofs that we will examine are also applied in other areas of computer science, including the principles that computers use to reason, the methods for confirming the accuracy of programs, etc. In mathematics, a lot of theorems are implications: p → q. Different methods of evidence arise from different ways of proving implications.
DIRECT PROOF
The implication p →q can be proved by showing that if p is true, the q must also be true. This shows that the combination p true and q false never occurs. A proof of this kind is called a direct proof.
| p | q | p → q |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | F |
SOME BASICS
- An integer n is even if, and only if, n = 2k for some integer k.
- An integer n is odd if, and only if, n = 2k + 1 for some integer k.
- An integer n is prime if, and only if, n > 1 and for all positive integers r and s, if n = r·s, then r = 1 or s = 1.
- An integer n > 1 is composite if, and only if, n = r·s for some positive integers r and s with r ≠ 1 and s ≠ 1.
- A real number r is rational if, and only if, a b for some integers a and b with b≠0.
- If n and d are integers and d ≠0, then d divides n, written d | n if, and only if, n = d.k for some integers k.
- An integer n is called a perfect square if, and only if, n = k2 for some integer k.
EXERCISE
Prove that the sum of two odd integers is even.
SOLUTION
Let m and n be two odd integers. Then by definition of odd numbers
m = 2k + 1 for some k ∈Z
n = 2l + 1 for some l ∈ Z
Now m + n = (2k + 1) + (2l + 1)
= 2k + 2l + 2
= 2 (k + l + 1)
= 2r where r = (k + l + 1) ∈Z
Hence m + n is even.