Discrete Mathematics for Computer Science

98 CHAPTER 2 Formal Logic

2.1.4 Using Gates to Represent Formulas

At the basic hardware level, computer memory has two states, which are identified as the

two logical values or boolean values of T and F. Computer operations are thought of as

being composed of operations on these boolean values and, hence, as operations of propo-

sitional logic. In describing computer circuits, a specialized notation for propositional logic

is used. Special physical devices, called gates, implement the A, v, and - operations. A set

of gates to represent a circuit is called a combinatorial circuit or combinatorial network.

Think of a gate as representing an operation and of the wires going into the gates as

representing its operands. For example, a A gate will let current flow out if and only if both

operands (that is, both wires coming in) carry current. Notation for these gates is shown in

Figure 2.5.

pvq p pv q p -11 -- q

q q

Figure2.5 AND, OR, and NOT gates.

A combinatorial circuit is, roughly, the analogue of a formula. Boolean circuit nota-

tion for the formula

((p A q) A r)

is shown in Figure 2.6.

pqq (p~q)^rr

r

Figure 2.6 AND gates.

For the formula

((p A p) A p),

instead of having three separate p's as in an expression tree, the gate to represent it has one

line that splits, as shown in Figure 2.7.

(P~)^p

P

Figure 2.7 Another form of AND gates.

Since gates are used to describe computer circuits that will be implemented in a device

or printed on a chip, it is common to represent more than one formula in the same diagram,

as shown in Figure 2.8. The arrow in Figure 2.8 indicates that the output from gate C is

an input for both gates A and B. Each of the "output wires" (A and B) corresponds to the

output of a different propositional formula, as described earlier.