Relation

Question 1
A relation R is said to be circular if aRb and bRc together imply cRa.
Which of the following options is/are correct?
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.
GATE CSE 2021 SET-1   Discrete Mathematics
Question 2
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 ______.
A
0.250
B
0.125
C
0.465
D
0.565
GATE CSE 2020   Discrete Mathematics
Question 3
Let G be an arbitrary group. Consider the following relations on G:

R1: \forall a,b \in G, aR_1b if and only if \exists g \in G such that a=g^{-1}bg
R2: \forall a,b \in G, aR_2b if and only if a=b^{-1}

Which of the above is/are equivalence relation/relations?
A
R1 and R2
B
R1 only
C
R2 only
D
Neither R1 nor R2
GATE CSE 2019   Discrete Mathematics
Question 4
The time complexity of computing the transitive closure of binary relation on a set of n elements is known to be
A
O(n)
B
O(n * \log (n))
C
O\left(n^{\frac{3}{2}}\right)
D
O\left(n^{3}\right)
ISRO CSE 2018   Discrete Mathematics
Question 5
The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be
A
O(n \log n)
B
O\left(n^{3 / 2}\right)
C
O\left(n^{3}\right)
D
O(n)
ISRO CSE 2017   Discrete Mathematics
Question 6
A binary relation R on \mathbb{N}\times \mathbb{N} is defined as follows: (a,b)R(c,d) if a \leq c or b \leq d. Consider the following propositions:
P: R is reflexive
Q: R is transitive
Which one of the following statements is TRUE?
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
GATE CSE 2016 SET-2   Discrete Mathematics
Question 7
Let R be a relation on the set of ordered pairs of positive integers such that ((p,q),(r,s)) \in R if and only if p-s=q-r. Which one of the following is true about R?
A
Both reflexive and symmetric
B
Reflexive but not symmetric
C
Not reflexive but symmetric
D
Neither reflexive nor symmetric
GATE CSE 2015 SET-3   Discrete Mathematics
Question 8
Consider two relations R1(A,B) with the tuples (1,5), (3,7) and R2(A,C) = (1,7), (4,9). Assume that R(A,B,C) is the full natural outer join of R1 and R2. Consider the following tuples of the form (A,B,C): a = (1,5,null), b = (1,null,7), c = (3, null, 9), d = (4,7,null), e = (1,5,7), f = (3,7,null), g = (4,null,9). Which one of the following statements is correct?
A
R contains a, b, e, f, g but not c, d.
B
R contains all of a, b, c, d, e, f, g.
C
R contains e, f, g but not a, b.
D
R contains e but not f, g.
GATE CSE 2015 SET-2   Discrete Mathematics
Question 9
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?
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
GATE CSE 2015 SET-2   Discrete Mathematics
Question 10
Consider the binary relation R = {(x,y), (x,z), (z,x), (z,y)} on the set {x,y,z}. Which one of the following is TRUE?
A
R is symmetric but NOT antisymmetric
B
R is NOT symmetric but antisymmetric
C
R is both symmetric and antisymmetric
D
R is neither symmetric nor antisymmetric
GATE CSE 2009   Discrete Mathematics
There are 10 questions to complete.

3 thoughts on “Relation”

Leave a Comment