What is Discrete Mathematics?

1
 From http://dictionary.oed.com:
Discrete adj.
1. a. Separate, detached from others, individually distinct.
Opposed to continuous.
2. a. Consisting of distinct or individual parts;
discontinuous.

According to writer Kenneth H. Rosen-

Discrete mathematics is the part of mathematics devoted to the
study of discrete objects.

2
 Kind of problem solving using discrete mathematics

• How many ways are there to choose a valid password on a computer system?
• What is the probability of winning a lottery?
• Is there a link between two computers in a network?
• What is the shortest path between two cities using a transportation system?
• How can a list of integers be sorted so that the integers are in increasing order?
• How many steps are required to do such a sorting?
• How can it be proved that a sorting algorithm correctly sorts a list?
• How can a circuit that adds two integers be designed?
• How many valid Internet addresses are there?
3
 Application Area

• Advanced algorithms & data • Database management systems

structures • Cryptography
• Programming language compilers & • Error correction codes
interpreters. • Graphics & animation
• Computer networks • Game engines, etc.…
• Operating systems • I.e., the whole field!
• Computer architecture

4
 Books?
Discrete Mathematics
Schema’s outline series: Seymour Lipshutz.

Discrete Mathematics and Its Applications

McGraw-Hill: Kenneth H. Rosen

5
 Set Basics
Examination [5]
1. What is Set?
2. State whether the sets in each pair are equal or not.
a) {a, b, c, d} and {a, c, d, b}
b) {2, 4, 6} and {x | x is an even number}
 Set Theory

7
Every extraordinary feat began in ordinary circumstances. I will start my journey of success from where I am now.
 License

Your are free –

– to Share – to copy, distribute and transmit the work
– to Remix – to adapt the work

For non commercial and educational purpose.

8
 References
Discrete Mathematics and its Applications by Kenneth H.
• Chapter 1 : Set Theory
Rosen
Discrete Mathematics by Seymour Lipschutz, Marc Lipso
• Chapter 2 : Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

Discrete Structures by Vladlen Koltun

• Lecture Note
Discrete Mathematics by Miguel A. Lerma
• Lecture Note
9
 Set Basics
Definition
A set is an unordered collection of objects, called elements or members
of the set. A set is said to contain its elements.

Example
People in a class: {Samiha, Bulbul, Tonmoy, Rafeed}

Districts in the BD : {Rajshahi, Dhaka, Nator, … }

Sets can contain non-related elements: {3, a, Potato}

All positive numbers less than or equal to 5: {1, 2, 3, 4, 5}

 Set Basics
Definition

A set is an unordered collection of “objects”

Example

People in a class: {Samiha, Bulbul, Tonmoy, Rafeed}

Districts in the BD : {Rajshahi, Dhaka, Nator, … }

Sets can contain non-related elements: {3, a, Potato}

All positive numbers less than or equal to 5: {1, 2, 3, 4, 5}

 Set Basics
Definition
A set is an unordered collection of objects, called elements or members
of the set. A set is said to contain its elements.

• It is common for SETS to be denoted using uppercase letters.

• Lowercase letters are usually used to denote elements of sets.
 Set Basics
Definition
A set is an unordered collection of objects, called elements or members
of the set. A set is said to contain its elements.

• It is common for SETS to be denoted using uppercase letters.

• Lowercase letters are usually used to denote elements of sets.
 Set and Elements
Let, A = { 1, a, e, u, i, o, 2, 3}

14
 How to describe a Set?
Three popular methods

1. Word description
Set of even counting numbers less than 10
2. The listing method / Roster method
{2, 4, 6, 8}
3. Set-builder notation
{x | x is an even counting number less than 10}
15
 How to describe a Set?
1. Word description
• Make a word description of the set.

16
 How to describe a Set?
2. Roster Method

17
 How to describe a Set?
3. Set-builder notation
• characterize all elements in the set by stating the property or properties they must have to
be members.
• the set O of all odd positive integers less than 10 can be written as
O = { x | x is an odd positive integer less than 10 }
O = { x ∈ Z+ | x is odd and x < 10 }

Example: B = {x | x is an even integer, x > 0}

• Read as- “B is the set of x such that x is an even integer and x is greater than 0”
• | is read as “such that” and comma as “and”.
18
 How to describe a Set?
3. Set-builder notation with interval
• the notation for intervals of real numbers. When a and b are real
numbers with a < b, we write
• [a, b] = {x | a ≤ x ≤ b}
• [a, b) = {x | a ≤ x < b}
• (a, b] = {x | a < x ≤ b}
• (a, b) = {x | a < x < b}

• Note that [a, b] is called the closed interval/unit interval from a to b and
(a, b) is called the open interval from a to b. 19
 Often used sets
• N = {0, 1, 2, 3, …} is the set of natural numbers
• Z = {…, -2, -1, 0, 1, 2, …} is the set of integers
• Z+ = {1, 2, 3, …} is the set of positive integers (a.k.a whole numbers)
– Note that people disagree on the exact definitions of whole numbers and natural numbers

• Q = {p/q | p ∈ Z, q ∈ Z, q ≠ 0} is the set of rational numbers

– Any number that can be expressed as a fraction of two integers (where the bottom one is not zero)

• R is the set of real numbers

• R+ the set of positive real numbers
• C the set of complex numbers.
20
 Specifying
Specifying Sets Set
(cont.)
•

A = {x | x is a letter in English, x is a vowel}

B = {2, 4, 6, …….}

E = {1, 2}
21
 Specifying
Specifying Sets Set
(cont.)
• A = {x: x ∈ Z, x is even, x <15 }

A = {… -8, -6, -4, -2, 0, 2, 4, …., 14}

• B = {x: x ∈ Z, x + 4 = 3 }

B = {-1}

• C = {x: x ∈ Z, x2 + 2 = 6 }
E = {-2, +2}
22
 Set - properties

Order does not matter

– {1, 2, 3, 4, 5} is equivalent to {3, 5, 2, 4, 1}

Frequency does not matter

- Consider the list of students in this class
• It does not make sense to list somebody twice

23
Set Terminology : The universal set

Definition
U is the universal set – the set of all of elements (or the “universe”) from
which given any set is drawn

• For the set {-2, 0.4, 2}, U would be the real numbers
• For the set {0, 1, 2}, U could be the N, Z, Q, R depending on the context
• For the set of the vowels of the alphabet, U would be all the letters of the
alphabet

24
Set Terminology : The Empty Set
Definition
If a set has zero elements, it is called the empty (or null) set

• Written using the symbol ∅

• Thus, ∅ = { } 🡨 VERY IMPORTANT
• It can be a element of other sets
{ ∅, 1, 2, 3, x } is a valid set

• ∅≠{∅}
The first is a set of zero elements
The second is a set of 1 element [A set with one element is called a singleton set]
25
 Venn diagrams
• Represents sets graphically
– The box represents the universal set
– Circles represent the set(s)
• Consider set S, which is the set of all b c d f
U
vowels in the alphabet g h j S
• The individual elements are usually not k l m

written in a Venn diagram n p q a e i

r s t
o u
v w x
y z

26
 Set Terminology : Subset
Definition
The set A is a sub set of B if and only if every element of A is also an
element of B.

• We use the notation A ⊆ B to indicate that A is a subset of the set B.

We see that A ⊆ B if and only if the quantification ∀x (x∈ A → x ∈ B) is true

27
 Set Terminology : Subset
Example
• If A = {2, 4, 6} and B = {1, 2, 3, 4, 5, 6, 7}; A is a subset of B
• If A = {1, 2, 3, 4} and B = {1, 2, 3, 4}; A is a subset of B

• Every nonempty set S has at least two subset

For any set S, S ⊆ S (∀S S ⊆ S)
For any set S, ∅ ⊆ S (∀S ∅ ⊆ S)

28
Set Terminology : Proper Subset
Definition

• For A ⊂ B to be true, it must be the case that A ⊆ B and there must exist an
element y of B that is not an element of A.

29
Set Terminology : Proper Subset
Example

30
Set Terminology : Set Equality
Definition
Two sets are equal if and only if they have the same elements. We write
A = B if A and B are equal sets.

• Therefore, if A and B are sets, then A and B are equal if and only if
∀x (x ∈ A ↔ x ∈ B)

31
Set Terminology : Set Equality
Example
• Let two sets A = {1, 2, 3} and B = {3, 2, 1}
then A = B (true or false?)
• Let two sets A = {1, 2, 3} and B = {3, 3, 2, 1, 2, 1}
then A = B (true or false?)

A = {x: x is an odd positive integer less than 10}

B = {1, 3, 5, 7, 9}

A=B?
32
Set Terminology : Set Cardinality
Definition
Let S be a set. If there are exactly n distinct elements in S where n is a
nonnegative integer, we say that S is a finite set and that n is the
cardinality of S. The cardinality of S is denoted by |S|.

The term cardinality comes from the common usage of the term cardinal number as
the size of a finite set.

33
Set Terminology : Set Cardinality
Example

5.

26

5.

34
Set Terminology : Finite Set and Infinite
Set
Definition : Finite Set

Let S be a set. If there are exactly n distinct elements in S where n is a

nonnegative integer, we say that S is a finite set
• R = {1, 2, 3, 4, 5} finite set

Definition : Infinite Set

A set is said to be infinite if it is not finite.

• The set of positive integers is infinite.

35
Set Terminology : Power Set
Definition
Given a set S, the power set of S is the set of all subsets of the set S. The
power set of S is denoted by P(S).

• What is the power set of the set {0,1,2}?

• What is the power set of the empty set?

• What is the power set of the set{∅}?

36
Set Terminology : Cartesian Product

Definition
Let A and B be sets. The Cartesian product of A and B, denoted by A x B,
is the set of all ordered pairs (a, b) where a ∈ A and b ∈B.
Hence A×B = {(a, b) | a ∈ A ∧ b ∈ B}.

Let, A = {1, 2} and b = {a, b, c}

A x B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}
BxA= ?

37
 Set Operations
Nakib Hayat Chowdhury
Lecturer, Dept. of CSE, VU

38
Every extraordinary feat began in ordinary circumstances. I will start my journey of success from where I am now.
 Set Operation
Operations
• Union (∪)
• Intersection (∩)
• Difference (−)
• Complement (“—”)
• Symmetric Difference (⊕)

39
 Set Operation : Union

Definition
Let A and B be sets. The union of the sets A and B, denoted by A ∪ B, is
the set that contains those elements that are either in A or in B, or in both.

A = {1, 2, 5, 7}, B = {3, 4, 5, 6} AUB= { 1, 2, 3, 4, 5, 6, 7}

40
 Set Operation : Intersection

Definition
Let A and B be sets. The intersection of the sets A and B, denoted by
A∩B, is the set containing those elements in both A and B.

A = {1, 2, 5, 7}, B = {3, 4, 5, 6} {5}

41
Union and Intersection in VD

42
Set Operation : Union and Intersection

Examples
A = {1, 2, 3, 4}, B = {3, 4, 5, 6, 7}, C = {2, 3, 5, 7}

• AUB= ?
• AUC= ?
• A∩B= ?
• B∩C=?

43
 Disjoint Sets
Definition
Two sets are called disjoint if their intersection is the empty set.
i.e. A ∩ B = ∅ .

{a, b} and {3, 4} are disjoint U

A B

44
 Disjoint Union
Definition
• When A and B are disjoint, the disjoint union operation is well defined.
The circle above the union symbol indicates disjointedness.

A B

45
Set Operation : principle
of inclusion–exclusion

46
 Set Operation : Difference
Definition
Let A and B be sets. The difference of A and B, denoted by A−B, is the
set containing those elements that are in A but not in B. The difference of
A and B is also called the complement of B with respect to A.

• The difference of A and B is also called the complement of B with respect to A.

• The difference of sets A and B is sometimes denoted by A \ B.

47
 Set Operation : Difference
Example
• Let A = {1, 3, 5}, B = {1, 2, 3}
A – B = {5}
• Let A = {1, 3, 5, 6}, B = {1, 2, 3,9,10}
A – B = {5, 6}

48
Set Operation : Complement
Definition

49
Set Operation : Symmetric Difference

Definition

A⊕B U

A B

50
How to Prove a Set identities
Five Methods

• Use the basic set identities

• Use membership tables

• Prove each set is a subset of each other

• Use set builder notation and logical equivalences

• Use Venn Diagram

51
 Set identities

A∪∅ = A A∪U = U
Identity Law Domination law
A∩U = A A∩∅ = ∅
A∪A = A
Idempotent Law (Ac)c = A Complement Law
A∩A = A
A∪B = B∪A (A∪B)c = Ac ∩ Bc
Commutative Law De Morgan’s Law
A∩B = B∩A (A∩B)c = Ac ∪ Bc

A∪(B∪C) = (A∪B)∪C A∩(B∪C) = (A∩B)∪(A∩C)

Associative Law Distributive Law
A∩(B∩C) = (A∩B)∩C A∪(B∩C) = (A∪B)∩(A∪C)

A∪(A∩B) = A A ∪ Ac = U
Absorption Law Complement Law
A∩(A∪B) = A A ∩ Ac = ∅
Set identities: (A ∪ B ) ∪ C = A ∪ (B ∪ C )
Using set definition and set builder notation

Proof : (A∪B )∪C = {x | x ∈ A ∪B ∨ x ∈ C } (by def.)

= {x | (x ∈ A ∨ x ∈ B ) ∨ x ∈ C } (by def.)
= {x | x ∈ A ∨ ( x ∈ B ∨ x ∈ C ) } (logical assoc.)
= {x | x ∈ A ∨ (x ∈ B ∪ C ) } (by def.)
= A∪(B ∪C ) (by def.)


53
Use set builder notation and logical equivalences

54
Set identities : A ∩ (B∪C) = (A∩B) ∪ (A∩C)
Use a membership table

55
Use set identity law

56
 Set Identities via Venn

It’s often simpler to understand an identity by drawing a Venn

Diagram.
For example DeMorgan’s first law

can be visualized as follows.

57
 Visual DeMorgan

A: B:

58
 Visual DeMorgan

A: B:

A ∪B
:

59
 Visual DeMorgan

A: B:

L5 60
 Visual DeMorgan

A: B:

A B
: :

61
 Visual DeMorgan

A: B:

A B
: :

62
 Visual DeMorgan

=
L5 63