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