Properties of Boolean Algebras | ||||
If (A, ∪, ∩, ¬, E∩, E∪ ) is a boolean algebra, then for every a, b, and c in A, the following identities hold. ---------------------------------------------------------------------------------------------------------------------------- | ||||
a ∪ (b ∪ c) = (a ∪ b) ∪ c | a ∩ (b ∩ c) = (a ∩ b) ∩ c | Associativity | ||
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 = b ∪ a | a ∩ b = b ∩ a | Commutativity | ||
E∪ ∪ a = a | E∩ ∩ a = a | Left identities | ||
a ∪ (b ∩ c) = (a ∪ b) ∩ (a ∪ c) | a ∩ (b ∪ c) = (a ∩ b) ∪ (a ∩ c) | Left Distributive Laws | ||
(a ∩ b) ∪ c = (a ∪ c) ∩ (b ∪ c) | (a ∪ b) ∩ c = (a ∩ c) ∪ (b ∩ c) | Right Distributive Laws | ||
---------------------------------------------------------------------------------------------------------------------------- Properties in black font are axioms. |
Preliminaries
Wednesday, December 31, 2008
The Right Distributive Laws hold for all Boolean Algebras
Monday, December 22, 2008
The Distinguished Elements of Boolean Algebra are Identities
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 ∩.