GATE CS 2015 Set 1 — Question 42

The given condition $x \lor (y \land z) = (x \lor y) \land (x \lor z)$ is one of the distributive laws for lattices. A lattice is called distributive if it satisfies both distributive laws for all its elements.First, let's analyze the given Hasse diagram for the lattice $L = \{p, q, r, s, t\}$:From the diagram, we can identify the order relations and thus the join ($\lor$) and meet ($\land$) operations:

• $p$ is the bottom element (least element).
• $t$ is the top element (greatest element).
• $q$ and $s$ are incomparable elements, both covering $p$.
• $r$ covers both $q$ and $s$. This means $q \lor s = r$ and $q \land s = p$.
• $t$ covers $r$.

This lattice structure is isomorphic to a Boolean lattice $B_2$ (if we consider the elements $p, q, s, r$) extended with an additional top element $t$. A Boolean lattice is always distributive.To confirm if the lattice $L$ is distributive, we can check if it contains any sublattice isomorphic to $M_3$ (diamond lattice with three incomparable elements between 0 and 1) or $N_5$ (pentagon lattice). The given lattice does not contain $M_3$ or $N_5$ as sublattices. The elements $q$ and $s$ are the only incomparable elements, and there are only two of them, not three as required for $M_3$. The structure does not match $N_5$ either.Therefore, the lattice $L$ is a distributive lattice.In a distributive lattice, the distributive law $x \lor (y \land z) = (x \lor y) \land (x \lor z)$ holds true for all elements $x, y, z \in L$.The question asks for $p_r$, the probability that an element $(x, y, z) \in L^3$ chosen equiprobably satisfies this identity. Since the identity holds for all possible triplets $(x, y, z)$ in a distributive lattice, every one of the $5^3 = 125$ possible triplets will satisfy the condition.Thus, the number of favorable outcomes is $125$, and the total number of outcomes is $125$. The probability $p_r$ is:
$p_r = \frac{\text{Number of favorable outcomes}}{\text{Total number of outcomes}} = \frac{125}{125} = 1$.The final answer is $\boxed{B}$