A truth table can represent any Boolean function by enumerating the outputs for all possible combinations of inputs bits. However, it is perhaps hard to visualize how truth tables alone can ever enable the design of a complex digital processor like a calculator or a phone. As is often the case in engineering and science, mathematics supplies a toolkit to help us work efficiently. This toolkit is called Boolean algebra.
A logical statement in Boolean algebra consists of variables (truth table inputs) that are combined into an expression (truth table output) that is either TRUE (1) or FALSE (0) depending on the truth or falsity of the inputs.
The fundamental operations for combining variables in a logical statement are AND, OR, and NOT. The AND of two or more bits is TRUE if and only if all the bits are true. The OR of two or more bits is TRUE if at least one of the bits is true. The NOT operation applies only to a single bit, inverting the state of the bit from TRUE to FALSE or from FALSE to TRUE, Figure 1.4.1.
\(a\)
\(b\)
\(a\) AND \(b\)
0
0
0
0
1
0
1
0
0
1
1
1
\(a\)
\(b\)
\(a\) OR \(b\)
0
0
0
0
1
1
1
0
1
1
1
1
\(a\)
NOT \(a\)
0
1
1
0
Figure1.4.1.Truth tables for two-bit AND and OR operations, and for the NOT operation.
We will illustrate the AND, OR, and NOT operations by deriving a logical statement for the \(x \lt 2\) function from its truth table (recall Figure 1.3.1).
\(x\) (decimal)
\(x_1\)
\(x_0\)
\(y\)
0
0
0
1
1
0
1
1
2
1
0
0
3
1
1
0
There are two ways for the output \(y\) to be true:
\(x = (x_1, x_0) = 00\text{,}\) i.e., if \(x_1=0 \text{ AND } x_0=0\)
\(x = (x_1, x_0) = 01\text{,}\) i.e., if \(x_1=0 \text{ AND } x_0=1\)
Either of these statements—one or the other—is sufficient for the truth of \(y\text{.}\) We can combine them into one expression with OR:
\begin{equation*}
y = (x_1=0 \text{ AND } x_0=0) \text{ OR } (x_1=0 \text{ AND } x_0=1)
\end{equation*}
The AND and OR operations combine two or more Boolean statements to make a more complex statement. The NOT operation, on the other hand, operates on a single statement, changing it from TRUE to FALSE or from FALSE to TRUE. Using the NOT operation, we may replace “\(x_1=0\)” by “NOT( \(x_1=1\))”, replace “\(x_0=0\)” by “NOT( \(x_0=1\))”, and rewrite the expression in terms of positive assertions about the inputs.
\begin{equation*}
y = ( \text{NOT}(x_1=1) \text{ AND } \text{NOT}(x_0=1) ) \text{ OR } ( \text{NOT}(x_1=1) \text{ AND } x_0=1 )
\end{equation*}
Now observe: if \(x\) is TRUE, then the statement "\(x=1\)" is TRUE, and if \(x\) is FALSE, the statement "\(x=1\)" is FALSE. The additional effort of writing \(x_0=1\) and \(x_1=1\) in our expression is redundant. We can instead just write \(x_0\) and \(x_1\text{,}\) and the expression for \(x \lt 2\) becomes simpler:
\begin{equation*}
y = ( \text{NOT}(x_1) \text{ AND } \text{NOT}(x_0) ) \text{ OR } ( \text{NOT}(x_1) \text{ AND } x_0 )
\end{equation*}
There are simple notations for AND, OR, and NOT that enable us to dispense with the words. We denote AND and OR by the symbols \(\cdot\) and \(+\text{,}\) respectively, like the ordinary algebraic symbols for multiplication and addition. We denote NOT by a prime, \(x^\prime\text{.}\) With this notation, we can express any complex logical operation as a logic equation.
For example, for the \(x \lt 2\) function we began with the wordy
\begin{equation*}
y = (x_1=0 \text{ AND } x_0=0) \text{ OR } (x_1=0 \text{ AND } x_0=1)
\end{equation*}
and now have the more concise algebraic expression:
Check this for yourself by plugging in 0s and 1s for \(x_1\) and \(x_0\text{,}\) and recreating the truth table.
Now that you have been introduced to the AND, OR, and NOT operations, watch the truth table video all the way through.
The AND and OR operations are defined for any number of inputs, e.g., \(a \cdot b \cdot c\text{,}\)\(a + b + c + d\text{.}\) We call the AND of two or more logical variables, \(a \cdot b \cdot c\text{,}\) a product term. The OR of two or more product terms, like \(a \cdot b + c \cdot d\text{,}\) is called a sum of products. Writing a logic equation from the rows of a truth table naturally results in a sum of products.
The method is summarized here and in the video.
Identify all the rows in which the output is TRUE.
For each of these rows, form a product term from the inputs. For each input, \(x\text{,}\)
Write \(x\) in the product if \(x=1\) in the row.
Write \(x^\prime\) in the product if \(x=0\) in the row.
Omit \(x\) from the product if it is marked as “don’t care” (—) in the row.
OR the product terms together.
Practice.
Repeat the truth table exercises in the previous section, writing logic equations from the truth tables
Checkpoint1.4.2.
Write a logic equation for a function \(y = f(x)\) that asserts a single output bit if the two-bit input is an odd number (zero is neither even nor odd). The truth table is
\(n\) (decimal)
\(x_1\)
\(x_0\)
\(y\)
0
0
0
0
1
0
1
1
2
1
0
0
3
1
1
1
Solution.
Either \(x = 01\) or \(x = 11\) will make \(y=1\text{.}\) Write \({x_1}^\prime \cdot x_0\text{,}\)\(x_1 \cdot x_0\text{,}\) and combine them with OR,
