View source for Boolean function

{{Short description|Function returning one of only two values}}
{{distinguish|Binary function}}
[[File:BinaryDecisionTree.svg|thumb|A [[binary decision diagram]] and [[truth table]] of a ternary Boolean function]]
{{Logical connectives sidebar}}

In [[mathematics]], a '''Boolean function''' is a [[function (mathematics)|function]] whose [[Argument of a function|arguments]] and result assume values from a two-element set (usually {true, false}, {0,1} or {-1,1}).<ref>{{Cite web|title=Boolean function - Encyclopedia of Mathematics|url=https://encyclopediaofmath.org/wiki/Boolean_function|access-date=2021-05-03|website=encyclopediaofmath.org}}</ref><ref>{{Cite web|last=Weisstein|first=Eric W.|title=Boolean Function|url=https://mathworld.wolfram.com/BooleanFunction.html|access-date=2021-05-03|website=mathworld.wolfram.com|language=en}}</ref> Alternative names are '''switching function''', used especially in older [[computer science]] literature,<ref>{{Cite web|title=switching function|url=https://encyclopedia2.thefreedictionary.com/switching+function|access-date=2021-05-03|website=TheFreeDictionary.com}}</ref><ref>{{Cite journal|last=Davies|first=D. W.|date=December 1957|title=Switching Functions of Three Variables|url=https://ieeexplore.ieee.org/document/5222038|journal=IRE Transactions on Electronic Computers|volume=EC-6|issue=4|pages=265–275|doi=10.1109/TEC.1957.5222038|issn=0367-9950}}</ref> and '''[[truth function]]''' (or '''logical function)''', used in [[logic]]. Boolean functions are the subject of [[Boolean algebra]] and [[switching theory]].<ref>{{Citation|last=McCluskey|first=Edward J.|title=Switching theory|date=2003-01-01|url=https://dl.acm.org/doi/10.5555/1074100.1074844|encyclopedia=Encyclopedia of Computer Science|pages=1727–1731|place=GBR|publisher=John Wiley and Sons Ltd.|doi=|isbn=978-0-470-86412-8|access-date=2021-05-03}}</ref>

A Boolean function takes the form <math>f:\{0,1\}^k \to \{0,1\}</math>, where <math>\{0,1\}</math> is known as the [[Boolean domain]] and <math>k</math> is a non-negative integer called the [[arity]] of the function. In the case where <math>k=0</math>, the function is a constant element of <math>\{0,1\}</math>. A Boolean function with multiple outputs, <math>f:\{0,1\}^k \to \{0,1\}^m</math> with <math>m>1</math> is a '''vectorial''' or ''vector-valued'' Boolean function (an [[S-box]] in symmetric [[cryptography]]).<ref name=":2" />

There are <math>2^{2^k}</math> different Boolean functions with <math>k</math> arguments; equal to the number of different [[truth table]]s with <math>2^k</math> entries.

Every <math>k</math>-ary Boolean function can be expressed as a [[propositional formula]] in <math>k</math> variables <math>x_1,...,x_k</math>, and two propositional formulas are [[logical equivalence|logically equivalent]] if and only if they express the same Boolean function.

== Examples ==
[[File:Logical connectives Hasse diagram.svg|alt=Diagram displaying the sixteen binary Boolean functions|thumb|The sixteen binary Boolean functions]]
{{See also|Truth table|Truth function}}
The rudimentary symmetric Boolean functions ([[logical connective]]s or [[logic gate]]s) are:

* [[Inverter (logic gate)|NOT]], [[negation]] or [[Logical complement|complement]] - which receives one input and returns true when that input is false ("not")
* [[AND gate|AND]] or [[Logical conjunction|conjunction]] - true when all inputs are true ("both")
* [[OR gate|OR]] or [[Logical disjunction|disjunction]] - true when any input is true ("either")
* [[XOR gate|XOR]] or [[Exclusive or|exclusive disjunction]] - true when one of its inputs is true and the other is false ("not equal")
* [[NAND gate|NAND]] or [[Sheffer stroke]] - true when it is not the case that all inputs are true ("not both")
*[[NOR gate|NOR]] or [[Logical NOR|logical nor]] - true when none of the inputs are true ("neither")
*[[XNOR gate|XNOR]] or [[logical equality]] - true when both inputs are the same ("equal")
An example of a more complicated function is the [[majority function]] (of an odd number of inputs).

== Representation ==
[[File:Three input boolean circuit.svg|thumb|A Boolean function represented as a [[Boolean circuit]]]]
A Boolean function may be specified in a variety of ways:

* [[Truth table]]: explicitly listing its value for all possible values of the arguments
**Marquand diagram: truth table values arranged in a two-dimensional grid (used in a [[Karnaugh map]])
**[[Binary decision diagram]], listing the truth table values at the bottom of a binary tree
**[[Venn diagram]], depicting the truth table values as a colouring of regions of the plane
Algebraically, as a [[propositional formula]] using rudimentary Boolean functions:

* [[Negation normal form]], an arbitrary mix of AND and ORs of the arguments and their complements
* [[Disjunctive normal form]], as an OR of ANDs of the arguments and their complements
* [[Conjunctive normal form]], as an AND of ORs of the arguments and their complements
*[[Canonical normal form]], a standardized formula which uniquely identifies the function:
**[[Algebraic normal form]] or [[Zhegalkin polynomial]], as a XOR of ANDs of the arguments (no complements allowed)
**''Full'' (canonical) [[disjunctive normal form]], an OR of ANDs each containing every argument or complement ([[minterms]])
**''Full'' (canonical) [[conjunctive normal form]], an AND of ORs each containing every argument or complement ([[maxterms]])
**[[Blake canonical form]], the OR of all the [[prime implicant]]s of the function
Boolean formulas can also be displayed as a graph:
* [[Propositional directed acyclic graph]]
**[[Circuit (computer science)|Digital circuit]] diagram of [[logic gate]]s, a [[Boolean circuit]]
**[[And-inverter graph]], using only AND and NOT
In order to optimize electronic circuits, Boolean formulas can be [[Minimization of Boolean functions|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:<ref name=":0">{{Cite web|title=Boolean functions — Sage 9.2 Reference Manual: Cryptography|url=https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/boolean_function.html|access-date=2021-05-01|website=doc.sagemath.org}}</ref>

* [[Constant function|Constant]]: Is always true or always false regardless of its arguments.
* [[Monotonic function#In Boolean functions|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 function|unate]] in a certain variable if it is monotone with respect to changes in that variable. 
* [[Linearity#Boolean functions|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 Boolean function|Symmetric]]: the value does not depend on the order of its arguments.
* [[Read-once function|Read-once]]: Can be expressed with [[logical conjunction|conjunction]], [[logical disjunction|disjunction]], and [[negation]] with a single instance of each variable.
*[[Balanced Boolean function|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 function|Bent]]: its derivatives are all balanced (the autocorrelation spectrum is zero)
* [[Correlation immunity|Correlation immune]] to ''m''th order: if the output is uncorrelated with all (linear) combinations of at most ''m'' arguments
*[[Evasive Boolean function|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 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''.<ref name=":1">{{Cite book|last1=Tarannikov|first1=Yuriy|last2=Korolev|first2=Peter|last3=Botev|first3=Anton|title=Advances in Cryptology — ASIACRYPT 2001 |chapter=Autocorrelation Coefficients and Correlation Immunity of Boolean Functions |date=2001|editor-last=Boyd|editor-first=Colin|series=Lecture Notes in Computer Science|volume=2248|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=460–479|doi=10.1007/3-540-45682-1_27|isbn=978-3-540-45682-7|doi-access=free}}</ref>

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.<ref name=":1" />

The ''[[Zhegalkin polynomial#Möbius transformation|Möbius transform]]'' (or ''Boole-Möbius transform'') of a Boolean function is the set of coefficients of its [[Zhegalkin polynomial|polynomial]] ([[algebraic normal form]]), as a function of the monomial exponent vectors. It is a [[Involution (mathematics)|self-inverse]] transform. It can be calculated efficiently using a [[Butterfly diagram|butterfly algorithm]] ("''Fast Möbius Transform''"), analogous to the [[Fast Fourier transform|Fast Fourier Transform]].<ref>{{Citation|last=Carlet|first=Claude|title=Boolean Functions for Cryptography and Error-Correcting Codes|date=2010|url=https://www.math.univ-paris13.fr/~carlet/chap-fcts-Bool-corr.pdf|work=Boolean Models and Methods in Mathematics, Computer Science, and Engineering|pages=257–397|editor-last=|editor-first=|series=Encyclopedia of Mathematics and its Applications|place=Cambridge|publisher=Cambridge University Press|isbn=978-0-521-84752-0|access-date=2021-05-17|editor2-last=|editor2-first=}}</ref> ''Coincident'' Boolean functions are equal to their Möbius transform, i.e. their truth table (minterm) values equal their algebraic (monomial) coefficients.<ref>{{Cite journal|last1=Pieprzyk|first1=Josef|last2=Wang|first2=Huaxiong|last3=Zhang|first3=Xian-Mo|date=2011-05-01|title=Mobius transforms, coincident Boolean functions and non-coincidence property of Boolean functions|url=https://doi.org/10.1080/00207160.2010.509428|journal=International Journal of Computer Mathematics|volume=88|issue=7|pages=1398–1416|doi=10.1080/00207160.2010.509428|s2cid=9580510 |issn=0020-7160}}</ref> There are 2^2^(''k''−1) coincident functions of ''k'' arguments.<ref>{{Cite journal|last1=Nitaj|first1=Abderrahmane|last2=Susilo|first2=Willy|last3=Tonien|first3=Joseph|date=2017-10-01|title=Dirichlet product for boolean functions|url=https://doi.org/10.1007/s12190-016-1037-4|journal=Journal of Applied Mathematics and Computing|language=en|volume=55|issue=1|pages=293–312|doi=10.1007/s12190-016-1037-4|s2cid=16760125 |issn=1865-2085}}</ref>

=== Cryptographic analysis ===
The ''[[Walsh transform]]'' of a Boolean function is a k-ary integer-valued function giving the coefficients of a decomposition into [[Parity function|linear functions]] ([[Walsh function]]s), analogous to the decomposition of real-valued functions into [[harmonic]]s 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.<ref name=":1" /> 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 immunity|correlation immune]] to that order.<ref name=":1" /> 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''.<ref name=":0" /><ref name=":1" /> 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]].<ref>{{Cite journal|last1=Canteaut|first1=Anne|last2=Carlet|first2=Claude|last3=Charpin|first3=Pascale|last4=Fontaine|first4=Caroline|date=2000-05-14|title=Propagation characteristics and correlation-immunity of highly nonlinear boolean functions|url=https://dl.acm.org/doi/10.5555/1756169.1756219|journal=Proceedings of the 19th International Conference on Theory and Application of Cryptographic Techniques|series=EUROCRYPT'00|location=Bruges, Belgium|publisher=Springer-Verlag|pages=507–522|isbn=978-3-540-67517-4}}</ref> 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.<ref name=":1" />

==== 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''.<ref name=":2">{{Cite web|last=Carlet|first=Claude|title=Vectorial Boolean Functions for Cryptography|url=https://www.math.univ-paris13.fr/~carlet/chap-vectorial-fcts-corr.pdf|url-status=live|website=University of Paris|archive-url=https://web.archive.org/web/20160117102533/http://www.math.univ-paris13.fr:80/~carlet/chap-vectorial-fcts-corr.pdf |archive-date=2016-01-17 }}</ref> The set of Walsh transforms of the components is known as a '''Linear Approximation Table''' (LAT)<ref name=":3">{{Cite web|last=Heys|first=Howard M.|title=A Tutorial on Linear and Differential Cryptanalysis|url=http://www.cs.bc.edu/~straubin/crypto2017/heys.pdf|url-status=live|archive-url=https://web.archive.org/web/20170517014157/http://www.cs.bc.edu:80/~straubin/crypto2017/heys.pdf |archive-date=2017-05-17 }}</ref><ref name=":4">{{Cite web|title=S-Boxes and Their Algebraic Representations — Sage 9.2 Reference Manual: Cryptography|url=https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/sbox.html|access-date=2021-05-04|website=doc.sagemath.org}}</ref> or ''correlation matrix'';<ref>{{cite conference | last1 = Daemen | first1 = Joan | last2 = Govaerts | first2 = René | last3 = Vandewalle | first3 = Joos | editor-last = Preneel | editor-first = Bart | title = Correlation matrices | doi = 10.1007/3-540-60590-8_21 | pages = 275–285 | publisher = Springer | series = Lecture Notes in Computer Science | book-title = Fast Software Encryption: Second International Workshop. Leuven, Belgium, 14-16 December 1994, Proceedings | volume = 1008 | year = 1994| doi-access = free }}</ref><ref>{{Cite web|last=Daemen|first=Joan|date=10 June 1998|title=Chapter 5: Propagation and Correlation - Annex to AES Proposal Rijndael|url=https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Standards-and-Guidelines/documents/aes-development/PropCorr.pdf|url-status=live|website=NIST|archive-url=https://web.archive.org/web/20180723015757/https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Standards-and-Guidelines/documents/aes-development/PropCorr.pdf |archive-date=2018-07-23 }}</ref> 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'',<ref name=":4" /> related by a Walsh transform of the components<ref>{{Cite web|last=Nyberg|first=Kaisa|date=December 1, 2019|title=The Extended Autocorrelation and Boomerang Tables and Links Between Nonlinearity Properties of Vectorial Boolean Functions|url=https://eprint.iacr.org/2019/1381.pdf|url-status=live|archive-url=https://web.archive.org/web/20201102023321/https://eprint.iacr.org/2019/1381.pdf |archive-date=2020-11-02 }}</ref> to the more widely used ''Difference Distribution Table'' (DDT)<ref name=":3" /><ref name=":4" /> 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 <math>f(x): \{0,1\}^n \rightarrow \{0,1\}</math> can be uniquely extended (interpolated) to the [[Real number|real domain]] by a [[multilinear polynomial]] in <math>\mathbb{R}^n</math>, constructed by summing the truth table values multiplied by [[Lagrange polynomial|indicator polynomials]]:<math display="block">f^*(x) = \sum_{a \in {\{0,1\}}^n} f(a) \prod_{i:a_i=1} x_i \prod_{i:a_i=0} (1-x_i)</math>For example, the extension of the binary XOR function <math>x \oplus y</math> is<math display="block">0(1-x)(1-y) + 1x(1-y) + 1(1-x)y + 0xy</math>which equals<math display="block">x + y -2xy</math>Some other examples are negation (<math>1-x</math>), AND (<math>xy</math>) and OR (<math>x + y - xy</math>). 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 [[Modular arithmetic|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:<math display="block">\begin{array}{lcl} 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) \\
\end{array}</math>this generalizes as the [[Möbius transform|Möbius inversion]] of the [[partially ordered set]] of bit vectors:<math display="block">f^*(m) = \sum_{a \subseteq m} (-1)^{|a|+|m|} f(a)</math>where <math>|a|</math> denotes the weight of the bit vector <math>a</math>. Taken modulo 2, this is the [[Zhegalkin polynomial|Boolean ''Möbius transform'']], giving the [[algebraic normal form]] coefficients:<math display="block">\hat f(m) = \bigoplus_{a \subseteq m} f(a)</math>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''.

When the domain is restricted to the n-dimensional [[hypercube]] <math>[0,1]^n</math>, the polynomial <math>f^*(x): [0,1]^n \rightarrow [0,1]</math> gives the probability of a positive outcome when the Boolean function ''f'' is applied to ''n'' independent random ([[Bernoulli distribution|Bernoulli]]) variables, with individual probabilities ''x''. A special case of this fact is the [[piling-up lemma]] for [[parity function]]s. 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 <math>\{-1, 1\}</math>, with false ("0") mapping to 1 and true ("1") to -1 (see [[Analysis of Boolean functions]]). The polynomial corresponding to <math>g(x): \{-1,1\}^n \rightarrow \{-1,1\}</math> is then given by:<math display="block">g^*(x) = \sum_{a \in {\{-1,1\}}^n} g(a) \prod_{i:a_i=-1} \frac{1-x_i}{2} \prod_{i:a_i=1} \frac{1+x_i}{2}</math>Using the symmetric Boolean domain simplifies certain aspects of the [[Analysis of Boolean functions|analysis]], since negation corresponds to multiplying by -1 and [[Parity function|linear functions]] are [[monomial]]s (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 <math>E(X) = P(X=1) - P(X=-1) \in [-1, 1]</math> (see [[piling-up lemma]] for an example).

==Applications==
Boolean functions play a basic role in questions of [[Computational complexity theory|complexity theory]] as well as the design of processors for [[digital computer]]s, where they are implemented in electronic circuits using [[logic gate]]s.

The properties of Boolean functions are critical in [[cryptography]], particularly in the design of [[symmetric key algorithm]]s (see [[substitution box]]).

In [[Cooperative game theory|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==
{{Portal|Philosophy}}
{{div col}}
*[[Pseudo-Boolean function]]
*[[Boolean-valued function]]
*[[List of Boolean algebra topics|Boolean algebra topics]]
*[[Algebra of sets]]
*[[Decision tree model]]
*[[Indicator function]]
*[[Signed set]]
{{div col end}}

==References==
{{reflist}}

==Further reading==
*{{citation |last1=Crama |first1=Yves |last2=Hammer |first2=Peter L. |authorlink2=Peter L. Hammer |year=2011 |title=Boolean Functions: Theory, Algorithms, and Applications |publisher=Cambridge University Press |doi=10.1017/CBO9780511852008 |isbn=9780511852008}}
*{{springer |title=Boolean function |id=p/b016940}}
*{{cite journal |last1=Janković |first1=Dragan |last2=Stanković |first2=Radomir S. |last3=Moraga |first3=Claudio |date=November 2003 |title=Arithmetic expressions optimisation using dual polarity property |journal=Serbian Journal of Electrical Engineering |volume=1 |issue=71-80, number 1 |doi=10.2298/SJEE0301071J |pages=71–80 |doi-access=free }}
*{{cite book |last=Arnold |first=Bradford Henry |date=1 January 2011 |title=Logic and Boolean Algebra |publisher=Courier Corporation |isbn=978-0-486-48385-6 |url=https://books.google.com/books?id=KoAsmTsOK9IC&q=%22boolean+function%22}}
*{{citation |last1=Mano |first1=M. M. |last2=Ciletti |first2=M. D. |year=2013 |title=Digital Design |publisher=Pearson}}

{{Mathematical logic}} {{Functions navbox}}

{{DEFAULTSORT:Boolean function}}
[[Category:Boolean algebra]]
[[Category:Binary arithmetic]]
[[Category:Logic gates]]
[[Category:Programming constructs]]