The GATE Grind

GATE 2020 CS – Question 27

Engineering Mathematics · Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices · 1 mark · Numerical answer

Let $\mathcal{R}$ be the set of all binary relations on the set $\{1,2,3\}$. Suppose a relation is chosen from $\mathcal{R}$ at random. The probability that the chosen relation is reflexive (round off to 3 decimal places) is ______.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 0.125 to 0.125

Explanation

The relation has $2^9=512$ possible subsets of the $3\times3=9$ ordered pairs, so there are 512 binary relations on $\{1,2,3\}$.

A relation is **reflexive** iff it contains the three pairs $(1,1),(2,2),(3,3)$. The other $9-3=6$ pairs can be present or not: $2^6=64$ reflexive relations.

$$P=\frac{64}{512}=\mathbf{0.125}.$$

More Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions

All Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions →