Discrete Mathematics

6

Lattices

A lattice is a special kind of an ordered set with two binary operations. Lattice structures are used in computing and mathematical applications.

6.1 LATTICE

Definition 6.1

A lattice is a partially ordered set (L, ≤) in which every subset {a, b} consisting of two elements has a least upper bound and a greatest lower bound.

We denote LUB({a, b}) by a ∨ b and call it join or sum of a and b. Similarly, we denote GLB ({a, b}) by a ∧ b and call it meet or product of a and b.

Other symbols used are

 

LUB: ⊕, +, ∪,

GLB: *, ·, ∩.

Thus Lattice is a mathematical structure with two binary operations, join and meet.

A totally ordered set is obviously a lattice but not all partially ordered sets are lattices.

EXAMPLE 6.1

Let A be any set and ...