Proof Methods
CSI 2101: Discrete Structures
School of Electrical Engineering and Computer Science, University of Ottawa
January 28, 2022
Copyright By PowCoder代写 加微信 powcoder
Md. Hasan (uOttawa) Discrete Structures Ch1e MdH W22 January 28, 2022 1 / 6
Exhaustive Proof
Some theorems can be proved by examining a relatively small number of examples. Such proofs are called exhaustive proofs because these proofs proceed by exhausting all possibilities. An exhaustive proof is a special type of proof by cases where each case involves checking a single example.
Proving that (n + 1)3 ≥ 3n if n is a positive integer with n ≤ 4.
– We just need to verify it for n = 1,2,3, and 4.
Md. Hasan (uOttawa) Discrete Structures Ch1e MdH W22 January 28, 2022 2 / 6
Proofs (cont.)
Proof By Cases
A proof by cases must cover all possible cases that arise in a theorem.
Proving that if n is an integer, then n2 ≥ n.
– It can be proved for every integer by considering three cases: (i) n = 0, (ii) n ≥ 1, and (iii) n ≤ −1.
Md. Hasan (uOttawa) Discrete Structures Ch1e MdH W22 January 28, 2022 3 / 6
Existence Proofs
A proof of a proposition of the form ∃xP(x) is called an existence proof.
Sometimes an existence proof of ∃xP(x) can be given by finding an element a, called a witness, such that P(a) is true. This type of existence proof is called constructive.
An existence proof that does not find an element a such that P(a) is true is called nonconstructive. A proof by contradiction is a common method of giving a nonconstructive existence prove.
Md. Hasan (uOttawa) Discrete Structures Ch1e MdH W22 January 28, 2022 4 / 6
Interesting Problems
Fermat’s Last Theorem
The equation xn + yn = zn has no solutions in integers x, y, and z with
xyz ̸= 0 whenever n is an integer with n > 2. The 3x + 1 Conjecture
Let T be the transformation that sends an even integer x to x/2 and an odd integer to 3x + 1. For all positive integers x when we repeatedly apply the transformation T, we will eventually reach the integer 1.
Md. Hasan (uOttawa) Discrete Structures Ch1e MdH W22 January 28, 2022 5 / 6
Thank You!
Questions and Comments?
Md. Hasan (uOttawa) Discrete Structures Ch1e MdH W22 January 28, 2022 6 / 6
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com