636
Boolean Algebra and Computer Logic
(x, y)
0
1
f 1
f 2
f 3
f 4
f 5
f 6
f 7
f 8
f 9
f 10 f 11 f 12 f 13 f 14
(0, 0)
0
1
1
1
1
1
1
1
0
0
0
1
0
0
0
0
(0, 1)
0
1
0
1
1
0
1
0
1
1
1
0
0
1
0
0
(1, 0)
0
1
1
0
1
0
0
1
1
1
0
0
1
0
1
0
(1, 1)
0
1
0
0
0
0
1
1
1
0
1
1
1
0
0
1
According to the theorem on finite Boolean algebras, this Boolean algebra is isomorphic to
3`(51, 2, 3, 46), c , d, ′, [, 51, 2, 3, 46 4. Complete the following definition of an isomorphism from B to
`(51, 2, 3, 46).
0 S [
1 S 51, 2, 3, 46
f 4 S 516
f 12 S 526
f 13 S 536
f 14 S 546
26. Let P, Q, and R be three statements in propositional logic with statement letters A and B. P, Q, and R
define the following three functions from 5T, F6
2
to 5T, F6. Also shown are the contradiction 0 and the
tautology 1.
A
B
P
Q
R
0
1
T
T
T
F
F
F
T
T
F
F
T
F
F
T
F
T
F
F
T
F
T
F
F
T
F
F
F
T
a. Let B = 5P, P′, Q, Q′, R, R′, 0, 16. Then 3B, ~ , ` , ′, 0, 14 is a Boolean algebra. Write the 8 × 8
tables for the ~ and ` operations and the 8 × 1 table for the ′ operation.
b. 3`(51, 2, 36, c , d, ′, [, 51, 2, 36 4 is a Boolean algebra. Write the 8 × 8 tables for the c and d operations and the 8 × 1 table for the ′ operation.
c. Find an isomorphism from the Boolean algebra of part (a) to the Boolean algebra of part (b).
27. Suppose that 3B, + , # , ′, 0, 14 and 3b, &, * , ″, f, 14 are isomorphic Boolean algebras and that f is an isomorphism from B to b.
a. Prove that f(0) = f.
b. Prove that f(1) = 1.
28. According to the theorem on finite Boolean algebras, which we did not prove, any finite Boolean algebra
must have 2
m
elements for some m. Prove the weaker statement that no Boolean algebra can have an odd
number of elements. (Note that in the definition of a Boolean algebra, 0 and 1 are distinct elements of B,
so B has at least two elements. Arrange the remaining elements of B so that each element is paired with its
complement.)
Boolean Algebra and Computer Logic
(x, y)
0
1
f 1
f 2
f 3
f 4
f 5
f 6
f 7
f 8
f 9
f 10 f 11 f 12 f 13 f 14
(0, 0)
0
1
1
1
1
1
1
1
0
0
0
1
0
0
0
0
(0, 1)
0
1
0
1
1
0
1
0
1
1
1
0
0
1
0
0
(1, 0)
0
1
1
0
1
0
0
1
1
1
0
0
1
0
1
0
(1, 1)
0
1
0
0
0
0
1
1
1
0
1
1
1
0
0
1
According to the theorem on finite Boolean algebras, this Boolean algebra is isomorphic to
3`(51, 2, 3, 46), c , d, ′, [, 51, 2, 3, 46 4. Complete the following definition of an isomorphism from B to
`(51, 2, 3, 46).
0 S [
1 S 51, 2, 3, 46
f 4 S 516
f 12 S 526
f 13 S 536
f 14 S 546
26. Let P, Q, and R be three statements in propositional logic with statement letters A and B. P, Q, and R
define the following three functions from 5T, F6
2
to 5T, F6. Also shown are the contradiction 0 and the
tautology 1.
A
B
P
Q
R
0
1
T
T
T
F
F
F
T
T
F
F
T
F
F
T
F
T
F
F
T
F
T
F
F
T
F
F
F
T
a. Let B = 5P, P′, Q, Q′, R, R′, 0, 16. Then 3B, ~ , ` , ′, 0, 14 is a Boolean algebra. Write the 8 × 8
tables for the ~ and ` operations and the 8 × 1 table for the ′ operation.
b. 3`(51, 2, 36, c , d, ′, [, 51, 2, 36 4 is a Boolean algebra. Write the 8 × 8 tables for the c and d operations and the 8 × 1 table for the ′ operation.
c. Find an isomorphism from the Boolean algebra of part (a) to the Boolean algebra of part (b).
27. Suppose that 3B, + , # , ′, 0, 14 and 3b, &, * , ″, f, 14 are isomorphic Boolean algebras and that f is an isomorphism from B to b.
a. Prove that f(0) = f.
b. Prove that f(1) = 1.
28. According to the theorem on finite Boolean algebras, which we did not prove, any finite Boolean algebra
must have 2
m
elements for some m. Prove the weaker statement that no Boolean algebra can have an odd
number of elements. (Note that in the definition of a Boolean algebra, 0 and 1 are distinct elements of B,
so B has at least two elements. Arrange the remaining elements of B so that each element is paired with its
complement.)