Discrete structures
1 Fundamentals 2
1.1 Sets and Subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Operations on Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Properties of the Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.6 Mathematical Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Logic 7
2.3 Methods of proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.4 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 Counting 8
3.1 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2 Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.3 Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.5 Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4 Relations and Digraphs 9
4.1 Product Sets and Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.2 Relations and Digraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.3 Paths in Relations and Digraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.4 Properties of Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.5 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.7 Operations on Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.8 Transitive Closure and Warshall’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 14
5 Functions 14
5.1 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.2 Functions for Computer Science . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.3 Growth of Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5.4 Permutation Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6 Order Relations and Structures 17
6.1 Partially Ordered Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6.2 Extremal Elements of Partially Ordered Sets . . . . . . . . . . . . . . . . . . . . . . . . . 18
6.3 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
6.4 Finite Boolean Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
6.5 Functions on Boolean Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
7 Trees 24
7.1 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
7.2 Labeled Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
7.3 Tree Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
7.4 Undirected Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
7.5 Minimal Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
8 Topics in Graph Theory 28
8.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
8.2 Euler Paths and Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
8.3 Hamiltonian Paths and Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1
,1 Fundamentals
1.1 Sets and Subsets
Sets
A set is any well-defined collection of objects called the elements or members of the set. Well-defined
just means that it is possible to decide whether a given object belongs to the collection or not.
We can either list out all elements of a set {a, b, c, . . . } or use a property {x | P (x)}
Several sets:
• Z+ = {x | x is a positive integer} • Q = {x | x is a rational number}
• N = {x | x is a positive integrer or zero} • R = {x | x is a real number}
• Z = {x | x is an integer} • The empty set, denoted by {} or ∅
Sets are completely known when their members are all known. Thus, we say that two sets A and B are
equal if they have the same elements, and we write A = B.
Subsets
If every element of A is also an element of B, that is, if whenever x ∈ A then x ∈ B, we say that A is a
subset of B or that A is contained in B, and we write A ⊂ B
We have ∅ ⊂ A for any set A and that A = B if and only if A ⊂ B and B ⊂ A.
A set A is called finite if it has ndistinct elements, where n ∈ N. In this case, n is called the cardinality
of A and is denoted by |A|. A set that is not finite is called infinite. If A is a set, then the set of all
subsets of A is called the power set of A and is denoted P (A).
1.2 Operations on Sets
If A and B are sets, we define their union as the set consisting of all elements that belong to A or B and
denote it by A ∪ B. Thus, A ∪ B = {x | x ∈ A or x ∈ B}
If A and B are sets, we define their intersection as the set consisting of all elements that belong to A
and B and denote it by A ∩ B. Thus, A ∩ B = {x | x ∈ A and x ∈ B}
Two sets that have no common elements are called disjoint sets.
The operations of union and intersection can be defined for three or more sets in an obvious manner:
n
[ n
\
Ak = A1 ∪ A2 ∪ · · · ∪ An , Ak = A1 ∩ A2 ∩ · · · ∩ An
k=1 k=1
If A and B are two sets, we define the complement of B with respect to A as the set of all elements that
belong to A but not to B, and we denote it by A − B. Thus, A − B = {x | x ∈ A and x ̸∈ B}
If A and B are two sets, we define their symmetric difference as the set of all elements that belong to A or
B, but not to both A and B, and we denote it by A⊕B. Thus A⊕B = {x |(x ∈ A and x ̸∈ B) or (x ̸∈ A and x ∈ B)},
i.e. A ⊕ B = (A − B) ∪ (B − A)
Algebraic properties of set operations
Theorem 1 The operations defined on sets satisfy the following properties:
2
, • Commutative properties – A ∪ (B ∩ C) = (A ∪ B) ∩ – U =∅
– A∪B =B∪A (A ∪ C) – A∪B =A∩B
– A∩B =B∩A • Idempotent Properties – A∩B =A∪B
– A∪A=A
• Associative properties • Properties of a universal set
– A∩A=A
– A ∪ (B ∪ C) = (A ∪ B) ∪ C – A∪U =U
• Properties of the complement
– A ∩ (B ∩ C) = (A ∩ B) ∪ C – A∩U =A
– (A) = A
• Distributive properties – A∪A=U • Properties of the empty set
– A ∩ (B ∪ C) = (A ∩ B) ∪ – A∩A=∅ – A∪∅=A
(A ∩ C) – ∅=U – A∩∅=∅
The Addition principle
Theorem 2 if A and B are finite sets, then |A ∪ B| = |A| + |B| − |A ∩ B|
Theorem 3 if A, B and C are finite sets, then |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩
C| + |A ∩ B ∩ C|
1.3 Sequences
A sequence is simply a list of objects arranged in a definite order; a first element, second element, third
element, and so on. The list may stop after n steps, n ∈ N, or it may go on forever. In the first case we
say that the sequence is finite, and in the second case we say that it is infinite. The elements may all be
different, or some may be repeated.
A formula that refers to previous terms to define the next term is called recursive. On the other hand, a
formula that only uses the position number is called explicit, because it tells us exactly what value any
particular term has.
Sequences of letters or other symbols, written without the commas, are also referred to as strings.
The set corresponding to a sequence is simply the set of all distinct elements in the sequence.
A sequence is sometimes called a linear array or a list.
Characteristic functions
The characteristic function fA of A is defined for each x ∈ U as follows:
(
1 x∈A
fA (x) =
0 x ̸∈ A
Theorem 1 Characteristic functions of subsets satisfy the following properties:
• fA∩B = fA fB
• fA∪B = fA + fB − fA fB
• fA⊕B = fA + fB − 2fA fB
Computer representation of sets and subsets
A set is called countable if it is the set corresponding to some sequence. Informally, this means that the
members of the set can be arranged in a list, with a first, second, third, etc element. A set that is not
countable is called uncountable.
3
1 Fundamentals 2
1.1 Sets and Subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Operations on Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Properties of the Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.6 Mathematical Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Logic 7
2.3 Methods of proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.4 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 Counting 8
3.1 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2 Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.3 Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.5 Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4 Relations and Digraphs 9
4.1 Product Sets and Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.2 Relations and Digraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.3 Paths in Relations and Digraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.4 Properties of Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.5 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.7 Operations on Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.8 Transitive Closure and Warshall’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 14
5 Functions 14
5.1 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.2 Functions for Computer Science . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.3 Growth of Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5.4 Permutation Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6 Order Relations and Structures 17
6.1 Partially Ordered Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6.2 Extremal Elements of Partially Ordered Sets . . . . . . . . . . . . . . . . . . . . . . . . . 18
6.3 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
6.4 Finite Boolean Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
6.5 Functions on Boolean Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
7 Trees 24
7.1 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
7.2 Labeled Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
7.3 Tree Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
7.4 Undirected Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
7.5 Minimal Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
8 Topics in Graph Theory 28
8.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
8.2 Euler Paths and Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
8.3 Hamiltonian Paths and Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1
,1 Fundamentals
1.1 Sets and Subsets
Sets
A set is any well-defined collection of objects called the elements or members of the set. Well-defined
just means that it is possible to decide whether a given object belongs to the collection or not.
We can either list out all elements of a set {a, b, c, . . . } or use a property {x | P (x)}
Several sets:
• Z+ = {x | x is a positive integer} • Q = {x | x is a rational number}
• N = {x | x is a positive integrer or zero} • R = {x | x is a real number}
• Z = {x | x is an integer} • The empty set, denoted by {} or ∅
Sets are completely known when their members are all known. Thus, we say that two sets A and B are
equal if they have the same elements, and we write A = B.
Subsets
If every element of A is also an element of B, that is, if whenever x ∈ A then x ∈ B, we say that A is a
subset of B or that A is contained in B, and we write A ⊂ B
We have ∅ ⊂ A for any set A and that A = B if and only if A ⊂ B and B ⊂ A.
A set A is called finite if it has ndistinct elements, where n ∈ N. In this case, n is called the cardinality
of A and is denoted by |A|. A set that is not finite is called infinite. If A is a set, then the set of all
subsets of A is called the power set of A and is denoted P (A).
1.2 Operations on Sets
If A and B are sets, we define their union as the set consisting of all elements that belong to A or B and
denote it by A ∪ B. Thus, A ∪ B = {x | x ∈ A or x ∈ B}
If A and B are sets, we define their intersection as the set consisting of all elements that belong to A
and B and denote it by A ∩ B. Thus, A ∩ B = {x | x ∈ A and x ∈ B}
Two sets that have no common elements are called disjoint sets.
The operations of union and intersection can be defined for three or more sets in an obvious manner:
n
[ n
\
Ak = A1 ∪ A2 ∪ · · · ∪ An , Ak = A1 ∩ A2 ∩ · · · ∩ An
k=1 k=1
If A and B are two sets, we define the complement of B with respect to A as the set of all elements that
belong to A but not to B, and we denote it by A − B. Thus, A − B = {x | x ∈ A and x ̸∈ B}
If A and B are two sets, we define their symmetric difference as the set of all elements that belong to A or
B, but not to both A and B, and we denote it by A⊕B. Thus A⊕B = {x |(x ∈ A and x ̸∈ B) or (x ̸∈ A and x ∈ B)},
i.e. A ⊕ B = (A − B) ∪ (B − A)
Algebraic properties of set operations
Theorem 1 The operations defined on sets satisfy the following properties:
2
, • Commutative properties – A ∪ (B ∩ C) = (A ∪ B) ∩ – U =∅
– A∪B =B∪A (A ∪ C) – A∪B =A∩B
– A∩B =B∩A • Idempotent Properties – A∩B =A∪B
– A∪A=A
• Associative properties • Properties of a universal set
– A∩A=A
– A ∪ (B ∪ C) = (A ∪ B) ∪ C – A∪U =U
• Properties of the complement
– A ∩ (B ∩ C) = (A ∩ B) ∪ C – A∩U =A
– (A) = A
• Distributive properties – A∪A=U • Properties of the empty set
– A ∩ (B ∪ C) = (A ∩ B) ∪ – A∩A=∅ – A∪∅=A
(A ∩ C) – ∅=U – A∩∅=∅
The Addition principle
Theorem 2 if A and B are finite sets, then |A ∪ B| = |A| + |B| − |A ∩ B|
Theorem 3 if A, B and C are finite sets, then |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩
C| + |A ∩ B ∩ C|
1.3 Sequences
A sequence is simply a list of objects arranged in a definite order; a first element, second element, third
element, and so on. The list may stop after n steps, n ∈ N, or it may go on forever. In the first case we
say that the sequence is finite, and in the second case we say that it is infinite. The elements may all be
different, or some may be repeated.
A formula that refers to previous terms to define the next term is called recursive. On the other hand, a
formula that only uses the position number is called explicit, because it tells us exactly what value any
particular term has.
Sequences of letters or other symbols, written without the commas, are also referred to as strings.
The set corresponding to a sequence is simply the set of all distinct elements in the sequence.
A sequence is sometimes called a linear array or a list.
Characteristic functions
The characteristic function fA of A is defined for each x ∈ U as follows:
(
1 x∈A
fA (x) =
0 x ̸∈ A
Theorem 1 Characteristic functions of subsets satisfy the following properties:
• fA∩B = fA fB
• fA∪B = fA + fB − fA fB
• fA⊕B = fA + fB − 2fA fB
Computer representation of sets and subsets
A set is called countable if it is the set corresponding to some sequence. Informally, this means that the
members of the set can be arranged in a list, with a first, second, third, etc element. A set that is not
countable is called uncountable.
3
