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