CVM University

ADIT GCET MBIT

102040405 Discrete Mathematics
Relation
1) How many different relations are there from a set with m Elements to a set with n
elements?
Ans: 𝑚𝑛
2) Let R be the relation R = {(a, b) | a<b}on the set of integers. Then 𝑅 𝑐 = ______
Ans: {(a, b)|a ≥ b}
3) How many nonzero entries does the matrix representing the relation R on
A = {1, 2, 3, ..., 100} consisting of the first 100 positive integers have if R ={(a, b) | a>b}?
Ans: 4950
4) How many nonzero entries does the matrix representing the relation R on
A = {1, 2, 3, ..., 100} consisting of the first 100 positive integers have if R ={(a, b) | a=b}?
Ans: 100
5) How many nonzero entries does the matrix representing the relation R on
A = {1, 2, 3, ..., 100} consisting of the first 100 positive integers have if R ={(a, b) |
a=b+1}?
Ans: 99
6) How many nonzero entries does the matrix representing the relation R on
A = {1, 2, 3, ..., 100} consisting of the first 100 positive integers have if R ={(a, b) | a=1}?
Ans: 100
7) How many nonzero entries does the matrix representing the relation R on
A = {1, 2, 3, ..., 100} consisting of the first 100 positive integers have if R ={(a, b) |
ab=1}?
Ans: 1
8) Let R be the relation R = {(a, b) | a divides b} on the set of positive integers.
Find 𝑅 −1 , 𝑅 𝑐
Ans: 𝑅 −1 = {(𝑎, 𝑏)|𝑏 𝑑𝑖𝑣𝑖𝑑𝑒𝑠 𝑎}.
𝑅 𝑐 = {(𝑎, 𝑏)|𝑎 𝑑𝑜𝑒𝑠𝑛𝑜𝑡 𝑑𝑖𝑣𝑖𝑑𝑒𝑠 𝑏}.
9) How many of the 16 different relations on {0, 1} contain the pair (0, 1)?
Ans: 8

1) List the ordered pairs in the relation R from

A = {0, 1, 2, 3, 4, 5} to B = {0, 1, 2, 3, 4, 5}, where (a, b) ∈ R
if and only if
𝑎) 𝑎 ≠ 𝑏.
𝑏) 𝑎 − 𝑏 = 4.
𝑐) 𝑎 | 𝑏.
𝑑) 𝑔𝑐𝑑(𝑎, 𝑏) = 1.
2) For each of these relations on the set {1, 2, 3, 4}, decide whether it is reflexive, whether it is
symmetric, whether it is antisymmetric, and whether it is transitive.
𝑎) {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}
𝑏) {(1, 2), (2, 3), (3, 4)}
𝑐) {(1, 1), (2, 2), (3, 3), (4, 4)}
𝑑) {(1, 3), (1, 4), (2, 3), (2, 4), (3, 1), (3, 4)}
3) Determine whether the relation R on the set of all integers is reflexive, symmetric,
antisymmetric, and/or transitive, where (x, y) ∈ R if and only if
a) 𝑥 = 𝑦.
 𝑏) 𝑥 ≡ 𝑦 (𝑚𝑜𝑑 5).
𝑐 ) 𝑥 𝑎𝑛𝑑 𝑦 𝑎𝑟𝑒 𝑏𝑜𝑡ℎ 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑒 𝑜𝑟 𝑏𝑜𝑡ℎ 𝑛𝑜𝑛𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑒.
𝑑) 𝑥 = 𝑦 2 . .
4) Let 𝑅1 = {(1, 2), (2, 3), (3, 4)} and
𝑅2 = {(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (3, 4)} be relations from {1,
2, 3} to {1, 2, 3, 4}. Find
𝑎) 𝑅1 ∪ 𝑅2 .
b) 𝑅1 ∩ 𝑅2
𝑐) 𝑅1 − 𝑅2
𝑑) 𝑅2 − 𝑅1 .
5) Consider following relations on the set of real numbers:
𝑅1 = {(𝑎, 𝑏) ∈ 𝑅 2 | 𝑎 > 𝑏}, the “greater than” relation,
𝑅2 = {(𝑎, 𝑏) ∈ 𝑅 2 | 𝑎 ≥ 𝑏}, the “greater than or equal to” relation,
𝑅3 = {(𝑎, 𝑏) ∈ 𝑅 2 | 𝑎 < 𝑏}, the “less than” relation,
𝑅4 = {(𝑎, 𝑏) ∈ 𝑅 2 | 𝑎 ≤ 𝑏}, the “less than or equal to” relation,
𝑅5 = {(𝑎, 𝑏) ∈ 𝑅 2 | 𝑎 = 𝑏}, the “equal to” relation,
𝑅6 = {(𝑎, 𝑏) ∈ 𝑅 2 | 𝑎 = 𝑏}, the “unequal to” relation.
Find
𝑎) 𝑅2 ∪ 𝑅4 .
𝑏) 𝑅3 ∪ 𝑅6 .
𝑐) 𝑅3 ∩ 𝑅6 .
𝑑) 𝑅4 ∩ 𝑅6 .
𝑒) 𝑅3 − 𝑅6 .
𝑓) 𝑅6 − 𝑅3 .
𝑔) 𝑅2 ⊕ 𝑅6 .
ℎ) 𝑅3 ⊕ 𝑅5 .
𝑖) 𝑅2 ◦ 𝑅1 .
𝑗) 𝑅2 ◦ 𝑅2 .
𝑘) 𝑅3 ◦ 𝑅5 .
𝑙) 𝑅4 ◦ 𝑅1 .
6) Let R be the relation on the set {1, 2, 3, 4, 5} containing the ordered pairs
(1, 1), (1, 2), (1, 3), (2, 3), (2, 4), (3, 1), (3, 4), (3, 5), (4, 2), (4, 5), (5, 1), (5, 2), and (5, 4).
Find
𝑎) 𝑅 2
𝑏) 𝑅 3
𝑐) 𝑅 4
𝑑) 𝑅 5 .
7) Represent each of these relations on {1, 2, 3} with a matrix and diagraph.
(With the elements of this set listed in increasing order).
𝑎) {(1, 1), (1, 2), (1, 3)}
𝑏) {(1, 2), (2, 1), (2, 2), (3, 3)}
𝑐) {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)}
8) List the ordered pairs in the relations on {1, 2, 3} corresponding to these matrices (where
the rows and columns correspond to the integers listed in increasing order).1
1 0 1 0 1 0 1 1 1
a) [0 1 0] b) [0 1 0] c) [1 0 1]
1 0 1 0 1 0 1 1 1
9) Let R be the relation represented by the matrix
0 1 1
𝑀𝑅 = [1 1 0]
1 0 1
Find the matrix representing
 a)𝑀𝑅−1 .
b)𝑀𝑅′ .
c)𝑀𝑅2 .
10) Let 𝑅1 and 𝑅2 be relations on a set A represented by the
matrices
0 1 0 0 1 0
𝑀𝑅1 = [1 1 1] and 𝑀𝑅2 = [0 1 1]
1 0 0 1 1 1
Find
a) 𝑀𝑅1 ∪ 𝑀𝑅2
b) 𝑀𝑅1 ∩ 𝑀𝑅2 .
c) 𝑀𝑅2°𝑅1 .
d) 𝑀𝑅12 .
e) 𝑀𝑅1⊕ 𝑅2 .
11) Draw the directed graph that represents the following relation on set {𝑎, 𝑏, 𝑐, 𝑑}
𝑅 = {(𝑎, 𝑎), (𝑎, 𝑏), (𝑏, 𝑐), (𝑐, 𝑏), (𝑐, 𝑑), (𝑑, 𝑎), (𝑑, 𝑏)}.
12) Let 𝑅 = {(𝑎, 𝑏)| 𝑎 ≡ 𝑏(𝑚𝑜𝑑 3)} be relation on set of integers. Show that R is an
equivalence relation. Also find equivalence classes.
13) Let 𝑅 = {(𝑎, 𝑏)|𝑎 − 𝑏 𝑖𝑠 𝑎𝑛 𝑖𝑛𝑡𝑒𝑔𝑒𝑟} be relation on set of real numbers. Determine
whether R is an equivalence relation.
14) Let 𝐴 = {1,2,3,4} and 𝑅 = {(1,1), (2,2), (3,3), (4,4), (1,2), (2,1), (3,1), (1,3)}.Is R
compatible relation? If yes, find maximal compatible blocks.
15) Find maximal compatible blocks of the relation given by following matrix on set of
{1,2,3,4,5,6}.
1 2 3 5
2 1
3 1 1
[ ]
5 0 0 1
6 1 0 1 1