Transcript m5zn_8a0e185bfba5c83

CS100 : Discrete Structures
Proof Techniques(1)
Dr.Saad Alabbad
Department of Computer Science
E-mail: [email protected]
Office # SR 068
Tel # 2581888
3/27/2016
Prepared by Dr.Saad Alabbad
1
Rules of Inference – Valid Arguments in
Propositional Logic
 Argument: An argument is a sequence of statements that
end with a conclusion.
 Valid: An argument is valid if and only if it is impossible for
all premises (preceding statements) to be true and the
conclusion to be false. By valid, we mean that the conclusion
of the argument must follow from the truth of the premises
of the argument.
 Consider the arguments:
“If you have a current password, then you can log onto the
network.”
“You have a current password.”
Therefore,
“You can log onto the network.”
3/27/2016
2
Rules of Inference – Valid Arguments in
Propositional Logic
 The conclusion “You can log onto the network” must be true
when the premises “If you have a current password, then
you can log onto the network” and “You have a current
password” are true.
 Let p= “You have a current password.”
and q=“You can log onto the network.” Then the argument
has the form
p→q
p
q
where  is the symbol that denotes “therefore.”
 The statement ((p → q) ⌃p) → q is a tautology.
3/27/2016
3
Rules of Inference – Rule for
Propositional Logic
The argument form with premises p1, p2, …., pn and
conclusion q is valid, when (p1⌃p2⌃….⌃pn) → q is a
tautology.
To show that an argument is valid, instead of showing
by truth table, we can establish the validity of some
relatively simple argument forms, called rules of
inference, which can be used as building blocks to
construct more complicated valid argument forms.
The tautology ((p → q) ⌃p) → q is the basis of the rule
of inference called modus ponens or law of
detachment.
3/27/2016
4
Rules of Inference – Rules for
Propositional Logic
 Example: Suppose that the conditional statement “If it
snows today, then we will go skiing” and its hypothesis “It is
snowing today”, are true. Then by modus ponens, it follows
that the conclusion of the conditional statement, “We will go
skiing” is true.
 Q1: Determine whether the argument given here is valid and
determine whether its conclusion must be true because of
the validity of the argument.
2
" If
3
3
2
2  , then ( 2 )    . We know that
2
2
3
2 .
2
2
9
3
Consequently , ( 2 ) 2  2     ."
4
2
3/27/2016
5
Rules of
Inference –
Rules for
Propositional
Logic
3/27/2016
6
Rules of Inference – Rule for
Propositional Logic
 Example: State which rule of inference is the basis of the
following argument: “It is below freezing now. Therefore, it
is either below freezing or raining now”.
 Sol: Let p= “It is below freezing now.” and q = “It is raining
now.” Then this argument is of the form:
p
p v q
This is an argument that uses the addition rule.
 Q2: State which rule of inference is the basis of the
following argument: “It is below freezing and raining now.
Therefore, it is below freezing”.
3/27/2016
7
Introduction to Proofs
 A theorem is a statement that can be shown to be
true (usually important statement)
 Less important theorem sometimes are called
propositions
 A proof is a sequence of statements (valid argument)
to show that a theorem is true
 The statements to be used in proofs include:
 Axioms (statement assumed to be true without
proof)

Ex: If x is positive integer then x+1 is positive integer.
 Hypothesis (premises) of the theorem
 Previously proven theorems
 Rules of inference used to draw conclusions and
to move from one step to another
3/27/2016
8
Introduction to Proofs
 A theorem is a statement that can be shown to be true (usually
important statement)
 Less important theorem sometimes are called propositions
 A proof is a sequence of statements (valid argument) to show
that a theorem is true
 The statements to be used in proofs include:
 Axioms (statement assumed to be true without proof)
 Ex:If x is positive integer then x+1 is positive integer.
 Hypothesis (premises) of the theorem
 Previously proven theorems
 Rules of inference used to draw conclusions and to move from
one step to another
Axioms
Hypothesis
proven theorems
3/27/2016
Rules of
inference
Prepared by Dr.Saad Alabbad
New theorem
9
Introduction to Proofs


1.
2.
3.
4.
5.
6.
7.
8.
9.
Example:
If I have a car (C) I will drive to Makkah(M). My boss gave me
40,000 (G) or Fired me(F). If I have SR40,000 (H) then I have
a car(C). My boss did not fire me. Therefore I will drive to
Makkah(M).
GF
Hypothesis
F
Hypothesis
G
Disjunctive syllogism rule using 1 and 2
GH
Axiom 
H C
Hypothesis
G C
Hypo. syllogism using 4,5
C
Modus ponens using 3 and 6
C M
Hypothesis
M
Modus ponens using 7 and 8
3/27/2016
Prepared by Dr.Saad Alabbad
10
Methods of proving theorems:
Direct proofs


1.
2.
3.
4.
5.
A direct proof of a conditional statement H1  H2 … Hn C is
established by assuming the truth of all hypothesis and using
rules of inference, axioms and proven theorems to assert the
truth of the conclusion
Example: prove that “if n is even then n2 is even”
Assume that n is even (hypothesis)
Therefore n=2k where k is integer (definition of even number)
By squaring n=2k we get n2=(2k)2=4k2=2(2k2)
Since 2K2 is integer (Axiom. See p.A-5)
Therefore n2=2r is even
3/27/2016
Prepared by Dr.Saad Alabbad
11
Methods of proving theorems:
Proof by contraposition
An indirect proof of a conditional statement p q is a direct
proof of its contraposition qp.
 Example 1: prove that “if n2 is even then n is even”
The contraposition is “if n is not even then n2 is not even”
1. Assume that n is not even i.e n is odd (hypothesis)
2. Therefore n=2k+1 where k is integer (definition of odd number)
3. By squaring n=2k+1 we get
 n2=(2k+1)2

=4k2+4k+1

=2(2k2+2k)+1= 2r+1
4. Since 2k2+2k is integer (Axiom. See p.A-5)
5. Therefore n2=2r+1 is not even (odd)

3/27/2016
Prepared by Dr.Saad Alabbad
12
Methods of proving theorems:
Proof by contraposition

Example 2: prove that if n=ab then an or bn where a and b
are positive integers
1. Let p be an , q be bn and r be n=ab
2. We want to prove that r pq
3.
The contraposition is (pq )   r (By definition)
4.
Which is equivalent to p  q  r (De Morgan’s law)
5.
6.
7.
Now assume that an and bn (p  q)
Then a.bn.n=n (by multiplying the two inequalities)
Therefore abn
8.
Which is the same as  r
3/27/2016
Prepared by Dr.Saad Alabbad
13
Methods of proving theorems:
Vacuous and Trivial Proofs

Vacuous Proof
If we know that p is false then pq is vacuously
true.
 Example 1: prove that if x20 then 1=2
where x is a real number
 Since x20 for every real number then
the implication is vacuously true
 Example 2: prove that if he is alive and he
is dead then the sun is ice cold.
 Since the hypothesis is always false the
implication is vacuously true.

Trivial Proof
If we know q is true then pq is trivially true.
 Example 1: prove that if x=2 then x2  0
for all real numbers
 Since x2  0 is true then the implication is
trivially true.(we didn’t use the fact x=2)
3/27/2016
Prepared by Dr.Saad Alabbad
p
q
pq
F
F
T
T
F
T
F
T
T
T
F
T
p
q
pq
F
F
T
T
F
T
F
T
T
T
F
T
14
Methods of proving theorems:
Proofs by Contradiction(1)


1.
In proof by contradiction it is shown that if some statement were
false, a logical contradiction occurs, hence the statement must be
true
Show that 2 is irrational
1.
Let p be 2 is irrational
Assume p is true “2 is rational”
1.
2.
3.
4.
5.
6.
7.
3/27/2016
Then 2=a/b where gcd(a,b)=1 , b0 and a0 (Definition of rational
numbers)
Squaring both sides we get 2=a2/b2
It follows that 2a2=b2
Hence b2 is even (Definition of even numbers)
Which means that b is even (Proved theorem. see slide 5)
But a2=b2/2=(2k)2/2=2k2 so a is even also (Definition of even numbers
and proved thoeorm)
But this is a contradiction since 7 and 8 contradict the fact that
gcd(a,b)=1 since if a and b are even then 2 is a common divisor.
Prepared by Dr.Saad Alabbad
15
Methods of proving theorems:
Proofs by Contradiction(2)



Why is this method valid ?
The contradiction forces us to reject our assumption because our other
steps based on that assumption are logical and justified. The only
“mistake” that we could have made was the assumption itself.
Be careful!

Sometimes the contradiction comes from a mistake in the steps of
the proof and not from the assumption. This makes the proof invalid.

Example: prove that 1=2
1.
Suppose that 21 and a=b for some a.
2.
Then 2b b
[multiply by b]
3.
a+b b
[2b=b+b=a+b by hypothesis]
4.
(a-b)(a+b)  b(a-b)
[multiply by a-b]
5.
a2-b2  ab-b2
6.
a2 ab
[subtract b2 from both sides]
7.
a b which contradicts our assumption that a=b
8.
Hence it follows that 1=2

Can you find the error 
3/27/2016
Prepared by Dr.Saad Alabbad
16
Methods of proving theorems:
Proofs by Contradiction(3)

To prove a conditional statement p  q by contradiction we prove
that p  q F is true which is equivalent to p  q .


Example:
If 3n+2 is odd then n is odd

Suppose that 3n+2 is odd and n is even [p  q] Then
1.
2.
3.
4.
5.
6.
7.
3/27/2016
n=2r
[hypothesis q and definition of even numbers]
3n=6r
[multiply 1 by 3]
3n+2=2+6r
[add 2 to both sides]
3n+2=2(1+3r)
3n+2=2k
[let k=1+3r]
Thus 3n+2 is even which is false (a contradiction !)
Therefore the implication is true.
Prepared by Dr.Saad Alabbad
17
Methods of proving theorems:
Proofs of Equivalence and Disproof by
counter example

Proofs of Equivalence
 To prove pq we have to prove p  q and q  p
 Example: prove “n is even if and only if n2 is even”



“if n is even then n2 is even” proved in slide 4
“n2 is even then n is even” proved in slide 5
Therefore, n is even if and only if n2 is even

Proving equivalence of several propositions
 If we want to prove that p1 p2  p3 …  pn
 Then it is sufficient to prove p1  p2,, p2  p3 … pn  p1

Disproof by Counterexample
 Prove that “For all real numbers x2>x” is false
 X=0.5 is a counterexample since 0.52>0.5 is not true
3/27/2016
Prepared by Dr.Saad Alabbad
18
Methods of proving theorems:
Exhaustive Proof and Proof by Cases(1)
Sometimes there is no single argument that works for all
possible cases appearing in the statement. So we have to
consider all different cases and/or instances .
 (1) Exhaustive Proof
In this type of proofs. All possible instances are relatively small. So
we prove each instance separately.
Example: Prove that (n+1)3 >= 3n if n is a positive integer with n 4.

We only have 4 instances to consider, n = 1, 2, 3, and 4.
Proof of case n = 1: (1+1)3 >= 31 i.e 4 >= 3 which is true.
Check n = 2, 3, and 4 similarly.


Notes
Human can perform exhaustive proofs with limited number of
possibilities. Computers can consider much larger number of
instances/cases. However
 Instances/cases must be finite and enumerable
3/27/2016
Prepared by Dr.Saad Alabbad
19
Methods of proving theorems:
Exhaustive Proof and Proof by Cases(2)
 (2) Proof by Cases
In this type of proofs. The proof covers each possible case. Each
case may cover an infinite number of instances
Example: Prove "if n is an integer then n2 >= n".
Case 1: n = 0. Since 02 = 0, 02 >= 0.
Case 2: n >= 1. n >= 1 implies n2 >= n.
Case 3: n <= -1. Since n is negative, n2 is positive, so n2 > n. .
 Question: prove that |xy|=|x||y|


Hint: Consider all 4 cases depending on whether x is positive
or x is negative and whether or not y is negative.
Common errors in with exhaustive proof and proof by cases:
 Draw conclusion from non-exhaustive examples
 Not covering all possible cases
3/27/2016
Prepared by Dr.Saad Alabbad
20
Methods of proving theorems:
Existence Proofs

Many theorems state that an object with certain
properties exists. I.e., xP(x) where P is a predicate. A
proof of such a theorem is called an EXISTENCE PROOF.
There are two kinds:
 (1) Constructive Existence Proof
The proof is established be giving example a such that P(a) is
true
Example: Prove "there is a positive integer that can be
written as the sum of cubes in two different ways."
Proof: consider 1729=103+93=123+13. Finding such
examples may require computer assistance.
Check n = 2, 3, and 4 similarly.
3/27/2016
Prepared by Dr.Saad Alabbad
21
Methods of proving theorems:
Existence Proofs
(2) Non-constructive Existence Proof
 The proof is established by showing that an object a with
P(a) is true must exist without explicitly demonstrating
one. Proofs by contradiction are usually used in such
cases.
 Example: Let x1,x2,..,xn be positive integers such that their
average is m. prove that there exists xi such that xi≥m
 Proof: suppose that there is no such number.i,e
x1m , x2m … xnm
By adding these inequalities we get: x1+ x2+…+ xn  nm
Dividing by n : (x1+ x2+…+ xn)/n  m
But since the average is defined as (x1+ x2+…+ xn)/n
Then we have mm which is a contradiction.
Therefore there must be a number xi such that xi≥m. But we can
not specify which number is that.
3/27/2016
Prepared by Dr.Saad Alabbad
22
Methods of proving theorems:
Uniqueness Proofs




Some theorems state that there is exactly one element with a
certain property.
A proof of such a theorem is called a UNIQUENESS PROOF.
Strategy here is (1) show that an element x with the desired
property exists (2) show that any other y (y != x) does not have
the property. I.e., if x and y both have the property, then x
must equal y.
Example: prove that the equation 3x+5=9 has a unique solution.
 (1) There exists a solution namely x=4/3
 (2) suppose that y and z are solutions then
3y+5=9=3z+5
So 3y=3z
Dividing by 3 we get y=z
This proves that the solution is unique
3/27/2016
Prepared by Dr.Saad Alabbad
23
END
3/27/2016
Prepared by Dr.Saad Alabbad
24