EWD804-0

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


EWD804-1
(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.