Question
Suppose is a lattice represented by the following Hasse diagram:
For any , not necessarily distinct, and are join and meet of , respectively. Let be the set of all ordered triplets of the elements of . Let be the probability that an element chosen equiprobably satisfies . Then:
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 is the standard diamond lattice with bottom , top , and three pairwise incomparable intermediate elements .
Total number of triplets in :
Testing the distributive identity :
- If any of is or , or if any two elements are equal, or if the elements are comparable, distributivity holds identically.
- In , the distributive law fails only when :
For example, if :Since , distributivity fails for this triplet. - Since there are permutations of distinct elements from , distributivity fails for only a very small number of triplets (specifically 6 or 12 depending on operand order).
- Hence, the vast majority of triplets ( out of ) satisfy the distributive equality.
The probability satisfies:
Since , we have:
This matches option D.
D
Assuming 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.