Post's lattice

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

${\displaystyle \pi _{k}^{n}(x_{1},\dots ,x_{n})=x_{k},}$

and given an m-ary function f, and n-ary functions g₁, ..., g_m, we can construct another n-ary function

${\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 which can be defined by a formula using propositional variables and connectives from B form a clone [B], indeed it is the smallest clone which 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,[3] (nonimplication), ?: (the ternary conditional operator) and the constant unary functions 0 and 1. Moreover, we need the threshold functions

${\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, th₁ⁿ is the large disjunction of all the variables x_i, and th_nⁿ is the large conjunction. Of particular importance is the majority function

${\displaystyle \mathrm {maj} =\mathrm {th} _{2}^{3}=(x\land y)\lor (x\land z)\lor (y\land z).}$

We denote elements of 2ⁿ (i.e., truth-assignments) as vectors: a = (a₁, ..., a_n). The set 2ⁿ carries a natural product Boolean algebra structure. That is, ordering, meets, joins, and other operations on n-ary truth assignments are defined pointwise:

${\displaystyle (a_{1},\dots ,a_{n})\leq (b_{1},\dots ,b_{n})\iff a_{i}\leq b_{i}{\text{ for }}i=1,\dots ,n,}$

${\displaystyle (a_{1},\dots ,a_{n})\land (b_{1},\dots ,b_{n})=(a_{1}\land b_{1},\dots ,a_{n}\land b_{n}).}$

Intersection of an arbitrary number of clones is again a clone. It is convenient to denote intersection of clones by simple juxtaposition, i.e., the clone C₁ ∩ C₂ ∩ ... ∩ C_k is denoted by C₁C₂...C_k. Some special clones are introduced below:

• M is the set of monotone functions: f(a) ≤ f(b) for every a ≤ b.
• D is the set of self-dual functions: ¬f(a) = f(¬a).
• A is the set of affine functions: the functions satisfying

${\displaystyle {\begin{aligned}&f(a_{1},\dots ,a_{i-1},c,a_{i+1},\dots ,a_{n})=f(a_{1},\dots ,d,a_{i+1},\dots )\\\Rightarrow &f(b_{1},\dots ,c,b_{i+1},\dots )=f(b_{1},\dots ,d,b_{i+1},\dots )\end{aligned}}}$

for every i ≤ n, a, b ∈ 2ⁿ, and c, d ∈ 2. Equivalently, the functions expressible as f(x₁, ..., x_n) = a₀ + a₁x₁ + ... + a_nx_n for some a₀, a.

• 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 f(a) = f(b) whenever a_i = b_i.
• Λ is the set of conjunctive functions: f(a ∧ b) = f(a) ∧ f(b). The clone Λ consists of the conjunctions ${\displaystyle f(x_{1},\dots ,x_{n})=\bigwedge _{i\in I}x_{i}}$ for all subsets I of {1, ..., n} (including the empty conjunction, i.e., the constant 1), and the constant 0.
• V is the set of disjunctive functions: f(a ∨ b) = f(a) ∨ f(b). Equivalently, V consists of the disjunctions ${\displaystyle f(x_{1},\dots ,x_{n})=\bigvee _{i\in I}x_{i}}$ for all subsets I of {1, ..., n} (including the empty disjunction 0), and the constant 1.
• For any k ≥ 1, T₀^k is the set of functions f such that

${\displaystyle \mathbf {a} ^{1}\land \cdots \land \mathbf {a} ^{k}=\mathbf {0} \ \Rightarrow \ f(\mathbf {a} ^{1})\land \cdots \land f(\mathbf {a} ^{k})=0.}$

Moreover, ${\displaystyle \mathrm {T} _{0}^{\infty }=\bigcap _{k=1}^{\infty }\mathrm {T} _{0}^{k}}$ is the set of functions bounded above by a variable: there exists i = 1, ..., n such that f(a) ≤ a_i for all a.

As a special case, P₀ = T₀¹ is the set of 0-preserving functions: f(0) = 0. Furthermore, ⊤ can be considered T₀⁰ when one takes the empty meet into account.

• For any k ≥ 1, T₁^k is the set of functions f such that

${\displaystyle \mathbf {a} ^{1}\lor \cdots \lor \mathbf {a} ^{k}=\mathbf {1} \ \Rightarrow \ f(\mathbf {a} ^{1})\lor \cdots \lor f(\mathbf {a} ^{k})=1,}$

and ${\displaystyle \mathrm {T} _{1}^{\infty }=\bigcap _{k=1}^{\infty }\mathrm {T} _{1}^{k}}$ is the set of functions bounded below by a variable: there exists i = 1, ..., n such that f(a) ≥ a_i for all a.

The special case P₁ = T₁¹ consists of the 1-preserving functions: f(1) = 1. Furthermore, ⊤ can be considered T₁⁰ when one takes the empty join into account.

• The largest clone of all functions is denoted ⊤, the smallest clone (which contains only projections) is denoted ⊥, and P = P₀P₁ is the clone of constant-preserving functions.

The set of all clones is a closure system, hence it forms a complete lattice. The lattice is countably infinite, and all its members are finitely generated. All the clones are listed in the table below.

Hasse diagram of Post's lattice

Central part of the lattice

The eight infinite families have actually also members with k = 1, but these appear separately in the table: T₀¹ = P₀, T₁¹ = P₁, PT₀¹ = PT₁¹ = P, MT₀¹ = MP₀, MT₁¹ = MP₁, MPT₀¹ = MPT₁¹ = MP.

The lattice has a natural symmetry mapping each clone C to its dual clone C^d = {f^d | f ∈ C}, where f^d(x₁, ..., x_n) = ¬f(¬x₁, ..., ¬x_n) is the de Morgan dual of a Boolean function f. For example, Λ^d = V, (T₀^k)^d = T₁^k, and M^d = M.

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 ⊤ (often called Post's classes) are M, D, A, P₀, P₁, 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[4] used the description of Post's lattice to show that B-SAT is NP-complete if the function ↛ can be generated from B (i.e., [B] ⊇ T₀^∞), and in all the other cases B-SAT is polynomial-time decidable.