642
Boolean Algebra and Computer Logic
Logic networks constructed of AND gates, OR gates, and inverters are also
called combinational networks. They have several features that we should note.
First, input or output lines are not tied together except by passing through gates.
Lines can be split, however, to serve as input to more than one device. There are
no loops where the output of an element is part of the input to that same element.
Finally, the output of a network is an instantaneous function of the input; there are
no delay elements that capture and remember input signals. Notice also that the
picture of any network is, in effect, a directed graph.
Canonical Form
Here is the situation so far (arrows indicate a procedure that we can carry out):
truth function d Boolean expression 4 logic network
We can write a unique truth function from either a network or an expression.
Given an expression, we can find a network with the same truth function, and
conversely. The last part of the puzzle concerns how to get from an arbitrary truth
function to an expression (and hence a network) having that truth function. An
algorithm to solve this problem is explained in the next example.
example 13
Suppose we want to find a Boolean expression for the truth function f of Table 8.4.
There are four rows in the table (rows 1, 3, 4, and 7) for which f is 1. The basic
form of our expression will be a sum of four terms
( ) + ( ) + ( ) + ( )
such that the first term has the value 1 for the input values of row 1 and for no others, the second term has the value 1 for the input values of row 3 and for no others,
and so on. Thus, the entire expression has the value 1 for these inputs and for no
others—precisely what we want. (Other inputs cause each term in the sum, and
hence the sum itself, to be 0.)
table 8.4
x 1
x 2
x 3
f(x 1 , x 2 , x 3 )
1
1
1
1
1
1
0
0
1
0
1
1
1
0
0
1
0
1
1
0
0
1
0
0
0
0
1
1
0
0
0
0