# 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

`(or`

*false*`and`

*0*`). The study of boolean functions is known as`

*1**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} $$

*Notation.*There are many competing notations for elementary boolean functions. In this chapter, we primarily use the circuit-design notation.*Truth tables.*One way to define a boolean function is to specify its value for each possible value of its arguments. We use a*truth table*to do so in an organized way. A truth table has one column for each variable, one row for each possible combination of variable values, and a column that specifies the value of the function for that combination.*n*variables has 2^{n}rows.*Boolean algebra.*Boolean algebra refers to symbolic manipulation of expressions made up of boolean variables and boolean operators. The familiar*identity*,*commutative*,*distributive*, and*associative*axioms from algebra define the axioms of Boolean algebra, along with the two*complementary*axioms.*DeMorgan’s laws*.*Boolean algebra in Java.*You can incorporate Boolean algebra into your Java programs, in two different ways.- Java’s boolean data type: In Section 1.2, we introduced boolean operations
with the values
and*true*and the*false*,*AND*, and*OR*operations using the operators*NOT*`&&`,`||`, and`!`, respectively. - Bitwise operations on integer values: In Section 6.1, we discussed Java’s bitwise
operations, which use the
,*AND*,*OR*, and*NOT*operators on each bit in the binary representations of integer values, using the operators*XOR*`&`,`|`,`~`, and`^`, respectively.

- Java’s boolean data type: In Section 1.2, we introduced boolean operations
with the values

## Boolean functions of three or more variables.

As the number of variables increases, the number of possible functions increases dramatically. There are 2^{8}different boolean functions of 3 variables, 2

^{16}functions of 4 variables, 2

^{32}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.

*AND and OR functions.*The definitions of theand*AND*functions for multiple arguments generalize in a natural way from our two-argument definitions:*OR*$$ \quad\quad\quad\quad\quad\quad \begin{align} AND(x_1, x_2, \ldots, x_n) &\;=\; \begin{cases} 1 & \text {if all arguments are $1$} \\[1ex] 0 & \text {otherwise} \end{cases} \\ \\ OR(x_1, x_2, \ldots, x_n) &\;=\; \begin{cases} 1 & \text {if any argument is $1$} \\[1ex] 0 & \text {otherwise} \end{cases} \\ \end{align} $$

*Majority and odd-parity functions.*We consider two additional functions that arise in the design of digital circuits: the*majority*and*odd-parity*functions:$$ \quad\quad\quad\quad\quad\quad \begin{align} MAJ(x_1, x_2, \ldots, x_n) &\;=\; \begin{cases} 1 & \text {if strictly more arguments are $1$ than 0} \\[1ex] 0 & \text {otherwise} \end{cases} \\ \\ ODD(x_1, x_2, \ldots, x_n) &\;=\; \begin{cases} 1 & \text {if an odd number of arguments are $1$} \\[1ex] 0 & \text {otherwise} \end{cases} \\ \end{align} $$

*Boolean expressions.*As with boolean functions of two variables, we can use a truth table to explicitly specify a boolean function.*n*variables is 2^{n}. Instead, we often prefer to use*boolean expressions*to define boolean functions. For example, it is not hard to verify these two identities:$$ \quad\quad\quad\quad\quad\quad \begin{align} AND(x_1, x_2, \ldots, x_n) &\;=\; x_1 x_2 \ldots x_n \\ \\ OR(x_1, x_2, \ldots, x_n) &\;=\; x_1 + x_2 + \ldots + x_n \end{align} $$

*Sum-of-products representations.*One of the fundamental results of Boolean algebra is that every boolean function can be represented with an expression that uses,*AND*, and*OR*operators and no others. For example, consider the following truth table:*NOT*$$\quad\quad\quad\quad\quad\quad MAJ(x, y, z) = x'yz + xy'z + xyz' + xyz$$

We can derive such an expression for any boolean function from its truth table: For each of the rows in the truth table in which the function value is 1, we create a term that is 1 if the input variables have the values on that row and 0 otherwise. Each term is the product of each input variable (if its corresponding entry on the row in question is 1) or its negation (if the entry is 0). The sum of all of these terms gives back the function.The boolean expression that we construct is known as the

*sum-of-products representation*or the*disjunctive normal form*of the function. As another example, here is the table for the odd parity function: