Done, your profile is created.Finish your profile by filling in the following fields
Forgot Password Earn Money,Free Notes
Password sent to your Email Id, Please Check your Mail
Updating Cart........ Please Wait........
Lecture Notes on Discrete Mathematics
lecture notes discrete mathematics and its applications and discrete mathematics for computer science lecture notes pdf free download
Miguel A. LermaContents
Chapter 1. Logic, Proofs 6
1.1. Propositions 6
1.2. Predicates, Quantiﬁers 11
1.3. Proofs 13
Chapter 2. Sets, Functions, Relations 19
2.1. Set Theory 19
2.2. Functions 27
2.3. Relations 32
Chapter 3. Algorithms, Integers 38
3.1. Algorithms 38
3.2. The Euclidean Algorithm 48
3.3. Modular Arithmetic, RSA Algorithm 52
Chapter 4. Induction, Recurences 59
4.1. Sequences and Strings 59
4.2. Mathematical Induction 62
4.3. Recurrence Relations 65
Chapter 5. Counting 69
5.1. Basic Principles 69
5.2. Combinatorics 71
5.3. Generalized Permutations and Combinations 73
5.4. Binomial Coeﬃcients 75
5.5. The Pigeonhole Principle 77
Chapter 6. Probability 78
6.1. Probability 78
Chapter 7. Graph Theory 82
7.1. Graphs 82
7.2. Representations of Graphs 88
7.3. Paths and Circuits 91
7.4. Planar Graphs 97
Chapter 8. Trees 100
8.1. Trees 100
8.2. Binary Trees 102
8.3. Decision Trees, Tree Isomorphisms 104
8.4. Tree Transversal 113
8.5. Spanning Trees 116
Chapter 9. Boolean Algebras 122
9.1. Combinatorial Circuits 122
9.2. Boolean Functions, Applications 127
Chapter 10. Automata, Grammars and Languages 133
10.1. Finite State Machines 133
10.2. Languages and Grammars 137
10.3. Language Recognition 144
Appendix A. 150
A.1. Eﬃcient Computation of Powers Modulo m 150
A.2. Machines and Languages 152Introduction
These notes are intended to be a summary of the main ideas in
course CS 310: Mathematical Foundations of Computer Science. I
may keep working on this document as the course goes on, so these
notes will not be completely ﬁnished until the end of the quarter.
The textbook for this course is Keneth H. Rosen: Discrete Mathe-
matics and Its Applications, Fifth Edition, 2003, McGraw-Hill. With
few exceptions I will follow the notation in the book.
These notes contain some questions and “exercises” intended to
stimulate the reader who wants to play a somehow active role while
at all if the reader does not wish to. I will recommend exercises and
give homework assignments separately.
Finally, ifyouﬁndanytyposorerrors, oryouhaveanysuggestions,
please, do not hesitate to let me know.
Miguel A. Lerma
A proposition is a declarative sentence that is either true or false
(but not both). For instance, the following are propositions: “Paris
is in France” (true), “London is in Denmark” (false), “2 4” (true),
“4 = 7 (false)”. However the following are not propositions: “what
is your name?” (this is a question), “do your homework” (this is a
command), “this sentence is false” (neither true nor false), “x is an
even number” (it depends on what x represents), “Socrates” (it is not
even a sentence). The truth or falsehood of a proposition is called its
1.1.1. Connectives, Truth Tables. Connectives are used for
making compound propositions. The main ones are the following (p
and q represent given propositions):
Name Represented Meaning
Negation ¬p “not p”
Conjunction p∧q “p and q”
Disjunction p∨q “p or q (or both)”
Exclusive Or p⊕q “either p or q, but not both”
Implication p→q “if p then q”
Biconditional p↔q “p if and only if q”
The truth value of a compound proposition depends only on the
value of its components. Writing F for “false” and T for “true”, we
can summarize the meaning of the connectives in the following way:
61.1. PROPOSITIONS 7
p q ¬p p∧q p∨q p⊕q p→q p↔q
T T F T T F T T
T F F F T T F F
F T T F T T T F
F F T F F F T T
Note that ∨ represents a non-exclusive or, i.e., p∨q is true when
any of p, q is true and also when both are true. On the other hand ⊕
represents an exclusive or, i.e., p⊕q is true only when exactly one of
p and q is true.
1.1.2. Tautology, Contradiction, Contingency.
1. A proposition is said to be a tautology if its truth value is T
forany assignment of truth values toits components. Example:
The proposition p∨¬p is a tautology.
2. A proposition is said to be a contradiction if its truth value is F
forany assignment of truth values toits components. Example:
The proposition p∧¬p is a contradiction.
3. A proposition that is neither a tautology nor a contradiction is
called a contingency.
p ¬p p∨¬p p∧¬p
T F T F
T F T F
F T T F
F T T F
1.1.3. Conditional Propositions. A proposition of the form “if
p then q” or “p implies q”, represented “p→q” is called a conditional
proposition. For instance: “if John is from Chicago then John is from
Illinois”. The proposition p is called hypothesis or antecedent, and the
proposition q is the conclusion or consequent.
Note that p→q is true always except when p is true and q is false.
So, the following sentences are true: “if 2 4 then Paris is in France”
(true → true), “if London is in Denmark then 2 4” (false → true),1.1. PROPOSITIONS 8
“if 4 = 7 then London is in Denmark” (false → false). However the
following one is false: “if 2 4 then London is in Denmark” (true →
In might seem strange that “p → q” is considered true when p is
false, regardless of the truth value of q. This will become clearer when
we study predicates such as “if x is a multiple of 4 then x is a multiple
of 2”. That implication is obviously true, although for the particular
case x = 3 it becomes “if 3 is a multiple of 4 then 3 is a multiple of 2”.
The proposition p ↔ q, read “p if and only if q”, is called bicon-
ditional. It is true precisely when p and q have the same truth value,
i.e., they are both true or both false.
1.1.4. Logical Equivalence. Note that the compound proposi-
tions p→q and¬p∨q have the same truth values:
p q ¬p ¬p∨q p→q
T T F T T
T F F F F
F T T T T
F F T T T
When two compound propositions have the same truth values no
matter what truth value their constituent propositions have, they are
called logically equivalent. For instance p→q and ¬p∨q are logically
equivalent, and we write it:
p→q ≡ ¬p∨q
Note that that two propositions A and B are logically equivalent
precisely when A↔B is a tautology.
Example: De Morgan’s Laws for Logic. The following propositions
are logically equivalent:
¬(p∨q) ≡ ¬p∧¬q
¬(p∧q) ≡ ¬p∨¬q
We can check it by examining their truth tables:1.1. PROPOSITIONS 9
p q ¬p ¬q p∨q ¬(p∨q) ¬p∧¬q p∧q ¬(p∧q) ¬p∨¬q
T T F F T F F T F F
T F F T T F F F T T
F T T F T F F F T T
F F T T F T T F T T
Example: The following propositions are logically equivalent:
p↔q ≡ (p→q)∧(q→p)
Again, this can be checked with the truth tables:
p q p→q q→p (p→q)∧(q→p) p↔q
T T T T T T
T F F T F F
F T T F F F
F F T T T T
Exercise: Check the following logical equivalences:
¬(p→q) ≡ p∧¬q
p→q ≡ ¬q→¬p
¬(p↔q) ≡ p⊕q
1.1.5. Converse,Contrapositive. Theconverse ofaconditional
proposition p → q is the proposition q → p. As we have seen, the bi-
proposition an its converse.
p↔q ≡ (p→q)∧(q→p)
So, for instance, saying that “John is married if and only if he has a
and “if he has a spouse then he is married”.
Note that the converse is not equivalent to the given conditional
proposition, for instance “if John is from Chicago then John is from
Illinois” is true, but the converse “if John is from Illinois then John is
from Chicago” may be false.1.1. PROPOSITIONS 10
The contrapositive of a conditional proposition p→q is the propo-
sition ¬q → ¬p. They are logically equivalent. For instance the con-
trapositive of “if John is from Chicago then John is from Illinois” is “if
John is not from Illinois then John is not from Chicago”.1.2. PREDICATES, QUANTIFIERS 11
1.2. Predicates, Quantiﬁers
1.2.1. Predicates. Apredicate orpropositionalfunction isastate-
ment containing variables. For instance “x+2 = 7”, “X is American”,
“xy”, “p is a prime number” are predicates. The truth value of the
we replacex with 1 in the predicate “x+2 = 7” we obtain “1+2 = 7”,
which is false, but if we replace it with 5 we get “5+2 = 7”, which
is true. We represent a predicate by a letter followed by the variables
enclosedbetweenparenthesis: P(x),Q(x,y), etc. An example forP(x)
is a value of x for which P(x) is true. A counterexample is a value of
x for which P(x) is false. So, 5 is an example for “x+2 = 7”, while 1
is a counterexample.
Each variable in a predicate is assumed to belong to a universe (or
domain) of discourse,forinstanceinthepredicate“nisanoddinteger”
’n’ represents an integer, so the universe of discourse of n is the set of
all integers. In “X is American” we may assume that X is a human
being, so in this case the universe of discourse is the set of all human
1.2.2. Quantiﬁers. Given a predicate P(x), the statement “for
some x, P(x)” (or “there is some x such that p(x)”), represented
“∃xP(x)”, has a deﬁnite truth value, so it is a proposition in the
usual sense. For instance if P(x) is “x+2 = 7” with the integers as
universe of discourse, then ∃xP(x) is true, since there is indeed an
integer, namely 5, such that P(5) is a true statement. However, if
Q(x) is “2x = 7” and the universe of discourse is still the integers,
then∃xQ(x) is false. On the other hand,∃xQ(x) would be true if we
extend the universe of discourse to the rational numbers. The symbol
∃ is called the existential quantiﬁer.
“for every x, P(x)”, “for each x, P(x)”—, represented “∀xP(x)”, has
a deﬁnite truth value. For instance, if P(x) is “x + 2 = 7” and the
Usually all variables occurring in predicates along a reasoning are supposed to
belong to the same universe of discourse, but in some situations (as in the so called
many-sorted logics) it is possible to use diﬀerent kinds of variables to represent
diﬀerent types of objects belonging to diﬀerent universes of discourse. For instance
in the predicate “σ is a string of length n” the variable σ represents a string, while
n represents a natural number, so the universe of discourse of σ is the set of all
strings, while the universe of discourse of n is the set of natural numbers.1.2. PREDICATES, QUANTIFIERS 12
universe of discourse is the integers, then ∀xP(x) is false. However if
Q(x) represents “(x+1) = x +2x+1” then ∀xQ(x) is true. The
symbol∀ is called the universal quantiﬁer.
quantiﬁers at the same time, for instance ∀x∀y∃zP(x,y,z), meaning
“for all x and all y there is some z such that P(x,y,z)”.
be swapped, i.e., in general ∀x∃yP(x,y) means something diﬀerent
from∃y∀xP(x,y). Forinstanceifxandy representhumanbeingsand
P(x,y) represents “x is a friend of y”, then ∀x∃yP(x,y) means that
everybody is a friend of someone, but ∃y∀xP(x,y) means that there
is someone such that everybody is his or her friend.
A predicate can be partially quantiﬁed, e.g. ∀x∃yP(x,y,z,t). The
and the rest (z and t in the example) are called free variables. A
partially quantiﬁed predicate is still a predicate, but depending on
1.2.3. Generalized De Morgan Laws for Logic. If∃xP(x) is
false then there is no value of x for which P(x) is true, or in other
words, P(x) is always false. Hence
¬∃xP(x) ≡ ∀x¬P(x).
On the other hand, if ∀xP(x) is false then it is not true that for
every x, P(x) holds, hence for some x, P(x) must be false. Thus:
¬∀xP(x) ≡ ∃x¬P(x).
of a more complex quantiﬁed statement, for instance:
¬∃x∀yp(x,y) ≡ ∀x¬∀yP(x,y) ≡ ∀x∃y¬P(x,y).
is a greater real number”. Write the negation of that statement.
Answer: The statement is: ∀x∃y(xy) (the universe of discourse
istherealnumbers). Itsnegationis: ∃x∀y¬(xy),i.e.,∃x∀y(x 6 y).
(Note that among real numbers x 6 y is equivalent to x ≥ y, but
formally they are diﬀerent predicates.)1.3. PROOFS 13
1.3.1. Mathematical Systems, Proofs. A Mathematical Sys-
tem consists of:
1. Axioms: propositions that are assumed true.
2. Deﬁnitions: used to create new concepts from old ones.
3. Undeﬁnedterms: correspondingtotheprimitiveconceptsofthe
system (for instance in set theory the term “set” is undeﬁned).
A theorem is a proposition that can be proved to be true. An
argument that establishes the truth of a proposition is called a proof.
Example: Prove that if x 2 and y 3 then x+y 5.
Answer: Assuming x 2 and y 3 and adding the inequalities
term by term we get: x+y 2+3 = 5.
That is an example of direct proof. In a direct proof we assume the
hypothesis together with axioms and other theorems previously proved
and we derive the conclusion from them.
An indirect proof or proof by contrapositive consists of proving the
contrapositive of the desired implication, i.e., instead of proving p→q
we prove ¬q→¬p.
Example: Prove that if x+y 5 then x 2 or y 3.
Answer: We must prove that x+y 5 → (x 2)∨(y 3). An
indirectproofconsistsofproving¬((x 2)∨(y 3))→¬(x+y 5).
Infact: ¬((x 2)∨(y 3))isthesameas(x≤ 2)∧(y≤ 3),soadding
both inequalities we get x+y≤ 5, which is the same as¬(x+y 5).
Proof by Contradiction. In a proof by contradiction or (Reductio ad
Absurdum) we assume the hypotheses and the negation of the conclu-
sion, and try to derive a contradiction, i.e., a proposition of the form
Example: Prove by contradiction that ifx+y 5 then eitherx 2
or y 3.
Answer: We assume the hypothesis x+y 5. From here we must
conclude that x 2 or y 3. Assume to the contrary that “x 2 or
y 3” is false, so x≤ 2 and y ≤ 3. Adding those inequalities we get1.3. PROOFS 14
x≤ 2+3 = 5, which contradicts the hypothesis x+y 5. From here
we conclude that the assumption “x≤ 2 and y ≤ 3” cannot be right,
so “x 2 or y 3” must be true.
proof and a proof by contradiction. In an indirect proof we prove an
implication of the form p → q by proving the contrapositive ¬q →
¬p. In an proof by contradiction we prove an statement s (which
may or may not be an implication) by assuming ¬s and deriving a
contradiction. In fact proofs by contradiction are more general than
Exercise: Prove by contradiction that 2 is not a rational number,
i.e., there are no integers a,b such that 2 =a/b.
Answer: Assume that 2 is rational, i.e., 2 =a/b, where a and b
are integers and the fraction is written in least terms. Squaring both
2 2 2 2
sides we have 2 = a /b , hence 2b = a . Since the left hand side is
even, then a is even, but this implies that a itself is even, so a = 2a.
2 0 2 0 2
Hence: 2b = 4a , and simplifying: b = 2a . This implies that b
0 0 0 0 0
is even, so b is even: b = 2b. Consequently a/b = 2a/2b = a/b,
contradicting the hypothesis that a/b was in least terms.
1.3.2. Arguments, Rules of Inference. An argument is a se-
quence of propositions p ,p ,...,p called hypotheses (or premises)
1 2 n
followed by a proposition q called conclusion. An argument is usually
p ,p ,...,p /∴ q
1 2 n
The argument is called valid if q is true whenever p ,p ,...,p are
1 2 n
true; otherwise it is called invalid.1.3. PROOFS 15
Rules of inference are certain simple arguments known to be valid
and used to make a proof step by step. For instance the following
argument is called modus ponens or rule of detachment:
In order to check whether it is valid we must examine the following
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
If we look now at the rows inwhichbothp→q andp are true(just
the ﬁrst row) we see that also q is true, so the argument is valid.
Other rules of inference are the following:
1. Modus Ponens or Rule of Detachment:
2. Modus Tollens:
5. Conjunction:1.3. PROOFS 16
6. Hypothetical Syllogism:
7. Disjunctive Syllogism:
Arguments are usually written using three columns. Each row con-
tains a label, a statement and the reason that justiﬁes the introduction
of that statement in the argument. That justiﬁcation can be one of the
1. The statement is a premise.
in the argument by using a rule of inference.
Example: Consider the following statements: “I take the bus or
I walk. If I walk I get tired. I do not get tired. Therefore I take the
bus.” We can formalize this by calling B = “I take the bus”, W =
“I walk” and T = “I get tired”. The premises are B∨W, W →T and
¬T, and the conclusion is B. The argument can be described in the
step statement reason
1) W →T Premise
2) ¬T Premise
3) ¬W 1,2, Modus Tollens
4) B∨W Premise
5) ∴B 4,3, Disjunctive Syllogism1.3. PROOFS 17
1.3.3. Rules of Inference for Quantiﬁed Statements. We
state the rules for predicates with one variable, but they can be gener-
alized to predicates with two or more variables.
1. Universal Instantiation. If∀xp(x) is true, then p(a) is true for
each speciﬁc element a in the universe of discourse; i.e.:
Forinstance,from∀x(x+1 = 1+x)wecanderive7+1 = 1+7.
2. Existential Instantiation. If∃xp(x)istrue, thenp(a)istruefor
some speciﬁc element a in the universe of discourse; i.e.:
The diﬀerence respect to the previous rule is the restriction in
of the universe of discourse. So, for instance, from ∃x(x = 2)
(the universe of discourse is the real numbers) we derive the
existence of some element, which we may represent ± 2, such
that (± 2) = 2.
3. Universal Generalization. If p(x) is proved to be true for a
generic element in the universe of discourse, then ∀xp(x) is
So, for instance, we can prove ∀x(x+1) =x +2x+1 (say,
for real numbers) by assuming that x is a generic real number
and using algebra to prove (x+1) =x +2x+1.
4. Existential Generalization. If p(a) is true for some speciﬁc ele-
ment a in the universe of discourse, then ∃xp(x) is true; i.e.:
For instance: from 7+1 = 8 we can derive ∃x(x+1 = 8).
Example: Show that a counterexample can be used to disprove a
universal statement, i.e., ifa is an element in the universe of discourse,1.3. PROOFS 18
then from ¬p(a) we can derive¬∀xp(x). Answer: The argument is as
step statement reason
1) ¬p(a) Premise
2) ∃x¬p(x) Existential Generalization
3) ¬∀xp(x) Negation of Universal StatementCHAPTER 2
Sets, Functions, Relations
2.1. Set Theory
2.1.1. Sets. A set is a collection of objects, called elements of the
set. A set can be represented by listing its elements between braces:
A =1,2,3,4,5. The symbol ∈ is used to express that an element is
(or belongs to) a set, for instance 3∈A. Its negation is represented by
6∈, e.g. 76∈A. If the set is ﬁnite, its number of elements is represented
A, e.g. if A =1,2,3,4,5 then A = 5.
Some important sets are the following:
1. N =0,1,2,3,··· = the set of natural numbers.
2. Z =··· ,−3,−2,−1,0,1,2,3,··· = the set of integers.
3. Q = the set of rational numbers.
4. R = the set of real numbers.
5. C = the set of complex numbers.
Is S is one of those sets then we also use the following notations:
1. S = set of positive elements in S, for instance
Z =1,2,3,··· = the set of positive integers.
2. S = set of negative elements in S, for instance
Z =−1,−2,−3,··· = the set of negative integers.
3. S = set of elements in S excluding zero, for instanceR = the
set of non zero real numbers.
Set-builder notation. An alternative way to deﬁne a set, called set-
builder notation, is by stating a property (predicate) P(x) veriﬁed by
exactly its elements, for instance A = x ∈Z 1 ≤ x ≤ 5 = “set of
Note thatN includes zero—for some authorsN =1,2,3,···, without zero.
When working with strings we will use a similar notation with a diﬀerent
meaning—be careful not to confuse it.
192.1. SET THEORY 20
integers x such that 1 ≤ x ≤ 5”—i.e.: A = 1,2,3,4,5. In general:
A =x∈U p(x), where U is the universe of discourse in which the
predicate P(x) must be interpreted, or A =xP(x) if the universe
of discourse for P(x) is implicitly understood. In set theory the term
universal set isoftenusedinplaceof“universeofdiscourse”foragiven
Principle of Extension. Two sets are equal if and only if they have
the same elements, i.e.:
A =B ≡ ∀x(x∈A↔x∈B).
Subset. We say that A is a subset of set B, or A is contained in
B, and we represent it “A⊆ B”, if all elements of A are in B, e.g., if
A =a,b,c and B =a,b,c,d,e then A⊆B.
A is a proper subset of B, represented “A ⊂ B”, if A ⊆ B but
A = 6 B, i.e., there is some element in B which is not in A.
Empty Set. A set with no elements is called empty set (or null set,
or void set), and is represented by ∅ or.
Note that nothing prevents a set from possibly being an element of
another set (which is not the same as being a subset). For instance
if A = 1,a,3,t,1,2,3 and B = 3,t, then obviously B is an
element of A, i.e., B ∈A.
Power Set. The collection of all subsets of a set A is called the
power set of A, and is representedP(A). For instance, if A =1,2,3,
Exercise: Prove by induction that if A =n then P(A) = 2 .
Multisets. Two ordinary sets are identical if they have the same
elements, so for instance, a,a,b and a,b are the same set because
they have exactly the same elements, namely a and b. However, in
some applications it might be useful to allow repeated elements in a
set. In that case we use multisets, which are mathematical entities
similar to sets, but with possibly repeated elements. So, as multisets,
a,a,b anda,b would be considered diﬀerent, since in the ﬁrst one
the element a occurs twice and in the second one it occurs only once.
Properly speaking, the universe of discourse of set theory is the collection of
all sets (which is not a set).