ic
Section 8.1 Boolean Algebra Structure
633
Then + and # are binary operations on B and ′ is a unary operation on B.
a. For n = 21, find
(i) 3 # 7
(ii) 7 # 21
(iii) 1 + 3
(iv) 3 + 21
(v) 3′
b. Prove that the commutative, associative, and distributive properties hold for both + and # .
c. Find the value of the “0” element and the “1” element, then prove properties 4 and 5 for both + and # .
d. Consider a value for n whose decomposition has repeated primes. In particular, let n = 12 = 2 # 2 # 3.
Prove that, using the above definitions for + and # , it’s not possible to define a complement for 6 in
the set 51, 2, 3, 4, 6, 126. Therefore a Boolean algebra cannot be constructed with n = 12 using the
process described.
7. Prove the following property of Boolean algebras. Give a reason for each step. (Hint: Remember the
uniqueness of the complement.)
(x′)′ = x
(double negation)
8. Prove the following property of Boolean algebras. Give a reason for each step. (Hint: Remember the
uniqueness of the complement.)
(x + y)′ = x′ # y′
(x # y)′ = x′ + y′ (De Morgan’s laws)
9. Prove the following properties of Boolean algebras. Give a reason for each step.
a. x + (x # y) = x
(absorption properties)
x # (x + y) = x
b. x # 3 y + (x # z) 4 = (x # y) + (x # z)
(modular properties)
x + 3 y # (x + z) 4 = (x + y) # (x + z)
c. (x + y) # (x′ + y) = y
(x # y) + (x′ # y) = y
d. (x + ( y # z))′ = x′ # y′ + x′ # z′
(x # ( y + z))′ = (x′ + y′) # (x′ + z′)
e. (x + y) # (x + 1) = x + (x # y) + y
(x # y) + (x # 0) = x # (x + y) # y
10. Prove the following properties of Boolean algebras. Give a reason for each step.
a. (x + y) + ( y # x′) = x + y
b. ( y + x) # (z + y) + x # z # (z + z′) = y + x # z
c. ( y′ # x) + x + ( y + x) # y′ = x + ( y′ # x)
d. (x + y′) # z = 3(x′ + z′) # ( y + z′) 4′
e. (x # y) + (x′ # z) + (x′ # y # z′) = y + (x′ # z)
Section 8.1 Boolean Algebra Structure
633
Then + and # are binary operations on B and ′ is a unary operation on B.
a. For n = 21, find
(i) 3 # 7
(ii) 7 # 21
(iii) 1 + 3
(iv) 3 + 21
(v) 3′
b. Prove that the commutative, associative, and distributive properties hold for both + and # .
c. Find the value of the “0” element and the “1” element, then prove properties 4 and 5 for both + and # .
d. Consider a value for n whose decomposition has repeated primes. In particular, let n = 12 = 2 # 2 # 3.
Prove that, using the above definitions for + and # , it’s not possible to define a complement for 6 in
the set 51, 2, 3, 4, 6, 126. Therefore a Boolean algebra cannot be constructed with n = 12 using the
process described.
7. Prove the following property of Boolean algebras. Give a reason for each step. (Hint: Remember the
uniqueness of the complement.)
(x′)′ = x
(double negation)
8. Prove the following property of Boolean algebras. Give a reason for each step. (Hint: Remember the
uniqueness of the complement.)
(x + y)′ = x′ # y′
(x # y)′ = x′ + y′ (De Morgan’s laws)
9. Prove the following properties of Boolean algebras. Give a reason for each step.
a. x + (x # y) = x
(absorption properties)
x # (x + y) = x
b. x # 3 y + (x # z) 4 = (x # y) + (x # z)
(modular properties)
x + 3 y # (x + z) 4 = (x + y) # (x + z)
c. (x + y) # (x′ + y) = y
(x # y) + (x′ # y) = y
d. (x + ( y # z))′ = x′ # y′ + x′ # z′
(x # ( y + z))′ = (x′ + y′) # (x′ + z′)
e. (x + y) # (x + 1) = x + (x # y) + y
(x # y) + (x # 0) = x # (x + y) # y
10. Prove the following properties of Boolean algebras. Give a reason for each step.
a. (x + y) + ( y # x′) = x + y
b. ( y + x) # (z + y) + x # z # (z + z′) = y + x # z
c. ( y′ # x) + x + ( y + x) # y′ = x + ( y′ # x)
d. (x + y′) # z = 3(x′ + z′) # ( y + z′) 4′
e. (x # y) + (x′ # z) + (x′ # y # z′) = y + (x′ # z)