Boolean function

Logical connectives
NOT ${\displaystyle \neg A}$, ${\displaystyle -A}$, ${\displaystyle {\overline {A}}}$, ${\displaystyle \sim A}$ AND ${\displaystyle A\land B}$, ${\displaystyle A\cdot B}$, ${\displaystyle AB}$, ${\displaystyle A\&B}$, ${\displaystyle A\&\&B}$ NAND ${\displaystyle A{\overline {\land }}B}$, ${\displaystyle A\uparrow B}$, ${\displaystyle A\mid B}$, ${\displaystyle {\overline {A\cdot B}}}$ OR ${\displaystyle A\lor B}$, ${\displaystyle A+B}$, ${\displaystyle A\mid B}$, ${\displaystyle A\parallel B}$ NOR ${\displaystyle A{\overline {\lor }}B}$, ${\displaystyle A\downarrow B}$, ${\displaystyle {\overline {A+B}}}$ XNOR ${\displaystyle A\ {\text{XNOR}}\ B}$ └ equivalent ${\displaystyle A\equiv B}$, ${\displaystyle A\Leftrightarrow B}$, ${\displaystyle A\leftrightharpoons B}$ XOR ${\displaystyle A{\underline {\lor }}B}$, ${\displaystyle A\oplus B}$ └nonequivalent ${\displaystyle A\not \equiv B}$, ${\displaystyle A\not \Leftrightarrow B}$, ${\displaystyle A\nleftrightarrow B}$ implies ${\displaystyle A\Rightarrow B}$, ${\displaystyle A\supset B}$, ${\displaystyle A\rightarrow B}$ converse ${\displaystyle A\Leftarrow B}$, ${\displaystyle A\subset B}$, ${\displaystyle A\leftarrow B}$
Related concepts
Propositional calculus Predicate logic Boolean algebra Truth table Truth function Boolean function Functional completeness Scope (logic)
Applications
Digital logic Programming languages Mathematical logic Philosophy of logic
Category
v t e

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.