CSC102: Introduction to Discrete

Mathematics
 Lecture Information

• Lecture day Wednesday

• Lecture time 2.00 PM – 4.00 PM
• Lecture venue E303
 Lecture Scheme
WK TOPIC
1 INTRODUCTION TO DISCRETE MATHEMATICS AND SETS
2 RELATIONS
3 FUNCTIONS
4 COMBINATORICS
5 LOGIC
6 EQUIVALENCE PARTITION RELATION
7 ORDERED SETS
8 BOOLEAN ALGEBRA
9 MATRICES AND REAL MATRICES
10 BOOLEAN MATRICES AND PATH MATRICES
11 ADJACENCY VECTORS/MATRICES
12 APPLICATION TO COUNTING
13,14,15 REVISION AND EXAMS
 TEACHING MATERIALS
• Discrete mathematics for new technology by
Rowan Garnier And John Taylor

• Discrete Mathematics and Its Applications

Seventh Edition by Kenneth H. Rosen
• Other books on Discrete Mathematics and
online tutorial
• Group discussions and assignments
 INTRODUCTION TO DISCRETE
MATHEMATICS COURSE
• What is discrete mathematics?
– field of mathematics that deals with the study of discrete
objects. Discrete here means separate, individual, distinct or
unconnected elements.

• Concepts and notations from discrete mathematics are

useful
• computer algorithms
• programming languages
• cryptography
• automated theorem proving
• software development
• The knowledge from the study of discrete
mathematics is useful in the following areas:
– MATHEMATICAL REASONING
– COMBINATORIAL ANALYSIS
– DISCRETE STRUCTURE
– ALGORITHMIC THINKING
– APPLICATION AND MODELING
 Week 2
Set and membership
 Learning Objectives
You should be able to:
- define formally what a set is
- state 3 examples of real-world sets and apply
various set operations on them
- generate valid subsets from a set
- apply the concept of sets to solving real life
problems
 Sets and Objects
• A set – a well-defined collection of objects, called
the elements or members of the set.

• An object can be anything.

• Each object in a set is called an element.

Examples of some real world sets

A set of fruits may contain banana, mango, pineapple
etc. A stone for instance cannot be part of this set.
 Set and membership contd.

• A “set” can also be called a “class,”

“collection,” and “family.”

• Capital letters such as A,B,X, Y, . . . , are usually

used to denote sets while lowercase letters
such as a, b, x, y, . . ., are used to denote
elements of sets.
Specifying Sets
• There are essentially two ways to specify a
particular set.

• One way, if possible, is to list its members

separated by commas and contained in braces
{ }.

• The other way is to use the format

• A = {y|cond(y) }. This means that the set A
contains y but there is a condition for generating
y.
 N o tati o n san d n o tati o n ald e
fi n iti o n o fse
t

Consider the notations below:

A = {Picasso, Eiffel Tower, π} means that A is a set

B = {2, 4, 6, 8, . . .} means that B is a set
C = { } means that C is an empty set or a null set.
It is usually denoted by the symbol

Note the use of braces {} in grouping the element

of the same set together.
 Examples
• The set B above could be defined as B = {n : n is
an even, positive integer}, or B = {n : n = 2m,
where m > 0 and m is an integer}, or, with a
slight change of notation, B = {2m : m > 0 and m
is an integer}.

• The set {1, 2} could alternatively be defined as

{x : x2−3x +2 = 0}. Then {1, 2} is the solution set
of the equation x2 − 3x + 2 = 0.
 More Examples
• The set B above could be defined as B = {n : n is
an even, positive integer}, or B = {n : n = 2m,
where m > 0 and m is an integer}, or, with a
slight change of notation, B = {2m : m > 0 and m
is an integer}.

• The set {1, 2} could alternatively be defined as

{x : x2−3x +2 = 0}. Then {1, 2} is the solution set
of the equation x2 − 3x + 2 = 0.
• Equality of set
– Two sets are defined to be equal if and only if they
contain the same elements; that is, A = B if ∀x[x ∈
A ↔ x ∈ B] is a true proposition, and conversely
• Cardinality of set
– If A is a finite set its cardinality, |A|, is the
number of (distinct) elements which it contains.
– If A has an infinite number of elements, we say it
has infinite cardinality and write |A| =∞.
 Subset
• The set A is a subset of the set B, denoted A ⊆ B, if
every element of A is also an element of B.
Symbolically, A ⊆ B if ∀x[x ∈ A → x ∈ B] is true,
and conversely.
• If A is a subset of B, we say that B is a superset of
A, and write B ⊇ A.
• Clearly every set B is a subset of itself, B ⊆ B. (This
is because, for any given x, x ∈ B → x ∈ B is
‘automatically’ true.)
• Any other subset of B is called a proper subset of B.
The notation A ⊂ B is used to denote ‘A is a
proper subset of B’. Thus A ⊂ B if and only if A ⊆ B
and A ≠ B.
• EXAMPLE 1.2 Consider the sets:
• A = {1, 3, 4, 7, 8, 9}, B= {1, 2, 3, 4, 5}, C= {1, 3}.
• Then C ⊆ A and C ⊆ B , but A ⊆/ B.

• Theorem: Let A, B, C be any sets. Then:

• (i) A ⊆ A
• (ii) If A ⊆ B and B ⊆ A, then A = B
• (iii) If A ⊆ B and B ⊆ C, then A ⊆ C
 Universal Set, Empty set

• All sets under investigation in any application

of set theory are assumed to belong to some
fixed large set called the universal set.
• It is usually denoted by U unless otherwise
stated or implied.
• Given a universal set U and a property P, there
may not be any elements of U which have
property P. For example, the following set has
no elements:
 S = {x | x is a positive integer, x2 = 3}
• Such a set with no elements is called the empty
set or null set and is denoted by ∅
• There is only one empty set. That is, if S and T are
both empty, then S = T , since they have exactly
the same elements, namely, none.
• The empty set ∅ is also regarded as a subset of
every other set. Thus we have the following
simple result which we state formally.
• For any set A, we have ∅ ⊆ A ⊆ U.

NOTE: Two sets A and B are said to be disjoint if

they have no elements in common.
 Operation on set
• The Venn diagram
– is a useful visual representation of sets. In such a
diagram sets are represented as regions in the
plane and elements which belong to a given set
are placed inside the region representing it.
• Venn diagrams

U
A B

C
• Intersection of A and B is the set of all
elements which belong both to A and B
– it is denoted A ∩ B.
• The union of A and B is the set of all elements
which belong to A or to B or to both
– it is denoted A ∪ B.
Symbolically:
– A ∩ B = {x : x ∈ A and x ∈ B}
– A ∪ B = {x : x ∈ A or x ∈ B or both}.
• Disjoint Sets A and B are said to be disjoint if they
have no elements in common
 By extending the definitions of intersection and union
to more than two say A1, A2 ……. An
• Their intersection is:
= A1 ∩ A2 ∩ · · · ∩ An = {x : x ∈ A1
and x ∈ A2 and . . . and x ∈ An}
= {x : x belongs to each set Ar, for r
= 1, 2, . . . , n}.
• Their union is:
= A1 ∪ A2 ∪ · · · ∪ An = {x : x ∈ A1
or x ∈ A2 or . . . or x ∈ An}
= {x : x belongs to at least one set
Ar , r = 1, . . . , n}.
• Complement: given a set A its complement AI
orAc are all the elements that are in the
universal set which do not belong to A
– If A = {x : P(x)} then .Ac = {x : ￢ P(x)}.

• Difference or relative complement of two

sets A and B, denoted A − B or A \ B. This set
contains all the elements of A which do not
belong to B:
 Counting techniques
• Counting Principle 1
– If A and B are disjoint sets, then |A ∪ B| = |A| + |B|.
• Counting Principle 2
– If A , A , . . . , A are sets, no pair of which have
1 2 n

elements in common,then|A ∪ A ∪ · · · ∪ A | = |A | +
1 2 n 1

|A |+· · ·+|A |.
2 n

• Theorem: (The inclusion–exclusion principle)

– If A and B are finite sets then |A ∪ B| = |A| + |B| − |
A ∩ B|.
 Algebra on set
• Idempotent laws
– A∩A=A
– A ∪ A = A.
• Commutative laws
– A∩B=B∩A
– A ∪ B = B ∪ A.
• Associative laws
– A ∩ (B ∩ C) = (A ∩ B) ∩ C
– A ∪ (B ∪ C) = (A ∪ B) ∪ C.
• Absorption laws
– A ∩ (A ∪ B) = A
– A ∪ (A ∩ B) = A.
• Distributive laws
– A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
– A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).
• Involution law
– = A.
• De Morgan’s laws
– A∪B=A∩B
– (A ∩ B) = A ∪ B
• Identity Law
–A∪ᴓ=A
–A∩ᴓ=ᴓ
–A∪U = U
–A∩U = A
• Complement law
–A∪ Ã=U
–A∩Ã=ᴓ
–U =ᴓ
–ᴓ=U
 Power set
• Given any set A, the set consisting of all subsets
of A is the Called the power set of A
– P(A) = {B : B ⊆ A}.
– If |A| = n then | P(A) | = 2n

EXAMPLE 1.10 Suppose S = {1, 2, 3}. Then

• P(S) = [∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, S]
• Note that the empty set ∅ belongs to P(S) since
∅ is a subset of S. Similarly, S belongs to P(S). As
expected
• from the above remark, P(S) has 23 = 8 elements.
END OF LECTURE