Boolean function: Difference between revisions

Revision as of 18:11, 11 April 2025

Revision as of 18:14, 11 April 2025

Line 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|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ö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>