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 ∩.

No comments:

Post a Comment