Mathematical Foundation of Computer Science

DHARM

166 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

6.7 Prove that every chain is a distributive lattice.

6.8 Prove De Morgan’s laws holds in a distributive, complemented lattice s.t.

GLB(x, y)′ = LUB(x′, y′) and LUB(x, y)′ = GLB(x′, y′)

6.9 Show that in a distributive, complemented lattice

x ≤ y ⇔ GLB(x, y′) = 0 ⇔ LUB(x′, y) = 1 ⇔ y′ ≤ x′

6.10 Let X = {0, 1} and the lattices (X, ≤) and (X^2 , ≤) are shown in Fig. 6.15 show that diagram of lattice

(Xn, ≤) is an n-cube.

(1, 1)

(1, 0) (0, 1)

(0, 0)

1

0

Fig. 6.15

6.11 Show that there are only five distinct Hasse diagrams possible for the partial ordered sets

having three elements.