ic
Section 8.1 Boolean Algebra Structure
635
21. Let S = 50, 16 and let a binary operation # be defined on S by
#
0
1
0
1
0
1
0
1
Let T = 55, 76, and let a binary operation + be defined on T by
+
5
7
5
7
5
7
5
7
Consider 3S, # 4 and [T, +] as mathematical structures.
a. If a function f is an isomorphism from 3S, # 4 to [T, +], what two properties must f satisfy?
b. Define a function f: S S T and prove that it is an isomorphism from 3S, # 4 to [T, +].
22. Consider the four-element Boolean algebra defined in Exercise 6 with n = 21. Find an isomorphism
from this Boolean algebra to the four-element Boolean algebra with set `(51, 26) that was defined in this
section.
23. Let R denote the real numbers and R
+
the positive real numbers. Addition is a binary operation on R, and
multiplication is a binary operation on R
+
. Consider [R, +] and 3R
+
, # 4 as mathematical structures.
a. Prove that the function f defined by f (x) = 2
x
is a bijection from R to R
+
.
b. Write the equation that an isomorphism from [R, +] to 3R
+
, # 4 must satisfy.
c. Prove that the function f of part (a) is an isomorphism from 3R, + 4 to 3R
+
, # 4.
d. What is f
−1
for this function?
e. Prove that f
−1
is an isomorphism from 3R
+
, # 4 to [R, +].
24. An isomorphism from the Boolean algebra with set B = 50, 1, a, a′6 to the Boolean algebra with set
`(51, 26) was defined in this section. Because the two Boolean algebras are essentially the same, an operation in one can be simulated by mapping to the other, operating there, and mapping back.
a. Use the Boolean algebra on `(51, 26) to simulate the computation 1 # a′ in the Boolean algebra on B.
b. Use the Boolean algebra on `(51, 26) to simulate the computation (a)′ in the Boolean algebra on B.
c. Use the Boolean algebra on B to simulate the computation 516 c 526 in the Boolean algebra on
`(51, 26).
25. Consider the set B of all functions mapping 50, 16
2
to 50, 16. We can define operations of + , # , and ′ on B by
( f 1 + f 2 )(x, y) = max( f 1 (x, y), f 2 (x, y))
( f 1 # f 2 )(x, y) = min( f 1 (x, y), f 2 (x, y))
f 1 ′(x, y) = e
1 if f 1 (x, y) = 0
0 if f 1 (x, y) = 1
Then 3B, +, # , ′, 0, 14 is a Boolean algebra of 16 elements (see Exercise 5). The following table assigns
names to these 16 functions.
Section 8.1 Boolean Algebra Structure
635
21. Let S = 50, 16 and let a binary operation # be defined on S by
#
0
1
0
1
0
1
0
1
Let T = 55, 76, and let a binary operation + be defined on T by
+
5
7
5
7
5
7
5
7
Consider 3S, # 4 and [T, +] as mathematical structures.
a. If a function f is an isomorphism from 3S, # 4 to [T, +], what two properties must f satisfy?
b. Define a function f: S S T and prove that it is an isomorphism from 3S, # 4 to [T, +].
22. Consider the four-element Boolean algebra defined in Exercise 6 with n = 21. Find an isomorphism
from this Boolean algebra to the four-element Boolean algebra with set `(51, 26) that was defined in this
section.
23. Let R denote the real numbers and R
+
the positive real numbers. Addition is a binary operation on R, and
multiplication is a binary operation on R
+
. Consider [R, +] and 3R
+
, # 4 as mathematical structures.
a. Prove that the function f defined by f (x) = 2
x
is a bijection from R to R
+
.
b. Write the equation that an isomorphism from [R, +] to 3R
+
, # 4 must satisfy.
c. Prove that the function f of part (a) is an isomorphism from 3R, + 4 to 3R
+
, # 4.
d. What is f
−1
for this function?
e. Prove that f
−1
is an isomorphism from 3R
+
, # 4 to [R, +].
24. An isomorphism from the Boolean algebra with set B = 50, 1, a, a′6 to the Boolean algebra with set
`(51, 26) was defined in this section. Because the two Boolean algebras are essentially the same, an operation in one can be simulated by mapping to the other, operating there, and mapping back.
a. Use the Boolean algebra on `(51, 26) to simulate the computation 1 # a′ in the Boolean algebra on B.
b. Use the Boolean algebra on `(51, 26) to simulate the computation (a)′ in the Boolean algebra on B.
c. Use the Boolean algebra on B to simulate the computation 516 c 526 in the Boolean algebra on
`(51, 26).
25. Consider the set B of all functions mapping 50, 16
2
to 50, 16. We can define operations of + , # , and ′ on B by
( f 1 + f 2 )(x, y) = max( f 1 (x, y), f 2 (x, y))
( f 1 # f 2 )(x, y) = min( f 1 (x, y), f 2 (x, y))
f 1 ′(x, y) = e
1 if f 1 (x, y) = 0
0 if f 1 (x, y) = 1
Then 3B, +, # , ′, 0, 14 is a Boolean algebra of 16 elements (see Exercise 5). The following table assigns
names to these 16 functions.