ic
Section 8.2 Logic Networks
639
Table 8.2 summarizes the behavior of the circuit. Substituting T for 1 and
F for 0 in the table results in the truth table for the logical connective of disjunction. Disjunction is an example of the Boolean algebra operation + in the realm of
propositional logic. Thus we may think of the circuit more abstractly as an electronic device that performs the Boolean operation +. Similarly, conjunction and
negation are examples of the Boolean algebra operations # and ′, respectively, in
the realm of propositional logic. Other devices perform these Boolean operations.
For example, switches connected in series would serve to implement the # operation;
both switches must be closed (x 1 = 1 and x 2 = 1) in order to have an output of 1.
However, we’ll ignore the details of implementing the devices; suffice it to say that
technology has progressed from mechanical switches through vacuum tubes and
then transistors to integrated circuits, and now even bacteria and DNA. We will
simply represent these devices by their standard symbols.
The Or gate, Figure 8.7a, behaves like the Boolean operation +. The aND
gate, Figure 8.7b, represents the Boolean operation # . Figure 8.7c shows an
inverter, corresponding to the unary Boolean operation ′. Because of the associativity property for + and # , the OR and AND gates can have more than two inputs.
x 1
x 1
x 2
x 1 + x 2
1
1
0
0
1
0
1
0
1
(a) OR gate
(b) AND gate
(c) Inverter
1
1
0
x 1 + x 2
x 2
x 1
x 1 + x 2
1
1
0
0
1
0
1
0
1
0
0
0
x 2
x 1
1
0
0
1
x' 1
x 1
x 2
x 1 . x 2
x 1
x' 1
figure 8.7
table 8.2
x 1
x 2 output
1
1
1
1
0
1
0
1
1
0
0
0
(The definition of a Boolean expression is another example of a recursive
definition; rule 1 is the basis step and rule 2 the inductive step.) When there
is no chance of confusion, we can omit the parentheses introduced by rule 2.
In addition, we define # to take precedence over + and ′ to take precedence
over + or # , so x 1 + x 2 # x 3 stands for x 1 + (x 2 # x 3 ) and x 1 + x 2
′ stands for
x 1 + (x 2
′); this convention also allows us to remove some parentheses. Finally, we
will generally omit the symbol # and use juxtaposition, so x 1 # x 2 is written x 1 x 2 .
Definition BooLeAn exPression
A boolean expression in n variables, x 1 , x 2 , … , x n , is any finite string of
symbols formed by applying the following rules:
1. x 1 , x 2 , … , x n , are Boolean expressions.
2. If P and Q are Boolean expressions, so are (P + Q), (P # Q), and (P′).
Boolean Expressions
Section 8.2 Logic Networks
639
Table 8.2 summarizes the behavior of the circuit. Substituting T for 1 and
F for 0 in the table results in the truth table for the logical connective of disjunction. Disjunction is an example of the Boolean algebra operation + in the realm of
propositional logic. Thus we may think of the circuit more abstractly as an electronic device that performs the Boolean operation +. Similarly, conjunction and
negation are examples of the Boolean algebra operations # and ′, respectively, in
the realm of propositional logic. Other devices perform these Boolean operations.
For example, switches connected in series would serve to implement the # operation;
both switches must be closed (x 1 = 1 and x 2 = 1) in order to have an output of 1.
However, we’ll ignore the details of implementing the devices; suffice it to say that
technology has progressed from mechanical switches through vacuum tubes and
then transistors to integrated circuits, and now even bacteria and DNA. We will
simply represent these devices by their standard symbols.
The Or gate, Figure 8.7a, behaves like the Boolean operation +. The aND
gate, Figure 8.7b, represents the Boolean operation # . Figure 8.7c shows an
inverter, corresponding to the unary Boolean operation ′. Because of the associativity property for + and # , the OR and AND gates can have more than two inputs.
x 1
x 1
x 2
x 1 + x 2
1
1
0
0
1
0
1
0
1
(a) OR gate
(b) AND gate
(c) Inverter
1
1
0
x 1 + x 2
x 2
x 1
x 1 + x 2
1
1
0
0
1
0
1
0
1
0
0
0
x 2
x 1
1
0
0
1
x' 1
x 1
x 2
x 1 . x 2
x 1
x' 1
figure 8.7
table 8.2
x 1
x 2 output
1
1
1
1
0
1
0
1
1
0
0
0
(The definition of a Boolean expression is another example of a recursive
definition; rule 1 is the basis step and rule 2 the inductive step.) When there
is no chance of confusion, we can omit the parentheses introduced by rule 2.
In addition, we define # to take precedence over + and ′ to take precedence
over + or # , so x 1 + x 2 # x 3 stands for x 1 + (x 2 # x 3 ) and x 1 + x 2
′ stands for
x 1 + (x 2
′); this convention also allows us to remove some parentheses. Finally, we
will generally omit the symbol # and use juxtaposition, so x 1 # x 2 is written x 1 x 2 .
Definition BooLeAn exPression
A boolean expression in n variables, x 1 , x 2 , … , x n , is any finite string of
symbols formed by applying the following rules:
1. x 1 , x 2 , … , x n , are Boolean expressions.
2. If P and Q are Boolean expressions, so are (P + Q), (P # Q), and (P′).
Boolean Expressions