Post 1921: Truth Tables and Complete Propositional Systems

Emil L. Post's 1921 paper is an original source for the truth-functional treatment of elementary propositions. The archived object has 36 physical pages; the article itself occupies physical pages 7–29, corresponding to printed pages 163–185. All pages, including the binding matter and Post's vita, were inspected.

What the paper establishes #

In Section 2, printed page 167, Post defines truth tables of positive order and counts the possible tables. In modern notation, an $n$-argument Boolean function with $n\geq1$ has $2^n$ input rows and therefore $2^{2^n}$ possible output columns. This is a count of extensional behaviors, not of formula strings: many formulas may have the same column.

Section 5, printed page 174, defines a complete system through its ability to represent every possible truth table and exhibits single binary truth tables that generate complete systems. The paper uses historical tables and notation; modern NAND and NOR identities are clearer constructive witnesses for current readers.

Source boundary #

This paper does not provide the exact five-obstruction functional-completeness criterion. That classification belongs to Post's later work. It also works with positive arity, so it does not settle a modern convention about nullary constants. It is controlling evidence for the historical truth-table framework and early completeness results, not for the entire modern clone lattice.