Functional Completeness and the Building Blocks of Logic

By Sergey Nosov

May 16, 2025

Let us explore a foundational concept in logic and computer science that underpins everything from digital circuit design to software architecture: functional completeness in Boolean logic.

Whether you're building cloud-native services or experimenting with low-level code, this idea shows how the logic we use to reason about computation can be constructed from just a handful of simple operators — or in some cases, just one.

🔍 Part 1: What Is Functional Completeness?

Functional completeness refers to the ability of a set of logical operations to express any Boolean function.

Think of it like Lego bricks: If a certain collection of bricks lets you build any structure, it's "complete." In Boolean logic, completeness means you can model any truth table using the functions you have.

Common examples:

• {AND, OR, NOT} – Complete set
• {NAND} alone – Also complete (called the Sheffer stroke)
• {NOR} alone – Also complete (called the Peirce arrow)

🧱 Part 2: Minimal Building Blocks

So, what does it take for a set of operators to be functionally complete?

Emil Post, in the 1920s, formalized this through a structure now known as Post's lattice. He showed that a set of Boolean functions is functionally complete if and only if it doesn’t fall entirely into any of these five “incomplete” classes:

1. T₀: Functions that preserve 0

If all zeros go in, zero comes out. Example: AND(0,0) = 0. Limitation: You can’t create constant 1 or invert values.

2. T₁: Functions that preserve 1

If all ones go in, one comes out. Example: OR(1,1) = 1. Limitation: Can’t express constant 0.

3. M: Monotonic functions

A function is monotonic if flipping an input from 0→1 never causes the output to go from 1→0. AND and OR are monotonic; NOT and NAND are not.

4. S: Self-dual functions

A function is self-dual if its output complements the output of the function when all inputs are flipped. In other words, for every input x, the function satisfies: f(x̄) = ¬f(x), where x̄ is the bitwise complement of x.

Example: If f(0,1) = 1, then f(1,0) must be 0. Self-dual functions are balanced — they don’t overly favor 0s or 1s in their output.

5. L: Linear functions

These can be expressed using only XOR and constants. Example: f(x, y) = x ⊕ y ⊕ 1. Limitation: They can’t express basic AND/OR logic.

To be functionally complete, a set must escape all five of these classes.

🔧 Part 3: NAND and NOR — One Function to Rule Them All

Here’s the beautiful part: NAND and NOR alone are functionally complete.

Why is NAND special?

• It’s not monotonic (violates M)
• It doesn’t preserve 0 or 1 (violates T₀ and T₁)
• It’s not self-dual
• It’s not linear

This single function, NAND(x, y) = NOT(AND(x, y)), can express everything:

• NOT x = NAND(x, x)
• AND(x, y) = NOT(NAND(x, y))
• OR(x, y) = NAND(NOT x, NOT y)

It’s a great exercise to verify these with truth tables!

🛠️ Part 4: Why This Matters to Developers

Why should we care about this in our daily work?

• It’s the foundation of all digital hardware: processors, memory circuits, etc.
• It’s essential for compiler theory and optimization of logical conditions.
• It’s crucial in formal verification and program synthesis.

More importantly, it reminds us how complex systems can be built from just a few simple, reliable primitives.

🎓 Part 5: Connection to “From Nand to Tetris”

You may have heard of the educational project "From Nand to Tetris" by Noam Nisan and Shimon Schocken.

It takes learners through the entire journey of building a computer from a single NAND gate all the way to running a game of Tetris.

Why it's brilliant:

• It demonstrates abstraction in action — from gates to operating systems.
• It reinforces how functional completeness enables the creation of any computable system.

Understanding this concept is the intellectual starting point of that journey.

🧭 Closing Thoughts

Functional completeness is more than a theoretical curiosity — it’s a lens into the structure of logic, the power of minimalism, and the hidden elegance behind our hardware and software systems.

Whether you’re working in React, C#, Rust, or at the hardware level, knowing what makes a logic system complete empowers you to better understand, optimize, and build.

Thank you.

📚 References

1. Post, Emil L. “Introduction to a General Theory of Elementary Propositions.” American Journal of Mathematics 43, no. 3 (1921): 163–185.
2. Nisan, Noam, and Shimon Schocken. The Elements of Computing Systems: Building a Modern Computer from First Principles. 2nd ed. Cambridge, MA: MIT Press, 2021.
3. Sheffer, Henry M. “A Set of Five Independent Postulates for Boolean Algebras, with Application to Logical Constants.” Transactions of the American Mathematical Society 14, no. 4 (1913): 481–488.
4. Peirce, Charles S. “On the Algebra of Logic: A Contribution to the Philosophy of Notation.” American Journal of Mathematics 7, no. 2 (1885): 180–202.
5. Mendelson, Elliott. Introduction to Mathematical Logic. 6th ed. Boca Raton: CRC Press, 2015.