Tag Archives: Logic

Proving Some Equalities in Propositional Logic

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