Post's lattice

It is named for Emil Post, who published a complete description of the lattice in 1941.

[2] A Boolean function, or logical connective, is an n-ary operation f: 2n → 2 for some n ≥ 1, where 2 denotes the two-element set {0, 1}.

We use the operations ¬, Np, (negation), ∧, Kpq, (conjunction or meet), ∨, Apq, (disjunction or join), →, Cpq, (implication), ↔, Epq, (biconditional), +, Jpq (exclusive disjunction or Boolean ring addition), ↛, Lpq,[3] (nonimplication), ?

The lattice has a natural symmetry mapping each clone C to its dual clone Cd = {fd | f ∈ C}, where fd(x1, ..., xn) = ¬f(¬x1, ..., ¬xn) is the de Morgan dual of a Boolean function f. For example, Λd = V, (T0k)d = T1k, and Md = M. The complete classification of Boolean clones given by Post helps to resolve various questions about classes of Boolean functions.

Namely, each clone C in Post's lattice which contains at least one constant function corresponds to two clones under the less restrictive definition: C, and C together with all nullary functions whose unary versions are in C. Post originally did not work with the modern definition of clones, but with the so-called iterative systems, which are sets of operations closed under substitution as well as permutation and identification of variables.

(Post also excluded the empty iterative system from the classification, hence his diagram has no least element and fails to be a lattice.)