UNIVERSITY OF SOUTHERN MINDANAO

Discrete Mathematics
(CpE 04)
Prepared by:
JEANNALEN P. LUNOD
Department of Computer Engineering
 Topic Outline
• Cartesian products
• Definition
• Cartesian Product of more than 2 sets
• Set operations

Discrete Mathematics - Cartesian Products 2

 Intended Learning Outcomes
• ILO1: obtain the Cartesian product of two
or more sets
• ILO2: perform operations on set
• ILO3: draw the Venn diagram of a given
set
• ILO4: solve problems using Venn diagram

Discrete Mathematics - Cartesian Products 3

 Definition
• ordered n-tuple (a1,a2,…,an)
▪ The ordered collection that has a1 as its
first element, a2 as its second element,…,
and an as its nth element.

Discrete Mathematics - Cartesian Products 4

 Definition
• 2 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
▪ Note: (a,b)  (b,a) unless a=b
▪ 2-tuples are called ordered pairs

Discrete Mathematics - Cartesian Products 5

 Cartesian Product of A and B
• 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 x B = { (a,b) | a A  b  B }

Discrete Mathematics - Cartesian Products 6

 Example:
1. What is the Cartesian product of A =
{1, 2} and B={a, b, c}?
ans.
A x B= { (1,a), (1,b), (1,c), (2,a), (2,b), (2,c)
}

Discrete Mathematics - Cartesian Products 7

2. If X = {1, 2, 3} andY={a, b}, find:
a) X xY

b) Y x X

c) X x X

d) Y xY

Discrete Mathematics - Cartesian Products 8

ans.
a) X x Y = { (1,a), (1,b), (2,a), (2,b), (3,a),
(3,b) }
b) Y x X = { (a,1), (a,2), (a,3), (b,1), (b,2),
(b,3) }
c) X x X = { (1,1), (1,2), (1,3), (2,1), (2,2),
(2,3), (3,1), (3,2), (3,3) }
d) Y x Y = { (a,a), (a,b), (b,a), (b,b) }

Discrete Mathematics - Cartesian Products 9

 Cartesian Product of more
than 2 sets
• What is the Cartesian product A x B x C,
where A = {0, 1}, B = {1, 2}, and C = {0, 1, 2}?
ans:
A x B x 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) }

Discrete Mathematics - Cartesian Products 10

 Set Operations
• A  B (union of sets A and B)
• The set that contains those elements that
are either in A or in B, or in both.

▪ A  B = { x | xA  xB }
▪ Example: The union of the sets {1, 3, 5}
and {1, 2, 3} that is:
{1, 3, 5}  {1, 2, 3} = {1, 2, 3, 5}
Discrete Mathematics - Cartesian Products 11
• A  B (intersection of the sets A and B)
• The set containing those elements in both
A and B

▪ A  B = { x | xA  xB }
▪ Example: {1, 3, 5}  {1, 2, 3} = {1, 3}

Discrete Mathematics - Cartesian Products 12

▪ 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}
▪ A  B =  ; A and B are DISJOINT

Discrete Mathematics - Cartesian Products 13

• A - B (Difference of A and B)
• The set containing those elements that
are in A but not in B
• is also called the complement of B with
respect to A

▪ A – B = { x | xA  xB }
▪ Examples:
• {1, 3, 5} - {1, 2, 3} = {5}
• {1, 2, 3} - {1, 3, 5} = {2}
Discrete Mathematics - Cartesian Products 14
• A (Complement of the set A)
• The complement of A with respect to U
(U-A) U
▪ A = { x | xA }
▪ Example:
▪ Let A = {a, e, i, o, u} where the universal
set is the set of letters of the English
alphabet. What is A?
▪ A = {x|x is a consonant letter of the
English alphabet}
Discrete Mathematics - Cartesian Products 15
• A  B (Symmetric Difference of A and B)
• The set containing those elements in
either A or B, but not in both A and B.

▪ Example:
• Find the symmetric difference of {1,3,5}
and {1,2,3}.
• {1, 3, 5}  {1, 2, 3} = {2,5}
Discrete Mathematics - Cartesian Products 16
 Exercises:
1. Let A = {1, 2, 3, 4, 5} and B = {0, 3, 6}. Find:
a) A  B
b) A  B
c) A - B
d) B - A
2. Let A = {0, 2, 4, 6, 8, 10}, B = {0, 1, 2, 3, 4, 5,
6} and C = {4, 5, 6, 7, 8, 9, 10}. Find
a) ABC
b) ABC
Discrete Mathematics - Cartesian Products 17
 a) (AB)  C
b) (AB)  C
3. Draw the Venn diagrams for each of these
combinations of the sets A, B and C.
a) A  (BC)
a) A  B  C
b) (A - B)  (A - C)  (B - C)

Discrete Mathematics - Cartesian Products 18

4) Find the sets A and B if A - B = {1, 5, 7, 8},
B - A = {2, 10} and A  B = {3, 6, 9}.

Discrete Mathematics - Cartesian Products 19

 Answers to some of the
Exercises:
1. Let A = {1, 2, 3, 4, 5} and B = {0, 3, 6}. Find:
a) A  B
b) A  B
ans.
a) A  B = { 0, 1, 2, 3, 4, 5, 6 }
b) A  B = { 3 }

Discrete Mathematics - Cartesian Products 20

2. Let A = {0, 2, 4, 6, 8, 10},
B = {0, 1, 2, 3, 4, 5, 6} and
C = {4, 5, 6, 7, 8, 9, 10}.
Find:
a) ABC
b) ABC
ans.
a) ABC = { 4, 6 }
b) ABC = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

Discrete Mathematics - Cartesian Products 21

3. Draw the Venn diagrams for each of these
combinations of the sets A, B and C.
a) A  (BC)
Solution:
First, shade the region
representing for BC

BC
Discrete Mathematics - Cartesian Products 22
• then identify region in set A being
intersected by the shaded region
representing BC
ans.

A  (BC)
Discrete Mathematics - Cartesian Products 23
4. Find the sets A and B if A - B = {1, 5, 7, 8},
B - A = {2, 10} and A  B = {3, 6, 9}.
Solution:
A - B = { 1, 5, 7, 8 }

Discrete Mathematics - Cartesian Products 24

• B - A = { 2, 10 }

• A  B = { 3, 6, 9 }

Discrete Mathematics - Cartesian Products 25

• Combining the 3 diagrams into one diagram,
we can easily determine sets A and B:

Ans. A = { 1, 3, 5, 6, 7, 8, 9 }
B = { 2, 3, 6, 9, 10 }
Discrete Mathematics - Cartesian Products 26
 Word problem on Venn
Diagram
1. In a class of 60 students, 25 students
play cricket and 20 students play tennis,
and 10 students play both the games.
Find the number of students who play
neither?

Discrete Mathematics - Cartesian Products 27

 Solution:
• 25 students play
• 10 students play cricket
both the games • 10+15=25
Cricket Tennis Cricket Tennis

10 15 10

Discrete Mathematics - Cartesian Products 28

 • All in all, there are 35
students involved in
• 20 students play playing cricket
tennis and/or tennis
• 10+10=20 • 15+10+10=35
Cricket Tennis Cricket Tennis

15 10 10 15 10 10

Discrete Mathematics - Cartesian Products 29

• Since there are 60 students in a class, 60-35
= 25.
• Thus, there are 25 students who play
neither
Cricket Tennis

15 10 10

25
Discrete Mathematics - Cartesian Products 30
2. A travel agent surveyed 100 people to find
out how many of them had visited the cities
of Melbourne and Brisbane. Thirty-one people
had visited Melbourne, 26 people had been to
Brisbane, and 12 people had visited both
cities. Draw a Venn diagram to find the
number of people who had visited:
a) Melbourne or Brisbane
b) Brisbane but not Melbourne
Discrete Mathematics - Cartesian Products 31
c) Only one of the two cities
d) Neither city

Discrete Mathematics - Cartesian Products 32

 Solution:
• “12 people had • “31 people had
visited both visited Melbourne”
cities” • 19+12=31
Melbourne Brisbane Melbourne Brisbane

12 19 12

Discrete Mathematics - Cartesian Products 33

 Find the number of
• “26 people had people who had
been to Brisbane” visited:
• 12+14=26 a) Melbourne or
Brisbane = 45
Melbourne Brisbane
• 19+12+14=45
Melbourne Brisbane
19 12 14
19 12 14

Discrete Mathematics - Cartesian Products 34

 c) Only one of the
b) Brisbane but not
two cities = 33
Melbourne = 14
• 19+14=33
Melbourne Brisbane Melbourne Brisbane

19 12 14 19 12 14

Discrete Mathematics - Cartesian Products 35

d) Neither city = 55
• “A travel agent surveyed 100 people”, thus,
100-19-12-14 = 55
Melbourne Brisbane

19 12 14

55

Discrete Mathematics - Cartesian Products 36

3. Twenty-four dogs are in a kennel. Twelve of
the dogs are black, six of the dogs have short
tails, and fifteen of the dogs have long hair.
There is only one dog that is black with a
short tail and long hair. Two of the dogs are
black with short tails and do not have long
hair. Two of the dogs have short tails and long
hair but are not black. If all of the dogs in the
kennel have at least one of the mentioned
characteristics, how many dogs
Discrete Mathematics - Cartesian Products 37
are black with long hair but do not have short
tails?

Discrete Mathematics - Cartesian Products 38

4. Refer to a group of 191 students, of which
▪ 10 are taking French, business, and
music;
▪ 36 are taking French and business;
▪ 20 are taking French and music;
▪ 18 are taking business and music;
▪ 65 are taking French;
▪ 76 are taking business; and
▪ 63 are taking music.
Discrete Mathematics - Cartesian Products 39
a. How many are taking French and music
but not business?
b. How many are taking business and neither
French nor music?
c. How many are taking French or business
(or both)?
d. How many are taking music or French (or
both) but not business?
e. How many are taking none of the three
subjects?
Discrete Mathematics - Cartesian Products 40
 Summary
• 2 ordered n-tuples are equal if and only if
each corresponding pair of their elements is
equal
• 2-tuples are called ordered pairs
• 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.

Discrete Mathematics - Cartesian Products 41

• A  B is the set that contains those
elements that are either in A or in B, or in
both.
• A  B is the set containing those elements in
both A and B
• A - B is the e set containing those elements
that are in A but not in B.

Discrete Mathematics - Cartesian Products 42

• A is the complement of A with respect to U
(U-A)
• A  B is the set containing those elements in
either A or B, but not in both A and B.

Discrete Mathematics - Cartesian Products 43

 References
• Johnsonbaugh, R. (2018). Discrete
Mathematics 8th Edition. Pearson.
• Levin, O. (2016). Discrete Mathematics: An
Open Introduction 3rd Edition.
• Rosen, K.H. (2019). Discrete Mathematics
and Its Applications 8th Edition. New York:
McGraw-Hill.

Discrete Mathematics - Cartesian Products 44