GATE CS 2015 Set 1 Q34 — Partial Orders and Lattices

To find the probability $p_r$, we analyze the number of triplets $(x, y, z) imes L^3$ that satisfy the distributive identity:

Since $L$ is a finite lattice with $5$ elements, it must have a unique least element (bottom) denoted by $0$ and a unique greatest element (top) denoted by $1$. Let us count the satisfying triplets:

1. Case 1: $x = 0$
   The identity becomes $0 \vee (y \wedge z) = (0 \vee y) \wedge (0 \vee z) \implies y \wedge z = y \wedge z$, which is always true. Since $y$ and $z$ can be any of the $5$ elements, this gives $1 \times 5 \times 5 = 25$ valid triplets.
2. Case 2: $x = 1$
   The identity becomes $1 \vee (y \wedge z) = (1 \vee y) \wedge (1 \vee z) \implies 1 = 1 \wedge 1$, which is always true. This gives another $1 \times 5 \times 5 = 25$ valid triplets.

Since $0 \neq 1$, these two cases are completely disjoint. Thus, there are at least $25 + 25 = 50$ satisfying triplets out of a total of $5^3 = 125$ possible triplets.

This gives the lower bound for the probability:

Since the Hasse diagram represents a non-distributive lattice (either $N_5$ or $M_3$), the distributive law does not hold universally, meaning $p_r < 1$. Therefore, we have: