Question

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

For any x,y∈Lx, y \in L, not necessarily distinct, x∨yx \lor y and x∧yx \land y are join and meet of x,yx, y, respectively. Let L3={(x,y,z):x,y,z∈L}L^3 = \{(x, y, z) : x, y, z \in L\} be the set of all ordered triplets of the elements of LL. Let prp_r be the probability that an element (x,y,z)∈L3(x, y, z) \in L^3 chosen equiprobably satisfies x∨(y∧z)=(x∨y)∧(x∨z)x \lor (y \land z) = (x \lor y) \land (x \lor z). Then:

Hasse diagram of 5-element diamond lattice L with bottom element p, top element t, and incomparable elements q, r, s
Hasse diagram of lattice L
Choose one option
Official answer and solution
Official answer
D
From
Official GATE 2015 answer key

Solution

Count the number of triplets in the non-distributive diamond lattice M3 that satisfy the distributive law.

The lattice L={p,q,r,s,t}L = \{p, q, r, s, t\} is the standard diamond lattice M3M_3 with bottom pp, top tt, and three pairwise incomparable intermediate elements q,r,sq, r, s.

Total number of triplets in L3L^3:

∣L3∣=53=125.|L^3| = 5^3 = 125.

Testing the distributive identity x∨(y∧z)=(x∨y)∧(x∨z)x \lor (y \land z) = (x \lor y) \land (x \lor z):

  • If any of x,y,zx, y, z is pp or tt, or if any two elements are equal, or if the elements are comparable, distributivity holds identically.
  • In M3M_3, the distributive law fails only when {x,y,z}={q,r,s}\{x, y, z\} = \{q, r, s\}:
    For example, if x=q,y=r,z=sx = q, y = r, z = s:
    x∨(y∧z)=q∨(r∧s)=q∨p=qx \lor (y \land z) = q \lor (r \land s) = q \lor p = q
    (x∨y)∧(x∨z)=(q∨r)∧(q∨s)=t∧t=t.(x \lor y) \land (x \lor z) = (q \lor r) \land (q \lor s) = t \land t = t.
    Since q≠tq \ne t, distributivity fails for this triplet.
  • Since there are 3!=63! = 6 permutations of distinct elements from {q,r,s}\{q, r, s\}, distributivity fails for only a very small number of triplets (specifically 6 or 12 depending on operand order).
  • Hence, the vast majority of triplets (>110> 110 out of 125125) satisfy the distributive equality.

The probability prp_r satisfies:

pr=125−6125=119125=0.952.p_r = \frac{125 - 6}{125} = \frac{119}{125} = 0.952.

Since 15=0.20<0.952<1\frac{1}{5} = 0.20 < 0.952 < 1, we have:

15<pr<1.\frac{1}{5} < p_r < 1.

This matches option D.

Final answer

D

Common trap

Assuming pr=0p_r = 0 because M3 is classified as a non-distributive lattice, failing to realize non-distributivity means not universally true for all triplets, not false for all triplets.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2015 Computer Science and Information Technology (CS) Session 1
Question
44 of 65, printed as CS Q.34
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.