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.
Basic concepts 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}. Particular Boolean functions are the projections
π k n ( x 1 , … , x n ) = x k , {\displaystyle \pi _{k}^{n}(x_{1},\dots ,x_{n})=x_{k},}
and given an m-ary function f, and n-ary functions g1, ..., gm, we can construct another n-ary function
h ( x 1 , … , x n ) = f ( g 1 ( x 1 , … , x n ) , … , g m ( x 1 , … , x n ) ) , {\displaystyle h(x_{1},\dots ,x_{n})=f(g_{1}(x_{1},\dots ,x_{n}),\dots ,g_{m}(x_{1},\dots ,x_{n})),}
called their composition. A set of functions closed under composition, and containing all projections, is called a clone. Let B be a set of connectives. The functions that can be defined by a formula using propositional variables and connectives from B form a clone [B], indeed it is the smallest clone that includes B. We call [B] the clone generated by B, and say that B is the basis of [B]. For example, [¬, ∧] are all Boolean functions, and [0, 1, ∧, ∨] are the monotone functions. 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, (nonimplication), ?: (the ternary conditional operator) and the constant unary functions 0 and 1. Moreover, we need the threshold functions
t h k n ( x 1 , … , x n ) = { 1 if | { i ∣ x i = 1 } | ≥ k , 0 otherwise. {\displaystyle \mathrm {th} _{k}^{n}(x_{1},\dots ,x_{n})={\begin{cases}1&{\text{if }}{\bigl |}\{i\mid x_{i}=1\}{\bigr |}\geq k,\\0&{\text{otherwise.}}\end{cases}}}
For example, thn1 is the large disjunction of all the variables xi, and thnn is the large conjunction. Of particular importance is the majority function
m a j = t h 2 3 = ( x ∧ y ) ∨ ( x ∧ z ) ∨ ( y ∧ z ) . {\displaystyle \mathrm {maj} =\mathrm {th} _{2}^{3}=(x\land y)\lor (x\land z)\lor (y\land z).}
We denote elements of 2n (i.e., truth-assignments) as vectors: a = (a1, ..., an). The set 2n carries a natural product Boolean algebra structure. That is, ordering, meets, joins, and other operations on n-ary truth assignments are defined pointwise:
… excerpt ends here. Continue reading the full article.
