(
at least some)
Boolean expressions can be represented by logic gates and vice versa. Actually, all Boolean functions can be implemented in terms of AND, OR, and NOT gates. Because of this close relationship between the laws of Boolean algebra and the behavior of logic gates, theorems that are true for Boolean algebra can also be used to transform digital logic into simpler forms. {+}
and {
and a unary operation { ' }, such that the following axioms hold: a+
b is in B
a b is in B
a+
b=
b+
a
a b=
b a
(
a+
b)
+
c=
a+
(
b+
c) =
a+
b+
c
(
a b)
c=
a(
b c) =
a b c
{+}
, designated by 0, such that a +
0 =
a for every a in B.{
, designated by 1, such that a 1 =
a for every a in B. a+
(
b c)
=
(
a+
b)
(
a+
c)
a(
b+
c)
=
(
a b)
+ (
a c)
(
the complement of a)
such that aNote: We use A' and interchangeably to represent complement in this chapter.+
a'=
1
a a'=
0
=
{
0, 1}
and the logical operations OR, AND, and NOT satisfy all the axioms of a Boolean algebra. Simply substitute 0 and 1 for a and b, OR for +
, AND for , and NOT for ', and show that the expressions are true. For example, to verify the commutative law for +
: A Boolean function uniquely maps some number of inputs over the set0 +
1=
1+
0 0 1=
1 0 1=
1 0=
0
{
0, 1}
into the set {
0, 1}
. A Boolean expression is an algebraic statement containing Boolean variables and operators. A theorem in Boolean algebra states that any Boolean function can be expressed in terms of AND, OR, and NOT operations. For example, in Section 1.3.3 we saw one way to map a truth table into a Boolean expression in the sum (
OR)
of products (
AND)
form. Take the Boolean expression . A version of the expression with parentheses would be .
Each pair of parentheses represents the expression generated by a single gate. Thus, the circuit is built up through a set of intermediate results, from the inside out:
The gate-level implementation is shown in Figure 2.4(
a)
, using two input gates. The primitive gates need not be limited to two inputs, however. Figure 2.4(
b)
shows the same circuit implemented using a three-input AND gate. These implementations are equivalent because of the associative law of Boolean algebra.
Each appearance of a variable or its complement in an expression is called a literal. In the preceding expression, we can see that there are four variables and four literals. The following expression has 10 literals but only three variables (
A, B, and C)
: Each literal represents the connection of a variable or its complement to a unique gate input.
The constant functions 0 and 1 and the functions X, , Y, X Y, and X +
Y represent only half of the possible functions. We now introduce the remaining Boolean operators.
NAND and NOR Two of the most frequently encountered Boolean operators are NAND (
not AND)
and NOR (
not OR)
. Their gate, truth table, and logical switch representations are shown in Figure 2.6 and Figure 2.7. The NAND operation behaves as if an AND is composed with a NOT: it yields a logic 0 in the truth table rows where AND is a 1, and it yields a 1 in the rows where AND is 0. The gate representation is an AND gate with a small circle or "bubble" at its output, denoting negation.
If you take a close look at the logic switch representation in Figure 2.6 and compare it to Figure 2.2, you will see that it looks like an AND function with the true and false inputs reversed. NAND is true, and a switching path exists from true to the output, when either X is 0 (
the top normally closed switch is closed)
or Y is 0 (
the bottom normally closed switch is closed)
. Alternatively, it is false when X and Y are both true, closing the path from false to the output.
NOR behaves in a similar fashion, but now with respect to OR. Once again the truth table outputs are complemented, and we draw the NOR gate as an OR gate with a bubble at the output. The switch representation in Figure 2.7 shows a topology like the OR gate of Figure 2.3, with the true and false inputs reversed. Both X and Y must be zero to close the normally closed switches and establish the path from true to the output.
NAND and NOR gates far outnumber AND and OR gates in a typical digital design, even though these functions are less intuitive. For electrical reasons, revealed in more detail in Appendix B, normally open switches are better at passing low voltages than high voltages. For example, 0 V at one side of the switch will yield close to 0 V at the other, but 5 V will yield approximately 3.5 V at the other side. The opposite behavior is true about normally closed switches. Thus, the switch configurations of Figures 2.6 and 2.7 are better behaved electrically than those of Figures 2.2 and 2.3.
Since any Boolean expression can be represented in terms of AND, OR, and NOT gates, it is hardly surprising that the same statement can be made about NAND, NOR, and NOT gates. In fact, NOT gates are superfluous: if you carefully examine the truth tables of Figures 2.6 and 2.7, you'll see that NAND and NOR act like NOT when both inputs are identically 0 or 1. We shall see an efficient method for mapping Boolean expressions into NAND and NOR logic in Section 2.2.2.
XOR/XNOR This leaves six functions still unnamed in Figure 2.5. Two of these, frequently of use, are exclusive OR (
XOR, also known as the inequality gate or difference function)
and exclusive NOR (
XNOR, also known as the equality gate or coincidence function)
. Their truth tables and gate representations are given in Figure 2.8.
XOR is true when its inputs differ in value. XNOR is true when its inputs coincide in value. The Boolean operator for XOR is Ý; XNOR is usually represented as the complement of XOR. As with any Boolean function, these can be implemented in terms of AND, OR, and NOT operations:
If you examine the truth table of Figure 2.8XOR: XNOR:
(
a)
, you can see that XOR is precisely the function needed to implement the half adder sum of Chapter 1! (
written X \xde Y)
is true under two -conditions: either X is false or both X and Y are true. The four remaining functions become X \xde Y, Y \xde X, NOT (
X \xde Y)
, and NOT (
Y \xde X)
. These are not commonly found as primitives readily available for realizing digital systems, so they won't be of much use to you. The timing waveforms for the common functions, AND, OR, NAND, NOR, XOR, and XNOR, are shown in Figure 2.9. The figure assumes a single-time-unit gate delay in computing new outputs from inputs.
Example
To illustrate the trade-offs just discussed, consider the following three-variable Boolean function: (
a)
. You would probably implement the function directly from the preceding equation, using three NOT gates, four 3-input AND gates, and a single 4-input OR gate. This is called a two-level implementation, with variables and their complements at the zeroth level, AND gates at the first level, and an OR gate at the second level.
You could implement the same truth table with fewer gates. An alternative two-level implementation is given in Figure 2.9(
b)
as function Z1:
It uses the same number of inverters and OR gates but only three AND gates. The original function has 12 literals. This alternative has only seven, thus reducing the wiring complexity.
The implementation of function Z2 is called multilevel:
The longest path from an input to an output passes through four gates. This contrasts with three gate delays in the two-level functions. In terms of gate counts, the circuit uses two rather than three inverters and only two-input AND and OR gates. Here you can see a trade-off between gate count and performance: Z2 uses simpler gates, but it is not as fast as Z1.
Z3 shows a third realization that uses an XOR gate:
XOR is sometimes called a complex gate, because you normally implement it by combining several NAND or NOR gates. Although this implementation has the lowest gate count, it is also likely to have the worst signal delay. An XOR gate tends to be slow compared with the implementations for Z based on simple AND and OR gates.
Figure 2.11 shows the timing waveforms for the three circuit alternatives, assuming (
somewhat unrealistically)
a single time unit delay per gate. All have equivalent behavior, although they exhibit slightly different propagation delays. All three circuits show a glitch on the transition ABC =
1 0 1 to ABC =
1 1 0.