---
title: "The Two-Valued Iterative Systems of Mathematical Logic"
authors:
  - "Emil L. Post"
year: 1941
venue: "Annals of Mathematics Studies, Princeton"
arxiv: null
doi: null
source: "https://press.princeton.edu/books/paperback/9780691095707/the-two-valued-iterative-systems-of-mathematical-logic"
topics:
  - boolean-clones
  - post
  - universal-gates
seed_rank: 538
seed_batch: "foundations-greats-2026-08-13"
reviewed: "2026-08-13"
pool: "maths-foundations"
relevance_score: 8
lineage: foundations-of-computing
cites:
  - title: "Introduction to a General Theory of Elementary Propositions"
    url: "https://doi.org/10.2307/2370324"
    year: 1921
    arxiv: null
    doi: "10.2307/2370324"
  - title: "A Symbolic Analysis of Relay and Switching Circuits"
    url: "https://doi.org/10.1109/T-AIEE.1938.5057767"
    year: 1938
    arxiv: null
    doi: "10.1109/T-AIEE.1938.5057767"
  - title: "Reliable circuits using less reliable relays"
    url: "https://doi.org/10.1016/0016-0032(56)90559-2"
    year: 1956
    arxiv: null
    doi: "10.1016/0016-0032(56)90559-2"
see:
  - "537-introduction-to-a-general-theory-of-elementary-propositions"
  - "552-a-symbolic-analysis-of-relay-and-switching-circuits"
  - "560-reliable-circuits-using-less-reliable-relays"
---

# The Two-Valued Iterative Systems of Mathematical Logic

## One-sentence takeaway

Post classifies every clone of Boolean functions—the lattice that says exactly which gate sets (NAND, NOR, majority+not, …) are functionally complete.

## Why it matters here

Foundations of circuit universality, and the reason Anoptic can compile arbitrary standing-rule predicates down to a chosen gate library. Pairs with Shannon's switching theory: Shannon shows how to realize a Boolean function; Post says which primitives can express every function.

## Key ideas

- An *iterative system* (clone) is a set of Boolean functions closed under composition and containing the projections.
- Post's lattice enumerates all such clones; the maximal ones under the full clone of all Boolean functions give the functional-completeness criteria.
- NAND alone, NOR alone, and several other small bases sit at the top of the lattice.
- Written 1921, published as Princeton Annals of Mathematics Study 5 in 1941.

## Caveats

## Links

- Princeton: https://press.princeton.edu/books/paperback/9780691095707/the-two-valued-iterative-systems-of-mathematical-logic