Page 42 - Discrete Mathematics and Its Applications

1.2 Applications of Propositional Logic 21

¬p p p ∨ q p p ∧ q
p
q q
Inverter OR gate AND gate

FIGURE 1 Basic logic gates.

p p ∧ ¬q
q (p ∧ ¬q) ∨ ¬r
¬q
r
¬r

FIGURE 2 A combinatorial circuit.

Complicated digital circuits can be constructed from three basic circuits, called gates, shown
in Figure 1. The inverter,or NOT gate, takes an input bit p, and produces as output ¬p. The
OR gate takes two input signals p and q, each a bit, and produces as output the signal p ∨ q.
Finally, the AND gate takes two input signals p and q, each a bit, and produces as output the
signal p ∧ q. We use combinations of these three basic gates to build more complicated circuits,
such as that shown in Figure 2.
Given a circuit built from the basic logic gates and the inputs to the circuit, we determine
the output by tracing through the circuit, as Example 9 shows.

EXAMPLE 9 Determine the output for the combinatorial circuit in Figure 2.

Solution: In Figure 2 we display the output of each logic gate in the circuit. We see that theAND
gate takes input of p and ¬q, the output of the inverter with input q, and produces p ∧¬q.
Next, we note that the OR gate takes input p ∧¬q and ¬r, the output of the inverter with
input r, and produces the final output (p ∧¬q) ∨¬r. ▲

Suppose that we have a formula for the output of a digital circuit in terms of negations,
disjunctions, and conjunctions. Then, we can systematically build a digital circuit with the
desired output, as illustrated in Example 10.

EXAMPLE 10 Build a digital circuit that produces the output (p ∨¬r) ∧ (¬p ∨ (q ∨¬r)) when given input
bits p, q, and r.

Solution: To construct the desired circuit, we build separate circuits for p ∨¬r and for ¬p ∨
(q ∨¬r) and combine them using an AND gate. To construct a circuit for p ∨¬r, we use an
inverter to produce ¬r from the input r. Then, we use an OR gate to combine p and ¬r.To
build a circuit for ¬p ∨ (q ∨¬r), we first use an inverter to obtain ¬r. Then we use an OR gate
with inputs q and ¬r to obtain q ∨¬r. Finally, we use another inverter and an OR gate to get
¬p ∨ (q ∨¬r) from the inputs p and q ∨¬r.
To complete the construction, we employ a final AND gate, with inputs p ∨¬r and ¬p ∨
(q ∨¬r). The resulting circuit is displayed in Figure 3. ▲

We will study logic circuits in great detail in Chapter 12 in the context of Boolean algebra,
and with different notation.