Discrete Structures
Uploaded by
nixonob380Discrete Structures
Uploaded by
nixonob380DISCRETE STRUCTURES
The Logic of Compound Statements
Acknowledgement
• The contents of these slides have origin from School of
Computing, National University of Singapore.
• We greatly appreciate support from Mr. Aaron Tan Tuck Choy,
and Dr. Terence SIM Mong Cheng for kindly sharing these
materials.
March 19, 2024 2
Policies for students
• These contents are only used for students PERSONALLY.
• Students are NOT allowed to modify or deliver these contents to
anywhere or anyone for any purpose.
March 19, 2024 3
Recording of modifications
• Course website address is changed to
https://elearning.tdtu.edu.vn
• Course codes CS1231, CS1231S are placed by 501044.
March 19, 2024 4
Logical Form
and Logical Equivalence
March 19, 2024 5
Example
If Jane is a math major or Jane is a computer
Jane is a computer science science major.
major, then Jane will take Therefore, Jane will
501044. take 501044.
If 501044 is easy or I study hard.
, then
Therefore, I will get A
. in this course.
March 19, 2024 6
2.1.1. Statements
If Jane is a math major or Jane is a computer science major,
then Jane will take 501044.
Jane is a computer science major. Statements
Therefore, Jane will take 501044.
Definition 2.1.1 (Statement)
A statement (or proposition) is a sentence that is
true or false, but not both.
March 19, 2024 7
Common Form
If Jane is a math major or Jane is a computer
science major, then Jane will take MA1101R.
Jane is a computer science major.
Therefore, Jane will take MA1101R.
If p or q, then r.
q.
Therefore, r.
Statement variables
March 19, 2024 8
2.1.2. Compound Statements
Logical connectives:
also
~
not and or
Truth values:
p q pq p q pq
p ~p T T T T T T
T F T F F T F T
F T F T F F T T
F F F F F F
March 19, 2024 9
Compound Statements: Negation, Conjunction, and
Disjunction
Definition 2.1.2 (Negation)
If p is a statement variable, the negation of p is “not
p” or “it is not the case that p” and is denoted ~p.
Definition 2.1.3 (Conjunction)
If p and q are statement variables, the conjunction of
p and q is “p and q”, denoted p q.
Definition 2.1.4 (Disjunction)
If p and q are statement variables, the disjunction of p
and q is “p or q”, denoted p q.
March 19, 2024 10
Compound Statements: Order of Operations
Order of operations:
~ is performed first
and are coequal in order of operation
~p q = (~p) q pqr
Ambiguous
Use parentheses to override or disambiguate
order of operations
~(p q) (p q) r p (q r)
Negation of p q Unambiguous
March 19, 2024 11
Compound Statements: Quick Quiz
Given:
h = “It is hot”
s = “It is sunny”
Write logical statements for the following:
a. “It is not hot but it is sunny.”
b. “It is neither hot nor sunny.”
March 19, 2024 12
2.1.3. Statement Form (Propositional Form)
Examples:
~p q (p q) ~(p q) (p q) r
Definition 2.1.5 (Statement Form/Propositional Form)
A statement form (or propositional form) is an
expression made up of statement variables and logical
connectives that becomes a statement when actual
statements are substituted for the component
statement variables.
March 19, 2024 13
Evaluating the Truth of Compound Statements
Construct the truth table for this statement form:
(p q) ~(p q)
p q pq pq ~(p q) (p q) ~(p q)
T T
T F
F T
F F
(p q) ~(p q) is also known as exclusive-or (why?)
Denoted as p q or p XOR q .
March 19, 2024 14
2.1.4. Logical Equivalence
(1) Dogs bark and cats meow. (2) Cats meow and dogs bark.
If (1) is true, it follows that (2) must also be true.
On the other hand, if (1) is false, it follows that (2) must
also be false.
(1) and (2) are logically equivalent statements.
March 19, 2024 15
Logical Equivalence
Definition 2.1.6 (Logical Equivalence)
Two statement forms are called logically equivalent if, and
only if, they have identical truth values for each possible
substitution of statements for their statement variables.
The logical equivalence of statement forms P and Q is
denoted by P Q.
Example: a b ab ba
a b and b a
T T T T always have the
T F F F same truth values,
F T F F hence they are
logically equivalent.
F F F F
March 19, 2024 16
Logical Equivalence: Double Negative Property
Double negation:
~(~p) p
p ~p ~(~p)
T F T
F T F
March 19, 2024 17
Logical Equivalence: Showing Non-equivalence
To show that statement forms P and Q are not
logically equivalent, there are 2 ways:
Truth table – find at least one row where their truth
values differ.
Find a counter example – concrete statements for each
of the two forms, one of which is true and the other of
which is false.
March 19, 2024 18
Logical Equivalence: Showing Non-equivalence
Show that the following 2 statement forms are not
logically equivalent.
~(p q) ~p ~q
Truth table method:
p q ~p ~q pq ~(p q) ~p ~q
T T F F T F F
T F F T F T F
F T T F F T F
F F T T F T T
March 19, 2024 19
Logical Equivalence: Showing Non-equivalence
Show that the following 2 statement forms are not
logically equivalent.
~(p q) ~p ~q
Counter example method:
Let p be the statement “0 < 1” and
q the statement “1 < 0”.
“Not the case that both 0<1 and 1<0”
~(p q)
which is TRUE.
~p ~q “Not 0<1” and “not 1<0” which is FALSE.
March 19, 2024 20
Logical Equivalence: De Morgan’s Laws
De Morgan’s Laws:
~(p q) ~p ~q
~(p q) ~p ~q
Write negations for each of the following:
a. John is 6 feet tall and he weighs at least 200 pounds.
John is not 6 feet tall or he weighs less than 200 pounds.
b. The bus was late or Tom’s watch was slow.
The bus was not late and Tom’s watch was not slow.
or Neither was the bus late nor was Tom’s watch slow.
March 19, 2024 21
2.1.5. Tautologies and Contradictions
Definition 2.1.7 (Tautology)
A tautology is a statement form that is always true
regardless of the truth values of the individual statements
substituted for its statement variables. A statement whose
form is a tautology is a tautological statement.
Definition 2.1.8 (Contradiction)
A contradiction is a statement form that is always false
regardless of the truth values of the individual statements
substituted for its statement variables. A statement whose
form is a contradiction is a contradictory statement.
March 19, 2024 22
Tautologies and Contradictions
Logical equivalence involving tautologies and
contradictions
Example: If t is a tautology and c is a contradiction, show that:
ptp and pcc
p t c pt pc
T T F T F
F T F F F
March 19, 2024 23
2.1.6. Summary of Logical Equivalences
Theorem 2.1.1 Logical Equivalences
Given any statement variables p, q and r, a tautology t and a
contradiction c:
1 Commutative laws pqqp pqqp
2 Associative laws (p q) r p (q r) (p q) r p (q r)
p (q r) p (q r)
3 Distributive laws
(p q) (p r) (p q) (p r)
4 Identity laws ptp pcp
5 Negation laws p ~p t p ~p c
6 Double negative law ~(~p) p
March 19, 2024 24
2.1.6. Summary of Logical Equivalences
Theorem 2.1.1 Logical Equivalences (continue)
Given any statement variables p, q and r, a tautology t and a
contradiction c:
7 Idempotent laws ppp ppp
Universal bound
8 ptt pcc
laws
9 De Morgan’s laws ~(p q) ~p ~q ~(p q) ~p ~q
10 Absorption laws p (p q) p p (p q) p
11 Negation of t and c ~t c ~c t
March 19, 2024 25
Simplifying Statement Forms: Quick Quiz
Use the laws in Theorem 2.1.1 to verify the
following logical equivalence:
~(~p q) (p q) p
~(~p q) (p q) (~(~p) ~q) (p q) De Morgan’s
March 19, 2024 26
2.2 Conditional Statements
March 19, 2024 27
2.2.1. Conditional Statements
If Jane is a math major or Jane
then Jane will take 501044.
is a computer science major,
hypothesis conclusion
If 4,686 is divisible by 6, then 4,686 is divisible by 3.
Conditional statement
If p, then q pq
28
Conditional Statements
Logical connective: Truth values: p q pq
T T T
T F F
if-then/implies F T T
F F T
Definition 2.2.1 (Conditional)
If p and q are statement variables, the conditional of q by
p is “if p then q” or “p implies q”, denoted p q.
It is false when p is true and q is false; otherwise it is true.
We called p the hypothesis (or antecedent) of the
conditional and q the conclusion (or consequent).
29
Conditional Statements
A conditional statement that is true by p q pq
virtue of the fact that its hypothesis is T T T
T F F
false is often called vacuously true or true F T T
by default. F F T
“If you show up for work Monday morning,
then you will get the job” is vacuously true if
you do NOT show up for work Monday
morning.
In general, when the “if” part of an if-then statement
is false, the statement as a whole is said to be true,
regardless of whether the conclusion is true or false.
30
Conditional Statements: Example #1
Example #1:
A Conditional Statement with a False Hypothesis
If 0 = 1, then 1 = 2
Strange as it may seem, the statement as a whole is
true!
31
Conditional Statements: Order of Operations
Order of operations:
~
not and or if-then/implies
Coequal in order
Performed first Performed last
32
Conditional Statements: Example #2
Example #2: Truth Table for p ~q ~p
p ~q ~p (p (~q)) (~p)
conclusion hypothesis
p q ~p ~q p ~q p ~q ~p
T T F F T
T F F T T
F T T F F
F F T T T
33
Conditional Statements: Example #3
Example #3: Show that
pqr (p r) (q r)
p q r pq pr qr pqr (p r) (q r)
T T T T T T
T T F T F F
T F T T T T
T F F T F T
F T T T T T
F T F T T F
F F T F T T
F F F F T T
34
2.2.2. Representation of If-Then as Or
Rewrite the following statement in if-then form:
Either you get to work on time or you are fired.
Let ~p be “You get to work on time”
~p q
and q be “You are fired”.
Also, p is “You do not get to work on time”.
If you do not get to work on time, you are fired.
pq
35
Representation of If-Then as Or
p q pq p q ~p q
T T T T T T
T F F T F F
F T T F
~p
T
q T
F F T F F T
pq
36
2.2.3. Negation of a Conditional Statement
In previous slide, we have shown
pq ~p q
~(p q) ~(~p v q) ~(~p) ~q p ~q
~(p q) p ~q
37
Negation of a Conditional Statement: Quick Quiz
Write negation for each of the following statements:
a. If my car is in the repair shop, then I cannot get to class.
b. If Sara lives in Athens, then she lives in Greece.
35
2.2.4. Contrapositive of a Conditional Statement
Definition 2.2.2 (Contrapositive)
The contrapositive of a conditional statement of the form
“if p then q” is
“if ~q then ~p”
Symbolically,
The contrapositive of p q is ~q ~p.
pq ~q ~p
contrapositive
36
Contrapositive: Quick Quiz
Write each of the following statements in its
equivalent contrapositive form:
a. If Howard can swim across the lake, then Howard can
swim to the island.
b. If today is Easter, then tomorrow is Monday.
37
2.2.5. Converse and Inverse of a Conditional Statement
Definition 2.2.3 (Converse)
The converse of a conditional statement “if p then q” is
“if q then p”
Symbolically,
The converse of p q is q p.
Definition 2.2.4 (Inverse)
The inverse of a conditional statement “if p then q” is
“if ~p then ~q”
Symbolically,
The inverse of p q is ~p ~q.
41
Converse and Inverse
Conditional statement: pq
qp ~p ~q
converse inverse
42
Converse and Inverse: Quick Quiz
Write the converse and inverse of the following
statements:
a. If Howard can swim across the lake, then Howard can
swim to the island.
Converse:
Inverse:
b. If today is Easter, then tomorrow is Monday.
Converse:
Inverse: 40
Conditional statement and its Contrapositive, Converse
and Inverse
pq ~q ~p
conditional contrapositive
statement
qp ~p ~q
converse inverse
Note that:
pq qp
44
2.2.6. Only If and the Biconditional
To say “p only if q” means that p can take place only if
q takes place also. That is, if q does not take place,
then p cannot take place.
Another way to say this is that if p occurs, then q
must also occur (using contrapositive).
Definition 2.2.5 (Only If)
If p and q are statements,
“p only if q” means “if not q then not p”
Or, equivalently,
“if p then q”
45
Only If : Quick Quiz
Rewrite the following statement in if-then form in two
ways, one of which is the contrapositive of the other.
John will break the world’s record only if he runs the mile in
under four minutes.
Version 1: If John does not run the mile in under four minutes,
then John will not break the world’s record.
Version 2:
43
Only If and the Biconditional
Definition 2.2.6 (Biconditional)
Given statement variables p and q, the biconditional of p
and q is “p if, and only if, q” and is denoted p q.
It is true if both p and q have the same truth values and is
false if p and q have opposite truth values.
The words if and only if are sometimes abbreviated iff.
pq p q pq
T T T
T F F
F T F
F F T
47
Only If and the Biconditional
pq (p q) (q p)
p q pq qp pq (p q) (q p)
T T T T T T
T F F T F F
F T T F F F
F F T T T T
48
Only If and the Biconditional
Order of operations:
~
not and or if-then/implies if and only if
Coequal in order Coequal in order
Performed first
Performed last
49
Biconditional : Quick Quiz
Rewrite the following statement as a conjunction of
two if-then statements.
This computer program is correct if, and only if, it produces
correct answers for all possible sets of input data.
47
2.2.7. Necessary and Sufficient Conditions
Definition 2.2.7 (Necessary and Sufficient Conditions)
If r and s are statements,
“r is a sufficient condition for s” means “if r then s”
“r is a necessary condition for s” means “if not r then not s”
In other words, to say “r is a sufficient condition for s”
means that the occurrence of r is sufficient to
guarantee the occurrence of s.
51
Necessary and Sufficient Conditions
On the other hand, to say “r is a necessary condition
for s” means that if r does not occur, then s cannot
occur either: The occurrence of r is necessary to
obtain the occurrence of s.
Note that due to the equivalence between a
statement and its contrapositive:
r is a necessary condition for s also means “if s then r”.
Consequently,
r is a necessary and sufficient condition for s
means “r, if and only if, s”.
52
Necessary and Sufficient Conditions
“If John is eligible to vote, then he is at least 18 years old.”
The truth of the condition “John is eligible to vote” is
sufficient to ensure the truth of the condition “John is
at least 18 years old.”
In addition, the condition “John is at least 18 years
old” is necessary for the condition “John is eligible to
vote” to be true.
If John were younger than 18, then he would not be
eligible to vote.
53
2.3 Valid and Invalid
Arguments
March 19, 2024 54
2.3.1. Valid and Invalid Arguments
Argument: a sequence of statements
ending in a conclusion. Abstract form
If Socrates is a man, then Socrates is mortal. If p, then q
Socrates is a man. p
Socrates is mortal.
q
An argument form is called valid if, and only if,
whenever statements are substituted that
make all the premises true, the conclusion is
also true.
55
Valid and Invalid Arguments
Definition 2.3.1 (Argument)
An argument (argument form) is a sequence of statements (statement forms).
All statements in an argument (argument form), except for the final one, are
called premises (or assumptions or hypothesis). The final statement
(statement form) is called the conclusion. The symbol , which is read
“therefore”, is normally placed just before the conclusion.
To say that an argument form is valid means that no matter what particular
statements are substituted for the statement variables in its premises, if the
resulting premises are all true, then the conclusion is also true.
Example:
If p, then q
premises
p
q conclusion
56
Valid and Invalid Arguments
When an argument is valid and its premises are true,
the truth of the conclusion is said to be inferred or
deduced from the truth of the premises.
If a conclusion “ain’t necessarily so”, then it isn’t a
valid deduction.
57
2.3.2. Determining Validity or Invalidity
Testing an Argument Form for Validity
1. Identify the premises and conclusion of the argument form.
2. Construct a truth table showing the truth values of all the
premises and the conclusion.
3. A row of the truth table in which all the premises are true is
called a critical row.
If there is a critical row in which the conclusion is false
the argument form is invalid.
If the conclusion in every critical row is true
the argument form is valid.
58
Determining Validity or Invalidity: Example #1
p q ~r
qpr Invalid argument
pr premises
conclusion
p q r ~r q ~r pr p q ~r qpr pr
Critical
T T T F T T T T T rows
T T F T T F T F
T F T F F T F T
T F F T T F T T F
F T T F T F T F
F T F T T F T F
F F T F F F T T T
F F F T T F T T T
59
2.3.3. Modus Ponens and Modus Tollens
Syllogism: An argument form consisting of two
premises and a conclusion.
A famous form of syllogism is called modus ponens:
If p then q
p
q
60
Modus Ponens and Modus Tollens
Modus ponens is a valid form of argument.
pq
p
p q pq p q
q
T T T T T
T F F T
F T T F
F F T F
61
Modus Ponens and Modus Tollens
Modus tollens is another valid form of argument.
If p then q
~q
~p
62
Modus Ponens and Modus Tollens: Quick Quiz
Use modus ponens or modus tollens to fill in the
blanks of the following arguments so that they
become valid inferences.
a. If there are more pigeons than there are pigeonholes,
then at least two pigeons roost in the same hole.
There are more pigeons than there are pigeonholes.
b. If 870,232 is divisible by 6, then it is divisible by 3.
870,232 is not divisible by 3.
60
2.3.4. Additional Valid Argument Forms: Rules of
Inference
A rule of inference is a form of argument that is valid.
Thus modus ponens and modus tollens are both rules of
inference.
More examples:
1. Generalization
2. Specialization
3. Elimination
4. Transitivity
5. Proof by Division into Cases
64
2.3.4.1. Rules of Inference: Generalization
The following argument forms are valid.
p q
pq pq
Example:
Anton is a junior.
(More generally) Anton is a junior or Anton is a senior.
65
2.3.4.2. Rules of Inference: Specialization
The following argument forms are valid.
Allows you to
pq pq discard extraneous
information to
p q concentrate on the
particular property
Example: of interest.
Ana knows numerical analysis and Ana knows graph
algorithms.
(In particular) Ana knows graph algorithms.
So if you are looking for someone who knows graph algorithms to work with you
on a project, and you discover that Ana knows both numerical analysis and graph
algorithms, would you invite her to work with you on your project?
66
2.3.4.3. Rules of Inference: Elimination
The following argument forms are valid.
pq pq When you have two
possibilities and you
~q ~p can rule one out,
the other must be
p q the case.
Example:
Suppose you know that for a particular number x,
x – 3 = 0 or x + 2 = 0
If you also know that x is not negative, then x -2, so
by elimination you can conclude that x = 3.
67
2.3.4.4. Rules of Inference: Transitivity
The following argument form is valid.
pq Many arguments in mathematics contain
chains of if-then statements.
qr From the fact that one statement implies a
second and the second implies the third,
pr you can conclude that the first statement
implies the third.
Example:
If 18,486 is divisible by 18, then 18,486 is divisible by 9.
If 18,486 is divisible by 9, then the sum of the digits of
18,486 is divisible by 9.
If 18,486 is divisible by 18, then the sum of the digits
of 18,486 is divisible by 9.
68
2.3.4.5. Rules of Inference: Proof by Division into Cases
The following argument form is valid.
pq It often happens that you know one thing
or another is true. If you can show that in
pr either case a certain conclusion follows,
qr then this conclusion must also be true.
r
Example:
Suppose you know that x is a nonzero real x is positive or x is negative.
number. If x is positive, then x2 > 0.
The trichotomy property of the real If x is negative, then x2 > 0.
numbers says that any number is positive, x2 > 0.
negative, or zero. Thus (by elimination) you
know that x is positive or negative.
You can deduce that x2 > 0 by arguing as
follows: 66
2.3.4.6. Rules of Inference: Example
You are about to leave for school in the morning and discover
that you don’t have your glasses. You know the following
statements are true:
a. If I was reading the newspaper in the kitchen, then my glasses are on
the kitchen table.
b. If my glasses are on the kitchen table, then I saw them at breakfast.
c. I did not see my glasses at breakfast.
d. I was reading the newspaper in the living room or I was reading the
newspaper in the kitchen.
e. If I was reading the newspaper in the living room then my glasses are
on the coffee table.
So, where are your glasses?
67
Rules of Inference: Example
Let
RK = I was reading the newspaper in the kitchen.
Here is a sequence of steps
GK = My glasses are on the kitchen table. you might use to reach the
SB = I saw my glasses at breakfast. answer, together with the
RL = I was reading the newspaper in the living rules of inference that allow
room. you to draw the conclusion
GC = My glasses are on the coffee table. of each step:
1. RK GK by (a)
GK SB by (b)
RK SB by transitivity
68
2.3.5. Fallacies
A fallacy is an error in reasoning that results in an
invalid argument.
Three common fallacies:
1. Using ambiguous premises, and treating them as if they
were unambiguous.
2. Circular reasoning (assuming what is to be proved without
having derived it from the premises)
3. Jumping to a conclusion (without adequate grounds)
72
Fallacies
For an argument to be valid, every argument
of the same form whose premises are all true
must have a true conclusion.
It follows that for an argument to be invalid
means that there is an argument of that form
whose premises are all true and whose
conclusion is false.
73
2.3.5.1. Fallacies: Converse Error
Example:
If Zeke is a cheater, then Zeke sits in the back row.
Zeke sits in the back row.
Zeke is a cheater.
pq qp
q q
p p
Converse error is also known as the
fallacy of affirming the consequence.
74
2.3.5.2. Fallacies: Inverse Error
Example:
If interest rates are going up, stock market prices will
go down.
Interest rates are not going up.
Stock market prices will not go down.
pq ~p ~q
~p ~p
~q ~q
75
2.3.5.3. Fallacies: A Valid Argument with a False
Premise and a False Conclusion
The argument below is valid by modus ponens. But its major
premise is false, and so is its conclusion.
If John Lennon was a rock star, then John Lennon
had red hair.
John Lennon was a rock star.
John Lennon had red hair.
76
2.3.5.4. Fallacies: An Invalid Argument with True
Premises and a True Conclusion
The argument below is invalid by the converse error, but it has
a true conclusion.
If New York is a big city, then New York has tall
buildings.
New York has tall buildings.
New York is a big city.
77
2.3.5.5. Fallacies: Sound and Unsound Arguments
Definition 2.3.2 (Sound and Unsound Arguments)
An argument is called sound if, and only if, it is valid and
all its premises are true.
An argument that is not sound is called unsound.
78
2.3.6. Contradictions and Valid Arguments
The concept of logical contradiction can be used to
make inferences through a technique of reasoning
called the contradiction rule. Suppose p is some
statement whose truth you wish to deduce.
Contradiction Rule
If you can show that the supposition that statement
p is false leads logically to a contradiction, then you
can conclude that p is true.
79
Contradictions and Valid Arguments: Example –
Contradiction Rule
Show that the following argument form is valid:
~p c where c is a contradiction
p
premise conclusion
Only one critical row, and
p ~p c ~p c p in this row the conclusion
T F F T T is true.
Hence this form of
F T F F argument is valid.
80
Contradictions and Valid Arguments: Example –
Contradiction Rule
The contradiction rule is the logical heart of the
method of proof by contradiction.
A slight variation also provides the basis for
solving many logical puzzles by eliminating
contradictory answers:
If an assumption leads to a contradiction,
then that assumption must be false.
81
2.3.7. Summary of Rules of Inference
Table 2.3.1 Rule of inference
Modus Ponens pq
p
q
Modus Tollens pq
~q
~p
Generalization p q
pq pq
Specialization pq pq
p q
Conjunction p
q
pq
82
2.3.7. Summary of Rules of Inference
Table 2.3.1 Rule of inference
(cont’d) Elimination pq pq
~q ~p
p q
Transitivity pq
qr
pr
Proof by Division pq
Into Cases pr
qr
r
Contradiction Rule ~p c
p
83
DISCRETE STRUCTURES
The Logic of Quantified Statements
Acknowledgement
• The contents of these slides have origin from School of
Computing, National University of Singapore.
• We greatly appreciate support from Mr. Aaron Tan Tuck Choy,
and Dr. Terence SIM Mong Cheng for kindly sharing these
materials.
March 19, 2024 2
Policies for students
• These contents are only used for students PERSONALLY.
• Students are NOT allowed to modify or deliver these contents to
anywhere or anyone for any purpose.
March 19, 2024 3
Recording of modifications
• Course website address is changed to
https://elearning.tdtu.edu.vn
• Course codes CS1231, CS1231S are placed by 501044.
March 19, 2024 4
3.1 Predicates and Quantified
Statements I
March 19, 2024 5
3.1.1. Predicates and Quantified Statements I
In logic, predicates can be obtained by removing some
or all of the nouns from a statement. For instance, let
P stand for “is a student at Bedford College” and let Q
stand for “is a student at.” Then both P and Q are
predicate symbols.
Predicate variables:
P(x) = “x is a student at Bedford College”
Q(x, y) = “x is a student at y”
When concrete values are substituted in place of
predicate variables, a statement results.
6
Predicates and Quantified Statements I
For simplicity, we define a predicate to be a predicate
symbol together with suitable predicate variables.
In some treatments of logic, such objects are referred
to as propositional functions or open sentences.
Definition 3.1.1 (Predicate)
A predicate is a sentence that contains a finite number of
variables and becomes a statement when specific values are
substituted for the variables.
The domain of a predicate variable is the set of all values
that may be substituted in place of the variable.
7
Predicates and Quantified Statements I
When an element in the domain of the variable of a
one-variable predicate is substituted for the variable,
the resulting statement is either true or false. The set
of all such elements that make the predicate true is
called the truth set of the predicate.
Definition 3.1.2 (Truth set)
If P(x) is a predicate and x has domain D, the truth set is the
set of all elements of D that make P(x) true when they are
substituted for x.
The truth set of P(x) is denoted {x D | P(x)}.
8
Predicates and Quantified Statements I: Finding the Truth
Set of a Predicate
Let Q(n) be the predicate “n is a factor of 8.”
Find the truth set of Q(n) if
a. the domain of n is the set Z+ of all positive integers
{1, 2, 4, 8} because these are exactly the positive
integers that divide 8 evenly.
b. the domain of n is the set Z of all integers.
6
3.1.2. The Universal Quantifier:
One sure way to change predicates into statements is
to assign specific values to all their variables.
Example: If x represents the number 35, the
sentence “x is divisible by 5” is a true
statement.
Another way to obtain statements from predicates is
to add quantifiers.
1
0
The Universal Quantifier:
Quantifiers are words that refer to quantities such as
“some” or “all” and tell for how many elements a
given predicate is true.
The symbol denotes “for all” (or “for any”, “for
every”, “for each”) and is called the universal quantifier.
Definition 3.1.3 (Universal Statement)
Let Q(x) be a predicate and D the domain of x. A universal
statement is a statement of the form “x D, Q(x)”.
It is defined to be true iff Q(x) is true for every x in D.
It is defined to be false iff Q(x) is false for at least one x in D. A
value for x for which Q(x) is false is called a counterexample.
11
The Universal Quantifier: Truth and Falsity of Universal
Statements
Truth and Falsity of Universal Statements
a. Let D = {1, 2, 3, 4, 5}, and consider the statement
x D, x2 x.
Show that this statement is true.
Check that “x2 x” is true for each x in D.
12 1, 22 2, 32 3, 42 4, 52 5.
Hence “x D, x2 x” is true.
This method is called the method of exhaustion.
12
The Universal Quantifier: Truth and Falsity of Universal
Statements
Truth and Falsity of Universal Statements
b. Consider the statement
x R, x2 x.
Find a counterexample to show that this statement
is false.
10
3.1.3. The Existential Quantifier:
Example: “There is a student in CS1231” can be
written as
a person p such that p is a student in CS1231.
Or, more formally,
p P such that p is a student in CS1231.
where P is the set of all people.
The words such that are inserted just before the
predicate. Some alternative expressions for “there
exists” are “there is a”, “we can find a”, “there is at least
one”, “for some”, and “for at least one”.
14
The Existential Quantifier:
Sentences that are quantified existentially are defined
as statements by giving them the truth values
specified in the following definition.
Definition 3.1.4 (Existential Statement)
Let Q(x) be a predicate and D the domain of x. An existential
statement is a statement of the form “x D such that Q(x)”.
It is defined to be true iff Q(x) is true for at least one x in D.
It is defined to be false iff Q(x) is false for all x in D.
15
The Existential Quantifier: Truth and Falsity of Existential
Statements
Truth and Falsity of Existential Statements
a. Show that the following statement is true.
m Z+ such that m2 = m.
Observe that 12 = 1. Thus “m2 = m” is true for at least one
integer m. Hence “m Z+ such that m2 = m” is true.
b. Let E = {5, 6, 7, 8}. Show that the following statement is false.
m E such that m2 = m.
Note that m2 = m is not true for any integer m from 5
through 8: 52 = 25 5, 62 = 36 6, 72 = 49 7,
82 = 64 8.
Hence “m E such that m2 = m” is false.
16
3.1.4. Formal Versus Informal Language
Rewrite the following formal statements in a variety of
equivalent but more informal ways. Do not use the
symbol or .
All real numbers have non-negative squares.
a. x R, x2 0. Every/Any real number has a non-negative square.
The square of each real number is non-negative.
b. x R, x2 -1. All real numbers have squares that are not -1.
No real numbers have squares equal to -1.
c. m Z+ such that m2 = m.
There is a positive integer whose square is itself.
We can find at least one positive integer equal to its own square.
Some positive integer equals its own square.
17
3.1.5. Universal Conditional Statements
A reasonable argument can be made that the most
important form of statement in mathematics is the
universal conditional statement:
x, if P(x) then Q(x).
Familiarity with statements of this form is essential if
you are to learn to speak mathematics.
18
Universal Conditional Statements Quick Quiz
Rewrite the following statement informally, without
quantifiers or variables:
x R, if x > 2 then x2 > 4.
If a real number is greater than 2, then its square is
greater than 4.
or Whenever a real number is greater than 2, its
square is greater than 4.
or
19
3.1.6. Equivalent Forms of Universal and Existential
Statements
Are these the same?
real numbers x, if x is an integers x, x is rational.
integer then x is rational.
20
Equivalent Forms of Universal and Existential Statements
By narrowing U to be the domain D consisting of
all values of the variable x that make P(x) true,
x U, if P(x) then Q(x) x D, Q(x)
Rewrite the statement “All squares are rectangles” in
the two forms:
x, if then .
x, _ _ _ _.
21
Equivalent Forms of Universal and Existential Statements
Similarly,
x such that P(x) and Q(x)
x D such that Q(x)
where D is the set of all x for which P(x) is true.
19
Equivalent Forms of Universal and Existential Statements
A prime number is an integer whose only positive
integer factors are itself and 1. Consider the statement
“There is an integer that is both prime and even.”
Let Prime(n) be “n is prime” and Even(n) be “n is even”.
Use the notation Prime(n) and Even(n) to rewrite this
statement in the following two forms:
a. n such that .
b. n such that .
20
3.1.7. Implicit Quantification
Mathematical writing contains many examples of implicitly
quantified statements. Some occur, through the presence
of the word a or an. Others occur in cases where the
general context of a sentence supplies part of its meaning.
For example, in an algebra course in which the letter x is
always used to indicate a real number, the predicate
If x > 2 then x2 > 4
is interpreted to mean the same as the statement
real numbers x, if x > 2 then x2 > 4.
24
Implicit Quantification: Using => and <=>
Mathematicians often use a double arrow to indicate
implicit quantification symbolically.
For instance, they might express the above statement as
x > 2 x2 > 4
Notation
Let P(x) and Q(x) be predicates and suppose the common
domain of x is D.
The notation P(x) Q(x) means that every element in the
truth set of P(x) is in the truth set of Q(x), or, equivalently,
x, P(x) Q(x).
The notation P(x) Q(x) means that P(x) and Q(x) have
identical truth sets, or, equivalently, x, P(x) Q(x).
25
Implicit Quantification: Using => and <=>
Let
Q(n) be “n is a factor of 8”,
R(n) be “n is a factor of 4”,
S(n) be “n < 5 and n 3”,
and suppose the domain of n is Z+, the set of positive
integers.
Use the and symbols to indicate true relationship
among Q(n), R(n), and S(n).
26
Implicit Quantification: Using => and <=>
1. The truth set of Q(n) is {1,2,4,8} Q(n) be “n is a factor of 8”,
and the truth set of R(n) is {1,2,4}. R(n) be “n is a factor of 4”,
S(n) be “n < 5 and n 3”
Thus it is true that every element in the truth
set of R(n) is in the truth set of Q(n), or,
n in Z+, R(n) Q(n)
so R(n) Q(n)
Or, equivalently,
n is a factor of 4 n is a factor of 8
27
Implicit Quantification: Using => and <=>
2. The truth set of S(n) is {1,2,4} Q(n) be “n is a factor of 8”,
which is the same as the truth R(n) be “n is a factor of 4”,
set of R(n), or S(n) be “n < 5 and n 3”
n in Z+, R(n) S(n)
So
R(n) S(n)
Or, equivalently,
n is a factor of 4 n < 5 and n 3.
28
3.1.8. Tarski’s World
Tarski’s World is a computer program developed by
information scientists Jon Barwise and John
Etchemendy to help teach the principles of logic.
It is described in their book The Language of First-
Order Logic, which is accompanied by a CD-ROM
containing the program Tarski’s World, named after
the great logician Alfred Tarski.
29
Tarski’s World
The program for Tarski’s World provides pictures of blocks of various
sizes, shapes, and colors, which are located on a grid.
Shown in Figure 3.1.1 is a picture of an arrangement of
objects in a two-dimensional Tarski world.
Figure 3.1.1
30
Tarski’s World
The configuration can be described using logical
operators and — for the two-dimensional version —
notation such as:
Triangle(x), meaning “x is a triangle,”
Blue(y), meaning “y is blue,” and
RightOf(x, y), meaning “x is to the right of y (but
possibly in a different row).”
Individual objects can be given names such as a, b, or c.
31
Tarski’s World
Determine the truth or falsity of the
following statements. The domain for
all variables is the set of objects in
the Tarski’s world shown on the right.
a. ∀t, Triangle(t) → Blue(t).
b. ∀x, Blue(x) → Triangle(x). Figure 3.1.1
c. ∃y such that Square(y) 𝖠 RightOf(d, y).
d. ∃z such that Square(z) 𝖠 Gray(z).
29
3.2 Predicates and Quantified
Statements II
March 19, 2024 33
3.2.1. Negations of Quantified Statements
Theorem 3.2.1 Negation of a Universal Statement
The negation of a statement of the form
x in D, P(x)
is logically equivalent to a statement of the form
x in D such that ~P(x)
Symbolically,
~(x in D, P(x)) x in D such that ~P(x)
That is, the negation of a universal statement (“all are”)
is logically equivalent to an existential statement (“some
are not” or “there is at least one that is not”).
34
Negations of Quantified Statements: Negation of an
Existential Statement
Theorem 3.2.2 Negation of an Existential Statement
The negation of a statement of the form
x in D such that P(x)
is logically equivalent to a statement of the form
x in D, ~P(x)
Symbolically,
~(x in D such that P(x)) x in D, ~P(x)
That is, the negation of an existential statement (“some
are”) is logically equivalent to a universal statement
(“none are” or “all are not”).
35
Negations of Quantified Statements: Quick Quiz
Write formal negations for the following statements:
a. primes p, p is odd.
b. a triangle T such that the sum of the angles of T equals
200.
33
3.2.2. Negations of Universal Conditional Statements
Of special importance in mathematics.
~(x, P(x) Q(x)) x such that ~(P(x) Q(x)) … (A)
~(P(x) Q(x)) P(x) ~Q(x) … (B)
Substituting (B) into (A):
~(x, P(x) Q(x)) x such that P(x) ~Q(x)
34
Negations of Universal Conditional Statements: Quick
Quiz
Write a formal negation for statement (a) and an
informal negation for statement (b):
a. people p, if p is blond then p has blue eyes.
b. If a computer program has more than 100,000 lines, then it
contains a bug.
35
3.2.3. The Relation among ∀ , ∃ , ∧ , and ∨
The negation of a for all statement is a there exists
statement, and the negation of a there exists
statement is a for all statement.
These facts are analogous to De Morgan’s laws,
which state that the negation of an and statement
is an or statement and that the negation of an or
statement is an and statement.
This similarity is not accidental. In a sense,
universal statements are generalizations of and
statements, and existential statements are
generalizations of or statements.
39
The Relation among ∀ , ∃ , ∧ , and ∨
If Q(x) is a predicate and the domain D of x is the set
{x1, x2 ,…, xn}, then
x D, Q(x) Q(x1) Q(x2) Q(xn)
Similarly, if Q(x) is a predicate and D = {x1, x2 ,…, xn},
then
x D such that Q(x) Q(x1) Q(x2) Q(xn)
40
3.2.4. Vacuous Truth of Universal Statements
Suppose a bowl sits on a table and next to the
bowl is a pile of five blue and five gray balls, any
of which may be placed in the bowl.
If three blue balls and one gray ball are placed in
the bowl, as shown in Figure 3.2.1(a), the
statement “All the balls in the bowl are blue”
would be false (since one of the balls in the bowl
Figure 3.2.1(a)
is gray).
Now suppose that no balls at all are placed in
the bowl, as shown in Figure 3.2.1(b).
Consider the statement:
All the balls in the bowl are blue.
Figure 3.2.1(b)
41
Vacuous Truth of Universal Statements
Is the statement true or false? The statement is false if, and
only if, its negation is true.
And its negation is
There exists a ball in the bowl that is not blue.
But the only way this negation can be true is for there
actually to be a non-blue ball in the bowl.
And there is not! Hence the negation is false, and so the
statement is true “by default”.
In general, a statement of the form
x in D, if P(x) then Q(x)
is called vacuously true or true by default
if, and only if, P(x) is false for every x in D.
42
3.2.5. Variants of Universal Conditional Statements
We have known that a conditional statement has a
contrapositive, a converse, and an inverse.
The definitions of these terms can be extended to
universal conditional statements.
Definition 3.2.1 (Contrapositive, converse, inverse)
Consider a statement of the form: x D, if P(x) then Q(x).
1. Its contrapositive is: x D, if ~Q(x) then ~P(x).
2. Its converse is: x D, if Q(x) then P(x).
3. Its inverse is: x D, if ~P(x) then ~Q(x).
43
Variants of Universal Conditional Statements
Write a formal and an informal contrapositive, converse, and
inverse for the following statement:
If a real number is greater than 2, then its square is greater than 4.
The formal version: x R, if x > 2 then x2 > 4.
Contrapositive: x R, if x2 4 then x 2.
If the square of a real number is less than or equal to 4, then the number is
less than or equal to 2.
Converse:
Inverse:
41
Variants of Universal Conditional Statements
Let P(x) and Q(x) be any predicates, let D be the domain of x,
and consider the statement:
x D, if P(x) then Q(x)
and its contrapositive
x D, if ~Q(x) then ~P(x)
Any particular x in D that makes “if P(x) then Q(x)” true also
makes “if ~Q(x) then ~P(x)” true (by the logical equivalence
between p q and ~q ~p).
It follows that “if P(x) then Q(x)” is true for all x in D iff “if ~Q(x)
then ~P(x)” is true for all x in D.
x D, if P(x) then Q(x) x D, if ~Q(x) then ~P(x)
45
Variants of Universal Conditional Statements
Consider the statement:
x R, if x > 2 then x2 > 4 True
and its converse
x R, if x2 > 4 then x > 2 False
A universal conditional statement is not logically
equivalent to its converse.
x D, if P(x) then Q(x) x D, if Q(x) then P(x)
46
3.2.6. Necessary and Sufficient Conditions, Only if
The definitions of necessary, sufficient, and only if can
also be extended to apply to universal conditional
statements.
Definition 3.2.2 (Necessary and Sufficient conditions, Only if)
“x, r(x) is a sufficient condition for s(x)”
means “x, if r(x) then s(x)”.
“x, r(x) is a necessary condition for s(x)” means “x, if
~r(x) then ~s(x)” or, equivalently, “x, if s(x) then r(x)”.
“x, r(x) only if s(x)” means “x, if ~s(x) then ~r(x)” or,
equivalently, “x, if r(x) then s(x)” .
47
Necessary and Sufficient Conditions, Only if
Rewrite the following statements as quantified
conditional statements. Do not use the word necessary
or sufficient:
a. Squareness is a sufficient condition for rectangularity.
x, if x is a square, then x is a rectangle.
Informal: If a figure is a square, then it is a rectangle.
b. Being at least 35 years old is a necessary condition for being
President of the United States.
45
3.3 Statements with Multiple
Quantifiers
March 19, 2024 49
Statements with Multiple Quantifiers
Consider the Tarski’s world again.
Show that the following statement is true:
For all triangles x, there is a square y such
that x and y have the same color.
The statement says that no matter which
triangle someone gives you, you will be
able to find a square of the same color.
Figure 3.3.1
There are only 3 triangles d, f, and i.
50
3.3.1. Interpreting Multiply-Quantified Statements
If you want to establish the truth of a statement of the form:
∀x in D, ∃y in E such that P(x, y)
your challenge is to allow someone else to pick whatever
element x in D they wish and then you must find an element y
in E that “works” for that particular x.
If you want to establish the truth of a statement of the form:
∃x in D such that ∀y in E, P(x, y)
your job is to find one particular x in D that will “work” no
matter what y in E anyone might choose to challenge you
with.
51
Interpreting Multiply-Quantified Statements
A college cafeteria line has four stations: salads, main courses,
desserts, and beverages.
The salad station offers a choice of green salad or fruit salad; the main
course station offers spaghetti or fish; the dessert station offers pie or
cake; and the beverage station offers milk, soda, or coffee. Three
students, Uta, Tim, and Yuen, go through the line and make the
following choices:
Uta: green salad, spaghetti, pie, milk
Tim: fruit salad, fish, pie, milk, coffee
Yuen: spaghetti, fish, pie, soda
52
Interpreting Multiply-Quantified Statements
These choices are illustrated in Figure 3.3.2.
Figure 3.3.2
53
Interpreting Multiply-Quantified Statements
Write each of following statements informally and find its
truth value.
1. an item I such that students S, S chose I.
There is an item that was chosen by every student. True of false?
2. a student S such that items I, S chose I.
3. a student S such that stations Z, an item I in Z such that
S chose I.
4. ∀ students S and ∀ stations Z, ∃ an item I in Z such that S
chose I.
51
3.3.2. Translating from Informal to Formal Language
Most problems are stated in informal language, but solving them
often requires translating them into more formal terms.
Example: The reciprocal of a real number a is a real number b
such that ab = 1. The following 2 statements are true. Rewrite
them formally using quantifiers and variables:
a. Every nonzero real number has a reciprocal.
nonzero real numbers u, a real number v such that uv = 1.
b. There is a real number with no reciprocal.
a real numbers c such that real number d, cd 1.
55
3.3.3. Ambiguous Language
You are visiting a computer microchips factory. The factory guide
tells you:
There is a person supervising every detail of the
production process.
“there is” – existential quantifier; “every” – universal quantifier.
Which of the following best describes its meaning?
There is one single person who supervises all the details of the
production process.
For any particular production detail, there is a person who
supervises the detail, but there might be different supervisors
for different details.
56
Ambiguous Language
Once you interpreted the sentence in one way, it may have been
hard for you to see that it could be understood in the other way.
Perhaps you had difficulty even though the two possible
meanings were explained.
Although statements written informally may be open to multiple
interpretations, we cannot determine their truth or falsity
without interpreting them one way or another.
Therefore, we have to use context to try to ascertain
their meaning as best we can.
57
3.3.4. Negations of Multiply-Quantified Statements
Recall in 3.2.1: ~(x in D, P(x)) x in D such that ~P(x)
~(x in D such that P(x)) x in D, ~P(x)
(A) So, to find: ∼(∀x in D, ∃y in E such that P(x, y))
∃x in D such that ∼(∃y in E such that P(x, y))
∃x in D such that ∀y in E, ∼P(x, y).
∼(∀x in D, ∃y in E such that P(x, y)) ∃x in D such that ∀y in E, ∼P(x, y)
(B) Similarly, to find: ∼(∃x in D such that ∀y in E, P(x, y))
∀x in D, ∼(∀y in E, P(x, y))
∀x in D, ∃y in E such that ∼P(x, y).
∼(∃x in D such that ∀y in E, P(x, y)) ∀x in D, ∃y in E such that ∼P(x, y)
58
Negations of Multiply-Quantified Statements
Refer to the Tarski’s world of Figure 3.3.1
again.
Write a negation for each of the
following statements, and determine
which is true, the given statement or
its negation.
a. For all squares x, there is a circle y
such that x and y have the same color. Figure 3.3.1
Negation:
a square x such that ~( a circle y such that x and y have the
same color)
a square x such that circles y, x and y do not have the
same color. TRUE (Square e is black and no circle is black).
59
Negations of Multiply-Quantified Statements
Refer to the Tarski’s world of Figure 3.3.1
again.
Write a negation for each of the
following statements, and determine
which is true, the given statement or
its negation.
b. There is a triangle x such that for all
squares y, x is to the right of y. Figure 3.3.1
57
3.3.5. Order of Quantifiers
∀ people x, ∃ a person y such that x loves y.
∃ a person y such that ∀ people x, x loves y.
Except for the order of the quantifiers,
these statements are identical.
Given any person, it is possible to find
someone whom that person loves.
They are not There is one amazing individual
logically who is loved by all people.
equivalent!
61
Order of Quantifiers
In a statement containing both and ,
changing the order of the quantifiers usually
changes the meaning of the statement.
However, if one quantifier immediately follows
another quantifier of the same type, then the order
of the quantifiers does not affect the meaning.
62
Order of Quantifiers
Refer to the Tarski’s world of Figure 3.3.1. What are the truth
values of the following two statements?
a. For every square x, there is a triangle y
such that x and y have different colors.
b. There exists a triangle y such that for
every square x, x and y have different
Figure 3.3.1
colors.
60
3.3.6. Formal Logical Notation
In some areas of computer science, logical statements
are expressed in purely symbolic notation.
The notation involves using predicates to describe all
properties of variables and omitting the words such as in
existential statements.
“x in D, P(x)” written as x (x in D P(x))
“∃x in D such that P(x)” written as x (x in D P(x))
64
Formal Logical Notation: Formalizing Statements in a
Tarski’s World
Example:
Tarski’s world.
Let the common domain D of all variables be the set of all the
objects in the Tarski’s world.
Triangle(x): “x is a triangle” Blue(x): “x is blue”
Circle(x): “x is a circle” Gray(x): “x is gray”
Square(x): “x is a square” Black(x): “x is black”
RightOf(x,y): “x is to the right of y”
Above(x,y): “x is above y”
SameColorAs(x,y): “x has the same color as y”
x = y: “x is equal to y”
65
Formal Logical Notation: Formalizing Statements in a
Tarski’s World
Use formal, logical notation to write the following statements,
and write a formal negation for each statement.
a. For all circles x, x is above f.
Statement: x (Circle(x) Above(x, f))
Negation: ~(x (Circle(x) Above(x, f)))
x ~(Circle(x) Above(x, f)) x (Circle(x) ~Above(x, f))
b. There is a square x such that x is black.
Statement: x (Square(x) Black(x))
Negation: ~(x (Square(x) Black(x)))
x ~(Square(x) Black(x)) x (~Square(x) ~Black(x))
66
Formal Logical Notation: Formalizing Statements in a
Tarski’s World
Use formal, logical notation to write the following statements,
and write a formal negation for each statement.
c. For all circles x, there is a square y such that x and y have the
same color.
Statement: ∀x(Circle(x) ∃y(Square(y) SameColor(x, y)))
Negation:
67
Formal Logical Notation: Formalizing Statements in a
Tarski’s World
Use formal, logical notation to write the following statements,
and write a formal negation for each statement.
d. There is a square x such that for all triangles y, x is to right of y.
Statement:
Negation:
68
Formal Logical Notation
Formal logical notation is used in branches of computer science such as
artificial intelligence, program verification, and automata theory and
formal languages.
Taken together, the symbols for quantifiers, variables, predicates, and
logical connectives make up what is known as the language of first-
order logic.
Even though this language is simpler in many respects than the
language we use every day, learning it requires the same kind of practice
needed to acquire any foreign language.
69
3.3.7. Prolog
The programming language Prolog (short for programming in logic)
was developed in France in the 1970s by A. Colmerauer and P.
Roussel to help programmers working in the field of artificial
intelligence.
A simple Prolog program consists of a set of statements describing
some situation together with questions about the situation. Built
into the language are search and inference techniques needed to
answer the questions by deriving the answers from the given
statements.
This frees the programmer from the necessity of having to write
separate programs to answer each type of question.
70
Prolog: A Prolog Program
Consider the following picture, which shows colored blocks
stacked on a table.
The following are statements in Prolog that describe this picture
and ask two questions about it.
71
Prolog: A Prolog Program
isabove(g, b1) color(g, gray) color(b3, blue)
isabove(b1, w1) color(b1, blue) color(w1, white)
isabove(w2, b2) color(b2, blue) color(w2, white)
isabove(b2, b3) isabove(X, Z) if isabove(X, Y) and isabove(Y, Z)
?color(b1, blue) ?isabove(X, w1)
The statements “isabove(g, b1)” and “color(g, gray)” are to be
interpreted as “g is above b1” and “g is colored gray”.
The statement “isabove(X, Z) if isabove(X, Y) and isabove(Y, Z)” is
to be interpreted as “For all X, Y, and Z, if X is above Y and Y is
above Z, then X is above Z.”
72
Prolog: A Prolog Program
The program statement
?color(b1, blue) Prolog answers this by writing
is a question asking whether Yes
block b1 is colored blue.
The program statement Prolog answers this by giving a
?isabove(X, w1) list of all such blocks. In this
case, the answer is
is a question asking for which
blocks X the predicate “X is X = b1, X = g.
above w1” is true..
Infer the solution X = g from the following statements:
isabove(g, b1)
isabove(b1, w1)
isabove(X, Z) if isabove(X, Y) and isabove(Y, Z) 70
Prolog: Quick Quiz
Write the answers Prolog would give if the following
questions were added to the program above.
a. ?isabove(b2, w1) “No”
b. ?color(w1, X)
c. ?color(X, blue)
isabove(g, b1) color(g, gray) color(b3, blue)
isabove(b1, w1) color(b1, blue) color(w1, white)
isabove(w2, b2) color(b2, blue) color(w2, white)
isabove(b2, b3) isabove(X, Z ) if isabove(X, Y ) and isabove(Y, Z)
71
3.4 Arguments with Quantified
Statements
March 19, 2024 75
3.4.1. Universal Instantiation
The rule of universal instantiation:
If some property is true of everything in the set,
then it is true of any particular thing in the set.
Universal instantiation is the fundamental tool of
deductive reasoning.
76
3.4.2. Universal Modus Ponens
The rule of universal instantiation can be combined with
modus ponens to obtain the valid form of argument
called universal modus ponens.
Universal Modus Ponens
Formal version Informal version
x, if P(x) then Q(x). If x makes P(x) true, then x makes Q(x) true.
P(a) for a particular a. a makes P(x) true.
Q(a). a makes Q(x) true.
77
Recognizing Universal Modus Ponens
Rewrite the following argument using quantifiers, variables,
and predicate symbols. Is this argument valid? Why?
If an integer is even, then its square is even.
k is a particular integer that is even.
k2 is even.
Solution:
Premise: x, if x is an even integer then x2 is even.
Let E(x) be “x is an even integer”, let S(x) be “x2 is even”, and
let k stand for a particular integer that is even.
x, if E(x) then S(x) . This argument has the form of
E(x), for a particular k. universal modus ponens and
S(k). is therefore valid.
78
3.4.3. Use of Universal Modus Ponens in a Proof
Proof: The sum of any two even integers is even.
integers x, x is even iff an integer k such that x = 2k.
Suppose m and n are particular but arbitrarily chosen
even integers, then m = 2r for some integer r(1), and n =
2s for some integer s(2).
Hence
m + n = 2r + 2s = 2(r + s) (3)
Now (r + s) is an integer(4), and so 2(r + s) is even(5).
Thus m + n is even.
79
Use of Universal Modus Ponens in a Proof
How universal modus ponens is used in the proof.
Suppose m and n are particular but arbitrarily chosen
even integers, then m = 2r for some integer r(1), and n =
2s for some integer s(2).
(1) If an integer is even, then it equals twice some integer.
m is a particular even integer.
m equals twice some integer r.
(2) Similar to (1).
80
Use of Universal Modus Ponens in a Proof
How universal modus ponens is used in the proof.
Hence
m + n = 2r + 2s = 2(r + s) (3)
(3) If a quantity is an integer, then it is a real number.
r and s are particular integers.
r and s are real numbers.
For all a, b, and c, if a, b, and c are real numbers, then
ab + ac = a(b + c).
2, r, and s are particular real numbers.
2r + 2s = 2(r + s).
81
Use of Universal Modus Ponens in a Proof
How universal modus ponens is used in the proof.
Now (r + s) is an integer(4), and so 2(r + s) is even(5).
Thus m + n is even.
(4) For all u and v, if u and v are integers, then (u + v) is an integer.
r and s are two particular integers.
(r + s) is an integer.
(5) If a number equals twice some integer, then that number is
even.
2(r + s) equals twice the integer (r + s).
2(r + s) is even.
82
3.4.4. Universal Modus Tollens
Another crucially important rule of inference is universal
modus tollens. Its validity results from combining
universal instantiation with modus tollens.
Universal modus tollens is the heart of proof of
contradiction.
Universal Modus Tollens
Formal version Informal version
x, if P(x) then Q(x). If x makes P(x) true, then x makes Q(x) true.
~Q(a) for a particular a. a does not make Q(x) true.
~P(a). a does not makes P(x) true.
83
Recognizing Universal Modus Tollens
Rewrite the following argument using quantifiers, variables, and
predicate symbols. Write the major premise in conditional form.
Is this argument valid? Why?
All human beings are mortal.
Zeus is not mortal.
Zeus is not human.
Solution:
Premise: x, if x is human then x is mortal.
Let H(x) be “x is human”, let M(x) be “x is mortal”, and let Z
stand for Zeus.
x, if H(x) then M(x) . This argument has the form of
~M(Z). universal modus tollens and is
~H(Z). therefore valid.
84
3.4.5. Proving Validity of Arguments with Quantified
Statements
The intuitive definition of validity for arguments with
quantified statements is the same as for arguments with
compound statements.
An argument is valid if, and only if, the truth of its conclusion
follows necessarily from the truth of its premises.
Definition 3.4.1 (Valid Argument Form)
To say that an argument form is valid means the following:
No matter what particular predicates are substituted for the
predicate symbols in its premises, if the resulting premise
statements are all true, then the conclusion is also true.
An argument is called valid if, and only if, its form is valid.
85
3.4.6. Using Diagrams to Test for Validity
Consider the statement: All integers are rational numbers.
integers n, n is a rational number.
Figure 3.4.1
86
Using Diagrams to Test for Validity
Use a diagram to show the invalidity of the following
argument:
All human beings are mortal.
Felix is mortal.
Felix is a human being.
Major premise Minor premise
Figure 3.4.4
87
Using Diagrams to Test for Validity
Use a diagram to show the invalidity of the following
argument:
All human beings are mortal. Hence,
Felix is mortal. argument
Felix is a human being. is invalid.
Conclusion Conclusion
is true. is false.
Figure 3.4.5
88
Using Diagrams to Test for Validity
The argument of previous example would be valid if the
major premise were replaced by its converse. But since a
universal conditional statement is not logically equivalent to
its converse, such a replacement cannot, in general, be
made.
We say that this argument exhibit the converse error.
Converse Error (Quantified Form)
Formal version Informal version
x, if P(x) then Q(x). If x makes P(x) true, then x makes Q(x) true.
Q(a) for a particular a. a makes Q(x) true.
P(a). a makes P(x) true.
89
Using Diagrams to Test for Validity
The following form of argument would be valid if a
conditional statement were logically equivalent to its inverse.
But it is not, and the argument form is invalid.
We say that this argument exhibit the inverse error.
Inverse Error (Quantified Form)
Formal version Informal version
x, if P(x) then Q(x). If x makes P(x) true, then x makes Q(x) true.
~P(a) for a particular a. a does not make P(x) true.
~Q(a). a does not make Q(x) true.
90
An Argument with “No
Use diagrams to test the following argument for validity:
No polynomial functions have horizontal asymptotes.
This function has a horizontal asymptote.
• This function is not a polynomial function.
Hence argument
is valid.
Figure 3.4.6
91
An Argument with “No
No polynomial functions have horizontal asymptotes.
This function has a horizontal asymptote.
• This function is not a polynomial function.
Alternatively, transform the first statement into:
x, if x is a polynomial function, then x does not have
a horizontal asymptote.
Then the argument has the form:
x, if P(x) then Q(x).
This is valid by universal
~Q(a), for a particular a.
modus tollens.
• ~P(a).
92
3.4.7. Creating Additional Forms of Argument
We have seen:
Universal Universal
Modus ponens +
instantiation modus ponens
Universal Universal
Modus tollens +
instantiation modus tollens
In the same way, additional forms of arguments involving
universally quantified statements can be obtained by
combining universal instantiation with other of the valid
argument forms discussed earlier.
93
Creating Additional Forms of Argument
Consider the following argument:
p q
q r
p r
This can be combined with universal instantiation to
obtain a valid argument form.
Universal Transitivity
Formal version Informal version
x, P(x) Q(x). Any x that makes P(x) true makes Q(x) true.
x, Q(x) R(x). Any x that makes Q(x) true makes R(x) true.
x, P(x) R(x). Any x that makes P(x) true makes R(x) true.
94
Evaluating an Argument for Tarski’s World
Consider the Tarski’s world:
Reorder and rewrite the premises to
show that the conclusion follows as a
valid consequence from the premises
1. All the triangles are blue.
2. If an object is to the right of all the Figure 3.3.1
squares, then it is above all the circles.
3. If an object is not to the right of all the
squares, then it is not blue.
All the triangles are above all the circles.
95
Evaluating an Argument for Tarski’s World
Consider the Tarski’s world:
Reorder and rewrite the premises to
show that the conclusion follows as a
valid consequence from the premises
Step 1:
1. x, if x is a triangle, then x is blue.
2. x, if x is to the right of all the squares, Figure 3.3.1
then x is above all the circles.
3. x, if x is not to the right of all the
squares, then x is not blue. Should be same as
conclusion of the
x, if x is a triangle, then x is above all last premise.
the circles. Should be same as hypothesis
93
of the first premise.
Evaluating an Argument for Tarski’s World
Consider the Tarski’s world:
Reorder and rewrite the premises to
show that the conclusion follows as a
valid consequence from the premises
Step 2:
1. x, if x is a triangle, then x is blue.
2. x, if x is not to the right of all the Figure 3.3.1
squares, then x is not blue.
3. x, if x is to the right of all the squares, Rewrite it in
then x is above all the circles. contrapositive form.
x, if x is a triangle, then x is above all
the circles.
97
Evaluating an Argument for Tarski’s World
Consider the Tarski’s world:
Reorder and rewrite the premises to
show that the conclusion follows as a
valid consequence from the premises
Step 3:
1. x, if x is a triangle, then x is blue.
2. x, if x is blue, then x is to the right of Figure 3.3.1
all the squares.
3. x, if x is to the right of all the squares,
then x is above all the circles.
x, if x is a triangle, then x is above all
the circles.
98
3.4.8. Remark on the Converse and Inverse Errors
A variation of the converse error is a very useful reasoning tool, Only for
provided that it is used with caution. reading.
It is the type of reasoning that is used by doctors to make medical
diagnoses and by auto mechanics to repair cars.
It is the type of reasoning used to generate explanations for
phenomena. It goes like this: If a statement of the form
For all x, if P(x) then Q(x)
is true, and if
Q(a) is true, for a particular a,
then check out the statement P(a); it just might be true.
99
Remark on the Converser and Inverse Errors
For instance, suppose a doctor knows that Only for
For all x, if x has pneumonia, then x has a fever and reading.
chills, coughs deeply, and feels exceptionally tired
and miserable.
And suppose the doctor also knows that
John has a fever and chills, coughs deeply,
and feels exceptionally tired and miserable.
On the basis of these data, the doctor concludes that a diagnosis of
pneumonia is a strong possibility, though not a certainty.
This form of reasoning has been named abduction by
researchers working in artificial intelligence.
100
DISCRETE STRUCTURES
Proof Techniques
Acknowledgement
• The contents of these slides have origin from School of
Computing, National University of Singapore.
• We greatly appreciate support from Mr. Aaron Tan Tuck Choy,
and Dr. Terence SIM Mong Cheng for kindly sharing these
materials.
March 19, 2024 2
Policies for students
• These contents are only used for students PERSONALLY.
• Students are NOT allowed to modify or deliver these contents to
anywhere or anyone for any purpose.
March 19, 2024 3
Recording of modifications
• Course website address is changed to
https://elearning.tdtu.edu.vn
• Course codes CS1231, CS1231S are placed by 501044.
March 19, 2024 4
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
The essential quality of a proof
is to compel belief.
Pierre de Fermat,
1601 — 1665
Reading
Sections 2.1 — 2.7 of Campbell
Sections 4.1 — 4.3, 4.7 of Epp
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
1.1.1. Notation
We begin our study of proofs by recalling the following notations:
R: the set of all real numbers
Z: the set of all integers
Q: the set of all rational numbers
Examples of real numbers: -1, π, 17, 2
Examples of integers: -3263, 0, 9, 232
21 1
Examples of rationals:− , , 5, 9. 99
10 2
And, as is well-known, all integers are rationals, and all rationals
are reals.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Additional notations:
∃ : There exists ...
∃! : There exists a unique ...
∀: For all ...
∈ : Member of (a set) ...
s : such that
Examples:
∃x ∈ Z s x 2 = 4
There exists an integer x such that x 2 = 4.
∀y ∈ R, ∃!z ∈ R s y + z = 0
For all real numbers y, there is a unique real z such that y + z = 0.
or
Every real number y has exactly one real z such that y + z = 0.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
We will also assume, without proof, the usual properties of
numbers. For example:
• Closure: integers are closed under addition and multiplication,
i.e. ∀x,y ∈ Z, x + y ∈ Z and xy ∈ Z.
For all real numbers a,b and c,
• Commutativity: a + b = b + a and ab = ba
• Distributivity: a(b + c) = ab + ac and (b + c)a = ba + ca
• Trichotomy: exactly one of the following is true:
a < b, or b < a, or a = b
See Appendix A of Epp’s textbook for all the properties.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
1.1.2. Number Theory
Let’s learn some Number Theory.
Definition 1.1.1 (Colorful)
An integer n is said to be colorful if there exists some integer k
such that n = 3k.
This terminology colorful is non-standard; used only in this class.
Questions:
• Is 1353 colorful?
• What about (208 − 201)?
• 0?
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Answer
• Yes, 1353 is colorful because 1353 = 3 × 451.
• No, because 208 − 201 = 7, and there is no integer k such
that 7 = 3k. (See Example 7: Proposition 1.6.2)
• Yes, 0 is colorful because 0 = 3 × 0.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
1.2. Proof by Construction
Existence Proof 1
Prove the following:
∃x ∈ Z s x > 2 and x 2 − 5x + 6 > 0.
That is, there exists an integer x such that x > 2 and
x 2 − 5x + 6 > 0.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Proof:
1. Note that 1000 ∈ Z and 1000 > 2.
2. Also, 10002 − 5(1000) + 6 = 995006 > 0.
QED1
• A proof is a concise, polished argument explaining the validity
of a statement to a skeptic (usually, you).
• Concise means there are no irrelevant details. It also means to
use few words.
• Polished means it should be the final draft, i.e. you need to
revise it to make it understandable, like writing an essay.
• Argument means every step should follow logically from all
previous steps.
1
quot erat demonstrandum — that which was to be demonstrated.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
• A proof is not an attempt to determine whether or not
something is true. That is your scratch work. You should be
convinced the statement is true before you write your proof.
• In the proof above, there is no need to explain how 1000 was
obtained. You just need to show that 1000 has the said
properties. Of course, many integers satisfy the same
properties (as you can easily verify), and any one of these will
suffice for the proof.
• This style of proof — where you explicitly find the value with
the correct properties — is called a proof by construction. It
is the most direct way to prove that something exists.
• Sometimes, finding the right thing takes some cleverness, as
the next example shows.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Existence Proof 2
Prove that there exist irrational numbers p and q such pq is
rational.
Recall that a number x is rational if it can be written as a ratio of
two integers: x = ba , where a,b ∈ Z and b = / 0.
A number that is not rational is irrational.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Proof:
1. We know from Theorem 4.7.1 (Epp) that 2 is irrational.
2
2. Consider 2 : it is either rational or irrational.
3. Case 1: It is rational.
3.1 Let p = q = 2, and we are done.
4. Case 2: It is irrational.
2
4.1 Then let p = 2 , and q = 2.
4.2 p is irrational (by assumption), so is q (by Theorem
4.7.1 (Epp))
2
4.3 Consider = ( 2 ) 2pq
4.4 = ( 2) 2× 2 , by the power law
4.5 = ( 2)2 = 2, by algebra
4.6 Clearly 2 is rational.
5. In either case, we have found the required p and q.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
1.2.3. Disproof
• To disprove a statement, you are arguing why the statement is
not true.
• You may use the same type of argument as in a proof. But
sometimes, it is easier just to show a counterexample.
Example
Disprove this statement:
∀x, y ∈ Z+, 𝑥 + 𝑦 = 𝑥 + 𝑦 .
In other words, for all positive integers x and y ,
𝑥 + 𝑦 = 𝑥 + 𝑦.
Z+ denotes the set of nonnegative integers, i.e. {1, 2, 3, . . .}.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Disproof
1. Let x = y = 2. Clearly, they are nonnegative integers.
2. Then 𝑥 + 𝑦 = 2 + 2 = 2,
3. But, 𝑥 + 𝑦= 2 + 2 = 2.828427…
4. Thus 𝑥 + 𝑦 ≠ 𝑥 + 𝑦, and the statement is false.
Disproof by counterexample is particularly useful for statements
involving ∀.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Quiz: you try
If the following statement is true, prove it, otherwise give a
counterexample:
The square of an irrational number is irrational.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
1.2.4. Jigsaw Analogy
• Doing a proof is like solving a jigsaw puzzle2. No two jigsaws
are alike; no two proofs are alike.
• Sometimes you solve large chunks quickly; other times you get
stuck. You don’t have to solve from top to bottom.
• Some strategies are useful eg. fixing the border of the puzzle
first. Likewise, there are useful strategies for proofs.
2
Adapted from D. Velleman, How to Prove It, 2nd Edition, 2006.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
1.3. if-then statements
Many statements to be proven take the form:
if P then Q
One strategy is to use a direct proof: assume P is true, then
combine this with other known facts F and theorems T to
conclude that Q must be true.
Think of P as the starting point, and Q the destination. The other
known facts F and theorems T make up the route that go from P
to Q. Each step of the route must be logically connected.
In your draft, you can work forwards from P, or backwards from Q,
but be careful never to assume Q to be true.
In your final, polished proof, you must argue only forwards, not
backwards.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Example
Prove that:
if x,y are colorful integers, then so is x + 2y.
Identify P and Q to be:
P : x,y are colorful integers
Q : x + 2y is colorful
We can immediately write down the start and end of the proof, as
follows:
Draft proof:
1. Assume that x,y are colorful integers.
2. ...
3. And thus x + 2y is colorful. QED.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
The next logical thing is to use the definition of colorful.
Draft proof:
1. Assume that x,y are colorful integers.
2. Then by definition of colorful, ∃a,b ∈ Z such that x = 3a
and y = 3b.
3. ...
4. So ∃c ∈ Z such that x + 2y = 3c.
5. And thus x + 2y is colorful, by definition of colorful. QED.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
This means we need to connect c to a and b. Obviously, we should
try writing (x + 2y) in terms of a,b:
x + 2y = 3a + 2(3b), by substitution
= 3a + (2 ·3)b, by associativity
= 3a + (3 ·2)b, by commutativity
= 3a + 3(2b), by associativity
= 3(a + 2b), by distributivity
Aha! It is clear what c should be now. So here’s our final proof:
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Proof.
1. Assume that x,y are colorful integers.
2. Then by definition of colorful, ∃a,b ∈ Z such that x = 3a
and y = 3b.
3. Now, x + 2y = 3a + 2(3b), by substitution
4. = 3a + 3(2b), by commutativity and associativity
5. = 3(a + 2b), by distributivity
6. Let c = a + 2b. Note that a + 2b ∈ Z because integers
are closed under addition and multiplication.
7. So ∃c ∈ Z such that x + 2y = 3c.
8. And thus x + 2y is colorful, by definition of colorful.□
Note that every step is justified by appealing to definitions or to
known properties of integers.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
1.3.2. Divisibility
Definition 1.3.1 (Divisibility)
e.g. Clearly 3 | 6 (3 divides 6), but 4 ∤ 11 (4 does not divide 11).
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
More examples
• For integers a,b,c, it is clear that if a | b and a | c, then
a | (b + c). Reason: if a is a factor of b and c, then it is a
factor of the sum.
Trivial example: 2 | 6 and 2 | 8. Also, 2 | (6 + 8).
• But the inverse is not true. That is, if a ∤b and a ∤c, then it
is still possible to have a | (b + c).
Trivial example: 3 ∤10 and 3 ∤14, but 3 | (10 + 14).
• Finally, it should be obvious that a | ab, for any b.
Warning!
Do NOT use division. There is no concept of division in Number
Theory. The notation a | b simply means a is a factor of b. No
actual division is performed.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Theorem 4.3.1 (Epp)
∀a,b ∈ Z+ , if a | b then a ≤ b.
That is, when dealing with positive integers, a divisor of a number
cannot be larger than the number.
Note that the theorem is silent for the case b = 0, because 0 is not
positive.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
When doing proofs, it is often helpful to keep track of what we are
given and what our goals are. Since the statement to be proven is
an if-then statement, we can quickly write the P as our givens and
the Q as our goal.
Givens Goals
a,b ∈ Z+ a≤b
a|b
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
From the definition of a | b, we know that b = ak for some integer
k. We may add this to our givens.
Givens Goals
a,b ∈ Z+ a≤b
a|b
b = ak, for some k ∈ Z
• So we now have one equality in our givens, but our goal
involves an inequality. How do we achieve this?
• Intuitively, the equality says that if a needs to be multiplied by
something to get b, then b must be larger than a. But this
requires k to be positive. Fortunately, rule T25 of Appendix A
(Epp) assures this.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
• So what we want is to argue that since ak = b and k is
positive, we may “drop” k to get a ≤ b. Although this is
intuitively true, none of the rules in Appendix A (Epp)
justifies this argument. We need another approach.
• Since k is a positive integer, we have the inequality 1 ≤ k for
“free”, which we can add to our givens. We can now invoke
rule T20 to multiply both sides of this inequality by a (which
is positive), to get a ≤ ak. The right hand side is now b,
which is our goal. Hence our proof:
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Proof.
1. Assume a,b ∈ Z+ , and a | b.
2. So by definition of divisibility, b = ak for some k ∈ Z.
3. Since a,b > 0, and b = ak, we deduce k is positive by
rule T25 of Appendix A (Epp).
4. Thus 1 ≤ k.
5. Using rule T20, multiply the inequality by a to get
a ≤ ak = b □.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Consider the statement:
∀a,b,c ∈ Z, if a | b and a | c, then ∀x,y ∈ Z,a | (bx + cy)
That is, if a divides both b and c, then it also divides (bx + cy),
for any integers x, y.
The following is an attempted disproof of the statement. Let’s play
detective and determine if it is right or wrong.
Proposed Disproof
1. Let a = 12,b = 4,c = 3.
2. We know that 12 | 4 and 12 | 3.
3. Let x = 1,y = 5. Then bx + cy = 4 ·1 + 3 ·5 = 19.
4. Clearly, 12 ∤19.
5. Therefore, ∃x,y ∈ Z such that a ∤(bx + cy).
6. Therefore, the statement is not true.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Now consider this proposed proof. Is it right or wrong?
Proposed Proof
1. Assume a | b and a | c for integers a,b,c.
2. So am = b and an = c, for some m,n.
3. Then bx + cy = amx + any = a(mx + ny).
4. Therefore, a | (bx + cy). QED
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Consider yet another proposed proof. Is it right or wrong?
Proposed Proof
1. Suppose a | b and a | c.
2. Then ax = b and ay = c for any integers x and y.
3. Then bx + cy = (ax)x + (ay)y = a(xx + yy).
4. Since x and y are any integers and the integers are
closed under addition and multiplication, we know that
(xx + yy) ∈ Z.
5. Thus a | (bx + cy). QED.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
1.4. for-all statements
∀x P(x)
The strategy for proving such statements is to prove from the
particular to the general. That is, take x to be a particular, but
arbitrarily chosen, value. Prove that P(x ) is true. Conclude that
since P(x) is true for this particular x (which has no other special
properties), it must be true for all x.
An analogy: suppose you are asked to prove the statement “All CS
students take CS1231”. You pick Tom, a typical CS student. Now
you show that Tom is taking (or has taken) CS1231. You then
argue that, since Tom is representative of CS students, what is
true about him must be true of all other CS students. And thus
the statement is true.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Theorem 4.3.3 (Epp) Transitivity of Divisibility
∀a,b,c ∈ Z , if a | b and b | c then a | c.
Proof.
1. Take any three integers a,b,c.
2. Assume that a | b and b | c.
3. Then by definition of divisibility, we know that b = ar
and c = bs, for some r ,s ∈ Z
4. Thus, c = (ar )s = a(rs), by basic algebra
5. Now, rs is an integer, by closure of integers
6. ∴ a | c, by definition of divisibility
7. Since a,b, c was chosen arbitrarily, the statement is true for
all integers. □
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Remarks:
• We will usually omit Line 7, since it is understood.
• For Line 1, if instead we had said: Take positive integers
a,b, c, then the proof would still be valid until Line 6. But in
Line 7, we would not be able to generalize to all integers,
because our proof thus far was valid only for positive integers.
• Likewise, we cannot assume a ≤ b or b ≤ c or a ≤ c, since
this is an unnecessary restriction.
• Another common mistake is to say, in Line 3: b = ar and
c = br. This forces b and c to be the same multiple, which
again restricts our proof.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
1.5. Proof by Contraposition
The contrapositive of the statement:
if P then Q
is the statement:
if ∼ Q then ∼ P
Note that ∼ P means not P, the negation of P. If P is True, then
∼ P is False, and vice versa.
Both statements are logically equivalent; that is, they are True and
False for exactly the same truth values of P and Q.
Thus, instead of proving an if-then statement directly, we may
prove it indirectly by proving its contrapositive.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Prove the following by Contraposition:
if x 2 is irrational then x is irrational
Proof.
Contrapositive form: if x is rational then x 2 is rational
1. Assume x is rational.
2. Then by definition of rationals, there exist integers a,b
such that b /= 0 and x = a/b.
3. So x 2 = (a ·a)/(b ·b), by basic algebra
4. Both numerator and denominator are integers, by the
closure property of integers.
5. Moreover, by rule T21 of Appendix A (Epp), b2 /= 0.
6. Thus, x 2 is a ratio of two integers.
7. Thus, by definition of rationals, x 2 is rational. □
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Remarks:
• To prove the statement directly, you would have to start by
assuming x 2 is irrational. That is, x 2 ≠ a/b for all integer a
and nonzero integer b.
The unequality ≠ makes it difficult to continue. What form
can you let x 2 take? Irrationality is defined by the absence,
rather than the presence, of a form. If you cannot write down
a form for x 2, then you cannot manipulate it to get a form for
x. The proof cannot proceed.
• By using the contrapositive, you instead deal with rationals,
rather than irrationals. You can thus exploit the form of
rationals in your proof.
• Thus, whenever you encounter an if-then statement involving
the absence of a form, you should consider proving by
contraposition instead.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
1.6. Proof by Contradiction
Reductio ad absurdum is one of a mathematician’s finest weapons.
G.H. Hardy, 1877 — 1947
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Remarks:
• To prove a statement S by contradiction, you first assume
that ∼ S is true. Based on this, you use known facts and
theorems to arrive at a contradiction. Since every step of your
argument thus far is logically correct, the problem must lie in
your assumption. Thus, you conclude that ∼ S is false, and
hence S is true.
• A formal definition of contradiction will be given in the
chapter on logic; for now, it suffices to say that a
contradiction is something that is logically impossible. For
example, at the start of your proof, you may assume (or
deduce) that x ≥ 5. Then later you deduce that x < 5. These
two facts are clearly contradictory.
• In a proof by contradiction, the contradictory facts need not
be directly related to S. As long as you contradict any known
thing in mathematics, eg. 1 = 0, your proof has succeeded.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Definition 1.6.1 (Even and Odd)
Examples:
328 is even because 328 = 2 × 164
91 is odd because 91 = 2 × 45 + 1
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Theorem 4.7.1 (Epp) Irrationality of 2
2 is irrational
As with Example 5, it is difficult to use a direct proof because
irrationality is the absence of a form.
On the other hand, proving by contradiction begins by assuming
that 2 is rational, thereby allowing us to exploit the form of a
rational number. The resulting proof is a mathematical classic.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Proof by contradiction
1. Assume that 2 is rational.
2. Then by definition of rationals, there exists integers m,n,
with n ≠ 0, such that 2 = m/n.
3. Further, we may assume that m/n is reduced to
lowest terms, ie. the only common factor of m,n is 1.
4. From Line 2, m2 = 2n2, by basic algebra.
5. So m2 is even, by definition of even, and because n2
is an integer by the closure property.
6. ⇒ m is even, by Proposition 4.6.4 (Epp)
7. ⇒ ∃k ∈ Z ∋ m = 2k, by definition of even.
8. Subtituting into Line 4: (2k)2 = 2n2.
9. ⇒ 2k2 = n2, by basic algebra.
···
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
proof cont’d
10. So n2 is even, by definition of even, and because k2
is an integer by the closure property.
11. ⇒ n is even by Proposition 4.6.4 (Epp).
12. But this means 2 is a common factor of m,n,
contradicting Line 3.
13. Hence 2 must be irrational. □
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Proposition 1.6.2
7 is not colorful.
Proof.
[Proof by contradiction]
1. Suppose 7 is colorful.
2. Then, by definition of colorful, 7 = 3k for some integer k.
3. ⇒ 6 = 3k − 1, by basic algebra.
4. ⇒ 1 = 3(k − 2), by basic algebra.
5. Since k − 2 is an integer by the closure property,
the above means that 3 | 1, by definition of divisibility.
6. Then by Theorem 4.3.1 (Epp), this means 3 ≤ 1.
7. Clearly, this is absurd, so the Proposition is true. □
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Remarks:
• It is wrong to say: “7 is not colorful because 7/3 = 2.333...,
which is not an integer.” There is no concept of division in
Number Theory. Moreover, the definition of colorful does not
use division, but instead uses the existence of an integer.
• It is also wrong to say: “I cannot find an integer k such
7 = 3k, therefore 7 is not colorful.” If you cannot find it, it
doesn’t mean no such integer exists.
• The irrefutable way to prove the non-existence of something is
to show that if it exists, then it will lead to an absurd
conclusion. This is the essence of a proof by contradiction.
Introduction by Construction if-then for-all by Contraposition by Contradiction Summary
Summary
• Proofs are at the heart of mathematics.
• Proving a statement is like solving a jigsaw puzzle. No two
proofs are alike. Some strategies are useful.
• These lecture notes illustrate strategies for dealing with:
existence proofs, if-then and for-all statements, disproof by
counterexample, proof by contraposition and contradiction.
• For a given proof, which strategy to use will come with
experience. For longer proofs, multiple strategies may be
combined.
• Read Section 4.1 (pages 154 — 158) of the textbook for how
to correctly write a proof, and the common mistakes to avoid.
Use indentation to facilitate reading.
• Two more proof techniques — Induction and Diagonalization
— will be covered in future lectures.
DISCRETE STRUCTURES
Number Theory
Acknowledgement
• The contents of these slides have origin from School of
Computing, National University of Singapore.
• We greatly appreciate support from Mr. Aaron Tan Tuck Choy,
and Dr. Terence SIM Mong Cheng for kindly sharing these
materials.
March 19, 2024 2
Policies for students
• These contents are only used for students PERSONALLY.
• Students are NOT allowed to modify or deliver these contents to
anywhere or anyone for any purpose.
March 19, 2024 3
Recording of modifications
• Course website address is changed to
https://elearning.tdtu.edu.vn
• Course codes CS1231, CS1231S are placed by 501044.
March 19, 2024 4
Recap Primes
God made the integers, all else
is the work of man.
Leopold Kronecker,
1823 — 1891
Reading
Sections 4.1 — 4.7 of Epp
Recap Primes
4.1. Recap
Definition 1.3.1 (Divisibility)
Reminder: No division is actually performed when we say: d | n.
Recap Primes
Theorem 4.1.1
∀a,b,c ∈ Z , if a | b and a | c, then ∀x,y ∈ Z ,a | (bx + cy)
That is, if a divides both b and c, then a divides their linear
combination.
Since it is useful, we make it a theorem.
Recap Primes
Proof.
1. For any a,b,c ∈ Z :
2. If a | b and a | c:
3. Let k ∈ Z such that b = ak. (by definition of divisibility)
4. Let m ∈ Z such that c = am. (by definition of
divisibility)
5. For any x,y ∈ Z :
6. bx + cy = (ak)x + (am)y = a(kx + my).
(by basic algebra)
7. Note that kx + my ∈ Z . (by closure of addition
and multiplication over integers)
8. Thus a | bx + cy. (by definition of divisibility) □
Recap Primes
4.2. Primes
Prime numbers are to integers
what atoms are to materials.
They are the indivisible
building blocks of integers.
We will learn some key
properties and see some
applications of prime numbers.
Recap Primes
Definition 4.2.1 (Prime number)
• 1 is neither prime nor composite.
• The first few primes are: 2,3,5,7,11,13,17,19.
• The first few composites are: 4,6,8,9,10,12,14,15.
Recap Primes
Every integer n > 1 is either prime or composite.
To see this, consider all positive pairs r , s such that n = rs. There
is always the trivial pairs r = n, s = 1, and r = 1, s = n. Note that
they satisfy 1 ≤ r,s ≤ n. But if these are the only pairs, then n is
prime by definition.
Otherwise, there exists a positive pair r , s such that n = rs and
1 < r,s < n. And thus n is composite by definition.
Recap Primes
4.2.1. Prime properties
Primes have interesting properties, some of which we will now
study. We begin with the property that if one prime divides
another, then they must be equal.
Proposition 4.2.2
For any two primes p and p', if p | p' then p = p'.
Note that this property does not hold for composites, e.g. 4 | 8 but
4 ≠ 8.
Recap Primes
Proof:
1. For any primes p and p':
2. If p | p':
3. Let k ∈ Z such that p' = pk, by definition of divisibility.
4. Then p = 1 or p = p', since p' is prime.
5. Also, p > 1, since p is prime.
6. Therefore p = p'. □
The next property of primes sets the stage for the important fact
that prime numbers do not end; ever larger primes exist.
Recap Primes
Proposition 4.7.3 (Epp)
For any a ∈ Z and any prime p, if p | a then p ∤ (a + 1).
Proof: (by Contradiction)
1. Suppose not. Then there exists a ∈ Z and prime p such that
p | a and p | (a + 1).
2. Then p | a(−1) + (a + 1)(1), by Theorem 4.1.1.
3. Then p | 1, by basic algebra.
4. By Theorem 4.3.1 (Epp), this implies p ≤ 1,
which contradicts the fact that p > 1.
5. Thus by the Contradiction Rule, the statement is true. □
Recap Primes
The statement to be proven takes the form:
S = ∀x(∀y(P (x,y) → Q (x,y)))
Thus, its negation is:
∼ S ≡ ∼ (∀x(∀y(P (x,y) → Q (x,y))))
≡ ∃x ∼ (∀y(P (x,y) → Q (x,y)))
≡ ∃x(∃y ∼ (P (x,y) → Q (x,y)))
≡ ∃x(∃y ∼ (∼ P (x,y) ∨Q (x,y)))
≡ ∃x(∃y(∼ (∼ P (x,y))∧ ∼ Q (x,y)))
≡ ∃x(∃y(P (x,y)∧ ∼ Q (x,y)))
The last line is the form used in Step 1 of the proof.
Recap Primes
Theorem 4.7.4 (Epp): Infinitude of Primes.
The set of primes is infinite.
Proof: (by Contradiction)
1. Suppose the set of primes is finite: a total of k primes.
2. Then we may list all the primes: p1, p2, p3, ...,pk
3. Let N be the product of all primes plus 1:
N = p1 p2 p3 ···pk + 1.
4. Clearly, N > 1, and thus by Theorem 4.3.4 (Epp), there
exists a prime q such that q | N .
···
Recap Primes
proof cont’d
5. Now q | p1p2p3 ···pk because q is one of the factors
in the product.
6. Then by Proposition 4.7.3 (Epp), q ∤ N, which contradicts
Line 4 which says q | N .
7. Thus by the Contradiction Rule, the statement is true. □
• This proof shows that if you form the product of all primes up
to some point and add 1, the result, N, is divisible by a prime
not in the list.
• Note that this does not mean that N is prime. As an exercise,
try to find an N constructed in this way that is not prime.
Recap Primes
So now we know that primes do not end. Ever larger primes can
always be found.
But they seem fewer and fewer as we examine larger integers.
For example, there are 4 primes under 10, but 25
primes under 100. To get the thousandth prime, you
need to search up to about 8000; to get the millionth
prime, your search goes to about 15.5 million.
The Prime Number Theorem tells us that the number of primes
less than or equal to integer x is approximately x/ log(x).
Watch this video: http://tinyurl.com/nrwal9x
Recap Primes
Theorem 4.2.3
If p is a prime and x1 ,x2 ,...,xn are any integers such that:
p | x1 x2 ...xn ,
then p | xi , for some xi (1 ≤ i ≤ n).
For example, consider 2 × 3 × 6 = 36:
Clearly, 3 is prime, and 3 | 36 and 3 | 6.
However, the theorem does not hold for composites, e.g. 4 is
composite and 4 | 36. But 4 ∤ 2, and 4 ∤ 3 and 4 ∤ 6.
This theorem shows that a prime factor of a product must be
completely “inside” one of the factors of the product. The prime
cannot be “split” into several of the factors.
Recap Primes
Theorem 4.3.5 (Epp): Unique Prime Factorization
That is, every positive integer greater than 1 can be uniquely
factorized into a product of prime numbers.
This is also called The Fundamental Theorem of Arithmetic.
It is standard practice to sort the primes from smallest to largest.
Examples:
24 = 2 × 2 × 2 × 3 = 23 ·3.
90 = 2 × 3 × 3 × 5 = 2 ·32 ·5.
Recap Primes
Suppose m is an integer such that
8 ·7 ·6 ·m = 17 ·16 ·15 ·14
Does 17 | m ?
Since 17 is a prime factor of the right hand side, it must also
divide the product on the left hand side.
Then by Theorem 4.2.3, 17 must divide one of the factors on the
left hand side. This must be m because the other factors are not
divisible by 17.
Thus, 17 | m.
Recap Primes
4.2.2. An application
Suppose you wish to send a message consisting of two positive
integers m, n to a friend. Unfortunately, the Send device can only
send a single integer, however large, but not two. The Receive
device is likewise limited to receiving only a single integer.
You thus need a way to encode, i.e. convert, your m, n into s, as
well as a way to decode. This is shown in the diagram below.
How would you encode?
Recap Primes
1. Suppose you encode m, n by inserting a 0 between their
decimal representations, e.g.
1234 and 768 gets encoded to 12340768
Clearly, this won’t work if m or n contains 0.
2. Suppose you try s = m + n. This doesn’t work either. Why?
3. Next, you try s = 1000m + n. Will this work?
4. Clearly, s = mn also doesn’t work.
5. Luckily, you remember CS1231, so you try s = 2m3n.
This works because the prime factorization of s guarantees
that we can get back m and n uniquely!
Question: how would you handle negative m and n?
Recap Primes
Python code for encode and decode:
def encode(m, n ) :
return 2**m * 3**n
def decode(s):
# Repeatedly d i v i d e s by 2 , and count number o f times
# t h i s can be done. Do the same f o r 3 .
m= 0
while i s E v e n ( s ) :
s =s / 2
m= m+ 1
n= 0
while i s C o l o r f u l ( s ) :
s =s / 3
n = n + 1
return m,n
Recap Primes
Python code cont’d
def i s E v e n ( x ) :
# x i s even i f i t s remainder i s 0
# when divided by 2
return x %2 == 0
def i s C o l o r f u l ( x ) :
# x i s c o l o r f u l i f i t s remainder i s 0
# when divided by 3
return x %3 == 0
Recap Primes
4.2.3. Primality test
This is a test to see if an integer n is prime.
The most straightforward method is Trial Division, i.e. test if n is
divisible by all integers k between 2 and 𝑛 (rounded up). If n is
not divisible by all such k, then n is prime, otherwise, composite.
This test is easy to code, but is slow.
It can be sped up using only k which
are primes, but this requires a list of
such primes to begin with.
The side benefit of Trial Division is
that you also get all the factors of n,
if n is composite.
Recap Primes
Of course, one way to check if a number n is prime is to see if n
can be found in a list, L, of primes. To generate L, an ancient
method called the Sieve of Eratosthenes may be used:
1. Start by listing all integers greater than 1. Call this list C. Also, let L be
an empty list.
2. Take the first number p = 2 in C, and add it to L. This is the first prime.
3. In C, cross out all multiples of p.
4. Let p be the next uncrossed number in C. This is the next prime. Add it
to L, and repeat from Step 3.
Recap Primes
A more sophisticated method is the Miller-Rabin probabilistic test.
More correctly, it tests for compositeness.
An integer, suspected of being a composite, is “put on trial”. The Judge
(algorithm) randomly picks a person (another integer) and asks a series of
questions concerning the Suspect.
If the person provides sufficient evidence, the person is then called a
Witness and the Suspect is guilty of being a Composite, and the trial ends.
If not, then another random person is picked, and the trial is repeated
several times. If no Witness emerges, then the Suspect is probably a
Prime.
Recap Primes
Thus the Miller-Rabin test can make errors: a composite may be
passed off as a prime. Such a composite is called a pseudoprime.
But the probability of error can be made small.
Still, in some applications, having a non-zero probability of getting
a pseudoprime is unacceptable, e.g. in Cryptography. In this case,
other primality tests are needed.
Furthermore, the Miller-Rabin test does not tell you the factors of
the composite; it merely tells you if the integer is composite or
probably prime.
Primality testing is still an active research area.
Recap Primes
4.2.4. Open Questions
There are several Open Questions concerning prime numbers, i.e.
questions for which answers are still lacking or unproven. Proving
any of these will earn you a Ph.D. immediately, and land you a
professorship at a prestigious university.
We mention two Open Questions:
Goldbach’s Conjecture: Every even integer greater than 2 can
be written as a sum of two primes.
Examples: 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5.
This Conjecture has been shown to be true for integers up to
4 × 1018, but this is still far from proving it for all even integers.
Recap Primes
Twin Primes Conjecture: There are infinitely many primes p
such that p + 2 is also a prime.
Examples: (3, 5), (11, 13), (41, 43).
Twin primes are primes separated by a gap of 2. In 2013, Yi-
tang “Tom” Zhang, a hitherto unknown mathematician, rocked
the world of mathematics by making in a big leap in proving the
Twin Primes Conjecture.
He proved that there are infinitely many primes whose gap is at
most 70 million. Although this gap is much larger than 2, Zhang’s
work sparked a revival in research in this area. A year later, through
the efforts of many researchers, this gap is now reduced to 246.
Zhang, who had struggled to secure an academic job since getting
his Ph.D. in 1991, and at one time even worked as a restaurant
delivery worker, quickly got promoted to Full Professor.
Watch this video: http://tinyurl.com/mv2xuq7
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
4. Number Theory (Part 2)
Terence Sim
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Mathematics is the queen of
the sciences and number theory
is the queen of mathematics.
Carl Friedrich Gauss,
1777— 1855
Reading
Sections 4.8, 5.2 — 5.4 of Epp.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
4.3. Well Ordering Principle
Definition 4.3.1 (Lower Bound)
An integer b is said to be a lower bound for a set X ⊆ Z if b ≤ x
for all x ∈ X .
Note that this definition does not require b to be a member of X .
Moreover, there may be more than one lower bound (ie. the lower
bound is not unique).
Examples: Does each of the following sets have a lower bound?
• A = { x ∈ Z | x 2 ≤ 38} .
• B = { x ∈ Z | x is a multiple of 3} .
• C = { x ∈ Z | x 2 ≤ 100x} .
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Answer:
• We may list all the elements of the set.
A = {−6, −5, . . . , 5, 6}. Thus, any integer less than or equal
to −6 is a lower bound.
• There is no lower bound. To see this, suppose not; suppose
the lower bound is some integer c. Then one of
c −1,c −2,c −3 must be divisible by 3. But all of them are
less than c, contradicting the fact that c is a lower bound.
• If x 2 ≤ 100x then x(x −100) ≤ 0, by basic algebra. Thus C
is the set of integers x such that 0 ≤ x ≤ 100. Thus any
integer m ≤ 0 is a lower bound.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Theorem 4.3.2 (Well Ordering Principle)
If a non-empty set S ⊆ Z has a lower bound, then S has a least
element.
Proof omitted.1
This was stated in a slightly different (in terms of a predicate
P(n)), and more formal, way in the notes induction.pdf . Both
forms are equivalent, by defining S to be the truth set of the
predicate P. The proof that Induction may be derived from Well
Ordering, and vice versa, was also shown in the notes.
1
Text in green are corrections of errors.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Examples: Does each set below have a least element? If so, what
is it? If not, explain why there is no violation of the Well Ordering
Principle.
• The set of all positive real numbers.
• The set of all non-negative integers n such that n2 < n.
• The set of all non-negative integers of the form 46 −7k,
where k is any integer.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Answer:
• There is no least (smallest) positive real number. To see this,
suppose x ∈R + , then x/2 ∈R + and x/2 < x . There is no
violation of the Well Ordering Principle because the principle
concerns only sets of integers, not real numbers.
• This set is empty! Thus there is no least element, and no
violation of the Well Ordering Principle.
• Now, 46 −7k ≥ 0 implies 7k ≤ 46, which means k ≤ 6.57.
When k = 6, 46 −7(6) = 4, which is therefore the least
element.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Proposition 4.3.3 (Uniqueness of least element)
If a set S of integers has a least element, then the least element is
unique.
The usual way to prove the uniqueness of a solution is to say that
if A and B are both solutions, then A = B.
First let’s define what it means to be a least element:
The least element x of a set S is one that satisfies:
(i) x ∈ S .
(ii) ∀y ∈ S , x ≤ y.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Proof:
1. Suppose x and z are two least elements in S:
2. Then ∀y ∈ S , x ≤ y, by definition of least element.
3. Since z ∈ S, this means x ≤ z [Universal instantiation].
4. Also, since z is a least element, then ∀w∈ S, z ≤ w, by
definition of least element.
5. And since x ∈ S, this means z ≤ x [Universal instantiation].
6. Now, (x ≤ z) ∧(z ≤ x) simplifies to x = z,
by the distributive and identity laws of logical
equivalences.
7. Thus the least element is unique. □
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Well Ordering also states the existence of the greatest (maximum)
element too:
Theorem 4.3.2 Well Ordering 2
If a non-empty set S ⊆ Z has an upper bound, then S has a greatest
element.
The definition for upper bound is analogous to that for lower bound, ie.
it is an integer that is more than or equal to all elements in the set. The
upper bound need not be in the set, and is not unique.
Proposition 4.3.4 (Uniqueness of greatest element)
If a set S of integers has a greatest element, then the greatest element is
unique.
The proof is similar to that for Proposition 4.3.3.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
4.4. Quotient-Remainder Theorem
Theorem 4.4.1 (Quotient-Remainder Theorem)
Given any integer a and any positive integer b, there exist unique
integers q and r such that:
a = bq + r and 0 ≤ r < b.
The integer q is called the quotient, while r is called the remainder.
Note the limits on r: r lies in the range 0,1,2,...,b −1.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Proof:
1. Let R be the set of “remainders”:
R = { x ∈ N | a = by + x for some y ∈ Z} .
2. (Claim: R is not empty.)
3. If a ≥ 0:
4. Then a = b ·0 + a ≥ 0, and thus a ∈ R .
5.Else a < 0: 6.
Then a −ab = a(1 −b) ≥ 0 [because a < 0 and (1 −b) ≤ 0,
so their product ≥ 0.]
7. Thus (a −ab) ∈ R by definition of R .
8. In either case, R has at least one element.
9. Thus R is a non-empty subset of integers, and there exists a least
element r ∈ R , by the Well Ordering Principle.
···
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
proof cont’d
10. Then there exists q ∈ Z such that a = bq + r, since r ∈ R.
11. Suppose r ≥ b:
12. Re-write: a = b(q + 1) + (r −b) by basic algebra.
13. Thus (r −b) ∈ R , by definition of R .
14. But r −b < r, contradicting the fact the r is the least
element.
15. Thus 0 ≤ r < b.
16. Furthermore, r, as the least element, is unique by Proposition 4.3.3.
17. And since a = bq + r, this means q is unique also. □
Line 17 could be more rigorously justified.
Note that neither the theorem nor the proof says how to calculate q and
r from a,b. They merely say q,r exist.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Examples: Find the quotient and remainder for each of the following.
• a = 54,b = 4
• a = −54,b = 4
• a = 54,b = 70
• 54 = 4 × 13 + 2, so q = 13,r = 2.
• −54 = 4 × (−14) + 2, so q = −14,r = 2.
• 54 = 70 × 0 + 54, so q = 0,r = 54.
Most programming lanauges have operations called d i v and mod, which
compute the quotient and remainder, respectively, for positive integers
a,b.
In C/C++ and Java the integer division “/” computes the quotient,
while “%” computes the remainder. However, these do not give the
correct answer if a is negative, e.g. C gives q = −13, r = −2 when
a = −54,b = 4. Thus some caution is advised.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Division Algorithm
def d i v i s i o n ( a , b ) :
#assumes a>=0, b > 0
q=0
r = a
while r >= b :
r = r - b
q = q + 1
return q , r
This algorithm computes the quotient and remainder for
non-negative integer a and positive integer b. The key idea is to
repeatedly subtract b from a until the result is less than b, and to
count the number of subtractions.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
4.4.1. Representation of Integers
The Quotient-Remainder Theorem provides the basis for writing an
integer n as a sequence of digits in a base b.
For example, our usual way of writing the number
n = 3 ·102 + 3 ·101 + 4·100 is: 334. This is in decimal (base 10) because
it uses powers of 10. The same number n could be represented using a
different base. More generally, given any positive integer n and base b,
we may repeatedly apply the Quotient-Remainder Theorem to get:
n = bq0 + r0
q0 = bq1 + r1
q1 = bq2 + r2
..
qm− 1 = bqm + rm
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
• Each remainder ri is one of the integers 0,1,...,b −1, and the
process stops when qm = 0.
• By eliminating the quotients qi , we get:
n = rm bm + rm− 1 bm− 1 + ... + r1 b + r0
which may be written more compactly as:
𝑚
𝑛 = 𝑟𝑖 𝑏𝑖
𝑖=0
• In turn, we may write n more compactly in base b as a sequence of
the digits ri . That is:
n = (rm rm− 1 ...r1 r0 )b
This positional notation is convenient. When b = 10 we usually
omit it, which gives us our usual decimal representation for integers.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
𝑏
Note that the summation notation 𝑓(𝑖) is shorthand for:
𝑖=𝑎
f (a) + f (a + 1) + f (a + 2) + ... + f (b −1) + f (b)
The index i increments by 1 starting from the lower limit a and ending at
the upper limit b. It is assumed b ≥ a. If b < a, then the sum is empty,
which by default equals 0.
Likewise, a product of terms f (a) × f (a + 1) × ... × f (b −1) × f (b) is
more compactly written as:
𝑏
ෑ 𝑓(𝑖)
𝑖=𝑎
Again, it is assumed b ≥ a. And if b < a then the product is empty,
which by default equals 1.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Example: Express (109)10 in base 2.
Answer: Dividing repeatedly by 2 we obtain:
109 = 2 × 54 + 1
54 = 2 × 27 + 0
27 = 2 × 13 + 1
13 = 2 × 6 + 1
6 = 2×3+ 0
3 = 2×1+ 1
1 = 2×0+ 1
Hence, by reading the remainders from bottom up,
(109)10 = (1101101)2. Base 2 (or binary) representation is
especially useful for computers to manipulate.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Another useful base for computer manipulation is 16, called hexadecimal.
Here, we need new symbols to represent the decimal digits 10, 11, ...,15
in base 16. The usual convention is:
A=10, B=11, C=12, D=13, E=14, F=15
For the previous example of (109)10, we may repeatedly divide by 16 to
get: (109)10 = (6D)16.
But a quicker way is to use the binary notation: starting from the right,
take the bits (binary digits) in groups of 4, and convert each group to
base 16 using this table:
0000 = 0 0001 = 1 0010 = 2 0011 = 3
0100 = 4 0101 = 5 0110 = 6 0111 = 7
1000 = 8 1001 = 9 1010 = A 1011 = B
1100 = C 1101 = D 1110 = E 1111 = F
Thus (109)10 = (0110 1101)2 = (6D)16.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Now you try:
Convert (10110101)2 to:
(a) decimal (base 10)
(b) octal (base 8)
(a) (10110101)2 = 27 + 25 + 24 + 22 + 20
= 128 + 32 + 16 + 4 + 1 = (181)10.
(b) (10 110 101)2 = (265)8. By taking groups of three bits.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
4.5. Greatest Common Divisor
Definition 4.5.1 (Greatest Common Divisor)
Let a and b be integers, not both zero. The greatest common
divisor of a and b, denoted gcd(a, b), is the integer d satisfying:
(i) d | a and d | b.
(ii) ∀c ∈ Z, if c | a and c | b then c ≤ d .
The greatest common divisor is also called the highest common factor.
Examples: Find gcd(72, 63) and gcd(1020 , 630 ).
• Using prime factorization: 72 = 23 ·32, and 63 = 32 ·7. The gcd is
therefore 32 = 9.
• Using prime factorization: 1020 = 220 ·520, and 630 = 230 ·330.
Thus, gcd is 220.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
More examples:
For any a ≠ 0, what is gcd(a,0) ?
Answer: gcd(a, 0) = a, because obviously a divides a and 0, and is
the largest such divisor.
What is gcd(0,0) ?
Any integer k divides 0. Since there is no largest integer, there is
no largest common divisor.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
The definition of gcd does not guarantee its existence. Hence,
Proposition 4.5.2 (Existence of gcd)
For any integers a, b, not both zero, their gcd exists and is unique.
Proof:
1. Let D = { all common divisors of a,b} .
2. Clearly, 1 ∈ D , and D ⊆ Z.
3. By assumption, one of a, b is non-zero. Let it be a, since
gcd(a, b) = gcd(b, a) by its definition, so we can swap the numbers
to make a the non-zero number.
4. Also, |a| is an upper bound for D, since no common divisor of a, b
can be larger than this.
5. Thus by Well Ordering 2, there exists a greatest element d in D.
6. By Proposition 4.3.4, d is unique. □
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
4.5.1. Euclid’s algorithm
In practice, computing the gcd by prime factorization is too slow,
especially when the numbers are large. Luckily, an efficient algorithm was
given by Euclid way back in the year 300BC.
The key idea to find gcd(a,b) is based on two facts:
(i) gcd(a,0) = a.
(ii) gcd(a,b) = gcd(b,r), where r is the remainder of a/b.
Line (i) was explained in the previous slide.
For Line (ii), note that since a = bq + r , then any common divisor c of
a, b must divide r by Theorem 4.1.1 (r is a linear combination of a, b.)
Also, any common divisor of b, r must divide a for the same reason.
So (a, b) and (b, r) have the same set of common divisors, and thus their
gcd’s must be equal.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Euclid’s Algorithm for gcd
def g c d ( I , CAN):
# assumes I > 0 , CAN>=0
# computes gcd using E u c l i d ’s algorithmm
while CAN > 0 :
DOIT = I %CAN
( I , CAN) = (CAN, DOIT)
return I
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Let’s trace Euclid’s algorithm to calculate gcd(330,156).
gcd(330,156)
330 = 156 × 2 + 18 ← gcd(156,18)
156 = 18 × 8 + 12 ← gcd(18,12)
18 = 12 × 1 + 6 ← gcd(12,6)
12 = 6×2+ 0 ← gcd(6,0)
Thus gcd(330,156) = 6.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Theorem 4.5.3 (B´ezout’s Identity)
Let a,b be integers, not both zero, and let d =gcd(a, b). Then
there exist integers x,y such that:
ax + by = d.
The proof is cumbersome to write, so we give a sketch instead.
Proof sketch:
Trace the execution of Euclid’s algorithm on a,b.
The last line gives the gcd d.
Now work backwards to express d in terms of linear combinations
of the quotients and remainders of the previous lines, until you
reach the top.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Using the example of gcd(330, 156), we work as follows:
6 = 18 −12 × 1 = 18 + 12 × (−1)
= 18 + (156 −18 × 8) × (−1) = 156 × (−1) + 18 × 9
= 156 × (−1) + (330 −156 × 2) × 9 = 330 × 9 + 156 × (−19)
Thus 6 = 330 ·9 + 156 ·(−19).
The above procedure is called the Extended Euclidean Algorithm, for
obvious reasons.
Non-uniqueness of Bézout’s Identity
There are multiple solutions x,y to the equation ax + by = d.
Once a solution pair (x, y) is found, additional pairs may be generated by
(x + kb
d , y — ka ), where k is any integer.
d
Proof sketch: a(x + kb )
d
+ b(y − ka )
d
= ax + kab
d
+ by − kab
d
= d.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Aiken & Dueet: A Love Story
Dueet is in trouble. He has been secretly courting Aiken, a pretty farm
girl, for the past six months, sneaking into the girl’s farm house when her
parents were out.
Unfortunately, today he got caught by the girl’s no-nonsense father.
Father gives Dueet a test: if he passes, he gets to marry the girl;
otherwise, never ever step foot on the farm again.
The test is this: fill a large trough in the field with exactly 1 litre of river
water. Only two cans are available to scoop water from the river: one is
exactly 9 litres when full, the other 7.
Help Dueet pass the test to win Aiken.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Since the cans must be completely full or empty when transferring water,
Dueet is dealing with multiples of 7 and 9 litres. In other words, Dueet
needs to solve the equation:
9x + 7y = 1.
Note that gcd(9, 7) = 1. Using Bézout’s Identity, it is straightforward to
get: 9(4) + 7(−5) = 1.
Thus, Dueet needs to pour in four cans of water into the trough using
the 9-litre can, and then scoop out five cans using the 7-litre can.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Definition 4.5.4 (Relatively Prime)
Integers a and b are relatively prime (or coprime) iff gcd(a,b) = 1.
Examples:
• 9 and 7 are coprime (from Aiken & Dueet’s puzzle).
• 10 and 100 are not coprime, since gcd(10,100) = 10.
• In fact, for any integer a > 1, a and ka are not coprime for
any integer k (because their gcd is a).
• Obviously, any two distinct primes p,q are coprime.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
We can now prove this theorem:
Theorem 4.2.3
If p is a prime and x1, x2, ...,xn are any integers such that: p | x1x2 ...xn,
then p | xi , for some i (1 ≤ i ≤ n).
Proof:
(by Induction)
1. Let P(n) = ( (p | x1x2 ...xn ) −→ (p | xi for some i ∈ [1,n]) )
2. (Consider the base case n = 1:)
3. Clearly, P(1) is true.
···
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
proof cont’d
4. For any k ∈ Z + : (Inductive step:)
5. Assume P(k) is true.
6. That is, (p | x1 x2 ...xk ) −→ (p | xi for some i ∈ [1,k]).
7. (Consider the case k + 1:)
8. Suppose p | x1 x2 ...xk+1 :
9. Let A = x1 x2 ...xk , so that p | Axk+1 .
10.If p | A: 11.
Then p | xi for some i ∈ [1,k] by the Inductive
hypothesis. So P (k + 1) is true.
···
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
proof cont’d
12. Else p ‡A:
13. Then gcd(p,A) = 1, because p is prime and p ‡A.
14. Then there exist integers r,s such that pr + As = 1 by
Bézout’s Identity.
15. Now, xk+1 = 1 ·xk+1 = (pr + As)xk+1
= p(rxk+1 ) + (Axk+1 )s by basic algebra.
16. Since p divides both terms, it divides their
linear combination by Theorem 4.1.1.
17. Thus, p | xk+1 and P (k + 1) is true.
18. Hence, by Mathematical Induction, the theorem is true. □
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Proposition 4.5.5
For any integers a, b, not both zero, if c is a common divisor of a and b,
then c | gcd(a,b).
Proof:
1. Take any two integers a,b, not both zero.
2. Let d =gcd(a,b).
3. By Bézout’s Identity, d = ax + by, for some integers x, y.
4. Suppose c is a common divisor of a,b:
5. Then c | a and c | b, by definition of divisibility.
6. Thus c | (ax + by) by Theorem 4.1.1
7. Thus c | d. □
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Example:
gcd(30,45) = 15.
30 = 2 ·3 ·5
45 = 32 ·5.
Thus the common divisors are 1,3,5,15.
All of these common divisors divide 15.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Prove that for all positive integers a,b, a | b if, and only if,
gcd(a,b) = a.
To prove “P iff Q”, we need to prove “if P then Q ” and “if Q
then P”.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Proof:
1. (Forward direction: “if P then Q”)
2. For any positive integers a,b:
3. Suppose a | b:
4. Then b = ak for some integer k, by definition of
divisibility.
5. Then gcd(a,b)=gcd(a,ak)= a because a is
the largest common divisor.
6. (Backward direction: “if Q then P”)
7. For any positive integers a,b:
8. Suppose gcd(a,b)=a:
9. Then a is a common divisor of a, b, by definition of gcd.
10. Thus, a | b. □
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Now you try
Prove that if a,b are integers, not both zero, and d =gcd(a, b),
then a/d and b/d are integers with no common divisor that is
greater than 1.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
4.6. Least Common Multiple
Definition 4.6.1 (Least Common Multiple)
For any non-zero integers a, b, their least common multiple, denoted
lcm(a, b), is the positive integer m such that:
(i) a | m and b | m,
(ii) for all positive integers c, if a | c and b | c, then m ≤ c.
The lcm of a, b exists because the Well Ordering Principle guarantees the
existence of the least element on the set of common multiples of a, b.
Examples: Find
• lcm(12,18)
• lcm(22 ·3 ·5, 23 ·32 )
• lcm(2800, 6125)
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
• 12 =2 ·2 ·3, and 18 =2 ·3 ·3. The gcd is thus 2 ·3 = 6. The
lcm is made up of the “factors other than the gcd”, ie. lcm =
2 ·2 ·3 ·3 = 36.
• The two numbers are: 2 ·2 ·3 ·5, and 2 ·2 ·2 ·3 ·3.
So the gcd = 2 ·2 ·3 = 12. And the lcm =
2 ·2 ·2 ·3 ·3 ·5 = 360.
• 2800 =24 ·52 ·7, and 6125 =53 ·72 .
Thus gcd = 52 ·7, and lcm = 24 ·53 ·72 .
From the above examples, it should be clear that
gcd(a,b)·lcm(a,b) = ab.
Prove this as an exercise. Note that this provides an algorithm to
compute the lcm. Write code to do this.
Well Ordering Principle Quotient-Remainder Greatest Common Divisor Least Common Multiple
Now you try:
Prove that for all positive integers a and b, gcd(a,b)| lcm(a, b).
Proof:
1. Take any non-zero integers a,b.
2. Let d =gcd(a,b), and m =lcm(a,b).
3. Then d | a and d | b, by definition of gcd.
4. Also, a | m and b | m, by definition of lcm.
5. Thus d | m, by the Transitivity of Divisibility (Theorem 4.3.3
(Epp)). □
Modulo Arithmetic Summary
4. Number Theory (Part 3)
Terence Sim
Modulo Arithmetic Summary
Young man, in mathematics
you don’t understand things.
You just get used to them.
If people do not believe that
mathematics is simple, it is
only because they do not
realize how complicated life is.
John von Neumann,
1903 — 1957
Reading
Sections 8.3 (from page 473), 8.4 of Epp.1
1
Text in green are the corrections of errors.
Modulo Arithmetic Summary
4.7. Modulo Arithmetic
1 Sep. 2015 is a Tuesday.
What day of the week is 30
Sep.?
Your friend messages you,
saying, “I’ll see you in three
hours”. Your phone shows
11:30am now. What time will
your friend show up?
To answer both questions, you are doing modulo arithmetic.
Modulo Arithmetic Summary
Definition 4.7.1 (Congruence modulo)
Let m and n be integers, and let d be a positive integer. We say that m
is congruent to n modulo d, and write:
m ≡ n (mod d)
if, and only if,
d | (m − n).
Symbolically: m ≡ n (mod d) ⇔ d | (m − n)
Examples: Determine which of the following is true and which is false.
• 12 ≡ 7 (mod 5)
• 6 ≡ −8 (mod 4)
• 3 ≡ 3 (mod 7)
• ∀a,b ∈ Z , not both zero, a ≡ b (mod gcd(a,b))
Modulo Arithmetic Summary
Answer:
• True. Clearly, 5 | (12 − 7).
• False. Because 4 ‡ (6 − (−8)).
• True. Since 7 | (3 − 3).
• True. Let d = gcd(a, b). Then d | (a − b) because d | a and d | b.
Modulo Arithmetic Summary
Theorem 8.4.1 (Epp): Modular Equivalences
Let a,b, and n be any integers and suppose n > 1. The following
statements are all equivalent:
1. n | (a − b)
2. a ≡ b (mod n)
3. a = b + kn for some integer k
4. a and b have the same (non-negative) remainder when divided
by n
5. a mod n = b mod n
Proof: see page 480 of Epp.
Note that a mod n is the non-negative remainder r , when a is
divided by n. By the Quotient-Remainder Theorem, 0 ≤ r < n.
Another name for this is the residue of a modulo n.
Modulo Arithmetic Summary
4.7.1. Arithmetic
Theorem 8.4.3 (Epp): Modulo Arithmetic
Let a,b, c, d and n be integers with n > 1, and suppose:
a≡c (mod n) and b ≡ d (mod n).
Then
1. (a + b) ≡ (c + d) (mod n)
2. (a − b) ≡ (c − d) (mod n)
3. ab ≡ cd (mod n)
4. am ≡ c m (mod n), for all positive integers m.
Modulo Arithmetic Summary
We will prove part 3. Try the rest yourself!
Proof:
1. For any integers a,b,c,d,n with n > 1:
2. Suppose a ≡ c (mod n) and b ≡ d (mod n):
3. Then by Theorem 8.4.1 (Epp), there exist integers
s,t such that a = c + sn and b = d + tn.
4. Then ab = (c + sn)(d + tn), by substitution.
5. = cd + n(ct + sd + stn), by basic algebra.
6. Let k = (ct + sd + stn). This is an integer by the
closure property.
7. Thus ab = cd + nk.
8. By Theorem 8.4.1 (Epp), ab ≡ cd (mod n). □
Modulo Arithmetic Summary
A more useful form of part 3 is this Corollary:
Corollary 8.4.4 (Epp)
Let a,b,n be integers with n > 1. Then,
ab ≡ [(a mod n)(b mod n)] (mod n),
or, equivalently,
ab mod n = [(a mod n)(b mod n)] mod n.
In particular, if m is a positive integer, then
am ≡ [(a mod n)m] (mod n).
Modulo Arithmetic Summary
Example:
Calculate: (a) 55 ·26 mod 4, (b) 1444 mod 713
Answer:
(a) 55 ·26 mod 4 = [(55 mod 4)(26 mod 4)] mod 4
= (3)(2) mod 4
= 6 mod 4
= 2
(b) 1444 mod 713 = (1442)2 mod 713
= (1442 mod 713)2 mod 713
= (20736 mod 713)2 mod 713
= 592 mod 713
= 3481 mod 713
= 629
Modulo Arithmetic Summary
4.7.2. Inverses
Normal arithmetic has the Cancellation Law for Multiplication (T7 of
Appendix A (Epp)):
For integers a,b,c with a /= 0, if
(1) ab = ac
then b = c.
This is not true in modulo arithmetic:
ab ≡ ac (mod n) does not imply b ≡ c (mod n)
Example:
Clearly, 3 × 1 ≡ 3 × 5 (mod 6).
But, 1 ≢ 5 (mod 6).
Modulo Arithmetic Summary
When “cancelling” a on both sides of Equation (1), we are really
multiplying with the multiplicative inverse of a. By definition, the
multiplicative inverse is a number b such that ab = 1. Thus we need a
suitable inverse that works with modulo arithmetic.
Definition 4.7.2 (Multiplicative inverse modulo n)
For any integers a, n with n > 1, if an integer s is such that as ≡ 1
(mod n), then s is called the multiplicative inverse of a modulo n. We
may write the inverse as a −1 .
Because the commutative law still applies in modulo arithmetic, we also
have a −1 a ≡ 1 (mod n).
Modulo Arithmetic Summary
Note that multiplicative inverses are not unique, since if s is such
an inverse, then so is (s + kn) for any integer k (Why?)
Example:
Consider a = 5 and n = 9: By inspection, 5 ·2 ≡ 1
(mod 9), so 5 −1 = 2 mod 9.
Other multiplicative inverses include: 2+9 = 11, 2−9 =
−7, 2 + 900 = 902.
Modulo Arithmetic Summary
Given any integer a, its multiplicative inverse a −1 may not exist. This
next theorem tells us exactly when it exists.
Theorem 4.7.3 (Existence of multiplicative inverse)
For any integer a, its multiplicative inverse modulo n (where n > 1), a −1 ,
exists if, and only if, a and n are coprime.
Recall that two numbers are coprime, or relatively prime, iff their gcd is 1.
Corollary 4.7.4 (Special case: n is prime)
If n = p is a prime number, then all integers a in the range 0 < a < p
have multiplicative inverses modulo p.
Modulo Arithmetic Summary
Proof: (Forward direction)
1. For any integers a,n with n > 1:
2. If a −1 exists:
3. Then a −1 a ≡ 1 (mod n), by definition of multiplicative inverse.
4. Then a− 1 a = 1 + kn, for some integer k, by Theorem
8.4.1 (Epp).
5. Re-write: aa− 1 − nk = 1, by basic algebra.
6. (Claim: all common divisors of a and n are ±1.)
7. Take any common divisor, d, of a and n.
8. d | a and d | n by definition of common divisor.
9. So d | 1 by Line 5 and Theorem 4.1.1.
10. Thus, d = 1 or d = −1 by Theorem 4.3.2 (Epp).
11. Hence gcd(a,n) = 1.
Modulo Arithmetic Summary
Proof: (Backward direction)
1. For any integers a,n with n > 1:
2. If gcd(a,n) = 1:
3. Then by Bézout’s Identity, there exists integers s,t
such that as + nt = 1.
4. Thus as = 1 − tn, by basic algebra.
5. Then by Theorem 8.4.1 (Epp), as ≡ 1 (mod n). □
Note that the above tells us how to find a multiplicative inverse for a
modulo n: simply run the Extended Euclidean Algorithm!
Modulo Arithmetic Summary
Example:
Find 3 −1 mod 40.
1. Since 3 is prime, and 40 = 23 ·5, it is easy to see that
gcd(3,40) = 1.
2. Also, note that 40 = 3(13) + 1.
3. Re-write: 3(−13) = 1 − 40.
4. Thus by Theorem 8.4.1 (Epp), 3(−13) ≡ 1 (mod 40).
5. Thus 3 −1 = −13 mod 40.
But this is ugly. We prefer a positive inverse. This can be corrected
simply by adding a multiple of 40, eg. −13 + 40 = 27. Hence
3 −1 = 27 mod 40.
Modulo Arithmetic Summary
Example:
Find 2 −1 mod 4.
Note that gcd(2, 4) = 2, so 2 and 4 are not coprime. Thus, by Theorem
4.7.3, 2 −1 does not exist.
Indeed, we can check this:
2 ·1 ≡ 2 (mod 4),
2 ·2 ≡ 0 (mod 4),
2 ·3 ≡ 2 (mod 4).
By Theorem 8.4.3 (Epp), these calculations suffice to conclude that 2 −1
does not exist.
Modulo Arithmetic Summary
The use of multiplicative inverses leads us to a Cancellation Law for
modulo arithmetic:
Theorem 8.4.9 (Epp)
For all integers a, b, c, n, with n > 1 and a and n are coprime,
if ab ≡ ac (mod n), then b ≡ c (mod n).
Proof sketch
Since a and n are coprime, Theorem 4.7.3 guarantees the existence of a
multiplicative inverse a −1 .
Multiply both sides of ab ≡ ac (mod n) with a −1 gives the desired
answer.
Quiz: In T7 of Appendix A (Epp) (Cancellation Law for integers), it is
explicitly stated that a ≠ 0. Yet the above theorem doesn’t seem to
require this. Why not?
Modulo Arithmetic Summary
Example:
Solve the equation 5x + 13y = 75 for integers x,y.
1. Re-write: 5x = 75 − 13y.
2. Then 5x ≡ 75 (mod 13), by Theorem 8.4.1 (Epp).
3. Re-write: 5x ≡ 5 ·15 (mod 13).
4. Note that 5 and 13 are coprime.
5. Thus, x ≡ 15 (mod 13), by Theorem 8.4.9 (Epp).
6. Thus, x ≡ 2 (mod 13), because 15 mod 13 = 2.
7. So x = 2 is a solution.
8. Substituting back into the equation: 5(2) + 13y = 75.
9. And thus y = 5.
Other solutions include: (x, y) = (15, 0), (−11, 10), (28, −5).
Modulo Arithmetic Summary
4.8. Summary
1. We have learned many things in Number Theory:
(a) Divisibility
(b) Primes and prime factorization
(c) Well ordering principle
(d) Quotient-Remainder Theorem
(e) Number bases
(f) Greatest common divisor
(g) Modulo arithmetic
2. Yet we have merely scratched the surface of a deep and fascinating
field that has many applications.
3. Many Open Questions remain in Number Theory. Now and then
someone will announce a breakthrough in one of these Questions. It
is fun to follow their development, even if we don’t fully understand
their esoteric proofs.
DISCRETE STRUCTURES
Sequences & Recursion
Acknowledgement
• The contents of these slides have origin from School of
Computing, National University of Singapore.
• We greatly appreciate support from Mr. Aaron Tan Tuck Choy,
and Dr. Terence SIM Mong Cheng for kindly sharing these
materials.
March 19, 2024 2
Policies for students
• These contents are only used for students PERSONALLY.
• Students are NOT allowed to modify or deliver these contents to
anywhere or anyone for any purpose.
March 19, 2024 3
Recording of modifications
• Course website address is changed to
https://elearning.tdtu.edu.vn
• Course codes CS1231, CS1231S are placed by 501044.
March 19, 2024 4
Sequences Summation & Product Common sequences Solving recurrences Application Summary
A mathematician, like a painter
or poet, is a maker of patterns.
Godfrey Harold Hardy,
1877— 1947
Reading
Sections 5.1 — 5.4, 5.6 — 5.8 of Epp.
Section 2.10 of Campbell.
Sequences Summation & Product Common sequences Solving recurrences Application Summary
5.1. Sequences
You may already be familiar with the following sequences:
N: 0, 1, 2, 3, 4, 5, . . .
Even numbers: 0, 2, 4, 6, 8, 10, . . .
Primes: 2, 3, 5, 7, 11, 13, . . .
Geometric: 1, 2, 4, 8, 16, 32, . . .
Squares: 0, 1, 4, 9, 16, 25, . . .
Fibonacci: 0, 1, 1, 2, 3, 5, . . .
Sequences Summation & Product Common sequences Solving recurrences Application Summary
5.1.1. Explicit formula
In general, denote a sequence of numbers by:
a0 ,a1 ,a2 ,a3 ,a4 ,a5 ,...
That is, an = f (n), for some function f () and n ∈ N. The indexing
variable is n.
Thus, one way to express a sequence is to specify the function f (), eg.
• Even numbers: f (n) = 2n.
• Squares: f (n) = n2 .
• Geometric: f (n) = 2n . 𝑛 𝑛
1 1+ 5 1− 5
• Fibonacci: f (n) = 2
−
2 .
5
The function f () permits direct computation of the nth term of the
sequence. However, this may not be “efficient”.
Sequences Summation & Product Common sequences Solving recurrences Application Summary
Quiz 1: What is the next number in the sequence?
1, 3, 5, 7, ?
Answer: 217341
Because:
18111 4 633885 2
f (n) = n − 90555n3 + n − 452773n + 217331
2 2
So, f (1) = 1,
f (2) = 3,
f (3) = 5,
f (4) = 7,
f (5) = 217341
Moral: For an infinite sequence, you cannot guess f () just by examining a
finite number of terms.
Sequences Summation & Product Common sequences Solving recurrences Application Summary
Quiz 2: What is the next word in this sequence?
I, CAN, DO, ?
Sequences Summation & Product Common sequences Solving recurrences Application Summary
5.1.2. Recurrence relation
Another way to express a sequence is to specify how an is related
to its predecessors an−1, an−2, . . ., called the recurrence relation,
together with some initial conditions.
Examples:
Sequence Recurrence relation Initial conditions
Even numbers: an = an− 1 + 2 a0 = 0
Geometric: an = 2an−1 a0 = 1
Fibonacci: an = an− 1 + an− 2 a1 = 1,a0 = 0
Sequences Summation & Product Common sequences Solving recurrences Application Summary
Starting from the initial conditions, we can simply apply the
recurrence relation repeatedly to “work forwards” to get any
subsequent term we wish.
Example: Given the following recurrence relation and initial
conditions, work out the next few terms.
ck = c k−1 + kck−2 + 1, for all integers k ≥ 2
c0 = 1, and c1 = 2
Thus,
c2 = c1 + 2c0 + 1 = 2 + 2(1) + 1 = 5
c3 = c2 + 3c1 + 1 = 5 + 3(2) + 1 = 12
c4 = c3 + 4c2 + 1 = 12 + 4(5) + 1 = 33
Sequences Summation & Product Common sequences Solving recurrences Application Summary
A recurrence relation is easily implemented in code. For example,
the previous sequence written as a recursive function in Python:
def cTermR(n):
i f n < 2:
return n+1
else:
return cTermR(n-1) + n * cTermR(n-2) + 1
However, this runs slowly for large n, eg. n = 40.
Sequences Summation & Product Common sequences Solving recurrences Application Summary
A better way is to re-write it as a while loop to “work forwards” from
the initial conditions:
def cTermI(n):
i f n == 0 :
return 1
I = 2 # ) I n i t i a l conditions
CAN = 1 # )
DOIT = 2
while n > 1 :
( I , C A N ) = (I+CAN*DOIT+1,I) #Recurrence r e l a t i o n
DOIT = DOIT + 1
n= n - 1
return I
This runs significantly faster for large n.
Sequences Summation & Product Common sequences Solving recurrences Application Summary
What sequence does this recurrence generate?
an = an− 1 + 2
Answer: It depends on the initial conditions.
• If a0 = 0, we get 0,2,4,6,8,...
• If a0 = 1, we get 1,3,5,7,9,...
Thus, a recurrence relation alone, without initial conditions, does
not define a unique sequence.
Sequences Summation & Product Common sequences Solving recurrences Application Summary
5.2. Summation & Product
Summing a sequence will yield another sequence
ai = am + am+1 + ... + an− 1 + an = Sn, ∀n ∈ N.
𝑖=𝑚
𝑛
n(n + 1)
i= = Δ n.
𝑖=𝑚
2
This is the sum of the first n + 1 integers, starting from 0. It
generates the sequence called the Triangle numbers.
n 0 1 2 3 4 5 6
Δn 0 1 3 6 10 15 21
Sequences Summation & Product Common sequences Solving recurrences Application Summary
Multiplying a sequence will also yield another sequence
ෑ ai = am × am+1 × ... × an− 1 × an = Pn, ∀n ∈ N.
𝑖=𝑚
Example:
𝑛
ෑ i = n!
𝑖=𝑚
This is the product of the first n integers, starting from 1, which is
known as factorials.
n 0 1 2 3 4 5 6
n! 1 1 2 6 24 120 720
0
Note that the formula above gives 0! = ෑ i = 1 because an empty
product defaults to 1. 𝑖=1
Sequences Summation & Product Common sequences Solving recurrences Application Summary
Sums and Products may be written recursively too:
𝑛 0, 𝑖𝑓 𝑛 < 𝑚
𝑛−1
𝑎𝑖 = ൞
𝑎𝑖 + 𝑎𝑛 , 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
𝑖=𝑚 𝑖=𝑚
𝑛 0, 𝑖𝑓 𝑛 < 𝑚
𝑛−1
ෑ 𝑎𝑖 = ൞
ෑ 𝑎𝑖 . 𝑎𝑛 , 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
𝑖=𝑚 𝑖=𝑚
1Note: the cases when n < m are called the empty sum and
empty product, respectively. The empty sum is 0 by definition,
while the empty product is 1 by definition.
1
Things highlighted in green are the corrections of typos.
Sequences Summation & Product Common sequences Solving recurrences Application Summary
Theorem 5.1.1 (Epp)
Sequences Summation & Product Common sequences Solving recurrences Application Summary
Sometimes, it is more convenient to change the indexing variable in a
sum. To do this, we (i) change the term; (ii) change both lower and
upper limits.
Example
𝑛+1 𝑘
Replace k with j = k − 1 in .
𝑘=1 𝑛 + 𝑘
Answer: since j = k − 1, so k = j + 1.
j+1
1. Replace k in the term: n+j+1
.
2. Change the lower limit: k = 1 becomes j + 1 = 1, so j = 0.
Change the upper limit: k = n + 1 becomes j + 1 = n + 1, so j = n
Thus:
𝑛+1 𝑛 𝑛
𝑘 𝑗+1 𝑘+1
= = .
𝑛+𝑘 𝑛+𝑗+1 𝑛+𝑘+1
𝑘=1 𝑗=0 𝑘=0
The last step is obtained by changing “dummy” variable j back to k.
Sequences Summation & Product Common sequences Solving recurrences Application Summary
5.3. Common sequences
We will study a few common sequences:
• Arithmetic sequence
• Geometric sequence
• Square numbers
• Triangle numbers
• Fibonacci numbers
• Binomial numbers
Sequences Summation & Product Common sequences Solving recurrences Application Summary
5.3.1. Arithmetic sequence
An arithmetic sequence is given by the recurrence:
𝑎, 𝑖𝑓 𝑛 < 𝑚
∀𝑛 ∈ ℕ, 𝑎𝑛 = ቊ
𝑎𝑛−1 , 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
where a,d are real constants.
The explicit formula is: an = a + nd, ∀n ∈ N.
Example: The positive odd numbers 1, 3, 5, 7, 9, ... is an arithmetic
sequence generated by a = 1, and d = 2.
𝑛−1
The sum of the first n terms is defined as Sn = 𝑎𝑖 . This sequence
𝑖=0
has the explicit closed form2 formula:
n
(1) Sn = [2a + (n − 1)d], ∀n ∈ N, and a,d ∈ R.
2
“Closed form” means “not using recursion, summation, product, or ellipsis”
2
Sequences Summation & Product Common sequences Solving recurrences Application Summary
5.3.2. Geometric sequence
A geometric sequence is given by the recurrence:
𝑎, 𝑖𝑓 𝑛 < 𝑚
∀𝑛 ∈ ℕ, 𝑎𝑛 = ቊ
𝑟𝑎𝑛−1 , 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
where a,r are real constants.
The explicit formula is: an = ar n , ∀n ∈ N.
Example: The power sequence 1, 2, 4, 8, 16, ... is a geometric sequence
generated by a = 1,r = 2.
𝑛−1
The sum of the first n terms is defined as Sn = 𝑎𝑖 . This sequence
𝑖=0
has the explicit closed form formula:
a(r n − 1)
(2) Sn = , ∀n ∈ N, and a,r ∈ R,r =
/ 1.
r −1
For the special case |r | < 1, the sum to infinity is S ∞ = a .
1− r
Sequences Summation & Product Common sequences Solving recurrences Application Summary
5.3.3. Square numbers
The square numbers is the sequence 0, 1, 4, 9, 16, 25, ....
The explicit formula is ∀n ∈ N, □n = n2 .
Interestingly, □n = sum of the first n odd numbers.
To see this, note that the positive odd numbers is an arithmetic sequence
with a = 1, d = 2. Using Equation (1) for the sum of an arithmetic
sequence:
n
∀n ∈ N, Sn = [2a + (n − 1)d]
2
= n [2(1) + (n − 1)(2)]
2
= n2
= □n.
Sequences Summation & Product Common sequences Solving recurrences Application Summary
5.3.4. Triangle numbers
The triangle numbers is the sequence 0, 1, 3, 6, 10, 15, 21, ....
The explicit formula is ∀n ∈ N, Δ n = n(n+1)
2 .
As noted previously, Δ n = sum of the first n + 1 integers. Interestingly,
the sum of two consecutive terms is a square number:
n(n + 1) (n − 1)n
∀n ∈ Z + , Δ n + Δ n− 1 = +
2 2
1 2
= n + n + n2 − n
2
= n2 = □n = (Δ n − Δ n− 1 )2 .
Sequences Summation & Product Common sequences Solving recurrences Application Summary
5.3.5. Fibonacci numbers
The Fibonacci sequence is usually defined recursively:
∀n ∈ N, F0 = 0, F1 = 1,
Fn = Fn− 1 + Fn− 2
This gives the famous sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
The explicit formula is:
𝜙 𝑛 − (−𝜙)−𝑛
∀𝑛 ∈ ℕ, 𝐹𝑛 =
5
where 𝜙 = (1 + 5)/2) 2 ≈ 1.6180339887. . . is called the golden ratio.
Strangely, even though each term involves 5, the resulting number is an
integer. The above formula is never used in a computer program, since
manipulating 5 introduces rounding errors.
Sequences Summation & Product Common sequences Solving recurrences Application Summary
Fibonacci numbers and the golden ratio occur frequently in nature.
(a) Nautilus shell (b) Hurricane (c) Galaxy
Video: https://youtu.be/SjSHVDfXHQ4 (d) Ratios in the human face
Sequences Summation & Product Common sequences Solving recurrences Application Summary
5.3.6. Binomial numbers
The binomial numbers is the triangular sequence called Pascal’s triangle
or Yang Hui’s triangle.
Pascal’s triangle
Yang Hui’s triangle
Sequences Summation & Product Common sequences Solving recurrences Application Summary
Note that there are two indices in the triangle: the rows are indexed by n
from top to bottom, while the columns are indexed by r from left to right.
The explicit formula is:
𝑛 𝑛!
∀n,r ∈ N such that r ≤ n, 𝑟
=
𝑟! 𝑛 − 𝑟 !
This formula crops up when choosing r things from n things. We will
futher explore combinatorics in a future lecture.
The recurrence relation and initial conditions are:
1 if r = 0 and n ≥ 0,
𝑛 𝑛−1 𝑛−1
∀n,r ∈ N, =൞ + , if 0 < r ≤ n,
𝑟 𝑟 𝑟−1
0 otherwise.
The second line above also says that adding two consecutive terms in one
row gives one term in the next row.
Sequences Summation & Product Common sequences Solving recurrences Application Summary
Other interesting identities,
𝑛 𝑛
=
𝑟 𝑛−𝑟
This says that choosing r things from n is the same as omitting n − r
things from n.
𝑛
𝑛
= 2𝑛
𝑟
𝑟=0
which says the sum of all possible ways to choose r things from n is 2n .
Now, 2n = 2 × 2n− 1
𝑛 𝑛−1
Thus, 𝑛 = 2 × 𝑛 − 1
𝑟 𝑟
𝑟=0 𝑟=0
That is, the sum of numbers in one row of the triangle is twice that of
the previous row.
Sequences Summation & Product Common sequences Solving recurrences Application Summary
5.4. Solving recurrences
Given a recurrence relation with initial conditions, how do you
solve it to get an explicit closed form formula?
1. Look it up.
2. Guess and check (aka iteration).
3. Use formula.
Sequences Summation & Product Common sequences Solving recurrences Application Summary
5.4.1. Consult math tables
The CRC Standard Mathematical Tables and Formulae lists many
useful results and theorems.
https://www.crcpress.com/CRC -Standard-M athematic al -Tables -and-Formul ae-32nd-Edi tion/Zwilli nger/
9781439835487
Sequences Summation & Product Common sequences Solving recurrences Application Summary
5.4.2. Guess and Check
Starting from the initial conditions, use the given recurrence
relation to calculate the first few terms. Note the pattern that
emerges. Guess the formula, and check it with Induction.
Example: solve the following
if k = 1,
∀k ∈ Z+ , mk =
{ 1,
2mk− 1 + 1, if k ≥ 2.
Sequences Summation & Product Common sequences Solving recurrences Application Summary
Solution:
m1 = 1
m2 = 2m1 + 1 = 2(1) + 1 = 2 + 1
m3 = 2m2 + 1 = 2(2 + 1) + 1 = 22 + 2 + 1
m4 = 2m3 + 1 = 2(22 + 2 + 1) + 1 = 23 + 22 + 2 + 1
m5 = 2m4 + 1 = 2(23 + 22 + 2 + 1) + 1 = 24 + 23 + 22 + 2 + 1
Thus, we may guess the formula: mn = 2n− 1 + 2n− 2 + ... + 21 + 20 .
This is the sum of a geometric sequence. Using Equation (2), we get:
mn = 2n − 1, for all integers n ≥ 1.
We then check the formula using Induction.
Sequences Summation & Product Common sequences Solving recurrences Application Summary
Check using Induction
1. Let P(n) = ( mn = 2n − 1 ), ∀n ∈ Z + .
2. m1 = 1, by the initial conditions.
3. Also, 21 − 1 = 1. Thus P(1) is true.
4. For any k ∈ Z + :
5. Assume P(k) is true.
6. That is, mk = 2k − 1.
7. Now, mk+1 = 2mk + 1, by the recurrence relation.
8. = 2(2k − 1) + 1, using the Inductive hypothesis.
9. = 2k+1 − 2 + 1 = 2k+1 − 1, so P(k + 1) is true.
10. Thus by Mathematical Induction, the statement is true. □
Sequences Summation & Product Common sequences Solving recurrences Application Summary
5.4.3. Using formula
Guess and check works for relatively simple recurrences. But for
something like the Fibonacci sequence, things get tedious very
quickly. Fortunately there is a better way.
Definition 5.4.1 (Second-order Linear Homogeneous
Recurrence Relation with Constant Coefficients)
A second-order linear homogeneous recurrence relation with
constant coefficients is a recurrence relation of the form:
ak = Aak− 1 + Bak− 2 , ∀k ∈ Z ≥ k0
where A, B are real constants, B /= 0 and k0 is an integer constant.
The Fibonacci sequence is an example of such a recurrence
relation.
Sequences Summation & Product Common sequences Solving recurrences Application Summary
Theorem 5.8.3 (Epp) Distinct-Roots Theorem
Suppose a sequence a0 ,a1 ,a2 ,... satisfies a recurrence relation
ak = Aak− 1 + Bak− 2
for real constants A, B, with B /= 0, and k ∈ Z ≥ 2 . If the characteristic
equation
t 2 − At − B = 0
has two distinct roots r and s, then a0, a1, a2, ... is given by the explicit
formula
an = Cr n + Dsn , ∀n ∈ N
where C, D are real numbers determined by the initial conditions a0, a1.
Proof: see page 322 of Epp.
Sequences Summation & Product Common sequences Solving recurrences Application Summary
Example: solve the Fibonacci sequence
Fk = F k−1 + Fk−2, for all integers k ≥ 2
with initial conditions F0 = 0,F1 = 1.
Clearly, the Fibonacci recurrence is a second-order linear homogeneous
recurrence relation, with A = B = 1. Its characteristic equation is:
t2 − t − 1 = 0
Using the standard quadratic formula, we get:
1 ± 1 − 4(−1)
𝑡=
2
which yields distinct roots:
𝜙 = (1+ 5)/2, 𝜓 = (1− 5)/2,
Sequences Summation & Product Common sequences Solving recurrences Application Summary
Thus, by Theorem 5.8.3 (Epp), the explicit formula is:
Fn = C 𝜙 n + D 𝜓 n , ∀n ∈ N
We now need to solve for C and D using the initial conditions.
F0 = 0 = C 𝜙 0 + D 𝜓 0 = C + D
F1 = 1 = C 𝜙 1 + D 𝜓 1 = C 𝜙 + D 𝜓
These are two linear equations in two unknowns. Solving them gives:
C= 1/ 5, D=-1/ 5
Note that 𝜓 = −1/𝜙. We can thus write:
𝜙 𝑛 −(−𝜙) −𝑛
∀n ∈ N, Fn = .
5
Sequences Summation & Product Common sequences Solving recurrences Application Summary
Theorem 5.8.5 (Epp) Single-Roots Theorem
Suppose a sequence a0 ,a1 ,a2 ,... satisfies a recurrence relation
ak = Aak− 1 + Bak− 2
for real constants A,B, with B =/ 0, and k ∈ Z ≥ 2 . If the characteristic
equation
t 2 − At − B = 0
has a single real root r , then a0, a1, a2, ... is given by the explicit formula
an = Cr n + Dnr n , ∀n ∈ N
where C, D are real numbers determined by the value a0, and any other
known value of the sequence.
Proof omitted.
Sequences Summation & Product Common sequences Solving recurrences Application Summary
5.5. Application
Tower of Hanoi
E´duoard Lucas invented this puzzle in 1883. The goal is to move a set of
n disks of different sizes from one pole to another, subject to:
(i) Only one disk can be moved at a time.
(ii)At all times, no disk can rest on a smaller disk.
What is the minimum number of moves needed?
Sequences Summation & Product Common sequences Solving recurrences Application Summary
The key to solving this puzzle is to think recursively.
(a) Initial position. (b) After moving k − 1 disks from
A to B.
(c) After moving bottom disk (d) After moving k − 1 disks from
from A to C. B to C.
Sequences Summation & Product Common sequences Solving recurrences Application Summary
1. To move the whole stack of k disks from A to C, at some point you
need to move the bottom (largest) disk from A to C.
2. Since the bottom disk cannot rest on something smaller, C must be
empty when you move the bottom disk over. Also, there cannot be
anything on top of the bottom disk when you want to move it.
3. Thus, the top k − 1 disks must be on B.
4. Suppose an efficient genie helped you move the top k − 1 disks
from A to B, using m k−1 moves.
···
Sequences Summation & Product Common sequences Solving recurrences Application Summary
5. You can now move the bottom disk from A to C, using 1 move.
6. You then ask the genie to move the k − 1 disks from B to C, using
another m k−1 moves.
7. Thus, total number of moves is mk = 2mk− 1 + 1.
8. This is the most efficient way, because if the bottom disk did not
move directly from A to C, but say, it went to B first, then this
would incur even more moves.
Line 7 is thus the recurrence relation, and the initial condition is
obviously m1 = 1, because a tower of 1 disk requires just 1 move.
From Section 5.4.2, the solution to this recurrence relation is:
mn = 2n − 1, for n ∈ Z + .
Sequences Summation & Product Common sequences Solving recurrences Application Summary
5.6. Summary
• Sequences are common in Computer Science. They can be
expressed either by an explicit closed-form formula, or by
recurrence relations plus some initial conditions.
• In either way, code can be written to generate the sequence.
• Common sequences include Arithmetic and Geometric
sequences, Square and Triangle numbers, Fibonacci, and
Binomial numbers.
• Sums and products of a sequence generate another sequence.
• Solving a recurrence relation may be done in several ways:
looking it up, guessing and checking, using a formula.
• Recurrence relations are important for analyzing the behavior
of algorithms and data structures.
DISCRETE STRUCTURES
Graphs
Acknowledgement
• The contents of these slides have origin from School of
Computing, National University of Singapore.
• We greatly appreciate support from Mr. Aaron Tan Tuck Choy,
and Dr. Terence SIM Mong Cheng for kindly sharing these
materials.
March 19, 2024 2
Policies for students
• These contents are only used for students PERSONALLY.
• Students are NOT allowed to modify or deliver these contents to
anywhere or anyone for any purpose.
March 19, 2024 3
Recording of modifications
• Course website address is changed to
https://elearning.tdtu.edu.vn
• Course codes CS1231, CS1231S are placed by 501044.
March 19, 2024 4
10.1 Graphs: Definitions and
Basic Properties
March 19, 2024 5
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Graphs: Introduction
Graphs: Introduction
Shall we add some colours to this map of the United States?
6
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Graphs: Introduction
Graphs: Introduction
Shall we add some colours to this map of the United States?
7
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Graphs: Introduction
Map Colouring
Four-Colour Conjecture
Proposed by Guthrie in 1852, who conjectured that…
Four colours are sufficient to colour any map in a plane,
such that regions that share a common boundary do not
share the same colour.
Many false proofs since then.
Finally proved by Appel and Haken in 1977, with the help
of computer.
Robertson et al. provided another proof in 1996.
8
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Graphs: Introduction
Map Colouring
Example of a 4-
coloured map. World map with 4 colours.
But this is a map, not a graph!
However, we can model it as a graph.
But what is a graph?
9
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Graphs: Definitions and Basic Properties
Graphs: Definitions and Basic Properties
A graph G consists of
a set of vertices V(G), and An edge connects one vertex to
a set of edges E(G). another, or a vertex to itself.
Sometimes, we write G = {V, E}.
1
0
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Graphs: Definitions and Basic Properties
Graphs: Definitions and Basic Properties
Definition: Graph
A graph G consists of 2 finite sets: a nonempty set V(G) of
vertices and a set E(G) of edges, where each edge is associated
with a set consisting of either one or two vertices called its
endpoints.
An edge is said to connect its endpoints; two vertices that are
connected by an edge are called adjacent vertices; and a vertex
that is an endpoint of a loop is said to be adjacent to itself.
An edge is said to be incident on each of its endpoints, and two
edges incident on the same endpoint are called adjacent edges.
We write e = {v, w} for an edge e incident on vertices v and w.
1
1
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Graphs: Definitions and Basic Properties
Graphs: Definitions and Basic Properties
Example: Consider the following graph:
a. Write the vertex set V and the
edge set E, and give the list of
edges with their end-points.
V = {v1, v2, v3, v4, v5, v6}
E = {e1, e2, e3, e4, e5, e6, e7}
e1 = {v1, v2} e4 = {v2, v3}
e2 = {v1, v3} e5 = {v5, v6}
e3 = {v1, v3} e6 = {v5}
e7 = {v6} 9
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Graphs: Definitions and Basic Properties
Graphs: Definitions and Basic Properties
Example: Consider the following graph:
b. Find all edges that are incident on v1,
all vertices that are adjacent to v1, all
edges that are adjacent to e1, all
loops, all parallel edges, all vertices
that are adjacent to themselves, and
all isolated vertices.
Edges incident on v1: e1, e2 and e3. v5 and v6 are adjacent
Vertices adjacent to v1: v2 and v3. to themselves.
Edges adjacent to e1: e2, e3 and e4. Isolated vertex: v4.
Loops: e6 and e7.
e2 and e3 are parallel.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Graphs: Definitions and Basic Properties
Graphs: Definitions and Basic Properties
Definition: Directed Graph
A directed graph, or digraph, G, consists of 2 finite sets: a
nonempty set V(G) of vertices and a set D(G) of directed edges,
where each edge is associated with an ordered pair of vertices
called its endpoints.
If edge e is associated with the pair (v, w) of vertices, then e is
said to be the (directed) edge from v to w. We write e = (v, w).
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Modelling Graph Problems
Modelling Graph Problems
Map Colouring Problem
Solve it as a graph problem.
Draw a graph in which the vertices
represent the states, with every edge
joining two vertices represents the
states sharing a common border.
Such two vertices cannot be coloured
with the same colour.
A vertex colouring of a graph is an
assignment of colours to vertices so
that no two adjacent vertices have
the same colour.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Modelling Graph Problems
Modelling Graph Problems
Guy
Ven Sur
Col Fre
Bra
Ecu
Per
Bol Par
Chi Uru
Arg
Fal
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Modelling Graph Problems
Modelling Graph Problems
Guy
Ven Sur
Col Fre
Bra
Ecu
Per
Bol Par
Chi Uru
Arg
Fal
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Modelling Graph Problems
Wedding Planner
You are your best friend’s wedding planner and you
need to plan the seating arrangement for his 16 guests
attending his wedding dinner. However, some of the
guests cannot get along with some others.
A doesn’t get along with F, G or H. You don’t want to put
B doesn’t get along with C, D or H. guests who cannot
C doesn’t get along with B, D, E, G or H. get along with each
D doesn’t get along with B, C or E. other at the same
E doesn’t get along with C, D, F, or G. table!
F doesn’t get along with A, E or G. How many tables do
G doesn’t get along with A, C, E or F. you need?
H doesn’t get along with A, B or C.
Acknowledgement: http://www.math.uri.edu/~eaton/0131873814_MEb.pdf 15
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Modelling Graph Problems
A doesn’t get along with F, G or H.
Wedding Planner B doesn’t get along with C, D or H.
C doesn’t get along with B, D, E, G or H.
D doesn’t get along with B, C or E.
Graph with vertices E doesn’t get along with C, D, F, or G.
representing the F doesn’t get along with A, E or G.
guests, and an edge G doesn’t get along with A, C, E or F.
is drawn between H doesn’t get along with A, B or C.
two guests who
Vertex colouring problem.
don’t get along.
4 colours (4 tables)?
Acknowledgement: http://www.math.uri.edu/~eaton/0131873814_MEb.pdf
16
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Modelling Graph Problems
Other Vertex Colouring Problems
If the vertices And two vertices Then a vertex colouring
represent… are adjacent if …. can be used to…
1. classes, the corresponding schedule classes.
classes have students
in common,
2. radio stations, the stations are assign non-
close enough to interfering
interfere with each frequencies to the
other, stations.
3. traffic the corresponding designate sets of signals
signals at an signals cannot be green that can be green at the
intersection, at the same time, same time.
17
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Special Graphs
Simple Graphs
Definition: Simple Graph
A simple graph is an undirected graph that does not have any
loops or parallel edges.
Example: Draw all simple graphs with the 4 vertices {u,
v, w, x} and two edges, one of which is {u, v}.
Each possible edge of a simple graph corresponds to a subset of
two vertices. Hence there are 24 = 6 such subsets. One is given.
Draw the other two.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Special Graphs
Complete Graphs
Definition: Complete Graph
A complete graph on n vertices, n > 0, denoted Kn, is a simple
graph with n vertices and exactly one edge connecting each pair
of distinct vertices .
Example: The complete graphs K1, K2, K3 and K4.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Special Graphs
Complete Bipartite Graphs
Definition: Complete Bipartite Graph
A complete bipartite graph on (m, n) vertices, where m, n > 0,
denoted Km,n, is a simple graph with distinct vertices v1, v2,…, vm,
and w1, w2,…, wn that satisfies the following properties:
For all i, k = 1, 2, …, m and for all j, l = 1, 2, …, n,
1. There is an edge from each vertex vi to each vertex wj.
2. There is no edge from any vertex vi to any other vertex vk.
3. There is no edge from any vertex wj to any other vertex wl.
K3,2 K2,5
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Special Graphs
Subgraph of a Graph
Definition: Subgraph of a Graph
A graph H is said to be a subgraph of graph G if, and only if,
every vertex in H is also a vertex in H, every edge in H is also an
edge in G, and every edge in H has the same endpoints as it has
in G.
A graph G A subgraph
of G
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
The Concept of Degree
Degree of a Vertex and Total Degree of a Graph
Definition: Degree of a Vertex and Total Degree of a Graph
Let G be a graph and v a vertex of G. The degree of v, denoted
deg(v), equals the number of edges that are incident on v, with
an edge that is a loop counted twice.
The total degree of G is the sum of the degrees of all the
vertices of G.
The degree of a vertex can be
obtained from the drawing of a
graph by counting how many
end segments of edges are
incident on the vertex.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
The Concept of Degree
Degree of a Vertex and Total Degree of a Graph
Example: Find the degree of each vertex of the graph G
shown below. Then find the total degree of G.
deg(v1) = 0
deg(v2) = 2
deg(v3) = 4
Total degree of G = 6
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
The Concept of Degree
Theorem 10.1.1 The Handshake Theorem
If G is any graph, then the sum of the degrees of all the vertices of
G equals twice the number of edges of G. Specifically, if the
vertices of G are v1, v2, …, vn, where n 0, then
The total degree of G = deg(v1) + deg(v2) + … + deg(vn)
= 2(the number of edges of G).
Corollary 10.1.2
The total degree of a graph is even.
Proposition 10.1.3
In any graph there are an even number of vertices of odd degree.
10.2 Trails, Paths, and
Circuits
March 19, 2024 28
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Introduction
Let’s Have Some Fun
(1) (2) (3) (4)
(5) (6) (7) (8)
26
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Introduction
Königsberg bridges
The subject of graph theory began in the year 1736
when the great mathematician Leonhard Euler
published a paper giving the solution to the following
puzzle:
The town of Königsberg in Prussia (now Kaliningrad in
Russia) was built at a point where two branches of the
Pregel River came together. It consisted of an island and
some land along the river banks.
These were connected by 7 bridges.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Introduction
Königsberg bridges
Question: Is it possible to
take a walk around town,
starting and ending at
the same location and
crossing each of the 7
bridges exactly once?
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Introduction
Königsberg bridges
In terms of this graph, the question is:
Is it possible to find a route through the graph that
starts and ends at some vertex, one of A, B, C, or D,
and traverses each edge exactly once?
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Definitions
Definitions
Travel in a graph is accomplished by moving from one
vertex to another along a sequence of adjacent edges.
In the graph below, for instance, you can go from u1 to
u4 by taking f1 to u2 and then f7 to u4. This is
represented by writing u1 f1 u2 f7 u4.
Or, you could take a
roundabout route:
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Definitions
Walk, Trail, Path, Closed Walk, Circuit, Simple Circuit
Definitions
Let G be a graph, and let v and w be vertices of G.
A walk from v to w is a finite alternating sequence of adjacent
vertices and edges of G. Thus a walk has the form
v0 e1 v1 e2 … vn-1 en vn ,
where the v’s represent vertices, the e’s represent edges, v0=v, vn=w,
and for all i {1, 2, …, n}, vi-1 and vi are the endpoints of ei.
The trivial walk from v to v consist of the single vertex v.
A trail from v to w is a walk from v to w that does not contain a
repeated edge.
A path from v to w is a trail that does not contain a repeated vertex.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Definitions
Walk, Trail, Path, Closed Walk, Circuit, Simple Circuit
Definitions
A closed walk is a walk that starts and ends at the same vertex.
A circuit (or cycle) is a closed walk that contains at least one edge
and does not contain a repeated edge.
A simple circuit (or simple cycle) is a circuit that does not have any
other repeated vertex except the first and last.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Definitions
Walk, Trail, Path, Closed Walk, Circuit, Simple Circuit
Often a walk can be specified unambiguously by giving
either a sequence of edges or a sequence of vertices.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Definitions
Walk, Trail, Path, Closed Walk, Circuit, Simple Circuit
In this graph, determine which of the following walks
are trails, paths, circuits, or simple circuits.
a. Trail; not a path.
b. Walk; not a trail.
c. Circuit; not a
simple circuit.
d.
e.
f.
34
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Definitions
Notes
Because most of the major developments in graph
theory have happened relatively recently and in a variety
of different contexts, the terms used in the subject have
not been standardized.
For example, what this book calls a graph is sometimes
called a multigraph, what this book calls a simple graph
is sometimes called a graph, what this book calls a vertex
is sometimes called a node, and what this book calls an
edge is sometimes called an arc.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Definitions
Notes
Similarly, instead of the word trail, the word path is
sometimes used; instead of the word path, the words
simple path are sometimes used; and instead of the
words simple circuit, the word cycle is sometimes used.
The terminology in this book is among the most
common, but if you consult other sources, be sure to
check their definitions.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Connectedness
Connectedness
A graph is connected if it is possible to travel from any vertex to
any other vertex along a sequence of adjacent edges of the graph.
Definition: Connectedness
Two vertices v and w of a graph G are connected if, and only if,
there is a walk from v to w.
The graph G is connected if, and only if, given any two vertices v and
w in G, there is a walk from v to w. Symbolically,
G is connected iff vertices v, w V(G), a walk from v to w.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Connectedness
Example: Which of the following graphs are connected?
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Connectedness
Some useful facts relating circuits and connectedness are
collected in the following lemma.
Lemma 10.2.1
Let G be a graph.
a. If G is connected, then any two distinct vertices of G can be
connected by a path.
b. If vertices v and w are part of a circuit in G and one edge is
removed from the circuit, then there still exists a trail from v
to w in G.
c. If G is connected and G contains a circuit, then an edge of
the circuit can be removed without disconnecting G.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Connected Component
Connected Component
The graphs in (b) and (c) are both made up of three
pieces, each of which is itself a connected graph.
A connected component of a graph is a connected
subgraph of largest possible size.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Connected Component
Definition: Connected Component
A graph H is a connected component of a graph G if, and only if,
1. The graph H is a subgraph of G;
2. The graph H is connected; and
3. No connected subgraph of G has H has a subgraph and contains
vertices or edges that are not in H.
The fact is that any graph is a kind of union of its
connected components.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Connected Component
Find all connected components of the following graph G.
G has 3 connected components H1, H2 and H3 with vertex
sets V1, V2 and V3 and edge sets E1, E2 and E3 , where
𝑉1 = 𝑣1 , 𝑣2 , 𝑣3 , 𝐸1 = e1 , e2
𝑉2 = 𝑣4 , 𝐸2 = ∅
𝑉3 = 𝑣5 , 𝑣6 , 𝑣7 , 𝑣8 , 𝐸3 = e3 , e4 , e5
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Euler Circuits
Euler Circuits
Now, let’s go back to the puzzle of the
Königsberg bridges.
Is it possible to find a route through
the graph that starts and ends at some
vertex, one of A, B, C, or D, and
traverses each edge exactly once?
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Euler Circuits
Definition: Euler Circuit
Let G be a graph. An Euler circuit for G is a circuit that contains
every vertex and every edge of G.
That is, an Euler circuit for G is a sequence of adjacent vertices and
edges in G that has at least one edge, starts and ends at the same
vertex, uses every vertex of G at least once, and uses every edge of
G exactly once.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Euler Circuits
Theorem 10.2.2
If a graph has an Euler circuit, then every vertex of the graph has
positive even degree.
Contrapositive Version of Theorem 10.2.2
If some vertex of a graph has odd degree, then the graph does not
have an Euler circuit.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Euler Circuits
Does each of the following graphs have an Euler circuit?
(1) (2) (3) (4)
(5) (6) (7) (8)
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Euler Circuits
Is the converse of Theorem 10.2.2 true?
If every vertex of a graph has even degree,
then the graph has an Euler circuit.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Euler Circuits
Theorem 10.2.3
If a graph G is connected and the degree of every vertex of G is a
positive even integer, then G has an Euler circuit.
The proof of Theorem 10.2.3 is constructive: It contains an algorithm to find an
Euler circuit for any connected graph in which every vertex has even degree.
Theorem 10.2.4
A graph G has an Euler circuit if, and only if, G is connected and
every vertex of G has positive even degree.
A corollary to Theorem 10.2.4 gives a criterion for determining when it is
possible to find a walk from one vertex of a graph to another, passing through
every vertex of the graph at least once and every edge of the graph exactly
once.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Euler Circuits
Definition: Euler Trail
Let G be a graph, and let v and w be two distinct vertices of G.
An Euler trail/path from v to w is a sequence of adjacent edges
and vertices that starts at v, ends at w, passes through every
vertex of G at least once, and traverses every edge of G exactly
once.
Corollary 10.2.5
Let G be a graph, and let v and w be two distinct vertices of G.
There is an Euler trail from v to w if, and only if, G is connected,
v and w have odd degree, and all other vertices of G have
positive even degree.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Euler Circuits
The following graphs do not have an Euler circuit.
Do they have an Euler trail/path?
(1) (5)
50
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Euler Circuits
The floor plan shown below is for a house that is open for public
viewing. Is it possible to find a trail that starts in room A, ends in
room B, and passes through every interior doorway of the house
exactly once? If so, find such a trail.
Each vertex of this graph has even degree except for A and B,
each of which has degree 1.
Hence by Corollary 10.2.5, there is an Euler path from A to B.
One such trail is AGHFEIHEKJDCB.
Hierholzer’s Algorithm for Identifying Eulerian Circuits
55
Example
56
57
Quiz
58
Fleury’s Algorithm for Identifying Eulerian Circuits
Chapter 9. Paths
12/30/2019 59
Quiz
60
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Hamiltonian Circuits
Hamiltonian Circuits
Recall Theorem 10.2.4:
Theorem 10.2.4
A graph G has an Euler circuit if, and only if, G is connected and
every vertex of G has positive even degree.
A related question:
Given a graph G, is it possible to find a circuit for G in
which all the vertices of G (except the first and the last)
appear exactly once?
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Hamiltonian Circuits
In 1859 the Irish mathematician Sir William Rowan
Hamilton introduced a puzzle in the shape of a
dodecahedron (DOH-dek-a-HEE-dron). (Figure 10.2.6
contains a drawing of a dodecahedron, which is a solid figure
with 12 identical pentagonal faces.)
Figure 10.2.6 Dodecahedron
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Hamiltonian Circuits
Each vertex was labeled with the name of a city —
London, Paris, Hong Kong, New York, and so on.
The problem Hamilton posed was to start at one city
and tour the world by visiting each other city exactly
once and returning to the starting city.
One way to solve the
puzzle is to imagine the
surface of the
dodecahedron stretched
out and laid flat in the
plane, as follows:
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Hamiltonian Circuits
The circuit denoted with black lines is one solution.
Note that although every city is visited, many edges are
omitted from the circuit. (More difficult versions of the
puzzle required that certain cities be visited in a certain order.)
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Hamiltonian Circuits
Definition: Hamiltonian Circuit
Given a graph G, a Hamiltonian circuit for G is a simple circuit
that includes every vertex of G.
That is, a Hamiltonian circuit for G is a sequence of adjacent
vertices and distinct edges in which every vertex of G appears
exactly once, except for the first and the last, which are the
same.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Hamiltonian Circuits
Note that although an Euler circuit for a graph G must
include every vertex of G, it may visit some vertices
more than once and hence may not be a Hamiltonian
circuit.
On the other hand, a Hamiltonian circuit for G does not
need to include all the edges of G and hence may not
be an Euler circuit.
Despite the analogous-sounding definitions of Euler
and Hamiltonian circuits, the mathematics of the two
are very different.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Hamiltonian Circuits
Theorem 10.2.4 gives a simple criterion for
determining whether a given graph has an Euler circuit.
Unfortunately, there is no analogous criterion for
determining whether a given graph has a Hamiltonian
circuit, nor is there even an efficient algorithm for
finding such a circuit.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Hamiltonian Circuits
There is, however, a simple technique that can be used
in many cases to show that a graph does not have a
Hamiltonian circuit.
This follows from the following considerations:
Suppose a graph G with at least two vertices has a
Hamiltonian circuit C given concretely as
Since C is a simple circuit, all the ei are distinct and all
the vj are distinct except that v0 = vn. Let H be the
subgraph of G that is formed using the vertices and
edges of C.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Hamiltonian Circuits
An example of such an H is shown below.
H is indicated by
the black lines.
Note that H has the same number of edges as it has
vertices since all its n edges are distinct and so are its
n vertices v1, v2, . . . , vn.
Also, by definition of Hamiltonian circuit, every vertex
of G is a vertex of H, and H is connected since any two
of its vertices lie on a circuit. In addition, every vertex
of H has degree 2.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Hamiltonian Circuits
The reason for this is that there are exactly two edges
incident on any vertex. These are ei and ei+1 for any
vertex vi except v0=vn, and they are e1 and en for v0 (=vn).
These observations have established the truth of the following
proposition in all cases where G has at least two vertices.
Proposition 10.2.6
If a graph G has a Hamiltonian circuit, then G has a subgraph H
with the following properties:
1. H contains every vertex of G.
2. H is connected.
3. H has the same number of edges as vertices.
4. Every vertex of H has degree 2.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Hamiltonian Circuits
The contrapositive of Proposition 10.2.6 says that if a
graph G does not have a subgraph H with properties
(1)–(4), then G does not have a Hamiltonian circuit.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Travelling Salesman Problem
Travelling Salesman Problem
Imagine that the drawing below is a map showing four
cities and the distances in kilometers between them.
Suppose that a salesman must travel to each city exactly
once, starting and ending in city A. Which route from
city to city will minimize the total distance that must be
travelled?
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Travelling Salesman Problem
This problem can be solved by writing all
possible Hamiltonian circuits starting and
ending at A and calculating the total distance
travelled for each.
Thus either route ABCDA or ADCBA gives a minimum total
distance of 125 km.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Travelling Salesman Problem
The general travelling salesman problem involves finding a
Hamiltonian circuit to minimize the total distance travelled for an
arbitrary graph with n vertices in which each edge is marked with
a distance.
One way to solve the general problem is to use the previous
method: Write down all Hamiltonian circuits starting and ending
at a particular vertex, compute the total distance for each, and
pick one for which this total is minimal.
However, this is impractical for even medium-sized values of n.
For n = 30 vertices, there would be (29!)/2 4.421030
Hamiltonian circuits starting and ending at a particular vertex to
check. If each circuit could be found and its total distance
computed in just one nanosecond, it would take approximately
1.4 1014 years to compute!
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Travelling Salesman Problem
At present, there is no known algorithm for solving the general
travelling salesman problem that is more efficient.
However, there are efficient algorithms that find “pretty good”
solutions—that is, circuits that, while not necessarily having the
least possible total distances, have smaller total distances than
most other Hamiltonian circuits.
10.3 Matrix Representations
of Graphs
March 19, 2024 76
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Matrix Representations of Graphs
Matrices
Definition: Matrix
An m n (read “m by n”) matrix A over a set S is a rectangular
array of elements of S arranged into m row and n columns.
ith row of A
jth column of A
We write A = (𝑎 ij ).
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Matrices
If A and B are matrices, then A = B if, and only if, A and B have the
same size and the corresponding entries of A and B are all equal;
that is,
𝑎i j = 𝑏i j for all i = 1, 2, ⋯ , 𝑚 and j = 1, 2, ⋯ , 𝑘.
A matrix for which the numbers of rows and columns are equal is
called a square matrix.
If A is a square matrix of size n n, then the main diagonal of A
consists of all the entries 𝑎11 , 𝑎22 , ⋯ 𝑎𝑛 𝑛 .
main diagonal of A
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Matrices and Directed Graphs
Matrices and Directed Graphs
Figure 10.3.1 A Directed Graph and Its Adjacency Matrix
This graph G is represented by the matrix A = (𝑎 ij ) for which 𝑎 ij =
number of arrows from vi to vj for all i = 1, 2, 3 and j = 1, 2, 3.
A is called the adjacency matrix of G.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Matrices and Directed Graphs
Definition: Adjacency Matrix of a Directed Graph
Let G be a directed graph with ordered vertices v1, v2, … vn. The
adjacency matrix of G is the n n matrix A = (𝑎 ij ) over the set
of non-negative integers such that
𝑎 ij = the number of arrows from vi to vj
for all i, j = 1, 2, …, n.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Matrices and Directed Graphs
Example: Find the adjacency matrices of the two directed graphs
below.
(a) (b)
(a)
72
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Matrices and Undirected Graphs
Matrices and Undirected Graphs
Definition: Adjacency Matrix of an Undirected Graph
Let G be an undirected graph with ordered vertices v1, v2, … vn.
The adjacency matrix of G is the n n matrix A = (𝑎 ij ) over the
set of non-negative integers such that
𝑎 ij = the number of edges connecting vi and vj
for all i, j = 1, 2, …, n.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Matrices and Undirected Graphs
Example: Find the adjacency matrix for the graph G shown below.
Note that the
matrix is symmetric.
Definition: Symmetric Matrix
An n n square matrix A = (𝑎 ij ) is called symmetric if, and only
if, for all i, j = 1, 2, …, n,
𝑎 ij = 𝑎 ji .
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Matrices and Connected Components
Matrices and Connected Components
Consider a graph G, as shown below, that consists of
several connected components.
Adjacency matrix of G:
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Matrices and Connected Components
As you can see, A consists of square matrix blocks (of
different sizes) down its diagonal and blocks of 0’s
everywhere else.
The reason is that vertices in
each connected component
share no edges with vertices in
other connected components.
For instance, since v1, v2, and v3 share no
edges with v4, v5, v6, or v7, all entries in
the top three rows to the right of the third
column are 0 and all entries in the left
three columns below the third row are
also 0.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Matrices and Connected Components
Sometimes matrices whose entries are all 0’s are
themselves denoted 0. If this convention is followed
here, A is written as:
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Matrices and Connected Components
The previous reasoning can be generalized to prove the following
theorem:
Theorem 10.3.1
Let G be a graph with connected components G1, G1, …, Gk. If
there are ni vertices in each connected component Gi and these
vertices are numbered consecutively, then the adjacency matrix of
G has the form:
𝐴1 O O O
O
O 𝐴2 O ⋯ O O
O O 𝐴3 O O
⋮ ⋮
where each Ai is ni nO O O ⋯ O 𝐴
i adjacency matrix of Gi, kfor all i = 1, 2, …, k,
and the O’s represent matrices whose entries are all 0s.
78
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Matrix Multiplication
Matrix Multiplication
Definition: Scalar Product
Suppose that all entries in matrices A and B are real numbers. If
the number of elements, n, in the ith row of A equals the
number of elements in the jth column of B, then the scalar
product or dot product of the ith row of A and the jth column
of B is the real number obtained as follows:
𝑏 1j
𝑏 2j
𝑎i1 𝑎i2 ⋯ 𝑎 i𝑛 = 𝑎i1 𝑏1j + 𝑎 i2 𝑏2j + ⋯ + 𝑎i 𝑛 𝑏 .
⋮
𝑛
𝑏 𝑛j j
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Matrix Multiplication
Definition: Matrix Multiplication
Let A = (aij) be an m k matrix and B = (bij) an k n matrix with real entries.
The (matrix) product of A times B, denoted AB, is that matrix (cij) defined as
follows:
where
𝑐i j = 𝑎i1 𝑏1 j + 𝑎i2 𝑏2 j + ⋯ + 𝑎ik 𝑏k j = ∑k𝑟=1 𝑎 i𝑟 𝑏 𝑟j .
for all i = 1, 2, …, m and j = 1, 2, …, n.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Matrix Multiplication
Example – Computing a Matrix Product
Solution:
2 3
where
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Matrix Multiplication
Example – Computing a Matrix Product
Solution:
2 3
-2 -1
where
–2
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Matrix Multiplication
Multiplication of real numbers is commutative, but matrix
multiplication is not.
On the other hand, both real number and matrix multiplications
are associative ((ab)c = a(bc), for all elements a, b, and c for which
the products are defined).
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Matrix Multiplication
Identity Matrix
These computations show that acts as an identity on
the left side for multiplication with 2 3 matrices and that
acts as an identity on the right side for multiplication
with 3 3 matrices.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Matrix Multiplication
Definition: Identity Matrix
For each positive integer n, the n n identity matrix, denoted
In = (ij) or just I (if the size of the matrix is obvious from
context), is the n n matrix in which all the entries in the main
diagonal are 1’s and all other entries are 0’s. In other words,
1, if i = j
ði j = { for all i, j = 1, 2, … , 𝑘.
0, if i ≠ j
The German mathematician Leopold Kronecker introduced the
symbol i j to make matrix computations more convenient. In his
honour, this symbol is called the Kronecker delta.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Matrix Multiplication
There are also similarities and differences between real
numbers and matrices with respect to the computation
of powers.
Any number can be raised to a non-negative integer
power, but a matrix can be multiplied by itself only if it
has the same number of rows as columns.
As for real numbers, however, the definition of matrix
powers is recursive.
Just as any number to the zero power is defined to be 1,
so any n n matrix to the zero power is defined to be
the n n identity matrix.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Matrix Multiplication
nth Power of a Matrix
Definition: Identity Matrix
For any n n matrix A, the powers of A are defined as follows:
A0 = I where I is the n n identity matrix
An = A An – 1 for all integers n 1
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Matrix Multiplication
Example – Power of a Matrix
Solution:
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Counting Walks of Length N
Counting Walks of Length N
A walk in a graph consists of an alternating sequence of
vertices and edges.
If repeated edges are counted each time they occur,
then the number of edges in the sequence is called the
length of the walk.
For instance, the walk v2e3v3e4v2e2v2e3v3 has length 4
(counting e3 twice).
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Counting Walks of Length N
Example: Consider the following graph G.
How many distinct walks of length 2 connect v2 and v2?
One walk of length 2 from v2 to v1:
v2e1v1e1v2.
One walk of length 2 from v2 to v2:
v2e2v2e2v2.
Four walks of length 2 from v2 to v3:
v2e3v3e4v2 ,
v2e4v3e3v2,
v2e3v3e3v2, Total = 6
v2e4v3e4v2.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Counting Walks of Length N
The general question of finding the number of walks
that have a given length and connect two particular
vertices of a graph can easily be answered using matrix
multiplication.
Consider the adjacency matrix A of the graph G.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Counting Walks of Length N
Compute A2:
Note that the entry in the second row and the second
column is 6, which equals the number of walks of
length 2 from v2 to v2.
Reason: To compute a22, you multiply the second row of A times
the second column of A to obtain a sum of three terms:
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Counting Walks of Length N
More generally, if A is the adjacency matrix of a graph G, the i j-th
entry of A2 equals the number of walks of length 2 connecting the
i-th vertex to the j-th vertex of G.
Even more generally, if n is any positive integer, the i j-th entry of
An equals the number of walks of length n connecting the i-th and
the j-th vertices of G.
Theorem 10.3.2
If G is a graph with vertices v1, v1, …, vm and A is the adjacency
matrix of G, then for each positive integer n and for all integers i, j
= 1, 2, …, m,
the ij-th entry of An = the number of walks of length n from vi to vj.
10.4 Isomorphims of Graphs
March 19, 2024 103
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Isomorphisms of Graphs
Introduction
The two drawings shown in Figure 10.4.1 both represent
the same graph: Their vertex and edge sets are identical,
and their edge-endpoint functions are the same. Call
this graph G.
Figure 10.4.1
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Isomorphisms of Graphs
Now consider the graph G' represented in Figure 10.4.2.
Figure 10.4.1 Figure 10.4.2
Observe that G' is a different graph from G (for instance,
in G the endpoints of e1 are v1 and v2, whereas in G' the
endpoints of e1 are v1 and v3).
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Isomorphisms of Graphs
Yet G' is certainly very similar to G. In fact, if the vertices
and edges of G' are relabeled by the functions shown in
Figure 10.4.3, then G' becomes the same as G.
Figure 10.4.3
Note that these relabeling functions are one-to-one and onto.
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Isomorphisms of Graphs
Two graphs that are the same except for the labeling of
their vertices and edges are called isomorphic.
Definition: Isomorphic Graph
Let G and G' be graphs with vertex sets V(G) and V(G') and edge
sets E(G) and E(G') respectively. G is isomorphic to G‘ if, and
only if, there exist one-to-one correspondences g: V(G) V(G')
and h: E(G) E(G') that preserve the edge-endpoint functions
of G and G‘ in the sense that for all v V(G) and e E(G),
v is an endpoint of e g(v) is an endpoint of h(e).
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Isomorphisms of Graphs
Example: Show that the following two graphs are
isomorphic.
To solve this, you find functions g: V(G) V(G') and
h: E(G) E(G') such that for all for all v V(G) and
e E(G), v is an endpoint of e if, and only if, g(v) is an
endpoint of h(e).
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Isomorphisms of Graphs
Example: Show that the following two graphs are
isomorphic.
100
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Isomorphisms of Graphs
It is not hard to show that graph isomorphism is an
equivalence relation on a set of graphs; in other words,
it is reflexive, symmetric, and transitive.
Theorem 10.4.1 Graph Isomorphism is an Equivalence Relation
Let S be a set of graphs and let R be the relation of graph
isomorphism on S. Then R is an equivalence relation on S.
110
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Isomorphisms of Graphs
“Is there a general method (algorithm) to determine if
two graphs G and G' are isomorphic?
There is such an algorithm, but it takes an unreasonably
long time to perform.
If G and G' each has n vertices and m edges, the number
of one-to-one correspondences from vertices to vertices
is n! and the number of one-to-one correspondences
from edges to edges is m!, so the total number of pairs
of functions to check is n!m!.
For example, if m = n = 20, there would be 20!20! 5.9
1036 pairs to check. If each check takes 1 ns, the total
time would be approximately 1.9 1020 years! 111
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Isomorphisms of Graphs
Though there is no more efficient algorithm known for
checking if two graphs are isomorphic, there are some
simple tests that can be used to show that certain pairs
of graphs are not isomorphic.
Since two isomorphic graphs must have the same
number of vertices and edges, we know they are not
isomorphic if they do not have the same number of
vertices or edges.
A property that is preserved by graph isomorphism is
called an isomorphic invariant. The number of vertices
and edges are two such invariants.
112
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Invariant for Graph Isomorphism
Invariant for Graph Isomorphism
Definition: Invariant for Graph Isomorphism
A property P is called an invariant for graph isomorphism if,
and only if, given any graphs G and G', if G has property P and
G' is isomorphic to G, then G' has property P.
113
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Invariant for Graph Isomorphism
Invariant for Graph Isomorphism
Theorem 10.4.2 Invariants for Graph Isomorphism
Each of the following properties is an invariant for graph
isomorphism, where n, m, and k are all non-negative integers.
1. has n vertices; 6. has a simple circuit of length k;
2. has m edges; 7. has m simple circuits of length k;
3. has a vertex of degree k; 8. is connected;
4. has m vertices of degree k; 9. has an Euler circuit;
5. has a circuit of length k; 10. has a Hamiltonian circuit.
114
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Invariant for Graph Isomorphism
Show that the following pairs of graphs are not
isomorphic by finding an isomorphic invariant that they
do not share.
a.
b.
115
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Graph Isomorphism for Simple Graphs
Graph Isomorphism for Simple Graphs
When graphs G and G are both simple, the definition of G being
isomorphic to G can be written without referring to the
correspondence between the edges of G and the edges of G.
Definition
If G and G' are simple graphs, then G is isomorphic to G' if, and
only if, there exists a one-to-one correspondence g from the
vertex set V(G) of G to the vertex set V(G') of G' that preserves
the edge-endpoint functions of G and G' in the sense that for all
vertices u and v of G,
{u, v} is an edge in G {g(u), g(v)} is an edge in G'.
116
Graphs: Definitions Trails, Paths, and Circuits Matrix Representations Isomorphisms
Graph Isomorphism for Simple Graphs
Example: Are the two graphs shown below isomorphic?
If so, define an isomorphism.
Yes.
Define g: V(G) → V(G) by the arrow diagram shown below.
Then g is one-to-one and onto by inspection.
117
DISCRETE STRUCTURES
Graphs
Acknowledgement
• The contents of these slides have origin from School of
Computing, National University of Singapore.
• We greatly appreciate support from Mr. Aaron Tan Tuck Choy,
and Dr. Terence SIM Mong Cheng for kindly sharing these
materials.
March 19, 2024 2
Policies for students
• These contents are only used for students PERSONALLY.
• Students are NOT allowed to modify or deliver these contents to
anywhere or anyone for any purpose.
March 19, 2024 3
Recording of modifications
• Course website address is changed to
https://elearning.tdtu.edu.vn
• Course codes CS1231, CS1231S are placed by 501044.
March 19, 2024 4
10.5 Trees
March 19, 2024 5
Trees Rooted Trees Spanning trees and Shortest Paths
Definition
6
Trees Rooted Trees Spanning trees and Shortest Paths
Definition
Definition
Definition: Tree
A graph is said to be circuit-free if, and only if, it has no circuits.
A graph is called a tree if, and only if, it is circuit-free and
connected.
A trivial tree is a graph that consists of a single vertex.
A graph is called a forest if, and only if, it is circuit-free and not
connected.
7
Trees Rooted Trees Spanning trees and Shortest Paths
Examples
Possibility Tree
As discussed in week 9, a possibility tree is used to keep
systematic track of all possibilities in which events happen in
order. For example:
Figure 9.2.1 The Outcomes of a Tournament
8
Trees Rooted Trees Spanning trees and Shortest Paths
Examples
Parse Tree
In the last 30 years, Noam Chomsky and others have
developed new ways to describe the syntax (or
grammatical structure) of natural languages such as
English.
In the study of grammars, trees are often used to show
the derivation of grammatically correct sentences from
certain basic rules. Such trees are called syntactic
derivation trees or parse trees.
9
Trees Rooted Trees Spanning trees and Shortest Paths
Examples
Parse Tree
A very small subset of English grammar, for example, specifies
that:
1. a sentence can be produced by writing first a noun phrase and then a
verb phrase;
2. a noun phrase can be produced by writing an article and then a noun;
3. a noun phrase can also be produced by writing an article, then an
adjective, and then a noun;
4. a verb phrase can be produced by writing a verb and then a noun
phrase;
5. one article is “the”;
6. one adjective is “young”;
7. one verb is “caught”;
8. one noun is “man”;
9. one (other) noun is “ball.”
10
Trees Rooted Trees Spanning trees and Shortest Paths
Examples
Parse Tree
The rules of a grammar are called productions. It is customary
to express them using the shorthand notation illustrated below,
in Backus-Naur notation:
1. <sentence> <noun phrase> <verb phrase>
2,3. <noun phrase> <article> <noun> |
<article> <adjective> <noun>
4. <verb phrase> <verb> <noun phrase>
5. <article> the
The symbol | represents or,
6. <adjective> young
and <> are used to enclose
7.<verb> caught 8,9.
terms to be defined.
<noun> man | ball
11
Trees Rooted Trees Spanning trees and Shortest Paths
Examples
Parse Tree
The derivation of the sentence “The young man caught the ball”
from the mentioned rules is described by the tree shown below:
12
Trees Rooted Trees Spanning trees and Shortest Paths
Characterizing Trees
Lemma 10.5.1
Any non-trivial tree has at least one vertex of degree 1.
Proof: Let T be a particular but arbitrarily chosen non-trivial tree.
Step 1: Pick a vertex v of T and let e be an edge incident on v.
Step 2: While deg(v) > 1, repeat steps 2a, 2b and 2c:
2a: Choose e' to be an edge incident on v such that e' e.
2b: Let v' be the vertex at the other end of e' from v.
2c: Let e = e' and v = v'.
The algorithm must eventually terminate because the set of
vertices of the tree T is finite and T is circuit-free. When it does, a
vertex v of degree 1 will have been found.
13
Trees Rooted Trees Spanning trees and Shortest Paths
Characterizing Trees
Lemma 10.5.1
Any non-trivial tree has at least one vertex of degree 1.
Using Lemma 10.5.1 it is not difficult to show that, in fact, any
tree that has more than one vertex has at least two vertices of
degree 1.
14
Trees Rooted Trees Spanning trees and Shortest Paths
Characterizing Trees
Definition: Terminal vertex (leaf) and internal vertex
Let T be a tree. If T has only one or two vertices, then each is
called a terminal vertex (or leaf). If T has at least three vertices,
then a vertex of degree 1 in T is called a terminal vertex (or
leaf), and a vertex of degree greater than 1 in T is called an
internal vertex.
15
Trees Rooted Trees Spanning trees and Shortest Paths
Characterizing Trees
Example: Find all terminal vertices and all internal
vertices in the following tree:
Terminal vertices: v0, v2, v4, v5, v7 and v8.
Internal vertices: v6, v1 and v3.
16
Trees Rooted Trees Spanning trees and Shortest Paths
Characterizing Trees
Theorem 10.5.2
Any tree with n vertices (n > 0) has n – 1 edges.
Proof: By mathematical induction.
Let the property P(n) be “any tree with n vertices has n – 1 edges”.
P(1): Let T be any tree with one vertex. Then T has no edges.
So P(1) is true.
Show that for all integers k 1, if P(k) is true then P(k+1) is true.
Suppose P(k) is true.
1. Let T be a particular but arbitrarily chosen tree with k + 1 vertices.
2. Since k is positive, (k + 1) 2, and so T has more than one vertex.
3. Hence, by Lemma 10.5.1, T has a vertex v of degree 1, and has at least
another vertex in T besides v.
17
Trees Rooted Trees Spanning trees and Shortest Paths
Characterizing Trees
Proof: (continued…)
3. Hence, by Lemma 10.5.1, T has a vertex v of degree 1, and has at least
another vertex in T besides v.
4. Thus, there is an edge e connecting v to the rest of T.
5. Define a subgraph T' of T so that V(T') = V(T) – {v} and E(T') = E(T) – {e}.
1. The number of vertices of T' is (k + 1) – 1 = k.
2. T' is circuit-free.
e T'
3. T' is connected. …
v
6. Hence by definition, T' is a tree.
7. Since T' has k vertices, by inductive hypothesis,
number of edges of T' = (number of vertices of T') – 1 = k – 1.
8. But number of edges of T = (number of edges of T') + 1 = k.
9. Hence P(k+1) is true.
18
Trees Rooted Trees Spanning trees and Shortest Paths
Characterizing Trees
Example: Find all non-isomorphic trees with four
vertices.
By Theorem 10.5.2, any tree with four vertices has
three edges. So by Theorem 10.1.1, the tree has a total
degree of six.
Also, every non-trivial tree has at least two vertices of
degree 1.
19
Trees Rooted Trees Spanning trees and Shortest Paths
Characterizing Trees
Example: Find all non-isomorphic trees with four
vertices.
The only possible combinations of degrees for the
vertices: and
20
Trees Rooted Trees Spanning trees and Shortest Paths
Characterizing Trees
Lemma 10.5.3
If G is any connected graph, C is any circuit in G, and one of the
edges of C is removed from G, then the graph that remains is still
connected.
Essentially, the reason why Lemma 10.5.3 is true is that
any two vertices in a circuit are connected by two
distinct paths.
It is possible to draw the graph so that one of these goes
“clockwise” and the other goes “counter-clockwise”
around the circuit.
21
Trees Rooted Trees Spanning trees and Shortest Paths
Characterizing Trees
For example, in the circuit shown below:
The clockwise path from v2 to v3 is
v2 e3 v3
and the counter-clockwise path from v2 to v3 is
v2 e2 v1 e1 v0 e6 v5 e5 v4 e4 v3
22
Trees Rooted Trees Spanning trees and Shortest Paths
Characterizing Trees
Theorem 10.5.4
If G is a connected graph with n vertices and n – 1 edges, then G
is a tree.
Proof:
1. Suppose G is a particular but arbitrarily chosen graph that is
connected and n vertices and n – 1 edges.
2. Since G is connected, it suffices to show that G is circuit-free.
3. Suppose G is not circuit free
1. Let C be the circuit in G.
2. By Lemma 10.5.3, an edge of C can be removed from G to obtain a
graph G' that is connected.
3. If G' has a circuit, then repeat this process: Remove an edge of the
circuit from G' to form a new connected graph.
4. Continue the process of removing edges from the circuits until
eventually a graph G'' is obtained that is connected and is circuit-free2.0
Trees Rooted Trees Spanning trees and Shortest Paths
Characterizing Trees
Proof: (continued…)
4. Continue the process of removing edges from the circuits until
eventually a graph G'' is obtained that is connected and is circuit-free.
5. By definition, G'' is a tree.
6. Since no vertices were removed from G to form G'', G'' has n vertices.
7. Thus, by Theorem 10.5.2, G'' has n – 1 edges.
8. But the supposition that G has a circuit implies that at least one edge
of G is removed to form G''.
9. Hence G'' has no more than (n – 1) – 1 = n – 2 edges, which contradicts
its having n – 1 edges.
10. So the supposition is false.
4. Hence G is circuit-free, and therefore G is a tree.
24
Trees Rooted Trees Spanning trees and Shortest Paths
Characterizing Trees
Note that although it is true that every connected graph with n
vertices and n – 1 edges is a tree, it is not true that every graph
with n vertices and n – 1 edges is a tree.
Example: Give an example of a graph with five vertices and four
edges that is not a tree.
By Theorem 10.5.4, such a graph cannot be connected. One
example of such an unconnected graph is shown below.
25
10.6 Rooted Trees
Trees Rooted Trees Spanning trees and Shortest Paths
Definitions
A rooted tree is a tree in which one vertex has been
distinguished from the others and is designated the root.
Definitions: Rooted Tree, Level, Height
A rooted tree is a tree in which there is one vertex that is
distinguished from the others and is called the root.
The level of a vertex is the number of edges along the unique
path between it and the root.
The height of a rooted tree is the maximum level of any vertex
of the tree.
27
Trees Rooted Trees Spanning trees and Shortest Paths
Definitions
Definitions: Child, Parent, Sibling, Ancestor, Descendant
Given the root or any internal vertex v of a rooted tree, the
children of v are all those vertices that are adjacent to v and are
one level farther away from the root than v.
If w is a child of v, then v is called the parent of w, and two
distinct vertices that are both children of the same parent are
called siblings.
Given two distinct vertices v and w, if v lies on the unique path
between w and the root, then v is an ancestor of w, and w is a
descendant of v.
28
Trees Rooted Trees Spanning trees and Shortest Paths
Definitions
Figure 10.6.1 A Rooted Tree
29
Trees Rooted Trees Spanning trees and Shortest Paths
Example
Example: Consider the tree with root v0 shown below.
a. What is the level of v5? 2
b. What is the level of v0? 0
c. What is the height of this rooted
tree?
d. What are the children of v3?
e. What is the parent of v2?
f. What are the siblings of v8?
g. What are the descendant of v3?
27
Trees Rooted Trees Spanning trees and Shortest Paths
Binary Trees
Binary Trees
Definitions: Binary Tree, Full Binary Tree
A binary tree is a rooted tree in which every parent has at most
two children. Each child is designated either a left child or a
right child (but not both), and every parent has at most one left
child and one right child.
A full binary tree is a binary tree in which each parent has
exactly two children.
31
Trees Rooted Trees Spanning trees and Shortest Paths
Binary Trees
Binary Trees
Definitions: Left Subtree, Right Subtree
Given any parent v in a binary tree T, if v has a left child, then
the left subtree of v is the binary tree whose root is the left
child of v, whose vertices consist of the left child of v and all its
descendants, and whose edges consist of all those edges of T
that connect the vertices of the left subtree.
The right subtree of v is defined analogously.
32
Trees Rooted Trees Spanning trees and Shortest Paths
Binary Trees
Binary Trees
Figure 10.6.2 A Binary Tree
33
Trees Rooted Trees Spanning trees and Shortest Paths
Example – Representation of Algebraic Expressions
Example – Representation of Algebraic Expressions
Binary trees are used in many ways in computer
science. One use is to represent algebraic expressions
with arbitrary nesting of balanced parentheses.
For instance, the following (labeled) binary tree
represents the expression a/b: The operator is at the
root and acts on the left and right children of the root
in left-right order.
34
Trees Rooted Trees Spanning trees and Shortest Paths
Example – Representation of Algebraic Expressions
More generally, the binary tree shown below
represents the expression a/(c + d). In such a
representation, the internal vertices are arithmetic
operators, the terminal vertices are variables, and the
operator at each vertex acts on its left and right
subtrees in left-right order.
35
Trees Rooted Trees Spanning trees and Shortest Paths
Example – Representation of Algebraic Expressions
Draw a binary tree to represent the expression
((a – b) * c) + (d/e).
36
Trees Rooted Trees Spanning trees and Shortest Paths
Full Binary Tree
An interesting theorem about binary trees says that if
you know the number of internal vertices of a full
binary tree, then you can calculate both the total
number of vertices and the number of terminal
vertices (leaves), and conversely.
Theorem 10.6.1: Full Binary Tree Theorem
If T is a full binary tree with k internal vertices, then T has a total
of 2k + 1 vertices and has k + 1 terminal vertices (leaves).
37
Trees Rooted Trees Spanning trees and Shortest Paths
Full Binary Tree
Proof:
1. Every vertex, except the root, has a parent.
2. Since every internal vertex of a full binary tree has exactly
two children, the number of vertices that have a parent is
twice the number of parents, or 2k.
#vertices of T = #vertices that have a parent +
#vertices that do not have a parent
= 2k + 1
3. #terminal vertices = #vertices – #internal vertices
= 2k + 1 – k = k + 1
4. Therefore T has a total of 2k + 1 vertices and has k + 1
terminal vertices.
38
Trees Rooted Trees Spanning trees and Shortest Paths
Full Binary Tree
Q: Is there a full binary tree that has 10 internal
vertices and 13 terminal vertices?
No, by Theorem 10.6.1, a full binary tree with 10
internal vertices has 10 + 1 = 11 terminal vertices.
39
Trees Rooted Trees Spanning trees and Shortest Paths
Height and Terminal Vertices of a Binary Tree
Height and Terminal Vertices of a Binary Tree
Theorem 10.6.2
For non-negative integers h, if T is any binary tree with height h
and t terminal vertices (leaves), then
t 2h
Equivalently,
log2 t h
This theorem says that the maximum number of
terminal vertices (leaves) of a binary tree of height h
is 2h. Alternatively, a binary tree with t terminal
vertices (leaves) has height of at least log2t.
40
Trees Rooted Trees Spanning trees and Shortest Paths
Height and Terminal Vertices of a Binary Tree
Proof: By mathematical induction
1. Let P(h) be “If T is any binary tree of height h, then the
number of leaves of T is at most 2h.
2. P(0): T consists of one vertex, which is a terminal vertex.
Hence t = 1 = 20.
3. Show that for all integers k 0, if P(i) is true for all integers i
from 0 through k, then P(k+1) is true.
4. Let T be a binary tree of height k + 1, root v, and t leaves.
5. Since k 0, hence k + 1 1 and so v has at least one child.
6. We consider two cases: If v has only one child, or if v has two
children.
41
Trees Rooted Trees Spanning trees and Shortest Paths
Height and Terminal Vertices of a Binary Tree
Proof: (continued…)
Case 1 (v has only one child):
v
Level 0
vL
Level 1
Level 2
Level 3
Left subtree TL
42
Trees Rooted Trees Spanning trees and Shortest Paths
Height and Terminal Vertices of a Binary Tree
Proof: (continued…)
7. Case 1 (v has only one child):
1. Without loss of generality, assume that v’s child is a left child
and denote it by vL. Let TL be the left subtree of v.
2. Because v has only one child, v is a leaf, so the total number of
leaves in T equals the number of leaves in TL + 1. Thus, if tL is
the number of leaves in TL , then t = tL + 1.
3. By inductive hypothesis, tL 2k because the height of TL is k,
one less than the height of T.
4. Also, because v has a child, k+1 1 and so 2k 20 = 1.
5. Therefore,
t = tL + 1 2k + 1 2k + 2k = 2k+1
43
Trees Rooted Trees Spanning trees and Shortest Paths
Height and Terminal Vertices of a Binary Tree
Proof: (continued…)
Case 2 (v has two children):
v
Level 0
vL
Level 1
vR
Level 2
Level 3
Level 4
Left subtree TL Right subtree TR
44
Trees Rooted Trees Spanning trees and Shortest Paths
Height and Terminal Vertices of a Binary Tree
Proof: (continued…)
8. Case 2 (v has two children):
1. Now v has a left child vL and a right child vR , and they are the
roots of a left subtree TL and a right subtree TR respectively.
2. Let hL and hR be the heights of TL and TR respectively.
3. Then hL k and hR k since T is obtained by joining TL and TR
and adding a level.
4. Let tL and tR be the number of leaves of TL and TR respectively.
5. Then, since both TL and TR have heights less than k + 1, by
inductive hypothesis, tL 2hL and tR 2hR.
6. Therefore,
t = tL + tR 2hL + 2hR 2k + 2k 2k+1
9. We proved both cases that P(k+1) is true.
10. Hence if T is any binary tree with height h and t terminal vertices
(leaves), then t 2h. 42
Trees Rooted Trees Spanning trees and Shortest Paths
Height and Terminal Vertices of a Binary Tree
Q: Is there a binary tree that has height 5 and 38
terminal vertices?
No, by Theorem 10.6.2, any binary tree T with height
5 has at most 25 = 32 terminal vertices, so such a
tree cannot have 38 terminal vertices.
46
Trees Rooted Trees Spanning trees and Shortest Paths
Binary Tree Traversal
Binary Tree Traversal
Tree traversal (also known as tree search) is the
process of visiting each node in a tree data structure
exactly once in a systematic manner.
There are two types of traversal: breadth-first search
(BFS) or depth-first search (DFS).
The following sections describe BFS and DFS on binary
trees, but in general they can be applied on any type
of trees, or even graphs.
47
Trees Rooted Trees Spanning trees and Shortest Paths
Binary Tree Traversal
Breadth-First Search
In breadth-first search (by E.F. Moore), it starts at the
root and visits its adjacent vertices, and then moves
to the next level.
1
The figure shows the
order of the vertices 2 3
visited.
4 5 6
7 8 9
48
Trees Rooted Trees Spanning trees and Shortest Paths
Binary Tree Traversal
Breadth-First Search
The figure on the left shows a graph representing
cities in Germany. The figure on the right shows the
breadth-first traversal on the graph.
Acknowledgement: Wikipedia https://en.wikipedia.org/wiki/Breadth-first_search 49
Trees Rooted Trees Spanning trees and Shortest Paths
Binary Tree Traversal
Depth-First Search
There are three types of depth-first traversal:
Pre-order
Print the data of the root (or current vertex)
Traverse the left subtree by recursively calling the pre-order function
Traverse the right subtree by recursively calling the pre-order function
In-order
Traverse the left subtree by recursively calling the in-order function
Print the data of the root (or current vertex)
Traverse the right subtree by recursively calling the in-order function
Post-order
Traverse the left subtree by recursively calling the post-order function
Traverse the right subtree by recursively calling the post-order function
Print the data of the root (or current vertex)
47
Trees Rooted Trees Spanning trees and Shortest Paths
Binary Tree Traversal
Depth-First Search
Pre-order: In-order: Post-order:
F, B, A, D, C, E, G, I, H
Acknowledgement: Wikipedia https://en.wikipedia.org/wiki/Tree_traversal 48
10.7 Spanning Trees and
Shortest Paths
Trees Rooted Trees Spanning trees and Shortest Paths
Definitions
An East Coast airline company wants to expand service to the
Midwest and has received permission from the Federal
Aviation Authority to fly any of the routes shown in
Figure 10.7.1.
Figure 10.7.1
53
Trees Rooted Trees Spanning trees and Shortest Paths
Definitions
The company wishes to legitimately advertise service to all the cities shown
but, for reasons of economy, wants to use the least possible number of
individual routes to connect them. One possible route system is given in
Figure 10.7.2, where the chosen routes are in red.
Figure 10.7.1 Figure 10.7.2
54
Trees Rooted Trees Spanning trees and Shortest Paths
Definitions
Lemma 10.5.3
Is the number of individual If G is any connected graph, C is any
routes minimal? circuit in G, and one of the edges of
C is removed from G, then the graph
The fact is that the graph of any that remains is still connected.
system of routes that satisfies
the company’s wishes is a tree,
because if the graph were to
contain a circuit, then one of
the routes in the circuit could
be removed without
disconnecting the graph (by
Lemma 10.5.3), and that would
give a smaller total number of
routes. Figure 10.7.2
55
Trees Rooted Trees Spanning trees and Shortest Paths
Definitions
What you have seen is a spanning tree.
Definition: Spanning Tree
A spanning tree for a graph G is a subgraph of G that contains
every vertex of G and is a tree.
Proposition 10.7.1
1. Every connected graph has a spanning tree.
2. Any two spanning trees for a graph have the same
number of edges.
56
Trees Rooted Trees Spanning trees and Shortest Paths
Definitions
Example: Find all spanning trees for the graph G below.
The graph G has one circuit v2v1v4v2 and removal of any edge
of the circuit gives a tree. Hence there are three spanning
trees for G.
57
Trees Rooted Trees Spanning trees and Shortest Paths
Minimum Spanning Trees
Minimum Spanning Trees
The graph of the routes allowed by the Federal Aviation
Authority shown in Figure 10.7.1 can be annotated by adding the
distances (in miles) between each pair of cities.
Now suppose the airline
company wants to serve all the
cities shown, but with a route
system that minimizes the total
mileage.
Figure 10.7.3
58
Trees Rooted Trees Spanning trees and Shortest Paths
Minimum Spanning Trees
Minimum Spanning Trees
Definitions: Weighted Graph, Minimum Spanning Tree
A weighted graph is a graph for which each edge has an
associated positive real number weight . The sum of the
weights of all the edges is the total weight of the graph.
A minimum spanning tree for a connected weighted graph is a
spanning tree that has the least possible total weight compared
to all other spanning trees for the graph.
If G is a weighted graph and e is an edge of G, then w(e)
denotes the weight of e and w(G) denotes the total weight of G.
59
Trees Rooted Trees Spanning trees and Shortest Paths
Kruskal’s Algorithm
Kruskal’s Algorithm (Joseph B. Kruskal, 1956)
In Kruskal’s algorithm, the edges of a connected
weighted graph are examined one by one in order of
increasing weight.
At each stage the edge being examined is added to
what will become the minimum spanning tree,
provided that this addition does not create a circuit.
After n – 1 edges have been added (where n is the
number of vertices of the graph), these edges, together
with the vertices of the graph, form a minimum
spanning tree for the graph.
60
Trees Rooted Trees Spanning trees and Shortest Paths
Kruskal’s Algorithm
Algorithm 10.7.1 Kruskal
Input: G [a connected weighted graph with n vertices]
Algorithm:
1. Initialize T to have all the vertices of G and no edges.
2. Let E be the set of all edges of G, and let m = 0.
3. While (m < n – 1)
3a. Find an edge e in E of least weight.
3b. Delete e from E.
3c. If addition of e to the edge set of T does not produce a
circuit, then add e to the edge set of T and set m = m + 1
End while
Output: T [T is a minimum spanning tree for G.]
61
Trees Rooted Trees Spanning trees and Shortest Paths
Kruskal’s Algorithm
Example: Describe the action of Kruskal’s algorithm on the graph
shown in Figure 10.7.4, where n = 8.
Figure 10.7.4
62
Trees Rooted Trees Spanning trees and Shortest Paths
Kruskal’s Algorithm
Using Kruskal’s algorithm we can formulate the following table.
Edge considered Wt Action taken
1 Chi – Mil 74 added
2 Lou – Cin 83 added
3 Lou – Nas 151 added
4 Cin – Det 230 added
5 StL – Lou 242 added
6 StL – Chi 262 added
7 Chi – Lou 269 not added
8 Lou – Det 306 not added
Figure 10.7.4
9 Lou – Mil 348 not added
10 Min – Chi 355 added
63
Trees Rooted Trees Spanning trees and Shortest Paths
Kruskal’s Algorithm
When Kruskal’s algorithm is used on a graph in which some
edges have the same weight as others, more than one minimum
spanning tree can occur as output.
To make the output unique, the edges of the graph can be
placed in an array and edges having the same weight can be
added in the order they appear in the array.
64
Trees Rooted Trees Spanning trees and Shortest Paths
Prim’s Algorithm
Prim’s Algorithm (Robert C. Prim, 1957)
Prim’s algorithm works differently from Kruskal’s. It builds a
minimum spanning tree T by expanding outward in connected
links from some vertex.
One edge and one vertex are added at each stage. The edge
added is the one of least weight that connects the vertices
already in T with those not in T, and the vertex is the endpoint of
this edge that is not already in T.
65
Trees Rooted Trees Spanning trees and Shortest Paths
Prim’s Algorithm
Algorithm 10.7.2 Prim
Input: G [a connected weighted graph with n vertices]
Algorithm:
1. Pick a vertex v of G and let T be the graph with this vertex only.
2. Let V be the set of all vertices of G except v.
3. For i = 1 to n – 1
3a. Find an edge e of G such that (1) e connects T to one of the
vertices in V, and (2) e has the least weight of all edges
connecting T to a vertex in V. Let w be the endpoint of e
that is in V.
3b. Add e and w to the edge and vertex sets of T, and delete w
from V.
Output: T [T is a minimum spanning tree for G.]
66
Trees Rooted Trees Spanning trees and Shortest Paths
Prim’s Algorithm
Example: Describe the action of Prim’s algorithm on the graph shown in
Figure 10.7.6, using the Minneapolis vertex as a starting point.
Figure 10.7.6
67
Trees Rooted Trees Spanning trees and Shortest Paths
Prim’s Algorithm
Using Prim’s algorithm we can formulate the following table.
Vertex added Edge added Weight
0 Minneapolis
1 Chicago Min – Chi 355
2 Milwaukee Chi – Mil 74
3 St. Louis Chi – StL 262
4 Louisville StL – Lou 242
5 Cincinnati Lou – Cin 83
6 Nashville Lou – Nas 151
7 Detroit Cin – Det 230
Figure 10.7.6
68
Trees Rooted Trees Spanning trees and Shortest Paths
Prim’s Algorithm
Note that the tree obtained is the same as that obtained by
Kruskal’s algorithm, but the edges are added in a different order.
As with Kruskal’s algorithm, in order to ensure a unique output,
the edges of the graph could be placed in an array and those
with the same weight could be added in the order they appear in
the array.
69
Trees Rooted Trees Spanning trees and Shortest Paths
Dijkstra’s Shortest Path Algorithm
Dijkstra’s Shortest Path Algorithm
In 1959, Edsgar Dijkstra developed an algorithm to find
the shortest path between a starting vertex (source) and
an ending vertex (destination) in a weighted graph in
which all weights are positive.
Somewhat similar to Prim’s algorithms, it works outward
from the source a, adding vertices and edges one by one
to construct a shortest path tree T. It differs from Prim’s
algorithm in the way it chooses the next vertex to add,
ensuring that for each added vertex v, the length of the
shortest path from a to v has been identified.
70
Trees Rooted Trees Spanning trees and Shortest Paths
Dijkstra’s Shortest Path Algorithm
Intuition behind Dijkstra’s algorithm:
Report the vertices in increasing order of their distance from
the source vertex.
Construct the shortest path tree edge by edge; at each step
adding one new edge, corresponding to construction of
shortest path to the current new vertex.
Example: To find shortest part from vertex a to vertex z.
1
71
Trees Rooted Trees Spanning trees and Shortest Paths
Dijkstra’s Shortest Path Algorithm
At the start, assign every vertex u a label L(u), which is
the current best estimate of the length of the shortest
path from a to u.
L(a) is set to 0.
0
1
L(u) of each vertex u
other than a is set to .
72
Trees Rooted Trees Spanning trees and Shortest Paths
Dijkstra’s Shortest Path Algorithm
As the algorithm progresses, the values of L(u) are
updated, eventually becoming the actual lengths of the
shortest paths from a to u.
We construct the shortest path tree T outward from a.
At each stage of the algorithm, the only vertices that
are candidates to join T are those that are adjacent to
at least one vertex of T. We call these candidates the
set of “fringe” vertices.
The graph G can be thought of as divided into 3 parts:
the tree T that is being built up, the set of “fringe”
vertices, and the rest of the vertices in G.
73
Trees Rooted Trees Spanning trees and Shortest Paths
Dijkstra’s Shortest Path Algorithm
The rest of
a the vertices
Each fringe vertex is a
Shortest “Fringe” candidate to be the next
path tree T vertices vertex added to T.
All vertices in T The one that is chosen is the one for which
already have their the length of the shortest path to it from a
final L(u) value through T is a minimum among all the
computed. vertices in the fringe.
74
Trees Rooted Trees Spanning trees and Shortest Paths
Dijkstra’s Shortest Path Algorithm
If L(v) + w(v, u) < L(u),
then the value of L(u) is
changed to L(v) + w(v, u).
After each addition of a vertex v to T, each fringe vertex u
adjacent to v is examined and two numbers are
compared: the current value of L(u) and the value of
L(v) + w(v, u), where L(v) is the length of the shortest path
to v (in T) and w(v, u) is the weight of the edge joining v
and u.
75
Trees Rooted Trees Spanning trees and Shortest Paths
Dijkstra’s Shortest Path Algorithm
Algorithm 10.7.3 Dijkstra
Input: G [a connected simple graph with positive weight
for every edge], [a number greater than the sum of the
weights of all the edges in G], w(u, v) [the weight of edge
{u, v}], a [the source vertex], z [the destination vertex].
Algorithm:
1. Initialize T to be the graph with vertex a and no edges.
Let V(T) be the set of vertices of T, and let E(T) be the set of
edges of T.
2. Let L(a) = 0, and for all vertices in G except a, let L(u) = .
[The number L(x) is called the label of x.]
3. Initialize v to equal a and F to be {a}. [The symbol v is used to
denote the vertex most recently added to T.]
73
Trees Rooted Trees Spanning trees and Shortest Paths
Dijkstra’s Shortest Path Algorithm
Algorithm 10.7.3 Dijkstra (continued…)
Let Adj(x) denote the set of vertices adjacent to vertex x.
4. while (z V(T))
a. F (F – {v}) {vertices Adj(v) and V(T)}
[The set F is the set of fringe vertices.]
b. For each vertex u Adj(v) and V(T), [The notation D(u) is
if L(v) + w(v, u) < L(u) then introduced to keep track
L(u) L(v) + w(v, u) of which vertex in T gave
rise to the smaller value.]
D(u) v
c. Find a vertex x in F with the smallest label.
Add vertex x to V(T), and add edge {D(x), x} to E(T).
vx
Output: L(z) [this is the length of the shortest path from a to z.]
77
Trees Rooted Trees Spanning trees and Shortest Paths
Dijkstra’s Shortest Path Algorithm
Example: Show the steps in the execution of Dijkstra’s
shortest path algorithm for the graph shown below
with starting vertex a and ending vertex z.
78
Trees Rooted Trees Spanning trees and Shortest Paths
Dijkstra’s Shortest Path Algorithm
3
Step 1: Going into the while loop:
0
V(T) = {a}, E(T) = Ø, and F = {a}
1
During iteration:
F = {b, c}, L(b) = 3, L(c) = 4.
Since L(b) < L(c), b is added to V(T) and {a, b} is added
to E(T).
79
Trees Rooted Trees Spanning trees and Shortest Paths
Dijkstra’s Shortest Path Algorithm
3
Step 2: Going into the while loop:
0
V(T) = {a, b}, E(T) = {{a, b}}
4 1
During iteration:
F = {c, d, e}, L(c) = 4, L(d) = 9, L(e) = 8.
Since L(c) < L(d) and L(c) < L(e), c is added to V(T) and
{a, c} is added to E(T).
80
Trees Rooted Trees Spanning trees and Shortest Paths
Dijkstra’s Shortest Path Algorithm
3
Step 3: Going into the while loop:
0
V(T) = {a, b, c},
E(T) = {{a, b}, {a, c}}
4 1
5
During iteration:
F = {d, e}, L(d) = 9, L(e) = 5.
L(e) becomes 5 because ace, which has length 5, is a
shorter path to e than abe, which has length 8. Since
L(e) < L(d), e is added to V(T) and {c, e} is added to E(T).
81
Trees Rooted Trees Spanning trees and Shortest Paths
Dijkstra’s Shortest Path Algorithm
3 7
Step 4: Going into the while loop:
0
V(T) = {a, b, c, e},
E(T) = {{a, b}, {a, c}, {c, e}}
4 1 5
During iteration:
F = {d, z}, L(d) = 7, L(z) = 17.
L(d) becomes 7 because aced, which has length 7, is a
shorter path to d than abd, which has length 9. Since
L(d) < L(z), d is added to V(T) and {e, d} is added to E(T).
82
Trees Rooted Trees Spanning trees and Shortest Paths
Dijkstra’s Shortest Path Algorithm
3 7
Step 5: Going into the while loop:
0
V(T) = {a, b, c, e , d},
14
E(T) = {{a, b}, {a, c}, {c, e}, {e, d}}
4 1 5
During iteration:
F = {z}, L(z) = 14.
L(z) becomes 14 because acedz, which has length 14, is
a shorter path to z than acez, which has length 17.
Since z is the only vertex in F, its label is a minimum,
and so z is added to V(T) and {d, z} is added to E(T).
Algorithm terminates at this point because z V(T).
The shortest path from a to z has length L(z) = 14.
83
Trees Rooted Trees Spanning trees and Shortest Paths
Dijkstra’s Shortest Path Algorithm
Keeping track of the steps in a table is a convenient way
to show the action of Dijkstra’s algorithm. Table 10.7.1
does this for the graph in the previous example.
{d, z}}
Table 10.7.1
84
You might also like
- Lecture02 LogicOfCompoundStatements FullNo ratings yetLecture02 LogicOfCompoundStatements Full81 pages
- Chapter 2 Fundamentals of Logic: Dept of Information Management National Central University Yen-Liang ChenNo ratings yetChapter 2 Fundamentals of Logic: Dept of Information Management National Central University Yen-Liang Chen64 pages
- w1,2 - Ch01-1 Propositional Logic - PrintNo ratings yetw1,2 - Ch01-1 Propositional Logic - Print51 pages
- Lecture02 LogicOfCompoundStatements SummaryNo ratings yetLecture02 LogicOfCompoundStatements Summary12 pages
- Propositional Logic Concepts and ExercisesNo ratings yetPropositional Logic Concepts and Exercises41 pages
- Logic Statements and Truth Values ExplainedNo ratings yetLogic Statements and Truth Values Explained17 pages
- Understanding Statements and Truth TablesNo ratings yetUnderstanding Statements and Truth Tables20 pages
- 4.5A Exercise Logicola GHV: Prove Each of These Arguments To Be Valid (All Are Valid)No ratings yet4.5A Exercise Logicola GHV: Prove Each of These Arguments To Be Valid (All Are Valid)10 pages
- Modality Central Problems of Philosophy PDF100% (1)Modality Central Problems of Philosophy PDF199 pages
- Teaching Levels and Research Ethics QuizNo ratings yetTeaching Levels and Research Ethics Quiz74 pages
- Test Bank For An Introduction To Moral Philosophy 1st EditionNo ratings yetTest Bank For An Introduction To Moral Philosophy 1st Edition12 pages
- Judge The Validity of The Evidence Listened ToNo ratings yetJudge The Validity of The Evidence Listened To17 pages
- Understanding Syllogism: Definitions & ExamplesNo ratings yetUnderstanding Syllogism: Definitions & Examples14 pages
- Math for Social Sciences Course OutlineNo ratings yetMath for Social Sciences Course Outline44 pages
