FIT2014 Lecture Notes - Lecture 4: Natural Number, Mathematical Induction, Mathematical Proof
28 Jun 2018
School
Department
Course
Professor
Lecture 4 Proof
- Proof by construction
- Proof by cases
- Proof by contradiction
- Proof by induction
Proof by construction (proof by example)
- An be used where the theorem assert the existence of some object with a specific property
o Just give the example, show it has property
- The example merely illustrates the idea of a proof , then it is not itself a proof
- Recall Lecture 1: English has a palindrome
Proof by cases (proof by exhaustion)
- Identify a number of different cases which cover all possibilities
- Divide all possibilities into a finite number of cases
- Prove the theorem for each of these cases
- Every English word has a vowel or a “y”.
Proof by contradiction
- Starting by assuming the negation of the statement you want to prove
- Deduce a contradiction
- Therefore, the statement must be true
- Not A implies false then it must be a true statement
Theorem
- The statement “ This statement is false” is not a proposition
- Proof:
- Assume that is a proposition, then it must be either true or false
- If it is true, then it is false
- If it is false, then it is true.
- So it is false if and only if it is true.
- This is a contradiction. So our assumption, that the statement is a proposition, must be false.
Proof by Induction
Recall de Morgan’s Law
¬(P ∨ Q) = ¬P ∧ ¬Q
¬(P ∧ Q) = ¬P ∨ ¬Q
¬(P1 ∨ … ∨ Pn) = ¬P1 ∧ … ∧ ¬Pn
The negation of the disjunction of the p1 to pn is the same of the conjunction of the negation
Theorm:
For all n : ¬(P1 ∨ … ∨ Pn) = ¬P1 ∧ … ∧ ¬Pn
First Proof
LHS is true…
if and only if P1 ∨ … ∨ Pn is False
if and only if P1 , …, Pn are all False
if and only if ¬P1, …, ¬Pn are all True
if and only if Right-Hand Side is True.
Let’s try for a different proof, using De Morgan’s Law.
Document Summary
An be used where the theorem assert the existence of some object with a specific property. Just give the example, show it has property. The example merely illustrates the idea of a proof , then it is not itself a proof. Identify a number of different cases which cover all possibilities. Divide all possibilities into a finite number of cases. Prove the theorem for each of these cases. E(cid:448)ery e(cid:374)glish (cid:449)ord has a (cid:448)o(cid:449)el or a (cid:862)y(cid:863). Starting by assuming the negation of the statement you want to prove. Not a implies false then it must be a true statement. The state(cid:373)e(cid:374)t (cid:862) this state(cid:373)e(cid:374)t is false(cid:863) is (cid:374)ot a propositio(cid:374) Assume that is a proposition, then it must be either true or false. If it is true, then it is false. If it is false, then it is true. So it is false if and only if it is true.
