12,080
edits
Changes
Copy text from Wikipedia under GFDL : Revision of 19:18, 27 June 2006 by Jon Awbrey
In [[mathematics]], a '''finitary boolean function''' is a [[function (mathematics)|function]] of the form ''f'' : '''B'''<sup>''k''</sup> → '''B''', where '''B''' = {0, 1} is a ''[[boolean domain]]'' and where ''k'' is a nonnegative integer. In the case where ''k'' = 0, the "function" is simply a constant element of '''B'''.
More generally, a function of the form ''f'' : ''X'' → '''B''', where ''X'' is an arbitrary set, is a ''[[boolean-valued function]]''. If ''X'' = '''M''' = {1, 2, 3, …}, then ''f'' is a ''binary sequence'', that is, an infinite [[sequence]] of 0's and 1's. If ''X'' = [''k''] = {1, 2, 3, …, ''k''}, then ''f'' is ''binary sequence'' of length ''k''.
There are <math>2^{2^k}</math> such functions. These play a basic role in questions of [[complexity theory]] as well as the design of circuits and chips for [[digital computer]]s. The properties of boolean functions play a critical role in [[cryptography]], particularly in the design of [[symmetric key algorithm]]s (see [[S-box]]).
A '''boolean mask operation''' on boolean-valued functions combines values point-wise, for example, by [[exclusive disjunction|XOR]], or other [[boolean operator]]s.
==Algebraic Normal Form==
A boolean function can be written uniquely as a sum ([[exclusive disjunction|XOR]]) of products ([[logical conjunction|AND]]). This is known as the [[Algebraic Normal Form]] (ANF).
{| cellpadding="4"
|-
|<math>f(x_1, x_2, \ldots , x_n) = \!</math>
|<math>a_0 + \!</math>
|-
|
|<math>a_1x_1 + a_2x_2 + \ldots + a_nx_n + \!</math>
|-
|
|<math>a_{1,2}x_1x_2 + a_{n-1,n}x_{n-1}x_n + \!</math>
|-
|
|<math>\ldots + \!</math>
|-
|
|<math>a_{1,2,\ldots,n}x_1x_2\ldots x_n \!</math>
|}
The values of the sequence <math>a_0, a_1, \ldots, a_{1, 2, \ldots, n}</math> can therefore also uniquely represent a boolean function. The algebraic degree of a boolean function is defined as the highest number of <math>x_i</math> that appear in a product term. Thus <math>f(x_1, x_2, x_3) = x_1 + x_3</math> has degree 1 (linear), whereas <math>f(x_1, x_2, x_3) = x_1 + x_1 x_2 x_3</math> has degree 3 (cubic).
==See also==
{{col-begin}}
{{col-break}}
* [[Algebra of sets]]
* [[Boolean algebra]]
* [[List of Boolean algebra topics|Boolean algebra topics]]
{{col-break}}
* [[Boolean domain]]
* [[Boolean logic]]
* [[Boolean value]]
{{col-break}}
* [[Boolean-valued function]]
* [[Logical connective]]
* [[Truth function]]
* [[Zeroth order logic]]
{{col-end}}
==External links==
* [http://www.isi.qut.edu.au/people/fuller/ Boolean Planet] — boolean functions in cryptography.
==Document history==
Portions of the above article were adapted from the following sources under the [[GNU Free Documentation License]], under other applicable licenses, or by permission of the copyright holders.
* [http://www.getwiki.net/-Boolean_function Boolean function], [http://www.getwiki.net/ GetWiki].
* [http://wikinfo.org/index.php/Boolean_function Boolean function], [http://wikinfo.org/index.php/Main_Page Wikinfo].
* [http://en.wikipedia.org/wiki/Boolean_function Boolean function], [http://en.wikipedia.org/ Wikipedia].
[[Category:Boolean algebra]]
[[Category:Cryptography]]
[[Category:Logic]]
[[Category:Mathematics]]
More generally, a function of the form ''f'' : ''X'' → '''B''', where ''X'' is an arbitrary set, is a ''[[boolean-valued function]]''. If ''X'' = '''M''' = {1, 2, 3, …}, then ''f'' is a ''binary sequence'', that is, an infinite [[sequence]] of 0's and 1's. If ''X'' = [''k''] = {1, 2, 3, …, ''k''}, then ''f'' is ''binary sequence'' of length ''k''.
There are <math>2^{2^k}</math> such functions. These play a basic role in questions of [[complexity theory]] as well as the design of circuits and chips for [[digital computer]]s. The properties of boolean functions play a critical role in [[cryptography]], particularly in the design of [[symmetric key algorithm]]s (see [[S-box]]).
A '''boolean mask operation''' on boolean-valued functions combines values point-wise, for example, by [[exclusive disjunction|XOR]], or other [[boolean operator]]s.
==Algebraic Normal Form==
A boolean function can be written uniquely as a sum ([[exclusive disjunction|XOR]]) of products ([[logical conjunction|AND]]). This is known as the [[Algebraic Normal Form]] (ANF).
{| cellpadding="4"
|-
|<math>f(x_1, x_2, \ldots , x_n) = \!</math>
|<math>a_0 + \!</math>
|-
|
|<math>a_1x_1 + a_2x_2 + \ldots + a_nx_n + \!</math>
|-
|
|<math>a_{1,2}x_1x_2 + a_{n-1,n}x_{n-1}x_n + \!</math>
|-
|
|<math>\ldots + \!</math>
|-
|
|<math>a_{1,2,\ldots,n}x_1x_2\ldots x_n \!</math>
|}
The values of the sequence <math>a_0, a_1, \ldots, a_{1, 2, \ldots, n}</math> can therefore also uniquely represent a boolean function. The algebraic degree of a boolean function is defined as the highest number of <math>x_i</math> that appear in a product term. Thus <math>f(x_1, x_2, x_3) = x_1 + x_3</math> has degree 1 (linear), whereas <math>f(x_1, x_2, x_3) = x_1 + x_1 x_2 x_3</math> has degree 3 (cubic).
==See also==
{{col-begin}}
{{col-break}}
* [[Algebra of sets]]
* [[Boolean algebra]]
* [[List of Boolean algebra topics|Boolean algebra topics]]
{{col-break}}
* [[Boolean domain]]
* [[Boolean logic]]
* [[Boolean value]]
{{col-break}}
* [[Boolean-valued function]]
* [[Logical connective]]
* [[Truth function]]
* [[Zeroth order logic]]
{{col-end}}
==External links==
* [http://www.isi.qut.edu.au/people/fuller/ Boolean Planet] — boolean functions in cryptography.
==Document history==
Portions of the above article were adapted from the following sources under the [[GNU Free Documentation License]], under other applicable licenses, or by permission of the copyright holders.
* [http://www.getwiki.net/-Boolean_function Boolean function], [http://www.getwiki.net/ GetWiki].
* [http://wikinfo.org/index.php/Boolean_function Boolean function], [http://wikinfo.org/index.php/Main_Page Wikinfo].
* [http://en.wikipedia.org/wiki/Boolean_function Boolean function], [http://en.wikipedia.org/ Wikipedia].
[[Category:Boolean algebra]]
[[Category:Cryptography]]
[[Category:Logic]]
[[Category:Mathematics]]