SOE ex.8.9
( Reference: Boolean Algebra
http://en.wikipedia.org/wiki/Boolean_algebra )
--------------------------------------------------------------------------
Axiom 1: Associativity
r1 `Union` (r2 `Union` r3) <=> (r1 `Union` r2) `Union` r3
r1 `Union` (r2 `Intersect` r3) <=> (r1 `Intersect` r2) `Intersect` r3
Axiom 2: Commutativity
r1 `Union` r2 <=> r2 `Union` r1
r1 `Intersect` r2 <=> r2 `Intersect` r1
Axiom 3: Distributivity
r1 `Intersect` (r2 `Union` r3) <=> (r1 `Intersect` r2) `Union` (r1 `Intersect` r3)
r1 `Union` (r2 `Intersect` r3) <=> (r1 `Union` r2) `Intersect` (r1 `Union` r3)
Axiom 4: Boundedness
r `Union` Empty <=> r
r `Intersect` univ <=> r
Axiom 5: Complements
r `Union` Complement r <=> univ
r `Intersect` Complement r <=> Empty
--------------------------------------------------------------------------
Idempotence: r `Intersect` r <=> r
From Axiom 4
r `Intersect` univ <=> r
<=> r `Intersect` (r `Union` Complement r) <=> r -- Apply Axiom 5
<=> (r `Intersect` r) `Union` (r `Intersect` Complement r) <=> r -- Apply Axiom 3
<=> (r `Intersect` r) `Union` Empty <=> r -- Apply Axiom 5
<=> r `Intersect` r <=> r -- Apply Axiom 4
CQFD
--------------------------------------------------------------------------
Idempotence: r `Union` r <=> r
From Axiom 4
r `Union` Empty <=> r
<=> r `Union` (r `Intersect` Complement r) <=> r -- Apply Axiom 5
<=> (r `Union` r) `Intersect` (r `Union` Complement r) <=> r -- Apply Axiom 3
<=> (r `Union` r) `Intersect` univ <=> r -- Apply Axiom 5
<=> r `Union` r <=> r -- Apply Axiom 4
CQFD
--------------------------------------------------------------------------
Boundedness: r `Union` univ <=> univ
r `Union` univ
<=> r `Union` (r `Union` Complement r) -- Apply Axiom 5
<=> (r `Union` r) `Union` Complement r -- Apply Axiom 1
<=> r `Union` Complement r -- Apply Idempotence just proved
<=> univ -- Apply Axiom 5
CQFD
--------------------------------------------------------------------------
Boundedness: r `Intersect` Empty <=> Empty
r `Intersect` Empty
<=> r `Intersect` (r `Intersect` Complement r) -- Apply Axiom 5
<=> (r `Intersect` r) `Intersect` Complement r -- Apply Axiom 1
<=> r `Intersect` Complement r -- Apply Idempotence just proved
<=> Empty -- Apply Axiom 5
CQFD
--------------------------------------------------------------------------
Absorption: r1 `Union` (r1 `Intersect` r2) <=> r1
For any r1, r2:
Left side `Intersect` Complement r1
<=> (r1 `Union` (r1 `Intersect` r2)) `Intersect` Complement r1
<=> (r1 `Intersect` Complement r1) `Union` ((r1 `Intersect` r2) `Intersect` Complement r1) -- Apply Axiom 3
<=> Empty `Union` ((r2 `Intersect` r1) `Intersect` Complement r1) -- Apply Axiom 5 and 2
<=> (r2 `Intersect` (r1 `Intersect` Complement r1)) -- Apply Axiom 4 and 1
<=> r2 `Intersect` Empty -- Apply Axiom 5
<=> Empty -- Apply Boundedness just proved
right-side `Intersect` Complement r1
<=> r1 `Intersect` Complement r1
<=> Empty -- Apply Axiom 5
so,
r1 `Union` (r1 `Intersect` r2) <=> r1
--------------------------------------------------------------------------
Absorption: r1 `Intersect` (r1 `Union` r2) <=> r1
Using the previous Absorption just proved:
r1 `Union` (r1 `Intersect` r2) <=> r1
<=> (r1 `Union` r1) `Intersect` (r1 `Union` r2) <=> r1 -- Apply Axiom 3
<=> r1 `Intersect` (r1 `Union` r2) <=> r1 -- Apply Idempotence just proved
--------------------------------------------------------------------------
Involution: Complement (Complement r) <=> r
(Complement r) `Union` Left-side
<=> (Complement r) `Union` Complement (Complement r)
<=> univ -- Apply Axiom 5
(Complement r) `Union` right-side
(Complement r) `Union` r
<=> r `Union` (Complement r) -- Apply Axiom 2
<=> univ -- Apply Axiom 5
so,
Complement (Complement r) <=> r
--------------------------------------------------------------------------
Empty and univ are complements: Complement Empty <=> univ
Empty `Union` Left-side
<=> Empty `Union` Complement Empty
<=> univ -- Apply Axiom 5
Empty `Union` Right-side
<=> Empty `Union` univ
<=> univ -- Apply Boundedness just proved
so,
Complement Empty <=> univ
--------------------------------------------------------------------------
Empty and univ are complements: Complement univ <=> Empty
Using the previous theorem just proved:
Complement Empty <=> univ
<=> Complement (Complement Empty) <=> Complement univ
<=> Empty <=> Complement univ -- Apply Involution just proved
--------------------------------------------------------------------------
De Morgan's laws: Complement (r1 `Union` r2) <=> Complement r1 `Intersect` Complement r2
(r1 `Union` r2) `Union` Left-side
<=> (r1 `Union` r2) `Union` Complement (r1 `Union` r2)
<=> univ -- Apply Axiom 5
(r1 `Union` r2) `Union` Right-side
<=> (r1 `Union` r2) `Union` (Complement r1 `Intersect` Complement r2)
<=> ((r1 `Union` r2) `Union` Complement r1) `Intersect` ((r1 `Union` r2) `Union` Complement r2) -- Apply Axiom 3
<=> (r2 `Union` (r1 `Union` Complement r1) `Intersect` (r1 `Union` (r2 `Union` Complement r2)) -- Apply Axiom 1 and 2
<=> (r2 `Union` univ) `Intersect` (r1 `Union` univ) -- Apply Axiom 5
<=> univ `Intersect` univ -- Apply Boundedness just proved
<=> univ -- Apply Axiom 4
so,
Complement (r1 `Union` r2) <=> Complement r1 `Intersect` Complement r2
--------------------------------------------------------------------------
De Morgan's laws: Complement (r1 `Intersect` r2) <=> Complement r1 `Union` Complement r2
Similar demonstration as previous: by using (r1 `Intersect` r2) `Union` Left-side and Right-side.