Post's lattice
In logic and universal algebra, Post's lattice denotes the lattice of all clones on a two-element set, ordered by inclusion. It is named for Emil Post, who published a complete description of the lattice in 1941. The relative simplicity of Post's lattice is in stark contrast to the lattice of clones on a three-element set, which has the cardinality of the continuum, and a complicated inner structure. A modern exposition of Post's result can be found in Lau.
Basic concepts
A Boolean function, or logical connective, is an n-ary operation for some, where 2 denotes the two-element set. Particular Boolean functions are the projectionsand given an m-ary function f, and n-ary functions g1,..., gm, we can construct another n-ary function
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 which can be defined by a formula using propositional variables and connectives from B form a clone , indeed it is the smallest clone which includes B. We call the clone generated by B, and say that B is the basis of . For example, are all Boolean functions, and are the monotone functions.
We use the operations ¬, Np,, ∧, Kpq,, ∨, Apq,, →, Cpq,, ↔, Epq,, +, Jpq, ↛, Lpq,, ?: and the constant unary functions 0 and 1. Moreover, we need the threshold functions
For example, th1n is the large disjunction of all the variables xi, and thnn is the large conjunction. Of particular importance is the majority function
We denote elements of 2n as vectors:. 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:
Naming of clones
of an arbitrary number of clones is again a clone. It is convenient to denote intersection of clones by simple, i.e., the clone is denoted by C1C2...Ck. Some special clones are introduced below:- M is the set of monotone functions: for every.
- D is the set of self-dual functions:.
- A is the set of affine functions: the functions satisfying
- U is the set of essentially unary functions, i.e., functions which depend on at most one input variable: there exists an i = 1,..., n such that whenever.
- Λ is the set of conjunctive functions:. The clone Λ consists of the conjunctions for all subsets I of , and the constant 0.
- V is the set of disjunctive functions:. Equivalently, V consists of the disjunctions for all subsets I of , and the constant 1.
- For any k ≥ 1, T0k is the set of functions f such that
- For any k ≥ 1, T1k is the set of functions f such that
- The largest clone of all functions is denoted ⊤, the smallest clone is denoted ⊥, and is the clone of constant-preserving functions.
Description of the lattice
of Post's lattice
| clone | one of its bases |
| ⊤ | ∨, ¬ |
| P0 | ∨, + |
| P1 | ∧, → |
| P | x ? y : z |
| T0k, k ≥ 2 | thkk+1, ↛ |
| T0∞ | ↛ |
| PT0k, k ≥ 2 | thkk+1, x ∧ |
| PT0∞ | x ∧ |
| T1k, k ≥ 2 | th2k+1, → |
| T1∞ | → |
| PT1k, k ≥ 2 | th2k+1, x ∨ |
| PT1∞ | x ∨ |
| M | ∧, ∨, 0, 1 |
| MP0 | ∧, ∨, 0 |
| MP1 | ∧, ∨, 1 |
| MP | ∧, ∨ |
| MT0k, k ≥ 2 | thkk+1, 0 |
| MT0∞ | x ∧, 0 |
| MPT0k, k ≥ 2 | thkk+1 for k ≥ 3, maj, x ∧ for k = 2 |
| MPT0∞ | x ∧ |
| MT1k, k ≥ 2 | th2k+1, 1 |
| MT1∞ | x ∨, 1 |
| MPT1k, k ≥ 2 | th2k+1 for k ≥ 3, maj, x ∨ for k = 2 |
| MPT1∞ | x ∨ |
| Λ | ∧, 0, 1 |
| ΛP0 | ∧, 0 |
| ΛP1 | ∧, 1 |
| ΛP | ∧ |
| V | ∨, 0, 1 |
| VP0 | ∨, 0 |
| VP1 | ∨, 1 |
| VP | ∨ |
| D | maj, ¬ |
| DP | maj, x + y + z |
| DM | maj |
| A | ↔, 0 |
| AD | ¬, x + y + z |
| AP0 | + |
| AP1 | ↔ |
| AP | x + y + z |
| U | ¬, 0 |
| UD | ¬ |
| UM | 0, 1 |
| UP0 | 0 |
| UP1 | 1 |
| ⊥ |
The eight infinite families have actually also members with k = 1, but these appear separately in the table:,,,,,.
The lattice has a natural symmetry mapping each clone C to its dual clone, where is the de Morgan dual of a Boolean function f. For example,,, and.
Applications
The complete classification of Boolean clones given by Post helps to resolve various questions about classes of Boolean functions. For example:- An inspection of the lattice shows that the maximal clones different from ⊤ are M, D, A, P0, P1, and every proper subclone of ⊤ is contained in one of them. As a set B of connectives is functionally complete if and only if it generates ⊤, we obtain the following characterization: B is functionally complete iff it is not included in one of the five Post's classes.
- The satisfiability problem for Boolean formulas is NP-complete by Cook's theorem. Consider a restricted version of the problem: for a fixed finite set B of connectives, let B-SAT be the algorithmic problem of checking whether a given B-formula is satisfiable. Lewis used the description of Post's lattice to show that B-SAT is NP-complete if the function ↛ can be generated from B, and in all the other cases B-SAT is polynomial-time decidable.
Variants
as well as permutation and identification of variables. The main difference is that iterative systems do not necessarily contain all projections. Every clone is an iterative system, and there are 20 non-empty iterative systems which are not clones. As another alternative, some authors work with the notion of a closed class, which is an iterative system closed under introduction of dummy variables. There are four closed classes which are not clones: the empty set, the set of constant 0 functions, the set of constant 1 functions, and the set of all constant functions.
Composition alone does not allow to generate a nullary function from the corresponding unary constant function, this is the technical reason why nullary functions are excluded from clones in Post's classification. If we lift the restriction, we get more clones. 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.