Discrete Mathematics and Its Applications

Chapter 2: Basic Structures:

Sets, Functions, Sequences,
and Sums (1)

1
2.1 Sets
Introduction

 Sets are used to group objects together. Often

the objects in a set have similar properties.
 Data structures: Array, linked list, boolean
variables, …
DEFINITION 1
A set is an unordered collection of objects.

2
2.1 Sets
DEFINITION 2
The objects in a set are called the elements, or members, of the set. A set is
said to contain its elements.

• aA: a is an element of the set A.

• aA: a is not an element of the set A.
• Note: lower case letters are used to denote elements.

3
2.1 Sets

 Ways to describe a set:

 Use { … }
 E.g. {a, b, c, d} – A set with four elements.
• V = {a, e, i, o, u} – The set V of all vowels in English
alphabet.
• O = {1, 3, 5, 7, 9} – The set O of odd positive integers less
than 10.
• {1, 2, 3, …, 99} – The set of positive integers less than
100.
 Use set builder notation: characterize all the elements in the set
by stating the property or properties.
 E.g. O = { x | x is an odd positive integer less than 10}
• O = { x  Z+| x is odd and x < 10}

4
2.1 Sets
 Commonly accepted letters to represent sets
 N = {0, 1, 2, 3, …}, the set of natural numbers
 Z = {…, -2, -1, 0, 1, 2, …}, the set of integers
 Z+ = {1, 2, 3, …}, the set of positive integers
 Q = {p/q | p  Z, q Z, and q ≠ 0}, the set of rational numbers
 R, the set of real numbers
 Sets can have other sets as members
 Example: The set {N, Z, Q, R} is a set containing four elements,
each of which is a set.

5
2.1 Sets
DEFINITION 3
Two sets are equal if and only if they have the same elements. That is, if
A and B are sets, then A and B are equal if and only if
x(x A↔ x B).  
We write A = B if A and B are equal sets.

• Example: 
• Are sets {1, 3, 5} and {3, 5,1} equal?
• Are sets {1, 3, 3, 3, 5, 5, 5, 5} and {1, 3, 5} equal?

6
2.1 Sets
 Venn Diagrams
 Represent sets graphically
 The universal set U, which contains all the objects under
consideration, is represented by a rectangle. The set varies
depending on which objects are of interest.
 Inside the rectangle, circles or other geometrical figures are used to
represent sets.
 Sometimes points are used to represent the particular elements of the
set.

U
a
u
V e
o i

7
2.1 Sets
 Empty Set (null set): a set that has no elements, denoted
by ф or {}.
 Example: The set of all positive integers that are greater
than their squares is an empty set.
 Singleton set: a set with one element
 Compare: ф and {ф}
 Ф: an empty set. Think of this as an empty folder
 {ф}: a set with one element. The element is an empty set. Think of
this as an folder with an empty folder in it.

8
2.1 Sets
DEFINITION 4
The set A is said to be a subset 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.

 A  B if and only if the quantification

 x(x A → x B) is true

A B

9
2.1 Sets
 every non-empty set S is guaranteed to have at least two
subset, the empty set and the set S itself, that is ф  S and
S  S.

THEOREM 1
For every set S,
(i) ф  S and (ii) S  S

 If A is a subset of B but A ≠ B, then A  B or A is a proper subset of B.

 For A B to be true, it must be the case that A  B and there must exist
an element x of B that is not an element of A, i.e.
 
x(x A →x B)Λ  x(x B Λx A)

10
2.1 Sets
DEFINITION 5
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|.

 Example:
 Let A be the set of odd positive integers less than 10. Then |A| = 5.
 Let S be the set of letters in the English alphabet. Then |A| = 26.
 Null set has no elements, | ф | = 0.

11
 2.1 Sets
DEFINITION 6
A set is said to be infinite if it is not finite. 
 Example: The set of positive integers is infinite.

12
 2.1 Sets
DEFINITION 7
Given a set, 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).

 Example:
 What is the power set of the set {0,1,2}?
Solution: P({0,1,2}) = {ф, {0}, {1}, {2}, {0,1}, {0,2}, {1,2}, {0,1,2}}
 What is the power set of the empty set? What is the power set of the set
{ф}?
Solution: The empty set has exactly one subset, namely, itself.
P(ф ) = {ф}
The set {ф} has exactly two subsets, namely, ф and the set {ф}.
P({ф}) = {ф, {ф}}
 If a set has n elements, its power set has 2n elements.
13
 2.1 Sets
Cartesian Products
 Sets are unordered, a different structure is needed to
represent an ordered collections – ordered n-tuples.
DEFINITION 8
The ordered n-tuple (a1, a2,…, an) is the ordered collection that has a1
as its first element, a2 as its second element, …, and an as its nth
element.

 Two ordered n-tuples are equal if and only if each

corresponding pair of their elements is equal.
 (a1, a2,…, an) = (b1, b2,…, bn) if and only if ai = bi for i = 1, 2, …, n

14
 2.1 Sets
DEFINITION 9
Let A and B be sets. The Cartesian product of A and B, denoted by A ×
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}.

 Example:
What is the Cartesian product of A = {1,2} and B = {a,b,c}?
Solution:
A × B = {(1,a), (1,b), (1,c), (2,a), (2,b), (2,c)}
 Cartesian product of A × B and B × A are not equal, unless
A = ф or B = ф (so that A × B = ф ) or A = B.
B × A = {(a,1),(a,2),(b,1),(b,2),(c,1),(c,2)}
15
 2.1 Sets
DEFINITION 10
The Cartesian product of sets A1, A2, …, An, denoted by A1 × A2 × …
× An is the set of ordered n-tuples (a1, a2, …, an), where ai belongs to
Ai for i = 1,2, …, n. In other words,

A1 × A2 × … × An = {(a1, a2, …, an) | ai Ai for i = 1,2, …, n}.

 Example:
What is the Cartesian product of A × B × C where A= {0,1},
B = {1,2}, and C = {0,1,2}?
Solution:
A × B × C= {(0,1,0), (0,1,1), (0,1,2), (0,2,0), (0,2,1), (0,2,2),
(1,1,0), (1,1,1), (1,1,2), (1,2,0), (1,2,1), (1,2,2)}
16
 2.1 Sets
 Using Set Notation with Quantifiers
  xS(P(x)) is shorthand for x(x S → P(x))
 xS(P(x)) is shorthand for x(xS Λ P(x))
 Example:
  x R(x2 ≥ 0) mean?
What do the statements
Solution:
For every real number x, x2 ≥ 0. “The square of every real
number
is nonnegative.
 The truth set of P is the set
 of elements x in D for which P(x)
is true. It is denoted by {x D |P(x)}.
 Example: What is the truth set of the predicate P(x) where the domain is
the set of integers and P(x) is “|x| = 1”?
Solution: {-1,1} 17
Discrete Mathematics and Its Applications

Chapter 2: Basic Structures:

Sets, Functions, Sequences,
and Sums (2)

CSE 211
Department of Computer Science and Engineering, CUET 18
2.2 Set Operations
Introduction
DEFINITION 1
Let A and B be sets. The union of the sets A and B, denoted by A U B, is the
set that contains those elements that are either in A or in B, or in both.

 A U B = { x | x A v x B}

19

 Shaded area represents A U B.

2.2 Set Operations

 Example:
 The union of the sets {1,3,5} and {1,2,3} is the set {1,2,3,5}; that is
{1,3,5} U {1,2,3} = {1,2,3,5}
 The union of the set of all computer science majors at your school
and the set of all mathematics majors at your school is the set of
students at your school who are majoring either in mathematics or
in computer science (or in both).
 SQL command when retrieving data from the student database:
select * from student
where major =‘cs’
UNION
select * from student
where major = ‘math’

20
2.2 Set Operations
DEFINITION 2
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 ∩ B = { x | x A Λ x B }

21

 Shaded area represents A ∩ B.

2.2 Set Operations

 Example:
 The intersection of the sets {1,3,5} and {1,2,3} is the set {1,3}; that
is {1,3,5} ∩ {1,2,3} = {1,3}
 The intersection of the set of all computer science majors at your
school and the set of all mathematics majors at your school is the
set of students at your school who are joint majors in mathematics
and in computer science.
 SQL command when retrieving data from the student database:
select *
from csMajor, mathMajor
where csMajor.studentID = mathMajor.studentID

22
2.2 Set Operations
DEFINITION 3
Two sets are called disjoint if their intersection is the empty set.

 Example: Let A = {1,3,5,7,9} and B = {2,4,6,8,10}. Because A ∩ B = ф,

A and B are disjoint.

23
2.2 Set Operations
DEFINITION 4
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.

 A – B = { x | x A Λ x B}

24

 A – B is shaded.
2.2 Set Operations

 Example:
 {1,3,5} - {1,2,3} = {5}
 {1,2,3} – {1,3,5} = {2}
 The difference of the set of computer science majors at your school
and the set of mathematics majors at your school is the set of all
computer science majors at your school who are not mathematics
majors.
 SQL command when retrieving data from the student database:
select *
from csMajor
where csMajor.studentID NOT IN (select studentID from mathMajor)

25
2.2 Set Operations
DEFINITION 5
Let U be the universal set. The complement of the set A, denoted by Ā, is the
complement of A with respect to U. In other words, the containing those
complement of the set A is U – A.

 Ā = { x | x A }

26

 Ā is shaded.
2.2 Set Operations

 Example:
 Let A be the set of positive integers greater than 10 (with universal
set the set of all positive integers.) Then Ā = {1,2,3,4,5,6,7,8,9,10}

27
2.2 Set Operations
Computer Representation of Sets
 Represent a subset A of U with the bit string of length n,
where the ith bit in the string is 1 if ai belongs to A and is 0 if
ai does not belong to A.
 Example:
 Let U = {1,2,3,4,5,6,7,8,9,10}, and the ordering of elements of U has the
elements in increasing order; that is ai = i.
What bit string represents the subset of all odd integers in U?
Solution: 10 1010 1010
What bit string represents the subset of all even integers in U?
Solution: 01 010 10101
What bit string represents the subset of all integers not exceeding 5 in
U?
Solution: 11 1110 0000
What bit string represents the complement of the set {1,3,5,7,9}?
Solution: 01 0101 0101 28
2.2 Set Operations

 The bit string for the union is the bitwise OR of the bit string
for the two sets. The bit string for the intersection is the
bitwise AND of the bit strings for the two sets.
 Example:
 The bit strings for the sets {1,2,3,4,5} and {1,3,5,7,9} are 11 1110 0000
and 10 1010 1010, respectively. Use bit strings to find the union and
intersection of these sets.
Solution:
Union:
11 1110 0000 V 10 1010 1010 = 11 1110 1010,
{1,2,3,4,5,7,9}
Intersection:
11 1110 0000 Λ 10 1010 1010 = 10 1010 0000, {1,3,5}

29
2.3 Functions
Introduction
 Function: task, subroutine, procedure, method, mapping, …
 E.g. Find the grades of student A.
int findGrades(string name){
//go to grades array,
//find the name, and find the corresponding grades
…
return grades;
}

Adams A
Chou B
Goodfriend C
Rodriguez D
Stevens F
30
2.3 Functions
DEFINITION 1
Let A and B to be nonempty sets. A function f from A to B is an assignment
of exactly one element of B to each element of A. We write f(a) = b if b is the
unique element of B assigned by the function f to the element a of A. If f is a
function from A to B, we write f: A → B.

 We can use a formula or a computer program to define a function.

Example: f(x) = x + 1
Or:
int increaseByOne(int x){
x = x + 1;
return x;
}

31
2.3 Functions

 A subset R of the Cartesian product A x B is called a relation from the

set A to the set B.
Example:
R = {(a,0),(a,1),(a,3),(b,1),(b,2),(c,0),(c,3)} is a relation from the set
{a,b,c} to the set {0,1,2,3}.
 A relation from A to B that contains one and only one ordered pair
(a,b) for every element a A, defines a function f from A to B.
Example: R={(a,2),(b,1),(c,3)}

32
2.3 Functions
DEFINITION 2
If f is a function from A to B, we say that A is the domain of f and B is the
codomain of f. If f(a) = b, we say that b is the image of a and a is a preimage
of b. The range of f is the set of all images of elements of A. Also, if f is a
function from A to B, we say that f maps A to B.

 When we define a function, we specify its domain, its codomain, and

the mapping of elements of the domain to elements in the codomain.
Two functions are equal when they have the same domain and
codomain, and map elements of their common domain to the same
elements in their common codomain. If we change either the domain
or the codomain of a function, we obtain a different function. If we
change the mapping of elements, we also obtain a different function.

33
2.3 Functions
 What are the domain, codomain, and range of the function that
assigns grades to students described in the slide 13?
Solution:
domain: {Adams, Chou, Goodfriend, Rodriguez, Stevens}
codomain: {A, B, C, D, F}
range: {A, B, C, F}
 Let f be the function that assigns the last two bits of a bit string of
length 2 or greater to that string. For example, f(11010) = 10. Then,
the domain of f is the set of all bit strings of length 2 or greater, and
both the codomain and range are the set {00,01,10,11}
 What is the domain and codomain of the function
int floor(float real){…}?
Solution: domain: the set of real numbers
codomain: the set of integer numbers

34
2.3 Functions
DEFINITION 3
If f1 and f2 be functions from A to R. Then f1 + f2 and f1 f2 are also functions
from A to R defined by
(f1 + f2 )(x) = f1(x) + f2 (x)
(f1 f2 ) (x) = f1(x) f2 (x)

 Example: Let f1 and f2 be functions from R to R such that f1(x) =x2 and
f2 (x) = x – x2. What are the functions f1 + f2 and f1 f2 ?
Solution:
(f1 + f2 )(x) = f1(x) + f2 (x) = x2 + (x – x2) = x
(f1 f2 ) (x) = f1(x) f2 (x) = x2(x – x2) = x3 – x4

35
2.3 Functions
One-to-One and Onto Functions
DEFINITION 5
A function f is said to be one-to-one, or injective, if and only if f(a) =
f(b) implies that a = b for all a and b in the domain of f. A function is
said to be an injection if it is one-to-one.

  ab(a ≠ b → f(a) ≠ f(b)) (If it’s a different element, it should map to

a different value.)
 Example: Determine whether the function f from {a,b,c,d} to {1,2,3,4,5}
with f(a) = 4, f(b) = 5, f(c) = 1 and f(d) = 3 is one-to-one.
a 1
b 2
c 3
d 4
5
Solution: Yes. 36
2.3 Functions
 Example: Determine whether the function f(x) = x2 from the set of
integers to the set of integers is one-to-one.
Solution: f(1) = f(-1) = 1, not one-to-one
DEFINITION 6
A function f whose domain and codomain are subsets of the set of real
numbers is called increasing if f(x) ≤ f(y), and strictly increasing if f(x) < f(y),
whenever x < y and x and y are in the domain of f. Similarly, f is called
decreasing if f(x) ≥ f(y), and strictly decreasing if f(x) > f(y), whenever x < y
and x and y are in the domain of f.

 A function that is either strictly increasing or strictly decreasing must

be one-to-one.

37
2.3 Functions
DEFINITION 7
A function f from A to B is called onto, or surjective, if and only if for every
element bB there is an element a  A with f(a) = b. A function f is called a
surjection if it is onto.

 Example: Let f be the function from {a,b,c,d} to {1,2,3} defined by f(a)

= 3, f(b) = 2, f(c) = 1, and f(d) = 3. Is f an onto function?
a 1
b 2
c 3
d
Solution: Yes.
 Example: Is the function f(x) = x2 from the set of integers to the set of
integers onto?
Solution: No. There is no integer x with x2 = -1, for instance. 38
 2.3 Functions
DEFINITION 8
The function f is a one-to-one correspondence or a bijection, if it is both one-
to-one and onto.

a. One-to-one, b. Onto, c. One-to-one, d. neither d. Not a

Not ontonot one-to-one and onto function
a 1 a a 1 a 1 1
b 2 b 1 b 2 b 2 a 2
c 3 c 2 c 3 c 3 b 3
4 d 3 d 4 d 4 c 4

39
2.4 Composition

DEFINITION 1
Let g be a function from the set A to the set B and let f be a function from the
set B to the set C. The composition of the functions f and g , denoted by
f ᵒ g , is defined by (f ᵒ g) (a)= f(g(a))

40
2.4 Sequences and Summations
Sequences
 A sequence is a discrete structure used to represent an ordered list
 Example: 1,2,3,5,8
1,3,9,27,81,…,30,…
DEFINITION 1
A sequence is a function from a subset of the set of integers (usually either
the set {0,1,2,…} or the set {1,2,3,…}) to a set S. We use the notation an to
denote the image of the integer n. We call an a term of the sequence.

 We use the notation {an} to denote the sequence.

 Example: Consider the sequence {an}, where an = 1/n.
The list of the terms of this sequence, beginning with a1, namely
a1, a2, a3, a4, …, starts with 1, 1/2, 1/3, 1/4, …

41
2.4 Sequences and Summations

DEFINITION 2
A geometric progression is a sequence of the form
a, ar, ar2, …, arn, …
where the initial term a and the common ratio r are real numbers.

 Example: The following sequence are geometric progressions.

{bn} with bn = (-1)n starts with 1, -1, 1, -1, 1, …
initial term: 1, common ratio: -1
{cn} with cn = 2*5n starts with 2, 10, 50, 250, 1250, …
initial term: 2, common ratio: 5
{dn} with dn = 6 *(1/3)n starts with 6,2, 2/3, 2/9, 2/27, …
initial term: 6, common ratio: 1/3

42
2.4 Sequences and Summations

DEFINITION 3
A arithmetic progression is a sequence of the form
a, a + d, a + 2d, …, a + nd, …
where the initial term a and the common difference d are real numbers.

 Example: The following sequence are arithmetic progressions.

{sn} with sn = -1 + 4n starts with -1, 3, 7, 11,…
initial term: -1, common difference: 4
{tn} with tn = 7 – 3n starts with 7, 4, 1, -2, …
initial term: 7, common difference: -3

43
2.4 Sequences and Summations

 Example: Find formulae for the sequences with the following first five
terms
(a). 1, 1/2, 1/4, 1/8, 1/16
Solution: an = 1/2n
(b). 1, 3, 5, 7, 9
Solution: an = 2* n + 1
(c). 1, -1, 1, -1, 1
Solution: an = (-1)n

44
2.4 Sequences and Summations
Summations
 The sum of the terms from the sequence {an} am + am+1, …, an can be
expressed as
n

n
a
j m
j j m
aj 
1 j  n
aj
, Or

 Example:
Express the 100
sum of the first 100 terms of the sequence {an}, where an
1 ….
= 1/n for n = 1,2,3,
Solution:
j 1 j

45
2.4 Sequences and Summations


5 2
 What is the value of j 1
j ?
Solution:

5 2
j 1
j = 1 + 4 + 9 + 16 + 25 = 55

 Expressed with a for loop:

int sum = 0;
for (int i=1; i<=5; i++){
sum = sum +i*i;
}

46
2.4 Sequences and Summations
4 3
 What is the value of the double summation
Solution: 4 3 4
 ij?
i 1 j 1
=  ij
i 1 j 1
(i  2i  3i )
i41

= 
= 66i+ 12 + 18 + 24 = 60
i 1
 Expressed with two for loops:
int sum1 = 0;
int sum2 = 0;
for (int i=1; i<=4; i++){
sum2 = 0;
for (int j=1; j<=3; j++){
sum2 = sum2 + i*j;
}
sum1 = sum1 + sum2;
}
 E.g. Find the total profit of all Subway branches in 48 states. 47