Discrete Mathematics for Computer Science

Truth and Logical Truth 113

Gates and Boolean Algebra

In Section 1.3.5, the axiom system for a boolean algebra was introduced. Example 10
showed that if B is a set of elements with values from {0, 11, and with the operations A and
V defined as

V^0 1 A^0 1

0 0 1 0 0 0

1 1 1 1 0 1

then B with A as meet and V as join forms a boolean algebra.
If we interpret the operation of v as the logical operation of OR and A as the logical
operation of AND as well as substitute T for 1 and F for 0, then these operation tables
are just the tables of AND and OR introduced in Table 2.3. The logical value T satisfies

the conditions for T, whereas F satisfies the conditions for _L. Finally, if we interpret

complementation as -x, then the conditions for complements hold. What all this means
is that there are two different but equivalent ways to represent a circuit. The first is to draw
the gates, as shown in Figure 2.11.

q

Sum

Figure 2.11 Half-adder.

The second is to represent the gates as boolean operations and the whole gate structure as
a boolean expression. In Figure 2.12, we show a circuit and its equivalent boolean expres-
sion.

P ý pA q (-p A q) v (p A -q) v (p A q)

q

p q

q

Figure 2.12 Gates for (-p A q) V (p A -q) V (p A q).

The power of this alternate representation is shown in Example 11 where we use
logic-which we can also think of as boolean algebra-to find a simpler expression to
represent this set of gates.