Properties of Lattice with Proofs

In this class, We discuss Properties of Lattice with Proofs.

The reader should have prior knowledge of lattice. Click here.

Properties of lattice:

V symbol used for the least upper bound

Λ symbol used for the greatest lower bound

Idempotent law:

a V a = a

a Λ a = a

Commutative law:

a V b = b V a

a Λ b = b Λ a

Associative law:

a V(b V c) = (a V b)V c

a Λ(b Λ c) = (a Λ b) Λ c

Proof:

x = a V(b V c)

y = (a V b)V c

LUB(a, (b V c)) = z

a <= z and b <= z

LUB(b, c)

b <= (b V c) and c <= (b V c)

b <= z and c <= z

a <= z and b <= z and c <= z

(a <= z and b <= z) and c <= z

(a V b)V c <= z

y <= z

Absorption law:

a V (a Λ b) = a

a Λ ( a V b) = a

Proof:

aV(aΛb) = a

a Λ b = GLB(a, b)

a Λ b <= a and a Λ b <= b

Also, a <= a

From above, a <= a and a Λ b <= a

a V (a Λ b) <= a