Post Logic

Origin. Emil Post (1921). First systematic many-valued logics. n-valued truth tables. Generalized negation cycles. Functional completeness results. Foundation for multi-valued computation.

Models. Truth values: 0, 1, ..., n-1. Cyclic negation: N(i) = i+1 mod n. Designated values: typically {n-1} or {k, k+1, ..., n-1}. All truth functions definable.

Formalism.

Truth values: V_n = {0, 1, 2, ..., n-1} Ordered: 0 < 1 < ... < n-1

Post negation (cyclic): N(v) = (v + 1) mod n N^n(v) = v (returns after n applications)

Post disjunction: v₁ ∨ v₂ = max(v₁, v₂)

Post conjunction: v₁ ∧ v₂ = min(v₁, v₂)

Jᵢ operator: Jᵢ(v) = n-1 if v = i, else 0 "Exactly value i" detector.

Functional completeness: {N, max, J₀} generates all n-valued functions. Any truth function expressible.

Post implication: v₁ → v₂ = min(n-1, n-1-v₁+v₂)

Designated values: Typically D = {n-1} (only top value). Valid: all arguments yield designated outputs.

Symbols.

Symbol	Unicode	Name	Meaning
∨	U+2228	Logical or	Disjunction, maximum
∧	U+2227	Logical and	Conjunction, minimum
→	U+2192	Rightwards arrow	Implication, min(n−1, n−1−v₁+v₂)
N	—	Cyclic negation	Successor modulo n; N(v) = (v+1) mod n
Jᵢ	—	J operator	Value detector: n−1 if v = i, else 0
Vₙ	—	Value set	{0, 1, …, n−1}, ordered
D	—	Designated set	Typically {n−1}
Pₙ	—	Post's n-valued system	The logic over Vₙ with N and max

Metatheory. Post (1921) proved these systems functionally complete: cyclic negation together with max-disjunction already defines every function Vₙᵏ → Vₙ, so the Jᵢ detectors are definable rather than primitive — for n = 3, J₀(x) is N(max(x, N(x))). Functional completeness makes Pₙ the many-valued analogue of the classical two-valued case, which it recovers exactly at n = 2, where cyclic negation is ordinary negation. Validity is decidable by evaluation over the finite matrix, and for each fixed n the tautology problem is coNP-complete. Post algebras (Rosenbloom 1942, Epstein 1960) supply the algebraic semantics; they form a variety, and the complemented elements of a Post algebra of order n form a Boolean algebra, which is the sense in which these systems generalize Boolean algebra rather than replacing it. Post's other classification — the 1941 lattice of all clones of Boolean functions, countable and completely described — has no many-valued analogue: Yanov and Muchnik (1959) showed that on a domain of k ≥ 3 elements there are continuum many clones, so the finite-valued case above two is not classifiable in Post's own sense.

Applies to. Multi-valued circuit design. Switching theory. Theoretical computer science. Mathematical logic foundations. Finite-valued semantics.

Limitations. Cyclic negation is neither order-preserving nor order-reversing — it sends the top value n−1 to 0 — so it carries no truth-order reading, the De Morgan laws fail for it, and it is not a negation in the sense that the Kleene, Łukasiewicz, or Belnap families use. Excluded middle fails accordingly: φ ∨ Nφ takes the value max(v, (v+1) mod n), which is designated only when v is n−1 or n−2. Functional completeness comes at the loss of interpretation — the intermediate values are positions in a cycle and carry no independent meaning, so the systems supply no account of vagueness, partiality, or paradox, which is why later many-valued logics abandoned the cyclic operator. The construction requires finiteness: a cycle of order n has no infinite-valued analogue, so nothing here reaches Łukasiewicz's Ł∞. And finite matrices are intrinsically limited as semantics — Gödel (1932) proved intuitionistic propositional logic has no finite characteristic matrix, so no Pₙ captures it. Which values are designated is not fixed by the algebra, and different choices give different consequence relations over the same tables.