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 ...

Get Discrete Mathematics now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.