Transcript ICS 353: Design and Analysis of Algorithms

1
King Fahd University of Petroleum & Minerals
Information & Computer Science Department
ICS 253: Discrete Structures I
Summer Semester 2010 - 2011 (103)
Dr. Wasfi G. Al-Khatib
SUMT: 12:45-2:00pm - 24:158
103 ICS 253: Discrete Structures I
2
The Foundations: Logic and Proofs
Reading Assignment
• K. H. Rosen, Discrete Mathematics and Its
Applications, 6th Ed., McGraw-Hill, 2006.
• Chapter 1, Sections 1-6
103 ICS 253: Discrete Structures I
•
3
The Foundations: Logic and Proofs
Section 1.1: Propositional Logic
Traditionally, logic distinguishes valid and invalid
arguments (2-valued logic).
• Is there other types of logic?
•
The building blocks of logic are propositions. A
proposition is a declarative statement that is either
true or false
1. Dr. Wasfi holds a Ph.D. in arts.
2. KFUPM is either a big University or a small University.
3. Do you have a van?
4. 82 = 16.
5. I will go fishing tomorrow.
6. Do not drive while you are asleep.
7. X – 8 = 12
103 ICS 253: Discrete Structures I
4
The Foundations: Logic and Proofs
Compound Propositions
• Compound propositions are formed from
single propositions using logical operators
•
•
•
•
•
•
Negation
Conjunction
Disjunction
Exclusive or
Implication
biconditional
103 ICS 253: Discrete Structures I
5
The Foundations: Logic and Proofs
Truth Tables
• A truth table displays the relationship
between the truth values of propositions
• Usually we are interested in knowing the
compound truth value of ALL possible truth
values of the “input” propositions
6
103 ICS 253: Discrete Structures I
The Foundations: Logic and Proofs
Truth table for negation p
p
T
F
p
103 ICS 253: Discrete Structures I
7
The Foundations: Logic and Proofs
Truth Table for Conjunction p  q
103 ICS 253: Discrete Structures I
8
The Foundations: Logic and Proofs
Truth Table for Disjunction p  q
103 ICS 253: Discrete Structures I
9
The Foundations: Logic and Proofs
Truth Table for Exclusive Or p  q
103 ICS 253: Discrete Structures I
10
The Foundations: Logic and Proofs
Truth Table for Implication p  q
103 ICS 253: Discrete Structures I
11
The Foundations: Logic and Proofs
Implication p  q
• Implication is expressed in many ways
•
•
•
•
•
•
•
If p then q
p is sufficient for q
a sufficient condition for q is p
q is necessary for p
a necessary condition for p is q
p only if q
q follows from p
•
•
•
•
•
•
If p, q
p implies q
q whenever p
q when p
q if p
q unless  p
103 ICS 253: Discrete Structures I
12
The Foundations: Logic and Proofs
Implication p  q
• Discuss the validity of the following
statements:
• If today is Friday, then 2 + 3 = 5
• If today is Friday, then 2 + 3 = 6
• Note that “if … then” in programming
languages is different from the one used in
logic.
103 ICS 253: Discrete Structures I
13
The Foundations: Logic and Proofs
Converse, Contrapositive and Inverse
• Converse of an implication
• qp
• Contrapositive of an implication
• qp
• Inverse of an implication
• pq
103 ICS 253: Discrete Structures I
14
The Foundations: Logic and Proofs
Truth Table for Bi-conditional p  q
103 ICS 253: Discrete Structures I
15
The Foundations: Logic and Proofs
Translating English Sentences into Logical
Expressions
•
Removes ambiguity
• May introduce certain assumptions
•
Identify “single” propositions and then write the
logical expressions corresponding to the
following compound propositions (Q10 pp 17):
1. You get an A on the final, you do every exercise in this
book, and you get an A in this class.
2. To get an A in this class, it is necessary for you to get
an A on the final.
3. Getting an A on the final and doing every exercise in
this book is sufficient for getting an A in this class.
103 ICS 253: Discrete Structures I
16
The Foundations: Logic and Proofs
Translating English Sentences into Logical
Expressions
• Example 13 Page 11: You cannot ride the
roller coaster if you are under 4 feet tall
unless you are older than 16 years old
103 ICS 253: Discrete Structures I
17
The Foundations: Logic and Proofs
Translating English Sentences into Logical
Expressions
• Q 16 page 18: For each of these sentences,
determine whether an inclusive or an
exclusive or is intended. Explain your answer
a. Experience with C++ or Java is required
b. Lunch includes soup or salad
c. To enter the country, you need a passport or a
voter registration card
d. Publish or perish
103 ICS 253: Discrete Structures I
18
The Foundations: Logic and Proofs
System Specifications
• System specifications should be consistent, i.e. not
contain conflicting requirements
• i.e. all “requirements” are true
• (Q51 pp20).
• The router can send packets to the edge system only if it
supports the new address space.
• For the router to support the new address space, it is
necessary that the latest software release be installed.
• The router can send packets to the edge system if the
latest software release is installed.
• The router does not support the new address space.
103 ICS 253: Discrete Structures I
19
The Foundations: Logic and Proofs
Logic and Bit Operations
• Computers represent information using bits
• A bit string is a sequence of zero or more bits.
• 0 represents F and 1 represents T
• How does C represent True and False??????
• Bit operations are carried out in exactly the same
manner as their corresponding logic operations.
• Evaluate 0001110001  1001001000
103 ICS 253: Discrete Structures I
20
The Foundations: Logic and Proofs
Section 1.2: Propositional Equivalences
• Tautology: A compound proposition that is
always true, regardless of the truth values
of the single/simple propositions in it.
• Propositions p and q are called logically
equivalent if pq is a tautology, denoted by
pq
• Contradiction: A compound proposition
that is always false.
• Contingency:
103 ICS 253: Discrete Structures I
21
The Foundations: Logic and Proofs
Example
• Show that the following proposition is a
tautology:
(pq)  p  q
p
q
T
T
T
F
F
T
F
F
pq
(pq) 
(pq) p q p  q
p  q
103 ICS 253: Discrete Structures I
22
The Foundations: Logic and Proofs
Some Useful Equivalences
Identity
pT  p
Laws
pF  p
Domination
pT  T
Laws
pF  F
Idempotent
pp  p
Laws
pp  p
pq  qp Commutative
Laws
pq  qp
Double
(p)  p
Negation Law
(pq)r  p(qr)
Associative
(pq)r  p(qr)
Laws
(pq)  pq
DeMorgan
(pq)  pq
Laws
p(qr)(pq)(pr)
Distributive
p(qr)(pq)(pr)
Laws
p  p  T
p  p  F
Other
Useful
(p  q)  (pq)
Laws
103 ICS 253: Discrete Structures I
23
The Foundations: Logic and Proofs
Why Know These Equivalences?
• Instead of using truth tables, we can use
these equivalences to arrive to the same
conclusion
• Any good reasons for not using truth tables?
103 ICS 253: Discrete Structures I
24
The Foundations: Logic and Proofs
Examples
• Show that (p(pq))  (p q)
• Show that (pq)  (pq)  (p q)
• Show that (pq)r is not equivalent to
p(q r)
103 ICS 253: Discrete Structures I
25
The Foundations: Logic and Proofs
Section 1.3: Predicates and
Quantifiers
• Propositional logic, studied in Sections 1.1 and
1.2 cannot adequately express the meaning of
statements in mathematics and in natural
language.
• E.g., suppose that we know that “Every student at
KFUPM has a computer account.” Are there any rules
in propositional logic that can make us conclude the
truth of the statement that “Ahmad, who is a student at
KFUPM, has a computer account”
26
103 ICS 253: Discrete Structures I
The Foundations: Logic and Proofs
Predicates
• Predicates refer to a property that the subject(s)
(variable(s)) of the statement has/have.
• Once value(s) has/have been assigned to the
variable(s), the predicate becomes a proposition.
• Examples
•
•
•
•
P(x)  x > 1
Q(x,y)  x = y – 5
R(x,y,z)  z > x – y
if P(x) then
x = x - 1;
else
x = x2;
end if;
103 ICS 253: Discrete Structures I
27
The Foundations: Logic and Proofs
Quantifiers
• Universal quantification of P(x) is the
proposition “P(x) is true for all values of x in
the universe of discourse (domain of x)”
which is denoted by
x P(x)
• Existential quantification of P(x) is the
proposition: “There exists an element x in the
universe of discourse (domain of x) such that
P(x) is true” which is denoted by
x P(x)
103 ICS 253: Discrete Structures I
28
The Foundations: Logic and Proofs
Quantifiers
• Uniqueness quantifier of P(x) is the
proposition that “there exists a unique
element x, in the domain of x, such that P(x)
is true,” which is denoted by
!x P(x).
103 ICS 253: Discrete Structures I
29
The Foundations: Logic and Proofs
Examples
• Express the following statement using proper
quantification
•
Every student in this class has studied calculus
• Question 9 pp 47
•
•
•
P(x)  x can speak Russian
Q(x)  x knows C++
For the universe of discourse “all students at your school”
•
•
•
•
There is a student at your school who can speak Russian and who
knows C++
There is a student at your school who can speak Russian but who
doesn’t know C++
Every student at your school either can speak Russian or knows C++
No student at your school can speak Russian or knows C++
103 ICS 253: Discrete Structures I
30
The Foundations: Logic and Proofs
Scientific Joke
• An astronomer, a physicist and a mathematician (it is said)
were holidaying in Scotland. Glancing from a train window,
they observed a black sheep in the middle of a field.
• The astronomer said: "How interesting, all scottish sheep are
black!"
• To which the physicist responded, "No, no! Some Scottish
sheep are black!"
• The mathematician gazed heavenward in supplication, and
then intoned, "In Scotland there exists at least one field,
containing at least one sheep, at least one side of which is
black."
103 ICS 253: Discrete Structures I
31
The Foundations: Logic and Proofs
Truth of Quantifiers
Statement
x P(x)
x P(x)
!x P(x)
When True?
When False?
32
103 ICS 253: Discrete Structures I
The Foundations: Logic and Proofs
Precedence of Quantifiers and
Logical Operators
Operator
Precedence
,
1

2

3

4

5

6
103 ICS 253: Discrete Structures I
33
The Foundations: Logic and Proofs
• The quantifiers  and  have higher
precedence than all logical operators from
propositional calculus.
• E.g., x P(x)  Q(x)
• means………………………..
• does not mean ……………………
103 ICS 253: Discrete Structures I
34
The Foundations: Logic and Proofs
Binding Variables
• The occurrence of a variable x is bound iff a value is
assigned to x or when a quantifier is used on x.
Otherwise, it is called free.
•
x Q ( x, y )
•
x P ( x )  Q ( x )    x R ( x ) 
103 ICS 253: Discrete Structures I
35
The Foundations: Logic and Proofs
Logical Equivalences Involving Quantifiers
• Statements involving predicates and
quantifiers are logically equivalent if and
only if they have the same truth value no
matter which predicates are substituted into
these statements and which domain of
discourse is used for the variables in these
propositional functions.
103 ICS 253: Discrete Structures I
36
The Foundations: Logic and Proofs
Logical Equivalences Involving Quantifiers
• Q 46 pp 49.
37
103 ICS 253: Discrete Structures I
The Foundations: Logic and Proofs
Negation
•  x P(x)  x P(x)
•  x P(x)  x P(x)
• These are called De Morgan’s Laws for
Quantifiers
• Find the negation of
• There is an honest politician
• x x 2  x


103 ICS 253: Discrete Structures I
38
Examples
•
•
•
•
•
Q 21 pp 47
Q23 pp 48
Q28 pp 48
Q31 pp 48
Q33 pp 48
The Foundations: Logic and Proofs
103 ICS 253: Discrete Structures I
39
The Foundations: Logic and Proofs
Question 59 pp. 50
•
P(x) = “x is a professor”
Q(x) = “x is ignorant”
R(x) = “x is vain”
Express the following statements using
quantifiers; logical connectives; and P(x), Q(x),
and R(x) where the universe of discourse is the
set of all people
1.
2.
3.
4.
No professors are ignorant
All ignorant people are vain
No professors are vain
Does (3.) follow from (1.) and (2.)? If not, is there a
correct conclusion?
103 ICS 253: Discrete Structures I
40
The Foundations: Logic and Proofs
Prolog: Programming in Logic
• Prolog Facts: Define predicates by specifying
the elements that satisfy these predicates
• Prolog Rules: Define new predicates from
prolog facts.
41
103 ICS 253: Discrete Structures I
The Foundations: Logic and Proofs
Example
Facts
instructor(Wasfi, ics253).
instructor(Yahya, ics324).
instructor(Marwan,coe202).
enrolled(991101, ics253).
enrolled(200111, ics324).
enrolled(981101, coe202).
enrolled(200123, coe202).
enrolled(991101, ics253).
enrolled(200123, ics324).
enrolled(991101, coe202).
enrolled(200111, ics253).
Queries
instructor(Wasfi, ics324)
enrolled(X, coe202)
teaches(X, 200123)
Rule
Teaches(P, S) :- instructor(P, C), enrolled(S, C)
103 ICS 253: Discrete Structures I
42
The Foundations: Logic and Proofs
Section 1.4: Nested Quantifiers
• Nested Quantifiers: Quantifiers that occur
within the scope of other quantifiers
• Examples
• xy (x + y = 0)
• You can think of it as xQ(x) where Q(x) is y P(x,y)
where P(x,y) is x + y = 0.
• xy (x + y = y + x)
• Does this remind you of nested loops????
103 ICS 253: Discrete Structures I
43
The Foundations: Logic and Proofs
Understanding Nested
Quantification
• Determine whether the following statements
are true or false:
•
•
•
•
•
•
x y (x > y) (domain of discourse is R)
x y (x > y) (domain of discourse is N)
x y (x < y) (domain of discourse is Z)
x y (x > y) (domain of discourse is Q)
x y (x < y) (domain of discourse is N)
x y (x < y) (domain of discourse is Z)
103 ICS 253: Discrete Structures I
44
The Foundations: Logic and Proofs
The Order of Quantifiers
• The order of quantifiers is important unless
all the quantifiers are universal or all the
quantifiers are existential.
• Let Q(x,y) denote “x + y = 0”. What are the
truth values of the quantifications
• x y Q(x,y)
• y x Q(x,y)
103 ICS 253: Discrete Structures I
45
The Foundations: Logic and Proofs
Quantifications of Two Variables
103 ICS 253: Discrete Structures I
46
The Foundations: Logic and Proofs
Example
• Question 6 page 58: Let C(x,y) mean that x is
enrolled in y, where the universe of discourse for x
is the set of all students in your school and the
universe of discourse for y is the set of classes
being given at your school. Express each of the
following statements by a simple English
sentence.
•
•
•
•
•
•
C(Randy Goldberg, CS252)
x C(x, Math 695)
y C(Carol Sitea, y)
x ( C(x, Math 222)  C(x, CS 252))
x y z ( (x  y)  (C(x,z)  C(y,z)) )
x y z ((x  y)  (C(x,z)  C(y,z)) )
103 ICS 253: Discrete Structures I
•
47
The Foundations: Logic and Proofs
Translating Mathematical
Statements
Using
Quantifiers
Q19 Page 60 Express each of these statements
using mathematical and logical operators,
predicates, and quantifiers, where the domain
consists of all integers.
a) The sum of two negative integers is negative.
b) The difference of two positive integers is not
necessarily positive.
c) The sum of the squares of two integers is greater
than or equal to the square of their sum.
d) The absolute value of the product of two
integers is the product of their absolute values.
103 ICS 253: Discrete Structures I
48
The Foundations: Logic and Proofs
More Examples
• Question 26 page 61: Q(x,y)”x+y=x-y”
Using the set of integers as a universe of
discourse, what are the truth values of the
following
• Q(1,1)
• Q(2,0)
• y Q(1,y)
• x Q(x,2)
• What is the truth values of x P(x) and x
P(x) where P(x) is the statement “x2 > 10”
and the universe of discourse is the set of
positive integers not exceeding 4?
103 ICS 253: Discrete Structures I
The Foundations: Logic and Proofs
49
More Examples
• What is the truth value of the following
statements
• x y (x < y)
• xy z (xy = z)
x,y 
x,y,z 
103 ICS 253: Discrete Structures I
50
The Foundations: Logic and Proofs
Negating Nested Quantifiers
• Apply negation rules “successively”
• Example (Question 33[b,d] pp. 61 ): Rewrite
each of the following statements so that
negations appear only within predicates
•  y x P(x,y)
•  ( x y  P(x,y)  x y Q(x,y) )
103 ICS 253: Discrete Structures I
51
The Foundations: Logic and Proofs
Translating Sentences into Logical Expressions
• Q9 pp 59: Let L(x,y) be the statement “x loves y”, where
the domain for both x and y consists of all people in the
world.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Everybody loves Jerry.
Everybody loves somebody.
There is somebody whom everybody loves.
Nobody loves everybody.
There is somebody whom Lydia does not love.
There is somebody whom no one loves.
There is exactly one person whom everybody loves.
There are exactly two people whom Lynn loves.
Everyone loves himself or herself
There is someone who loves no one besides himself or
herself
103 ICS 253: Discrete Structures I
52
The Foundations: Logic and Proofs
Section 1.5: Rules of Inference
• Proofs in mathematics are valid arguments
that establish the truth of a mathematical
statements
• An argument is a sequence of statements that end
with a conclusion.
• Valid means the conclusion must follow from
the truth of the preceding statements (premises)
of the argument.
103 ICS 253: Discrete Structures I
53
The Foundations: Logic and Proofs
Valid Arguments in Propositional
p
Logic
• “If you have a current password, then
you can log onto the network” q
• “You have a current password”
• Therefore, “You can log onto the network.”
• Is this a valid argument?
pq
• Note that both pq and p are true
p
q
103 ICS 253: Discrete Structures I
54
The Foundations: Logic and Proofs
Definitions
• An argument in propositional logic is a sequence of
propositions. All but the final proposition in the
argument are called premises and the final proposition
is called the conclusion.
• An argument is valid if the truth of all its premises
implies that the conclusion is true.
• An argument form in propositional logic is a sequence
of compound propositions involving propositional
variables.
• An argument form is valid if no matter which
particular propositions are substituted for the
propositional variables in its premises, the conclusion
is true if the premises are all true.
103 ICS 253: Discrete Structures I
55
The Foundations: Logic and Proofs
Valid Arguments in Propositional
Logic
 p  q  p  q
• Note that
is a tautology.
• From the previous definition, an argument form
with premises p1, p2, …, pn and conclusion q is
valid when (p1p2…pn  q) is a tautology.
• This rule of inference is called
modus ponens
pq
p
q
103 ICS 253: Discrete Structures I
The Foundations: Logic and Proofs
56
Valid Arguments in Propositional
Logic
• A valid argument form can lead to incorrect
conclusions if one or more false propositions are
used
3 , then
2
2
3
2
2
• If

 
2
 
3
2  
2
2
9
3
2  2      2.25
4
2
2
2
103 ICS 253: Discrete Structures I
57
The Foundations: Logic and Proofs
Some Important Rules of Inference
Tautology
Rule of Inference Name
p  ( p  q)
Addition
( p  q)  p
Simplification
(( p ) ( q ))  ( p  q )
Conjunction
[ p  ( p  q )]  q
Modus ponens
[  q  ( p  q )]   p
Modus tollens
[( p  q )  ( q  r )]  ( p  r )
Hypothetical syllogism
[( p  q )   p ]  q
Disjunctive syllogism
[  p  q    p  r ]  q  r 
Resolution
103 ICS 253: Discrete Structures I
58
The Foundations: Logic and Proofs
Examples for Use of Rules of
Inference
• Q2 pp 72: Find the argument form for the
following argument and determine whether it
is valid. Can we conclude that the conclusion
is true if the premises are true?
• If George does not have eight legs, then he is not
an insect.
George is an insect.
 George has eight legs.
103 ICS 253: Discrete Structures I
59
The Foundations: Logic and Proofs
Examples for Use of Rules of
Inference
Q4 pp 72: What rule of
inference is used in each argument?
•
a) Kangaroos live in Australia and are marsupials. Therefore,
kangaroos are marsupials.
b) It is either hotter than 100 degrees today or the pollution is
dangerous. It is less than 100 degrees outside today. Therefore,
the pollution is dangerous.
c) Linda is an excellent swimmer. If Linda is an excellent swimmer,
then she can work as a lifeguard. Therefore, Linda can work as a
lifeguard.
d) Steve will work at a computer company this summer. Therefore,
this summer Steve will work at a computer company or he will be
a beach bum.
e) If I work all night on this homework, then I can answer all the
exercises. If I answer all the exercises, I will understand the
material. Therefore, if I work all night on this homework, then I
will understand the material.
103 ICS 253: Discrete Structures I
60
The Foundations: Logic and Proofs
Using Rules of Inference to Build
Arguments
• Q6 pp 72: Use rules of inference to show that
the hypotheses "If it does not rain or if it is
not foggy, then the sailing race will be held
and the lifesaving demonstration will go on,"
"If the sailing race is held, then the trophy
will be awarded,” and "The trophy was not
awarded" imply the conclusion "It rained."
103 ICS 253: Discrete Structures I
The Foundations: Logic and Proofs
61
Resolution
• Rule of inference used in many computer
programs (Prolog, Automatic Theorem
Proving, …)
• ((p  q)  (p  r))  q  r
resolvent
103 ICS 253: Discrete Structures I
62
The Foundations: Logic and Proofs
Fallacies
• Fallacies resemble rules of inference but are
based on contingencies rather than tautologies
• For example
[p  ( p  q )] q
[q  ( p  q )] 
p
103 ICS 253: Discrete Structures I
63
The Foundations: Logic and Proofs
Rules of Inference for Quantified
U is the Universe of Discourse Statements
Rule of Inference
Name
 xP( x )
 P ( c ) if c  U
Universal
instantiation
P ( c ) for an arbitrary c  U
  xP( x )
Universal
generalization
 xP( x )
 P ( c ) for some element c  U
Existential
instantiation
P ( c ) for some element c  U
  xP( x )
Existential
generalization
103 ICS 253: Discrete Structures I
64
The Foundations: Logic and Proofs
Example
• Show that the premises "A student in this
class has not read the book," and "Everyone
in this class passed the first exam" imply the
conclusion "Someone who passed the first
exam has not read the book."
103 ICS 253: Discrete Structures I
65
The Foundations: Logic and Proofs
Combining Rules of Inference for
Propositions and Quantified
Statements
xP( x)  Q( x) 
P(a), where a is a particular element in the domain
 Q(a )
103 ICS 253: Discrete Structures I
66
The Foundations: Logic and Proofs
Question 16(a,b) pp. 73
• For each of the following arguments, determine
whether it is correct or not and explain why:
• Everyone enrolled in the University has lived in a
dormitory. Mia has never lived in a dormitory.
Therefore, Mia is not enrolled in the University.
• A convertible car is fun to drive. Isaac’s car is not a
convertible. Therefore, Isaac’s car is not fun to drive.
103 ICS 253: Discrete Structures I
67
The Foundations: Logic and Proofs
Section 1.6: Introduction to Proofs
• The methods of proof discussed in this
section are important not only because they
are used to prove mathematical theorems, but
also for their many applications to computer
science.
•
•
•
•
•
Verifying that computer programs are correct
Establishing that operating systems are secure
Making inferences in artificial intelligence
Showing that system specifications are consistent
…etc.
103 ICS 253: Discrete Structures I
68
The Foundations: Logic and Proofs
Terminology
• Theorem= A statement that can be shown to be true.
•
•
Less important theorems are called propositions.
Demonstrated to be true through a proof.
• Proof = A sequence of statements that forms an
argument.
•
Some of these statements can be axioms or posulates.
• Axioms =
•
•
•
Underlying assumptions about mathematical structures
Hypotheses of the theorem to be proved
Previously proved theorems
103 ICS 253: Discrete Structures I
69
The Foundations: Logic and Proofs
Definitions
• Rules of Inference = Means used to draw
conclusions from other
assertions, which tie together
the steps of a proof.
• Lemma
= A simple theorem used in the
proof of other theorems.
• Corollary
= A proposition that can be
established directly from a
theorem.
• Conjecture = A statement whose truth value is
unknown, but “thought” to be
true.
103 ICS 253: Discrete Structures I
70
The Foundations: Logic and Proofs
How Theorems are Stated
• Many theorems assert that a property holds for all elements in a
domain.
• Although the precise statement of such theorems needs to include a
universal quantifier, the standard convention in mathematics is to
omit it.
• For example, the statement "If x > y, where x and y are positive real
numbers, then x2 > y2."
really means
"For all positive real numbers x and y, if x > y, then x2 > y2."
• The law of universal instantiation is often used without explicit
mention.
• Proof Steps:
• Select a general (arbitrary) element of the domain.
• Show that this element has the property in question (using rules of
inference!)
• Finally, universal generalization implies that the theorem holds for all
members of the domain.
103 ICS 253: Discrete Structures I
71
The Foundations: Logic and Proofs
Methods of Proving Theorems
• Direct Proof (Modus Ponens)
•
Assume that p is true and use axioms, definitions, and
previously proven theorems, together with rules of
inference, to show that q must also be true.
• Indirect Proof (Modus tollens or Proof by Contraposition)
• Vacuous Proof
•
If p is false in the implication p  q, then the implication is
true
• Trivial Proof
•
If the conclusion q is true, p  q is trivially true
• Proof By Contradiction
•
If a contradiction q can be found such that p  q is true
103 ICS 253: Discrete Structures I
72
The Foundations: Logic and Proofs
Methods of Proving Theorems
• PROOFS OF EQUIVALENCE
• To prove a theorem that is a biconditional
statement, that is, a statement of the form p  q,
we show that p  q and q  p are both true. The
validity of this approach is based on the tautology
(p  q)  [(p  q)  (q  p)]
103 ICS 253: Discrete Structures I
73
The Foundations: Logic and Proofs
Proof Strategy
1. Check whether a direct proof seems
promising
•
Expand definitions from hypotheses and reason
using theorems and axioms
2. Otherwise, look for an indirect proof
103 ICS 253: Discrete Structures I
74
The Foundations: Logic and Proofs
Examples
• Q10 pp 85: Use a direct proof to show that
the product of two rational numbers is
rational.
• Q11 pp 85: Prove or disprove that the
product of two irrational numbers is
irrational.
• Q15 pp 85: Use a proof by contraposition to
show that if x + y  2, where x and y are real
numbers, then x  1 or y  1.
103 ICS 253: Discrete Structures I
75
The Foundations: Logic and Proofs
Examples
• Q17 (b) pp 85: Show that if n is an integer
and n3 + 5 is odd, then n is even using a proof
by contradiction.
• Q19 pp 85: Prove the proposition P(0), where
P(n) is the proposition "If n is a positive
integer greater than 1, then n2 > n.“
What kind of proof did you use?
103 ICS 253: Discrete Structures I
76
The Foundations: Logic and Proofs
Examples
• Q21 pp 85: Let P(n) be the proposition "If a and
b are positive real numbers, then
(a + b)n  an + bn ."
Prove that P (1) is true. What kind of proof did
you use?
• Show that these statements about the integer n
are equivalent:
p1: n is even.
p2: n – 1 is odd.
p3: n2 is even.
103 ICS 253: Discrete Structures I
77
The Foundations: Logic and Proofs
Counter Examples
• To prove that  x P ( x ) is false, you only need
to look for one y in the domain such that P(y)
is false.
103 ICS 253: Discrete Structures I
78
The Foundations: Logic and Proofs
Mistakes in Proofs
• Incorrect operations/conclusions: (Prove that 1=2)
1. a = b
2. a2 = ab
3. a2 – b2 = ab – b2
4. (a – b)(a + b) = b(a – b)
5. a + b = b
6. 2b = b
7. 2 = 1
• Circular reasoning: (if n2 is even, n is even)
• Suppose that n2 is even. Then n2 = 2k for some integer k.
Let n = 2m for some integer m. This shows that n is even.