Lattice – GATE CSE Engineering MathematicsPractice Questions & PYQs

A poset is a lattice if every pair of elements has a unique least upper bound (join) and a unique greatest lower bound (meet). For the given poset (X, R), we can verify that for any pair of elements, a join and a meet already exist within the set X. For example, the join of {b, d} is e, and their meet is a. Since this property holds for all pairs, the poset is already a lattice. Therefore, no additional ordered pairs need to be added.

The total number of ordered triplets $(x, y, z)$ from the set $L$ is $5^3 = 125$. The given equation, $x\vee (y \wedge z)=(x\vee y)\wedge (x\vee z)$, is the distributive property for a lattice.

The property does not hold for all triplets. For example, if we take $x=q, y=r, z=s$:

• $x \vee (y \wedge z) = q \vee (r \wedge s) = q \vee p = q$.
• $(x \vee y) \wedge (x \vee z) = (q \vee r) \wedge (q \vee s) = t \wedge t = t$.
  Since $q \neq t$, the property fails, meaning the probability $P_r$ is less than 1.

However, the property holds for some triplets. For instance, if $x=t$ (the maximum element), the equation becomes $t \vee (...) = (t \vee ...) \wedge (t \vee ...)$, which simplifies to $t = t \wedge t = t$. This is always true. There are $1 \times 5 \times 5 = 25$ such triplets. Thus, $P_r \ge \frac{25}{125} = \frac{1}{5}$. Since other combinations also satisfy the property, $P_r > \frac{1}{5}$.

Combining these, we get $\frac{1}{5} < P_r < 1$.

A partially ordered set is defined as a lattice if and only if every pair of elements $\{a, b\}$ has a unique least upper bound (join, $a \vee b$) and a unique greatest lower bound (meet, $a \wedge b$). Diagram (i) represents a diamond structure (the Boolean lattice $B_2$), where every pair of elements possesses a unique join and meet, satisfying the lattice condition. Diagram (iv) represents a chain (a totally ordered set), where for any pair, the join is defined as $\max(a, b)$ and the meet as $\min(a, b)$, which inherently makes it a lattice. Conversely, diagrams (ii) and (iii) fail to be lattices because they contain incomparable elements that lack a unique join or meet within the structure, violating the required properties.

A poset is a lattice if every pair has a unique join (LUB) and meet (GLB); here, every pair of incomparable elements $\{b, c, d\}$ has join $a$ and meet $e$, confirming it is a lattice. A lattice is distributive if and only if it does not contain the diamond sublattice $M_3$. The given structure is isomorphic to $M_3$, where $b \vee (c \wedge d) = b \vee e = b$, while $(b \vee c) \wedge (b \vee d) = a \wedge a = a$. Since $b \neq a$, the distributive law is violated. Thus, it is a lattice but not distributive, and therefore not a Boolean algebra.

A complete lattice must contain the infimum (greatest lower bound) and supremum (least upper bound) for every subset of elements. The infimum of the entire set $S$ is the intersection of all its members:
$\bigcap S = \{1, 2\} \cap \{1, 2, 3\} \cap \{1, 3, 5\} \cap \{1, 2, 4\} \cap \{1, 2, 3, 4, 5\} = \{1\}$
Since $\{1\} \notin S$, the set lacks a global bottom element $\perp$, which is a requirement for a complete lattice. Adding $\{1\}$ is the necessary step to introduce this bottom element. Among the options, identifying $\{1\}$ as the required element to complete the lattice structure makes it the necessary and sufficient choice.

In a bounded lattice, an element $x$ is a complement of $e$ if it satisfies $e \lor x = 1$ and $e \land x = 0$, where $0$ is the bottom element and $1$ is the top element. By inspecting the Hasse diagram, we first identify the unique bottom element $0$ and the unique top element $1$. We then systematically evaluate every element $x$ in the lattice by calculating its least upper bound (join) and greatest lower bound (meet) with $e$. Testing each pair, we find exactly three distinct elements that satisfy both $e \lor x = 1$ and $e \land x = 0$. Consequently, the element $e$ has 3 complements.