628
Boolean Algebra and Computer Logic
Isomorphism as Applied to Boolean Algebra
Now let’s determine specifically what is involved when two instances of a Boolean
algebra are isomorphic. Suppose we have two Boolean algebras, 3B, +, # , ′, 0, 14
and 3b, &, *, ″, f, 14. This notation means that, for example, if x is in B, x′ is
the result of performing on x the unary operation defined in B, and if z is an element of b, z″ is the result of performing on z the unary operation defined in b.
How would we define isomorphism between these two Boolean algebras? First,
we would need a bijection f from B onto b. Then f must preserve in b the effects of
the various operations in B. There are three operations, so we use three equations
to express these preservations. To preserve the operation +, we want to be able to
operate using + on two elements in B and then map the result to b, or to map the
two elements to b and operate using the corresponding operation & on the results
there. (Think “operate and map = map and operate.”) Thus, for x and y in B, we
require
f (x + y) = f (x) & f ( y)
PraCtiCe 5
a. Write the equation requiring f to preserve the effect of the binary operation # .
b. Write the equation requiring f to preserve the effect of the unary operation ′.
■
b
d
e
f
c
a
Map
Operate
Operate
(a)
b
d
a
Map
Map
(b)
figure 8.3
figure 8.4
Boolean Algebra and Computer Logic
Isomorphism as Applied to Boolean Algebra
Now let’s determine specifically what is involved when two instances of a Boolean
algebra are isomorphic. Suppose we have two Boolean algebras, 3B, +, # , ′, 0, 14
and 3b, &, *, ″, f, 14. This notation means that, for example, if x is in B, x′ is
the result of performing on x the unary operation defined in B, and if z is an element of b, z″ is the result of performing on z the unary operation defined in b.
How would we define isomorphism between these two Boolean algebras? First,
we would need a bijection f from B onto b. Then f must preserve in b the effects of
the various operations in B. There are three operations, so we use three equations
to express these preservations. To preserve the operation +, we want to be able to
operate using + on two elements in B and then map the result to b, or to map the
two elements to b and operate using the corresponding operation & on the results
there. (Think “operate and map = map and operate.”) Thus, for x and y in B, we
require
f (x + y) = f (x) & f ( y)
PraCtiCe 5
a. Write the equation requiring f to preserve the effect of the binary operation # .
b. Write the equation requiring f to preserve the effect of the unary operation ′.
■
b
d
e
f
c
a
Map
Operate
Operate
(a)
b
d
a
Map
Map
(b)
figure 8.3
figure 8.4