I. Boolean Algebra
Define an abstract Boolean Algebra, B, as follows:
The three operations are:
+ ( x + y addition)
˜ ( ˜ x the complement or the negation of x)
{B, + , 0 } is a commutative monoid
1. State the commutative law of addition: ___________________________________________
2. State the associative law of addition: _____________________________________________
3. State the law that says 0 is an additive identity __________________________________
{B, • , 1 } is a commutative monoid
4. State the commutative law of multiplication: ____________________________________
5. State the associative law of multiplication: _______________________________________
6. State the law that says 1 is a multiplicative identity _____________________________
7. State the distributive law of multiplication: ______________________________________
8. State the distributive law of addition: _____________________________________________
Finally it is given that:
9. x + ˜ x = 1
10. x • ˜ x = 0
The above ten properties are necessary and sufficient conditions to prove a given algebra is a Boolean algebra.
For a Boolean Algebra prove the idempotent properties:
1. x • x = x
2. x + x = x
For a Boolean Algebra prove the Zero and One Properties:
3. 0 • x = 0
4. 1 + x = 1
Prove the four Absorption Laws for a Boolean Algebra:
5. x + (x • y) = x
6. x • ( x + y) = x
7. x + (˜x • y) = x + y
8. x • ( ˜x + y) = x • y
9. Prove that if the element y acts as the additive complement of x, i.e. x + y = 1, and y acts as the multiplicative complement of x, i.e. x•y = 0, then in fact x is the complement of y, i.e. y = ˜x.
Note. The Involution Law: ˜ ˜x = x, is true, by the fact of the uniqueness of the complement (see 9. above) and the fact that x acts as the complement of ˜x .
Prove the following De Morgan Laws (Hint: use the uniqueness of the complement)
10. ˜ ( x + y ) = (˜x) • (˜y)
11. ˜ ( x + y ) = (˜x) • (˜y)