Transcript Introduction to Proofs

Fall 2008/2009
The Foundations: Logic
and Proofs
Introduction to Proofs
I. Arwa Linjawi & I. Asma’a Ashenkity
1
Fall 2008/2009
Some terminology
 Theorem: is a statement that can be shown to
be true.
 Axioms (postulates): Statements that used in
a proof and are assumed to be true.
 Proof Methods
Proving pq
Direct proof: Assume p is true, and prove q.
Indirect proof: Assume q, and prove p.
Trivial proof: Prove q true.
Vacuous proof: Prove p is true
I. Arwa Linjawi & I. Asma’a Ashenkity
2
Fall 2008/2009
Direct proof
Proving pq
Direct proof: Assume p is true, and prove q
 Direct proofs lead from the hypothesis of a
theorem to the conclusion.
 They begin with the premises; continue with a
sequence of deductions, and ends with the
conclusion.
 Direct proof often reaches dead ends.
I. Arwa Linjawi & I. Asma’a Ashenkity
3
Fall 2008/2009
Direct proof
Definition 1:
The integer n is even if there exists an
integer k such that n=2k, and
n is odd if there exists an integer k such
that n=2k+1.
Axiom: Every integer is either odd or even
I. Arwa Linjawi & I. Asma’a Ashenkity
4
Fall 2008/2009
Direct proof
 Example 1:
Give direct proof that : Theorem : “If n is an odd integer,
then n2 is an odd integer”.
 Proof
 We assume that the hypothesis of this condition is true “ n is odd”
 n = 2k+1 for some integer k
 We want to show that n2 is odd ,
 thus n2 = (2k+1)2
 n2 = 4k2 + 4k + 1
 n2 = 2(2k2 + 2k) + 1
 Therefore n2 is of the form 2j + 1
 (with j the integer 2k2 + 2k), thus n2 is odd
I. Arwa Linjawi & I. Asma’a Ashenkity
5
Fall 2008/2009
Direct proof
 Example 2:
Give direct proof that : Theorem : “if m and n are both
perfect squares , then mn is also perfect squares”.
a is a perfect square when a= b2
 Proof
 We assume “m and n are both perfect squares”
 m = s2 and n=t2
 We want to show that mn is also perfect squares
 mn= s2 t2
 mn= (s t)2
 Therefore mn = x2 which x=st
 thus mn is also perfect squares from the definition
I. Arwa Linjawi & I. Asma’a Ashenkity
6
Fall 2008/2009
Direct proof
 Example
Prove that if n is an integer and 3n+2 is odd, then n is odd.
 We assume that 3n+2 is an odd integer
 This mean that 3n+2=2k+1
 There is no direct way to proof that n is odd integer (Direct
proof often reaches dead ends.)
I. Arwa Linjawi & I. Asma’a Ashenkity
7
Fall 2008/2009
Indirect proof
 We need other method of proving theorem of pq,
which is not direct
 which don’t start with the hypothesis and end with the
conclusion ( we call it indirect proof)
 Indirect proof (proof by contraposition): Assume q,
and prove p.
 Contraposition (pq  q  p)
 We take  q as hypothesis , and using axioms ,
definitions any proven theorem to follow p
I. Arwa Linjawi & I. Asma’a Ashenkity
8
Fall 2008/2009
Indirect proof
Example 3:
Prove that if n is an integer and 3n+2 is odd, then n is odd.
 Proof
 Suppose that the conclusion is false, i.e., that n is even (q)
 Then n=2k for some integer k.
 Then 3n+2 = 3(2k)+2 = 6k+2 = 2(3k+1).
 Thus 3n+2 is even, because it equals 2j for integer j = 3k+1.
 So 3n+2 is not odd p
 We have shown that ¬(n is odd)→¬(3n+2 is odd), thus its
contraposition (3n+2 is odd) → (n is odd) is also true.
I. Arwa Linjawi & I. Asma’a Ashenkity
Fall 2008/2009
Indirect proof
 Example 4:
Prove that if n=ab, where a and b are positive integers, then
a  √n or b  √n
Proof
 We assume that (a  √n or b  √n ) is false (q)
 (a  √ n  b  √n )
 (a > √n  b > √n ) we multiply these to obtain
 ab > √n √n.
 ab > n which ab ≠ n (p)
 The theorem is proved.
I. Arwa Linjawi & I. Asma’a Ashenkity
Fall 2008/2009
Trivial &Vacuous proofs
Vacuous proof
Proving pq
Vacuous proof: Prove p is true
Examples
Theorem: (For all n) If n is odd and even, then n2 = n + n.
Proof:
The statement “n is both odd and even” is necessarily
false, since no number can be both odd and even. So, the
theorem is vacuously true.
I. Arwa Linjawi & I. Asma’a Ashenkity
11
Fall 2008/2009
Trivial &Vacuous proofs
Trivial proof
Proving pq
Trivial proof: Prove q true.
Example
Theorem: (For integers n) If n is the sum of two prime
numbers, then either n is odd or n is even.
Proof:
Any integer n is either odd or even. So the conclusion of
the implication is true regardless of the truth of the
hypothesis. Thus the implication is true trivially.
This kind will be discuss in 4.1
I. Arwa Linjawi & I. Asma’a Ashenkity
12
Fall 2008/2009
Examples of Proof Methods
Definition 2:
The real number r is rational if there exist
integers p and q with q≠0 such that r =p/q.
A real number that is not rational is called
irrational
I. Arwa Linjawi & I. Asma’a Ashenkity
13
Fall 2008/2009
Examples Proof Methods
Example 7:
Theorem: Prove that the sum of two rational numbers is
rational.
 Proof
 assume that r and s are rational numbers
 r=p/q and s=t/u where p,q,t,u are integers and p≠0, u≠0
 r+s=(p/q)+(t/u) = (pu+qt)/(qu)
 Because p≠0 and u≠0, then qu≠0
 Both (pu+qt) and (qu) are integers
 Then the theorem is proved
 Note that :Our attempt to find direct proof succeeded
.Do example 8
I. Arwa Linjawi & I. Asma’a Ashenkity
14
Fall 2008/2009
Indirect Proof (Proof by
Contradiction)
we want to prove that if the negation of p ( which
is true ) conclude false , this means that we
prove the theorem .
Examples:
 Prove that √ 2 is irrational by giving a proof of
contradiction
p = “√2 is irrational “ , suppose that p is true
 Give a proof by contradiction that “ if 3n +2 is odd ,
then n is odd”
Let p be “3n+2 is odd“ and q be “n is odd“
We assume that (pq ) is true which means p q
is true ( as indirect example )
15
I. Arwa Linjawi & I. Asma’a Ashenkity