Exercises 4-Lecture 4
Relations
Prepared by : Dr. Sarah Alhammad
Question#1:
Determine whether each of the following relations are reflexive, symmetric and
transitive:
(i) Relation R in the set A = {1, 2, 3…13, 14} defined as
R = {(x, y): 3x − y = 0}
(ii) Relation R in the set N of natural numbers defined
as R = {(x, y): y = x + 5 and x < 4}
(iii) Relation R in the set A = {1, 2, 3, 4, 5, 6} as
R = {(x, y): y is divisible by x}
(iv) Relation R in the set Z of all integers defined as
R = {(x, y): x − y is as integer}
Solution
(i) A = {1, 2, 3 … 13, 14}
R = {(x, y): 3x − y = 0}
∴ R = {(1, 3), (2, 6), (3, 9), (4, 12)}
R is not reflexive since (1, 1), (2, 2) … (14, 14) ∉ R.
Also, R is not symmetric as (1, 3) ∈ R, but (3, 1) ∉ R. [3(3) − 1 ≠ 0]
Also, R is not transitive as (1, 3), (3, 9) ∈ R, but (1, 9) ∉ R. [3(1) − 9 ≠ 0]
Hence, R is neither reflexive, nor symmetric, nor transitive.
(ii) R = {(x, y): y = x + 5 and x < 4} = {(1, 6), (2, 7), (3, 8)}
It is clear that (1, 1) ∉ R.
∴ R is not reflexive.
(1, 6) ∈ R But, (1, 6) ∉ R.
∴ R is not symmetric.
Now, since there is no pair in R such that (x, y) and (y, z) ∈ R, then (x, z) cannot
belong to R.
∴ R is not transitive.
Hence, R is neither reflexive, nor symmetric, nor transitive.
CS 100 T
First semester of the academic year 1442 H
(iii) A = {1, 2, 3, 4, 5, 6}
R = {(x, y): y is divisible by x}
We know that any number (x) is divisible
by itself. So, (x, x) ∈ R
∴ R is
reflexi
ve.
Now,
(2, 4) ∈ R
But, (4, 2) ∉ R.
∴ R is not symmetric.
Let (x, y), (y, z) ∈ R. Then, y is divisible by x and z is divisible by y.
∴ z is divisible by x.
⇒ (x, z) ∈ R
∴ R is transitive.
Hence, R is reflexive and transitive but not symmetric.
(iv) R = {(x, y): x − y is an integer}
Now, for every x ∈ Z, (x, x) ∈ R as x − x = 0 is an integer.
∴ R is reflexive.
Now, for every x, y ∈ Z, if (x, y) ∈ R, then x − y is an integer.
⇒ −(x − y) is also an integer.
⇒ (y − x) is an integer.
∴ (y, x) ∈ R
CS 100 T
First semester of the academic year 1442 H
∴ R is
symmetr
ic. Now,
Let (x, y) and (y, z) ∈ R, where x, y, z ∈ Z.
⇒ (x − y) and (y − z) are integers.
⇒ x − z = (x − y) + (y − z) is an integer.
∴ (x, z) ∈ R
∴ R is transitive.
Hence, R is reflexive, symmetric, and transitive.
Question#2:
Check whether the relation R defined in the set {1, 2, 3, 4, 5, 6} as R =
{(a, b): b = a + 1} is reflexive, symmetric or transitive.
Solution
Let A = {1, 2, 3, 4, 5, 6}.
A relation R is defined on set A as: R = {(a, b): b = a + 1}
∴ R = {(1, 2), (2, 3), (3, 4), (4, 5), (5, 6)}
we can find (a, a) ∉ R, where
a ∈ A. For instance,
(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6) ∉ R
∴ R is not reflexive.
It can be observed that (1, 2) ∈ R, but (2, 1) ∉ R.
∴ R is not
symmetric.
Now, (1, 2),
CS 100 T
First semester of the academic year 1442 H
(2, 3) ∈ R
But, (1, 3) ∉ R
∴ R is not transitive
Hence, R is neither reflexive, nor symmetric, nor transitive.
Question#3:
Show that the relation R in R defined as R = {(a, b): a ≤ b}, is reflexive
and transitive but not symmetric.
Solution
R = {(a, b): a ≤ b}
Clearly (a, a) ∈ R [as a = a]
∴ R is reflexive.
Now, (2, 4) ∈ R (as 2 < 4)
But, (4, 2) ∉ R as 4 is greater than 2.
∴ R is not
symmetric. Now,
let (a, b), (b, c) ∈
R. Then, a ≤ b
and b ≤ c
⇒a≤c
⇒ (a, c) ∈ R
∴ R is transitive.
Hence R is reflexive and transitive but not symmetric.
CS 100 T
First semester of the academic year 1442 H
Question#4:
Let A = {1, 2, 3} and B = {1, 2, 3, 4}. The relation R1 is on A
and the relation R2 is on B:
R1 = {(1, 1), (2, 2), (3, 3)} and
R2 = {(1, 1), (1, 2), (1, 3), (1, 4)}.
Determine the following relations.
a. R1 ∪ R2
b. R1 ∩ R2
c. R1 − R2
d. R2 − R1
Solution
a. R1 ∪ R2 = {(1, 1), (2, 2), (3, 3),(1, 2), (1, 3), (1, 4)}.
b. R1 ∩ R2 = {(1, 1)}
c. R1 − R2 = {(2, 2), (3, 3)}
d. R2 − R1 = {(1, 2), (1, 3), (1, 4)}.
CS 100 T
First semester of the academic year 1442 H
Question#5:
LetR be arelation from{1,2,3} to {1,2,3,4} and
let S be the relation from {1, 2, 3, 4} to {0, 1, 2} where,
R ={(1,1),(1,2),(2,4),(3,2),(4,3)}
S ={(1,0),(2,4),(3,1),(3,2),(4,1)}
What is the composite of the relations R and S, S ◦ R?
S◦ R=
Solution
S ◦ R = {(1,0),(1,4),(2,1),(3,4),(4,1),(4,2)}
Question#6:
Let P = {2, 3, 4, 5}. Consider the relation R and S on P defined by
R = {(2, 2), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5), (5, 3)}
S = {(2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 3), (4, 5), (5, 2), (5, 5)}.
Find the matrices of the above relations.
Use matrices to find the following composition of the relation R and S.
(i)RoS (ii)RoR (iii)SoR
Solution
CS 100 T
First semester of the academic year 1442 H
The matrices of the relation R and S are a shown in fig:
To obtain the composition of relation R and S. First multiply
MR with MS to obtain the matrix MR x MS as shown in fig:
The non zero entries in the matrix MR x MS tells the elements related in
RoS. So,
Hence the composition R o S of the relation R and S is
R o S = {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (4, 2), (4, 5), (5, 2), (5, 3), (5, 4
), (5, 5)}.
(ii) First, multiply the matrix MR by itself, as shown in fig
CS 100 T
First semester of the academic year 1442 H
Hence the composition R o R of the relation R and S is
1. R o R = {(2, 2), (3, 2), (3, 3), (3, 4), (4, 2), (4, 5), (5, 2), (5, 3), (5, 5)}
(iii) Multiply the matrix MS with MR to obtain the matrix MS x MR as
shown in fig:
The non-zero entries in matrix MS x MR tells the elements related in S o
R.
Hence the composition S o R of the relation S and R is
S o R = {(2, 4) , (2, 5), (3, 3), (3, 4), (3, 5), (4, 2), (4, 4), (4, 5), (5, 2), (5,
3), (5, 4), (5, 5)}.
CS 100 T
First semester of the academic year 1442 H
Question#7:
Represent each of these relations on {1, 2, 3} with a matrix (with the
elements of this set listed in
increasing order).
a {(1, 1),(1, 2),(1, 3)}
b {(1, 2),(2, 1),(2, 2),(3, 3)}
c {(1, 1),(1, 2),(1, 3),(2, 2),(2, 3),(3, 3)}
Solution
a {(1, 1),(1, 2),(1, 3)}
111
000
000
b {(1, 2),(2, 1),(2, 2),(3, 3)}
010
110
001
c {(1, 1),(1, 2),(1, 3),(2, 2),(2, 3),(3, 3)}
111
011
001
CS 100 T
First semester of the academic year 1442 H
Question#8:
Draw the directed graphs representing each of the relations
a. {(1, 2),(1, 3),(1, 4),(2, 3),(2, 4),(3, 4)}
b. {(1, 1),(1, 4),(2, 2),(3, 3),(4, 1)}
c. {(1, 2),(1, 3),(1, 4),(2, 1),(2, 3),(2, 4),(3, 1),(3, 2),(3, 4),(4, 1),(4,
2),(4, 3)}
Solution:
a.
b.
c.
CS 100 T
First semester of the academic year 1442 H
Question#9:
Determine whether the relation represented by the digraph shown below
are reflexive, symmetric, antisymmetric, and/or transitive.
a.
b.
Solution:
a. Not reflexive because every vertex does not have a self loop.
Not symmetric because we do not have (b, a) for (a, b).
Not antisymmetric because we have (b, c) and (c, b).
CS 100 T
First semester of the academic year 1442 H
Not transitive because the path for (b, c), (c, b) from b to b is missing the
edge(b, b).
b. Not reflexive because every vertex does not have a self loop.
Not symmetric because we do not have (c, a) for (a, c).
Is antisymmetric because there are no edges that go in the opposite
direction for each edge.
Not transitive because we do not have (a, d) for the edges (a, c) and (c, d).
Question#10:
Let R be the relation on the set {0, 1, 2, 3} containing the ordered pairs
(0, 1),(1, 1),(1, 2),(2, 0),(2, 2),(3, 0).
Find a) reflexive closure of R
b) symmetric closure of R
Solution:
a) reflexive closure of R
We need to add (a, a) in R to make a reflexive closure. {(0, 0),(0, 1),(1,
1),(1, 2),(2, 0),(2, 2),(3, 0),(3, 3)}
b) symmetric closure of R
We need to add (b, a) for each (a, b) in R to make a symmetric closure.
{(0, 1),(0, 2),(0, 3),(1, 0),(1, 1),(1, 2),(2, 0),(2, 1),(2, 2),(3, 0)}
CS 100 T
First semester of the academic year 1442 H
Question#11:
Are these equivalence relations on {0, 1, 2}
(a) {(0, 0),(1, 1),(0, 1),(1, 0)}
(b) {(0, 0),(1, 1),(2, 2),(0, 1),(1, 2)}
(c) {(0, 0),(1, 1),(2, 2),(0, 1),(1, 2),(1, 0),(2, 1)}
(d) {(0, 0),(1, 1),(2, 2),(0, 1),(0, 2),(1, 0),(1, 2),(2, 0),(2, 1)}
(e) {(0, 0),(1, 1),(2, 2)}
Solution:
(a) R is not reflexive: (2, 2) ∈/ R. Thus, by definition, R is not an
equivalence relation.
(b) R is not symmetric: (1, 2) ∈ R but (2, 1) ∈/ R. Thus R is not an
equivalence relation.
(c) R is not transitive: (0, 1),(1, 2) ∈ R, but (0, 2) ∈/ R. Thus R is not an
equivalence relation.
(d) R is reflexive, symmetric, and transitive. Thus R is an equivalence
relation.
Question#12:
Give one possible partition for {1, 2, 3, 4, 5, 6,7,8}
Solution
{1,3}, {2,7,8}, {4,5,6}
CS 100 T
First semester of the academic year 1442 H
Question#13:
Consider the equivalence relation R induced by the partition
P={{1},{3},{2,4,5,6}}
of A={1,2,3,4,5,6}
(a) Write the equivalence classes for this equivalence relation. (b) Write
the equivalence relation as a set of ordered pairs.
Solution :
(a) [1]={1} [2]={2,4,5,6} [3]={3} [1]={1} [2]={2,4,5,6} [3]={3}
(b) From the two 1-element equivalence classes {1}{1} and {3}{3}, we
find two ordered pairs (1,1)(1,1) and (3,3)(3,3) that belong to RR. From
the equivalence class {2,4,5,6}{2,4,5,6}, any pair of elements produce an
ordered pair that belongs to R. Therefore,
R={(1,1),(3,3),(2,2),(2,4),(2,5),(2,6),(4,2),(4,4),(4,5),(4,6),(5,2),(5,4),(5,5)
,(5,6),(6,2),(6,4),(6,5),(6,6)}
