Boolean function

In mathematics and logic, a Boolean function is a function whose arguments, as well as the function itself, assume values from a two-element set (usually {0,1} or {true, false}). An alternative name is switching function, used especially in older computer science literature. Boolean functions are the subject of Boolean algebra and switching theory.
A Boolean function takes the form formula_1, where formula_2 is known as the Boolean domain and formula_3 is a non-negative integer called the arity of the function. In the case where formula_4, the "function" is a constant element of formula_2. A Boolean function with multiple outputs, formula_6 with formula_7 is a "vectorial" or "vector-valued" Boolean function (an S-box in cryptography).
There are formula_8 different Boolean functions with formula_3 arguments; equal to the number of different truth tables with formula_10 entries. 
Every formula_3-ary Boolean function can be expressed as a propositional formula in formula_3 variables formula_13, and two propositional formulas are logically equivalent if and only if they express the same Boolean function. 
Examples.
The rudimentary symmetric Boolean functions (logical connectives or logic gates) are:
An example of a more complicated function is the majority function (of an odd number of inputs).
Representation.
A Boolean function may be specified in a variety of ways:
Algebraically, as a propositional formula using rudimentary boolean functions:
Boolean formulas can also be displayed as a graph:
In order to optimize electronic circuits, Boolean formulas can be minimized using the Quine–McCluskey algorithm or Karnaugh map.
Analysis.
Properties.
A Boolean function can have a variety of properties:
Circuit complexity attempts to classify Boolean functions with respect to the size or depth of circuits that can compute them.
Derived functions.
A Boolean function may be decomposed using Boole's expansion theorem in positive and negative "Shannon" "cofactors" (Shannon expansion), which are the (k-1)-ary functions resulting from fixing one of the arguments (to zero or one). The general (k-ary) functions obtained by imposing a linear constraint on a set of inputs (a linear subspace) are known as "subfunctions".
The "Boolean derivative" of the function to one of the arguments is a (k-1)-ary function that is true when the output of the function is sensitive to the chosen input variable; it is the XOR of the two corresponding cofactors. A derivative and a cofactor are used in a Reed–Muller expansion. The concept can be generalized as a k-ary derivative in the direction dx, obtained as the difference (XOR) of the function at x and x + dx.
The "Möbius transform" (or "Boole-Möbius transform") of a Boolean function is the set of coefficients of its polynomial (algebraic normal form), as a function of the monomial exponent vectors. It is a self-inverse transform. It can be calculated efficiently using a butterfly algorithm ("Fast Möbius Transform"), analogous to the Fast Fourier Transform. "Coincident" Boolean functions are equal to their Möbius transform, i.e. their truth table (minterm) values equal their algebraic (monomial) coefficients. There are 2^2^("k"−1) coincident functions of "k" arguments.
Cryptographic analysis.
The "Walsh transform" of a Boolean function is a k-ary integer-valued function giving the coefficients of a decomposition into linear functions (Walsh functions), analogous to the decomposition of real-valued functions into harmonics by the Fourier transform. Its square is the "power spectrum" or "Walsh spectrum". The Walsh coefficient of a single bit vector is a measure for the correlation of that bit with the output of the Boolean function. The maximum (in absolute value) Walsh coefficient is known as the "linearity" of the function. The highest number of bits (order) for which all Walsh coefficients are 0 (i.e. the subfunctions are balanced) is known as "resiliency", and the function is said to be correlation immune to that order. The Walsh coefficients play a key role in linear cryptanalysis.
The "autocorrelation" of a Boolean function is a k-ary integer-valued function giving the correlation between a certain set of changes in the inputs and the function ouput. For a given bit vector it is related to the Hamming weight of the derivative in that direction. The maximal autocorrelation coefficient (in absolute value) is known as the "absolute indicator". If all autocorrelation coefficients are 0 (i.e. the derivatives are balanced) for a certain number of bits then the function is said to satisfy the "propagation criterion" to that order; if they are all zero then the function is a bent function. The autocorrelation coefficients play a key role in differential cryptanalysis.
The Walsh coefficients of a Boolean function and its autocorrelation coefficients are related by the equivalent of the Wiener–Khinchin theorem, which states that the autocorrelation and the power spectrum are a Walsh transform pair.
These concepts can be extended naturally to "vectorial" Boolean functions by considering their output bits ("coordinates") individually, or more thoroughly, by looking at the set of all linear functions of output bits, known as its "components". The set of Walsh transforms of the components is known as a "Linear Approximation Table" (LAT) or "correlation matrix"; it describes the correlation between different linear combinations of input and output bits. The set of autocorrelation coefficients of the components is the "autocorrelation table", related by a Walsh transform of the components to the more widely used "Difference Distribution Table" (DDT) which lists the correlations between differences in input and output bits (see also: S-box).
Applications.
Boolean functions play a basic role in questions of complexity theory as well as the design of processors for digital computers, where they are implemented in electronic circuits using logic gates. 
The properties of Boolean functions are critical in cryptography, particularly in the design of symmetric key algorithms (see substitution box).
In cooperative game theory, monotone Boolean functions are called simple games (voting games); this notion is applied to solve problems in social choice theory.