GATE CSE 1997 | Question: 3.3

Question

In the lattice defined by the Hasse diagram given in following figure, how many complements does the element ‘$e$’ have?

• A. $2$
• B. $3$
• C. $0$
• D. $1$

Comments

@raja11sep complement of g is b,c,d,e.

---

@samarpita thanks for the correction.

---

e^-1=g,c,d

Answer 1

Answer: B

Complement of an element $a$ is $a'$ if:

• $a ∧ a' = 0$ (lowest vertex in the Hasse diagram)
• $a ∨ a' = 1$ (highest vertex in the Hasse diagram)

$g, c$ and $d$ are the complements of $e.$

Comments

thanx. i'm considering only meet condition & missed join condition.

---

To make things faster remember that compliment of an element is such an element which is not related to it and LUB of that goes to I and GLB to O.

So, the complement of e must be an element $e^{'}$ such that LUB(e,$e^{'}$)=I and GLB(e,$e^{'}$)=O, the topmost and bottom-most elements of hasse diagram respectively.

Now, candidates to be looked for the complement of e should be all those elements, to which there is no path in the hasse diagram and those are g,c,d and if you check them these 3 are complements of e.

Now why you only look for non-related elements to be the complement?

Say if I assume b to be a complement of e, from the diagram it is clear that eRb. So by lattice laws

LUB(e,b)=b(b $\not= I$ not okay!!) and GLB(e,b)=e(e=O okay!), so b can never be complement of e.

---

@Ayush so it means if a element is not related to other element in any lattice they become compliment of each other?

Answer 2

Option B

vertex 'e' have three complement like 'g','c' and 'd'.

When it will take LUB or GLB with g ,c or d get same answer.

Comments

We don't want the same answer. We want the LUB and GLB to be $I$ and $O$ respectively.

Answer 3

The complements of e can be g, c and d.

So, Option B

See this:https://gateoverflow.in/91351/gate1988-1vii

Answer 4

Another easier way of solving is:=

Find out the greatest and least element, Here it is a and f respectively

For complements, check if the LUB and GLB of any 2 elements (here e with all the other elements) coincide with the greatest and least element respectively.

Here, (e,c)(e,g)(e,d) satisfies the above condition i.e. the LUB and GLB coincide with the greatest and least elements for all the 3 pairs.

But for (e,f), The upper bounds are a,b,e, and the LUB is e. But LUB != maximal element, so it is not a complement.