Post's lattice

EN Texto en inglés Aún no hay artículo en tu idioma: extracto en inglés.

In logic and universal algebra, Post's lattice denotes the lattice of all clones on a two-element set {0, 1}, ordered by inclusion. It is named for Emil Post, who published a complete description of the lattice in 1941. The lattice is shown in the image on the right. The relative simplicity of Post's lattice is in stark contrast to the lattice of clones on a three-element (or larger) set, which has the cardinality of the continuum, and a complicated inner structure. As a special case, the lattice implies Post's functional completeness theorem: any set of Boolean operations is functionally complete if and only if it is not a subset of either the monotone, affine, self-dual, truth-preserving, or false-preserving functions. Post's lattice consists of 9 named clones, two countably infinite families of clones indexed by the positive integers, and all finite intersections of these.