Zhegalkin Polynomial: Any Boolean Function as One Formula

The Boolean function calculator prints PDNF and PCNF — and places a third form next to them: the Zhegalkin polynomial. It contains neither negation nor disjunction: two operations are enough, addition modulo two and multiplication. In 1927 the Moscow mathematician Ivan Zhegalkin proved that such a representation exists for every truth table and is unique. Western textbooks call the form algebraic normal form, ANF, and in cryptography it is still a working tool.

What a polynomial over zeros and ones looks like

Let us fix the notation: addition is XOR (⊕, sum modulo two), multiplication is conjunction (∧). The polynomial in variables x₁, …, x_n looks like a sum of products:

f = a₀ ⊕ a₁x₁ ⊕ a₂x₂ ⊕ a₁₂x₁x₂ ⊕ … ⊕ a₁…ₙx₁…xₙ

The coefficients a are 0 or 1: a term either enters the polynomial or does not. Here is how the basic operations expand:

The last row needs a comment: when both inputs are 1, XOR gives 0 while disjunction wants 1 — hence the correction term x·y added to x ⊕ y. Negation is a special case of the same arithmetic: adding one modulo two flips the bit, ¬x = x ⊕ 1. Any expression assembles from the two rules: x → y expands as ¬x ∨ y and, after collecting terms, becomes 1 ⊕ x ⊕ x·y (we will verify it with a table below; take it on faith for now).

The polynomial exists and is unique

Let us count. A monomial (a product of distinct variables) is built by a choice: take each of the n variables into the product or not; the empty product is the constant. That gives 2ⁿ monomials, each with a coefficient of 0 or 1 — hence exactly 2^(2ⁿ) distinct polynomials. Exactly that many Boolean functions of n variables exist too. Zhegalkin's theorem (1927) says every function is representable as a polynomial. Since functions and polynomials come in equal numbers and each polynomial defines exactly one function, the representation must be unique: two different truth tables cannot yield the same polynomial.

A sanity check for n = 2: 4 monomials (1, x, y, x·y), 2⁴ = 16 polynomials — the same 16 functions a four-row truth table enumerates.

Getting the polynomial from a truth table

The method of undetermined coefficients solves the polynomial row by row, first row to last. Take the implication x → y with value vector 1, 1, 0, 1 (rows 00, 01, 10, 11) and substitute into the general form:

f = a ⊕ b·x ⊕ c·y ⊕ d·x·y

00: f = a             = 1 → a = 1
01: f = a ⊕ c         = 1 → c = 0
10: f = a ⊕ b         = 0 → b = 1
11: f = a ⊕ b ⊕ c ⊕ d = 1 → d = 1

Each new row introduces exactly one new unknown and never contradicts the previous ones: the system is triangular and resolves in a single pass. The answer: x → y = 1 ⊕ x ⊕ x·y. For n variables the scheme is identical, only with 2ⁿ rows.

The calculator goes faster, via the Möbius transform: it takes the value vector and, for each variable, replaces the lower half of every block with its sum with the upper half. For the vector 1101 (the same implication): the starting state is 1 1 0 1, one pass along y gives 1 0 0 1, one pass along x gives 1 0 1 1. The four output numbers are the coefficients of 1, y, x and x·y — again 1 ⊕ x ⊕ x·y. The intermediate vectors appear in the solution when you switch on the "Show solution" option.

Polynomial degree and linear functions

The degree is the largest number of variables in one product. A polynomial of degree at most one is special: it is a constant, the XOR of variables, or the XOR of possibly inverted variables (x ⊕ 1 = ¬x). Such functions form Post's class L, and the calculator tests membership in it through exactly this polynomial: found a product of two or more variables — the function is nonlinear.

The most recognizable linear function is strict parity, the XOR of all inputs. Shift registers with feedback run on it: in an LFSR the new bit is a linear polynomial of several stages, for instance x₁ ⊕ x₅. The LFSR component lives in the sandbox: apply a clock tick and watch the one run around the ring.

Where the polynomial works

In circuit design the form pays off wherever XOR is cheaper than disjunction: adder sums, parity generators and checkers, CRC — these are chains of exclusive-or, that is, polynomials of first or low degree packed into a minimal number of gates.

In cryptography ANF is the language of block-cipher analysis: the degree of an S-box's polynomials and its distance from the class of linear functions (nonlinearity) decide whether the algorithm survives linear and algebraic attacks. A good S-box is built so that its Zhegalkin polynomial contains many high-degree terms: then each individual equation tells you almost nothing about the key.

Why it matters in the game

The full adder (level 1.7) is the textbook case of the difference in forms. The sum of three bits takes four minterms in PDNF, but one line in a polynomial: A ⊕ B ⊕ P, where P is the incoming carry. The carry is written equally shortly in both forms: AB ⊕ AP ⊕ BP. The coincidence with the minimal DNF from the previous article is not an accident: on every input combination where the majority function outputs 1, exactly one pair of inputs is satisfied or all three are — an odd count; for an odd number of ones disjunction and addition modulo two agree.

assign sum   = a ^ b ^ c;
assign carry = (a & b) ^ (a & c) ^ (b & c);

Enter the voting vector 00010111 into the calculator, switch on "Show solution", and you will get the polynomial AB ⊕ AP ⊕ BP plus all three Möbius passes in a separate table. A truth table for the same function is also available in the truth table generator.

Summary

1. A Zhegalkin polynomial is a sum modulo two of products of variables with 0/1 coefficients; the operations ⊕ and ∧ suffice.

2. The representation exists and is unique: there are exactly as many polynomials as functions (2^(2ⁿ)); Zhegalkin proved it in 1927.

3. Coefficients solve by triangular substitution of truth-table rows, the method of undetermined coefficients; the calculator uses the Möbius transform in n passes.

4. Degree at most one means linear functions: parity, XOR chains, LFSR feedback — that is class L in the Post test.

5. The polynomial saves gates wherever XOR is cheap: the full adder's sum is one line against four minterms in PDNF.

On levels 1.6–1.8 look at the sums of the full and 8-bit adders with fresh eyes: both are linear in Zhegalkin's form, and that is why the bit-summing blocks in your circuit are XOR chains rather than four-level PDNF schemes. Check any function of your own in the calculator; next in the course comes arithmetic: Binary Math for Beginners.