630
Boolean Algebra and Computer Logic
We claim that the mapping f : B S `(S ) given by
f (0) = [
f (1) = 51, 26
f (a) = 516
f (a′) = 526
is an isomorphism. Certainly it is a bijection. For x, y [ B, we can verify each of
the equations
f (x + y) = f (x) c f ( y)
f (x # y) = f (x) d f ( y)
f (x′) = ( f (x))
′
by examining all possible cases. Thus, for example,
f (a # 1) = f (a) = 516 = 516 d 51, 26 = f (a) d f (1)
■
Practice 7 Verify the following equations.
a. f (0 + a) = f (0) c f (a)
b. f (a + a′) = f (a) c f (a′)
c. f (a # a′) = f (a) d f (a′)
d. f (1′) = ( f (1))′
The remaining cases also hold. Even without testing all cases, it is pretty clear
here that f is going to work because it merely relabels the entries in the tables for
B so that they resemble the tables for `(S ). In general, however, it may not be so
easy to decide whether a given f is an isomorphism between two instances of a
structure. Even harder to answer is the question of whether two given instances of
a structure are isomorphic; we must either think up a function that works or show
that no such function exists. One case where no such function exists is when the
sets involved are not the same size; we cannot have a four-element Boolean algebra isomorphic to an eight-element Boolean algebra.
We just showed that a particular four-element Boolean algebra is isomorphic to `(51, 26). It turns out that any finite Boolean algebra is isomorphic to
the Boolean algebra of a power set. Although we state this as a theorem, we
will not prove it.
Theorem On Finite BOOlean algeBras
Let B be any Boolean algebra with n elements. Then n = 2
m
for some m, and B is
isomorphic to `(51, 2, … , m6).
This theorem gives us two pieces of information. The number of elements in
a finite Boolean algebra must be a power of 2. Also we learn that finite Boolean
algebras that are power sets are—in our lumping together of isomorphic things—
Boolean Algebra and Computer Logic
We claim that the mapping f : B S `(S ) given by
f (0) = [
f (1) = 51, 26
f (a) = 516
f (a′) = 526
is an isomorphism. Certainly it is a bijection. For x, y [ B, we can verify each of
the equations
f (x + y) = f (x) c f ( y)
f (x # y) = f (x) d f ( y)
f (x′) = ( f (x))
′
by examining all possible cases. Thus, for example,
f (a # 1) = f (a) = 516 = 516 d 51, 26 = f (a) d f (1)
■
Practice 7 Verify the following equations.
a. f (0 + a) = f (0) c f (a)
b. f (a + a′) = f (a) c f (a′)
c. f (a # a′) = f (a) d f (a′)
d. f (1′) = ( f (1))′
The remaining cases also hold. Even without testing all cases, it is pretty clear
here that f is going to work because it merely relabels the entries in the tables for
B so that they resemble the tables for `(S ). In general, however, it may not be so
easy to decide whether a given f is an isomorphism between two instances of a
structure. Even harder to answer is the question of whether two given instances of
a structure are isomorphic; we must either think up a function that works or show
that no such function exists. One case where no such function exists is when the
sets involved are not the same size; we cannot have a four-element Boolean algebra isomorphic to an eight-element Boolean algebra.
We just showed that a particular four-element Boolean algebra is isomorphic to `(51, 26). It turns out that any finite Boolean algebra is isomorphic to
the Boolean algebra of a power set. Although we state this as a theorem, we
will not prove it.
Theorem On Finite BOOlean algeBras
Let B be any Boolean algebra with n elements. Then n = 2
m
for some m, and B is
isomorphic to `(51, 2, … , m6).
This theorem gives us two pieces of information. The number of elements in
a finite Boolean algebra must be a power of 2. Also we learn that finite Boolean
algebras that are power sets are—in our lumping together of isomorphic things—