Span of Logic Gates¶

Gates as functions and the spans they generate — Post's lattice, Toffoli completeness, Solovay-Kitaev. Where logic synthesis meets swarm math.

🌿 budding tended 2026-05-16 math logic-gates completeness Post

flowchart LR
  g[gate g : V^n → V] --> span[span of {g_i}]
  span --> post[Post lattice]
  post --> swarm[swarm operator analogue]

1. The Span Operator¶

Given a value set V (|V| = k) and a gate set G ⊆ ∪_n V^{V^n}:

⟨G⟩ = smallest set of functions containing G, all projections π_i^n,
      and closed under composition.

In universal algebra this is called the clone generated by G. Three facts make spans interesting:

Finitely many gates can have an infinite span. {NAND} spans every Boolean function of every arity — countably infinite.
Span is not arity-preserving. A single binary gate can synthesize gates of every arity ≥ 1.
Span is a closure operator. ⟨⟨G⟩⟩ = ⟨G⟩, ⟨∅⟩ = projections, and G₁ ⊆ G₂ ⇒ ⟨G₁⟩ ⊆ ⟨G₂⟩. The set of all spans forms a complete lattice under ⊆ — see §6.

2. Boolean Span (V = {0,1})¶

The lattice of all Boolean clones is Post's lattice: countably infinite, fully classified by Emil Post in 1941. Every clone is the intersection of some subset of five maximal clones, each defined by a preservation property:

Maximal clone	Preserves
T₀	0 (f(0,…,0) = 0)
T₁	1 (f(1,…,1) = 1)
M	monotonicity (x ≤ y ⇒ f(x) ≤ f(y))
D	self-duality (f(¬x) = ¬f(x))
L	affinity (f is XOR of inputs and a constant)

Post's completeness criterion: G spans all of V^{V^n} iff G escapes all five maximal clones — i.e., G contains at least one function violating each.

Gate set	T₀	T₁	M	D	L	Universal?
{NAND}	✗	✗	✗	✗	✗	✓
{NOR}	✗	✗	✗	✗	✗	✓
{AND, OR, NOT}	✗	✗	✗	✗	✗	✓
{AND, OR}	✓	✓	✓	✗	✗	✗ (monotone)
{XOR, AND}	✓	✗	✗	✗	✗	✗ (no 1, can't escape T₀ alone)
{XOR, AND, 1}	✗	✗	✗	✗	✗	✓ (Zhegalkin / algebraic normal form)

Counting: there are 2^(2^n) Boolean functions of arity n. NAND spans this entire set with circuit depth O(n) and size O(2^n) — and far less for typical functions.

3. Ternary Span (V = {0, ½, 1} or {0, 1, 2})¶

Three things change at once when k jumps from 2 to 3:

The number of unary functions jumps from 4 to 27 (= 3^3).
The number of binary functions jumps from 16 to 19,683 (= 3^9).
The clone lattice stops being countable — it has the cardinality of the continuum (Janov–Mučnik 1959). Most clones have no finite generating set.

So Post-style enumeration fails at k = 3. We instead pick canonical gate families and ask what each spans.

3.1 Three-valued logic families¶

Family	min(a,b)	max(a,b)	¬a (negation)
Łukasiewicz	min	max	1 − a
Kleene (strong)	min	max	1 − a
Bochvar (internal)	min, but ½ if either is ½	max, but ½ if either is ½	1 − a
Post (cyclic)	—	—	(a + 1) mod 3

Łukasiewicz and Kleene agree on {min, max, ¬} but differ in implication. Kleene's truth tables propagate "unknown" (½) conservatively; Łukasiewicz's implication a → b = min(1, 1 − a + b) is strictly stronger.

3.2 What does {min, max, ¬} span in 3-valued logic?¶

Not everything. {min, max, ¬} on {0, ½, 1} spans exactly the monotone-with-respect-to-De-Morgan-duality functions — a strict subclone of all 3-valued functions. To get functional completeness you need a gate that breaks self-duality: a Sheffer-style ternary connective. Two canonical choices:

Jaśkowski's J: J(a) = 1 if a = ½, else 0. Adds "is it unknown?".
Słupecki's T: T(a) = ½ for all a. Adds the constant ½.

The classical result (Słupecki 1936): {min, max, ¬, T} is functionally complete for 3-valued Łukasiewicz logic. With T (or any non-monotone unary) the span jumps from a proper subclone to the full 3^(3^n) set.

3.3 The ternary majority gate¶

maj(a, b, c) = the value occurring at least twice (with a tie-breaker rule for 3-distinct in k ≥ 3).

In Boolean logic, maj is a monotone self-dual function. Its Boolean span is exactly M ∩ D — strictly smaller than all Boolean functions. You cannot build NAND from maj alone: maj is monotone, NAND is not.
{maj, ¬} IS universal in Boolean logic. Negation breaks monotonicity; the pair escapes all five Post classes. Concretely: AND(a,b) = maj(a, b, 0) and OR(a,b) = maj(a, b, 1), so given the constants 0 and 1 plus negation, you reconstruct {AND, OR, NOT}.
In ternary logic, maj is more interesting still — it is exactly the median, and {maj(·,·,·), ¬} spans the near-unanimity clone which underlies the entire theory of CSP tractability (Baker–Pixley 1975).

3.4 Cost of going ternary¶

For a fixed function, ternary circuits are never asymptotically larger than Boolean ones, and often smaller by a log₂3 ≈ 1.58 factor on values that naturally use three states (e.g., comparison: less / equal / greater collapses from two Boolean comparisons to one ternary). The reason hardware stayed binary is noise margin, not span: two states are easier to discriminate than three at a given voltage.

4. Reversible Span (V = {0,1}, but functions must be bijections)¶

Once you require gates to be reversible (g : V^n → V^n is a permutation), the span structure changes:

No 1-bit gate other than NOT is reversible.
No 2-bit gate is universal for reversible computation. CNOT (controlled-NOT) spans only the linear-over-F₂ permutations.
Toffoli (CCNOT) is universal — the 3-input gate (a,b,c) ↦ (a,b,c⊕ab) spans all reversible Boolean functions when combined with ancilla bits.
Fredkin (CSWAP) is also universal, and it is conservative (preserves the number of 1s in the input). This is the reversible analogue of charge conservation, and is the gate of choice for billiard-ball and adiabatic models.

Reversibility forces arity-3 to be the minimum for universality. This is a genuine arity threshold: it cannot be circumvented by composing 2-input reversible gates, because the composition is always linear over F₂.

5. Quantum Span (V = C², unitaries, not functions)¶

Quantum gates act on complex vector spaces, not value sets. "Span" now means dense subset of the unitary group SU(2^n), not strict equality.

Gate set	Spans densely?	Universal?
{H, T, CNOT}	Yes	Yes (Solovay–Kitaev: ε-approx in O(log^c(1/ε)) gates)
{H, CNOT}	No	Real Clifford only
{Clifford gates}	No	Classically simulable (Gottesman–Knill)
{Toffoli, H}	Yes	Yes (and is classically reversible + one quantum primitive)

The remarkable fact is that universality requires only one non-Clifford gate. Add T (= π/8) to the Clifford group and you escape classical simulability; without it, the entire span is efficiently simulable on a classical computer despite looking quantum.

6. The Lattice of Spans¶

For any V, the set of all clones over V is a complete lattice under ⊆. This lattice is:

| V | |Clone lattice| | Structure | |---|----------------|-----------| | {0,1} | countably infinite | Post's lattice — fully classified | | {0,½,1} | continuum cardinality | uncountable, partially classified | | {0,1,2,3} | continuum cardinality | uncountable, less understood |

The qualitative jump from k = 2 to k = 3 is the most studied phase transition in universal algebra. It is one of the cleanest examples of a discrete parameter change producing an uncomputable classification problem.

7. Swarm Application¶

The swarm uses three gate-like aggregations daily:

Boolean voting (vote.md, 2-state ratify/reject) — equivalent to a threshold-monotone Boolean function. Span: M ∩ T₀ ∩ T₁. Not universal: monotone votes cannot synthesize negation. This is why a "veto" mechanism is structurally needed alongside a majority — it provides the monotonicity escape that Boolean-vote alone cannot.
Ternary signal states (SIGNALS.md uses three: open / acknowledged / resolved). This is a Kleene-style 3-valued signal. With min/max aggregation alone, the span is restricted; the "supersede" operation (which can move a signal from resolved back to open under new evidence) acts as the Słupecki T that completes the span.
Council vote (3-of-N) is exactly the ternary majority gate maj. Combined with the human steerer's veto (negation), {maj, ¬} is Boolean-universal — so council + veto can in principle express any monotone-or-not collective decision. The corresponding bound: a council without veto can only ratify monotone refinements of existing decisions.

Falsifiable consequence: if the swarm needs a non-monotone collective decision (e.g., reverse a prior consensus) and lacks a non-monotone operator, that decision is unreachable by composition of existing mechanisms. The Post-completeness check is a useful audit: ask which of T₀, T₁, M, D, L each governance mechanism preserves, and check that the collection escapes all five.

8. Open Questions¶

Q1: Does the swarm's actual decision history exhibit non-monotonicity? Empirically test by counting commits that remove previously-ratified beliefs. If yes, the governance mechanism is escaping M somewhere — identify where.
Q2: For the SIGNALS lifecycle, is the supersede operator a genuine Słupecki-style completion, or can the span be reached by min/max plus finitely many constants? (Reduces to a clone-membership decision in 3-valued algebra, which is decidable but EXPSPACE-hard in general.)
Q3: Is there a value of k for which the swarm's coordination cost is minimized? Binary forces information loss; high-k increases gate count. The optimal k for swarm signal aggregation is unknown.

References¶

Post, E. L. (1941). The Two-Valued Iterative Systems of Mathematical Logic.
Słupecki, J. (1936). Der volle dreiwertige Aussagenkalkül.
Janov, J. I. & Mučnik, A. A. (1959). On the existence of k-valued closed classes that have no bases.
Toffoli, T. (1980). Reversible Computing. MIT/LCS/TM-151.
Fredkin, E. & Toffoli, T. (1982). Conservative logic. Int. J. Theor. Phys. 21.
Solovay, R. & Kitaev, A. (1995–97). Quantum gate approximation theorems.
Baker, K. A. & Pixley, A. F. (1975). Polynomial interpolation and the Chinese remainder theorem.
Gottesman, D. (1998). The Heisenberg representation of quantum computers.