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 {0,1}, and such that F also takes values in {0, 1}. A function on a general ___domain of a function taking values in {0, 1} would be 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, i.e. an infinite sequence of 0's and 1's; by restricting to { 1, 2, 3, ..., n } a Boolean function is in a natural way coded by a sequence of length n.

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

• list of Boolean algebra topics
• truth function

External links

• Boolean Planet — boolean functions in cryptography.