632
Boolean Algebra and Computer Logic
4. Let M 2 (Z) denote the set of 2 × 2 matrices with integer entries, and let + denote matrix addition and #
denote matrix multiplication. Given
A = c
a b
c d
d  then A′ = c
−a −b
−c −d
d .
Using c
0 0
0 0
d and c
1 0
0 1
d as the 0 element and the 1 element, respectively, either prove that
3M 2 (Z), + , # , ′, 0, 14 is a Boolean algebra or give a reason why it is not.
5. Let S be the set 50, 16. Then S
2
is the set of all ordered pairs of 0s and 1s; S
2
= 5(0, 0), (0, 1), (1, 0), (1, 1)6.
Consider the set B of all functions mapping S
2
to S. For example, one such function, f (x,y), is given by
f (0, 0) = 0
f (0, 1) = 1
f (1, 0) = 1
f (1, 1) = 1
a. How many elements are in B?
b. For f 1 and f 2 members of B and (x, y) [ S
2
, define
( 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 ′(x, y) = e
1 if f 1 (x, y) = 0
0 if f 1 (x, y) = 1
Suppose
f 1 (0, 0) = 1
f 2 (0, 0) = 1
f 1 (0, 1) = 0
f 2 (0, 1) = 1
f 1 (1, 0) = 1
f 2 (1, 0) = 0
f 1 (1, 1) = 0
f 2 (1, 1) = 0
What are the functions f 1 + f 2 , f 1 # f 2 , and f 1 ′?
c. Prove that 3B, + , # , ′, 0, 14 is a Boolean algebra where the functions 0 and 1 are defined by
0(0, 0) = 0
1(0, 0) = 1
0(0, 1) = 0
1(0, 1) = 1
0(1, 0) = 0
1(1, 0) = 1
0(1, 1) = 0
1(1, 1) = 1
6. Let n be a positive integer whose decomposition into prime factors has no repeated prime. Let
B = 5x 0 x is a divisor of n6. For example, if n = 21 = 3 # 7, then B = 51, 3, 7, 216. Let the following
operations be defined on B:
x + y = lcm(x, y)
x # y = gcd(x, y)
x′ = n͞x