Previous Year Questions: Relation | Engineering Mathematics for Computer Science Engineering - Computer Science Engineering (CSE) PDF Download

Q1: A relation R is said to be circular if aRb and bRc together imply cRa. Which of the following options is/are correct?  (2021 SET-1)
(a) If a relation S is reflexive and symmetric, then S is an equivalence relation.
(b) If a relation S is circular and symmetric, then S is an equivalence relation.
(c) If a relation S is reflexive and circular, then S is an equivalence relation.
(d) If a relation S is transitive and circular, then S is an equivalence relation.
Ans: (c)
Sol: Let S be an empty relation
Empty relation is all symmetric, transitive and circular (as all these three are conditional)
But it is not reflexive.
equivalence relation : reflexive, symmetric and transitive
S is both circular and symmetric but not reflexive, hence B is false
S is both transitive and circular but not reflexive, hence D is false
option A clearly does not follow the definition of equivalence relation,
so only option left is C
and C indeed is the correct answer as proved below
Let S be both reflexive and circular,
case 1: x has only diagonal elements ( aSa exists for all a)
Then S is all reflexive, symmetric, transitive and circular  (hence equivalence )
case 2:  let for some 3 different elements a, b, c  aSb  exists  but bSc does not exist
Both aSa, bSb also exist   (it is given reflexive)
(aSa and aSb) → bSa (from circular property),
so, aSb → bSa, hence it is symmetric
And transitive as well (because i assumed if aSb exists then no bSc exists for any three different elements a, b, c)
Hence this case will also be equivalence
case 3: let for some 3 different elements a,b,c both  aSb, bSc exists
aSa, bSb, cSc (exists from reflexive property)
bSb and bSc → cSb   (from circular property)
(Hence it is symmetric)aSb and bSc → cSa   (from circular property)
cSa → aSc   (from symmetric property)    (already proved symmetric 2 steps above)
so, we can conclude,
aSb and bSc → aSc   (hence it is transitive as well)
as we just proved it as both symmetric and transitive, it is definitely equivalence relation
In all three cases we proved that if S is both reflexive and circular then it an is equivalence relation.
C is correct ans.

Q2: Let R be the set of all binary relations on the set {1, 2, 3}. Suppose a relation is chosen from R at random. The probability that the chosen relation is reflexive (round off to 3 decimal places) is ______.  (2020)
(a) 0.250
(b) 0.125
(c) 0.465
(d) 0.565
Ans: (b)
Sol: No. of relations on set A with n elements  = 2^n∗n
There are n reflexive pairs, and n²−n non-reflexive pairs
For a relation which is reflexive, all reflexive pairs must present and are no-restrictions on the non-reflexive pairs.
So, there are two possibilities for non-reflexive pairs- present or absent.
∴ No. of reflexive relations
Probability that a chosen relation is reflexive

Q3: Let G be an arbitrary group. Consider the following relations on G:
R1: ∀a, b ∈ G, aR₁b if and only if ∃g ∈ G such that a = g⁻¹bg
R2: ∀a, b ∈ G, aR₂b  if and only if a = b⁻¹ 
Which of the above is/are equivalence relation/relations?  (2019)
(a) R1 and R2
(b) R1 only
(c) R2 only
(d) Neither R1 nor R2
Ans: (b)
Sol: R₁ : ∀a, b ∈ G, aR₁b iff ∃g ∈ G such that a = g⁻¹bg
let g and h are inverse for each other.
Reflexive:
aR₁a
a = g⁻¹ag
ga = gg⁻¹ag //Left multiplication by g
gag⁻¹ = agg⁻¹ //Right multiplication by g⁻¹
gag⁻¹ = a
a = gag⁻¹
a = h⁻¹ah  (∃h ∈ G)
we have aR₁a. So the relation is reflexive.
Alternative :- in the group, there should exist identity element, So we can take it as some g.
Symmetric:
let (a, b) exist, then
a = g⁻¹bg
gag⁻¹ = b
h⁻¹ah = b  (∃h ∈ G)
∴ (b, a) should be in the relation.
Hence the relation is symmetric.
Transitive:
If (a, b) and (b, c) present, then
a = x⁻¹bx and b = y⁻¹cy
What is the inverse of x⁻¹y⁻¹?
x⁻¹y⁻¹ . _________ = Identity.
to cancel the term y⁻¹, we must multiply with it's inverse.
to cancel the term x⁻¹, we must multiply with it's inverse.
So, inverse of x⁻¹y⁻¹ is y.x
∴ a = p⁻¹cp, where p is y.x
∴ (a, c) should be in the relation.
Hence the relation is transitive.
R₁ is equivalence relation.
R₂: ∀a, b ∈ G, aR₂b iff a = b⁻¹
Reflexive:
for including a pair of (a, a), we need to a = a⁻¹ .
For an arbitrary group this may not be true. So the relation is not reflexive.
R₂ is not equivalence relation.
Correct Answer (B).

Q4: The time complexity of computing the transitive closure of binary relation on a set of n elements is known to be  (2018)
(a) O(n)
(b) O(n ∗ log(n))
(c) O(n^3/2)
(d) O(n³)
Ans: (d)
Sol: The matrix of the transitive closure of a relation on a set of n elementscan be found using n2(2n−1)(n−1)+(n−1)n2 bit operations, which gives the time complexity of O(n4).
But using  Warshall's Algorithm: Transitive Closure we can do it in O(n3) bit operations.
Hence D is the correct answer.

Q5: The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be  (2017)
(a) O(n log n)
(b) O(n^3/2)
(c) $O\left(n3\right)$O(n³)
(d) $O\left(n\right)$O(n)
Ans: (c)
Sol: 

If above is a binary relation in it's matrix representation.
Then the following is the O(V³) Warshall's Algorithm to find the Transitive closure of the underlying graph or binary relation.

Q6: A binary relation R on  is defined as follows: (a, b) R(c, d) if a ≤ c or b ≤ d. Consider the following propositions:
P: R is reflexive
Q: R is transitive
Which one of the following statements is TRUE?  (2016 SET-2)
(a) Both P and Q are true
(b) P is true and Q is false.
(c) P is false and Q is true
(d) Both P and Q are false
Ans: (b)
Sol: (B) Reflexive, but not transitive.
it is "a ≤ c OR b ≤ d",
NOT
"a ≤ c and b ≤ d",
(2, 5) R(6, 3), (6, 3) R(1, 4), but (2, 5)

Q7: Let R be a relation on the set of ordered pairs of positive integers such that ((p, q), (r, s)) ∈ R if and only if p − s = q − r. Which one of the following is true about R?  (2015 SET-3)
(a) Both reflexive and symmetric
(b) Reflexive but not symmetric
(c) Not reflexive but symmetric
(d) Neither reflexive nor symmetric
Ans: (c)
Sol: The key trick here is to realize that the relation is of the form :
{ordered pair, ordered pair} and not simply ordered pair.
Ok, so for reflexive
∀_a,b if((a, b), (a, b)) ∈ R→ reflexive
((a, b), (a, b)) ∈ R ↔ (a − b = b − a) (not possible for any postive integers b and a)
But that is a contradiction hence it is not reflexive.
Now, for symmetric
((a, b), (c, d)) ∈ R → ((c, d), (a, b)) ∈ R
((a, b), (c, d)) ∈ R → (a−d = b−c)
((c, d), (a, b)) ∈ R
∵ (c − b = d − a) ↔ (d − a = c − b) ↔ (−(a − d) = −(b − c)) ↔ (a − d = b − c)
So, it is symmetric.
Hence, C is the correct option.

Q8: Let R be the relation on the set of positive integers such that aRb if and only if a and b are distinct and have a common divisor other than 1. Which one of the following statements about R is true?  (2015 SET-2)
(a) R is symmetric and reflexive but not transitive
(b) R is reflexive but not symmetric and not transitive
(c) R is transitive but not reflexive and not symmetric
(d) R is symmetric but not reflexive and not transitive
Ans: (d)
Sol: Take (3, 6) and (6, 2) elements of R. For transitivity (3, 2) must be element of R, but 3 and 2 don't have a common divisor and hence not in R.
For any positive integer n, (n, n) is not element of R as only distinct m and n are allowed for (m, n) in R. So, not reflexive also.