First described by Emil Post in "The Two-Valued Iterative Systems Of Mathematical Logic",
Post's Lattice is the lattice of clones (sets of functions closed under composition) of
Boolean functions, partially ordered by inclusion. The lattice is surprisingly simple,
being only countably infinite due to the presence of eight infinite families.
The description of the lattice has proven to be an invaluable asset when studying anything
involving Boolean function composition or construction. Most notably, it has found
applications in digital logic, circuit design, and complexity theory. One of its most
immediate uses is that it enables one to efficiently determine which Boolean functions
can be constructed using a given set of logical connectives.
The diagram only displays the clones that both include the Min Clone and are included within the Max Clone. To adjust these parameters, first select the desired clone, then click on either the Min Clone or Max Clone button. The complete diagram can be restored by clicking the Reset Button. Additionally, use the Labels Switch to toggle label visibility according to your preference.
\( B \): The clone of all Boolean functions.
\( P_0 \): The clone of all falsity-preserving functions \( \forall f \in P_0: f(0, 0, \ldots, 0) = 0 \).
\( P_1 \): The clone of all truth-preserving functions \( \forall f \in P_1: f(1, 1, \ldots, 1) = 1 \).
\( P \): The clone of all constant-preserving functions \( P = P_0 \cap P_1 \).
\( F_{0}^{k} \): The clones of all \( k \)-order falsity-preserving functions \( \forall f \in F_{0}^{k}: \bigwedge(V_1, V_2, \ldots, V_k) = \) \( (0, 0, \ldots, 0) \Rightarrow \) \( \bigwedge(f(V_1), f(V_2), \ldots, f(V_k)) = 0 \). Note that \( P_0 = F_{0}^{1} \).
\( F_{0}^{\infty} \): The clone of all variable falsity-preserving functions \( \forall f \in F_{0}^{\infty}: \exists i \in \{1, 2, \ldots, n\}: f(V) \leq v_i \). Equivalently, \( F_{0}^{\infty} = \bigcap_{k=1}^{\infty} F_{0}^{k} \).
\( PF_{0}^{k} \): The clones of all constant-preserving \( k \)-order falsity-preserving functions \( PF_{0}^{k} = F_{0}^{k} \cap P \). Note that \( P = PF_{0}^{1} \).
\( PF_{0}^{\infty} \): The clone of all constant-preserving variable falsity-preserving functions \( PF_{0}^{\infty} = F_{0}^{\infty} \cap P \). Equivalently, \( PF_{0}^{\infty} = \) \( \bigcap_{k=1}^{\infty} PF_{0}^{k} \).
\( F_{1}^{k} \): The clones of all \( k \)-order truth-preserving functions \( \forall f \in F_{1}^{k}: \bigvee(V_1, V_2, \ldots, V_k) = \) \( (1, 1, \ldots, 1) \Rightarrow \) \( \bigvee(f(V_1), f(V_2), \ldots, f(V_k)) = 1 \). Note that \( P_1 = F_{1}^{1} \).
\( F_{1}^{\infty} \): The clone of all variable truth-preserving functions \( \forall f \in F_{1}^{\infty}: \exists i \in \{1, 2, \ldots, n\}: f(V) \geq v_i \). Equivalently, \( F_{1}^{\infty} = \bigcap_{k=1}^{\infty} F_{1}^{k} \).
\( PF_{1}^{k} \): The clones of all constant-preserving \( k \)-order truth-preserving functions \( PF_{1}^{k} = F_{1}^{k} \cap P \). Note that \( P = PF_{1}^{1} \).
\( PF_{1}^{\infty} \): The clone of all constant-preserving variable truth-preserving functions \( PF_{1}^{\infty} = F_{1}^{\infty} \cap P \). Equivalently, \( PF_{1}^{\infty} = \) \( \bigcap_{k=1}^{\infty} PF_{1}^{k} \).
\( MC \): The clone of all monotone functions \( \forall f \in MC: V_1 \leq V_2 \Rightarrow f(V_1) \leq f(V_2) \) with the constants \( MC = M \cup \{0, 1\} \). In other words, it is the clone of all functions for which changing an input variable from 0 to 1 will never change the output from 1 to 0. For example, if \( f(0, 1, 1, 0) = 1 \), \( f(1, 1, 1, 0) = 1 \).
\( M_0 \): The clone of all monotone functions with \( 0 \) ( \( M0 = M \cup \{0\} \) ). Equivalently, it is the clone of all falsity-preserving monotone functions ( \( M0 = MC \cap P_0 \) ).
\( M_1 \): The clone of all monotone functions with \( 1 \) ( \( M1 = M \cup \{1\} \) ). Equivalently, it is the clone of all truth-preserving monotone functions ( \( M1 = MC \cap P_1 \) ).
\( M \): The clone of all monotone functions without the constants. Equivalently, it is the clone of all constant-preserving monotone functions ( \( M = MC \cap P \) ).
\( MF_{0}^{k} \): The clones of all monotone \( k \)-order falsity-preserving functions with \( 0 \) \( (MF_{0}^{k} = F_{0}^{k} \cap M0 = MPF_{0}^{k} \cup \{0\}) \). Note that \( M0 = MF_{0}^{1} \).
\( MF_{0}^{\infty} \): The clone of all monotone variable falsity-preserving functions with \( 0 \) \( (MF_{0}^{\infty} = F_{0}^{\infty} \cap M0 = \) \( MPF_{0}^{\infty} \cup \{0\}) \). Equivalently, \( MF_{0}^{\infty} = \bigcap_{k=1}^{\infty} MF_{0}^{k} \).
\( MPF_{0}^{k} \): The clones of all monotone \( k \)-order falsity-preserving functions without the constants. Equivalently, they are the clones of all constant-preserving monotone \( k \)-order falsity-preserving functions \( MPF_{0}^{k} = MF_{0}^{k} \cap P \). Note that \( M = MPF_{0}^{1} \).
\( MPF_{0}^{\infty} \): The clone of all monotone variable falsity-preserving functions without the constants. Equivalently, \( MPF_{0}^{\infty} = \bigcap_{k=1}^{\infty} MPF_{0}^{k} \).
\( MF_{1}^{k} \): The clones of all monotone \( k \)-order truth-preserving functions with \( 1 \) \( (MF_{1}^{k} = F_{1}^{k} \cap M1 = MPF_{1}^{k} \cup \{1\}) \). Note that \( M1 = MF_{1}^{1} \).
\( MF_{1}^{\infty} \): The clone of all monotone variable truth-preserving functions with \( 1 \) \( (MF_{1}^{\infty} = F_{1}^{\infty} \cap M1 = \) \( MPF_{1}^{\infty} \cup \{1\}) \). Equivalently, \( MF_{1}^{\infty} = \bigcap_{k=1}^{\infty} MF_{1}^{k} \).
\( MPF_{1}^{k} \): The clones of all monotone \( k \)-order truth-preserving functions without the constants. Equivalently, they are the clones of all constant-preserving monotone \( k \)-order truth-preserving functions \( MPF_{1}^{k} = MF_{1}^{k} \cap P \). Note that \( M = MPF_{1}^{1} \).
\( MPF_{1}^{\infty} \): The clone of all monotone variable truth-preserving functions without the constants. Equivalently, \( MPF_{1}^{\infty} = \bigcap_{k=1}^{\infty} MPF_{1}^{k} \).
\( D \): The clone of all self-dual functions \( \forall f \in D: f(V) = \neg f(\neg V) \).
\( DP \): The clone of all constant-preserving self-dual functions \( DP = D \cap P \).
\( DM \): The clone of all monotone self-dual functions \( DM = D \cap M \).
\( L \): The clone of all linear functions, also known as affine; counting functions \( \forall f \in L: \exists (v_0, V): f(x_1, x_2, \ldots, x_n) = \) \( v_0 \oplus (v_1 \land x_1) \oplus (v_2 \land x_2) \) \( \oplus \ldots \oplus (v_n \land x_n) \).
\( LP_0 \): The clone of all ⊕ functions \( \forall f \in LP_0: \exists V: f(x_1, x_2, \ldots, x_n) = 0 \) \( \oplus (v_1 \land x_1) \oplus (v_2 \land x_2) \oplus \ldots \oplus (v_n \land x_n) \). Equivalently, it is the clone of all falsity-preserving linear functions \( LP_0 = L \cap P_0 \).
\( LP_1 \): The clone of all ↔ functions \( \forall f \in LP_1: \exists V: f(x_1, x_2, \ldots, x_n) = \) \( 1 \leftrightarrow (v_1 \land x_1) \leftrightarrow (v_2 \land x_2) \) \( \leftrightarrow \ldots \leftrightarrow (v_n \land x_n) \). Equivalently, it is the clone of all truth-preserving linear functions \( LP_1 = L \cap P_1 \).
\( LD \): The clone of all linear functions with an odd number of non-dummy variables. Equivalently, it is the clone of all self-dual linear functions \( LD = L \cap D \).
\( LP \): The clone of all ⊕/↔ functions with an odd number of non-dummy variables. Equivalently, it is the clone of all constant-preserving linear functions \( LP = L \cap P \).
\( AC \): The clone of all \( \wedge \) functions with the constants \( (AC = A \cup C) \).
\( A_0 \): The clone of all \( \wedge \) functions with \( 0 \) \( (A_O = A \cup \{0\}) \).
\( A_1 \): The clone of all \( \wedge \) functions with \( 1 \) \( (A_1 = A \cup \{1\}) \).
\( A \): The clone of all \( \wedge \) functions without the constants.
\( OC \): The clone of all \( \vee \) functions with the constants \( (OC = O \cup C) \).
\( O_0 \): The clone of all \( \vee \) functions with \( 0 \) \( (O_0 = O \cup \{0\}) \).
\( O_1 \): The clone of all \( \vee \) functions with \( 1 \) \( (O_1 = O \cup \{1\}) \).
\( O \): The clone of all \( \vee \) functions without the constants.
\( UC \): The clone of all unary functions (functions with only one non-dummy variable) with the constants \( (UC = U \cup C) \).
\( U \): The clone of all unary functions without constants.
\( IC \): The clone of all identity functions with the constants \( (IC = I \cup C) \).
\( I_0 \): The clone of all identity functions with \( 0 \) \( (I_0 = I \cup \{0\}) \).
\( I_1 \): The clone of all identity functions with \( 1 \) \( (I_1 = I \cup \{1\}) \).
\( I \): The clone of all identity functions, also known as projection functions \( \forall f \in I: \exists i \in \{1, 2, \ldots, n\}: \) \( f(x_1, x_2, \ldots, x_n) = x_i \).
\( B \):
\( P_0 \):
\( P_1 \):
\( P \):
\( F_{0}^{k} \):
\( F_{0}^{\infty} \):
\( PF_{0}^{k} \):
\( PF_{0}^{\infty} \):
\( F_{1}^{k} \):
\( F_{1}^{\infty} \):
\( PF_{1}^{k} \):
\( PF_{1}^{\infty} \):
\( MC \):
\( M_0 \):
\( M_1 \):
\( M \):
\( MF_{0}^{k} \):
\( MF_{0}^{\infty} \):
\( MPF_{0}^{k} \):
\( MPF_{0}^{\infty} \):
\( MF_{1}^{k} \):
\( MF_{1}^{\infty} \):
\( MPF_{1}^{k} \):
\( MPF_{1}^{\infty} \):
\( D \):
\( DP \):
\( DM \):
\( L \):
\( LP_0 \):
\( LP_1 \):
\( LD \):
\( LP \):
\( AC \):
\( A_0 \):
\( A_1 \):
\( A \):
\( OC \):
\( O_0 \):
\( O_1 \):
\( O \):
\( UC \):
\( U \):
\( IC \):
\( I_0 \):
\( I_1 \):
\( I \):