634
Boolean Algebra and Computer Logic
11. Prove the following properties of Boolean algebras. Give a reason for each step.
a. x + y′ = x + (x′ # y + x # y)′
b. 3(x # y) # z 4 + ( y # z) = y # z
c. x # y + y # x′ = x # y + y
d. (x + y)′ # z + x′ # z # y = x′ # z
e. (x # y′) + ( y # z′) + (x′ # z) = (x′ # y) + ( y′ # z) + (x # z′)
12. Prove the following properties of Boolean algebras. Give a reason for each step.
a. (x + y # x)′ = x′
b. x # (z + y) + (x′ + y)′ = x
c. (x # y)′ + x′ # z + y′ # z = x′ + y′
d. x # y + x′ = y + x′ # y′
e. x # y + y # z # x′ = y # z + y # x # z′
13. Prove that in any Boolean algebra, x # y′ + x′ # y = y if and only if x = 0.
14. Prove that in any Boolean algebra, x # y′ = 0 if and only if x # y = x.
15. A new binary operation ! in a Boolean algebra (exclusive OR) is defined by
x ! y = x # y′ + y # x′
Prove that
a. x ! y = y ! x
b. x ! x = 0
c. 0 ! x = x
d. 1 ! x = x′
16. Prove that for any Boolean algebra:
a. If x + y = 0, then x = 0 and y = 0.
b. x = y if and only if x # y′ + y # x′ = 0.
17. Prove that the 0 element in any Boolean algebra is unique; prove that the 1 element in any Boolean algebra
is unique.
18. a. Find an example of a Boolean algebra with elements x, y, and z for which x + y = x + z but y ∙ z.
(Here is further evidence that ordinary arithmetic of integers is not a Boolean algebra.)
b. Prove that in any Boolean algebra, if x + y = x + z and x′ + y = x′ + z, then y = z.
19. Let (S, d) and (S′, d′) be two partially ordered sets. (S, d) is isomorphic to (S′, d′) if there is a bijection
f: S S S′ such that for x, y in S, x a y S f (x) a ′ f (y) and f (x) a ′ f (y) S x a y.
a. Show that there are exactly two nonisomorphic, partially ordered sets with two elements (use
diagrams).
b. Show that there are exactly five nonisomorphic, partially ordered sets with three elements.
c. How many nonisomorphic, partially ordered sets with four elements are there?
20. Find an example of two partially ordered sets (S, d) and (S′, d′) and a bijection f: S S S′ where, for x, y
in S, x a y S f (x) a ′ f ( y) but f (x) a ′ f ( y) S ∙ x a y.
Boolean Algebra and Computer Logic
11. Prove the following properties of Boolean algebras. Give a reason for each step.
a. x + y′ = x + (x′ # y + x # y)′
b. 3(x # y) # z 4 + ( y # z) = y # z
c. x # y + y # x′ = x # y + y
d. (x + y)′ # z + x′ # z # y = x′ # z
e. (x # y′) + ( y # z′) + (x′ # z) = (x′ # y) + ( y′ # z) + (x # z′)
12. Prove the following properties of Boolean algebras. Give a reason for each step.
a. (x + y # x)′ = x′
b. x # (z + y) + (x′ + y)′ = x
c. (x # y)′ + x′ # z + y′ # z = x′ + y′
d. x # y + x′ = y + x′ # y′
e. x # y + y # z # x′ = y # z + y # x # z′
13. Prove that in any Boolean algebra, x # y′ + x′ # y = y if and only if x = 0.
14. Prove that in any Boolean algebra, x # y′ = 0 if and only if x # y = x.
15. A new binary operation ! in a Boolean algebra (exclusive OR) is defined by
x ! y = x # y′ + y # x′
Prove that
a. x ! y = y ! x
b. x ! x = 0
c. 0 ! x = x
d. 1 ! x = x′
16. Prove that for any Boolean algebra:
a. If x + y = 0, then x = 0 and y = 0.
b. x = y if and only if x # y′ + y # x′ = 0.
17. Prove that the 0 element in any Boolean algebra is unique; prove that the 1 element in any Boolean algebra
is unique.
18. a. Find an example of a Boolean algebra with elements x, y, and z for which x + y = x + z but y ∙ z.
(Here is further evidence that ordinary arithmetic of integers is not a Boolean algebra.)
b. Prove that in any Boolean algebra, if x + y = x + z and x′ + y = x′ + z, then y = z.
19. Let (S, d) and (S′, d′) be two partially ordered sets. (S, d) is isomorphic to (S′, d′) if there is a bijection
f: S S S′ such that for x, y in S, x a y S f (x) a ′ f (y) and f (x) a ′ f (y) S x a y.
a. Show that there are exactly two nonisomorphic, partially ordered sets with two elements (use
diagrams).
b. Show that there are exactly five nonisomorphic, partially ordered sets with three elements.
c. How many nonisomorphic, partially ordered sets with four elements are there?
20. Find an example of two partially ordered sets (S, d) and (S′, d′) and a bijection f: S S S′ where, for x, y
in S, x a y S f (x) a ′ f ( y) but f (x) a ′ f ( y) S ∙ x a y.