Boolean function

In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually {true, false}, {0,1} or {-1,1}).[1][2] Alternative names are switching function, used especially in older computer science literature,[3][4] and truth function (or logical function), used in logic. Boolean functions are the subject of Boolean algebra and switching theory.[5]

A Boolean function takes the form ${\displaystyle f:\{0,1\}^{k}\to \{0,1\}}$, where ${\displaystyle \{0,1\}}$ is known as the Boolean domain and ${\displaystyle k}$ is a non-negative integer called the arity of the function. In the case where ${\displaystyle k=0}$, the function is a constant element of ${\displaystyle \{0,1\}}$. A Boolean function with multiple outputs, ${\displaystyle f:\{0,1\}^{k}\to \{0,1\}^{m}}$ with ${\displaystyle m>1}$ is a vectorial or vector-valued Boolean function (an S-box in symmetric cryptography).[6]

There are ${\displaystyle 2^{2^{k}}}$ different Boolean functions with ${\displaystyle k}$ arguments; equal to the number of different truth tables with ${\displaystyle 2^{k}}$ entries.

Every ${\displaystyle k}$-ary Boolean function can be expressed as a propositional formula in ${\displaystyle k}$ variables ${\displaystyle x_{1},...,x_{k}}$, and two propositional formulas are logically equivalent if and only if they express the same Boolean function.