Boolean function
is a vectorial or vector-valued Boolean function (an S-box in symmetric cryptography).
arguments; equal to the number of different truth tables with
, and two propositional formulas are logically equivalent if and only if they express the same Boolean function.
A Boolean function can have a variety of properties:[7] Circuit complexity attempts to classify Boolean functions with respect to the size or depth of circuits that can compute them.
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).
[8] 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.
[9] Coincident Boolean functions are equal to their Möbius transform, i.e. their truth table (minterm) values equal their algebraic (monomial) coefficients.
The maximum (in absolute value) Walsh coefficient is known as the linearity of the function.
[8] 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.
[8] The Walsh coefficients play a key role in linear cryptanalysis.
For a given bit vector it is related to the Hamming weight of the derivative in that direction.
[12] 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.
[8] 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.
[6] The set of Walsh transforms of the components is known as a Linear Approximation Table (LAT)[13][14] or correlation matrix;[15][16] 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,[14] related by a Walsh transform of the components[17] to the more widely used Difference Distribution Table (DDT)[13][14] which lists the correlations between differences in input and output bits (see also: S-box).
can be uniquely extended (interpolated) to the real domain by a multilinear polynomial in
, constructed by summing the truth table values multiplied by indicator polynomials:
When all operands are independent (share no variables) a function's polynomial form can be found by repeatedly applying the polynomials of the operators in a Boolean formula.
When the coefficients are calculated modulo 2 one obtains the algebraic normal form (Zhegalkin polynomial).
this generalizes as the Möbius inversion of the partially ordered set of bit vectors:
Taken modulo 2, this is the Boolean Möbius transform, giving the algebraic normal form coefficients:
gives the probability of a positive outcome when the Boolean function f is applied to n independent random (Bernoulli) variables, with individual probabilities x.
A special case of this fact is the piling-up lemma for parity functions.
The polynomial form of a Boolean function can also be used as its natural extension to fuzzy logic.
, with false ("0") mapping to 1 and true ("1") to -1 (see Analysis of Boolean functions).
Using the symmetric Boolean domain simplifies certain aspects of the analysis, since negation corresponds to multiplying by -1 and linear functions are monomials (XOR is multiplication).
The polynomial also has the same statistical interpretation as the one in the standard Boolean domain, except that it now deals with the expected values
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).
