The absorption and compliment axioms of Boolean Algebra imply that the distinguished elements e∩ and e∪ are right identities of the conjunction and disjunction operations. Here are poofs: Let (A, ∩, ∪, ¬, e∩, e∪) be a Boolean algebra. Let a be an element of A. Let b = ¬a and define E∩ = e∪ and E∪ = e∩.
| Proof that E∪ is a right identity of the disjunction operation ∪ | ||
| a ∪ (a ∩ b) = a | Absorption axiom. | 1 |
| b = ¬a | By definition. | 2 |
| a ∪ (a ∩ ¬a) = a | By 1 and 2. | 3 |
| a ∩ ¬a = e∩ | Complement axiom. | 4 |
| a ∪ e∩ = a | By 3 and 4. | 5 |
| E∪ = e∩ | By definition. | 6 |
| a ∪ E∪ = a | By 5 and 6. | 7 |
| Therefore, E∪ is a right identity of the disjunction operation ∪. | ||
| Proof that E∩ is a right identity of the conjunction operation ∩ | ||
| a ∩ (a ∪ b) = a | Absorption axiom. | 1 |
| b = ¬a | By definition. | 2 |
| a ∩ (a ∪ ¬a) = a | By 1 and 2. | 3 |
| a ∪ ¬a = e∪ | Complement axiom. | 4 |
| a ∩ e∪ = a | By 3 and 4. | 5 |
| E∩ = e∪ | By definition. | 6 |
| a ∩ E∩ = a | By 5 and 6. | 7 |
| Therefore, E∩ is a right identity of the conjunction operation ∩. | ||
We can now add the existence of right identities to our list of properties of Boolean Algebras.
| A Boolean Algebra is a 6-tuple (A, ∩, ∪, ¬, E∪, E∩) that satisfies the following Properties For all a, b, and c in A: |
| |
| a ∪ (a ∩ b) = a | a ∩ (a ∪ b) = a | Absorption |
| a ∪ ¬a = E∩ | a ∩ ¬a = E∪ | Complements |
| a ∪ E∪ = a | a ∩ E∩ = a | Right identities |
| a ∪ (b ∪ c) = (a ∪ b) ∪ c | a ∩ (b ∩ c) = (a ∩ b) ∩ c | Associativity |
| a ∪ (b ∩ c) = (a ∪ b) ∩ (a ∪ c) | a ∩ (b ∪ c) = (a ∩ b) ∪ (a ∩ c) | Distributivity |
| a ∪ b = b ∪ a | a ∩ b = b ∩ a | Commutativity |
| Axioms are in blue font. Derived properties, just one of them so far—the existence of right identities—are listed in black font. | ||
Notice that I have replaced e∩ and e∪ with E∪ and E∩ respectively. The ¬ operator is not a true analog to negation. Since a ∪ ¬a = E∩ (the identity of ∩) rather than E∪ (the identity of ∪), ¬a is not an inverse of a with respect to ∪. Likewise, ¬a is not and inverse of a with respect to ∩.
No comments:
Post a Comment