Boolean function

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 ${\displaystyle 2^{2^{n}}}$ 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).

${\displaystyle f(x_{1},x_{2},\ldots ,x_{n})=\!}$	${\displaystyle a_{0}+\!}$
	${\displaystyle a_{1}x_{1}+a_{2}x_{2}+\ldots +a_{n}x_{n}+\!}$
	${\displaystyle a_{1,2}x_{1}x_{2}+a_{n-1,n}x_{n-1}x_{n}+\!}$
	${\displaystyle \ldots +\!}$
	${\displaystyle a_{1,2,\ldots ,n}x_{1}x_{2}\ldots x_{n}\!}$

The values of the sequence ${\displaystyle 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 ${\displaystyle x_{i}}$  that appear in a product term. Thus ${\displaystyle f(x_{1},x_{2},x_{3})=x_{1}+x_{3}}$  has degree 1 (linear), whereas ${\displaystyle f(x_{1},x_{2},x_{3})=x_{1}+x_{1}x_{2}x_{3}}$  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.