Boolean function: Difference between revisions

Revision as of 04:08, 5 July 2023

Revision as of 21:30, 6 July 2023

Line 69:

=== 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 journalbook|last1=Tarannikov|first1=Yuriy|last2=Korolev|first2=Peter|last3=Botev|first3=Anton|datetitle=Advances in Cryptology — ASIACRYPT 2001 |editor-last=Boyd|editor-first=Colin|titlechapter=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)-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" />