Post’s Functional Completeness: 1 Perfect Guide to Post’s Classes

Before simply filling out a table with pluses and minuses, let’s understand the ultimate goal of this mathematical process. Why do we need Post’s classes? In computer engineering, our goal is to build complex processors containing billions of transistors. But can we build an entire computer if the factory only supplies us with one or two types of microchips (for example, only AND and NOT gates)?

The brilliant American mathematician Emil Post proved a fundamental theorem: for a specific set of logic gates to be able to construct any existing digital circuit in the Universe (a property known as Post’s functional completeness), this set of functions must not completely belong to any of the five fundamental closed classes.

When computer scientists discuss Boolean functional completeness, they are referring to this exact concept of logic gates universality. In practical hardware terms, if a specific set of logical operators can be combined to express absolutely every possible truth table, it is deemed mathematically universal. This is exactly why hardware manufacturers can build entire complex processors using exclusively NAND or NOR gates, a foundational principle of digital electronics detailed in resources like Wikipedia’s overview of Functional Completeness.

For our analysis, let’s take the value vector of our function $f(x, y, z)$, which we obtained from its truth table. The vector corresponds to the sets of input variables from binary 000 (the first element) to 111 (the last element):

$$V = (1, 0, 0, 1, 0, 0, 0, 1)$$

✍️ Detailed Algorithm for Evaluating Function $f$

Stage 1: Evaluating $T_0$ (Preserving Zero)

• Mathematical Essence: For a function to belong to class $T_0$, it must be “indifferent” to the absence of a signal. If you apply 0 to all inputs (no current), the output must also be 0.
• Logic of Analysis:
  We take the input set $x=0, y=0, z=0$. In binary code, this is set No. 0.
  We look at the first element of our value vector $V$.
  $$f(0,0,0) = 1$$
• Conclusion: The function received all zeros at the input, but somehow generated a 1 at the output. It does not preserve zero.
  Since $1 \neq 0$, we conclude: $f \notin T_0$. We place a minus (–) in the table.

Stage 2: Evaluating $T_1$ (Preserving One)

• Mathematical Essence: This is the mirror image of the previous rule. If you apply the maximum signal (1s) to all inputs, the circuit must not “extinguish” it; it must output a 1.
• Logic of Analysis:
  We take the input set $x=1, y=1, z=1$. This is the last set in the truth table (set No. 7).
  We look at the last (eighth) element of vector $V$.
  $$f(1,1,1) = 1$$
• Conclusion: The function preserved the maximum signal.
  Since the result is 1, we conclude: $f \in T_1$. We place a plus (+) in the table.

Stage 3: Evaluating $S$ (Self-Dual Class)

• Mathematical Essence: A self-dual function acts as an “inverting mirror”. If you invert (flip $0 \leftrightarrow 1$) absolutely all input variables, the value of the function itself must also strictly invert.
  Definition: $f(x, y, z) = \neg f(\neg x, \neg y, \neg z)$.
• Logic of Analysis (Finding a Counterexample):
  To prove that a function is not self-dual, it is enough to find at least one pair of opposite input sets where the rule breaks.
  1. Let’s take set $A(0,0,0)$. The function’s value is: $f(0,0,0) = 1$.
  2. Let’s take its exact opposite, set $B(1,1,1)$ (we inverted all inputs).
  3. The function’s value for set $B$ is: $f(1,1,1) = 1$.
• Conclusion: For self-duality, the output values should have been different (if the first was 1, the second should have become 0). But here, $1 = 1$. The circuit failed to react to a total input inversion. It is not self-dual.
  We conclude: $f \notin S$. We place a minus (–) in the table.

Real-World Application: Understanding how a self-dual function behaves is critical for advanced cryptography and error-checking circuits. If a logical function perfectly mirrors its inverted inputs, it possesses a strict structural symmetry. To ensure a cipher is robust and unpredictable, security engineers often actively avoid using a purely self-dual function in their S-box designs.

Stage 4: Evaluating $M$ (Monotonic Class)

• Mathematical Essence: Monotonicity means the function “has no right to fall”. If you gradually increase the values at the inputs (switching 0s to 1s), the output value can either stay the same or increase. But it can never drop from 1 to 0!
  Set $A \preceq B$ (A precedes B), if every bit in $A$ is less than or equal to the corresponding bit in $B$.
• Logic of Analysis (The Hypercube Method):
  Imagine a 3D cube where you move from the bottom vertex $(0,0,0)$ upward along the edges.
  1. Let’s take the bottom vertex: $A(0,0,0)$. Value: $f(0,0,0) = 1$.
  2. Let’s take one step “up” (increasing variable $z$): $B(0,0,1)$.
  3. Let’s check the precedence condition: $0 \le 0$, $0 \le 0$, $0 \le 1$. Therefore, $A \preceq B$ (the input set genuinely increased).
  4. Let’s check the function’s value: $f(0,0,1) = 0$.
• Conclusion: The inputs increased, but the function collapsed (dropped from 1 to 0). This is a direct violation of the law of monotonicity.
  Since $f(A) > f(B)$, we conclude: $f \notin M$. We place a minus (–) in the table.

Real-World Application: In digital logic, a monotonic Boolean function represents a highly predictable, one-way transition system. Once an input flips from a low state (0) to a high state (1), the output is mathematically forbidden from reverting to 0. You can explore the rigid mathematical properties of these directional relationships at authoritative mathematical databases like Wolfram MathWorld. Proving that a digital circuit does not act strictly as a monotonic Boolean function is an absolutely necessary step in fulfilling Emil Post’s requirements for hardware universality.

Stage 5: Evaluating $L$ (Linear Class)

• Mathematical Essence: A function is linear if its Zhegalkin polynomial consists exclusively of independent variables ($x, y, z$) connected by the XOR operator ($\oplus$). There must be absolutely no logical multiplications (conjunctions)!
• Logic of Analysis:
  In our previous module, we found the polynomial for this function (hypothetically):
  $$f(x, y, z) = 1 \oplus z \oplus y \oplus yz \oplus xz \oplus xyz$$
  We can clearly see the presence of “glued” (multiplied) variables: $yz$, $xz$, $xyz$.
• Conclusion: The presence of even a single product of variables instantly makes the polynomial non-linear.
  We conclude: $f \notin L$. We place a minus (–) in the table.

📊 Final Verification of Post’s Functional Completeness

To demonstrate the true power of Post’s functional completeness theorem, let’s add a hypothetical function $f_2$ (for example, a standard conjunction $x \land y$) to our function $f_1$, and check if we can build a universal computer using only these two microchips.

Let’s compile the matrix for Post’s classes:

Applying Post’s Theorem

The Rule: A system of Boolean functions achieves Post’s functional completeness if and only if it does not completely belong to any of the five classes. Visually, this means that every vertical column in the table must contain at least one minus “–”.

Let’s analyze our matrix column by column:

• Column $T_0$: There is a minus (in $f_1$). The class is covered. ✅
• Column $T_1$: There are no minuses! Both functions have a plus. ❌
• Column $S$: There is a minus. The class is covered. ✅
• Column $M$: There is a minus. The class is covered. ✅
• Column $L$: There is a minus. The class is covered. ✅

The Final Verdict

Because there is no minus in the $T_1$ column (both functions preserve one), this set is not functionally complete. Using only microchips $f_1$ and $f_2$, you will never be able to build a circuit that outputs a 0 when fed exclusively with 1s. To achieve true universal computing potential, you would have to add another function to this set (like a NOT inverter) to successfully “close” the $T_1$ column with a minus.