Boolean function explained

Boolean function should not be confused with Binary function.

In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually, or).[1] [2] Alternative names are switching function, used especially in older computer science literature,[3] [4] and truth function (or logical function), used in logic. Boolean functions are the subject of Boolean algebra and switching theory.

A Boolean function takes the form

f:\{0,1\}k\to\{0,1\}

, where

\{0,1\}

is known as the Boolean domain and

k

is a non-negative integer called the arity of the function. In the case where

k=0

, the function is a constant element of

\{0,1\}

. A Boolean function with multiple outputs,

f:\{0,1\}k\to\{0,1\}m

with

m>1

is a vectorial or vector-valued Boolean function (an S-box in symmetric cryptography).

There are

2k
2
different Boolean functions with

k

arguments; equal to the number of different truth tables with

2k

entries.

Every

k

-ary Boolean function can be expressed as a propositional formula in

k

variables

x1,...,xk

, and two propositional formulas are logically equivalent if and only if they express the same Boolean function.

Examples

See also: Truth table and Truth function. 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

See also: Analysis of Boolean functions.

Properties

A Boolean function can have a variety of properties:[5]

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.

if evaluation of the function always requires the value of all arguments

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.[6]

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.[7] There are 2^2^(k−1) coincident functions of k arguments.[8]

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 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 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.[9] 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.

Linear approximation table

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.[10] The set of Walsh transforms of the components is known as a Linear Approximation Table (LAT)[11] [12] or correlation matrix;[13] [14] 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[15] 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

On the unit hypercube

Any Boolean function

f(x):\{0,1\}n\{0,1\}

can be uniquely extended (interpolated) to the real domain by a multilinear polynomial in

Rn

, constructed by summing the truth table values multiplied by indicator polynomials:f^*(x) = \sum_ f(a) \prod_ x_i \prod_ (1-x_i)For example, the extension of the binary XOR function

xy

is0(1-x)(1-y) + 1x(1-y) + 1(1-x)y + 0xywhich equalsx + y -2xySome other examples are negation (

1-x

), AND (

xy

) and OR (

x+y-xy

). 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).

Direct expressions for the coefficients of the polynomial can be derived by taking an appropriate derivative:\begin f^*(00) & = & (f^*)(00) & = & f(00) \\ f^*(01) & = & (\partial_1f^*)(00) & = & -f(00) + f(01) \\f^*(10) & = & (\partial_2f^*)(00) & = & -f(00) + f(10) \\f^*(11) & = & (\partial_1\partial_2f^*)(00) & = & f(00) -f(01)-f(10)+f(11) \\\endthis generalizes as the Möbius inversion of the partially ordered set of bit vectors:f^*(m) = \sum_ (-1)^

m
f(a)where

|a|

denotes the weight of the bit vector

a

. Taken modulo 2, this is the Boolean Möbius transform, giving the algebraic normal form coefficients:\hat f(m) = \bigoplus_ f(a)In both cases, the sum is taken over all bit-vectors a covered by m, i.e. the "one" bits of a form a subset of the one bits of m.

[0,1]n

, the polynomial

f*(x):[0,1]n[0,1]

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.

On the symmetric hypercube

Often, the Boolean domain is taken as

\{-1,1\}

, with false ("0") mapping to 1 and true ("1") to -1 (see Analysis of Boolean functions). The polynomial corresponding to

g(x):\{-1,1\}n\{-1,1\}

is then given by:g^*(x) = \sum_ g(a) \prod_ \frac \prod_ \fracUsing 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). This polynomial form thus corresponds to the Walsh transform (in this context also known as Fourier 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

E(X)=P(X=1)-P(X=-1)\in[-1,1]

(see piling-up lemma for an example).

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.

See also

Further reading

Notes and References

  1. Web site: Boolean function - Encyclopedia of Mathematics. 2021-05-03. encyclopediaofmath.org.
  2. Web site: Weisstein. Eric W.. Boolean Function. 2021-05-03. mathworld.wolfram.com. en.
  3. Web site: switching function. 2021-05-03. TheFreeDictionary.com.
  4. Davies. D. W.. December 1957. Switching Functions of Three Variables. IRE Transactions on Electronic Computers. EC-6. 4. 265–275. 10.1109/TEC.1957.5222038. 0367-9950.
  5. Web site: Boolean functions — Sage 9.2 Reference Manual: Cryptography. 2021-05-01. doc.sagemath.org.
  6. Book: Tarannikov. Yuriy. Korolev. Peter. Botev. Anton. Advances in Cryptology — ASIACRYPT 2001 . Autocorrelation Coefficients and Correlation Immunity of Boolean Functions . 2001. Boyd. Colin. Lecture Notes in Computer Science. 2248. en. Berlin, Heidelberg. Springer. 460–479. 10.1007/3-540-45682-1_27. 978-3-540-45682-7. free.
  7. Pieprzyk. Josef. Wang. Huaxiong. Zhang. Xian-Mo. 2011-05-01. Mobius transforms, coincident Boolean functions and non-coincidence property of Boolean functions. International Journal of Computer Mathematics. 88. 7. 1398–1416. 10.1080/00207160.2010.509428. 9580510 . 0020-7160.
  8. Nitaj. Abderrahmane. Susilo. Willy. Tonien. Joseph. 2017-10-01. Dirichlet product for boolean functions. Journal of Applied Mathematics and Computing. en. 55. 1. 293–312. 10.1007/s12190-016-1037-4. 16760125 . 1865-2085.
  9. Canteaut. Anne. Carlet. Claude. Charpin. Pascale. Fontaine. Caroline. 2000-05-14. Propagation characteristics and correlation-immunity of highly nonlinear boolean functions. Proceedings of the 19th International Conference on Theory and Application of Cryptographic Techniques. EUROCRYPT'00. Bruges, Belgium. Springer-Verlag. 507–522. 978-3-540-67517-4.
  10. Web site: Carlet. Claude. Vectorial Boolean Functions for Cryptography. live. University of Paris. https://web.archive.org/web/20160117102533/http://www.math.univ-paris13.fr:80/~carlet/chap-vectorial-fcts-corr.pdf . 2016-01-17 .
  11. Web site: Heys. Howard M.. A Tutorial on Linear and Differential Cryptanalysis. live. https://web.archive.org/web/20170517014157/http://www.cs.bc.edu:80/~straubin/crypto2017/heys.pdf . 2017-05-17 .
  12. Web site: S-Boxes and Their Algebraic Representations — Sage 9.2 Reference Manual: Cryptography. 2021-05-04. doc.sagemath.org.
  13. Daemen . Joan . Govaerts . René . Vandewalle . Joos . Preneel . Bart . Correlation matrices . 10.1007/3-540-60590-8_21 . 275–285 . Springer . Lecture Notes in Computer Science . Fast Software Encryption: Second International Workshop. Leuven, Belgium, 14-16 December 1994, Proceedings . 1008 . 1994. free .
  14. Web site: Daemen. Joan. 10 June 1998. Chapter 5: Propagation and Correlation - Annex to AES Proposal Rijndael. live. NIST. https://web.archive.org/web/20180723015757/https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Standards-and-Guidelines/documents/aes-development/PropCorr.pdf . 2018-07-23 .
  15. Web site: Nyberg. Kaisa. December 1, 2019. The Extended Autocorrelation and Boomerang Tables and Links Between Nonlinearity Properties of Vectorial Boolean Functions. live. https://web.archive.org/web/20201102023321/https://eprint.iacr.org/2019/1381.pdf . 2020-11-02 .