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.^[1]

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.

A Boolean function, or logical connective, is an n-ary operationf: 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, 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 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 ringaddition), ↛, Lpq,^[2] (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{ถ้า }}{\bigl |}\{i\mid x_{i}=1\}{\bigr |}\geq k,\\0&{\text{มิเช่นนั้น}}\end{cases}}}$

For example, thⁿ is the large disjunction of all the variables x, and thⁿ 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). The set 2ⁿ carries a natural productBoolean 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{ สำหรับ }}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 is denoted by CC...C. Some special clones are introduced below:

• M = [∧, ∨, 0, 1] is the set of monotone functions: f(a) ≤ f(b) for every a ≤ b.
• D = [maj, ¬] is the set of self-dual functions: ¬f(a) = f(¬a).
• A = [↔, 0] 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) = a + ax + ... + ax for some a, a.

• U = [¬, 0] is the set of essentially unary functions, i.e., functions that depend on at most one input variable: there exists an i = 1, ..., n such that f(a) = f(b) whenever a = b.
• Λ = [∧, 0, 1] 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 = [∨, 0, 1] 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 = [th^k+2, ↛] 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.}$

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.

• 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 for all a.
• For any k ≥ 1, T^k = [th^k+2, →] คือเซตของฟังก์ชันfเช่นนั้น

${\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,}$

กรณีพิเศษP = T¹ = [∧, →] ประกอบด้วย ฟังก์ชัน ที่รักษาค่า 1 : f ( 1 ) = 1ยิ่งไปกว่านั้น ⊤ สามารถพิจารณาได้ว่าเป็นT⁰ เมื่อพิจารณาการเชื่อมต่อที่ว่างเปล่าด้วย

• ยิ่งไปกว่านั้น= [→] คือเซตของฟังก์ชันที่มีขอบเขตล่างโดยตัวแปร: มีอยู่i = 1, ..., nที่f ( a ) ≥ a สำหรับทุกa${\displaystyle \mathrm {T} _{1}^{\infty }=\bigcap _{k=1}^{\infty }\mathrm {T} _{1}^{k}}$
• โคลนที่ใหญ่ที่สุดของฟังก์ชันทั้งหมดจะถูกแสดงด้วยสัญลักษณ์ ⊤ = [∨, ¬]

นอกจากนี้ โคลนที่เล็กที่สุด (ซึ่งประกอบด้วยเฉพาะการฉายภาพ) จะถูกแทนด้วย ⊥ = [] และP = P P = [ x  ? y  : z ] คือโคลนของฟังก์ชัน ที่รักษาค่าคงที่

เซตของโคลนทั้งหมดเป็นระบบปิดดังนั้นจึงก่อให้เกิดแลตทิซที่สมบูรณ์ แลตทิซ นี้มี จำนวนอนันต์ที่นับได้ และสมาชิกทั้งหมดของ แลตทิซถูกสร้างขึ้นโดยจำนวนจำกัด โคลนทั้งหมดแสดงอยู่ในตารางด้านล่าง

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) = ¬f(¬x, ..., ¬x) 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 if and only if it is not included in any 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^[3] 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.

If one only considers clones that contain the constant functions ${\displaystyle 0}$ and ${\displaystyle 1}$ (i.e., UP and UP), the classification is simpler. There are only 7 such clones: UM, Λ, V, U, A, M, and ⊤. This can be derived from the full classification or via a simpler proof taking less than a page.^[4]

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 that 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

${\displaystyle h(x_{1},\dots ,x_{n+m-1})=f(x_{1},\dots ,x_{n-1},g(x_{n},\dots ,x_{n+m-1})),}$

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 that are not clones. (Post also excluded the empty iterative system from the classification, hence his diagram has no least element and fails to be a lattice.) 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 that 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.

A modern exposition of Post's lattice can be found in David Lau (2006): Function algebras on finite sets: Basic course on many-valued logic and clone theory.^[5]