A Boolean function takes the form, where is known as theBoolean domain and is a non-negative integer called thearity of the function. In the case where, the function is a constant element of. A Boolean function with multiple outputs, with is avectorial orvector-valued Boolean function (anS-box in symmetriccryptography).[6]
There are different Boolean functions with arguments; equal to the number of differenttruth tables with entries.
Every-ary Boolean function can be expressed as apropositional formula in variables, and two propositional formulas arelogically equivalent if and only if they express the same Boolean function.
A Boolean function can have a variety of properties:[7]
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 beunate 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 (aparity function).
Symmetric: the value does not depend on the order of its arguments.
A Boolean function may be decomposed usingBoole's expansion theorem in positive and negativeShannoncofactors (Shannon expansion), which are the (k−1)-ary functions resulting from fixing one of the arguments (to 0 or 1). The generalk-ary functions obtained by imposing a linear constraint on a set of inputs (a linear subspace) are known assubfunctions.[8]
TheBoolean 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 aReed–Muller expansion. The concept can be generalized as ak-ary derivative in the direction dx, obtained as the difference (XOR) of the function at x and x + dx.[8]
TheMöbius transform (orBoole–Möbius transform) of a Boolean function is the set of coefficients of itspolynomial (algebraic normal form), as a function of the monomial exponent vectors. It is aself-inverse transform. It can be calculated efficiently using abutterfly algorithm ("Fast Möbius Transform"), analogous to thefast Fourier transform.[9]Coincident Boolean functions are equal to their Möbius transform, i.e. their truth table (minterm) values equal their algebraic (monomial) coefficients.[10] There are 2^2^(k−1) coincident functions ofk arguments.[11]
TheWalsh transform of a Boolean function is a k-ary integer-valued function giving the coefficients of a decomposition intolinear functions (Walsh functions), analogous to the decomposition of real-valued functions intoharmonics by theFourier transform. Its square is thepower spectrum orWalsh 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 thelinearity 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 asresiliency, and the function is said to becorrelation immune to that order.[8] The Walsh coefficients play a key role inlinear cryptanalysis.
Theautocorrelation 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 output. 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 theabsolute indicator.[7][8] 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 thepropagation criterion to that order; if they are all zero then the function is abent function.[12] The autocorrelation coefficients play a key role indifferential cryptanalysis.
The Walsh coefficients of a Boolean function and its autocorrelation coefficients are related by the equivalent of theWiener–Khinchin theorem, which states that the autocorrelation and the power spectrum are a Walsh transform pair.[8]
These concepts can be extended naturally tovectorial 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 itscomponents.[6] The set of Walsh transforms of the components is known as alinear approximation table (LAT)[13][14] orcorrelation 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 theautocorrelation table,[14] related by a Walsh transform of the components[17] to the more widely useddifference distribution table (DDT)[13][14] which lists the correlations between differences in input and output bits (see also:S-box).
Any Boolean function can be uniquely extended (interpolated) to thereal domain by amultilinear polynomial in, constructed by summing the truth table values multiplied byindicator polynomials:For example, the extension of the binary XOR function iswhich equalsSome other examples are negation (), AND () and OR (). 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 calculatedmodulo 2 one obtains thealgebraic normal form (Zhegalkin polynomial).
Direct expressions for the coefficients of the polynomial can be derived by taking an appropriate derivative:this generalizes as theMöbius inversion of thepartially ordered set of bit vectors:where denotes the weight of the bit vector. Taken modulo 2, this is theBooleanMöbius transform, giving thealgebraic normal form coefficients:In both cases, the sum is taken over all bit-vectorsa covered bym, i.e. the "one" bits ofa form a subset of the one bits ofm.
When the domain is restricted to the n-dimensionalhypercube, the polynomial gives the probability of a positive outcome when the Boolean functionf is applied ton independent random (Bernoulli) variables, with individual probabilitiesx. A special case of this fact is thepiling-up lemma forparity functions. The polynomial form of a Boolean function can also be used as its natural extension tofuzzy logic.
Often, the Boolean domain is taken as, with false ("0") mapping to 1 and true ("1") to −1 (seeAnalysis of Boolean functions). The polynomial corresponding to is then given by:Using the symmetric Boolean domain simplifies certain aspects of theanalysis, since negation corresponds to multiplying by −1 andlinear functions aremonomials (XOR is multiplication). This polynomial form thus corresponds to theWalsh transform (in this context also known asFourier transform) of the function (see above). 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 (seepiling-up lemma for an example).
Boolean functions play a basic role in questions ofcomplexity theory as well as the design of processors fordigital computers, where they are implemented in electronic circuits usinglogic gates.
Incooperative game theory, monotone Boolean functions are calledsimple games (voting games); this notion is applied to solve problems insocial choice theory.
^Davies, D. W. (December 1957). "Switching Functions of Three Variables".IRE Transactions on Electronic Computers.EC-6 (4):265–275.doi:10.1109/TEC.1957.5222038.ISSN0367-9950.
^McCluskey, Edward J. (2003-01-01),"Switching theory",Encyclopedia of Computer Science, GBR: John Wiley and Sons Ltd., pp. 1727–1731,ISBN978-0-470-86412-8, retrieved2021-05-03
^abcdefTarannikov, Yuriy; Korolev, Peter; Botev, Anton (2001). "Autocorrelation Coefficients and Correlation Immunity of Boolean Functions". In Boyd, Colin (ed.).Advances in Cryptology — ASIACRYPT 2001. Lecture Notes in Computer Science. Vol. 2248. Berlin, Heidelberg: Springer. pp. 460–479.doi:10.1007/3-540-45682-1_27.ISBN978-3-540-45682-7.
Category
