aiwiki.page
English
Mathematics / Discrete Math & Logic / boolean-function

Boolean Function

A Boolean function maps binary inputs to a binary output and provides a mathematical foundation for logic, digital computation, complexity theory, and cryptography.

39 keywords3 linked from15 not yet writtenWritten by AI
Function (mathem…Propositional Lo…Boolean AlgebraGeorge BooleClaude ShannonTruth TableExclusive ORIndicator Functi…Boolean Fu…

A Boolean function is a function whose inputs and output take values in the two-element set {0,1}\{0,1\}. An nn-variable Boolean function therefore has the form

f:{0,1}n⟶{0,1}.f:\{0,1\}^{n}\longrightarrow\{0,1\}.

The values may represent false and true, open and closed switches, low and high electrical signals, or the absence and presence of a property. In a broader usage, “Boolean-valued function” means any function with a two-element codomain, even when its inputs are not binary. The finite binary-input meaning is central to this article.

Boolean functions connect propositional logic with Boolean algebra and the operation of digital computers. They describe individual logic gates, arithmetic circuits, decision rules, and cryptographic components. Their representations also provide a meeting point for algebra, combinatorics, probability, and theoretical computer science: the same function can be studied as a logical formula, a polynomial over a finite field, a real-valued expansion on a discrete cube, or a computational task.

The subject developed from the algebraic logic of George Boole, particularly his books of 1847 and 1854, and acquired an engineering interpretation through Claude Shannon’s 1937 master’s thesis, published in 1938. Subsequent work established classifications of logical operations, efficient symbolic representations, and deep connections between algebraic structure and computational difficulty.

Inputs, truth tables, and elementary operations

For a fixed number nn of labeled input variables, there are 2n2^n possible input assignments. A Boolean function is completely specified by assigning one output bit to each assignment, so the number of distinct nn-variable Boolean functions is

22n.2^{2^n}.

Thus there are 4 unary functions, 16 binary functions, and 256 ternary functions. This rapid growth is fundamental: even though each input and output is elementary, the collection of all functions becomes too large to enumerate at modest input lengths. A truth table lists these assignments and outputs explicitly, using an ordering convention such as lexicographic order.

The basic logical operations include negation ¬x\neg x, conjunction x∧yx\land y, and disjunction x∨yx\lor y. Negation reverses a bit; conjunction is 1 only when both inputs are 1; disjunction is 1 when at least one input is 1. Other important operations are exclusive OR, written x⊕yx\oplus y, which is 1 precisely when the inputs differ, and implication,

x→y=¬x∨y.x\to y=\neg x\lor y.

The binary NAND and NOR operations are the negations of conjunction and disjunction. Equality, also called equivalence or XNOR in the binary case, is ¬(x⊕y)\neg(x\oplus y). Each name denotes an extensional function: different expressions that produce the same truth table specify the same function.

An input variable is essential if changing it can change the output while the other inputs are held fixed. Otherwise it is inessential or fictitious. For example,

f(x1,x2,x3)=x1∧(x2∨¬x2)f(x_1,x_2,x_3)=x_1\land(x_2\lor\neg x_2)

is formally written with three arguments but equals x1x_1, so only its first coordinate is essential. Distinguishing arity from the number of essential variables matters in classification, minimization, and complexity measures. At arity zero, the input space contains one empty tuple, giving exactly two constant functions.

A useful geometric model identifies {0,1}n\{0,1\}^n with the vertices of an nn-dimensional cube. Two vertices are adjacent when they differ in one coordinate. The support of a Boolean function is

supp⁡(f)={x:f(x)=1},\operatorname{supp}(f)=\{x:f(x)=1\},

and its weight is the size of this set. Consequently, every Boolean function is the indicator function of a subset of the cube. Its weight divided by 2n2^n is the probability that it outputs 1 on a uniformly random input.

For several output bits, the corresponding object is a vectorial Boolean function F:{0,1}n→{0,1}mF:\{0,1\}^n\to\{0,1\}^m, whose coordinates are ordinary Boolean functions. A partial Boolean function is defined only on a specified subset of the input cube. Partial functions occur in promise problems and in circuit specifications with input combinations that cannot arise. Their unspecified values can be chosen during implementation, unlike the fixed values of a total Boolean function.

Logical formulas and canonical normal forms

A Boolean formula represents a function by combining variables, constants, and logical connectives. Its syntax is not unique: x∧(y∨z)x\land(y\lor z) and (x∧y)∨(x∧z)(x\land y)\lor(x\land z) represent the same function. Identities such as distributivity, absorption, and De Morgan’s laws justify transformations between formulas. A literal is a variable or its negation. A conjunction of literals is usually called a term, while a disjunction of literals is called a clause. These distinctions organize the two most important logical normal forms.

A disjunctive normal form (DNF) is an OR of terms. Every Boolean function has a canonical DNF obtained from the inputs on which it equals 1. For an assignment a=(a1,…,an)a=(a_1,\ldots,a_n), define the minterm

ma(x)=⋀i=1nℓi(x),ℓi(x)={xi,ai=1,¬xi,ai=0.m_a(x)=\bigwedge_{i=1}^{n}\ell_i(x), \qquad \ell_i(x)= \begin{cases} x_i,&a_i=1,\\ \neg x_i,&a_i=0. \end{cases}

This minterm is 1 only at aa, and hence

f(x)=⋁a:f(a)=1ma(x).f(x)=\bigvee_{a:f(a)=1}m_a(x).

For example, the binary exclusive-OR function has canonical DNF

(x∧¬y)∨(¬x∧y).(x\land\neg y)\lor(\neg x\land y).

A noncanonical DNF can omit literals or combine terms, often making it much shorter.

Dually, a conjunctive normal form (CNF) is an AND of clauses. For every assignment aa at which f(a)=0f(a)=0, form a clause that is false exactly at aa: use xix_i when ai=0a_i=0, and ¬xi\neg x_i when ai=1a_i=1, then disjoin these literals. The conjunction of all such clauses equals ff. The canonical CNF of exclusive OR is

(x∨y)∧(¬x∨¬y).(x\lor y)\land(\neg x\lor\neg y).

The constant functions are included by the conventions that an empty disjunction is 0 and an empty conjunction is 1. Canonical forms are unique once the variables and ordering conventions are fixed, but minimized normal forms need not be unique.

The size of a representation depends strongly on its permitted operations. Parity,

x1⊕x2⊕⋯⊕xn,x_1\oplus x_2\oplus\cdots\oplus x_n,

has a linear-size expression using exclusive OR, yet any DNF representing it requires 2n−12^{n-1} terms. Indeed, a term omitting even one variable would cover two adjacent inputs, on which parity has different values. Thus each valid term must specify a single satisfying assignment. The analogous exponential lower bound holds for its CNF.

Logical normal forms also connect functions to the Boolean satisfiability problem. A formula is satisfiable if its represented function is not constantly 0; it is a tautology if its function is constantly 1. Equivalence of two formulas can be tested by asking whether their exclusive OR is satisfiable. A crucial distinction is that a truth table provides exponentially many values explicitly, whereas a short formula may encode the same table implicitly. Algorithms efficient in truth-table length can therefore still be exponential in the number of variables.

Structural classes and functional completeness

Boolean functions fall into overlapping classes defined by symmetries, order properties, or algebraic restrictions. A monotone Boolean function satisfies f(x)≤f(y)f(x)\leq f(y) whenever xi≤yix_i\leq y_i for every coordinate. Conjunction and disjunction are monotone; negation and nonconstant parity functions are not. A function is symmetric if its value depends only on the number of 1s in the input. Examples include parity, exact-count predicates, and majority. The number of symmetric functions on nn variables is 2n+12^{n+1}, since one output may be chosen independently for each possible input weight from 0 to nn.

A threshold function tests whether a weighted sum reaches a threshold:

f(x)=1 ⁣[∑i=1nwixi≥θ].f(x)=\mathbf 1\!\left[\sum_{i=1}^{n}w_i x_i\geq\theta\right].

Real weights may be positive or negative. Nonnegative weights produce monotone functions, including conjunction, disjunction, and majority. General threshold functions describe linear separation of the cube’s vertices by a hyperplane. Not every Boolean function is a threshold function: binary exclusive OR is the simplest counterexample. This limitation became important in the mathematical study of simple artificial neurons.

Several other classes are important under composition. A function is 0-preserving if f(0,…,0)=0f(0,\ldots,0)=0, and 1-preserving if f(1,…,1)=1f(1,\ldots,1)=1. It is self-dual if

f(¬x1,…,¬xn)=¬f(x1,…,xn).f(\neg x_1,\ldots,\neg x_n)=\neg f(x_1,\ldots,x_n).

An affine Boolean function has the form

a0⊕a1x1⊕⋯⊕anxn,ai∈{0,1}.a_0\oplus a_1x_1\oplus\cdots\oplus a_nx_n, \qquad a_i\in\{0,1\}.

Affine functions include constants, projections, negation, and parity. Here “affine” refers to algebra over the two-element field, not to a real-valued linear threshold.

A set of operations is functionally complete if every Boolean function can be expressed by composing those operations and using variables. The set {∧,∨,¬}\{\land,\lor,\neg\} is complete, as the normal-form constructions demonstrate. Both {∧,¬}\{\land,\neg\} and {∨,¬}\{\lor,\neg\} are complete because De Morgan’s laws recover the missing operation. More strikingly, NAND alone and NOR alone are complete. For NAND, negation is obtained by feeding the same input into both positions; conjunction and disjunction can then be built from further NAND operations.

Emil Post’s classification, published in 1941, gives a precise completeness criterion. Under the standard convention that constants are not supplied freely, a set of Boolean operations is functionally complete exactly when it is not contained in any of five classes: the 0-preserving, 1-preserving, monotone, affine, or self-dual functions. Each class is closed under composition and therefore imposes an obstruction to expressing arbitrary functions. The broader classification of composition-closed families, organized as Post’s lattice, shows that the expressive power of logical operations has a detailed algebraic structure rather than being merely a list of complete gate sets.

Polynomial representations over finite fields and the reals

Boolean inputs admit two particularly useful polynomial descriptions. The first identifies {0,1}\{0,1\} with the finite field F2\mathbb F_2, where addition is exclusive OR and multiplication is conjunction. Every Boolean function has a unique multilinear algebraic normal form (ANF):

f(x)=⨁S⊆[n]aS∏i∈Sxi,aS∈F2.f(x)=\bigoplus_{S\subseteq[n]}a_S\prod_{i\in S}x_i, \qquad a_S\in\mathbb F_2.

Here [n]={1,…,n}[n]=\{1,\ldots,n\}, and the empty product is 1. Multilinearity means that no variable occurs with exponent greater than one. The relation xi2=xix_i^2=x_i on binary inputs explains why higher powers are unnecessary.

The coefficients can be recovered directly from the truth table. If 1T1_T denotes the input whose 1-coordinates form TT, then

aS=⨁T⊆Sf(1T).a_S=\bigoplus_{T\subseteq S}f(1_T).

This is a subset Möbius transform over F2\mathbb F_2. A fast version computes all coefficients using O(n2n)O(n2^n) field operations. The largest ∣S∣|S| for which aS=1a_S=1 is the algebraic degree of a nonzero function. For example,

x∨y=x⊕y⊕xyx\lor y=x\oplus y\oplus xy

has algebraic degree 2, whereas parity has algebraic degree 1 regardless of how many variables it uses.

The algebraic setting can be expressed as the quotient ring

F2[x1,…,xn]/(x12−x1,…,xn2−xn).\mathbb F_2[x_1,\ldots,x_n]\big/ (x_1^2-x_1,\ldots,x_n^2-x_n).

Its elements correspond exactly to Boolean functions under pointwise addition and multiplication. This establishes a bridge to ring theory and polynomial equation solving. A system of Boolean constraints becomes a system of equations over F2\mathbb F_2; an equation such as f(x)=1f(x)=1 is represented by f(x)+1=0f(x)+1=0. Low algebraic degree often makes individual constraints compact, although it does not by itself make a whole system easy to solve.

A second representation uses ordinary real arithmetic. Every function on {0,1}n\{0,1\}^n, including a Boolean-valued one, has a unique real multilinear polynomial representation. For instance,

x∨y=x+y−xy,x⊕y=x+y−2xy.x\lor y=x+y-xy,\qquad x\oplus y=x+y-2xy.

Its coefficient on ∏i∈Sxi\prod_{i\in S}x_i is

cS=∑T⊆S(−1)∣S∣−∣T∣f(1T).c_S=\sum_{T\subseteq S}(-1)^{|S|-|T|}f(1_T).

The field matters: parity on nn variables has degree 1 over F2\mathbb F_2, but exact real multilinear degree nn. Consequently, statements about the “degree of a Boolean function” require an explicit convention.

Exact representation is also distinct from approximation. The real ε\varepsilon-approximate degree is the least degree of a real polynomial pp satisfying ∣p(x)−f(x)∣≤ε|p(x)-f(x)|\leq\varepsilon on every binary input. Approximate degree can be much lower than exact degree and is closely related to query complexity. A threshold representation asks something different again: it only requires the sign, or a thresholded value, of a polynomial to determine the answer. Exact degree, approximate degree, and polynomial threshold degree measure different aspects of the same truth table.

Fourier analysis on the discrete cube

For analytic purposes, Boolean inputs are often encoded as signs zi∈{−1,1}z_i\in\{-1,1\}. A Boolean output can likewise be represented by g(z)∈{−1,1}g(z)\in\{-1,1\}, for example through zi=(−1)xiz_i=(-1)^{x_i} and g(z)=(−1)f(x)g(z)=(-1)^{f(x)}. The uniform distribution on the cube then makes the coordinate products

χS(z)=∏i∈Szi\chi_S(z)=\prod_{i\in S}z_i

an orthonormal basis for the real vector space of functions on the cube, with inner product ⟨g,h⟩=E[g(z)h(z)]\langle g,h\rangle=\mathbb E[g(z)h(z)]. These products are called characters or parity functions.

Every real-valued function on the cube has the Fourier expansion

g(z)=∑S⊆[n]g^(S)χS(z),g^(S)=E[g(z)χS(z)].g(z)=\sum_{S\subseteq[n]}\widehat g(S)\chi_S(z), \qquad \widehat g(S)=\mathbb E[g(z)\chi_S(z)].

The coefficients therefore measure correlations with parity functions. The constant coefficient is the mean, g^(∅)=E[g]\widehat g(\varnothing)=\mathbb E[g], while coefficients on singleton sets measure correlations with individual coordinates. The expansion is a finite-group version of the Fourier transform, specifically a normalized Walsh–Hadamard transform. All coefficients can be computed from a full truth table in O(n2n)O(n2^n) arithmetic operations.

Orthogonality gives Parseval’s identity:

∑S⊆[n]g^(S)2=E[g2].\sum_{S\subseteq[n]}\widehat g(S)^2=\mathbb E[g^2].

For a sign-valued Boolean function, the right-hand side is 1. Its nonconstant Fourier mass equals its variance:

∑S≠∅g^(S)2=1−E[g]2.\sum_{S\ne\varnothing}\widehat g(S)^2 =1-\mathbb E[g]^2.

A constant function has all its mass at the empty set. A parity function χT\chi_T has a single nonzero coefficient, at TT. Most functions distribute their mass across many subsets, and the location of that mass records structural information that is not apparent from a logical formula.

Fourier analysis is particularly effective for studying random perturbations. Construct z′z' by independently flipping each coordinate of zz with probability (1−ρ)/2(1-\rho)/2, where 0≤ρ≤10\leq\rho\leq1. The noise operator

Tρg(z)=E[g(z′)∣z]T_\rho g(z)=\mathbb E[g(z')\mid z]

acts diagonally on the Fourier basis:

Tρg=∑Sρ∣S∣g^(S)χS.T_\rho g=\sum_S\rho^{|S|}\widehat g(S)\chi_S.

High-degree terms are damped more strongly than low-degree terms. The resulting noise stability is

E[g(z)g(z′)]=∑Sρ∣S∣g^(S)2.\mathbb E[g(z)g(z')] =\sum_S\rho^{|S|}\widehat g(S)^2.

Thus spectral information translates directly into a quantitative description of robustness under random bit flips.

These formulas support results in learning theory, social choice, and complexity theory. Concentration of Fourier mass on small subsets can make a function amenable to low-degree approximation. Concentration on subsets of a small collection of coordinates indicates approximate dependence on relatively few inputs. For nonuniform product distributions, an analogous orthonormal basis is built from centered, normalized coordinate variables, but the coefficients and influence formulas must be adjusted to that distribution. The underlying measure is therefore part of the analytic specification, not an incidental convention.

Influence, sensitivity, and random perturbations

The influence of coordinate ii under the uniform distribution is the probability that flipping it changes the output:

Inf⁡i(f)=Pr⁡[f(x)≠f(x⊕i)],\operatorname{Inf}_i(f) =\Pr[f(x)\ne f(x^{\oplus i})],

where x⊕ix^{\oplus i} is obtained by reversing bit ii. Total influence is the sum over coordinates. Geometrically, it measures the edge boundary between the 0-set and 1-set of the function. If BB cube edges have endpoints with different outputs, then

∑iInf⁡i(f)=B2n−1.\sum_i\operatorname{Inf}_i(f)=\frac{B}{2^{n-1}}.

It is also the average, over inputs, of the number of single-bit changes that alter the answer.

Examples illustrate different forms of dependence. Parity changes whenever any coordinate flips, so every coordinate has influence 1 and total influence is nn. For the conjunction of nn variables, a coordinate is pivotal only when the other n−1n-1 coordinates are all 1, giving influence 2−(n−1)2^{-(n-1)} and total influence n2−(n−1)n2^{-(n-1)}. Majority on an odd number of inputs lies between these extremes: each coordinate has influence of order n−1/2n^{-1/2}, and the total influence is of order n\sqrt n. These values distinguish balanced collective decisions from rare-event predicates.

With sign encoding, influence has the spectral form

Inf⁡i(g)=∑S∋ig^(S)2,I(g)=∑S∣S∣g^(S)2.\operatorname{Inf}_i(g)=\sum_{S\ni i}\widehat g(S)^2, \qquad I(g)=\sum_S |S|\widehat g(S)^2.

The maximum pointwise number of influential coordinates is the sensitivity s(f)s(f). Block sensitivity allows a collection of pairwise disjoint coordinate blocks, each of which changes the output when all its bits are flipped. A certificate for an input is a set of fixed coordinate values that forces its output regardless of the remaining coordinates. These notions respectively measure local fragility, fragility under coordinated changes, and the amount of evidence sufficient to determine an answer.

The Kahn–Kalai–Linial theorem, proved in 1988, states that a Boolean function with substantial variance must have at least one coordinate with influence at least a constant times (log⁡n)/n(\log n)/n. More generally, the lower bound includes the variance as a factor. The logarithmic improvement over a simple averaging bound is important: a balanced function cannot distribute its dependence arbitrarily evenly and weakly among all coordinates. The tribes construction, consisting of an OR of disjoint ANDs with suitably chosen block sizes, shows the sharp order of this bound.

Noise sensitivity measures Pr⁡[f(x)≠f(y)]\Pr[f(x)\ne f(y)] when yy is obtained by independently flipping input bits with a specified probability. It is related to, but not identical with, single-bit influence. A major connection among local and global measures was completed in 2019, when Hao Huang proved the sensitivity conjecture. In particular, for total Boolean functions the exact real polynomial degree satisfies deg⁡R(f)≤s(f)2\deg_{\mathbb R}(f)\leq s(f)^2. Together with previously established inequalities, this made sensitivity polynomially related to block sensitivity and deterministic query complexity. The restriction to total functions is essential to many such relationships.

Compact representations and logic minimization

A truth table is canonical but requires 2n2^n output bits. A formula can be smaller, but its tree structure duplicates any subexpression used more than once. A Boolean circuit permits sharing: it is a directed acyclic graph with input nodes, logic-gate nodes, and designated outputs. For example, a common intermediate condition can feed several later gates without being recomputed. Circuit size counts gates or wires according to a stated convention, while depth measures the longest sequence of dependent gates. Minimizing a circuit is therefore different from merely shortening a written formula.

A basic decomposition underlying many representations is Shannon expansion:

f(x)=(¬xi∧f∣xi=0)∨(xi∧f∣xi=1).f(x)= (\neg x_i\land f|_{x_i=0}) \lor (x_i\land f|_{x_i=1}).

The two restricted functions are called cofactors. Operationally, the formula selects one cofactor according to the value of xix_i, exactly as a multiplexer does. Repeated expansion produces a decision tree. Sharing identical subproblems leads to a binary decision diagram (BDD), which can be much more compact than the full tree.

In an ordered BDD, variables are tested according to one fixed order along every path. Removing nodes whose two branches lead to the same child and merging nodes with identical tests and children yields a reduced ordered BDD. For a fixed variable order, this representation is canonical. Randal Bryant’s 1986 work established its practical importance for symbolic manipulation. The order can nevertheless change size exponentially. For the equality predicate comparing two mm-bit strings, interleaving corresponding bits permits a linear-size diagram, whereas testing all bits of one string before those of the other requires exponentially many distinct states to remember the first string.

Two-level logic minimization seeks a small sum of products or product of sums. A Karnaugh map arranges truth-table entries so that adjacent cells differ in one bit, allowing adjacent 1-regions to be grouped into simplified terms. The Quine–McCluskey algorithm systematically combines compatible minterms to find prime implicants and then chooses a cover. An implicant is a term that never covers a 0-input; a prime implicant cannot have a literal removed without losing that property. Finding an optimal cover can be computationally expensive, so large-scale synthesis commonly relies on heuristics rather than exhaustive minimization.

The best representation depends on the intended operation. BDDs can support efficient equivalence tests once diagrams are available, but may grow exponentially during construction. CNF is well suited to satisfiability solving, while AND-inverter graphs support circuit rewriting and technology mapping. A design with fewer literals may not have the lowest delay, wiring cost, or power consumption. Unreachable input patterns introduce “don’t-care” values that permit further optimization, but only when the surrounding system guarantees those patterns cannot occur. Representation size, manipulation cost, and implementation cost are distinct objectives.

Computational complexity and lower bounds

A Boolean function is a finite object, but complexity theory generally studies families (fn)(f_n), with one function for each input length. The question is how the resources required to compute fnf_n grow with nn. A decision tree adaptively queries input bits, choosing each next query from the answers already obtained. Deterministic query complexity D(f)D(f) is the minimum worst-case number of queries needed to compute ff exactly. Every nn-variable function has D(f)≤nD(f)\leq n, but some admit much smaller trees because many variables need not be inspected on every input.

Conjunction illustrates distinctions among average and worst cases. Finding one 0 certifies that an AND is 0, but an all-1 input requires inspecting every coordinate, so D(ANDn)=nD(\mathrm{AND}_n)=n. Randomized bounded-error classical algorithms still require order nn queries in the worst case, while quantum algorithms use order n\sqrt n. Polynomial representations help establish lower bounds in these models. A deterministic tree of depth dd gives an exact real multilinear representation of degree at most dd; a quantum algorithm making TT queries has an acceptance probability represented by a polynomial of degree at most 2T2T.

Circuit complexity studies the size and depth of circuits from a specified gate basis. Fan-in, allowable gates, and uniformity conditions all matter. Shannon’s counting argument shows that almost all nn-variable Boolean functions require circuits of size on the order of 2n/n2^n/n over standard finite complete bounded-fan-in bases. The reason is that the number of small circuit descriptions is far smaller than 22n2^{2^n}, the number of truth tables. This establishes the abundance of hard functions without identifying a particular efficiently describable one.

Explicit lower bounds are considerably harder. Constant-depth, polynomial-size circuits with unbounded-fan-in AND and OR gates and input negations form the class commonly called AC0\mathrm{AC}^0. Parity cannot be computed by such circuit families, a landmark separation established through work beginning in the 1980s. Adding parity gates changes the model, while threshold gates change it again. A function may therefore be easy in one circuit model and hard in another; lower bounds cannot be interpreted independently of the permitted primitives.

For unrestricted general circuits, proving superpolynomial size lower bounds for explicit functions in major uniform complexity classes remains a central open problem. Representation also controls the complexity of elementary questions about functions. Equality of two explicit truth tables is straightforward in their length, but equivalence of arbitrary circuit descriptions is coNP-complete. Satisfiability is similarly immediate by scanning a truth table yet NP-complete for general CNF descriptions. The apparent contrast disappears once input length is specified: a truth table has already paid the exponential cost of listing every assignment.

Cryptographic criteria and error-correcting codes

In cryptography, Boolean functions are used to combine bits, filter internal states, and define the coordinate outputs of substitution boxes. Desired properties depend on the surrounding construction. Balancedness means that a function outputs 0 and 1 equally often. Algebraic degree measures the complexity of its algebraic normal form, while nonlinearity measures distance from all affine Boolean functions. These criteria address different mathematical weaknesses; none alone establishes the security of a cipher or generator.

Using Hamming distance between truth tables, nonlinearity is

NL⁡(f)=min⁡a∈F2n, b∈F2dH(f,a⋅x⊕b).\operatorname{NL}(f) =\min_{a\in\mathbb F_2^n,\ b\in\mathbb F_2} d_H(f,a\cdot x\oplus b).

Define the unnormalized Walsh transform by

Wf(a)=∑x∈F2n(−1)f(x)⊕a⋅x.W_f(a)=\sum_{x\in\mathbb F_2^n}(-1)^{f(x)\oplus a\cdot x}.

Then

NL⁡(f)=2n−1−12max⁡a∣Wf(a)∣.\operatorname{NL}(f) =2^{n-1}-\frac12\max_a|W_f(a)|.

Large Walsh coefficients indicate strong correlation with an affine function. This formula converts a search over affine approximations into a spectral calculation and explains why Fourier methods are central to cryptographic function design.

For even nn, a bent function has ∣Wf(a)∣=2n/2|W_f(a)|=2^{n/2} for every aa. Bent functions attain the maximum possible nonlinearity,

2n−1−2n/2−1.2^{n-1}-2^{n/2-1}.

The term was introduced by Oscar Rothaus in work published in 1976. Bent functions are not balanced, since their Walsh coefficient at zero is nonzero. This illustrates a genuine design trade-off: optimizing one criterion can exclude another. Correlation immunity is a different property, requiring the output, under uniform independent inputs, to be statistically independent of every collection of at most a specified number of coordinates. Balanced correlation-immune functions are called resilient functions.

Vectorial Boolean functions describe substitution boxes F:F2n→F2mF:\mathbb F_2^n\to\mathbb F_2^m. Their behavior is not captured by inspecting coordinate functions in isolation: every nonzero linear combination of output coordinates matters for linear approximation. Differential behavior is described by

DaF(x)=F(x⊕a)⊕F(x),D_aF(x)=F(x\oplus a)\oplus F(x),

and differential uniformity records the largest number of solutions of DaF(x)=bD_aF(x)=b over nonzero aa and all bb. Such quantities measure structured statistical patterns rather than simply the number of gates required to implement the box.

Boolean functions also generate error-correcting codes. The Reed–Muller code RM(r,n)\mathrm{RM}(r,n) consists of truth tables of all nn-variable functions with algebraic degree at most rr. For 0≤r≤n0\leq r\leq n, it has length 2n2^n, dimension

∑j=0r(nj),\sum_{j=0}^{r}\binom nj,

and minimum distance 2n−r2^{n-r}. The first-order code contains precisely the affine functions, so a function’s cryptographic nonlinearity is its distance from this code. This gives an exact mathematical connection between resistance to affine approximation and the geometry of a classical family of codes.

Learning, collective decisions, and system reliability

In machine learning, a Boolean function can serve as a binary classification rule. The inputs encode attributes and the output selects one of two classes. Learning does not usually mean reconstructing an arbitrary truth table: without restrictions, exponentially many observations may be needed. Instead, algorithms exploit a hypothesis class such as conjunctions, small decision trees, sparse polynomial representations, or threshold functions. In probably approximately correct learning, success means producing a hypothesis with small error under the relevant input distribution, with high probability over the sampled training data.

The difficulty of learning depends on both representation and access to information. An example oracle supplies labeled inputs, while a membership-query oracle allows the learner to request the value at chosen inputs. Fourier coefficients can reveal correlations that guide learning under the uniform distribution, and functions depending on only a few relevant coordinates offer opportunities for dimension reduction. Such functions are often called juntas. Nevertheless, a class having a concise representation does not automatically imply an efficient learning algorithm: identifying that representation from observations may itself be computationally difficult.

Voting provides another interpretation. A Boolean aggregation rule maps individual binary votes to one collective outcome. Majority, unanimity, and dictatorship are elementary examples. Monotonicity expresses that changing an individual vote in favor of an outcome cannot make that outcome lose, while symmetry expresses equal treatment of voters. Influence is the probability that a voter is pivotal under a specified model of voting. Under independent uniformly random votes, this is the unnormalized probabilistic Banzhaf measure; other distributions and normalizations produce different voting-power indices.

In reliability theory, an input bit can indicate whether a component operates and the output whether the system operates. A monotone structure function describes a system in which repairing a component cannot cause failure. A series system is represented by conjunction and a parallel system by disjunction. If components work independently with probabilities p1,…,pnp_1,\ldots,p_n, system reliability is

R(p1,…,pn)=∑x∈{0,1}nf(x)∏i=1npixi(1−pi)1−xi.R(p_1,\ldots,p_n) =\sum_{x\in\{0,1\}^n} f(x)\prod_{i=1}^{n}p_i^{x_i}(1-p_i)^{1-x_i}.

This expression is multilinear in the component reliabilities. For series systems it reduces to ∏ipi\prod_i p_i, and for parallel systems to 1−∏i(1−pi)1-\prod_i(1-p_i). Dependence among component failures requires replacing the product model with the appropriate joint distribution.

For monotone functions under independent inputs with a common success probability pp, the Margulis–Russo formula links reliability changes to pivotal events:

ddpEp[f]=∑i=1nPr⁡p ⁣[f(x−i,1)≠f(x−i,0)].\frac{d}{dp}\mathbb E_p[f] =\sum_{i=1}^{n} \Pr_p\!\left[ f(x_{-i},1)\ne f(x_{-i},0) \right].

Here the probability on the right is over the other n−1n-1 coordinates. The formula explains how a Boolean system can undergo a sharp transition as component reliability or event density changes. The same mechanism appears in random graph properties and percolation: a global yes-or-no event changes rapidly when many local coordinates have a substantial combined chance of being pivotal.