Boolean function: Difference between revisions

Revision as of 21:30, 6 July 2023

Latest revision as of 10:25, 25 August 2025

(19 intermediate revisions by 10 users not shown)

Line 2:

{{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>

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,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" />

Line 12 ⟶ 14:

== 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:

Line 25 ⟶ 27:

== Representation ==

[[File:Three input Booleanboolean circuit.jpgsvg|thumb|A Boolean function represented as a [[Boolean circuit]]]]

A Boolean function may be specified in a variety of ways:

Line 32 ⟶ 34:

**[[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 booleanBoolean functions:

* [[Negation normal form]], an arbitrary mix of AND and ORs of the arguments and their complements

Line 60 ⟶ 62:

* [[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 booleanBoolean 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

Line 69 ⟶ 71:

=== 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''−1)-ary functions resulting from fixing one of the arguments (to zero0 or one1). 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|journal=Advances in Cryptology – ASIACRYPT 2001|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''−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öbiusBoole–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 [[Fastfast 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|url-access=subscription}}</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 ===

Line 83 ⟶ 85:

==== 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 '''Linearlinear Approximationapproximation Tabletable''' (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>{{Citecite conference journal| last1 = Daemen | first1 = Joan | last2 = Govaerts | first2 = René | last3 = Vandewalle | first3 = Joos |date=1995| editor-last = Preneel | editor-first = Bart | title = Correlation matrices |journal doi =Fast Software10.1007/3-540-60590-8_21 Encryption| pages = 275–285 | publisher = Springer | series = Lecture Notes in Computer Science |volume=1008|language=en|___location book-title =Berlin Fast Software Encryption: Second International Workshop. Leuven, HeidelbergBelgium, 14-16 December 1994, Proceedings |publisher volume =Springer 1008 |pages year =275–285|doi=10.1007/3-540-60590-8_21|isbn=978-3-540-47809-6 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 ''Differencedifference Distributiondistribution Tabletable'' (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 ==

Line 98 ⟶ 100:

=== 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−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−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==

Line 129 ⟶ 131:

*{{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}}