Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 6 Marks

Year: May 2016

Distributed Lattice:

A distributive lattice is a lattice in which join ∨ and meet ∧ distribute over each other, in that for all x, y, z in the lattice, the distributivity laws are satisfied:

$$x ∨ (y ∧ z)=(x ∨ y)∧(x ∨ z) \\ x ∧ (y ∨ z)=(x ∧ y)∨(x ∧ z)$$

In a bounded distributive lattice, if a complement exists, it’s unique

Proof. Let L be a bounded distributive lattice.

Let x and y be two complments of an element a in L.

$\therefore a \vee x=I, a \wedge x=0, a\vee y=I,a \wedge y=0 \\ Now \ \ \ x=x\vee 0=x \vee (a \wedge y)=(x \vee a)\wedge(x \vee y)=(a \vee x)\wedge(x \vee y)=I \wedge(x \vee y)=x \vee y \\ and \ \ \ y=y \vee 0=y \vee (a \wedge x)=(y \vee a)\wedge(y \vee x)=(a \vee y)\wedge(x \vee y)=I \wedge(x \vee y)=x \vee y \\ \therefore x=y (each=x \vee y) \\ \therefore \text{The theorem holds.}$