Discrete Mathematics

76 DISCRETE MATHEMATIC..._

________________________

_

Fig.

1.6:

An

expression tree

for

the

Boolean expression:

((p

1\

q)

v ( -,p

1\

-.q))

In Fig. 1.6, we can see that the root

of

the tree (the circle at the top) is an OR, which is the last operation

to

be

applied. It is applied to two ANDs, which are its left and right children.

If

we replace the circles with AND gates,

OR

gates, and

NOT

gates, then we will get the circuit

in

Fig. 1.7. The only difference (which is fairly minor) is that p and q are

in

one

location and there are wires (the

black lines) that connect the circuit. The boolean expression for the output

of

the circuit is placed ...