Notes taken while listening to Max‘s course on logic, recorded here for memo.
The basic laws we assume of a boolean algebra:
- commutativity,
- associativity,
- absorption: a /\ (a \/ b) = a; a \/ (a /\ b) = a;
- complement: a \/ ~a = T; a /\ ~a = F;
- distribution: a /\ (b \/ c) = (a /\ b) \/ (a /\ c); a \/ (b /\ c) = (a \/ b) /\ (a \/ c).
Basics
Prove a /\ T = a (and complementarily, a \/ F = a):
a /\ T
= { complement }
a /\ (a \/ ~a)
= { absorption }
a
Prove a /\ F = F (and complementarily, a \/ T = T):
a /\ F
= { since a \/ F = a }
(a \/ F) /\ F
= { absorption }
F
Prove ~T = F (and complementarily, ~F = T):
~T
= { since a /\ T = a }
~T /\ T
= { complement }
F
Prove a /\ a = a = a \/ a:
a /\ a
= { since a \/ F = a}
a /\ (a \/ F)
= { absorption }
a
The other side follows similarly.
De Morgan’s Laws
De Morgan’s laws:
~(a /\ b) = ~a \/ ~b
~(a \/ b) = ~a /\ ~b
They are more tricky to prove. The following proof is from Notes on Basic Proofs of Peter Williams.
We will need the following lemma:
If a /\ b = F and a \/ b = T, then a = ~b.
We try to prove the first of the two laws.
Firstly, we prove that (a /\ b) /\ (~a \/ ~b) = F:
(a /\ b) /\ (~a \/ ~b)
= { distribution }
((a /\ b) /\ ~a) \/ ((a /\ b) /\ ~b)
= { commutativity, associativity }
((a /\ ~a) /\ b) \/ (a /\ (b /\ ~b))
= { complement }
(F /\ b) \/ (a /\ F)
= { since a /\ F = F }
0 \/ 0
= 0
Then we prove that (a /\ b) \/ (~a \/ ~b) = T:
(a /\ b) \/ (~a \/ ~b)
= { associativity }
((a /\ b) \/ ~a) \/ ~b
= { distributivitiy }
((a \/ ~a) /\ (b \/ ~a)) \/ ~b
= { complement }
(T /\ (b \/ ~a)) \/ ~ b
= { since T /\ a = a }
(b \/ ~a) \/ ~b
= { associativity, commutativity }
(b \/ ~b) \/ ~a
= { complement }
T \/ ~a
= T
The lemma, on the other hand, is proved below. The following proof is adapted from that on AntiQuark. We show that ~b = a with the assumptions a \/ b = T and a /\ b = F:
~b
= ~b /\ T
= { assumption: a \/ b = T }
~b /\ (a \/ b)
= { distribution }
(~b /\ a) \/ (~b \/ b)
= { complement }
(~b /\ a) \/ F
= { assumption: a /\ b = F }
(~b /\ a) \/ (a /\ b)
= { distribution (backwards) }
a /\ (~b \/ b)
= a /\ T
= a
Double Negation
The seemingly simple rule ~~a = a turns out to be the most tricky:
~~a
= ~~a /\ T
= ~~a /\ (~a \/ a)
= (~~a /\ ~a) \/ (~~a /\ a)
= { complement: (~~a /\ ~a) = F }
F \/ (~~a /\ a)
= (~a /\ a) \/ (~~a /\ a)
= (a /\ ~a) \/ (a /\ ~~a)
= { distribution (backwards) }
a /\ (~a \/ ~~a)
= a /\ T
= a