A monoid (M, ∗, e) is a semigroup (M, ∗) with a two-sided identity element e. Semigroups are associative magmas and a magma (M, ∗) is just a binary operation ∗: M×M→M on M.
Given a Boolean Algebra (A, ∩, ∪, ¬, E∪, E∩), we want to show that (A, ∩, E∩) and (A, ∪, E∪) are monoids. We start by noting that ∩: A×A→A and ∪: A×A→A are binary operations. So, (A, ∩) and (A, ∪) are, by definition, magmas. Next, we note that ∩ and ∪ both satisfy the associative law. So, (A, ∩) and (A, ∪) are, by definition, semigroups.
Next, recall that the absorption and compliment axioms imply that E∪ and E∩ are right identities of ∪ and ∩ respectively. We can use this fact together with the commutative laws to prove that (A, ∩, E∩) and (A, ∪, E∪) are monoids. The proof follows.
| 1 | a ∪ E∪ = a | a ∩ E∩ = a | Since E∪ and E∩ are right identities. | |||
| 2 | E∪ ∪ a = a | E∩ ∩ a = a | Using the Commutative Laws. | |||
| Therefore, E∪ and E∩ are Left Identities of ∪ and ∩, respectively. | ||||||
| Therefore, E∪ and E∩ are two-sided identities of ∪ and ∩, respectively. | ||||||
| Therefore, (A, ∪, E∪ ) and (A, ∩, E∩) are monoids. | ||||||
We can now add left identities to our list of properties of Boolean Algebras.
| 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) | Distributivity | ||
| Properties in blue font are axioms. Properties in black font are derived from the axioms. | ||||
No comments:
Post a Comment