Boolean function

From CryptoDox, The Online Encyclopedia on Cryptography and Information Security

A Boolean function describes how to determine a Boolean value output based on some logical calculation from Boolean inputs. 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).

1 Algebraic Normal Form
2 Finitary Boolean Function
3 Efficient Representations
4 See also
5 External links

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_{1,2}x_1x_2 + a_{1,3}x_1x_3 + \ldots + a_{n-1,n}x_{n-1}x_n + \!$
	$\ldots + \!$
	$a_{1,2,\ldots,n}x_1x_2\ldots x_n \!$

where $a_0, a_1, \ldots, a_{1,2,\ldots,n} \in \{0,1\}^*$ .

The values of the sequence $a_0,a_1,\ldots,a_{1,2,\ldots,n}$ 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 1 x 2 x 3$ has degree 3 (cubic).

Finitary Boolean Function

Template:Technical (expert)

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 a binary sequence of length k.