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