A lattice is a mathematical structure composed of a set
*S* and a relation *r*. If *x*, *y*, and *z*
are elements of *S*, and *r* is a relation over those elements,
then (*S*, *r*) is a lattice if and only if the following
conditions are met:

*r*is reflexive, so for every element*x*in*S*,*xrx*.*r*is antisymmetric, so if*xry*and*yrx*, then*x*=*y*.*r*is transitive, so if*xry*and*yrz*, then*xrz*.- Every pair of elements in
*S*has a lower bound. In other words, there is a*z*in*S*such that*zrx*and*zry*for every pair (*x*,*y*). - Every pair of elements in
*S*has an upper bound. In other words, there is a*z*in*S*such that*xrz*and*yrz*for every pair (*x*,*y*).

Does ({ 1, 2, 3, 4, 5 }, <=) form a lattice?
How about ({*true*, *false*}, **and**)?

You can also see this document in its native format, in Postscript, in PDF, or in ASCII text.

Send email to cs153@csif.cs.ucdavis.edu.

Department of Computer Science

University of California at Davis

Davis, CA 95616-8562