Boolean function

From Wikinfo

In mathematics, a finitary boolean function is a function of the form f : B^k → 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 computers. The properties of boolean functions play a critical role in cryptography, particularly in the design of symmetric key algorithms (see S-box).

A boolean mask operation on boolean-valued functions combines values point-wise (for example, by XOR, or other boolean operators).

Contents 1 Algebraic Normal Form 2 See also 3 External links 3.1 References

Algebraic Normal Form

A boolean function can be written uniquely as a sum (XOR) of products (AND). This is known as the Algebraic Normal Form (ANF).

<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_1x_2x_3</math> has degree 3 (cubic).

See also

Algebra of sets Boolean algebra Boolean algebra topics

Boolean domain Boolean logic Boolean value

Boolean-valued function Logical connective Truth function Zeroth order logic

External links

• Boolean Planet � boolean functions in cryptography.[[es:Funci�n l�gica]]

[[fr:Fonction bool�enne]]

References

• Adapted from the Wikipedia article, "Boolean_function" http://en.wikipedia.org/wiki/Boolean_function, used under the GNU Free Documentation License