Normal Forms and Post's Theorem

SDNF and SCNF

SDNF (perfect disjunctive normal form): disjunction of minterms. A minterm is the conjunction of all variables (with or without negations) corresponding to a row of the truth table with f=1.

f(x,y) = (x AND NOT y) OR (NOT x AND y) = x⊕y (XOR).

SCNF (perfect conjunctive normal form): conjunction of maxterms (disjunctions for rows with f=0).

Post's Completeness Theorem

A closed class of functions is a set F closed under superposition (substitution, identification of variables).

The five Post classes:

• T₀: functions preserving 0 (f(0,...,0)=0)
• T₁: functions preserving 1 (f(1,...,1)=1)
• S: self-dual (f(¬x₁,...,¬xₙ) = ¬f(x₁,...,xₙ))
• M: monotone (xᵢ ≤ yᵢ → f(x) ≤ f(y))
• L: linear (over GF(2))

Post's theorem: A system F of functions is complete if and only if it is not contained in any of the five classes.

Applications

Minimization of Boolean functions is a task of logic synthesis. The Quine–McCluskey method: finding a minimal CNF/DNF. Karnaugh map — a graphical method for functions up to 4-5 variables.

In CAD: synthesis of digital circuits = minimization of Boolean functions with constraints on the number of gates.

The Five Closed Post Classes: Details

Each closed class has substantive meaning. T₀ (preserving 0) includes AND, OR, XOR, constant 0, but not NOT (NOT(0)=1). T₁ (preserving 1) includes AND, OR, but not XOR (XOR(1,1)=0). S (self-dual) — functions for which, upon simultaneous inversion of all arguments, the value inverts: f(¬x) = ¬f(x). NOT is self-dual: NOT(¬x) = ¬(NOT x). Majority M(x,y,z) = “at least two out of three” is self-dual. M (monotone) — the value does not decrease when going from 0 to 1: AND, OR, constants are monotone, NOT is not. L (linear) — functions of the form c₀ ⊕ c₁x₁ ⊕ ... ⊕ cₙxₙ over GF(2): XOR, NOT, identity. AND is nonlinear.

The system {AND, OR, NOT} is complete: NOT ∉ T₀, AND ∉ S, OR ∉ L. {NAND} is complete: a single function violates all five classes. {XOR, AND, 1} is complete: AND violates S and T₀; check the rest.

Complexity of Completeness Recognition

Verifying Post’s theorem for a specific system of functions is an algorithmically solvable problem of polynomial complexity: it is necessary to check the inclusion of each function in each of the five classes. But the problem of finding a minimal complete system in a given class of functions is NP-hard.

There exist functionally complete single-element systems: {NAND}, {NOR}. Processors are actually built from NAND gates: they are universal, cheap to manufacture, and implemented in CMOS technology with a minimal transistor count. NAND(x,y) = ¬(x∧y): NOT(x) = NAND(x,x); AND(x,y) = NAND(NAND(x,y), NAND(x,y)); OR(x,y) = NAND(NAND(x,x), NAND(y,y)).

Zhegalkin Polynomials

Every Boolean function can be written uniquely as a Zhegalkin polynomial — a polynomial over GF(2) with coefficients 0 or 1: f(x₁,...,xₙ) = c₀ ⊕ c₁x₁ ⊕ ... ⊕ c_{12}x₁x₂ ⊕ ... ⊕ c_{12...n}x₁x₂...xₙ. Linear functions (Post's class L) are exactly those whose Zhegalkin polynomial lacks terms of degree ≥ 2. This criterion gives an algorithm for checking linearity in O(2^n) via the difference triangle (analogous to Pascal’s triangle).

Completeness Theorem for Many-Valued Logics

In the three-valued Łukasiewicz logic (values: 0, 1/2, 1), classical two-valued completeness fails — {NAND} is not complete. Completeness criteria for many-valued logics are more complex and depend on structure. In fuzzy logic (values from [0,1]), AND plays the role of a t-norm (min or multiplication), OR — t-conorm (max or probabilistic sum), NOT — involution. Completeness depends on the choice of operations.

Quantum Logic Gates: Generalization of Boolean

Quantum gates act on qubits — superpositions of |0⟩ and |1⟩. They are represented by unitary matrices, not Boolean functions. The Hadamard gate H: |0⟩ → (|0⟩+|1⟩)/√2 (superposition). The CNOT gate (controlled-NOT): |x,y⟩ → |x, y⊕x⟩ — quantum analog of XOR. Solovay-Kitaev theorem: any quantum gate is approximated by a product of basic gates {H, T, CNOT} with exponentially small error, using O(log^c(1/ε)) gates. This is the quantum analog of Post’s theorem of functional completeness.

Quantum Entanglement and Its Computational Implications

Entanglement: the state of a two-qubit system is called entangled if it cannot be written as |ψ₁⟩⊗|ψ₂⟩. Example: |Φ⁺⟩ = (|00⟩+|11⟩)/√2 — Bell state. EPR paradox and Bell inequalities: quantum correlations exceed any local hidden variable theory. Quantum teleportation: transmission of a quantum state without physical transfer of a particle, using entanglement and two classical bits. Super-dense coding: transmit 2 classical bits using 1 qubit (with an entangled pair present).

Numerical Example: Normal Forms and Functional Completeness

Task: (a) Represent f(a,b)=a∧¬b in DNF and CNF. (b) Check if {⊕,1} (XOR and constant 1) is complete.

Step 1 (Normal Form): Truth table for f(a,b): (0,0)=0, (0,1)=0, (1,0)=1, (1,1)=0. One unit minterm: (1,0).

Step 2 (DNF): DNF: f = a∧¬b. CNF: zero rows (0,0),(0,1),(1,1) → max-disjuncts (a∨b), (a∨¬b), (¬a∨¬b). CNF: f=(a∨b)∧(a∨¬b)∧(¬a∨¬b). Simplification: (a∨b)∧(a∨¬b)=a; f=a∧(¬a∨¬b)=a∧¬b ✓.

Step 3 (completeness): Post criterion: {⊕,1} is linear (⊕ — XOR, 1 — linear constant). Any superposition of linear functions is linear. The conjunction a∧b is nonlinear → not realizable.

Step 4: {⊕,1} is NOT functionally complete. For completeness, add ∧: then {⊕,∧,1} is complete (implements ¬a=a⊕1, all operations). The system {NAND} is complete: ¬a=NAND(a,a), a∧b=¬NAND(a,b), a∨b=NAND(¬a,¬b). Normal forms are used in VLSI verification via BDD circuit equivalence checking.