Boolean Functions

Definition¹

The following function is called a Boolean function. For $n \in \mathbb{N}$,

$$ f : \left\{ 0, 1 \right\}^{n} \to \left\{ 0, 1 \right\} $$

Here, $1 =$ means true, and $0 =$ means false.

Generalization

For $n, m \in \mathbb{N} (m \gt 2)$,

$$ f : \left\{ 0, 1 \right\}^{n} \to \left\{ 0, 1 \right\}^{m} $$

This is called a vector-valued Boolean function.

Explanation

Named after the British mathematician George Boole. George Boole was the founder of Boolean algebra, and by algebraically dealing with logic, he greatly influenced symbolic logic.

The Boolean function is also called a Boolean operation or a logical operation/connective.

In computer theory, since $1$ and $0$ respectively mean the presence and absence of an electrical signal, they are referred to as gates due to the understanding that electrical signals come in and out. Therefore, the combination of multiple gates is called a circuit.

Reversible Functions

According to Landauer’s principle, energy is used every time information is lost, thus, there is an interest in one-to-one Boolean functions from a computing efficiency aspect. One-to-one Boolean functions are called reversible, and those that are not are called non reversible. To be reversible, it must naturally be $m=n$. The reversible functions include the following.

• $\operatorname{CNOT}$ Gate
• Toffoli Gate
• Fredkin Gate

Types

• $\text{AND}$ Gate
• $\text{OR}$ Gate
• $\text{NOT}$ Gate
• $\text{XOR}$ Gate
• $\text{NAND}$ Gate
• $\text{NOR}$ Gate
  ${}$
• Cloning function $\text{cl}$
• Projection $p_{i}$
• Injection $\imath_{i}$, $\jmath_{i}$