Boolean function

In mathematics, a boolean function is usually a function

F(b₁, b₂, ..., b_n)

of a number n of boolean variables b_i from the two-element boolean algebra B = {0, 1}, such that F also takes values in B. A function on an arbitrary set X taking values in B is called a boolean-valued function, so that boolean functions are a special case. Such a function with ___domain {1, 2, 3, …} is commonly called a binary sequence, that is, an infinite sequence of 0's and 1's. By restricting to {1, 2, 3, …, k } a boolean function is in a natural way coded by a 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 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

• Boolean algebra topics
• Truth function

External links

• Boolean Planet — boolean functions in cryptography.