Properties A Boolean function can have a variety of properties: •
Constant: Is always true or always false regardless of its arguments. •
Monotone: for every combination of argument values, changing an argument from false to true can only cause the output to switch from false to true and not from true to false. A function is said to be
unate in a certain variable if it is monotone with respect to changes in that variable. •
Linear: for each variable, flipping the value of the variable either always makes a difference in the truth value or never makes a difference (a
parity function). •
Symmetric: the value does not depend on the order of its arguments. •
Read-once: Can be expressed with
conjunction,
disjunction, and
negation with a single instance of each variable. •
Balanced: if its
truth table contains an equal number of zeros and ones. The
Hamming weight of the function is the number of ones in the truth table. •
Bent: its derivatives are all balanced (the autocorrelation spectrum is zero) •
Correlation immune to
mth order: if the output is uncorrelated with all (linear) combinations of at most
m arguments •
Evasive: if evaluation of the function always requires the value of all arguments • A Boolean function is a
Sheffer function if it can be used to create (by composition) any arbitrary Boolean function (see
functional completeness) • The
algebraic degree of a function is the order of the highest order monomial in its
algebraic normal form 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 0 or 1). 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.
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 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. 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, to the more widely used
difference distribution table (DDT) which lists the correlations between differences in input and output bits (see also:
S-box). == Real polynomial form ==