Showing posts with label commutativity. Show all posts
Showing posts with label commutativity. Show all posts

Wednesday, December 31, 2008

The Right Distributive Laws hold for all Boolean Algebras

The Right Distributive Laws of Boolean Algebra follow immediately from the Left Distributive Laws and the Commutative Laws. We can therefore add these laws directly to our table of:


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.

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