The appendix covering logic design principles in P&H is relatively short and of shallow depth. This laboratory provides greater detail and fills in some of the gaps left by the cursory treatment this material is given in the text. Therefore, we begin by adding to the material discussed in the required reading.
P&H, Appendix B, Sections 1-3.
entries in a truth table for a
function with n inputs. (Hint: Use induction.) 
.
The brief discussion in P&H on logic gates introduces the symbols for
the basic AND, OR, and NOT (inverter) gates. There are more gates,
however, although the functions they represent should not be foreign
to a student in computer science. The standard symbols for 2-input
NAND, NOR, XOR and XNOR are depicted in Figure 
.
Figure: More logic gate representations.
Can gates have more than two inputs? Yes, but only if it makes sense, which is of course subjective. Generally, only the AND, OR, NAND and NOR gates can have two or more inputs. The logic functions for these gates are simply extended to more inputs (e.g. ANDing three inputs is easily defined) whereas the XOR or XNOR of more than two logic inputs does not make much sense. To draw the ``multi-input'' gates, just add more input lines.
Figure B.2 shows two simple logic circuits; notice that the inputs and outputs are labeled with variable names. If an input to a logic device is always one or always zero (high or low, respectively) then we simply write '1' or '0' at the input, rather than a variable name. A logic input is said to be ``active high'' when it performs a specified action it is high or '1' (using a positive-logic convention is assumed in this discussion). Similarly, we can have active low inputs as well. For example, we shall see later that some more complex devices such as decoders generally have ``enable'' inputs, which can be asserted active high or low. We shall assume that an input is active high unless otherwise specified. If we wish to indicate that an input is active low, we put a prefix of / in front of the name.
Page B-10 mentions the concept of two-level representation, which are implemented in two ways: sum-of-products (SOP) and product-of-sums (POS). We shall deal exclusively with the SOP representation, for convenience, unless otherwise noted. Read over the example on page B-11. The equation for D is an SOP expression derived directly from the truth table. Our engineering intuitions might prompt us to ask two questions at this point:
One technique for gate reduction is through the use of
Karnaugh maps, which graphically represent the values in a truth
table. Figure shows the Karnaugh maps (also know as
``K-maps'') for 2-,3-, and 4-variable functions.
Figure: K-maps for 2-, 3-, and 4-variable logic functions.
The labeling may seem a bit strange, but it does serve several purposes:
cells,
representing each line in a truth table. is the 3-variable
K-map for this truth table.
Figure: Example truth table and K-map.
Now reason for the funny ordering comes to light -- each cell is different from an adjacent cell by one variable! So what? Recall the combining theorem from the Preparatory Exercises section. If we use the general form of this theorem by considering A to be a logic function itself, then min-terms can be combined into a simpler form. Look at cell numbers 5 and 7. The two min-terms that they correspond to in the overall SOP expression are:
Now here's the quick way to get the same answer: if we take a close
look at the K-map, the area covering cells 5 and 7 are completely
contained in the area bracketed by both A and C. So the product
term is 
. It is easier to see if we circle the adjacent
cell pairs, as in Figure .
Figure: Example K-map with min-terms circled.
In fact, we must circle all min-terms to include all possible
ones. Notice that cells 1 and 5 are indeed adjacent, but what min-term
does this correspond to? The area covering cells 1 and 5 are
completely contained in the area bracketed by C and completely
outside B. The product term is therefore 
. The last min-term 
cannot be
reduced because it stands alone. Understand how to get the expression
for that min-term by visual inspection!
So the truth table yields this final expression: 
, which is
significantly smaller than the expression for the four individual
min-terms.
In general, the goal is to circle together as many terms as possible,
specifically rectangular sets of size cells contain 1s, taking
into account wrap-around. Look at Figure and
be sure to understand it (0s left out for simplicity):
Figure: Example K-map with min-terms circled.
In our final example (Figure ), we shall
demonstrate two rules of thumb:
Figure: Example K-map with min-terms circled.
Notice that cells 2, 4, and 14 are all only covered by one circle.
The result is cell 7 can be covered in one of two ways. either using
the circle representing 
or 
. We
should pick the former product term, because it has less variables.
But we don't need both. It would be redundant.
The book states, ``don't cares are important because they make it
easier to optimize the implementation of a logic function.'' We can
indeed use them in our K-maps, with the simple rule: if including a
don't care term in a circle reduces the number of product terms, use
it; otherwise leave it alone. Look at the example starting on page
B-16. Let's minimize the output function F with respect to the
inputs 
.
Figure: Function F: without and with don't cares.
(See Figure .) The K-map on the left is
derived from the truth table without don't cares. It cannot be
reduced because there are no adjacent cells. However, the K-map on
the right does possess don't care entries (marked as d's), and thus
simplifies the logic greatly (to just B + C, in fact). Notice the
don't care in cell 4 is not used, because it would require more logic
than we need (or care about).
where 
is the most significant bit),