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

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.

## No comments:

## Post a Comment