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 operator).

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})=a_{0}\oplus a_{1}x_{1}\oplus a_{2}x_{2}\oplus \ldots \oplus a_{n}x_{n}\oplus a_{1,2}x_{1}x_{2}\oplus a_{n-1,n}x_{n-1}x_{n}\oplus \ldots \oplus a_{1,2,\ldots ,n}x_{1}x_{2}\ldots x_{n}}$ 

See also

• Boolean algebra topics
• Truth function

External links

• Boolean Planet — boolean functions in cryptography.