Algebraic Normal Form of Boolean Functions Explained

This article provides a clear overview of the Algebraic Normal Form (ANF) of Boolean functions, detailing how it represents logical operations through polynomial equations in the binary system. You will learn the mathematical foundation of ANF, how truth values are mapped to the binary field \(\mathbb{F}_2\) (or GF(2)), the rules for converting standard logic operations into algebraic terms, and the practical significance of this canonical representation in modern computing and cryptography.

What is Algebraic Normal Form (ANF)?

Algebraic Normal Form (ANF), also known as the Zhegalkin polynomial, is a canonical way of expressing any Boolean function as a polynomial over the two-element Galois field, denoted as \(\text{GF}(2)\) or \(\mathbb{F}_2\).

In standard Boolean logic, functions are typically expressed using combinations of AND (\(\land\)), OR (\(\lor\)), and NOT (\(\neg\)) operators. In contrast, ANF expresses functions exclusively using two fundamental operations: 1. Addition modulo 2 (equivalent to the logical XOR operation, denoted as \(\oplus\)). 2. Multiplication (equivalent to the logical AND operation, denoted as \(\cdot\) or simple concatenation).

Because the representation is canonical, every Boolean function corresponds to one and only one unique ANF polynomial.

Expressing Truth Values in the Binary System

ANF operates strictly within the binary number system by mapping standard Boolean truth values to elements of \(\text{GF}(2)\):

The Arithmetic Operations

  1. Addition (\(\oplus\)): Modulo-2 Addition (XOR)
    • \(0 \oplus 0 = 0\)
    • \(0 \oplus 1 = 1\)
    • \(1 \oplus 0 = 1\)
    • \(1 \oplus 1 = 0\)
  2. Multiplication (\(\cdot\)): Standard Binary Multiplication (AND)
    • \(0 \cdot 0 = 0\)
    • \(0 \cdot 1 = 0\)
    • \(1 \cdot 0 = 0\)
    • \(1 \cdot 1 = 1\)
  3. Additive Inversion (NOT) The logical NOT of a variable \(x\) is expressed algebraically as adding \(1\): \[\neg x = 1 \oplus x\]

Because \(x \cdot x = x\) (idempotence) and \(x \oplus x = 0\) in binary field arithmetic, no variable in an ANF expression ever has an exponent greater than \(1\), and identical terms cancel each other out.

Mathematical Structure of ANF

For a Boolean function with \(n\) variables, \(f(x_1, x_2, \dots, x_n)\), the ANF is written as the XOR sum of all possible product terms (monomials):

\[f(x_1, \dots, x_n) = a_0 \oplus \bigoplus_{1 \le i \le n} a_i x_i \oplus \bigoplus_{1 \le i < j \le n} a_{ij} x_i x_j \oplus \dots \oplus a_{12\dots n} x_1 x_2 \dots x_n\]

Where: * \(a_0, a_i, a_{ij}, \dots \in \{0, 1\}\) are binary coefficients. * \(a_0\) is the constant term (\(f(0, 0, \dots, 0)\)). * Linear terms have single variables (\(x_i\)). * Higher-order terms represent the conjunction (AND) of multiple variables (\(x_i x_j\)).

There are \(2^n\) possible coefficients, matching the total number of entries in a truth table for \(n\) variables.

Example: Converting Standard Logic to ANF

Consider the standard inclusive OR function: \(f(x, y) = x \lor y\).

Using De Morgan’s Laws and binary arithmetic: 1. \(x \lor y = \neg(\neg x \land \neg y)\) 2. Replace \(\neg z\) with \((1 \oplus z)\) and \(\land\) with multiplication: \[f(x, y) = 1 \oplus ((1 \oplus x)(1 \oplus y))\] 3. Expand the product: \[f(x, y) = 1 \oplus (1 \oplus y \oplus x \oplus xy)\] 4. Simplify using modulo-2 rules (\(1 \oplus 1 = 0\)): \[f(x, y) = x \oplus y \oplus xy\]

This final expression, \(x \oplus y \oplus xy\), is the unique Algebraic Normal Form for the OR operation.

Key Properties and Significance