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 = ^* = {1, 2, 3, …, k}, then f is binary sequence of length k.

There are $2^\{2^k\}$ 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).

The values of the sequence $a\_0,a\_1,\backslash ldots,a\_\{1,2,\backslash ldots,n\}$ can therefore also uniquely represent a boolean function. The algebraic degree of a boolean function is defined as the highest number of $x\_i$ that appear in a product term. Thus $f(x\_1,x\_2,x\_3)\; =\; x\_1\; +\; x\_3$ has degree 1 (linear), whereas $f(x\_1,x\_2,x\_3)\; =\; x\_1\; +\; x\_1x\_2x\_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.

Boolean algebra | Cryptography

Boolesche Funktion | Función lógica | Fonction booléenne | Funzione booleana | 布尔函数