De Morgan’s Laws are (Mostly) Constructive!

Most programmers and anybody with a basic knowledge of logic will have heard of De Morgan’s Laws. They provide an easy way to switch back and forth between “or” and “and” in Boolean logic, which is very handy.

When I was first introduced to intuitionistic logic,  I remember being somewhat scared off it by the statement that De Morgan’s Laws don’t hold in it.  This will make any programmer nervous!

So, it came as a surprise to me to learn that in fact three quarters of the propositions that make up De Morgan’s Laws still hold for intuitionistic logic!

It is interesting to examine why.  De Morgan’s Laws can be broken up into four implications:

1)      (¬ P) ∧ (¬ Q) → ¬ (P ∨ Q)

2)      ¬ (P ∨ Q) → (¬ P) ∧  (¬ Q)

3)      (¬ P) ∨ (¬ Q) → ¬ (P ∧ Q)

4)      ¬ (P ∧ Q) → (¬ P) ∨  (¬ Q)

Of these four implications, only the fourth one fails for intuitionistic logic!

Let’s check.

Case 1) If I have a proof that P is false, and a proof that Q is false than I can’t possibly find a proof that either P or Q is true, by the basic definition of ∨.

Case 2) If I have a proof that P ∨ Q can’t be true, then clearly there is no proof for either of P or Q, by the basic definition of ∨.

Case 3) If I have a proof that P is false, or a proof that Q is false, there can’t possibly be a proof that both P and Q are true, again by the basic definition of ∧.

So far so good.  But here is where things go awry.

Case 4) If I have a proof that both P and Q can’t be true at the same time, that doesn’t tell me for sure that I have proof that either one in particular is false.  They just can’t both be true.   So case 4) isn't guaranteed to always be true, and therefore isn't a law after all.


However, if I find a definite proof that one of P or Q is true, I can still conclude that the other is false.  This can be formalized as:

      4')      ¬ (P ∧ Q) → P → ¬ Q

So even this fourth case, with a small caveat, still contains a lot of useful information. Maybe we can say that De Morgan’s Laws are more than three quarters constructive!

The moral of the story is not to be scared away by constructive (i.e. intuitionistic) mathematics: more of the familiar rules still work than you might think, even if you have to be a bit more careful around the edges.