In a lattice defined by the Hasse diagram given in figure, how many…

1997

In a lattice defined by the Hasse diagram given in figure, how many complements does the element 'e' have?

GATE-CS-1997-Q3

Answer: B. 3To find the complements of e quickly, we look for any element x that satisfies two conditions with e: Meet (Bottom): They must only intersect at the very…

  1. A.

    2

  2. B.

    3

  3. C.

    0

  4. D.

    1

Attempted by 1 students.

Show answer & explanation

Correct answer: B

To find the complements of e quickly, we look for any element x that satisfies two conditions with e:

  1. Meet (Bottom): They must only intersect at the very bottom (f).

  2. Join (Top): Their paths upward must meet for the first time at the very top (a).

Here is the direct analysis for element e:

  • Elements b, a, and f fail immediately because b and a are directly above e (violating the bottom condition), and f is directly below e (violating the top condition).

This leaves us to check the entire right and middle branches: g, c, and d.

  • Checking g: * Going down: e and g only meet at f.

    • Going up: The paths from e (via b) and g meet for the first time at a.

    • Result: g is a complement.

  • Checking c: * Going down: e and c only meet at f.

    • Going up: The paths from e (via b) and c meet for the first time at a.

    • Result: c is a complement.

  • Checking d: * Going down: e and d only meet at f.

    • Going up: The paths from e (via b) and d (via c) meet for the first time at a.

    • Result: d is a complement.

Since g, c, and d all satisfy both conditions, e has exactly 3 complements.

Explore the full course: Iocl Engineers Officers Grade A Paper 2

Loading lesson…