Showing posts with label axioms. Show all posts
Showing posts with label axioms. Show all posts

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

Wednesday, December 17, 2008

The Standard Axioms of Boolean Algebra

A Boolean algebra is a 6-tuple consisting of a set A, equipped with two binary operations, a unary operation, and two distinguished elements. The first binary operation ∩: A × A → A is referred to as “conjunction”, “meet”, or “and”. The second binary operation ∪: A × A → A is referred to as “disjunction”, “join”, or “or”. The unary operation ¬: A → A is referred to as “compliment” or “not”. The distinguished elements are often denoted as 0 and 1. However, I will denote these elements as e and e.

The 6-tuple (A, ∩, ∪, ¬, e, e) is called a “Boolean algebra” if it satisfies certain stated axioms. The axioms differ depending upon the needs of a particular author. The five following axiom pairs are a particularly common formulation of Boolean algebra. For all a, b, and c in A:

The Standard Axioms of Boolean Algebra


a ∪ (a ∩ b) = a

a ∩ (a ∪ b) = a

absorption

a ∪ (b ∪ c) = (a ∪ b) ∪ c

a ∩ (b ∩ c) = (a ∩ b) ∩ c

associativity

a ∪ ¬a = e

a ∩ ¬a = e

complements

a ∪ (b ∩ c) = (a ∪ b) ∩ (a ∪ c)

a ∩ (b ∪ c) = (a ∩ b) ∪ (a ∩ c)

distributivity

a ∪ b = b ∪ a

a ∩ b = b ∩ a

commutativity