The GATE Grind

GATE 2015 CS – Question 42

Engineering Mathematics · Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices · 2 marks · Multiple choice

Suppose $\mathcal{L} = \{p, q, r, s, t\}$ is a lattice represented by the following Hasse diagram:

[Hasse diagram: $p$ is the bottom, $t$ is the top, and $q$, $r$, $s$ are three incomparable elements between them.]

For any $x, y \in \mathcal{L}$, not necessarily distinct, $x \vee y$ and $x \wedge y$ are join and meet of $x, y$, respectively. Let $\mathcal{L}^3 = \{(x, y, z) : x, y, z \in \mathcal{L}\}$ be the set of all ordered triplets of the elements of $\mathcal{L}$. Let $p_r$ be the probability that an element $(x, y, z) \in \mathcal{L}^3$ chosen equiprobably satisfies $x \vee (y \wedge z) = (x \vee y) \wedge (x \vee z)$. Then

Diagram for GATE 2015 CS question 42
  1. $p_r = 0$
  2. $p_r = 1$
  3. $0 < p_r \leq \frac{1}{5}$
  4. $\frac{1}{5} < p_r < 1$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $\frac{1}{5} < p_r < 1$

Explanation

There are $5^3 = 125$ triples. The distributive law fails when $x$, $y$ and $z$ are three different elements of $\{q, r, s\}$, because then $x \vee (y \wedge z) = x \vee p = x$ while $(x \vee y) \wedge (x \vee z) = t \wedge t = t$. There are $3! = 6$ such triples. In every other triple the law holds, so $p_r = \frac{119}{125} = 0.952$, which is between $\frac{1}{5}$ and 1.