7.1   Boolean Logic


A boolean function is a mathematical function that maps arguments to a value, where the allowable values of range (the function arguments) and domain (the function value) are just one of two values— true and false (or 0 and 1). The study of boolean functions is known as Boolean logic.

Boolean functions.

To define any boolean function, we need only to specify its value for each possible value of its inputs. The not function is a boolean function of one variable.
$$ \quad\quad\quad\quad\quad\quad \begin{align} NOT(x) &\;=\; \begin{cases} 1 & \text {if $x$ is $0$} \\[1ex] 0 & \text {if $x$ is $1$} \end{cases} \end{align} $$
The and, or, and exclusive or functions are familiar boolean functions of two variables.
$$ \quad\quad\quad\quad\quad\quad \begin{align} AND(x, y) &\;=\; \begin{cases} 1 & \text {if both $x$ and $y$ are $1$} \\[1ex] 0 & \text {otherwise} \end{cases} \\ \\ OR(x, y) &\;=\; \begin{cases} 1 & \text {if either $x$ or $y$ (or both) is $1$} \\[1ex] 0 & \text {otherwise} \end{cases} \\ \\ XOR(x, y) &\;=\; \begin{cases} 1 & \text {if $x$ and $y$ are different} \\[1ex] 0 & \text {otherwise} \end{cases} \end{align} $$

Boolean functions of three or more variables.

As the number of variables increases, the number of possible functions increases dramatically. There are 28 different boolean functions of 3 variables, 216 functions of 4 variables, 232 functions of 5 variables, and so forth. Several such functions play a critical role in computation and in circuit design, so we will now consider them.