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 the O’Reilly learning platform.

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

Start your free trial