Quick Reference

An algebraic structure, such as a Boolean algebra, in which there are two dyadic operations that are both commutative and associative and satisfy the absorption and idempotent laws. The two dyadic operators, denoted by ∧ and ∨, are called the meet and the join respectively.

An alternative but equivalent view of a lattice is as a set L on which there is a partial ordering defined. Further, every pair of elements has both a greatest lower bound and a least upper bound. The least upper bound of {x,y} can be denoted by xy and is referred to as the join of x and y. The greatest lower bound can be denoted by xy and is called the meet of x and y. It can then be shown that these operations satisfy the properties mentioned in the earlier definition, since a partial ordering ≤ can be introduced by defining ab iff ab = a

ab iff ab = a

Lattices in the form of Boolean algebras play a very important role in much of the theory and mathematical ideas underlying computer science. Lattices are also basic to much of the approximation theory underlying the ideas of denotational semantics.

Subjects: Computing.

Reference entries