Fact-checked by Grok 2 weeks ago

Boolean function

A Boolean function is a function f: \{0,1\}^n \to \{0,1\}, where n is a non-negative integer, mapping binary inputs to a binary output, often interpreted as true/false or 1/0 values. These functions form the foundation of propositional logic and digital computation, with each possible input tuple corresponding to a truth value in a truth table representation. Boolean functions originated in the mid-19th century through George Boole's development of algebraic logic in works like The Mathematical Analysis of Logic (1847) and An Investigation of the Laws of Thought (1854), which formalized operations on logical classes using symbols akin to arithmetic. Their modern application to and was pioneered by in his 1938 master's thesis, demonstrating how could model switching circuits. Today, Boolean functions underpin diverse fields, including , where they define logic gates; complexity theory, analyzing computational hardness via measures like circuit size; and , where properties such as nonlinearity and immunity ensure secure stream ciphers. Key representations of Boolean functions include (DNF), a disjunction of minterms for all inputs yielding 1, and (CNF), its dual for inputs yielding 0, both facilitating testing central to . over the provides spectral insights, decomposing functions into characters (parity functions) to study influences, noise stability, and depth, with applications in learning and social choice. Notable properties include monotonicity, linearity, and bentness, the latter optimizing resistance to in block ciphers.

Fundamentals

Definition and Notation

A Boolean function is formally defined as a mapping f: \{0,1\}^n \to \{0,1\}, where n \geq 0 is the number of input variables, known as the of the function. This definition captures functions that take inputs and produce a output, forming the foundation for computations in logic and . Claude E. Shannon established the connection between and the analysis of electrical switching circuits in his 1938 master's thesis. In standard notation, the input variables are denoted as x_1, x_2, \dots, x_n \in \{0,1\}, with the function value written as f(x_1, x_2, \dots, x_n). The of a Boolean function f, denoted \operatorname{supp}(f), is the set of indices \{i \in : f depends on x_i\}, identifying the variables that influence the output. Boolean functions are typically total, meaning they are defined for every possible input in the \{0,1\}^n; partial Boolean functions, which are defined only on a proper of the domain, arise in certain contexts but are not the primary focus here. A common way to represent a Boolean function f of arity n is as a vector \mathbf{f} \in \{0,1\}^{2^n}, where the k-th entry (for k = 0, 1, \dots, 2^n - 1) is f(\mathbf{x}) and \mathbf{x} is the binary representation of k as an n-bit string, ordered lexicographically. This vector encoding corresponds directly to the truth table of f, listing outputs for all inputs in binary order.

Basic Examples

Boolean functions with a single input variable, known as functions, provide the foundational building blocks for more complex expressions. The constant 0 function outputs 0 for any input x \in \{0,1\}, while the constant 1 function outputs 1 regardless of the input. These functions are independent of the input and serve as trivial cases in . The simply returns the input, f(x) = x, preserving the value unchanged. In contrast, the function inverts the input, denoted f(x) = \neg x or, in arithmetic form over the reals, f(x) = 1 - x. Binary Boolean functions operate on two input variables x, y \in \{0,1\} and are commonly illustrated through their s, which enumerate all possible input combinations and corresponding outputs. The AND function, f(x,y) = x \land y or in arithmetic form xy, outputs 1 only if both inputs are 1. Its is:
xyx \land y
000
010
100
111
The OR , f(x,y) = x \lor y or arithmetically x + y - xy, outputs 1 if at least one input is 1. Its is:
xyx \lor y
000
011
101
111
The XOR function, f(x,y) = x \oplus y or arithmetically x + y - 2xy, outputs 1 if the inputs differ. Its truth table is:
xyx \oplus y
000
011
101
110
The NAND function is the negation of AND, f(x,y) = \neg (x \land y), outputting 0 only if both inputs are 1. Its truth table is:
xyNAND
001
011
101
110
The NOR function is the negation of OR, f(x,y) = \neg (x \lor y), outputting 1 only if both inputs are 0. Its truth table is:
xyNOR
001
010
100
110
To illustrate functions with more inputs, consider the on three variables x, y, z \in \{0,1\}, which outputs 1 if at least two inputs are 1 and 0 otherwise. This function captures a voting-like decision where the determines the outcome, and it appears in applications such as and error correction.

Representations

Truth Tables

A truth table provides the canonical tabular representation for exhaustively specifying a Boolean function, listing every possible input and its corresponding output value. For a Boolean function f: \{0,1\}^n \to \{0,1\}, the truth table has $2^n rows, one for each input vector from the domain, ordered lexicographically from (0,0,\dots,0) to (1,1,\dots,1), with an additional column for the output f(x). The construction involves systematically enumerating all binary input tuples in this order and evaluating the function at each point. This representation ensures uniqueness: every Boolean function maps to precisely one truth table of size $2^n, fully capturing its input-output behavior without omission or redundancy. offer complete specification of the function, enabling straightforward verification of properties, equivalence checks between functions, and manual analysis for small n. Their primary limitation is the exponential scaling with n, as the table size $2^n becomes impractical to store, compute, or inspect for n > 20, where even modern hardware struggles with the resulting volume of data. A representative example is the binary exclusive-or (XOR) function f(x_1, x_2) = x_1 \oplus x_2, which returns 1 if exactly one input is 1. Its truth table is:
x_1x_2f
000
011
101
110
For three variables, the f(x_1, x_2, x_3) outputs 1 if the number of 1s among the inputs is odd. Its is:
x_1x_2x_3f
0000
0011
0101
0110
1001
1010
1100
1111

Normal Forms

In Boolean functions, normal forms offer canonical representations that express any function using only disjunctions and conjunctions of literals, facilitating analysis and synthesis in digital logic and . These forms ensure every Boolean function can be uniquely described in a standardized manner, independent of its original expression. The two fundamental normal forms are the (DNF) and the (CNF), which are duals of each other under . Disjunctive Normal Form (DNF)
The disjunctive normal form represents a Boolean function as a disjunction (logical OR) of conjunctions (logical ANDs) of literals, where a literal is either a variable x_i or its negation \neg x_i. This form was introduced by Claude Shannon in the context of switching circuit design, where it corresponds to a two-level OR-AND circuit. The canonical or full DNF, also known as the sum-of-minterms form, includes every minterm where the function evaluates to true, ensuring completeness without redundancy beyond the necessary terms. In contrast, a minimal DNF seeks to reduce the number of terms and literals by merging overlapping minterms using absorption laws, though it may not be unique. A minterm for an input \alpha = (\alpha_1, \dots, \alpha_n) \in \{0,1\}^n is the of literals that evaluates to true exactly when the inputs match \alpha: m_\alpha = \prod_{i=1}^n l_i, \quad \text{where } l_i = \begin{cases} x_i & \text{if } \alpha_i = 1, \\ \neg x_i & \text{if } \alpha_i = 0. \end{cases} The DNF of a f: \{0,1\}^n \to \{0,1\} is then the disjunction of all such minterms where f(\alpha) = 1: f(x_1, \dots, x_n) = \bigvee_{\alpha : f(\alpha)=1} m_\alpha. This representation is unique up to the ordering of terms and literals, as each minterm corresponds uniquely to a row in the function's where f = 1. For example, consider the f(x_1, x_2) = x_1 \land x_2; its DNF is x_1 x_2, consisting of the single minterm for \alpha = (1,1). Conjunctive Normal Form (CNF)
The represents a Boolean function as a (logical AND) of disjunctions (logical ORs) of literals, corresponding to a two-level . It is the dual of DNF, obtained by applying to negate a DNF representation. The or full CNF, also known as the product-of-maxterms form, includes every maxterm where the function evaluates to false. A maxterm for \alpha \in \{0,1\}^n is the disjunction of literals that evaluates to false exactly when the inputs match \alpha: M_\alpha = \bigvee_{i=1}^n l_i, \quad \text{where } l_i = \begin{cases} \neg x_i & \text{if } \alpha_i = 1, \\ x_i & \text{if } \alpha_i = 0. \end{cases} The CNF is the of all such maxterms where f(\alpha) = 0: f(x_1, \dots, x_n) = \bigwedge_{\alpha : f(\alpha)=0} M_\alpha. Like canonical DNF, this form is unique up to ordering, as it directly mirrors the rows where f = 0. A minimal CNF reduces clauses by merging using consensus laws, but uniqueness is not guaranteed. For the same example f(x_1, x_2) = x_1 \land x_2, the CNF is (x_1 \lor x_2) \land (x_1 \lor \neg x_2) \land (\neg x_1 \lor x_2), covering the three assignments where f = 0. To obtain these forms, start from the of the Boolean function and select the relevant minterms for DNF or maxterms for CNF, forming the disjunction or accordingly. This process guarantees the canonical representation for any function.

Algebraic Expressions

functions can be viewed as elements of the over the GF(2), known as the \mathbb{F}_2[x_1, \dots, x_n] / (x_i^2 + x_i \mid i=1,\dots,n), where corresponds to XOR and to AND. In this representation, every Boolean function f: \mathbb{F}_2^n \to \mathbb{F}_2 is uniquely expressed as a of degree at most n, with no squared variables due to the relations x_i^2 = x_i in GF(2). The Algebraic Normal Form (ANF), also called the Reed-Muller expansion or Zhegalkin normal form, writes f as an XOR of monomials, each being the AND of distinct variables: f(x) = \bigoplus_{I \subseteq \{1,\dots,n\}} a_I \prod_{i \in I} x_i, where the coefficients a_I \in \mathbb{F}_2 are 0 or 1, and the representation is unique for each function because the quotient ring has dimension $2^n, matching the number of Boolean functions on n variables. Equivalently, using , f(x) = \bigoplus_{u \in \mathbb{F}_2^n} a_u x^u with x^u = \prod_{j=1}^n x_j^{u_j}. The coefficient a_I of a monomial corresponding to subset I is given by the Möbius inversion formula: a_I = \bigoplus_{\substack{x \in \mathbb{F}_2^n \\ \mathrm{supp}(x) \subseteq I}} f(x), where \mathrm{supp}(x) is the support of x, i.e., the set of indices where x_i = 1; this sums f over all inputs whose 1-positions are contained in I. Algebraic operations on Boolean functions, such as composition f(g(x)), can be performed directly in this polynomial form, preserving the overall structure and allowing the ANF of the result to be derived by substitution, though the degree may increase unless g is affine. For example, the AND function on two variables has ANF f(x_1, x_2) = x_1 \cdot x_2, while the XOR function has ANF f(x_1, x_2) = x_1 + x_2.

Properties

Functional Properties

A Boolean function f: \{0,1\}^n \to \{0,1\} is monotone (or non-decreasing) if, for any two input vectors x, y \in \{0,1\}^n with x \leq y componentwise (i.e., x_i \leq y_i for all i=1,\dots,n), it holds that f(x) \leq f(y). This property captures functions that preserve the partial order on the Boolean cube, such as the conjunction (AND) function, which outputs 1 only if all inputs are 1. Equivalently, a function is monotone if and only if its (DNF) representation contains no negated literals, meaning all terms are conjunctions of uncomplemented variables. Linearity and affinity describe algebraic structures of Boolean functions over the field \mathrm{GF}(2). A function f: \mathrm{GF}(2)^n \to \mathrm{GF}(2) is linear if it satisfies f(x + y) = f(x) + f(y) for all x, y \in \mathrm{GF}(2)^n, which implies it can be expressed as an inner product f(x) = a \cdot x for some a \in \mathrm{GF}(2)^n. More generally, f is affine if it is the sum of a linear function and a constant, i.e., f(x) = a \cdot x + b where b \in \mathrm{GF}(2). These forms are fundamental in coding theory and cryptography due to their simplicity and computational efficiency. Degeneracy refers to the dependence structure of a Boolean function on its variables. A function f: \{0,1\}^n \to \{0,1\} is degenerate if it does not depend on at least one input variable, meaning there exists some i \in \{1,\dots,n\} such that f(x) remains unchanged when x_i is flipped while keeping other coordinates fixed. Conversely, a variable x_i is essential if flipping it can change the function's output for some input, i.e., there exist x, y differing only in the i-th coordinate with f(x) \neq f(y). Non-degenerate functions, which depend on all n variables, are thus essential in every coordinate. Self-duality is a symmetry property relating a function to its complement under input negation. A Boolean function f: \{0,1\}^n \to \{0,1\} is self-dual if f(\neg x) = \neg f(x) for all x \in \{0,1\}^n, where \neg x denotes the vector with each bit flipped and \neg f(x) = 1 - f(x). This condition implies that the function and its dual (obtained by interchanging 0s and 1s in the truth table) are equivalent up to input complementation. Additional functional properties include the algebraic degree and . The algebraic degree of f is the maximum size of any monomial with nonzero coefficient in its (ANF), a unique multivariate representation over \mathrm{GF}(2). A function is if the preimage of 1 under f has exactly half the size of the , i.e., |f^{-1}(1)| = 2^{n-1}, ensuring an equal number of inputs mapping to 0 and 1.

Symmetry and Invariants

A Boolean function f: \{0,1\}^n \to \{0,1\} is symmetric if its output value depends solely on the of the input vector, that is, f(x) = g(|x|) for some g: \{0,1,\dots,n\} \to \{0,1\}, where |x| denotes the number of 1's in x. This property implies invariance under any of the input variables, as permuting variables preserves the Hamming weight. Symmetric functions form a subclass of all Boolean functions, with exactly $2^{n+1} such functions on n variables, since g can assign arbitrary values to each of the n+1 possible weights. Examples of symmetric Boolean functions include threshold functions, such as the , which outputs 1 if the exceeds n/2 (for odd n) and is widely used in voting schemes and models. Another example is the , which outputs the modulo 2. Symmetric functions can be expressed in (ANF) as a over of elementary symmetric polynomials: f(x) = \sum_{k=0}^n a_k \sigma_k(x), where \sigma_k(x) = \sum_{1 \leq i_1 < \cdots < i_k \leq n} x_{i_1} \cdots x_{i_k} is the sum of all products of k distinct variables, and the a_k \in \{0,1\} are coefficients. These elementary symmetric functions \sigma_k serve as a basis for the of symmetric functions, with \sigma_k itself being symmetric of degree k. Invariants under variable permutations include the Hamming weight of the function, defined as the number of inputs mapping to 1, which remains unchanged since permutations merely reorder the truth table entries without altering the count of 1's. Another invariant is the autocorrelation spectrum, the multiset of autocorrelation values C_f(\omega) = \sum_{x \in \{0,1\}^n} (-1)^{f(x) + f(x \oplus \omega)} for all \omega \in \{0,1\}^n, which is preserved under affine equivalences including variable permutations, as these transformations maintain the pairwise differences in function values. For symmetric functions specifically, the weight can be computed efficiently from the value vector specifying outputs per Hamming weight, and the autocorrelation further exhibits symmetry in its distribution. The symmetric group S_n acts on the set of Boolean functions by permuting the variables: for \pi \in S_n and f \in \{0,1\}^{\{0,1\}^n}, define (\pi \cdot f)(x) = f(\pi^{-1}(x)), ensuring the action preserves function composition. The invariance group (or stabilizer) S(f) = \{\pi \in S_n \mid \pi \cdot f = f\} consists of all permutations leaving f unchanged, with symmetric functions having S(f) = S_n. By the orbit-stabilizer theorem, the size of the orbit of f under this action—the number of distinct functions obtainable by permuting variables—is |S_n| / |S(f)| = n! / |S(f)|, which equals 1 for symmetric functions and grows large for functions with trivial stabilizers. Asymptotically, almost all Boolean functions have trivial invariance groups S(f) = \{e\}, implying their orbits have size n!. Classification of Boolean functions up to permutation equivalence relies on Pólya enumeration, which uses the cycle index of S_n to count the number of orbits under the group action, thereby enumerating inequivalent functions modulo variable relabeling. For symmetric functions, this simplifies to the direct count of $2^{n+1}, but Pólya theory more broadly characterizes possible invariance groups S(f) via fixed-point enumerations over conjugacy classes of permutations. This approach has been applied to determine that only specific permutation groups (e.g., cyclic or certain wreath products) arise as S(f) for some f.

Analysis

Complexity Measures

Boolean functions are evaluated in terms of their through various measures that quantify the resources required to represent or compute them. These measures include circuit size and depth, depth, formula size, and the minimum number of literals in disjunctive or conjunctive normal forms. Such metrics provide insights into the inherent difficulty of synthesizing efficient representations for given functions and highlight the challenges in minimization problems. Circuit complexity assesses the efficiency of implementing a Boolean function f: \{0,1\}^n \to \{0,1\} using Boolean circuits composed of gates such as AND, OR, and NOT. The size of a circuit is the number of gates it contains, while the depth is the length of the longest path from an input to the output. Smaller size and depth indicate more efficient implementations suitable for hardware design. Claude Shannon demonstrated that almost all Boolean functions require circuits of size at least \Omega(2^n / n), using a counting argument that compares the number of possible functions ($2^{2^n}) to the number of circuits of size s (roughly O(s^{2s})), showing that for s = o(2^n / n), most functions cannot be realized. Minimizing the circuit size for a given function is computationally challenging; for multi-output Boolean functions, determining the minimum circuit size is NP-hard. Decision tree complexity measures the minimum depth of a binary decision tree that computes the function by querying input bits. This depth, denoted D(f), represents the worst-case number of queries needed in a deterministic adaptive algorithm to evaluate f. A related notion is the sensitivity s(f), defined as the maximum, over all inputs x, of the number of single-bit flips from x that change f(x); sensitivity provides a lower bound on decision tree complexity since each query can reduce uncertainty by at most a factor related to the sensitive bits. For example, the parity function, which outputs 1 if the number of 1s in the input is odd, has decision tree complexity n, as every input bit must be queried in the worst case to determine the parity. Formula size evaluates tree-like circuits without gate sharing, where each gate has fan-out at most 1. The size L(f) is the number of leaves (input literals) in the minimal such formula computing f. Shannon's counting argument extends to formulas, yielding an average formula size of \Omega(2^n / n) for random Boolean functions, as the number of formulas of size s is at most O(2^{s \log s}), insufficient to cover most functions for smaller s. The literal count in (DNF) or (CNF) measures the minimum number of literals across all terms (or clauses) in a representation of f. For DNF, this is the smallest number of literals in any DNF equivalent to f, often prioritizing irredundant forms to minimize hardware costs. Computing the minimum literal count for DNF is NP-complete, as shown by from known hard problems like Circuit-SAT. Similar hardness holds for CNF minimization. These measures are foundational for understanding trade-offs in normal form representations.

Spectral Analysis

Spectral analysis of Boolean functions employs the Walsh-Hadamard transform, also known as the Fourier-Walsh transform, to decompose a function into its frequency components over the hypercube. For a Boolean function f: \{0,1\}^n \to \{0,1\}, the transform is defined by considering the real-valued extension F(x) = (-1)^{f(x)}, and the Walsh coefficients are given by W_f(u) = \sum_{x \in \{0,1\}^n} (-1)^{u \cdot x + f(x)}, \quad u \in \{0,1\}^n, where u \cdot x denotes the dot product modulo 2. The normalized coefficients, often denoted \hat{c}_u or simply the spectrum values, are \hat{c}_u = 2^{-n} W_f(u). These coefficients represent the correlation between f and the linear functions \chi_u(x) = (-1)^{u \cdot x}, providing a frequency-domain view of the function's structure. The Walsh spectrum of f is the set \{ \hat{c}_u \mid u \in \{0,1\}^n \}, which fully characterizes the via the inverse transform F(x) = \sum_u \hat{c}_u (-1)^{u \cdot x}, from which f(x) = \frac{1 - F(x)}{2}. A key property is , which states that \sum_u W_f(u)^2 = 2^{2n}, or equivalently \sum_u \hat{c}_u^2 = 1 for the normalized . For balanced functions (where the number of 1's is $2^{n-1}), the variance of F is 1, aligning with the 's energy distribution. This identity underscores the unit-norm preservation in the transform, analogous to classical . The algebraic degree of f, defined as the highest degree of monomials in its algebraic normal form, can be determined from the support of the spectrum: it equals the maximum Hamming weight |u| over all u with \hat{c}_u \neq 0. This follows because each character \chi_u corresponds to a monomial of degree |u|, and the expansion's highest-degree term dictates the overall degree. Nonlinearity, measuring the minimum Hamming distance from f to any affine function, is computed as N_f = 2^{n-1} - \frac{1}{2} \max_u |W_f(u)|. High nonlinearity requires the spectrum to be flat, with small maximum absolute values away from the origin. Autocorrelation provides insight into linear approximations under shifts, defined as C_v = 2^{-n} \sum_x (-1)^{f(x) + f(x \oplus v)} for v \in \{0,1\}^n. It measures the of the derivative f(x \oplus v) + f(x). The function relates to the via the inverse Walsh transform of the squared coefficients: C_v = \sum_u \hat{c}_u^2 (-1)^{u \cdot v}. This connection, akin to the Wiener-Khinchin theorem, links time-domain shifts to frequency-domain magnitudes, enabling analysis of propagation characteristics. Low autocorrelation magnitudes indicate resilience to linear attacks. As an example, consider the 2-variable AND function f(x_1, x_2) = x_1 x_2. Its truth values are f(00)=0, f(01)=0, f(10)=0, f(11)=1, so F(x) = (1,1,1,-1). The unnormalized Walsh coefficients are W_f(00)=2, W_f(01)=2, W_f(10)=2, W_f(11)=-2. The normalized spectrum is \hat{c}_{(00)}=0.5, \hat{c}_{(01)}=0.5, \hat{c}_{(10)}=0.5, \hat{c}_{(11)}=-0.5, satisfying \sum \hat{c}_u^2 = 1. The maximum |W_f(u)|=2 yields nonlinearity N_f = 2 - 1 = 1, and the support spans weights up to 2, matching the degree. Autocorrelations are C_0=1, C_{(01)}=0, C_{(10)}=0, C_{(11)}=0, reflecting the function's structure.

Cryptographic Properties

Boolean functions play a pivotal role in such as S-boxes and combining functions in stream ciphers, where they must exhibit properties that resist linear, , , and algebraic attacks. These properties ensure that the functions deviate sufficiently from linear behavior and maintain statistical independence under various input manipulations. Key cryptographic criteria include nonlinearity, correlation immunity, algebraic immunity, propagation characteristics, and characteristics, each addressing specific vulnerability classes.

Nonlinearity

The nonlinearity of an n-variable Boolean function f measures its distance from the set of all affine functions and is defined as the minimum Hamming weight of f \oplus l, where l ranges over all affine functions; equivalently, N_f = 2^{n-1} - 2^{n-1} \max_{u \in \mathbb{F}_2^n} |\hat{f}(u)|, with \hat{f}(u) denoting the normalized Walsh-Hadamard transform of f. This property quantifies resistance to , as high nonlinearity limits the accuracy of linear approximations. The maximum possible nonlinearity for n variables is $2^{n-1} - 2^{n/2 - 1}, achieved only when n is even by bent functions, which have flat Walsh spectra with all nonzero coefficients equal to \pm 2^{n/2}. Bent functions, first characterized for their maximal nonlinearity, are particularly valued in designing components like S-boxes, though constructing them with additional properties like high algebraic degree remains challenging.

Correlation Immunity

Correlation immunity assesses a function's independence from linear combinations of input bits, crucial for resisting correlation attacks on nonlinear combiners in stream ciphers. A Boolean function f is of correlation immunity order if its output is statistically uncorrelated with any linear function depending on at most input variables, meaning the Walsh transform satisfies \hat{f}(u) = 0 for all u with at most . Siegenthaler established that the maximum order for an n-variable balanced function satisfies + \deg(f) \leq n, linking it to algebraic degree and limiting high-immunity constructions. Functions with \geq 1 are called correlation-immune, and higher orders enhance security against partitioning attacks, though they often trade off with nonlinearity.

Algebraic Immunity

Algebraic immunity evaluates resistance to algebraic attacks, which solve systems of multivariate equations over \mathbb{F}_2 derived from the function and observed outputs. For a Boolean function f, an is a nonzero g such that f \cdot g = 0 or (1 \oplus f) \cdot g = 0 (mod 2), and the algebraic immunity AI(f) is the minimum degree over all such annihilators. Courtois and Meier showed that random n-variable functions typically have AI(f) \approx 0.22n, but cryptographic functions require AI(f) \geq \lceil n/2 \rceil to counter fast algebraic attacks, which reduce equation degrees using additional relations. Constructions achieving optimal immunity, such as those based on Niho exponents, balance this with other properties like balancedness.

Propagation Characteristics

Propagation characteristics describe how input differences propagate through a function, essential for resisting differential attacks on block ciphers. For vectorial Boolean functions (S-boxes) from \mathbb{F}_2^n to \mathbb{F}_2^m, the difference distribution table (DDT) tabulates, for each nonzero input difference \alpha, the distribution of output differences \beta = f(x \oplus \alpha) \oplus f(x), with entries \Delta_f(\alpha, \beta) counting solutions x. Typically for n=8 in AES-like designs, low maximum entries in the DDT (e.g., 4 for optimal APN S-boxes when m=n) indicate uniform propagation, minimizing differential probabilities bounded by \max_{\alpha \neq 0} \max_{\beta} \Delta_f(\alpha, \beta) / 2^n. The strict avalanche criterion requires exactly half the outputs to change for any single input bit flip, a first-order propagation property.

Linear Approximation Table

The linear approximation table (LAT) captures correlations between linear combinations of inputs and outputs, central to . For a vectorial Boolean function f, the LAT entry LAT_f(a, b) for input mask a and output mask b is $2 \cdot \#\{x \mid \langle x, a \rangle = \langle f(x), b \rangle \} - 2^n, where \langle \cdot, \cdot \rangle is the mod 2; the absolute correlation is |LAT_f(a, b)| / 2^n. High-impact approximations occur when \max_{a \neq 0, b} | \hat{c}_{a,b} | is small, with \hat{c}_{a,b} the coefficient, ensuring biases below 2^{-n/2} for security. These tables, computed via fast Walsh transforms, guide S-box design to avoid exploitable linear trails. The Walsh transform from spectral analysis computes component function correlations underlying the LAT.

Advanced Representations

Polynomial Forms

Boolean functions, which map from \{0,1\}^n to \{0,1\}, can be represented as multilinear over the real numbers, providing a real-valued extension that agrees with the function on the Boolean hypercube. This form is given by f(\mathbf{x}) = \sum_{S \subseteq } a_S \prod_{i \in S} x_i, where each x_i \in \{0,1\} and the polynomial is linear in each variable, ensuring no higher powers appear since x_i^2 = x_i on the domain. This representation contrasts with the over , which uses modulo-2 arithmetic and binary coefficients. The coefficients a_S in this expansion are computed using the on the Boolean lattice: a_S = \sum_{T \subseteq S} (-1)^{|S| - |T|} f(T), where f(T) denotes the value of f at the input with 1s exactly on the coordinates in T and 0s elsewhere. This inclusion-exclusion-based formula arises from inverting the zeta transform of the function values over the subset poset. The degree of the polynomial is defined as the largest |S| such that a_S \neq 0. While related to the degree over —which is the maximum |S| in the expansion—the real multilinear degree can be strictly larger, as the real coefficients must ensure exact 0/1 outputs without modular reduction. Every Boolean function admits a unique such multilinear representation of degree at most n, due to the of the monomials \prod_{i \in S} x_i when evaluated on \{0,1\}^n. For example, the two-variable XOR function f(x,y) = x \oplus y, which has degree 1 as x + y over GF(2), has real x + y - 2xy of degree 2. This satisfies f(0,0) = 0, f(0,1) = 1, f(1,0) = 1, and f(1,1) = 0.

Decision Diagrams

Binary decision diagrams (BDDs) are directed acyclic graphs used to represent and manipulate functions efficiently. Each non-terminal node in a BDD is labeled with a variable and has two outgoing edges: a low edge (0-child) and a high edge (1-child), leading to sub-diagrams representing the cofactors of the function. The graph terminates at two distinct nodes: one for the constant 0 and one for the constant 1, ensuring a canonical structure for evaluation by traversing from the root based on variable assignments. BDDs are constructed recursively via the Shannon expansion, which decomposes a Boolean function f with respect to a variable x_i as: f(\mathbf{x}) = \bar{x_i} \cdot f(0, x_{-i}) \vee x_i \cdot f(1, x_{-i}), where x_{-i} denotes the variables excluding x_i, and the cofactors f(0, x_{-i}) and f(1, x_{-i}) are represented by the low and high children, respectively. To ensure compactness, reduction rules are applied during construction: identical sub-diagrams are shared (isomorphism elimination), and nodes with both children pointing to the same sub-diagram are removed (redundancy elimination). These rules prevent exponential growth in the graph size compared to the full decision tree, which has $2^n leaves for n variables. A key variant is the reduced ordered binary decision diagram (ROBDD), which imposes a fixed linear ordering on the variables and applies the reduction rules throughout. ROBDDs provide a unique representation for a given under a specific , enabling straightforward checking by comparing structures. However, the choice of variable ordering critically affects the ROBDD size; a poor can result in (e.g., O(2^n) nodes), while an optimal may yield size for certain . BDD size serves as a measure for , correlating with computational hardness in tasks. Common operations on BDDs include (substituting a variable with another function or constant), (eliminating variables by OR-ing cofactors), and (AND-ing cofactors). These operations are performed via graph manipulations, such as recursive traversal and application of reduction rules, with polynomial in the input BDD sizes. checking is particularly efficient: a Boolean function is satisfiable if its ROBDD is not the constant 0 terminal, verifiable in O(|G|) time, where |G| is the number of nodes. For example, the on three variables x_1, x_2, x_3, which outputs 1 if at least two inputs are 1, has a compact ROBDD with variable order x_1 < x_2 < x_3: the root node for x_1 branches to an x_2 node A on the low edge and to an x_2 node B on the high edge. Node A branches to the 0-terminal on its low edge and to an x_3 node (low to 0, high to 1) on its high edge. Node B branches to the x_3 node on its low edge and directly to the 1-terminal on its high edge. This structure shares the x_3 subgraph and has four non-terminal nodes, illustrating the sharing of subgraphs for symmetric cofactors.

Applications

Logic Design

Boolean functions form the foundation of digital circuit design, enabling the representation and realization of logical operations in hardware. In his seminal 1938 master's thesis, demonstrated how could be applied to analyze and synthesize switching circuits using relays, establishing the theoretical groundwork for modern logic design by mapping electrical contacts to Boolean variables and operations. This work bridged mathematics and , showing that any Boolean function could be implemented as a network of switches, which directly influenced the development of electronic digital computers. A key aspect of logic design involves minimizing Boolean functions to reduce the number of gates and interconnections in circuits, thereby improving efficiency and cost. Disjunctive normal form (DNF) and conjunctive normal form (CNF) provide canonical representations that can be directly translated into sum-of-products or product-of-sums circuits, respectively. For small numbers of variables (up to six), the Karnaugh map offers a visual method for minimizing DNF expressions by grouping adjacent 1's in a toroidal grid that exploits the adjacency of minterms differing by one bit, allowing designers to identify prime implicants without exhaustive enumeration. For more complex functions or exact minimization, the Quine-McCluskey algorithm provides a tabular systematic approach, first outlined by Willard V. Quine in 1952 for simplifying truth functions by generating prime implicants and selecting a minimal cover. Edward J. McCluskey extended this in 1956 into a complete procedure that combines implicants iteratively based on the number of 1's in their binary representations and resolves essential prime implicants to yield an optimal sum-of-products expression, which is crucial for logic synthesis tools that automate the transformation from high-level specifications to gate-level netlists. These minimization techniques ensure circuits are compact while preserving functionality. In practical implementations, timing issues such as hazards can cause —temporary incorrect outputs due to signal propagation delays. Static hazards occur when a single input change should keep the output steady, but delays create a momentary (static-1 for a falling spike or static-0 for a rising one), often arising from uncovered transitions in the where adjacent implicants fail to overlap. Dynamic hazards manifest as multiple (three or more) output transitions during a single input change, typically in circuits with redundant paths; they are mitigated by ensuring hazard-free covers through consensus terms or careful gate sizing. Identifying covered versus uncovered transitions during minimization helps eliminate these issues, ensuring reliable operation. To realize minimized Boolean functions in hardware, programmable logic arrays (PLAs) and (PALs) provide flexible structures for sum-of-products implementations. PLAs, introduced in the early 1970s by , feature a programmable AND plane followed by a programmable OR plane, allowing any Boolean function to be configured by fusing links to define product terms and their summation. PALs, developed in by Monolithic Memories Inc., streamline this by fixing the OR plane while keeping the AND plane programmable, reducing complexity and cost for smaller circuits with up to tens of inputs, and enabling through fusible links. These devices revolutionized logic design by allowing field-programmable customization without custom masks, supporting efficient realization of multi-output functions.

Cryptography

Boolean functions serve as fundamental components in symmetric , providing nonlinearity essential for resisting various attacks in block ciphers, stream ciphers, and hash functions. In block ciphers like and , substitution boxes (S-boxes) are bijective vectorial Boolean functions that map input bits to output bits, introducing to obscure the relationship between and ciphertext. For instance, the S-box is an 8-bit bijective function designed with specific cryptographic criteria, including a maximum differential uniformity of 4, which limits the probability of differential characteristics to 1/256, ensuring resistance to differential cryptanalysis. Similarly, the S-boxes consist of eight nonlinear 6-to-4-bit components that provide the cipher's primary source of nonlinearity, constructed to balance effects and resist early cryptanalytic attacks. In stream ciphers, Boolean functions are employed in filter generators and combiner generators to produce pseudorandom keystreams from linear feedback shift registers (LFSRs). A filter generator applies a nonlinear Boolean function directly to the state of a single LFSR to generate output bits, where high nonlinearity and immunity are required to prevent attacks. Combiner generators, on the other hand, use a multi-output Boolean function to combine bits from multiple LFSRs, enhancing security against algebraic and linear attacks by ensuring the output decorrelates from individual register states. These designs leverage properties like high algebraic degree and low to maintain unpredictability. Hash functions utilize functions in their compression rounds to achieve one-wayness and , often incorporating bent or highly nonlinear functions to maximize and . Bent functions, which achieve the maximum possible nonlinearity of $2^{n-1} for even n-variable functions, are particularly valued for their flat Walsh spectrum, making them ideal for resisting linear approximations in hash iterations. For example, the hash function employs five distinct 7-variable functions across its rounds, selected for properties like and strict criterion to ensure sensitivity to input changes. Construction methods, such as concatenating bent functions from smaller dimensions, allow designers to build larger secure S-boxes or filter functions while preserving optimal nonlinearity. Cryptanalytic attacks on these systems often exploit weaknesses in Boolean function , such as low nonlinearity or high correlation. Differential cryptanalysis, introduced by Biham and Shamir, analyzes propagation probabilities through S-boxes, targeting functions with high differential uniformity to find high-probability characteristics that distinguish the cipher from random. Linear , developed by Matsui, approximates the cipher as a over , succeeding when Boolean functions exhibit non-zero correlations between input and output masks, as demonstrated in attacks on reduced-round . These attacks underscore the need for Boolean functions with balanced cryptographic , such as those referenced in the "Cryptographic Properties" section, to ensure robust security in practical implementations.

Theoretical Computer Science

Boolean functions are central to , particularly in the study of the problem (SAT). SAT asks whether there exists an assignment of truth values to the variables of a given that makes the true. When the is expressed in (CNF), consisting of a of where each is a disjunction of literals, the problem is NP-complete. This was established by the Cook-Levin theorem, which reduces any problem in to CNF-SAT via a that simulates the nondeterministic as a instance. Query provides a fundamental measure of the computational resources needed to evaluate functions in black-box models. In the deterministic query model, the D(f) of a function f: {0,1}^n → {0,1} is the minimum number of input queries required in the worst case, equivalent to the height of the computing f. The randomized query R(f) extends this to probabilistic algorithms, defined as the minimum number of queries needed to compute f with error probability at most 1/3 on any input. Here, the of a measures its average impact on the acceptance probability of the randomized algorithm, linking query bounds to notions like and block sensitivity. These models reveal separations, such as quadratic gaps between deterministic and randomized complexities for certain functions. In learning theory, Boolean functions are analyzed through the Probably Approximately Correct (PAC) framework, where an algorithm must output a hypothesis that approximates the target function with high probability over random examples. Disjunctive normal form (DNF) representations, consisting of a disjunction of conjunctions of literals, are PAC-learnable under the uniform distribution using membership queries, as shown by an efficient algorithm that identifies relevant terms via Fourier analysis and consistency checks. Occam's razor bounds formalize the intuition that simple hypotheses suffice: if a concept class has polynomial VC dimension, any consistent hypothesis from a polynomial-sized subclass achieves low generalization error with high probability, bounding the sample complexity by O((VC(H) + log(1/δ))/ε). Property testing examines how few queries suffice to distinguish Boolean functions with a desired property from those far from it. For —functions satisfying f(x ⊕ y) = f(x) ⊕ f(y) over GF(2)—the Blum-Luby-Rubinfeld tester queries f at random points x, y, z and checks if f(x) ⊕ f(y) ⊕ f(z) = f(x ⊕ y ⊕ z), accepting linear functions with probability 1 and rejecting ε-far functions with constant probability using O(1/ε) queries. Monotonicity testing, where f(x) ≤ f(y) whenever x ≤ y componentwise, uses algorithms that query ordered pairs and detect violations; an improved tester achieves Õ(√n / ε^2) queries for functions over {0,1}^n, rejecting ε-far non-monotone functions with high probability. These results highlight efficient query-efficient verification without full evaluation. Boolean functions underpin circuit lower bounds, revealing inherent computational hardness. The , outputting 1 if the number of 1s in the input is odd, requires Ω(n) size in circuits, as gates (AND, OR) cannot negate inputs to capture the alternating nature of , necessitating linear growth to approximate or embed such behavior in restricted models. This connects to broader results, like Razborov's superpolynomial lower bounds for circuits computing the function, using approximation methods to show that small circuits fail on specific inputs.