# 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 1 Explanation:
 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.25 B 0.125 C 0.465 D 0.565
GATE CSE 2020   Discrete Mathematics
Question 2 Explanation:
 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 3 Explanation:
 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 4 Explanation:
 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 5 Explanation:
 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 6 Explanation:
 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 7 Explanation:
 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 8 Explanation:
 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 9 Explanation:
 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
Question 10 Explanation:
There are 10 questions to complete.

### 3 thoughts on “Relation”

1. In the question 23, please update the correct option to B