On equality of propositions

After the observation that equality of propositions seems to be underused in mathematical reasoning, I discovered that I myself was --perhaps not surprisingly-- only vaguely familiar with all sorts of equalities. This note --which is not deep at all-- is written to remedy that situation. I shall not repeat that ∧ and ∨ are symmetric, associative and mutually distributive; neither shall I repeat de Morgan's laws.

The following expressions (E0.i) are all equal.

 (E0.0) P (E0.1) ¬¬P (E0.2) P ∨ P (E0.3) P ∧ P (E0.4) P ∨ F (E0.5) P ∧ T (E0.6) P ∨ (P ∧ Q) (E0.7) P ∧ (P ∨ Q)

With the possible exception of the last two, (the so-called "Laws of Absorption") this is very familiar ground. Also expressions (E1.i) are all equal.

In the following, = has the lowest binding power

 (E1.0) P = Q (E1.1) ¬P = ¬Q (E1.2) (P ∨ ¬Q) ∧ (¬P ∨ Q) (E1.3) (P ∧ Q) ∨ (¬P ∧ ¬Q)

Also expressions (E2.i) are all equal; since (E2.0) is symmetric, they occur in pairs.

 (E2.0) P ∨ Q (E2.1) P ∨ ¬Q = P (E2.2) ¬P ∨ Q = Q (E2.3) P ∧ ¬Q = ¬Q (E2.4) ¬P ∧ Q = ¬P (E2.5) P ∧ (R ∨ ¬Q) = (P ∧ R) ∨ ¬Q (E2.6) (¬P ∨ R) ∧ Q = ¬P ∨ (R ∧ Q)

The last two were absolutely new for me; their discovery --in a completely different context-- provided the incentive to write this note.

 Plataanstraat 5 5671 AL NUENEN The Netherlands 5 October 1981 prof.dr. Edsger W. Dijkstra Burroughs Research Fellow

Transcriber: Kevin Hely.
Last revised on Sun, 22 Jun 2003.