Suppose \(L = \left\{ p, q, r, s, t\right\}\) is a lattice represented by the…

2015

Suppose \(L = \left\{ p, q, r, s, t\right\}\) is a lattice represented by the following Hasse diagram:

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

  1. A.

    \(p_r = 0\)

  2. B.

    \(p_r = 1\)

  3. C.

    \(0 < p_r ≤ \frac{1}{5}\)

  4. D.

    \(\frac{1}{5} < p_r < 1\)

Attempted by 111 students.

Show answer & explanation

Correct answer: D

Concept

A lattice is distributive when x \vee (y \wedge z) = (x \vee y) \wedge (x \vee z) holds for every choice of x, y, z. This is a property of the lattice, not an automatic law: the diamond lattice M_3 (a bottom, a top, and three pairwise-incomparable middle elements) is the textbook example of a non-distributive lattice. Two facts always come for free, though: if x is the bottom element then x \vee w = w for all w, and if x is the top element then x \vee w = \text{top} for all w; in both cases the identity collapses to a trivial truth.

Here (L, \le) is exactly M_3: bottom p, top t, and three incomparable atoms q, r, s. So the identity is true for most triples but must fail for some. We count how many of the 5^3 = 125 ordered triples (x, y, z) satisfy it.

Application — count by fixing x

Split the 125 triples by the value of x, because the behaviour of x \vee (\cdot) depends only on where x sits in the lattice. For each x there are 5 \times 5 = 25 ordered pairs (y, z).

  1. x = p (bottom): p \vee w = w, so the left side is y \wedge z and the right side is (p \vee y) \wedge (p \vee z) = y \wedge z. Both sides are equal — the identity holds for all 25 pairs.

  2. x = t (top): t \vee w = t, so the left side is t and the right side is t \wedge t = t. Equal again — the identity holds for all 25 pairs.

  3. Each atom x \in \{q, r, s\}: for an atom, x \vee w = x when w \in \{p, x\}, and x \vee w = t otherwise (when w is one of the two other atoms or t). Checking all 25 pairs, the only failures occur when y and z are the two distinct atoms different from x: then the left side is x \vee (y \wedge z) = x \vee p = x, but the right side is t \wedge t = t. That is exactly 2 ordered pairs, so the identity holds for 25 - 2 = 23 pairs for each atom.

Tally

Value of x

Pairs (y, z) that satisfy

p (bottom)

25

t (top)

25

q (atom)

23

r (atom)

23

s (atom)

23

Total

119

Satisfying triples = 25 + 25 + 3 \times 23 = 119. Since |L^3| = 5^3 = 125, we get p_r = \dfrac{119}{125} = 0.952.

Cross-check

The value 0.952 lies strictly between \tfrac{1}{5} = 0.2 and 1, so \tfrac{1}{5} < p_r < 1. As a sanity check that p_r \neq 1 (the lattice really is non-distributive), take x = q, \ y = r, \ z = s: then q \vee (r \wedge s) = q \vee p = q, while (q \vee r) \wedge (q \vee s) = t \wedge t = t, and q \neq t — a genuine failure, consistent with the 6 failing triples found above.

Explore the full course: Gate Guidance By Sanchit Sir