Boolean function
Encyclopedia : B : BO : BOO : Boolean function
In mathematics, a finitary boolean function is a function of the form f : Bk → B, where B = 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 = , then f is a binary sequence, that is, an infinite sequence of 0's and 1's. If X = [k] = , then f is binary sequence of length k.
There are [2^] 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).
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).
| [f(x_1, x_2, \ldots , x_n) = \!] | [a_0 + \!] |
| [a_1x_1 + a_2x_2 + \ldots + a_nx_n + \!] | |
| [a_x_1x_2 + a_x_x_n + \!] | |
| [\ldots + \!] | |
| [a_x_1x_2\ldots x_n \!] |
The values of the sequence [a_0,a_1,\ldots,a_] can therefore also uniquely represent a boolean function. The algebraic degree of a boolean function is defined as the highest number of [x_i] that appear in a product term. Thus [f(x_1,x_2,x_3) = x_1 + x_3] has degree 1 (linear), whereas [f(x_1,x_2,x_3) = x_1 + x_1x_2x_3] has degree 3 (cubic).