638
Boolean Algebra and Computer Logic
30. a. Let n be a positive integer and consider B to be the set of all positive integer divisors of n. Prove that
(B, d) is a partially ordered set where x d y means x 0 y.
In the terminology of Exercise 29, the least upper bound of x and y is the least common multiple of x and
y, and the greatest lower bound is the greatest common divisor. (B, d) is a distributive lattice.
b. Prove that for n = 6, (B, d) is a Boolean algebra. (Hint: 1 is the least element and 6 is the greatest
element).
c. For n = 8, (B, d) is not a Boolean algebra.
(i) Show that this is true by using the definition of a Boolean algebra.
(ii) Show that this is true by using Exercise 6.
S e c t i o n 8 . 2 logiC net workS
Combinational networks
Basic Logic Elements
In 1938 the American mathematician Claude Shannon perceived the parallel between propositional logic and circuit logic and realized that Boolean algebra could
play a part in systematizing this new realm of electronics.
Let us imagine that the electrical voltages carried along wires fall into one
of two ranges, high or low, which we represent by 1 and 0, respectively. Voltage
fluctuations within these ranges are ignored, so we are forcing a discrete, indeed
binary, mask on an analog phenomenon. We also suppose that switches can be
wired so that a signal of 1 causes the switch to be closed and a signal of 0 causes
the switch to be open (Figure 8.5). Now we combine two such switches, controlled
by lines x 1 and x 2 , in parallel. If either or both lines carry a 1 value, one or both
of the switches will be closed, and the output line will have a value of 1. However,
values of x 1 = 0 and x 2 = 0 will cause both switches to be open and thus break the
circuit, so that the voltage level on the output line will be 0. Figure 8.6 illustrates
the various cases.
x = 1
x = 0
Closed switch
Open switch
figure 8.5
x 2 = 1
x 1 = 1
1
x 2 = 1
x 1 = 0
1
x 1 = 0
x 2 = 0
x 2 = 0
x 1 = 1
1
0
figure 8.6
Boolean Algebra and Computer Logic
30. a. Let n be a positive integer and consider B to be the set of all positive integer divisors of n. Prove that
(B, d) is a partially ordered set where x d y means x 0 y.
In the terminology of Exercise 29, the least upper bound of x and y is the least common multiple of x and
y, and the greatest lower bound is the greatest common divisor. (B, d) is a distributive lattice.
b. Prove that for n = 6, (B, d) is a Boolean algebra. (Hint: 1 is the least element and 6 is the greatest
element).
c. For n = 8, (B, d) is not a Boolean algebra.
(i) Show that this is true by using the definition of a Boolean algebra.
(ii) Show that this is true by using Exercise 6.
S e c t i o n 8 . 2 logiC net workS
Combinational networks
Basic Logic Elements
In 1938 the American mathematician Claude Shannon perceived the parallel between propositional logic and circuit logic and realized that Boolean algebra could
play a part in systematizing this new realm of electronics.
Let us imagine that the electrical voltages carried along wires fall into one
of two ranges, high or low, which we represent by 1 and 0, respectively. Voltage
fluctuations within these ranges are ignored, so we are forcing a discrete, indeed
binary, mask on an analog phenomenon. We also suppose that switches can be
wired so that a signal of 1 causes the switch to be closed and a signal of 0 causes
the switch to be open (Figure 8.5). Now we combine two such switches, controlled
by lines x 1 and x 2 , in parallel. If either or both lines carry a 1 value, one or both
of the switches will be closed, and the output line will have a value of 1. However,
values of x 1 = 0 and x 2 = 0 will cause both switches to be open and thus break the
circuit, so that the voltage level on the output line will be 0. Figure 8.6 illustrates
the various cases.
x = 1
x = 0
Closed switch
Open switch
figure 8.5
x 2 = 1
x 1 = 1
1
x 2 = 1
x 1 = 0
1
x 1 = 0
x 2 = 0
x 2 = 0
x 1 = 1
1
0
figure 8.6