Transcript Chapter 5 - Set Theory

5.1.1
Chapter 5 - Set Theory
1. Basic Definitions
2. Empty Set, Partitions, Power Set
3. Properties of Sets
5.1.2
Section 1. Basic Definitions
•
•
•
•
A Set is a collection of items, called elements.
{1, 2, 3}
{x  R | x2 > 5}
S = {Tom, Sue, Jim}
5.1.3
•
•
•
•
•
We use ellipses to simplify things:
{1, 2, 3, …, 10}
{1, 2, 3, …}
{…, -2, -1, 0, 1, 2, …}
Be careful! ({1, 2, …}???)
5.1.4
• We relate an item in the set with the set
using the “(element of)” relation.
• x  {x, y, z}
• {1, 2}  {{1, 2}, {1, 2, 3}}.
5.1.5
Special Sets
• We refer to specific sets of numbers so often
that we give them special names.
• These sets, and their corresponding
symbols, will be referenced throughout this
course.
5.1.6
Natural Numbers
• We define the Natural Numbers to be:
N = {0, 1, 2, 3, …}
• Note that the Naturals are “closed” under
addition and multiplication.
5.1.7
The Integers
• We define the Integers to be:
Z = {…, -2, -1, 0, 1, 2, 3, …}
• Note that Z is “closed” under addition,
subtraction, and multiplication.
5.1.8
The Rational Numbers
• We define the Rationals to be:
Q = {p/q | p,q  Z and q  0}
• Note that Q is “closed” under addition,
subtraction, multiplication, and non-zero
division.
5.1.9
The Rational Numbers
• Alternatively, we can view Q as the set of
all infinite, repeating decimal expansions.
• 7.35 = 7.3500000…  Q
• 1.234234234…  Q
• However, p  Q
5.1.10
The Irrational Numbers
• I = {all infinite, nonrepeating decimals}
• Obviously, irrational numbers are
impossible to write down exactly.
• We use symbols to represent special values
such as p, e, and 2.
• The Irrationals are not closed under + or .
5.1.11
The Real Numbers
• R = {all decimal expansions}
• The Real Numbers are created by adjoining
the Rationals with the Irrationals.
• The Reals are closed under all operations
and satisfy the Field Axioms (see Appendix
A, p. 695).
• The Reals form a continuum: we use the
Real Number Line to represent this.
5.1.12
The Complex Numbers
• The Reals fall short when solving simple
polynomial equations like x2 + 1 = 0.
• The Complex Numbers patch this hole.
• C = {a + bi | a,b  R and i =  (-1)}
• Use the Complex Plane to represent these
numbers.
• The Complex Numbers are also a field.
5.1.13
Subsets
• If A and B are sets, A is called a subset of B,
denoted A  B, provided every element of A
is an element of B.
• So, A B means "x, if x  A, then x  B.
• We also say, “A is contained in B” or
“B contains A” to show this relationship.
• Equivalently, we denote A  B provided
$x ' x  A and x  B.
5.1.14
Examples of Subsets
• If A = {1, 2, 3} and B = {0, 1, 2, 3, 4}, then
clearly A B.
• {{1}, {2}} {{1}, {2}, {1,2}}.
•
•
•
•
Q R and Z Q and N Z.
{a, b, c} is a proper subset of {a, b, c, d}.
{a, b, c} is an improper subset of {a, b, c}.
We denote interval subsets of R as
[a, b) = {x  R | a  x < b}. So [2, 5)  [0,5].
5.1.15
Set Equality
• We say sets A and B are equal (A = B) if
every element of A is in B and every element
of B is in A.
• Thus, A = B means A B and B A.
• For example {1, 2, 3} = {1, 2, 3}, but
A = {1, 2, 3}  {1, 2, 3, 4} = B, since 4  B
but 4  A.
• Also, [a, b)  [a, b] since b is only in [a, b].
5.1.16
Operations on Sets
• Given sets A and B, which are subsets of a
universal set, U, we define the following:
• (Union) A  B = {x  U | x  A or x  B}.
• (Intersection) A  B = {x  U | x  A and x  B}.
• (Difference or Relative Complement)
A - B = {x  U | x  A and x  B}.
• (Complement) Ac = {x  U | x  A}.
• Note that Ac = U - A.
5.1.17
Examples of Set Operations
•
•
•
•
•
•
•
Let U = R, A = [1, 3] and B = (2, 4).
A  B = [1, 4)
A  B = (2, 3]
A - B = [1, 2]
B - A = (3, 4)
Ac = (-, 1)  (3, )
Bc = (-, 2]  [4, )
5.1.18
Cartesian Products
• Given two sets, A and B, we define the Cartesian
Product, A  B = {(a, b) | a  A and b  B}.
• The element (a, b) is called an ordered pair, since
(a, b) and (b, a) are distinct if a  b.
• If A = {1, 2, 3} and B = {8, 9}, then:
A  B = {(1, 8), (1, 9), (2, 8), (2, 9), (3, 8), (3, 9)}
B  A = {(8, 1), (8, 2), (8, 3), (9, 1), (9, 2), (9, 3)}
5.1.19
Generalized Cartesian Products
• Given three sets, A, B, and C, we define their
Cartesian Product by
A  B  C = {(a, b, c) | a  A, b  B and c  C}.
• Although similar, we note that A  B  C and
(A  B)  C are not, technically, the same since
one contains (a, b, c) and the other ((a, b), c).
• In general, we define A1A2A3...An to be
{(a1,a2,a3,…,an) | a1A1,a2A2,a3A3,…, anAn}
5.1.20
Formal Languages
• Let S be a finite set, which we will, henceforth,
call an alphabet.
• A string of characters of the alphabet S (or a
string over S ) is either: (1) an ordered n-tuple of
elements of S written without parentheses or
commas, or (2) the null string e, which has no
characters.
5.1.21
Formal Languages (cont’d.)
• If S ={1,2,3}, then 131221 is a string of length
6 over S.
• 131221 (1, 3, 1, 2, 2, 1)  SSSSSS.
• Clearly, the length of a string, s, over an alphabet
S, is the number of characters of S that are in s.
• We denote the function L(s) to be this length.
• Hence, if S = {0, 1}, then L(101100111) = 9.
5.1.22
Formal Languages (cont’d.)
• Any set of strings over an alphabet is called a
formal language over the alphabet.
• Let S be an alphabet and n  N :
Sn = {strings over S with L(s) = n};
Gn = {strings over S with L(s)  n};
S* = {strings over S of finite length}.
5.1.23
Examples
Let S = {0, 1}:
S3 = {000, 001, 010, 011, 100, 101, 110, 111}
G3 = {e, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011,
100, 101, 110, 111}
S* = {e, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011,
100, 101, 110, 111, …, 000000, …, 111111, ...}.
5.3.24
Section 5.3
•
•
•
•
The Empty Set
Partitions
Power Sets
Boolean Algebras
5.3.25
The Empty Set
• The unique set containing no elements is
called the empty set, denoted  or {}.
• Theorem: If A is a set, then A.
• Corollary: is unique.
• Why? Since 1 2 and 2 1 we
conclude 1 = 2 .
5.3.26
Set Operations With 
• For any set A from a universal set U:
A  = 
A  = A
A  Ac = 
A  Ac = U
Uc = and c = U.
5.3.27
Partitions of a Set
• Two sets are called disjoint if they have
no elements in common. That is, A and
B are disjoint provided A  B = .
• Theorem: If A and B are any sets, then (A
- B) and B are disjoint.
• A collection of sets {A1,A2,…,An} is
called mutually or pairwise disjoint if
Ai  Aj =  whenever i  j.
5.3.28
Partitions of a Set (cont’d.)
• A collection of sets {A1,A2,…,An} is
called a partition of a set A provided:
1. {A1,A2,…,An} is mutually disjoint;
2. A1  A2  ...  An = A.
• {{1, 2, 3},{4, 5},{6, 7, 8}} partitions?
• {{1,2,3,...},{-1,-2,-3,...},{0}} partitions?
• {Q, I} partitions?
5.3.29
Power Sets
• If A is a set, the Power Set of A, denoted
P (A), is the set of all subsets of A.
• Since A, we conclude P (A),
and A A implies A  P (A).
• If A = {0,1}, P (A) = {,{0},{1},{0,1}}
• Theorem: If A and B are sets with A  B,
then P (A)  P (B).
• Theorem: If |A| = n, then | P (A) | = 2n.
5.3.30
Boolean Algebras
• If A is a set, the collection {A, +, } is called
a Boolean Algebra if:
1. "a,bA, a + b = b + a and a  b = b  a
2. "a,b,cA, (a + b) + c = a + (b + c)
and (a  b)  c = a  (b  c)
3. "a,b,cA, a + (b  c) = (a + b)  (a + c)
and a  (b + c) = (a  b) + (a  c)
4. $! 0,1A ' "aA, a + 0 = a and a  1 = a
5. "aA, $ bA ' a + b = 1 and a  b = 0
1.1.31
Chapter 1. Symbolic Logic
•
•
•
•
Logical Form and Equivalence
Conditional Statements
Valid and Invalid Arguments
Digital Logic Circuits (Boolean Polynomials)
1.1.32
Logic of Compound Statements
• A statement (or proposition) is a sentence that is
true (T) or false (F), but not both or neither.
• Examples:
Today is Monday.
x is even and x > 7.
If x2 = 4, then x = 2 or x = -2.
1.1.33
Counterexamples
• If a sentence cannot be judged to be T or F or is
not even a sentence, it cannot be a statement.
• Examples:
Open the door! (imperative)
Did you open the door? (interrogative)
If x2 = 4. (fragment)
1.1.34
Compound Statements
• Denote statements using the symbols p, q, r, ...
• Denote the operations ,,~,  (to be defined
shortly), where:
p  q - conjunction of p and q (p and q);
p  q - disjunction of p and q (p or q);
~ p - negation of p (not p);
p  q - implication of p and q (p implies q);
1.1.35
Compound Statements (cont’d.)
• A Compound statement (or statement form) is a
statement which includes at least one operation
and one other “atomic” statement.
• For example, “x = 7 and y = 2” is a compound
statement based on the “atomic” statements
p = “x = 7” and q = “y = 2”.
• In this instance, we can symbolize the compound
statement as r = p  q.
1.1.36
Compound Statements (cont’d.)
• The Truth Table of a compound statement is the
collection of all the output truth values
corresponding to all possible combinations of
input truth values of the atomic statements.
• Since each atomic statement can take on 1 of 2
values, 2 inputs have 4 combinations, 3 inputs
have 8, 4 inputs have 16, 5 inputs have 32, etc.
1.1.37
Logical Operations
• Negation:
p ~p
T F
F T
• Conjunction:
p q (p  q)
T T T
T F
F
F T
F
F F
F
• Disjunction:
p q (p  q)
T T T
T F T
F T T
F F F
Example: (p  q)  ~r
• Proceed from left to right:
p q r (p  q) ~r (p  q)  ~r
T T T
T
F
F
T T F
T
T
T
T F T
T
F
F
T F F
T
T
T
F T T
T
F
F
F T F
T
T
T
F F T
F
F
F
F F F
F
T
F
1.1.38
1.1.39
Logical Equivalence
• Two compound statements are logically
equivalent if they have the same truth table. We
denote this as p  q.
•
p ~p ~(~p)
T F
T
F T
F
hence p  ~(~p).
• ~(p  q)  ~p  ~q ?
No, since ~(T  F)  T, but (~T  ~F)  F.
1.1.40
Tautology & Contradiction
• A statement whose truth table is all “T” is called
a tautology, denoted as p  t.
• A statement whose truth table is all “F” is called
a contradiction, denoted as p  c.
• Clearly, ~t  c and ~c  t.
• Are all logical statements either tautology or
contradiction?
1.1.41
Algebra of Symbolic Logic
• Commutative Laws:
pqqp
pqqp
• Associative Laws:
(p q)  r  p  (q r)
(p q)  r  p  (q r)
• Distributive Laws:
p (q r)  (p q) (p r)
p (q r)  (p q) (p r)
1.1.42
Algebra of Symbolic Logic
• Identity Laws:
ptp
pcp
• Negation Laws:
p  ~p  c
p  ~p  t
• Double Negative Laws: ~(~p)  p
• Negations of t and c:
~t  c
~c  t
1.1.43
Algebra of Symbolic Logic
• Idempotent Laws: p  p  p p  p  p
• DeMorgan’s Laws:
~(p q)  ~p  ~q
~(p q)  ~p  ~q
• Universal Bound Laws: p  c  c
ptt
• Absorption Laws:
p (p q)  p
p (p q)  p
1.2.44
Section 1.2
•
•
•
•
Conditional Statements
Logical Equivalences Involving Conditionals
Converses, Inverses, and Contrapositives
Biconditional Statements
1.2.45
Conditional Statements
• If p and q are statement variables, the conditional
or implication of q by p is “If p then q” or
“p implies q” and is denoted by p  q.
• The truth table of the implication operator is:
p
T
T
F
F
q
T
F
T
F
pq
T
F
T
T
• Example: If you mow my lawn, I’ll pay $20.
1.2.46
Hypotheses & Conclusions
• In the form “If p then q” the statement p is called
the hypothesis and the statement q is the
conclusion.
• Conditionals form the basis of “deductive”
reasoning. (Aristotilean Logic)
• In looking at the truth table, we consider the
cases where the hypothesis is false to yield
vacuous results. The interesting cases are when
the hypothesis is true.
1.2.47
Logical Equivalences
• In the framework of symbolic logic, the
implication operator would seem to be a new and
distinct process.
• However, this is not the case!
• Theorem: p  q  ~p  q.
• Thus, we can always rewrite an implication as a
disjunction.
• Corollary: ~(p  q)  p  ~q.
1.2.48
Negation of a Conditional
• From the previous corollary, the negation of
p  q is p  ~q.
• For example, the negation of
If today is Sunday, then I wash my car.
is:
Today is Sunday and I do not wash my car.
1.2.49
Converse of a Conditional
• Given the statement p  q, we define its
converse to be the statement q  p.
• For example, the converse of
If today is Sunday, then I wash my car.
is:
If I wash my car, then today is Sunday.
1.2.50
Contrapositive of a Conditional
• Given the statement p  q, we define its
contrapositive to be the statement ~q  ~p.
• For example, the contrapositive of
If today is Sunday, then I wash my car.
is:
If I do not wash my car, then today is not Sunday.
1.2.51
Inverse of a Conditional
• Given the statement p  q, we define its inverse
to be the statement ~p  ~q.
• For example, the inverse of
If today is Sunday, then I wash my car.
is:
If today is not Sunday, then I do not wash my car.
1.2.52
Equivalent Forms
• Theorem: Given the statement p  q, we have
that p  q  ~q  ~p.
• Corollary: Given the statement p  q, we have
that q  p  ~p  ~q.
• Therefore from the above, we see that a
conditional and its contrapositive are logically
equivalent.
• Moreover, the statement’s converse and inverse
forms are logically equivalent to each other.
1.2.53
Biconditional Statements
• Definition: Given the statement variables p and
q, the biconditional of p and q is read, “p if and
only if q,” denoted p  q and means that both
p  q and q  p .
• By direct calculation:
p q p q
T T T
T F
F
F T
F
F F
T
1.2.54
Using the Biconditional
• Looking closely at the truth table, we see that
p  q is T whenever p and q have the same truth
value.
• Theorem: p  q is a tautology implies p  q and
conversely, p  q implies p q is a tautology.
• This gives us a systematic way to calculate
logical equivalence, rather then just scan the
matches of truth values by eye.
1.3.55
Section 1.3
•
•
•
•
•
Valid and invalid argument forms.
Special valid argument forms.
Dilemmas
Fallacies.
Contradictions and valid arguments.
1.3.56
Valid and Invalid Arguments
• An argument (or argument form) is a sequence of
statements.
• All statements but the final one are called
premises, assumptions, or hypotheses.
• The final statement is called the conclusion.
• An argument form is valid provided its
conclusion is always true whenever all of its
premises are true.
1.3.57
Valid and Invalid Arguments
• An argument (or argument form) is a sequence of
statements.
• All statements but the final one are called
premises, assumptions, or hypotheses.
• The final statement is called the conclusion.
• An argument form is valid provided its
conclusion is always true whenever all of its
premises are true.
• The truth of the conclusion follows inescapably
from the truth of the hypotheses.
1.3.58
Testing for Validity
• Identify the premises and conclusion.
• Construct a truth table for the premises and
conclusion.
• Find the critical rows, where all premises are T.
• For each critical row, if the conclusion is also T,
then the argument is valid.
• If at least one critical row leads to a conclusion
being F, the argument is invalid.
• If there are no critical rows, the argument is
vacuously valid.
1.3.59
A Valid Argument
Truth Table:
p (q  r)
~r
\ (p  q)
p q r [p (q  r)] ~r (p  q)
TTT
T
F
T
T T FT
T
T
T F TT
F
T
TFF
T
T
T
F T TT
F
T
FTF
T
T
T
FFT
T
F
F
FFF
F
T
F
1.3.60
An Invalid Argument
Truth Table:
p (q  r)
~r
\ (p  r)
p q r [p (q  r)] ~r (p  r)
TTT
T
F
T
T T FT
T
T
T F TT
F
T
TFF
T
T
T
F T TT
F
T
FTF
T
T
F
FFT
T
F
T
FFF
F
T
F
1.3.61
Special Argument Forms
Modus Ponens: p q
p
\q
Truth Table:
p q p q p q
T T
T
T T
T F
F
T F
F T
T
F T
F F
T
F F
Premises: If today is Sunday, then I was my car.
Today is Sunday.
Conclusion: I wash my car.
1.3.62
Modus Tollens
Modus Tollens: p q
~q
\ ~p
Truth Table:
p q p q ~q ~p
T T
T
F F
T F
F
T F
F T
T
F T
F F
T
T T
Premises: If today is Sunday, then I was my car.
I do not wash my car.
Conclusion: Today is not Sunday.
1.3.63
Disjunctive Addition
Disjunctive Addition:
p
\pq
Truth Table:
p q p q
T T
T
T F
T
F T
T
F F
F
Premise: Today is Sunday.
Conclusion: Today is Sunday or I wash my car.
1.3.64
Conjunctive Simplification
pq
\p
also \ q
Truth Table:
p q p q
T T
T
T F
F
F T
F
F F
F
Premise: Today is Sunday and I wash my car.
Conclusion 1: Today is Sunday.
Conclusion 2: I wash my car.
Conjunctive Simplification:
1.3.65
Disjunctive Syllogism
pq
pq
~p
~q
\q
\p
Truth Table:
p q p q ~p
T T
T F
T F
T F
F T
T T
F F
F T
Premises: Today is Sunday or Saturday.
Today is not Sunday.
Conclusion: Today is Saturday.
Disjunctive Syllogism:
1.3.66
Hypothetical Syllogism
pq
qr
\pr
Premises: If x is an integer, then x is a rational.
If x is a rational, then x is a real.
Conclusion: If x is an integer, then x is real.
Hypothetical Syllogism:
1.3.67
Dilemma: Division Into Cases
Dilemma: p  q
pr
qr
\r
Premises: x is positive or x is negative.
If x is positive , then x2 is positive.
If x is negative, then x2 is positive.
Conclusion: x2 is positive.
1.3.68
Application: Find My Glasses
1. If my glasses are on the kitchen table, then I saw them at
breakfast.
2. I was reading in the kitchen or I was reading in the
living room.
3. If I was reading in the living room, then my glasses are
on the coffee table.
4. I did not see my glasses at breakfast.
5. If I was reading in bed, then my glasses are on the bed
table.
6. If I was reading in the kitchen, then my glasses are on
the kitchen table.
1.3.69
Find My Glasses (cont’d.)
Let: p = My glasses are on the kitchen table.
q = I saw my glasses at breakfast.
r = I was reading in the living room.
s = I was reading in the kitchen.
t = My glasses are on the coffee table.
u = I was reading in bed.
v = My glasses are on the bed table.
1.3.70
Find My Glasses (cont’d.)
Then the original statements become:
1. p  q
2. r  s
3. r  t
4. ~q
5. u  v
6. s  p
and we can deduce (why?):
1. p  q 2. s  p 3. r  s 4. r  t
~q
~p
~s
r
\ ~p
\ ~s
\r
\t
Hence the glasses are on the coffee table!
1.3.71
Fallacies
• A fallacy is an error in reasoning that
results in an invalid argument.
• Three common fallacies:
– Using vague or ambiguous premises;
– Begging the question;
– Jumping to a conclusion.
• Two dangerous fallacies:
– Converse error;
– Inverse error.
1.3.72
Converse Error
If Zeke cheats, then he sits in the back row.
Zeke sits in the back row.
\ Zeke cheats.
• The fallacy here is caused by replacing the
impication (Zeke cheats  sits in back)
with its biconditional form (Zeke cheats 
sits in back), implying the converse (sits in
back  Zeke cheats).
1.3.73
Inverse Error
If Zeke cheats, then he sits in the back row.
Zeke does not cheat.
\ Zeke does not sit in the back row.
• The fallacy here is caused by replacing the
impication (Zeke cheats  sits in back)
with its inverse form (Zeke does not cheat
 does not sit in back), instead of the
contrapositive (does not sit in back  Zeke
does not cheat).
1.3.74
Contradiction Rule
• If you can show that assuming statement p
is false leads logically to a contradiction,
then you can conclude that p is true.
• In argument form:
~p  c
\p
• This is the logical heart of the proof method
called Proof by Contradiction.
1.4.75
Section 1.4
•
•
•
•
Digital Logic Circuits
Boolean Polynomials
Normal Forms (Disjunctive/Conjunctive)
Designing Circuits with Specified
Conditions
• Showing Two Circuits Are Equivalent
1.4.76
Digital Logic Circuits
• Developed by Claude Shannon in 1938 to
model telephone switching circuits:
x
y
Series Switch
x AND y
x
x OR y
y
Parallel Switch
1.4.77
Logical Gates
• Instead of working with switches, we model
digital circuits using gates: AND-gates, ORgates, and NOT-gates.
• We draw these as:
x
y
x
y
OR
x+y
x
AND
xy
NOT
x’
1.4.78
Notation
• Modeling digital circuits leads to the
equivalent analysis of symbolic logic.
• Symbolic Logic
Digital Circuits
T, t
1, 1
F, c
0, 0
p, q, r, ...
x, y, z, ...
~p
x’
pq
xy
pq
x+y
1.4.79
Boolean Polynomials
• When modeling, we use Boolean
polynomials to describe algebraically the
function of a combinatorial circuit.
• A combinatorial circuit is one in which the
output at any time depends on the inputs at
the previous time. (i.e. no feedback loops)
• A Boolean polynomial is a function which
takes 0,1 inputs and outputs a 0 or 1 using
the operations AND, OR, and NOT.
1.4.80
Examples of Boolean Polynomials
• When working with Boolean polynomials,
we must first know the specific input
variables.
• Examples:
f(x,y,z) = x + y + z
f(x,y) = x’ + xy
f(x,y,z) = x(y + z’)
1.4.81
Evaluating Boolean Polynomials
• Using: x y x’ y’ (x + y) xy
1 1 0 0
1
1
1 0 0 1
1
0
0 1 1 0
1
0
0 0 1 1
0
1
• Examples: Find f(x,y) = x’ + xy
x y x’ xy (x’ + xy)
1 1 0 1
1
1 0 0 0
0
0 1 1 0
1
0 0 1 0
1
1.4.82
Normal Forms
• Expressing a Boolean Polynomial in its
normal form provides an easy method to
calculate its truth table.
• We can create two different normal forms
for Boolean Polynomials: the disjunctive
and the conjunctive normal form.
• These forms are made up of special terms
called minterms or maxterms.
1.4.83
Disjunctive Normal Form
• A minterm is a Boolean polynomial that is
only the product of each variable or its
negation (but not both).
• Examples: f(x,y) = xy’
f(x,y,z) = x’yz’
f(w,x,y,z) = wx’y’z
• The disjunctive normal form (DNF) is a
Boolean polynomial that is the sum of
minterms (sum of products).
1.4.84
Disjunctive Normal Form (cont’d.)
• Express f(x,y,z) = x + x’z in its DNF.
f(x,y,z) = x + x’z
= x(y + y’)(z + z’) + x’(y + y’)z
= (xy + xy’)(z + z’) + (x’y + x’y’)z
= xyz + xyz’ + xy’z + xy’z’ + x’yz + x’y’z
• The thing to note here is that each minterm
has an output of 1 at only a single,
particular line of the truth table.
• i.e. xy’z = 1 at 101 and = 0 elsewhere.
1.4.85
Disjunctive Normal Form (cont’d.)
• We can now think of the inputs, in fact, as
their associated minterms to get outputs:
xyz
xyz
f(x,y,z)
111
xyz
1
110
x y z’
1
101
x y’z
1
100
x y’z’
1
011
x’y z
1
010
x’y z’
0
001
x’y’z
1
000
x’y’z’
0
Designing Circuits
with Specified Conditions
1.4.86
• In the other direction:
x y z f(x,y,z)
111 0
0
0
0
0
110 0
0
0
0
0
101 1
1
0
0
0
100 0  0 + 0 + 0 + 0
011 1
0
1
0
0
010 1
0
0
1
0
001 1
0
0
0
1
000 0
0
0
0
0
f(x,y,z) = xy’z + x’yz + x’yz’ + x’y’z
1.4.87
Conjunctive Normal Form
• In a similar fashion, we can analyze
functions using the conjunctive normal
form - the product of sums.
• In this case, we look for the 0’s in the
function’s output and associate each with a
maxterm, whose output is 0 at that row.
1.4.88
Equivalent Circuits
• Two logical circuits are equivalent if and
only if they have the same truth table.
• This can be thought similarly as holding
when the two circuits have the same
disjunctive (conjunctive) normal form.
5.2.89
Section 5.2
• Properties of sets
• Methods to show one set is a subset of
another
• Set identities
• Methods to show two sets are equal
5.2.90
Some Subset Relations
• For all sets A, B, and C:
1. A B A and A B B
2. A A B and B A B
3. If A B and B C, then A C.
5.2.91
Procedural Versions
of the Set Operations
•
•
•
•
•
x  A B means x  A or x  B.
x  A B means x  A and x  B.
x  A - B means x  A and x  B.
x  Ac means x  A.
(x, y)  A  B means x  A and y  B.
5.2.92
Example: Show A B  A
Let x  A B. Show x  A.
x  A B means x  A and x  B.
In particular, this means x  A.
Hence, given x  A B, we deduce
that x  A.
• Therefore A B  A.
•
•
•
•
5.2.93
Set Identities
Commutative Laws
A B = B  A and A  B = B  A
Associative Laws
(A  B)  C = A  (B  C)
(A  B)  C = A  (B  C)
Distributive Laws
A  (B  C) = (A  B)  (A  C)
A  (B  C) = (A  B)  (A  C)
5.2.94
Set Identities (cont’d.)
Intersection with U
A U = A
Universal Bound
A U = U
Double Complement Law
(Ac)c = A
Idempotent Laws
A  A = A and A  A = A
5.2.95
Set Identities (cont’d.)
DeMorgan’s Laws
(A B)c = Ac  Bc and (A  B)c = Ac  Bc
Set Difference Law
A - B = A  Bc
Absorption Laws
A  (A  B) = A
A  (A  B) = A
5.2.96
Basic Method to Show Set
Equality
•
•
•
•
Let sets A and B be given. Show A = B.
First, show A  B.
Second, show B  A.
If the “” holds in both directions, then we
can conclude that A = B.
5.2.97
Example 1:
A  (B  C) = (A  B)  (A  C)
First, show A  (B  C)  (A  B)  (A  C).
Then, show (A  B)  (A  C)  A  (B  C).
5.2.98
Example 2: If A  B, then
A  B = B and A  B = A
First, show A  B  A.
Then, show A  A  B.
5.2.99
(A  B) - C = (A - C)  (B - C)
• To show these sets are equal, we will simply
apply the Properties of Sets.
(A  B) - C
= (A  B)  Cc
= (A  Cc)  (B  Cc )
= (A - C)  (B - C )
2.1.100
Chapter 2. The Logic of
Quantified Statements
• Predicates
• Quantified Statements
• Valid Arguments and Quantified Statements
2.1.101
Section 1. Predicates and
Quantified Statements I
• In Chapter 1, we studied the logic of compound
statements, but the argument reasoning in there
cannot show the validity of the following simple
argument:
All men are mortal.
Socrates is a man.
Therefore, Socrates is mortal.
2.1.102
Predicates
• To study these types of logical arguments, we
turn to predicate calculus.
• 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.
2.1.103
Predicate Notation
• If P(x) is a predicate and x has a domain D, the
truth set of P(x) is the set of all elements of D
that make P(x) true when substituted for x.
• The truth set is denoted {x  D | P(x)}.
• If P(x) and Q(x) are predicates and the common
domain of x is D, then the notation P(x)  Q(x)
denotes that the truth set of P(x) is a subset of
the truth set of Q(x).
• If P(x) and Q(x) have the same truth set, we
denote this as P(x)  Q(x).
2.1.104
The Universal Quantifier
• We often find predicates involved when we are
making claims about properties that some or all
the elements of a set obey. This leads us to look
at statements using one of two quantifiers.
• The Universal Quantifier: If P(x) is a predicate
over a domain D, we say a universal statement
is one of the form “"x  D, P(x).”
• This universal statement is true provided P(x) is
true for every x in D.
• Any x  D with P(x) false, is a counterexample.
2.1.105
Examples
• Example 1: Let D = {1,2,3,4,5} and let P(x) be
the predicate x2  x. Using the Method of
Exhaustion, we find that 12  1, 22  2, 32  3,
42  4, and 52  5 are all true, hence the
universal statement "x {1,2,3,4,5}, x2  x is
true.
• Example 2: If we change this universal
statement to: "x  R, x2  x, it is no longer true
since x = 1/2 is a counterexample.
2.1.106
The Existential Quantifier
• The Existential Quantifier: If P(x) is a predicate
over a domain D, we say an existential
statement is one of the form “$x  D ' P(x).”
• This existential statement is true provided P(x)
is true for at least one x in D, and is false if P(x)
is false for every x in D.
• From this, we see that the negation of an
existential statement is a universal statement,
and, likewise, the negation of a universal
statement is an existential one.
2.1.107
More Examples
• Consider: $x  D ' x2 < 0.
• Example 1: If D = C (the Complex numbers),
then x = i yields i2 = (-1) < 0, hence the
existential statement is true.
• Example 2: If D = R, then by the properties of
R, we know that x2  0 for all x in R, hence the
existential statement is false.
• This second example show us the negation of
$ x  R ' x2 < 0 is the universal statement
"x  R, x2  0.
2.1.108
Negations of Quantifiers
• As seen in the previous example, the negation of
an existential statement is a universal statement.
• Formally, we denote:
~[$x  D ' P(x)]  "x  D, ~P(x).
• By the same process, we have that:
~["x  D, P(x)]  $x  D ' ~P(x).
• Intuitively, the first says the opposite of at least
one thing satisfying a property is that none do,
and the opposite of all things satisfying the
property is that at least one does not.
2.1.109
Examples of Negations
• The negation of:
Some people are sad.
is
All people are not sad.
• The negation of:
All integers are rational.
is
At least one integer is irrational.
• Which of each pair is true?
2.1.110
Universal Conditional
• The statement:
"x, if P(x), then Q(x)
is called the universal conditional.
• Many mathematical statements are universal
conditionals.
• Example: "x  R, if x > 2 then x2 > 4 (formal)
is equivalent to: (informally)
– Every real number greater than 2 has a square
greater than 4.
– The square of any real number greater than 2 is
greater than 4.
2.1.111
Negation of Quantified Conditionals
• Since we see the properties of symbolic logic
carry over when dealing with quantified logic,
we deduce that:
~["x  D, if P(x), then Q(x)]
is
$x  D ' P(x) and ~Q(x).
• Similarly, ~[$x  D ' if P(x), then Q(x)]
is
"x  d, P(x) and ~Q(x).
• Negate: 1. Every CS student studies CMSC203.
2. Some CS students study CMSC203.
2.2.112
Section 2 - More Quantified
Statements
• Statements with multiple quantifiers;
• Negations of multiply quantified statements;
• Equivalent forms of universal conditionals.
2.2.113
Multiply Quantified Statements
• Consider the following statement:
Given any real number, there is a
smaller real number.
• This is equivalent to the formal statement:
"xR, $yR ' y < x.
• This is an example of a multiply quantified
statement.
2.2.114
Examples
• The formal statement:
$xR+ ' "yR+, y < x
can be interpreted informally as:
• There is a non-negative real number with the
property that all other non-negative real
numbers are smaller than this number;
• There is a non-negative real number that is
larger than all other non-negative real numbers.
2.2.115
Another Example
• INFORMAL:
Everybody loves somebody.
• FORMAL:
" people x, $ a person y ' x loves y.
• INFORMAL:
Somebody loves everybody.
• FORMAL:
$ a person x ' " people y, x loves y.
2.2.116
Negation of Universal Existentials
• What is the negation of the statement:
" people x, $ a person y such that x loves y?
• Recall this is “Everybody loves somebody,” so
its negation would be the case of “Somebody
who does not love anybody.”
• In formal terms:
$ a person x ' " people y, x does not love y.
• Thus:
~ ["x, $y ' P(x,y) ]  $x ' "y, ~P(x,y)
2.2.117
Negation of Existential Universals
• What is the negation of the statement:
$ a person x such that " people y, x loves y?
• Recall this is “Somebody loves everybody,” so
its negation would be the case of “Everybody
has at least one person they do not love.”
• In formal terms:
" people x, $ person y ' x does not love y.
• Thus:
~ [$x ' "y, P(x,y) ]  "x, $y ' ~P(x,y)
Equivalent Forms of
Universal Conditionals
2.2.118
• Given the statement:
"xD, if P(x), then Q(x)
analogous to our definitions from propositional
calculus, we can construct the following.
• Contrapositive: "xD, if ~Q(x), then ~P(x).
• Converse: "xD, if Q(x), then P(x).
• Inverse: "xD, if ~P(x), then ~Q(x).
• Negation: $xD ' P(x), and ~Q(x).
2.2.119
Example
•
•
•
•
•
Statement:
"xR, if x > 2, then x2 > 4.
Converse:
"xR, if x2 > 4, then x > 2.
Inverse:
"xR, if x  2, then x2  4.
Contrapositive: "xR, if x2  4, then x  2.
Negation:
$xR ' x > 2 and/but x2  4.
2.3.120
Section 3 - Valid Arguments
•
•
•
•
Argument Forms;
Diagrams to Test for Validity;
Quantified Converse and Inverse Errors;
Abduction.
2.3.121
Universal Instantiation
• Consider the following statement:
All men are mortal
Socrates is a man.
Therefore, Socrates is mortal.
• This argument form is valid and is called
universal instantiation.
• In summary, it states that if P(x) is true for all
xD and if aD, then P(a) must be true.
2.3.122
Universal Modus Ponens
• Formal Version:
" xD, if P(x), then Q(x).
P(a) for some aD.
\ Q(a).
• Informal Version:
If x makes P(x) true, then x makes Q(x) true.
a makes P(x) true.
\ a makes Q(x) true.
• The first line is called the major premise and the
second line is the minor premise.
2.3.123
Universal Modus Tollens
• Formal Version:
" xD, if P(x), then Q(x).
~Q(a) for some aD.
\ ~P(a).
• Informal Version:
If x makes P(x) true, then x makes Q(x) true.
a makes Q(x) false.
\ a makes P(x) false.
2.3.124
Examples
• Universal Modus Ponens or Tollens???
If a number is even, then its square is even.
10 is even.
Therefore, 100 is even.
If a number is even, then its square is even.
25 is odd.
Therefore, 5 is odd.
2.3.125
Using Diagrams to Show Validity
• Does this diagram portray the argument of the
second slide?
Mortals
Men
Socrates
2.3.126
Modus Ponens in Pictures
• For all x, P(x) implies Q(x).
P(a).
Therefore, Q(a).
{x | Q(x)}
{x | P(x)}
a
2.3.127
A Modus Tollens Example
• All humans are mortal.
Zeus is not mortal.
Therefore, Zeus is not human.
Zeus
Mortals
Humans
2.3.128
Modus Tollens in Pictures
• For all x, P(x) implies Q(x).
~Q(a).
Therefore, ~P(a).
a
{x | Q(x)}
{x | P(x)}
2.3.129
Converse Error in Pictures
• All humans are mortal.
Felix the cat is mortal.
Therefore, Felix the cat is human.
Mortals
Felix?
Humans
Felix?
2.3.130
Inverse Error in Pictures
• All humans are mortal.
Felix the cat is not human.
Therefore, Felix the cat is not mortal.
Mortals
Felix?
Felix?
Humans
Quantified Form of Converse
and Inverse Errors
• Converse Error:
"x, P(x) implies Q(x).
Q(a), for a particular a.
\ P(a).
• Inverse Error:
"x, P(x) implies Q(x).
~P(a), for a particular a.
\ ~Q(a).
2.3.131
2.3.132
An Argument with “No”
• Major Premise: No Naturals are negative.
• Minor Premise: k is a negative number.
• Conclusion: k is not a Natural number.
Natural numbers
Negative numbers
k
2.3.133
Abduction
• Major Premise: All thieves go to Paul’s Bar.
Minor Premise: Tom goes to Paul’s Bar.
Converse Error: Therefore, Tom is a thief.
• Although we can’t conclude decisively if Tom is
a thief or not, if we have further information that
99 of the 100 people in Paul’s Bar are thieves,
then the odds are that Tom is a thief and the
converse error is actually valid here.
• This is called abduction by Artificial
Intelligence researchers.
3.1.134
Chapter 3 - Elementary Number
Theory and Proofs
• Direct & Indirect Proofs;
• Properties of Primes, Integers, Rationals, and
Reals;
• Divisibility (Unique Factorization Theorem);
• Modular Forms (Quotient-Remainder Theorem);
• The Division & Euclidean Algorithms.
3.1.135
Section 1 - Direct Proof
and Counterexample
• Mathematics is built on the Axiomatic Method.
• Start with Definitions and Axioms.
• Use these in valid arguments to demonstrate
Theorems.
• Use all of the above to deduce NEW Theorems.
• Continue ad infinitum.
• Get paid! (or pass course!)
3.1.136
Even and Odd Integers
• Definition: An integer n is even provided there
exists an integer k such that n = 2k.
• Definition: An integer n is odd provided there
exists an integer k such that n = 2k + 1.
• 38 is even since 38 = 2(19) and 19 is an integer.
• 417 is odd since 417 = 2(208) + 1 and 208 Z.
• 417 is not even since 417 = 2(208.5) but
208.5 Z.
3.1.137
Prime and Composite Integers
• Definition: An integer n is prime if, and only if,
n > 1, and for all positive integers r and s, if
n = rs, then r = 1 or s = 1.
• Definition: An integer n is composite if, and
only if, n > 1, and for all positive integers
r and s, if n = rs, then r  1 and s  1.
• Every natural number > 1 is either prime or
composite.
• 2 is the only even prime number.
3.1.138
Proving Existential Statements
• To show: There exists an a such that P(a).
• Demonstrate an Example:
Prove there is an even integer that can be
written in two ways as the sum of two primes.
Proof: 10 = 3 + 7 = 5 + 5.
• Construct an Example:
Prove if r,s Z, then 4r + 6s is even.
Proof: Let r,s Z. Thus 2r + 3s = k Z, and
4r + 6s = 2k, therefore (4r + 6s) is even.
3.1.139
Proving Universal Statements
• Most theorems are of the form:
" xD, if P(x), then Q(x).
• If D is a finite set, we can just exhaust over each
element n to verify that Q(n) holds.
• Example: Prove all n  {4, 6, 8, 10, 12} can be
written as the sum of two primes.
Proof:
4=2+2
6=3+3
8=3+5
10 = 3 + 7
12 = 5 + 7.
Generalizing from the
Generic Particular
3.1.140
• When it is not feasible to exhaust over each
element of the domain, we turn to the method of
generalizing from the generic particular:
– To show that every element of a domain satisfies a
certain property, suppose x is a particular, but
arbitrarily chosen element of the domain, and show
that x satisfies the property.
• This is the strategy we employ in the method of
direct proof.
3.1.141
Method of Direct Proof
• Express the statement to be proved in the form:
" xD, if P(x), then Q(x)
if possible. (Often, this is done mentally)
• Start the proof by supposing that n is a
particular but arbitrary element of D for which
P(n) is true. (Suppose nD and P(n))
• Show that the conclusion Q(n) follows from
P(n) by using definitions, axioms, previously
established results, and the rules for logical
inference.
3.1.142
Theorem 3.1.1
Prove: If the sum of two integers is even, then
so is their difference.
Proof: Let m and n be any integers with (m + n)
even. This means there is an integer k such that
(m + n) = 2k.
Now, (m - n) = (m + n) - 2n = 2k - 2n
= 2 (k - n) = 2p,
where k - n = p is an integer. Thus (m - n) is
even. Also, (n - m) = -(m - n) = 2(-p),
so (n - m) is also even. Therefore, the difference
of m and n is even. QED
3.1.143
Directions for Writing Proofs
• Write the statement to be proved.
• Clearly mark the beginning of your proof with
the word Proof.
• Make your proof self-contained:
– Identify each variable used in the body of the proof;
– Introduce only necessary variables and notation;
– Use Lemmas to show significant but related ideas.
• Write proofs in complete (English) sentences.
3.1.144
Common Mistakes
•
•
•
•
Arguing from examples;
Using the same letter to mean different things;
Jumping to a conclusion;
Begging the question (i.e. assuming true that
which you want to prove);
• Using if when you mean since, hence, thus,
therefore, hencely, thusly, hereforthwith, etc.
3.2.145
Section 2 - Rational Numbers
• Recall the definition of a Rational Number:
A real number r is rational provided there
exist integers a and b such that r = a/b and
b  0.
• Theorem: Every integer is a rational number.
Proof: Let a be an integer, then a = a/1.
Moreover, 1 is an integer and 1  0. Therefore a
is a rational number. QED
3.2.146
Proving Properties of Rationals
• We will now look at some theorems and
corollaries (theorems that follow essentially
trivially from another theorem) about rational
numbers.
• We will rely on the Closure Properties of the
Integers under +, -, and :
If a,b are integers, then (a+b), (a-b), (b-a),
and ab are also integers.
• We will also use their Zero-Product Property:
If a,b  Z, with a  0 and b  0, then ab  0.
3.2.147
Closure of the Rationals Under +
• Theorem: If r, s  Q, then (r + s)  Q.
• Proof: Let r, s  Q. Thus $ a, b, c, d  Z such
that r = a/b with b  0 and s = c/d with d  0.
Now, (r + s) = a/b + c/d = (ad + bc)/bd.
Since a, b, c, d  Z, we have that (ad + bc)  Z
and that bd  Z. Moreover, since b  0 and d 
0, we conclude that bd  0. Consequently,
(r + s) is the quotient of integers with non-zero
denominator. Therefore (r + s)  Q. QED
3.2.148
A Corollary
• Corollary: Double a rational is rational.
• Proof: Let r = s in the previous theorem.
3.3.149
Section 3 - Divisibility
• Definition: If n and d are integers and d  0, then
n is divisible by d provided n = d  k for some
integer k.
• Alternatively, we say:
n is a multiple of d
d is a factor of n
d is a divisor of n
d divides n (denoted with d | n).
3.3.150
Properties of Divisibility
• Divisors of 0: If k is a non-zero integer, then
k divides 0 since 0 = k  0.
• Positive Divisors of a Positive Number:
If a and b are positive integers and a | b, is a  b?
Yes. Since a | b, $ k  Z,such that b = a  k.
Moreover, 0 < k, since a and b are, so 1  k.
Thus:
a = a  1  a  k = b.
Therefore
a  b.
• Divisors of 1: The only divisors of 1 are 1 and -1.
3.3.151
Divisibility of Algebraic Terms
• Let a and b be integers.
• Does 3 | (3a + 3b)?
Yes, since (3a + 3b) = 3(a + b) and (a + b)  Z.
• Does 5 | 10ab?
Yes again, since 10ab = 5(2ab) and (2ab)  Z.
• If m  Z and m | (a + b), does m | a and m | b?
No. 2 | 8 but 2 | 5 and 2 | 3.
3.3.152
Divisibility and Non-divisibility
• There is another way to test for divisibility:
If d | n, there is integer k with n = dk, then
k = (n/d). So, if (n/d) is an integer, then d | n.
• This leads to an easy way to test for nondivisibility: If (n/d) is not an integer, then d
cannot divide n.
• Examples:
3 | 12 since 12/3 = 4  Z.
5 | 12 since 12/5 = 2.4  Z.
3.3.153
Proving Properties of Divisibility
• Theorem: Transitivity of Divisibility
For all a,b,c  Z, if a | b and b | c, then a | c.
• Proof: Let a, b, and c be integers, and assume
a | b and b | c. Thus there exist m,n  Z with
b = ma and c = nb.
Now, c = nb = n(ma) = (nm)a. Since
m,n  Z, we have nm  Z, therefore a | c. QED
• Example: 3 | 9 and 9 | 909, therefore 3 | 909.
3.3.154
Divisibility by a Prime
• Theorem: Every positive integer greater than 1
is divisible by a prime number.
• Proof: Let n  Z with n > 1. Then either n is
prime or composite. If n is prime, it is divisible
by itself, and we are done.
Now, assume n is composite. Thus there are
integers (greater than 1) a and b, such that
n = ab. If a is prime, we are done. If not, factor
a, .... Will we eventually get to a prime factor?
3.3.155
Standard Factored Form
• Definition: Given any integer n > 1, the
standard factored form of n is an expression of
the form:
n = (p1)e1  (p2)e2  (p3)e3...(pk)ek,
where k is a positive integer ; p1,p2,...,pk are
prime numbers with p1 < p2 < ... < pk; and
e1,e2,...,ek are positive integers.
• Example:
3300 = 33  100 = 3  11  102
= 22  3  52  11.
3.3.156
Unique Factorization Theorem
• Theorem: Given any integer n > 1, there exist
positive integer k; prime numbers p1,p2,...,pk;
and positive integers e1,e2,...,ek, with
n = (p1)e1  (p2)e2  (p3)e3...(pk)ek,
and any other expression of n as a product of
prime numbers is identical to this except,
perhaps, for the order in which the factors
appears.
• This is also referred to as the Fundamental
Theorem of Arithmetic.
Fundamental Theorem
of Arithmetic
3.3.157
• Theorem: Every positive integer greater than 1
has a unique factorization as the product of
primes.
• Proof: (outline)
1. Apply the previous theorem to each composite
factor encountered.
2. Sort the final listing to get the prime factors in
increasing (decreasing?) numeric order.
3. Rewrite using exponents.
3.4.158
Section 4 - The Quotient
Remainder Theorem
•
•
•
•
•
The Quotient-Remainder Theorem;
Modular Arithmetic (div and mod functions);
Proofs Requiring Division into Cases;
Representations of the Integers.
The Parity Theorem
3.4.159
Quotient-Remainder Theorem
• Theorem: Given any integer n and a positive
integer d, there exist unique integers q and r such
that: n = dq + r, and 0  r < d.
• Example: If n = 27 and d = 5, then consider:
27 = 0  5 + 27
27 = 1  5 + 22
27 = 2  5 + 17
27 = 3  5 + 12
27 = 4  5 + 7
27 = 5  5 + 2 here, r = 2 and q = 5.
27 = 6  5 + (-3)
3.4.160
div and mod Functions
• Definition: Given a nonnegative integer n and a
positive integer d,
n div d = the integer quotient obtained
when n is divided by d;
n mod d = the integer remainder obtained
when n is divided by d.
• Symbolically, if n and d are positive integers:
n div d = q and n mod d = r, where n, d, q, and r
are as described in the Quotient-Remainder
Theorem.
3.4.161
div and mod Examples
• Consider the previous example of n = 27 and
d = 5. Since 27 = 55 + 2 yields q = 5 and
r = 2, we have that:
27 div 5 = 5;
27 mod 5 = 2.
• More: 100 div 10 = 10
100 mod 10 = 0
100 div 8 = 12
100 mod 8 = 4
10 div 100 = 0
10 mod 100 = 10
365 div 7 = 52
365 mod 7 = 1
3.4.162
Representations of the Integers
• Recall, we have claimed previously that every
integer is either even or odd.
• Consider:
Even: ... -10 -8 -6 -4 -2 0 2 4 6 8 10 ...
Odd:
... -9 -7 -5 -3 -1 1 3 5 7 9 11 ...
• We note that all the evens are n = 2q = 2q + 0
and all the odds are n = 2q + 1.
• Moreover, each successive integer alternates
parity (its mod 2 value).
3.4.163
More Representations of Integers
• If we continue representing integers via the
Quotient-Remainder Theorem, we observe:
Modulus Forms
2
2n 2n + 1
3
3n 3n + 1 3n + 2
4
4n 4n + 1 4n + 2 4n + 3
...
k
kn kn + 1 kn + 2 ... kn + (k-1)
3.4.164
Division into Cases
• Sometimes when proving a theorem, the logical
flow will fork into different directions, each of
which need investigation.
• This is analogous to needing IF THEN ELSE
instead of just IF THEN in programming flow.
• An example is the Parity Theorem.
• Theorem: Any two consecutive integers have
opposite parity.
Division into Cases (cont’d.)
3.4.165
Proof: Let m be an integer, so its successor is
(m+1). Show m and (m+1) have opposite parity.
Case 1 (m even): If m is even, there is an integer k
such that m = 2k, hence (m+1) = 2k + 1, thus
(m+1) is odd. So, m even implies (m+1) is odd.
Case 2 (m odd): If m is odd, there is integer k such
that m = 2k + 1. Hence:
(m+1) = (2k + 1) + 1 = 2k + 2 = 2(k +1), and so
(m+1) is even. So, m odd implies (m+1) is even.
Therefore, consecutive integers have opposite
parity. QED
The Square of an Odd Integer
3.4.166
Theorem: If n is an odd integer, (n2 mod 8) = 1.
Proof: Let n be an odd integer, so it has the
representation modulo 4 of n = 4q+1 or 4q+3.
Case 1: Let n = 4q+1. Thus n2 = (4q+1)2
= 16q2 + 8q + 1 = 8(2q2 + q) + 1.
Case 2: Let n = 4q+3. Thus n2 = (4q+3)2
= 16q2 + 24q + 9 = 16q2 + 24q + 8 + 1
= 8(2q2 + 3q + 1) + 1.
Therefore, in either case, (n2 mod 8) = 1. QED
3.6.167
Section 6 - Indirect Argument
• Method of Proof by Contradiction;
• Method of Proof by Contraposition;
• Examples of Each Method.
Proof by Contradiction
3.6.168
• Instead of the Universal Modus Ponens argument
form: "x, [P(x)  Q(x) AND P(x)]  Q(x), a
Proof by Contradiction (reductio ad absurdum)
follows the Universal Modus Tollens form: "x,
[P(x)  Q(x) AND ~Q(x)]  ~P(x).
• We obtain a contradiction when the conclusion of
this form is combined with our standard
assumption in a direct proof the P(x) holds.
• This differs marginally from the Method of
Contraposition which proves directly the validity
of the comtrapositive statement.
3.6.169
Method of Proof By Contradiction
• Suppose the statement to be proved is FALSE;
• Show this supposition leads logically to a
contradiction (either to the original hypotheses
or to some other statement of fact);
• Conclude that the original statement to be
proved is TRUE.
3.6.170
Example: No Greatest Integer
Theorem: There is no greatest integer.
Proof: (Contradiction) Suppose there is a greatest
integer N. Thus for every integer k, k  N.
Now, since N is an integer, by closure, (N+1)
is an integer. Thus:
N+1N,
hence
1  0.*
Therefore, there is no greatest integer. QED
3.6.171
Sums of Rationals and Irrationals
Theorem: The sum of a rational and an irrational
is irrational.
Proof: (Contradiction) Let r be rational, s be
irrational, and assume (r + s) is rational. Thus
there exist a,b,c,d  Z, with r = a/b,
(r + s) = c/d and b,d  0.
Now, s = (r + s) - r = c/d - a/b
= (bc - ad)/bd.
Since a,b,c,d  Z and b,d  0, we have s  Q.*
Therefore (r + s) is irrational. QED
3.6.172
Argument by Contraposition
• Since we know that a statement and its
contrapositive are logically equivalent, if we can
pose our conjecture in the form of a conditional,
we can work, equivalently, with its
contrapositive form.
• We call this strategy, simply enough, Argument
by Contraposition.
3.6.173
Method of Proof by Contraposition
• Express the statement to be proved in the form
"x, if P(x) then Q(x).
• Rewrite this as its contrapositive
"x, if ~Q(x) then ~P(x).
• Prove the contrapositive form directly:
– Suppose x is such that Q(x) is FALSE.
– Show that P(x) is FALSE.
3.6.174
Example of Contraposition
Theorem: Given any integer n, if n2 is even, then
n is even.
(Contrapositive: If n is odd, then n2 is odd.)
Proof: (Contraposition) Let n be an integer and
assume that n is odd. Thus, there is an integer k
such that n = 2k + 1. Show that n2 is odd.
Now, n2 = (2k + 1)2 = 4k2 + 4k + 1
= 2(2k2 + 2k) + 1.
Since k is an integer, (2k2 + 2k) is an integer.
Therefore n2 is odd. QED
3.7.175
Section 7 - Two Classical Theorems
Prove: The 2 is irrational.
Proof: (Contradiction) Assume 2 is rational.
Then, there exist p,q  Z in “lowest terms” with
2 = p/q and q  0.
Now, 2 = p/q implies 2q2 = p2, hence p2 is
even. From a previous result, this yields that p is
even, so we deduce $m  Z with p = 2m.
Thus 2q2 = (2m)2 = 4m2, so q2 = 2m2. This
time, we get that q2 is even, hence q is even.*
Therefore 2 is irrational.
3.7.176
A Corollary
Corollary: (1 + 32) is irrational.
Proof: (Contradiction) Assume (1 + 32) is
rational. Then, there exist p,q  Z in “lowest
terms” with (1 + 32) = p/q and q  0.
Now, solving for 2, we get
2 = (p - q)/3q,
which implies 2 is rational.*
Therefore (1 + 32) is irrational.
3.7.177
The Infinitude of the Primes
Theorem: The set of prime numbers is infinite.
Lemma: If a  Z and p is prime with p | a, then
p | (a + 1).
Proof: (Contradiction) Let a  Z and p be prime
with p | a. Assume that p | (a + 1). Then there
are m,n  Z such that a = mp and (a + 1) = np.
Now, (a + 1) = np implies 1 = np - mp, so
1 = p(n - m), thus p | 1. However, this means
p = 1,-1.* Therefore, p | (a + 1).
3.7.178
The Infinitude of the Primes
Proof: (Contradiction) Assume there are a finite
number of primes, say p1, p2, ..., pk.
Now, consider a = p1p2...pk. Since each pi is
an integer, a is likewise an integer, and so is
(a+1). Thus, by a previous result, (a+1) is
divisible by some prime, pj.
Since pj is a prime, it must divide a, and by
assumption, pj divides (a+1).*
Therefore the collection of primes is
infinite. QED
3.8.179
Section 8 - Two Algorithms
• We look at two algorithms to obtain values of use
in number theory.
• The Division Algorithm is a process to calculate
(n div d) and (n mod d) as specified in the
Quotient-Remainder Theorem.
• The Euclidean Algorithm uses the QuotientRemainder Theorem to calculate Greatest
Common Divisors.
3.8.180
The Division Algorithm
Input: Integers n and d.
Output: Integers q (= n div d) and r (= n mod d).
Begin
set r = n;
set q = 0;
while (r d)
set r = r - d;
set q = q + 1;
endwhile
output q, r;
End
3.8.181
Tracing the Division Algorithm
Calculate: (19 div 4) and (19 mod 4)
Iteration Number
0
1
2
3
4
n
19
d
4
r
19 15 11 7
3
q
0
1
2
3
4
Thus (19 div 4) = 4 and (19 mod 4) = 3.
3.8.182
Greatest Common Divisors
Definition: An integer d is a common divisor of
integers m and n provided d | n and d | m.
Example: Since 6 | 12 and 6 | 30, 6 is a common
divisor of 12 and 30.
Definition: If m,n  Z not both 0, then d  Z is
the greatest common divisor of m and n when:
1. d is a common divisor of m and n;
2. if c is also a common divisor of m and n,
then c  d.
We denote d = gcd(m,n).
3.8.183
Calculating GCDs
• Find gcd(72,63)
72 = 98 = 3324 = 2334
63 = 97 = 33 7
hence gcd(72,63) = 33 = 9.
• Find gcd(1020,630)
1020 = (25)20 = 220  520
630 = (23)30 = 230  330 = 220  210  330
hence gcd(1020,630) = 220.
3.8.184
Two Lemmas
• Lemma1: If r is a positive integer,
then gcd(r,0) = r.
Why? Everything divides 0 and r is the biggest
thing to divide r.
• Lemma 2: If a,b  Z, b  0 and q,r  Z+ with
a = bq + r,
then gcd(a,b) = gcd(b,r).
Proof of Lemma 2
3.8.185
Proof: Let a,bZ, b  0, and q,rZ+ with a = bq+r.
Case 1: Show gcd(a,b)  gcd(b,r).
Let x = gcd(a,b), so that x | a and x | b.
Now, since a = bq + r, we have r = a - bq,
thus x | r. But x | b, hence gcd(a,b) = x  gcd(b,r).
Case 2: Show gcd(a,b)  gcd(b,r).
Let y = gcd(b,r), so that y | b and y | r.
Now, since a = bq + r, we see that y | a.
But y | b, hence gcd(a,b)  y = gcd(b,r).
Therefore gcd(a,b) = gcd(b,r). QED
3.8.186
Calculating GCDs a la Euclid
•
•
•
•
•
•
Find gcd(330,156).
330 = 156  2 + 18
156 = 18  8 + 12
18 = 12  1 + 6
12 = 6  2 + 0
Hence gcd(330,156) = gcd(156,18)
= gcd(18,12) = gcd(12,6) = gcd(6,0) = 6.
3.8.187
The Euclidean Algorithm
Input: Integers A and B.
Output: gcd(A,B).
Begin
set a = A;
set b = B;
while (b 0)
set r = a mod b;
set a = b;
set b = r;
endwhile
output a;
End
4.1.188
Chapter 4 - Sequences and
Mathematical Induction
•
•
•
•
Sequences & Series (Summations);
Principle of Mathematical Induction;
Weak Form of Induction;
Strong Form of Induction.
4.1.189
Section 1 - Sequences
• A sequence is a list of elements called terms.
• We think of each term as occupying a specific
position within the sequence, so we may use an
index variable to denote specific but arbitrary
terms in the sequence.
• For example, if we have the sequence:
1, 2, 4, 8, 16, 32, 64, 128, ...
we can denote a0 = 1, a1 = 2, a2 = 4, a3 = 8, ...
• This is useful since we can now describe the
sequence as {ai = 2i}
Explicit Formulas
• Define the sequences {ai} and {bj} as:
ai = i / (i + 1) for i > 0;
bj = (j - 1) / j for j > 1.
• Thus
ai = 1/2, 2/3, 3/4, 4/5, 5/6, ...
and
bj = 1/2, 2/3, 3/4, 4/5, 5/6, ...
• Are these the same sequence?
• This indicates a natural way to check if two
sequences are equal:
Two sequences {ai} and {bi} are equal if
ai = bi for each value of i.
4.1.190
Alternating Sequences
4.1.191
• Consider the sequence defined as:
ai = (-1)i, for all positive integers i.
• We get: a1 = -1
a2 = 1
a3 = -1
a4 = 1, etc.
• Such a sequence in which successive terms have
opposite sign is called an alternating sequence.
4.1.192
Summation Notation
• Often, it is useful to sum up the terms of a
sequence. This expression of summation is
called a series.
• To save the tedium of continually writing
a1 + a2 + a3 + ... + an, we will use the
summation notation:
n
S ai = a1 + a2 + a3 + ... + an
i=1
4.1.193
Working with Summations
• Given
n
S ai = am + am+1 + am+2 + ... + an
i=m
we call i the index of summation, m the lower
limit, and n the upper limit.
• To compute a summation, we perform the
substitutions and calculations called for by the
formula:
5
9
S i2 = 22 + 32 + 42 + 52 = 54, S i2 = 92.
i=2
i=9
4.1.194
Telescoping Series
Consider:
n
S  k _ k + 1
k=1  k + 1 k + 2
Plugging into the formula, we get:
(1/2 - 2/3) + (2/3 - 3/4) + (3/4 - 4/5) + ...
... + [(n-1)/n - n/(n+1)] + [n/(n+1) - (n+1)/(n+2)]
= 1/2 - (n+1)/(n+2).
This type of series is called a telescoping series.
4.1.195
Changing Variables
• Rewrite:
n
S k / (k + 1) as a sum from 3 to (n+2).
k =1
• To do this, we use a change of variables from
k to j using the transformation j = k + 2 (so that
k = j - 2).
• Thus k = 1 becomes j = 3; k = n becomes j = n+2;
and k + 1 becomes (j - 1). Consequently:
n
n+2
S k / (k + 1) = S (j - 2) / (j - 1)
k =1
j =1
4.1.196
Product Notation
• Instead of summing the terms of a sequence, if we
want to multiply each term, we use the product
notation:
n
P ak = a1a2a3 ... an
k =1
• For example:
12
P 3k = 353637 ... 312 = 368
k =5
4.1.197
Properties of Sums and Products
• If {ak} and {bk} are sequences of real numbers,
and c is a non-zero real number, then for m  n:
n
n
n
1.
S ak + S bk = S (ak + bk)
k=m
k=m k=m
n
n
2.
S (c  ak)= c  S (ak)
k=m
k=m
n
n
n
3.
P ak  P bk = P ak bk
k=m k=m k=m
4.1.198
Factorial Notation
• Although products of the terms of a sequence do
not arise in problems as much as summations, one
particular type of product does.
• Definition: For each positive integer n, the
quantity n factorial, denoted n!, is defined to be
the product of all integers from 1 to n.
• Thus, n! = n(n-1)(n-2)...321.
• For completeness, we define 0! = 1.
4.1.199
Computing with Factorials
• 8!/7! = 87!/7! = 8.
• 5!/(2!3!) = (543!)/2!3! = 54/21 = 52 = 10.
• 1/(2!4!) + 1/(3!3!) = 13/(32!4!) + 14/(3!43!)
= (3 + 4)/(3!4!)
= 7/(624)
= 7/144.
• n!/(n - 3)! = [n(n - 1)(n - 2)(n - 3)!]/(n - 3)!
= n(n - 1)(n - 2)
= n(n2 - 3n + 2)
= n3 - 3n2 + 2n.
4.2.200
Section 2: Mathematical Induction
• Principle of Mathematical Induction;
• Formula for the Sum of the First n Integers;
• Formula for the Sum of a Geometric Series.
4.2.201
What Is Induction
• One of the more recently developed proof
techniques;
• Used to verify conjectures about processes that
occur repeatedly, according to definite patterns;
• Used to prove statements indexed on the Natural
Numbers (i.e. For all integers n  0, ...)
4.2.202
Climbing Infinite Staircases
• Consider the problem of trying to climb an
infinitely tall staircase.
• How can I know that this staircase is climbable?
• First, show the staircase exists. (Basis)
• Second, show standing at any arbitrary step
implies I can climb to the next step. (Induction)
• The basis shows there is an initial step.
• The induction validates a rule of motion from
one step to another.
4.2.203
In Pictures
Induction
Induction
Induction
Induction
Basis
4.2.204
Principle of Mathematical Induction
• Let P(n) be a predicate that is defined for
integers n, and let a be a fixed integer.
• Suppose the following two statements are true:
1. P(a) is true;
2. For all integers k  a, if P(k) is true, then P(k + 1) is
true.
• Then, for all integers n  a, P(n) is true.
4.2.205
Outline of an Inductive Proof
• Basis step says to show P(initial value) is true.
• Inductive step says:
– Assume P(k) is true for an arbitrary k.
– Use this to show P(k + 1) is true.
• This assumption of P(k) is called the inductive
hypothesis.
4.2.206
Tuppence and Nickels
• Show that any monetary value of 4 cents or
more can be composed of tuppence (a two-cent
coin) and nickels.
• BASIS: 4 cents = tuppence + tuppence.
• INDUCTION: Assume k-cents can be made up
from tuppence and nickels (k = 2t + 5n). Show
(k+1) can too.
4.2.207
Tuppence and Nickels (cont’d.)
• Case 1: (At least one of each coin: k = 2t + 5n)
k + 1 = 2t + 5n + 1 = 2t + 5n + 6 - 5
= (2t + 6) + (5n - 5) = 2(t + 3) + 5(n - 1).
• Case 2: (No tuppence: k = 5n)
k + 1 = 5n + 1 = 5n + 6 - 5 = 2(3) + 5(n - 1).
• Case 3: (No nickels and t > 2: k = 2t)
k + 1 = 2t + 1 = 2t + 5 - 4 = 2(t - 2) + 5(1).
4.2.208
Sum of the First n Integers
• Carl Friederich Gauss is bored in school.
• Teach instructs him to add together the numbers
from 1 to 100.
• Zip! Carl is done. Sum is 5050. How?
• 1 + 2 + 3 + ... + 100
= (1 + 100) + (2 + 99) + (3 + 98) +...+ (50 + 51)
= 101 + 101 + 101 +...+ 101
= 50(101)
= 5050.
4.2.209
Sum of the First n Integers (cont’d.)
Prove:
n
S k = n(n + 1) / 2 .
k =1
Proof: (Induction)
Basis: Show: 1
S k = 1(2) / 2 .
k =1
1
S k = 1 and 1(2)/2 = 2/2 = 1, so they are equal.
k =1
4.2.210
Sum of the First n Integers (cont’d.)
Inductive: Assume for some p:
1 + 2 +...+ p = p(p + 1)/2.
Show: (1 + 2 +...+ p) + (p + 1) = (p + 1)(p + 2)/2.
Now, (1 +...+ p) + (p + 1) = p(p + 1)/2 + (p + 1)
= (p + 1)[p/2 + 1]
= (p + 1)[p/2 + 2/2]
= (p + 1)(p + 2)/2.
Therefore 1 + 2 +...+ n = n(n+1)/2 for all integers n.
QED
4.2.211
The Geometric Series
• Any sum of the form: 1 + r + r2 + r3 +...+ rn is
called a Geometric Series.
• Thus, 1 + 2 + 4 + 8 + 16 +...+ 2n is a geometric
series.
• To find the sum of this series, consider:
S = 1 + r + r2 + r3 +...+ rn.
So
-rS = -r - r2 - r3 -...- r(n + 1).
and (1 - r)S = 1 - r(n + 1).
Therefore, 1 + r + r2 +...+ rn = 1 - r(n + 1) .
1-r
Proof of the Geometric Series
4.2.212
• Prove: 1 + r + r2 +...+ rn = [r(n + 1) - 1] / (r - 1)
• Proof: (Induction) Basis: Show true for n = 0. LHS
= 1. RHS = [r(0+1) - 1]/(r - 1) = (r-1)/(r-1) = 1.
Therefore LHS = RHS.
Induction: Assume 1+r+r2+...+rk = r(k+1)-1/r-1.
Show 1+r+r2+...+rk+r(k+1) = [r(k+2) - 1]/(r - 1).
Now, 1+r+r2+...+rk+r(k+1) = r(k+1)-1/r-1 + r(k+1)
= [r(k+1) - 1 + (r - 1)r(k+1) ]/(r - 1)
= [r(k+1) - 1 + rr(k+1) - r(k+1) ]/(r - 1)
= [r(k+2) - 1]/(r - 1). QED
4.3.213
Section 3: Mathematical Induction II
Prove: 22n - 1 is divisible by 3, for integers n > 0.
Proof: (Induction) Basis: 22(1) - 1 = 22 - 1 = 4 - 1 =
3, which is clearly divisible by 3.
Induction: Assume for some integer k, 22k - 1 is
divisible by 3.
Now, 22(k + 1) - 1 = 2(2k + 2) - 1 = 22k22 - 1
= 22k(4) - 1 = 22k(3 + 1) - 1 = 3(22k) + 22k - 1
= 3(22k) + (22k - 1).
Since each term in parentheses is divisible by 3, we
have therefore that 22(k + 1) -1 is also. QED
4.3.214
Proving An Inequality
Prove: 2n + 1 < 2n, for all integers n  3.
Proof: (Induction) Basis: LHS = 2(3) + 1 = 7, and
RHS = 23 = 8, so clearly 2n + 1 < 2n for n = 3.
Induction: Assume for some integer k, 2k + 1 < 2k.
Show 2(k + 1) + 1 < 2(k+1).
Now, 2(k + 1) + 1 = (2k + 1) + 2
< 2k + 2 < 2k + 2k = 2(k+1).
Therefore, 2n + 1 < 2n, for all integers n  3.. QED
4.3.215
Number of Subsets
Prove: A set with n elements has 2n subsets.
Proof: (Induction) Basis: Since the empty set has 1
subset (itself), and 20 = 1, then a set with 0
elements has 20 subsets.
Induction: Assume every k-element set has 2k subsets.
Show every (k+1)-element set has 2(k+1) subsets.
Now let A = {a1, a2, a3,..., ak, b}, so that A has
(k+1) elements. We partition P(A) into two subcollections where the first contains subsets of A
which don’t have b in them and the second contains
4.3.216
Number of Subsets (cont’d.)
subsets of A which do have b in them. Thus:
First Sub-collection Second Sub-collection
{}
{b}
{a1}
{a1, b}
{a1, a2}
{a1, a2, b}
{a1, a2, ..., ak}
{a1, a2, ..., ak, b}
Clearly, the first collection is made up of all the
subsets from the k-element set {a1, a2, ..., ak} so it
has 2k entries.
4.3.217
Number of Subsets (cont’d.)
Now, by construction, it follows that the second
collection must have the same number of entries as
the first, so it too must have 2k entries.
Since the collection of all subsets of A has been
partitioned into these two sub-collections, we see
that A must have 2k + 2k = 2(k+1) subsets. QED
4.4.218
Section 4: Strong Induction
• The Principle of Mathematical Induction asserts
that P(k) being true implies P(k+1) is true.
• However, sometimes we need to “look” further
back than 1 step to obtain P(k+1).
• That’s where the Strong Form of Mathematical
Induction comes in useful.
Principle of Strong
Mathematical Induction
4.4.219
Let P(n) be a predicate defined over all integers n,
and let a and b be fixed integers with a  b.
Suppose the following two statements are true:
1. P(a), P(a+1),..., P(b) are all true. (Basis step)
2. For any integer k > b, if P(i) is true for all
integers i with a  i < k, then P(k) is true.
(Inductive step)
Then the statement P(n) is true for all integers n  a.
4.4.220
Divisibility by a Prime
To see, via strong induction, that every integer
greater than 1 is divisible by a prime number, we
note that the basis value of 2 is trivially divisible
by a prime (itself).
Now, if we assume the strong inductive
hypothesis that every integer up to k is divisible
by a prime, when we look at k itself, either it is
prime (and hence divisible by itself), or can be
factored as lesser integers, each of which having
a prime factor. Thus k is divisible by a prime.
4.4.221
Binary Representation Theorem
Theorem: Every positive integer n can be expressed
as: n = cr2r + cr-12r-1 + ... + c222 + c12 + c0.
Proof: (Strong Induction) Clearly n = 1 corresponds
to just c0 = 1.
Assume every integer up to k has a binary
representation. Show k does too.
If k is even, then k/2 is an integer which is less
than k, so it has a binary expansion of the form:
k/2 = cr2r + cr-12r-1 + ... + c222 + c12 + c0.
Therefore, k = cr2r+1 + cr-12r +...+ c223 + c122 + c02.
4.4.222
Binary Representation Theorem (cont’d.)
In the case where k is odd, then (k-1)/2 is an
integer which is less than k, so it has a binary
expansion of the form:
(k-1)/2 = cr2r + cr-12r-1 + ... + c222 + c12 + c0.
Solving for k, we have:
k = cr2r+1 + cr-12r +...+ c223 + c122 + c02 + 1.
Therefore k has a binary representation. QED
4.4.223
Property of a Sequence
Consider the sequence a1, a2, a3, ... defined as:
a1 = 1, a2 = 2, a3 = 3 and an = an-1 + an-2 + an-3.
Show that an < 2n.
Basis: a4 = a1 + a2 + a3 = 1 + 2 + 3 = 6 < 16.
Inductive: Assume ai < 2i for i = 5, 6, 7, ..., (k - 1).
Show ak < 2k .
Now, ak = ak-1 + ak-2 + ak-3, so applying the
inductive hypothesis: ak-1 < 2k-1, ak-2 < 2k-2, and
ak-3 < 2k-3, we get:
4.4.224
Property of a Sequence (cont’d.)
ak = ak-1 + ak-2 + ak-3 < 2k-1 + 2k-2 + 2k-3
< (22 + 2 + 1)2k-3
= 72k-3
< 82k-3
< 232k-3 = 2k.
Therefore ak < 2k. QED
4.4.225
Why Use Strong Induction?
• In the first proof, we could not use weak
induction since factoring a composite number
yields values which are strictly less than the
composite number minus 1.
• In the second theorem, we apply strong induction
to a value (k/2 or (k - 1)/2) which is clearly much
less than k - 1.
• In the sequence problem, we need to apply the
inductive hypothesis to values at the three stages
k - 1, k - 2, and k - 3.
10.1.226
Chapter 10: Relations
•
•
•
•
•
•
•
Relations from one set to another;
Relations on a set;
Graphs of relations;
Congruence Modulo n;
Properties of Relations;
Equivalence Relations and Classes;
Partitions and Relations.
10.1.227
Section 1: Relations on Sets
• Definition: Let A and B be sets. A (binary)
relation R from A to B is a subset of A  B.
• If A = B, then we say R is a relation on A.
• Given an ordered pair (x,y) in A  B, x is related
to y by R, written x R y, if and only if (x,y)  R.
• Think of the usual relations we deal with and
replace for R in the notation x R y:
x = y, x  y, x > y, x | y, etc.
10.1.228
A Binary Relation as a Subset
• Let A = {1,2} and let B = {1,2,3} and define the
binary relation from A to B as:
R = {(x,y) | x  A and y  B and x - y is even}.
• What is R?
• (1,1)  0 is even 
(2,1)  1 is even 
(1,2)  -1 is even 
(2,2)  0 is even 
(1,3)  -2 is even 
(2,3)  -1 is even 
• Hence R = {(1,1), (2,2), (1,3)}.
10.1.229
Congruence Modulo 2
• If we generalize the last example to relate Z to Z
by: R = {(x,y) | x,y  Z and x - y is even}, we
get the relation congruence modulo 2:
R = {(x,y) | x,y  Z and x  y mod 2}.
• If we look hard at this relation, we see that:
even R even, since 2m - 2n = 2(m - n), and
odd R odd, since 2m+1 - (2n+1) = 2(m - n).
10.1.230
Relations on Strings
• Recall that if S is an alphabet, then Sn = {all
strings over S of length n}.
• Now, let S = {0,1} and define the relation on S6
to be: R = {(s,t) | s,t  S6 and first four characters
of s = first four characters of t}.
• (110011,110011)  R.
• (100000,100001)  R and (100001,100000)  R.
• (000000,000001), (000001,000011) and
(000000,000011) are all in R.
10.1.231
Graphs of a Relation
• R = {(x,y) | x,y  R and x2 + y2 = 1}
1
x
1
y
• Arrow Diagrams: R = {(1,a),(1,b),(2,b),(3,a)}
1
2
3
a
b
10.1.232
Functions
• A function from A to B is a relation that satisfies
the properties:
1. For each x in A, there is a y in B such that (x,y)
is in the function;
2. If (x,y) and (x,z) are in the function, then y = z.
10.1.233
Examples of Functions (Not)
• To understand functions, it is easier to study what
are not:
Violates Property 1
1
2
3
4
a
b
Violates Property 2
1
2
3
4
a
b
10.1.234
Inverse Relations
• Definition: If R is a relation from set A to set B,
then the inverse relation of R, denoted R-1, is
R-1 = {(y,x) | (x,y)  R}.
• For example, if R = {(1,3), (2,1), (4,5), (6,6)},
then R-1 = {(3,1), (1,2), (5,4), (6,6)}.
• Could R = R-1?
• Sure - let R = {(1,2), (2,1), (2,3), (3,2), (4,4)}.
Directed Graph of a Relation
10.1.235
• When R is a relation on a set A, we draw it using
a directed graph. For example, if
R = {(1,1), (2,4), (3,2), (4,1), (4,3)},
then its directed graph is:
2
3
1
4
Section 2: Reflexivity,
Symmetry, and Transitivity
10.2.236
• Definition: Let R be a binary relation on A.
• R is reflexive if for all x  A, (x,x)  R.
(Equivalently, for all x e A, x R x.)
• R is symmetric if for all x,y  A, (x,y)  R
implies (y,x)  R. (Equivalently, for all x,y  A,
x R y implies that y R x.)
• R is transitive if for all x,y,z  A, (x,y)  R and
(y,z)  R implies (x,z)  R. (Equivalently, for all
x,y,z  A, x R y and y R z implies x R z.)
Examples
10.2.237
• Reflexive: The relation R on {1,2,3} given by
R = {(1,1), (2,2), (2,3), (3,3)} is reflexive. (All
loops are present.)
• Symmetric: The relation R on {1,2,3} given by
R = {(1,1), (1,2), (2,1), (1,3), (3,1)} is symmetric.
(All paths are 2-way.)
• Transitive: The relation R on {1,2,3} given by
R = {(1,1), (1,2), (2,1), (2,2), (2,3), (1,3)} is
transitive. (If I can get from one point to another
in 2 steps, then I can get there in 1 step.)
Violations of the Properties
10.2.238
• Why is R = {(1,1), (2,2), (3,3)} not reflexive on
{1,2,3,4}?
Because (4,4) is missing.
• Why is R = {(1,2), (2,1), (3,1)} not symmetric?
Because (1,3) is missing.
• Why is R = {(1,2), (2,3), (1,3), (2,1)} not
transitive?
Because (1,1) and (2,2) are missing.
• Is {(1,1), (2,2), (3,3)} symmetric? transitive?
Yes! Yes!
The Transitive Closure
10.2.239
• Definition: Let R be a binary relation on a set A.
The transitive closure of R is the binary relation
Rt on A satisfying the following three properties:
1. Rt is transitive;
2. R is a subset of Rt;
3. If S is any other transitive relation that
contains R, then S contains Rt.
• In other words, the transitive closure of R is the
smallest transitive relation containing R.
10.2.240
Example of the Transitive Closure
• Given the relation R on {1,2,3,4},
1
2
4
3
its transitive closure is:
1
2
4
3
Properties of Equality
10.2.241
• Consider the Equality (=) relation on R:
Equality is reflexive since for each x  R, x = x.
Equality is symmetric since for each x,y  R, if
x = y, then y = x.
Equality is transitive since for each x,y,z  R, if x
= y and y = z, then x = z.
• As a graph, the relation contains only loops, so
symmetry and transitivity are vacuously satisfied!
10.2.242
Properties of Congruence Mod p
• Let p be an integer greater than 1, and consider
the relation on Z given by:
R = {(x,y) | x,y  Z and x  y mod p}.
• When we say x  y mod p, this means (x - y) = kp
for some integer k.
• Now, R is reflexive since (x - x) = 0 = 0p, for all
integers x.
• Moreover, R is symmetric, since if x  y mod p,
then (x - y) = kp, thus (y - x) = (-k)p, implying
that y  x mod p.
Congruence Mod p (cont’d.)
10.2.243
• Finally, R is transitive. Why?
• Let x  y mod p and y  z mod p. This means
there are integers k and j such that (x - y) = kp
and (y - z) = jp. Hence, (x - z) = (x - y) + (y - z)
= kp + jp = (k + j)p. Therefore, x  z mod p.
Properties of Inequality
10.2.244
• Consider the Inequality (< or >) relation on R:
Inequality is not reflexive since for no x  R is it
true that x < x.
Inequality is not symmetric since for each
x,y  R, if x < y is true, then y < x is false.
Inequality is transitive since for each x,y,z  R, if
x < y and y < z, then x < z.
• Inequality is so pathelogically unsymmetric, that
we define a special property to describe it.
The Anti-symmetry Property
10.2.245
• Definition: A relation R on a set A is called antisymmetric if (x,y)  R and (y,x)  R implies x = y.
• This is equivalent to requiring that if x  y and
(x,y)  R, then (y,x)  R. (All streets are one-way.)
• Example: R = {(1,1), (1,2), (3,2), (3,3)} is antisymmetric.
• Is every relation symmetric or anti-symmetric?
• No! Consider R = {(1,2), (2,1), (1,3)}.
10.3.246
Section 3: Equivalence Relations
• Definition: Let R be a binary relation on A. R is
an equivalence relation on A if R is reflexive,
symmetric, and transitive.
• From the last section, we demonstrated that
Equality on the Real Numbers and Congruence
Modulo p on the Integers were reflexive,
symmetric, and transitive, so we can describe
them as equivalence relations.
Examples
10.3.247
• What is the “smallest” equivalence relation on a
set A?
R = {(a,a) | a  A}, so that n(R) = n(A).
• What is the “largest” equivalence relation on a set
A?
R = A  A, so that n(R) = [n(A)]2.
Equivalence Classes
10.3.248
• Definition: If R is an equivalence relation on a set
A, and a  A, then the equivalence class of a is
defined to be:
[a] = {b  A | (a,b)  R}.
• In other words, [a] is the set of all elements
which relate to a by R.
• For example: If R is congruence mod 5, then
[3] = {..., -12, -7, -2, 3, 8, 13, 18, ...}.
• Another example: If R is equality on Q, then
[2/3] = {2/3, 4/6, 6/9, 8/12, 10/15, ...}.
• Observation: If b  [a], then [b] = [a].
A String Example
10.3.249
• Let S = {0,1} and denote L(s) = length of s, for
any string s  S*. Consider the relation:
R = {(s,t) | s,t  S* and L(s) = L(t)}
• R is an equivalence relation. Why?
• REF: For all s  S*, L(s) = L(s);
SYM: If L(s) = L(t), then L(t) = L(s);
TRAN: If L(s) = L(t) and L(t) = L(u), L(s) = L(u).
• What are the equivalence classes of R?
• [q], [0], [00], [000], [0000], ...
in other words, S0, S1, S2, S3, S4, ...
Relations and Partitions
10.3.250
• Recall that a partition of a set is a collection of
mutually disjoint subsets whose union is the
original set.
• Equivalence relations and partitions are tied
together by the following:
• Definition: Given a partition of a set A, the binary
relation induced by the partition is
R = {(x,y) | x and y are in the same partition set}.
• Theorem: If A is a set with a partition and R is the
relation induced by the partition, then R is an
equivalence relation.
Making Equivalence Relations
10.3.251
• This example shows how to apply this theorem to
create the induced equivalence relation.
• The collection {{1,2,3}, {4,5}, {6}} is a partition
of {1,2,3,4,5,6}. To find the induced equivalence
relation, observe:
• {1,2,3}  {1,2,3} = {(1,1), (1,2), (1,3), (2,1), (2,2),
(2,3), (3,1), (3,2), (3,3)}
{4,5}  {4,5}
= {(4,4), (4,5), (5,4), (5,5)}
{6}  {6}
= {(6,6)}
• R = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1),
(3,2), (3,3), (4,4), (4,5), (5,4), (5,5), (6,6)}
Formally Making
Equivalence Relations
10.3.252
• Theorem: Let A be a set partitioned by the
collection {A1, A2, A3, ...}. Then the equivalence
relation induced by the partition is given by:
R = (A1  A1)  (A2  A2)  (A3  A3) ...
• From the last example, the collection
{{1,2,3}, {4,5}, {6}} partitioned {1,2,3,4,5,6},
so the induced relation is:
R = {1,2,3}{1,2,3} {4,5}{4,5} {6}{6}
10.3.253
Equivalence Classes and Partitions
• Theorem: Let A be a set partitioned by the
collection {A1, A2, A3, ...}. If a1A1, a2A2,
a3A3, etc., then the equivalence relation
induced by the partition is given by:
R = ([a1][a1])  ([a2][a2])  ([a3][a3]) ...
• From the last example, the collection
{{1,2,3}, {4,5}, {6}} partitioned {1,2,3,4,5,6},
so the induced relation is:
R = ([1]  [1]) ([4]  [4]) ([6]  [6])
10.3.254
Going the Other Way
• Theorem: Let A be a non-empty set and let R be
an equivalence relation on A. Then the distinct
equivalence classes of R partition A.
• For example, given the relation of congruence
mod 5 on the Integers, we obtain the partition:
Z = [0] [1] [2] [3] [4].
• If S = {0,1}, what partition of S4 is induced by
R = {(s,t) | s,t  S4 and density(s) = density(t)}?
S4 = [0000][0001][0011][0111][1111]
10.3.255
Functions, Relations & Partitions
• Let f be a function defined on a set A, and
consider the relation R={(a,b) | f(a) = f(b)}.
Show R is an equivalence relation and describe
the partition of A induced by R.
• REF: f(a) = f(a) for all a  A;
SYM: If f(a) = f(b), then f(b) = f(a);
TRAN: If f(a) = f(b) and f(b) = f(c), f(a) = f(c).
• Each partition set contains those elements whose
output from f is the same.
An Example
10.3.256
• Let f be the function on Z, given by f(x) = x4 + 1.
•
x: 0 1 2 3 4 ...
f(x): 1 2 9 82 257 ...,
• This function induces the partition:
Z = {0} {-1, 1} {-2, 2}
{-3, 3} {-4,4}...
10.3.257
Graphs & Partitions
• If we generate the directed graph of an
equivalence relation just right, then the induced
partition jumps out:
3
2
6
1
4
5
Chapter 7: Functions
•
•
•
•
Functions defined on general sets;
One-to-one, onto, and inverse functions;
Composition of functions;
Cardinality and functions.
7.1.258
7.1.259
Section 1: Functions on General Sets
• Definitions: A function f from set X to set Y is a
relation such that each x in X is related to a unique
y in Y. We denote this action as f:X  Y.
• We call the set X the domain of f, denoted dom(f ),
and the set Y, the range of f, denoted ran(f ). The
set of actual elements of Y that appear as outputs
of f is called the image of f, denoted im(f ) or f(X).
• In summary, dom(f ) = X, ran(f ) = Y and
im(f ) = f(X) = {y  Y | "x  X, f(x) = y}.
Arrow Diagrams of Functions
7.1.260
• We use arrow diagrams to illustrate the behaviour
of the function:
X = {1,2,3,4} Y={a,b}
1
a
f = {(1,a),(2,a),(3,b),(4,b)}
2
3
4
1
2
3
b
a
b
X = {1,2,3} Y = {a,b}
f(A) = {a}
f = {(1,a),(2,a),(3,a)}
Equality of Functions
7.1.261
• If f:X  Y and g:X  Y are functions, then we
say f = g provided f(x) = g(x) for each x  X.
• Consider f:R  R and g:R  R given by
f(x) = (x2) and g(x) = |x|. In this instance, f = g.
• Consider f:R  R and g:R  R given by
f(x) = x (the identity function) and g(x) = |x|.
In this case, f and g are equal only for x  0, but
f(-1) = -1 and g(-1) = 1, hence f  g.
Functions on Binary Strings
7.1.262
• Let S = {0,1} represent the binary alphabet. We
consider the following functions involving binary
strings:
• Length: L:S*  N defined as L(s) = length of s.
• Density: d:S*  N defined as d(s) = # 1’s in s.
• Hamming Distance Function: H:Sn x Sn  N
defined as H(s,t) = # places where s and t
disagree.
• For example, L(101100) = 6, d(101100) = 3, and
H(101100,100110) = 2.
Hamming Distance Function
7.1.263
• The Hamming Distance function is of
fundamental importance in the world of Error
Correcting Codes, to find the distance between
binary codewords in digital communications.
• H(s,t) can be calculated in two steps:
1. Set w = s  t;
2. Calculate d(w);
• In other words: H(s,t) = d(s t).
• Thus H(101100,100110) = d(001010) = 2.
Boolean Functions
7.1.264
• We can consider the boolean functions we studied
in Chapter 1 in the context of our function
definition.
• Notation: {0,1}n = {0,1}  {0,1} ... {0,1}
(n cross products)
• Definition: An (n-place) Boolean function is any
f:{0,1}n {0,1}.
• Thus, we can think of the function
f(x,y,z) = xy + z’ as a function f:{0,1}3 {0,1}
Boolean Function Example
• In this case, the function f(x,y,z) = xy + z’ is:
111
110
101
100
011
010
001
000
0
1
7.1.265
7.1.266
Relations Which Are Not Functions
• The following is an example of a relation that is
not a function. Why?
f:R  R given by f(x) = (-x2).
Not defined for any value in the domain!
• Here is another relation that is not a function.
Why?
f:Q  Z given by f(p/q) = p.
1/2 = 2/4 = ..., but f(1/2) = 1, f(2/4) = 2, etc.
7.3.267
Section 3: One-to-one, Onto,
and Inverse Functions
• In this section, we will look at three special
classes of functions and see how their properties
lead us to the theory of counting.
• So far, we have the general notion of a function
f:X  Y, but in terms of the comparative sizes of
the three sets involved (X, Y and f ), all we can
say is that |f | = |X|.
• In this section, we compare |X| with |Y|.
One-to-one Functions
7.3.268
• Definition: A one-to-one (injective) function f
from set X to set Y is a function such that each
x in X is related to a different y in Y.
• More formally, we can restate this definition as
either: f :X  Y is 1-1 provided
f(x1) = f(x2) implies x1 = x2,
or f :X  Y is 1-1 provided
x1  x2 implies f(x1)  f(x2).
Illustrative Examples
• The function below is 1-1:
1
2
3
4
a
b
c
d
e
This function is not:
1
2
3
a
b
7.3.269
Proving Functions Are 1-1
7.3.270
• If f:R  R is given by f(x) = 3x + 7, prove it is
one-to-one.
• Proof: Assume f(a) = f(b). Show a = b.
Now f(a) = f(b) means 3a + 7 = 3b + 7, so
3a = 3b, therefore a = b.
• Why is f:R  R given by f(x) = x2 not 1-1?
• Since 9 = f(3) = f(-3), but 3  -3, the definition is
violated.
Onto Functions
7.3.271
• Definition: A function f:X  Yis said to be onto
(surjective) if for every y in Y, there is an x in X
such that f(x) = y.
• This can be restated as: A function is onto when
its image equals its range, i.e. f(X) = Y.
• Examples:
1
1
2
3
ONTO
0
1
1
2
3
2
3
4
NOT ONTO
7.3.272
Testing Onto For Infinite Functions
• Show that f:R  R given by f(x) = 5x - 7 is onto.
• Let y be in R. Then (y + 7) and (y + 7)/5 are also
real numbers.
Now f( (y + 7)/5 ) = 5[(y + 7)/5] - 7 = y, hence
if y is in R, there exists an x in R such that
f(x) = y.
• Is f:R  R given by f(x) = 1/x onto?
• No! There is no x in R that has output = 0.
One-to-one Correspondences
7.3.273
• Definition: A function is called a one-to-one
correspondence (bijection) if it is one-to-one and
onto.
• One-to-one correspondences define the theory of
counting. Why?
• If f:X  Y is one-to-one, then |X| |Y|, and if f
is onto, then |X|  |Y|, so if f is both, |X| = |Y|.
• Hence, to count the elements of an unknown set,
we create a 1-1 correspondence between the set
and a set of known size. Simple!
Inverse Functions
7.3.274
• Recall that the inverse relation is created by
inverting all the ordered pairs that comprise the
original relation.
• When is the inverse of a function itself a
function?
1
2
3
1
2
3
4
1
2
3
4
1
2
3
1
2
3
4
1
2
3
4
1-1
onto
both
not onto
not 1-1
(f -1 is a function)
(f -1 not def.) (f -1 not well-def.)
Finding Inverse Functions
7.3.275
• Theorem: If f:X  Y is a one-to-one and onto,
then f -1 is a one-to-one and onto function.
• Given f , how do we find f -1?
• Let f:R  R be given by f(x) = 4x - 1 = y. Now,
swap x and y and solve for y:
4y - 1 = x
4y = x + 1
y=x+1
4.
• Thus f -1(x) = (x + 1)/4.
7.5.276
Section 5: Composition of Functions
• Recall the Hamming distance function, which
we calculated as the density of the XOR of two
equal length binary strings.
• This functions is calculated by chaining or
composing two functions in such a way that the
output of the first becomes the input of the
second.
• This chaining process demonstrates the
composition of two functions.
Composition of Functions
7.5.277
• Definition: Let f:X  Y and g:Y  Z be
functions such that the image of f is a subset of
the domain of g. Define the new function
g  f:X  Z as (g  f )(x) = g( f (x)) for all x in X.
We call g  f the composition of f and g, putting f
first since it acts upon x first.
x
X
f (x)
Y
g  f (x)
Z
Example on Finite Sets
• Let f = {(1,4),(2,3),(3,4),(4,5),(5,6)}
and g = {(1,3),(2,5),(3,1),(4,2),(5,3),(6,4)}.
Then g  f = {(1,2),(2,1),(3,2),(4,3),(5,4)}
1
2
3
4
5
1
2
3
4
5
6
f
g
1
2
3
4
5
7.5.278
Example on Infinite Sets
7.5.279
• If f:R  R is given by f (x) = 3x + 7, and
g:R  R given by g(x) = x2, then
(g  f )(x) = g(f (x)) = g(3x + 7) = (3x + 7)2, and
(f  g )(x) = f (g(x)) = f (x2) = 3x2 + 7.
• Note: this example illustrates that in general:
(g  f )(x)  (f  g )(x),
since (3x + 7)2  3x2 + 7
Identity Functions
7.5.280
• Definition: Given a set X, the identity function on
X, iX:X  X is the function iX(x) = x.
• In pictures: If X = {1,2,3,4} then
1
2
3
4
1
2
3
4
iX
• When composing the identity function with a
general function f:X  Y, we see f  iX = f and
iY  f = f.
7.5.281
Inverse Functions
• Definition: Given a one-to-one and onto function
f:X  Y, the inverse function of f, is the function f
-1:Y  X such that f  f -1 = i and f -1  f = i .
Y
X
• In pictures:
1
2
3
4
f
1
2
3
4
f -1
1
2
3
4
Composition of 1-1 Functions
7.5.282
• Theorem: Given one-to-one functions f:X  Y,
and g:Y  Z, then the composition g  f: X  Z
is a one-to-one function.
• In pictures:
1
2
3
4
f
5
6
7
8
9
g
10
11
12
13
14
15
Composition of Onto Functions
7.5.283
• Theorem: Given onto functions f:X  Y, and
g:Y  Z, then the composition g  f: X  Z is an
onto function.
• In pictures:
X
f
Y
g
Z
Chapter 6: Counting
•
•
•
•
•
•
•
6.1.284
Counting and probability;
Possibility trees & the Multiplication Rule;
The Addition Rule;
Inclusion/Exclusion Rule;
Permutations and combinations;
Generalized permutations and combinations;
Pascal’s Triangle & Combinatorial Identities.
6.1.285
Section 1: Counting and Probablilty
• Imagine tossing a coin and noting the results
(Heads or Tails) repeatedly.
• You expect the outcome of each toss to be
independent of any previous toss.
• You expect that either H or T is equally likely at
any toss, so a given collection of outcomes
occurred at random.
• A sample space is the set of all possible outcomes
of a random process, and an event is a subset of
the sample space.
Probability
6.1.286
• If S is a finite sample space in which all outcomes
are equally likely and E is an event in S, then the
probability of event E is P(E) = |E| / |S|.
• For example, if we toss our coin twice and record
the outcomes, then S = {HH, HT, TH, TT}. Now
if we ask what is the probability the two tosses
match, then E = {HH, TT}, so P(E) = 2/4 = 0.5.
• The odds of an event are (# way for):(# ways not)
so O(E) = |E|:(|S| - |E|). Thus the odds of flipping
the coin twice to match is 2:(4 - 2) = 2:2 = 1:1.
6.1.287
Probabilities for Playing Cards
• Many interesting counting problems involve the
standard 52-card deck of playing cards: 2 red
suits (Diamonds and Hearts), 2 black suits (Clubs
and Spades) with 13 values (2, 3, 4, 5, 6, 7, 8, 9,
10, Jack, Queen, King, Ace) in each suit. The
Jack, Queen, King, and Ace cards are called face
cards.
• P(Black face card) = 8/52 = 2/13.
• P(Ace) = 4/52 = 1/13.
• P(Royal Straight Flush) = ???
Probablilties for Dice
• Consider the case of rolling two 6-sided dice:
1
2
3
4
5
6
1 2
3
4
5
6
7
2 3
4
5
6
7
8
3 4
5
6
7
8
9
4 5
6
7
8
9
10
5 6
7
8
9
10 11
6 7
8
9
10 11 12
• P(7) = 6/36 = 1/6
P(12) = 1/36
• P(at least 1 die = 6) = 11/36
6.1.288
Counting Elements in a List
6.1.289
• How many integers from 1 to 100, inclusive?
• 100 is the answer, but 100 - 1 = 99. Need to
correct for the missing endpoint.
• Theorem: If m and n are integers with m  n, then
there are (n - m + 1) integers from m to n.
• Hence 100 - 1 + 1 = 100.
• From -5 to 18?
18 - (-5) + 1 = 24.
6.2.290
Section 2: The Multiplication Rule
• Consider the game of tossing a coin, then rolling
a die, then picking a card. One possible event
would be (H, 2, 2clubs). How many events are in
the sample space?
• One way to visualize this counting problem is to
construct a possibility tree, where each
intermediate leaf branches out successively
according to the type of event generated at that
stage.
6.2.291
Coin - Die - Card Possibility Tree
(Start)
Heads
1 2 3 4 5 6
2c...As 2c...As
Tail
1 2 3 4
...
5 6
2c...As
The Multiplication Rule
6.2.292
• The total number of ways of generating output
from this last example is obtained by counting the
number of leaves at the end of the tree. Clearly in
this case the number is 2652 = 624 events.
• The Multiplication Rule: If event1 can be done e1
ways and event2 can be done e2 ways, then the
number of ways to complete event1 AND event2
is e1e2 ways.
• The key observations is that AND leads us to
multiply the counts.
License Plates
6.2.293
• Suppose Maryland issued auto license plates
using the following scheme:
Letter Letter Letter Digit Digit Digit
(where Letter = A,B,...,Z and Digit = 0,1,2,...,9).
• How many possible license plates could be issued
without duplication?
Answer: 262626101010=263103
• How about Letter Digit Letter Digit Letter Digit?
Answer: 261026102610=263103
Cartesian Products & Strings
6.2.294
• If a set A has m elements and a set B has n
elements, how many elements are in A  B?
• We view this as taking an element from A and
then taking an element from B, the multiplication
rule applies: |A  B| = |A||B| = mn.
• If S is an alphabet, how many elements in S6?
• We model this as: __ __ __ __ __ __, where each
slot can be filled in one of the elements of S.
Therefore |S6| = |S||S||S||S||S||S| = |S|6.
• In general, we see that |Sn| = |S|n.
Permutations
6.2.295
• A permutation of a collection of objects is an
ordering of the objects in a row.
• Equivalently, a permutation is a one-to-one and
onto mapping of a set to itself.
List:
abcde  acdbe
Bijective
Function:
a
b
c
d
e
a
b
c
d
e
Counting Permutations
6.2.296
• To count how many permutations (orderings) of n
things there are, consider it in terms of filling in
slots:
n (n-1) (n-2) ... 3 2 1 .
• We denote this product n(n-1)(n-2) ... 321 as
n! (read “n factorial”).
• Hence the number of different orderings of 6
distinct books on a shelf is 6! = 654321 = 720.
• We define 0! = 1 because it makes things work.
More Counting Permutations
6.2.297
• How many orderings of the letters of the word
COMPUTER are there? C O M P U T E R
Answer: 8! = 40,320
• How many orderings of the letters of the word
COMPUTER are there if the letters CO must stay
together in this order? CO M P U T E R
Answer: 7! = 5,040
• What is the probablilty the CO will appear in a
given permutation of the letters of COMPUTER?
Answer: 7!/8! = 7!/(87!) = 1/8.
6.2.298
Circular Permutations
• Permutations are a linear ordering. However, we
can ask how many ways can we order things
around a circle (or other closed polygon).
• In this case, the number of ways to arrange n
things in a circle (square, hexagon, etc.) is (n-1)!
since placing the first element does not matter.
• Consider ABCDE around a circle:
A
E
D
D
E
B
C
D
C
A
B
C
C
B
E
A
B
B
A
D
E
A
E
C
D
Partial Permutations
6.2.299
• What happens if we don’t want to list out all n
elements in a linear permutation. Suppose we
only want the first r elements, where r < n.
______ ______ ______ ... ______
n-0
n-1
n-2
n-(r-1)
• Total = n(n-1)(n-2)...(n-r+1)
= n(n-1)(n-2)...(n-r+1)[(n-r)!/(n-r)!]
= n!/(n-r)!
• We denote the partial permutation P(n,r).
• Theorem: P(n,r) = n(n-1)...(n-r+1) = n!/(n-r)!
6.2.300
Evaluating of Partial Permutations
• How many 5-letter strings can be formed from
the letters of COMPUTER?
Answer: P(8,5) = 8!/(8-5)! = 8!/3! = 87654
• How many 6-character license plates can be made
if a character can be a letter or digit, but no
character can repeat?
Answer: P(36,6) = 36!/30! = 363534333231
• When do you use which formula:
– Use n!/(n-r)! when the form of the answer counts.
– Use the expanded product to actually calculate.
Summary
6.2.301
• Multiplication Rule: If there are m ways to do A
and n ways to do B, then there are (mn) ways to
do A and B. (order matters & repetition allowed)
• Permutations (order matters & NO repetition):
– There are n! linear orderings of n things.
– There are n!/n = (n-1)! circular orderings of n things.
– There are P(n,r) = n!/(n-r)! orderings of r things from
a total of n things.
Section 3: Counting
Elements in Disjoint Sets
6.3.302
• In the last section, we looked at counting events
that branch from one state to the next. These
events we modelled using possibility trees and
obtained counts using the Multiplication Rule.
• In this section, we will learn how to count
elements in the union, difference, or intersection
of two sets using the Addition Rule.
• We will also look at counting when set
operations are acting upon subset structures.
The Addition Rule
6.3.303
• Theorem: Suppose a finite set A is partitioned by
the collection {A1, A2, ..., An}. Then:
n(A) = n(A1) + n(A2) +...+ n(An).
• How many binary strings of length up to and
including 4 are there?
Answer: G4 = S0  S1  S2  S3  S4, and
Si  Sj =  if i  j, so
|G4| = |S0| + |S1| + |S2| + |S3| + |S4|
= 2 0 + 2 1 + 22 + 23 + 2 4
= 1 + 2 + 4 + 8 + 16 = 31.
Another Example
6.3.304
• Let D be set of 3-digit integers (from 100 to 999)
which are divisible by 5. How big is D?
• Solution: We know an integer is divisible by 5 if
it ends in a 0 or 5. Let’s call a typical 3-digit
integer abc, where a is one of {1,2,3,4,5,6,7,8,9},
and b is one of {0,1,2,3,4,5,6,7,8,9}.
• Now, we partition D into those integers of the
form ab0 and those of the form ab5. The first set
has 910 elements and the second set has 910
elements, hence D has 180 elements.
License Plates
6.3.305
• We have already used the addition rule without
realizing it in the last section. When we are
counting the number of license plates with certain
properties and allow a particular character to be
either a digit or a letter, we have applied the
addition rule:
• The slot drawing
(Digit or Letter) (Digit or Letter) ...
gives us the counts (26 + 10)  (26 + 10)...
The Difference Rule
• Consider the following:
A1
6.3.306
A2
A
so |A| = |A1| + |A2|.
• Now, in the addition rule, we know |A1| and |A2|
and use this to find |A|. But if we know |A| and
either |A1| or |A2|, then we get:
• Difference Rule: If A1 and A2 partition A, then
|A2| = |A| - |A1| and |A1| = |A| - |A2|.
6.3.307
Counting Things Without a Condition
• How many 3-digit integers are not divisible by 5?
• Before, we saw that there are 180 3-digit integers
which are divisible by 5, hence:
{all 3-digit integers not divisible by 5}
=
{all 3-digit integers}
- {all 3-digit integers divisible by 5}.
• Therefore there are (999 - 100 + 1) - 180 = 720
3-digit integers which are not divisible by 5.
6.3.308
Another Complement Example
• How many ways can 4 couples sit around a
circular table if one couple cannot be seated next
to each other?
• Solution: We see that {seatings w/ couple apart}
= {all seatings} - {seating w/ couple together}
• Label the people abcdefgh and suppose couple ab
cannot sit together. Thus we want to count how to
seat Xcdefgh around a table, then repeat it since X
represents both the ab and ba orderings.
• Answer = 7! - 6! - 6! = 7! - 26!.
A Probability Example
6.3.309
• Suppose there are 10,000 total ways to carry out
an experiment with 2,123 of those experiments
leading to success. What is the probability the
experiment will fail?
• Solution: Starting from the sample space, we get:
|{all experiments}| = |{successes}| + |{failures}|,
• Dividing boths sides by the LHS, we see that:
1 = P(success) + P(failure), so
P(failure) = 1 - P(success) = 1 - 0.2123 = 0.7877.
• We find there is a 78.77% probability of failure.
Inclusion/Exclusion Rule
6.3.310
• So far, our counting under the addition and
subtraction rules have required that the files in
question are disjoint.
• This is an unreasonable requirement in general.
• How do we account for the aggregrate knowing
the parts that make it up?
AB
A
AB
B
• Inclusion/Exclusion Rule: For any sets A and B,
|A  B| = |A| + |B| - |A  B|.
Inclusion/Exclusion Example
6.3.311
• How many 6-character license plates begin with
“A” or end with “9”?
• Effectively, we want to count all plates of the
forms Axxxxx or xxxxx9, but recognizing that
these individual cases overlap for plates of the
form Axxxx9.
• Now |{Axxxxx}| = 365, and |{xxxxx9}| = 365, and
|{Axxxx9}| = 364, hence the total number of plates
is 2365 - 364.
What About For 3 Sets?
1
4
6
7
3
2
5
6.3.312
• Using the labeling in the
above drawing, we see that
A = 1  4  6  7,
B = 2  4  5  7,
and C = 3  5  6  7.
• Thus |A  B  C|
= |A| + |B| + |C| (1+4+6+7+2+4+5+7+3+5+6+7)
- |AB| - |AC| - |BC| (-4-7-5-7-6-7)
+ |ABC| (+7)
• 1+4+6+7+2+4+5+7+3+5+6+7-4-7-5-7-6-7+7
= 1+2+3+4+5+6+7.
6.3.313
Inclusion/Exclusion Rule for 3 Sets
• If A, B, and C are sets, then: |A  B  C| =
|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC|.
• Example: The CS department teaches Algol,
Basic, and C languages. Suppose:
–
–
–
–
–
22 students study Algol; 30 study Basic; 42 study C;
12 study Algol and Basic;
18 study Basic and C;
16 study Algol and C;
9 study all three.
• How many students study a language?
• Answer: 57 = 22+30+42-12-18-16+9.
Section 4: Counting
Subsets of a Set
6.4.314
• In Section 2, we looked at counting events with
or without repetition, but in either instance the
order of the elements mattered.
• Now, we shall relax the order restriction to allow
counting set structures where events are not
distinguished by the order of elements, but by
the mere clustering of elements together.
• This will lead to the last rule, the Division Rule
(not in the text!).
The Division Rule
6.4.315
• Theorem: Suppose a set A has n elements and is
partitioned by the collection {A1, A2, ..., Ap},
where each partition set has m elements. Then:
p = n/m.
• In other words, if a set is partitioned into equalsized partition sets, then the number of partition
sets is the quotient of the size of the set with the
size of any partition set.
• For example, if a set has 100 elements and is
partitioned in 20-element subsets, then there must
be 5 subsets (equivalence classes).
Counting Subsets
6.4.316
• How many 3-element subsets of a 4-element set
are there:
• Let A = {1,2,3,4} then all 3-permutations are:
123, 132, 213, 231, 312, 321  {1,2,3}
124, 142, 214, 241, 412, 421  {1,2,4}
134, 143, 314, 341, 413, 431  {1,3,4}
234, 243, 324, 342, 423, 432  {2,3,4}.
• Hence # 3-element subsets
= (# 3-permutations) / (# 3-orderings)
= P(4,3) / 3! = 4! / (1!3!) = 4! / 3! = 4.
Combinations
6.4.317
• What we have just counted is a combination. In
this instance, it was a combination of 4 elements
taken 3 at a time.
• We use the Division Rule to negate the order
condition of the permutation counts.
• In general, C(n,k) = P(n,k) / k!
• Equivalently, we use the “choose” notation to get:
n
k
()=
n!
k!(n - k)!
More Counting Subsets
6.4.318
• How many subsets of a 10-element set have 3
elements? How many have 7 elements?
• Solution:
C(10,3) = 10! / (3!7!)
C(10,7) = 10! / (7!3!), the same!
• Note: Counting subsets containing 3 elements is
the same as counting subsets NOT containing the
other 7 elements!
• Theorem: C(n,k) = C(n,n-k).
• How many subsets have at least 8 elements?
• Solution: C(10,8) + C(10,9) + C(10,10)
Counting Binary Strings
6.4.319
• How many 10-bit strings have three 1’s?
• Solution: We model this as requiring us to choose
three of the ten slots to place a 1 then the other
seven remaining slots will get a 0. Thus the
number of 10-bit strings that have three 1’s is
C(10,3) = 10! / (3!7!).
• In general, the number of n-bit binary strings with
density k is C(n,k).
• As before, having k 1’s is the same thing as
having (n - k) 0’s.
Counting Teams
6.4.320
• Suppose a group of 5 men and 7 women want to
pick a 5-person team.
• How many teams can they make with 3 men and 2
women?
• C(5,3)C(7,2) = [5!/(3!2!)][7!/(5!2!)] = 7!/(3!2!2!).
• How many teams have at least 1 man?
• (All - teams w/no man) = C(12,5) - C(7,5)
= [12!/(7!5!)] - [7!/(5!2!)]
• How many teams have at most 1 man?
• (teams w/no man) + (teams w/1 man)
= C(7,5) + C(5,1)C(7,4) = 7!/(5!2!) + [5!/4!][7!/(3!4!)]
Generalized Permutations
6.4.321
• In Section 2, we learned how to count the number
of orderings of the letters of COMPUTER. What
about the number of orderings of the letters of
MISSISSIPPI?
• In this case, we note that not all the letters are
distinct. In particular,
MISSISSIPPI  IIIISSSSPPM,
so although we are still searching for an ordering
structures, there are sub-unorderings present,
induced by the repeated letters, for which we have
to account.
Generalized Permutations Take 1
6.4.322
• Let’s apply the Division Rule to negate the effect
of the unordering portions of the overall order
problem.
• This leaves us with a total count of 11!/4!4!2!.
• Here, the first quotient of 4! “mods” out the effect
of the unordered I’s, the second quotient of 4!
“mods” out the effect of the unordered S’s, and the
last quotient of 2! “mods” out the effect of the
unordered P’s.
Generalized Permutations Take 2
6.4.323
• If we model this problem, purely as a combination,
and not a permutation at all, we can reason the task
as:
1. Choose 4 slots from 11 for the I’s;
2. Choose 4 slots from the remaining 7
for the S’s;
3. Choose 2 slots from the remaining 3
for the P’s;
4. Place the M (only 1 way remaining).
• This yields: C(11,4)C(7,4)C(3,2)C(1,1) =
(11!7!3!)/(7!4!4!3!2!1!) = 11!/(4!4!2!).
6.4.324
Generalized Permutation Theorem
• Theorem: Suppose a collection consists of n
objects of which:
n1 are of type 1, indistinguishable from each other;
n2 are of type 2, indistinguishable from each other;
...
nk are of type k, indistinguishable from each other;
and n1 + n2 + ... + nk = n. Then the number of
distinct permutations of the n objects is:
C(n,n1)C(n-n1,n2)C(n-n1-n2,n3)...C(nk,nk) =
n! / (n1!n2!n3!...nk!).
Section 5: Combinations
with Repetition
6.5.325
• In the last section, we saw how to count
combinations, where order does not matter,
based on permutation counts, and we saw how to
count permutations where repetitions occur.
• Now, we shall consider the case where we don’t
want order to matter, but we will allow
repetitions to occur.
• This will complete the matrix of counting
formulae, indexed by order and repetition.
A Motivating Example
6.5.326
• How many ways can I select 15 cans of soda
from a cooler containing large quantities of Coke,
Pepsi, Diet Coke, Root Beer and Sprite?
• We have to model this problem using the chart:
Coke Pepsi Diet Coke Root Beer Sprite
A: 111 111
111
111
111 =15
B: 11
111111
111111
1 =15
C:
1111 1111111
1111
=15
• Here, we set an order of the categories and just
count how many from each category are chosen.
6.5.327
A Motivating Example (cont’d.)
• Now, each event will contain fifteen 1’s, but we
need to indicate where we transition from one
category to the next. If we use 0 to mark our
transitions, then the events become:
A: 1110111011101110111
B: 1100111111011111101
C: 0011110111111101111
• Thus, associated with each event is a binary
string with #1’s = #things to be chosen and #0’s =
#transitions between categories.
6.5.328
Counting Generalized Combinations
• From this example we see that the number of ways
to select 15 sodas from a collection of 5 types of
soda is C(15 + 4,15) = C(19,15) = C(19,4).
• Note that #zeros = #transitions = #categories - 1.
• Theorem: The number of ways to fill r slots from n
catgories with repetition allowed is:
C(r + n - 1, r) = C(r + n - 1, n - 1).
• In words, the counts are:
C(#slots + #transitions, #slots)
or
C(#slots + #transitions, #transitions).
6.5.329
Another Example
• How many ways can I fill a box holding 100
pieces of candy from 30 different types of candy?
Solution: Here #slots = 100, #transitions = 30 - 1,
so there are C(100+29,100) = 129!/(100!29!)
different ways to fill the box.
• How many ways if I must have at least 1 piece of
each type?
Solution: Now, we are reducing the #slots to
choose over to (100 - 30) slots, so there are
C(70+29,70) = 99!/70!29!
When to Use Generalized
Combinations
6.5.330
• Besides categorizing a problem based on its order
and repetition requirements as a generalized
combination, there are a couple of other
characteristics which help us sort:
– In generalized combinations, having all the slots filled
in by only selections from one category is allowed;
– It is possible to have more slots than categories.
6.5.331
Integer Solutions to Equations
• One other type of problem to be solved by the
generalized combination formula is of the form:
How many non-negative integer solutions
are there to the equation a + b + c + d = 100.
• In this case, we could have 100 a’s or 99 a’s and
1 b, or 98 a’s and 2 d’s, etc.
• We see that the #slots = 100 and we are ranging
over 4 categories, so #transitions = 3.
• Therefore, there are C(100+3,100) = 103!/100!3!
non-negative solutions to a + b + c + d = 100.
6.5.332
Integer Solutions with Restrictions
• How many integer solutions are there to:
a + b + c + d = 15,
when a  3, b  0, c  2 and d  1?
• Now, solution “strings” are 111a0b011c01d,
where the a,b,c,d are the remaining numbers of
each category to fill in the remaining slots.
• However, the number of slots has effectively been
reduced to 9 after accounting for a total of 6
restrictions.
• Thus there are C(9+3,9) = 12!/(9!3!) solutions.
6.5.333
More Integer Solutions & Restrictions
• How many integer solutions are there to:
a + b + c + d = 15,
when a  -3, b  0, c  -2 and d  -1?
• In this case, we alter the restrictions and equation
so that the restrictions “go away.” To do this, we
need each restriction  0 and balance the number
of slots accordingly.
• Hence a  -3+3, b  0, c  -2+2 and d  -1+1,
yields a + b + c + d = 15+3+2+1 = 21
• So, there are C(21+3,21) = 24!/(21!3!) solutions.
6.5.334
Summary
• Theorem: The number of integer solutions to:
a1 + a2 + a3 +...+ an = r,
when a1  b1, a2  b2, a3  b3 , ..., an  bn is
C(r+n-1-b1-b2-b3-...-bn , r-b1-b2-b3-...-bn).
• Theorem: The number of ways to select r things
from n categories with b total restrictions on the r
things is C(r + n - 1 - b , r - b).
• Corollary: The number of ways to select r things
from n categories with at least 1 thing from each
category is C(r - 1 , r - n) (set b = n).
6.6.335
Section 6: The Algebra
of Combinations
• In this section, we will look at some identities
involving the choosery function. We will also
resurrect Pascal’s Triangle and see how it relates
to combinations.
• Three Simple Calculations:
C(n,n) = n! / [n!(n-n)!] = n!/(n!0!) = n!/n! = 1.
C(n,1) = n! / [1!(n-1)!] = [n(n-1)!] / (n-1)! = n.
C(n,2) = n! / [2!(n-2)!] = [n(n-1)(n-2)!] / [2(n-2)!]
= n(n-1)/2.
6.6.336
A Half-empty Set
• We have already seen and used the identity:
C(n,r) = C(n,n-r).
• This identity is easy to demonstrate algebraically.
• However, we can reason it combinatorically.
• We use C(n,r) to count how many subset of size r
an n-element set A has. But we can identify
uniquely with any r-element subset B of A the
(n-r)-element subset that is its complement,
A-B. Moreover, this identification is a bijection.
(Why?) Hence, the number of r-element subsets
equals the number of (n-r)-element subsets.
6.6.337
Using Substitutions
• We have seen the identity C(n,2) = n(n-1)/2.
• Combining this with C(n,2) = C(n,n-2), we see
that C(n,n-2) = n(n-1)/2.
• We can now use this to get related identities by
substituting “interesting” values for n:
n  n+1: C(n+1,n-1) = n(n+1)/2.
n  n-1: C(n-1,n-3) = (n-1)(n-2)/2.
n  n+2: C(n+2,n) = (n+2)(n+1)/2.
Pascal’s Triangle
6.6.338
Recall the number array we call Pascal’s Triangle:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
Rule of generation: T(n,r) = T(n-1,r-1) + T(n-1,r).
Using Pascal’s Triangle
6.6.339
• One application of Pascal’s Triangle is to find the
coefficients of the binomial expansion (a + b)n.
• For example, to expand (a + b)5 we look at the
6th row: 1,5,10,10,5,1 to get:
1a5 + 5a4b + 10a3b2 + 10a2b3 + 5ab4 + 1b5.
• However, the Binomial Theorem tells us each of
these coefficients is of the form C(5,r).
• Thus each term of Pascal’s Triangle is actually a
combination, that is T(n,r) = C(n,r).
Pascal’s Formula
6.6.340
• Now, if we replace the the T(n,r) terms of the rule
of generation with the binomial coefficients, we
get:
C(n,r) = C(n-1,r-1) + C(n-1,r).
• Proof: C(n-1,r-1) + C(n-1,r)
= (n-1)!/(r-1)!(n-1-r+1)! + (n-1)!/r!(n-r-1)!
= (n-1)!/(r-1)!(n-r)! + (n-1)!/r!(n-r-1)!
[want (r-1)!  r! want (n-r-1)!  (n-r)!]
= (n-1)!r/r!(n-r)! + (n-1)!(n-r)/r!(n-r)!
= [(n-1)!(r + n - r)] / r!(n-r)!
= (n-1)!n / r(n-r)! = n!/r!(n-r)! = C(n,r).
8.1.341
Chapter 8: Recursion
• Recursively defined sequences;
• The Iteration Method to solve recurrence
relations;
• Solve linear, homogeneous recurrence relations;
• Count Fibonacci’s bunnies.
Section 1: Recursively Defined
Sequences
8.1.342
• In Chapter 4, we looked at sequences, although
most of them were generated by a function.
• In this section, we will study sequences where
new terms are calculated based on the values of
predecessor terms.
• Definition: A recurrence relation for a sequence
a1, a2, ..., an, is a formula that calculates each
term ak in terms of ak-1,ak-2,...,ak-i, for some
integer i. The initial conditions for a recurrence
relation specify values for a1, a2, ..., ak-1.
8.1.343
Examples of Recurrence Relations
• To actually determine the sequence specified by a
recurrence relation, you need:
(1) the relation:
an = an-1 + an-2, and
(2) initial conditions:
a0 = 1 and a1 = 3.
This example yields the sequence:
1, 3, 4, 7, 11, 18, 29, ...
• If we keep the same recurrence relation, but
change our initial conditions (say a0 = 2, a1 = -5),
we get a completely different sequence:
2, -5, -3, -8, -11, -19, -30, ...
8.1.344
Different Representations
• We can specify a sequence using essentially the
same recurrence relation, but in different ways if
we get “unstuck” in time.
• Consider these two descriptions of the same
sequence:
(1) sk = (3sk-1 - 1), for all integers k  1;
(2) sk+1 = (3sk - 1), for all integers k  0.
• If we let s1 = 1, (1) becomes 1, 2, 5, 14, 41, ...
• If we let s0 = 1, (2) becomes 1, 2, 5, 14, 41, ...
8.1.345
The Tower of Hanoi
• Here is a game that generates a recurrence
relation.
• The Tower of Hanoi consist of a collection of
disks with holes in the middle placed on a board
with three vertical posts. The disks are such that
they can be placed on a single post and from the
bottom up, each successive disk has decreasing
diameter.
8.1.346
The Tower of Hanoi (cont’d.)
• The game is to move the tower of disks from one
post to another using the rules that you can only
move 1 disk at a time and you cannot place a disk
of larger diameter on top of a smaller disk.
• How many moves (mn) will it take to solve the ndisk Tower of Hanoi?
• Clearly m1 = 1.
• Now, claim m2 = 3. Why?
• (1,2)()()  (2)(1)()  ()(1)(2)  ()()(1,2).
8.1.347
The Tower of Hanoi (cont’d.)
• How about the 3-disk Tower of Hanoi?
• (1,2,3)()()  (2,3)(1)()  (3)(1)(2)  (3)()(1,2)
()(3)(1,2)  (1)(3)(2)  (1)(2,3)()
 ()(1,2,3)().
• Thus, m3 = 7.
• This example illustrates the recursive nature of
the game: To solve the 3-disk problem, we solve
the 2-disk problem, then move disk 3, then solve
the 2-disk problem again. So m3 = 2m2 + 1.
• Continuing this logic, we see mn= 2mn-1 + 1.
8.1.348
Fibonacci Numbers
• Leonardo of Pisa, son of Bonacci (and hence,
Fibonacci), posed the following in 1202:
– A single pair of rabbits (a male and a female) are born
at the beginning of the year. Rabbit pairs are fertile one
month after their birth, and produce one mixed pair
each month thereafter. The rabbit population suffers no
deaths during the course of the year.
• How many rabbits will there be at the end of the
year?
• Clearly, at the end of any given month:
#rabbits = #alive at the beginning + #babies.
8.1.349
Fibonacci Numbers (cont’d.)
• Suppose the number of pairs of rabbits alive at the
beginning of month k is Fk. Then:
(a)
F0 = 1
(A)
F1 = 1
(A,b)
F2 = 1 + 1 = 2
(A,B,c)
F3 = 1 + 1 + 1 = 3 = F2 + 1 = F2 + F1
(A,B,C,d,e) F4 = 3 + 1 + 1 = 3 + 2 = 5 = F3 + F2
(A,B,C,D,E,f,g,h) F5 = 5 + 3 = F4 + F3.
• In general:
Fk = Fk-1 + Fk-2 , so the sequence is:
1,1,2,3,5,8,13,21,34,55,89,144,233 = 1 year!
8.1.350
Solving Recurrence Relations
• The last example nicely illustrates why we want to
“solve” recurrence relations; that is, obtain an
expression for the general term (Fn) that only
depends on n and not Fn-1, Fn-2, Fn-3, ...
• To find a term like F13, it requires us to find all the
predecessor terms, a tedious and uninteresting task.
• What if we had to find F1,000,000?????
• From here on, we will develop methods to solve
recurrence relations, so we won’t need to plug in
values again and again.
8.2.351
Section 2: Solving Recurrence
Relations by Iteration
• As we noted at the end of the last lecture, when
analyzing recurrence relations, we want to rewrite
the general term as a function of the index and
independent of predecessor terms.
• This will allow us to compute any arbitrary term
in the sequence without having to compute all the
previous terms.
• In this section, we will look at one method for
solving recurrence relations.
8.2.352
The Method of Iteration
• Let {ai} be the sequence defined by:
ak = ak-1 + 2
with a0 = 1.
• Plugging values of k into the relation, we get:
a1 = a0 + 2 = 1 + 2
a2 = a1 + 2 = 1 + 2 + 2 = 1 + 2(2)
a3 = a2 + 2 = 1 + 2 + 2 + 2 = 1 + 3(2)
a4 = a3 + 2 = 1 + 2 + 2 + 2 + 2 = 1 + 4(2)
• Continuing in this fashion reinforces the apparent
pattern that an = 1 + n(2) = 1 + 2n.
• This brute force technique is the Method of
Iteration.
8.2.353
The Tower of Hanoi
• Recall the Tower of Hanoi relation:
mk = 2mk-1 + 1 with m1 = 1.
• Plugging values of k into the relation, we get:
m2 = 2m1 + 1 = 2 + 1
m3 = 2m2 + 1 = 2(2 + 1) + 1 = 22 + 2 + 1
m4 = 2m3 + 1 = 2(22 + 2 + 1) + 1
= 23 + 2 2 + 2 + 1
m5 = 2m4 + 1 = 2(23 + 22 + 2 + 1)
= 24 + 23 + 22 + 2 + 1.
• Thus, we guess: mn = 2n-1 + 2n-2 +...+ 22 + 2 + 1.
• This is a Geometric Series, so mn = 2n - 1.
8.2.354
Another Example
• Let {ai} be the sequence given by:
ak = ak-1 + k
with a0 = 0.
• Solve this recurrence relation and find a100.
• Now,
a1 = a0 + 1 = 1 + 0
a2 = a1 + 2 = 2 + 1 + 0
a3 = a2 + 3 = 3 + 2 + 1 + 0
a4 = a3 + 4 = 4 + 3 + 2 + 1 + 0
• Thus
an = n + (n-1) + (n-2) +...+ 3 + 2 + 1 + 0
so
an = n(n+1)/2.
• Plugging in n = 100: a100 = 100(101)/2 = 5050.
8.2.355
A Geometric Sequence
• Let a and b be non-zero constants, and consider:
sk = ask-1
with s0 = b.
• Thus: s1 = as0 = ab
s2 = as1 = a(ab) = a2b
s3 = as2 = a(a2b) = a3b
s4 = as3 = a(a3b) = a4b.
• From this, we can make the conjecture that:
sn = anb.
• Note: if b = 1, then sn = an.
8.2.356
A Perturbed Geometric Sequence
• Let a be non-zero constants, and consider:
sk = ask-1 + 1
with s0 = 1.
• Thus: s1 = as0 + 1 = a + 1
s2 = as1 + 1 = a(a + 1) + 1 = a2 + a + 1
s3 = as2 + 1 = a(a2 + a + 1) + 1
= a3 + a2 + a + 1
s4 = as3 + 1 = a(a3 + a2 + a + 1)
= a4 + a3 + a2 + a + 1.
• It appears that sn = an + an-1 +...+ a2 + a + 1, so
sn = (an+1 - 1) / (a - 1) .
8.2.357
Some Observations
• In solving these recurrence relations, we point out
the following observations:
1. Each recurrence relation looks only 1 step back; that is
each relation has been of the form sn = F(sn-1);
2. We have relied on luck to solve the relation, in that we
have needed to observe a pattern of behavior and
formulated the solution based on the pattern;
3. The initial condition has played a role in making this
pattern evident;
4. Generating a formula from the generalization of the
pattern looks back to our study of induction.
8.2.358
Verifying Solutions
• Once we “guess” the form of the solution for a
recurrence relation, we need to verify it is, in fact,
the solution.
• We use Mathematical Induction to do this.
• For example, in the Tower of Hanoi game, we
conjecture that the solution is mn = 2n -1.
• Basis Step: m1 = 1 (by playing the game), and
21 - 1 = 2 - 1 = 1, therefore m1 = 21 -1.
• Inductive Step: Recall the recurrence relation is
mk = 2mk-1 + 1. Assume mk = 2k - 1.
8.2.359
Verifying Solutions (cont’d.)
• Inductive Step: Show mk+1 = 2k+1 - 1.
Now, mk+1 = 2mk + 1
= 2(2k - 1) + 1
= 22k - 2 + 1
= 2k+1 - 1.
Therefore mk = 2k - 1 is the solution to
mk = 2mk-1 + 1, when m1 = 1. QED
• A similar verification process will work for all the
other formulas we discovered in this section.
8.3.360
Section 3: Linear, Homogeneous
Recurrence Relations
• So far, we have seen that certain simple
recurrence relations can be solved merely by
interative evaluation and keen observation.
• In this section, we seek a more methodical
solution to recurrence relations.
• In particular, we shall introduce a general
technique to solve a broad class of recurrence
relations, which will encompass those of the last
section as well as the tougher Fibonnaci relation.
8.3.361
Linear, Homogeneous Recurrence
Relations with Constant Coefficients
• If A and B (0) are constants, then a recurrence
relation of the form: ak = Aak-1 + Bak-2
is called a linear, homogeneous, second order,
recurrence relation with constant coefficients.
• We will use the acronym LHSORRCC.
• Linear: All exponents of the ak’s are 1;
• Homogeneous: All the terms have the same
exponent.
• Second order: ak depends on ak-1 and ak-2;
8.3.362
Higher Order Linear, Homogeneous
Recurrence Relations
• If we let C1, C2, C3, ..., Cn be constants (Clast 0),
we can create LHRRCC’s of arbitrary order.
• As we shall see, the techniques the book develops
for second order relations generalizes nicely to
higher order recurrence relations.
• Third order: ak = C1ak-1 + C2ak-2 + C3ak-3
• Fourth order: ak = C1ak-1 + C2ak-2 + C3ak-3 + C4ak-4
• nth order: ak = C1ak-1 + C2ak-2 + ... + Cnak-n;
8.3.363
Solving LHSORRCC’s
• Let’s start with the second order case before we
generalize to higher orders.
• Definition: Given ak = Aak-1 + Bak-2, the
characteristic equation of the recurrence relation
is x2 = Ax + B, and the characteristic polynomial
of the relation is x2 - Ax - B.
• Theorem: Given ak = Aak-1 + Bak-2, if s,t,C,D are
non-zero real numbers, with s  t, and s,t satisfy
the characteristic equation of the relation, then its
General Solution is an = C(sn)+ D(tn).
8.3.364
An Example
• Let ak = 5ak-1 - 6ak-2. Find the general solution.
• The relation has characteristic equation:
x2 = 5x - 6,
so
x2 - 5x + 6 = 0
hence
(x - 2)(x - 3) = 0
implying either (x - 2) = 0 or (x - 3) = 0
thus
x = 2,3
• General Solution is an = C(2n) + D(3n).
8.3.365
Finding Particular Solutions
• Once we have found the general solution to a
recurrence relation, if we have a sufficient number
of initial conditions, we can find the particular
solution.
• This means we find the values for the arbitrary
constants C and D, so that the solution for the
recurrence relation takes on those initial
conditions.
• The required number of initial conditions is the
same as the order of the relation.
8.3.366
An Example
• For the last example, we found the recurrence
relation ak = 5ak-1 - 6ak-2 has general solution
an = C(2n) + D(3n). Find the particular solution
when a0 = 9 and a1 = 20.
a0 = C(20)+ D(30) = C + D = 9
a1 = C(21)+ D(31) = 2C + 3D = 20, so
2C + 2D = 18
2C + 3D = 20, so D = 2 and C = 7.
Therefore, the particular solution is:
an = 7(2n) + 2(3n).
8.3.367
Generalizing These Methods
• We can extend these techniques to higher order
LHRRCC quite naturally. Suppose we have a
LHRRCC whose charateristic poylnomial has
roots x = 2, -3,5,7,11, and 13. Then its general
solution is:
an = C2n + D(-3)n + E5n + F7n + G11n + H13n.
• Moreover, if we have initial conditions specified
for a0, a1, a2, a3, a4, and a5, we can plug them into
the general solution and get a 66 system of
equations to solve for C, D, E, F, G, and H.
8.3.368
Solving The Fibonacci Relation
• Solve: an = an-1 + an-2 when a0 = 1 and a1 = 1.
• Solution: In this case, the characteristic polynomial
is x2 - x - 1, which doesn’t factor nicely. We turn to
the quadratic formula to find the roots.
• Quadratic Formula: If ax2 + bx + c = 0, then
x = [-b   (b2 - 4ac)]/2a.
• In our case, we have a = 1, b = -1 and c = -1, so
x = [-(-1)  ((-1)2 - 4(1)(-1))]/2(1) = (1  5)/2.
• Thus an = C[(1 + 5)/2]n + D[(1 - 5)/2]n.
8.3.369
Solving The Fibonacci Relation (cont’d.)
• If we apply the initial conditions a0 = 1 and a1 = 1
to an = C[(1 + 5)/2]n + D[(1 - 5)/2]n, we get:
a0 = C + D = 1
a1 = [(1 + 5)/2]C + [(1 - 5)/2]D = 1, yielding
C = (1 + 5)/(25) and D = -(1 - 5)/(25).
• Therefore an = [(1 + 5)/(25)][(1 + 5)/2]n +
[-(1 - 5)/(25)][(1 - 5)/2]n
• This simplifies to
an = (1/5){[(1 + 5)/2]n+1 - [(1 - 5)/2]n+1
8.3.370
Single Root Case
• So far, our technique for solving LHSORRCCs
has depended on the fact that the two roots of the
characteristic polynomial are distinct.
• This is not always the case, however. We can find
that a polynomial has only one root, s, whenever
the polynomial factors as (x - s)2.
• In this case, our solution takes on a special variant
to ensure “linear independence” of the solutions.
• Theorem: If an LHSORRCC has a repeated root s,
then the general solution is an = (A + Bn)sn.
8.3.371
Single Root Case Example
• Find the general solution of an - 6an-1 + 9an-2 = 0.
• This LHSORRCC has a characteristic polynomial
equation of x2 - 6x + 9 = 0, so (x - 3)2 = 0, which
yields the sole root x = 3.
• Therefore, the general solution is an = (A + Bn)3n.
• If we add initial conditions a0 = 2 and a1 = 21, we
get: a0 = (A + B(0))30 = A = 2, and
a1 = (A + B(1))31 = 3(A + B) = 3(2 + B) = 21,
so 2 + B = 7, hence B = 5.
• Therefore the particular solution is an = (2 + 5n)3n
8.3.372
Higher Order Repeated Root Case
• This method of building up the “coefficient” when
the variable part degenerates because of repeated
roots extends nicely to higher order problems as
well.
• Example: If a LHRRCC has characteristic
polynomial with roots x = 7,7,7,7,7,7,7,9,9,9 then
its general solution is:
• an = (A + Bn + Cn2 + Dn3 + En4 + Fn5 + Gn6)7n
+ (H + In + Jn2)9n.
• How many IC are needed for a particular solution?
Summary
8.3.373
• Our general technique for solving LHRRCCs is a
two-step process.
• Step 1: Find the roots of the characteristic
polynomial and use them to develop the general
solution.
How do I find roots of polynomials?
• Step 2: Use the initial conditions to make and
solve a system of linear equations that determine
the arbitrary constants in the general solution to
get the particular solution.
How do I solve systems of linear equations?
8.3.374
Board Example #1
• Given the recurrence relation an =4an-1 - 3an-2,
find a999 when a0 = 5 and a1 = 7.
8.3.375
Board Example #2
• Given the recurrence relation an =4an-1 - 4an-2,
find a999 when a0 = 5 and a1 = 7.
8.3.376
Board Example #3
• What is the general solution for the LHRRCC
whose characteristic polynomial is:
(x + 5)6(x - 3)4(x + 8)2
8.3.377
Board Example #4
• Given the LHRRCC an =2an-1 +5an-2 - 6an-3, find
a999 when a0 = 17, a1 = 14, and a2 = 110.
Validity of the General Solution I
8.3.378
Prove: If Aan + Ban-1 + Can-2 =0, and s  t satisfy
Ax2 + Bx + C = 0, then ak = Msk + Ntk satisfies the
relation.
Proof: Let Aan +Ban-1 +Can-2 =0, and s  t satisfy
Ax2 + Bx + C = 0. Thus:
As2 + Bs + C = At2 + Bt + C = 0.
Now, an = Msn + Ntn, an-1 = Msn-1 + Ntn-1, and
an-2 = Msn-2 + Ntn-2 hence Aan +Ban-1 +Can-2
= A(Msn + Ntn) +B(Msn-1 + Ntn-1) +C(Msn-2 + Ntn-2)
= M(Asn + Bsn-1 + Csn-2) + N(Atn + Btn-1 + Ctn-2)
= Msn-2(As2 + Bs + C) + Ntn-2(At2 + Btn-1 + C) =
Validity of the General Solution II
8.3.379
Prove: If Aan + Ban-1 + Can-2 =0, and s is the only
solution of Ax2 + Bx + C = 0, then ak = (P + Qk)sk
satisfies the relation.
Proof: Let Aan +Ban-1 +Can-2 =0, and s be the only
solution of Ax2 + Bx + C = 0, so As2 + Bs + C = 0.
Now, an = (P + Qn)sn, an-1 = [P + Q(n-1)]sn-1, and
an-2 = [P + Q(n-2)]sn-2 hence Aan +Ban-1 +Can-2
= A(P + Qn)sn +B[P + Q(n-1)]sn-1
+C[P + Q(n-2)]sn-2
= P(Asn + Bsn-1 + Csn-2)
+ Q[Ansn + B(n-1)sn-1 + C(n-2)sn-2]
Validity of the General Solution II
8.3.380
Thus, Aan +Ban-1 +Can-2
= Psn-2(As2 + Bs + C) + Q(Ansn + Bnsn-1 - Bsn-1
+ Cnsn-2 - 2Csn-2)
= Qnsn-2(As2 + Bs + C ) + Qsn-2(-Bs - 2C)
= Qsn-2(-Bs - 2C) = 0?????
However, since s is the only root of the characteristic
polynomial, from the Quadratic Formula, we have
that (B2 - 4AC) = 0 and s = -B/2A.
Thus (-Bs - 2C) = -B(-B/2A) - 2C
= B2/2A - 2C(2A/2A) = (B2 - 4AC)/2A = 0. QED