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

See also

• Boolean algebra topics
• Truth function

External links

• Boolean Planet — boolean functions in cryptography.