Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 57 ยท Logic Gates

Functional Completeness and Post's Theorem

Learn which sets of gates can build every Boolean function. Apply Post's five classes (0-preserving, 1-preserving, monotone, self-dual, affine) with a Python checker.

In Universal Gates and Gate Counts you saw that NAND alone, or NOR alone, can build every other gate. That raises a bigger question: which sets of gates can build every Boolean function, and which cannot? A set that can is called functionally complete (some books say functionally universal).

The question is practical. A library of cells in a chip factory, a set of instructions in a tiny processor, and a set of operators in a query language are all "gate sets". You want to know whether yours is enough, and whether you could drop a gate without losing power. There is a clean test, due to the logician Emil Post, and you can run it in a few lines of Python.

What "complete" means

A set of functions S is functionally complete if every Boolean function of any number of variables can be written using only members of S (reusing inputs and outputs freely, and allowing the constant inputs 0 and 1 only if they are in S).

Some quick facts you already know:

  • {AND, OR, NOT} is complete: that is exactly what sum-of-products form uses (see Canonical and Standard Forms).
  • {AND, NOT} is complete, because a OR b = NOT(NOT a AND NOT b) by De Morgan's laws. So is {OR, NOT}.
  • and are each complete on their own.
  • {AND, OR} is not complete. You can never produce NOT from them. The reason is subtle, and it is where Post's theorem comes in.

Why a set can fail

Look at what AND and OR have in common. Feed them all zeros and you get zero. Feed them all ones and you get one. Any circuit built from only AND and OR inherits both habits: all-zeros in gives zero out, all-ones in gives one out. But NOT breaks both habits. So NOT can never come out of an AND/OR network.

That is the whole idea: find a property that is closed under composition (gates that have it can only build circuits that have it) and that some function lacks. If every gate in your set has the property, the set is incomplete.

Post's five classes

Emil Post proved in 1941 that there are exactly five such properties that matter. A set is functionally complete if and only if it contains at least one function that is outside each of these five classes.

Class Name A function f belongs when... Examples inside Examples outside
T0 0-preserving f(0, 0, ..., 0) = 0 AND, OR, XOR NAND, NOR, NOT, XNOR
T1 1-preserving f(1, 1, ..., 1) = 1 AND, OR, XNOR NAND, NOR, NOT, XOR
M monotone raising an input never lowers the output AND, OR NOT, XOR, NAND
S self-dual f(NOT x1, ..., NOT xn) = NOT f(x1, ..., xn) NOT, majority AND, OR, NAND
L affine (linear) f is an XOR of inputs, optionally XOR 1 NOT, XOR, XNOR AND, OR, NAND

Read the table as a checklist. To be complete, your set needs:

  1. one member that fails 0-preservation,
  2. one that fails 1-preservation,
  3. one that is not monotone,
  4. one that is not self-dual,
  5. one that is not affine.

One function can tick several boxes at once, which is why a single NAND is enough: it is outside all five classes.

Post's classes are why the constants matter. A set that contains the constant 1 as an input (as in programmable logic where you can tie a pin high) has more power than the same gates without it. The test below lets you include constants in the set.

A checker in Python

The code represents each function by its truth table, then tests each of the five properties. The affine test tries every combination of coefficients, which is fine for the tiny functions we use here.

Python Post's theorem as a checker

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first table shows which classes each gate lies in. The second block applies Post's test to several sets. Notice the interesting ones: {XOR, AND} is incomplete (both are 0-preserving), but adding the constant ONE makes it complete; that combination is the algebra of Zhegalkin polynomials, where every function is an XOR of AND-terms. And {NOT, MAJ} is incomplete: both are self-dual, so no network of them can ever compute AND.

Proving completeness the constructive way

Post's test tells you yes or no. To prove a set is complete in a paper, you usually build one known-complete set from it:

  1. Show you can build NOT (or a constant plus a way to negate).
  2. Show you can build AND or OR.
  3. Conclude, because {AND, NOT} or {OR, NOT} is already complete.

This is exactly how the NAND construction works: NOT a = NAND(a, a), then AND = NOT(NAND).

Python Building NOT and AND from implication and zero

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why it matters for hardware

  • Standard-cell libraries always contain a complete set, usually NAND, NOR and inverters, plus larger cells for speed.
  • Reversible and quantum logic study sets such as that are complete only with constant inputs, which is exactly the situation Post's classes capture.
  • Query languages and rule engines are checked for expressive power the same way: can they say NOT? can they say OR?
  • Minimal designs ask the reverse question: is any gate in my set redundant? Removing it keeps completeness only if some other member covers each class.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why is {AND, OR} not functionally complete?

    AND and OR both output 0 for all-zero inputs and 1 for all-one inputs, and any network of them keeps both properties. NOT violates both.
  2. 2. How many Post classes must a complete set escape (have a member outside of)?

    Post's theorem names five classes: 0-preserving, 1-preserving, monotone, self-dual and affine. The set needs a member outside each one.
  3. 3. Which single gate lies outside all five Post classes?

    NAND is not 0-preserving, not 1-preserving, not monotone, not self-dual and not affine, which is why it alone is complete.
  4. 4. Why is {XOR, AND} incomplete, while {XOR, AND, constant 1} is complete?

    XOR and AND both map all-zero inputs to 0. The constant 1 fails 0-preservation, and with it NOT = XOR(a, 1) becomes available.

Summary

  • A set of gates is functionally complete when it can build every Boolean function.
  • Post's theorem: a set is complete exactly when it has a member outside each of five classes: 0-preserving, 1-preserving, monotone, self-dual and affine.
  • {AND, OR}, {XOR, AND} and {NOT, MAJ} fail; , , {AND, NOT} and {OR, NOT} succeed.
  • Constants change the answer, as the {XOR, AND, 1} example shows.
  • To prove completeness by hand, build NOT and AND (or OR) from the set.

Next: Two-Level Logic Implementations, the eight AND-OR style forms.