Gate Discrete Maths

Question

Consider the lattice D30

a)Draw the Hasse Diagram of D30.

b) Is D30 complemented?

c) Is D30 distributive?

Answer 1

(a)

(b)In a Complemented Lattice each element has at least one complemented.

(1) 1∨30 =30                  1∧30 = 1         $\Rightarrow$ 1' =30 and 30'=1

(2) 2∨15 = 30                 2∧15 = 1         $\Rightarrow$  2'=15 and 15'=2

(3)3∨10 = 30                  3∧10 = 1         $\Rightarrow$ 3'=10 and 10'=3

(4)5∨6 = 30                    5∧6 = 1            $\Rightarrow$ 5'=6 and 6'=5

Here Every element has one element hence, it is a complemented Lattice.

(c)In a Distributive Lattice complement of an element if exists is unique i.e. each element has at most one element.

Here in D30, Every element has a unique complement. Hence, it is a Distributive Lattice.  

Comments

very good explanation..

---

“Here in D30 Every element has unique  complement.Hence, it is Distributive Lattice.”  This logic is not correct.

Correct logic is : If lattice has at least one element having more than 1 complement then it is not distributive lattice. converse is not true.

To check for D30 lattice we have to check that no Kite and no pentagon sub lattice exist.

Answer 2

D₃₀={1,2,3,5,6,10,15,30}

because D₃₀ is square free so it is boolean algebra and every  boolean algebra is distributed and complemented also

Comments

what do you mean by square free ?

---

@ LavTheRawkstar 

Square free --> None of the factors is the perfect square.