We tell four tales of De Morgan.

In each case we have something that looks like AND, something that looks like OR, and something that looks like NOT.

Sets

The Collection of Objects

Consider a universe of discourse/universal set/ambient set  U. When talking about people this might be the collection of all people. When talking about natural numbers this might be the set \mathbb{N}. When talking about real numbers this might be the set \mathbb{R}. When talking about curves it might be the set of subsets of the plane, \mathcal{P}(\mathbb{R}\times \mathbb{R}), etc.

The collection of objects in this case is the set of subsets of U, denoted \mathcal{P}(U).

Suppose, for the purposes of illustration, that

U=\{1,2,3,4,5\}.

Consider the subsets A=\{2,3,5\}, and B=\{1,3,5\} .

in the obvious way.

AND

Note that two objects are contained both in A AND in B. We call the set of such objects the intersection of A AND B, A\cap B:

A\cap B=\{3,5\}.

We can represent the ambient set U, as well as the sets A and B — and the fact that they intersect — using a Venn Diagram:

graph1

We can demonstrate for a general A and B ‘where’ the intersection is:

Venn2.jpg

OR

Another set that can be formed from A and B is their union. The union of A and B, denoted A\cup B, consists of all those objects that are elements of A OR* elements of B. So, with the instances of A and B above:

A\cup B=\{2,3,5\}\cup \{1,3,5\}=\{1,2,3,5\}.

*The “OR” here is a ‘mathematical OR’ rather than an ‘exclusive OR’, the likes of which we sometimes use in every day speech:

Imagine the following question put to a ‘normal’ person and a mathematician, both of whom ate a starter and a dessert:

Question: Did you have starter or a dessert?

Responses:

‘Normal Person’: I actually had both.

Mathematician: Yes.

If you really want, you can think of the union as being all objects that are in A, OR in B, OR in both A AND B:

A\cup B = (in A) OR (in B) OR (in both) = (in A) OR (in B) OR (in A\cap B)

We can represent the union as follows:

Venn3.jpg

NOT

We can also talk about the complement of a set — the set of objects that are NOT in a set. Now there are lots of things that are NOT in the set A. For example, Chuck Norris is NOT in the set A — but we don’t chuck Chuck Norris into the complement of A — only objects in the ambient set U in which the objects in A ‘live’.

For a set A, we denote this set by \overline{A} and so, for example, for the instance of A sitting in U=\{1,2,3,4,5\} above:

\overline{A}=\overline{\{2,3,5\}}=\{1,4\}.

We can also represent the complement using a Venn Diagram, for example, \overline{A}:

Venn4.jpg

De Morgan’s Laws

Now consider all the objects that are in \overline{A\cup B}:

\overline{A\cup B}=\overline{\{1,2,3,5\}}=\{4\}.

This set contains objects that are NOT in A AND not in B:

\overline{A}=\{1,4\}, \overline{B}=\{2,4\},

the objects that are in \overline{A} AND \overline{B} are the intersection of these sets:

\overline{A}\cap\overline{B}=\{1,4\}\cap\{2,4\}=\{4\},

which is the same as \overline{A\cup B} so we have demonstrated that

\displaystyle \overline{A\cup B}=\overline{A}\cap \overline{B}.

This is known as De Morgan’s Law and is always true.

Look at what is says:

If an object is NOT in ‘A OR B’, then it must NOT be in A AND it must NOT be in B.

Similarly,

If an object is NOT in ‘A AND B’, then it is NOT in A OR it is NOT in B.

This is the other De Morgan’s Law

\displaystyle \overline{A\cap B}=\overline{A}\cup \overline{B}.

Logic

The Collection of Objects

Now I should really be careful with what I write here, but all we are really doing is analogy and so a lot of subtlety is being swept under the carpet.

Consider the set of all sentences S. A sentence is either true or false.

We will not define further what a sentence is (fairly big carpet used).

Examples

  • The capital of Ireland is Dublin (true)
  • Wednesday is not a weekday (false)
  • 4 is a prime number (false)
  • The word “Earth” contains five letters (true)

AND

If S_1 and S_2 are sentences, then their conjunction is the sentence

S_1\wedge S_2

The conjunction is true whenever S_1 AND S_2 are true and so the conjunction \wedge is AND.

For example, with A=\{2,3,5\} and B=\{1,3,5\},

(1\in A) \wedge (1\in B)

is a false statement, while

(2\in A) \wedge (1\in B)

is a true sentence.

Therefore the conjunction is AND.

OR

The disjunction of sentences S_1 and S_2 is the sentence

S_1\vee S_2,

which is true whenever S_1 OR S_2 is true (mathematical OR); that is S_1\vee S_2 is true if and only if

S_1 is true or S_2 is true.

NOT

The negation of a sentence S is a sentence \lnot S, which is true whenever S is false.

For example, where A=\{2,3,5\},

\lnot (1\in A)

is true, because (1\in A) is false.

Indeed

\lnot (1 is an element of A) = (1 is not an element of A),

and so the negation \lnot is NOT.

De Morgans’s Laws

Now consider for sentences S_1,S_2 the sentences:

\lnot (S_1\wedge S_2).

This is true whenever S_1\wedge S_2 is false. For S_1\wedge S_2 to be false, either S_1 OR S_2 (or both) must be false. That is either \lnot S_1 OR \lnot S_2 must be true, and so the truth values of

\lnot (S_1\wedge S_2), and (\lnot S_1)\vee (\lnot S_2),

are the same and we say they are equal as sentences:

\lnot (S_1\wedge S_2) and (\lnot S_1)\vee (\lnot S_2).

This is De Morgan’s Law for sentences. We also have a second De Morgan Law:

\lnot (S_1\vee S_2) and (\lnot S_1)\wedge (\lnot S_2).

Switches

The Collection of Objects

Consider a set of n switches.

\{S_1,S_2,\dots,S_n\}.

Each switch may be ON OR OFF.

AND

We can combine switches in series:

switch1

We denote such a switch by S_1\otimes S_2. We have S_1\otimes S_2 is on if if S_1 is on AND S_2 is on — that is the series switch is on if both constituent switches are on.

OR

We can combine switch in parallel:

switch2

We denote such a switch by S_1\oplus S_2. The switch S_1\oplus S_2 is on if S_1 is on OR S_2 is on.

NOT

So consider the operation of flipping a switch: from on to off or vice versa. For example, if S is on, then \text{flip}(S) is off, that is:

S\text{ is on}\Rightarrow \text{flip}(S),\text{ is off}.

De Morgan’s Laws

Now ask the question: when is S_1\oplus S_2 off, that is \text{flip}(S_1\oplus S_2) is on? This can only happen with both S_1 is off AND S_2 is off, that is when both \text{flip}(S_1) is on and \text{flip}(S_2) is on:

\text{flip}(S_1\oplus S_2)\text{ is on} \Leftrightarrow (\text{flip}(S_1)\otimes \text{flip}(S_2)\text{ is on}.

A similar situation holds when the flipped parallel switch is off and so we have that:

\text{flip}(S_1\oplus S_2)=\text{flip}(S_1)\otimes \text{flip}(S_2)

It might look different at this time, but this is a De Morgan’s Law for switches. Similarly we have:

\text{flip}(S_1\otimes S_2)=\text{flip}(S_1)\oplus \text{flip}(S_2)

Functions

Collection of Objects

Consider the set \{1,2,\dots,5\} and consider the collection of all 0-1 valued functions on \{1,2,3,4,5\}.

For example, consider f_1 defined by

f_1(1)=0,\,f_1(2)=1,\,f_1(3)=1,\,f_1(4)=0,\,f_1(5)=1,

which we can write in ordered pair notation:

f_1=\{(1,0),(2,1),(3,1),(4,0),(5,1)\}.

Consider also f_2 defined by:

f_2=\{(1,1),(2,0),(3,1),(4,0),(5,1)\}.

We can combine elements f_1 and f_2 of F in two particular ways.

The first is the max function \max(f_1,f_2) defined by

\max(f_1,f_2)(x)=\max\{f_1(x),f_2(x)\}.

For example,consider f_1,\,f_2 as above.

Well, anyway,

\max (f_1,f_2)(1)=\max\{f_1(1),f_2(1)\}=\max(\{0,1\})=1.

and we have:

\max(f_1,f_2)=\{(1,1),(2,1),(3,1),(4,0),(5,1)\}.

Similarly we can define the min function \min(f_1,f_2), for example:

\min(f_1,f_2)=\{(1,0),(2,0),(3,1),(4,0),(5,1)\}.

Consider for a function f\in F the function \text{toggle}(f), given by:

\text{toggle}(f)(x)=1-f(x),

so for example we have

\text{toggle}(f_1)=\{(1,1),(2,0),(3,0),(4,1),(5,0)\},

so that \text{toggle}(f) is found by flipping the values 0\leftrightarrow 1.

There are De Morgan’s Laws here also; namely:

\text{toggle}(\max(f_1,f_2))=\min(\text{toggle}(f_1),\text{toggle}(f_2)), and

\text{toggle}(f)(\min(f_1,f_2))=\max((\text{toggle}(f_1),\text{toggle}(f_2)).

Epilogue: Proofs and Counterexamples

Proofs

Let P_{(x,y)} be the statement that for fixed x,y\in\mathbb{R}:

x^2-y^2=(x-y)\times (x+y).

It is quite easy to find pairs (x,y) such that P_{(x,y)} is true. For example, P_{(9,6)} is true because

9^2-6^2=81-36=45=3\times 15=(9-6)\times (9+6).

In mathematics, when we say P_{(x,y)} is true, as in

x^2-y^2=(x-y)\times (x+y) is true,

we actually mean the statement P:

for any possible pair (x,y)\in\mathbb{R}\times \mathbb{R}, P_{(x,y)} is true.

To demonstrate the truth of this, one has to demonstrate the truth of (uncountably) many statements. Call this statement P: the power of algebra is that it can achieve this, algebra can prove the (countably) infinite conjunction:

P= \bigwedge_{x,y\in\mathbb{R}}(P_{(x,y)})

Counterexamples

Let Q_n be the statements that for n\in\mathbb{N}:

n^2+n+41 is a prime number.

Again, it is quite easy to find numbers n such that Q_n is true. For example, Q_{20} is true because:

20^2+20+41=461 is a prime number.

Consider the statement Q that

for any natural number, Q_n is true.

That is Q_1 is true and Q_2 is true and Q_3 is true… and we have infinitely many statements to prove again, because

Q=Q_1\wedge Q_2\wedge Q_3\wedge \cdots

We might again employ algebra to help us, but we struggle. Perhaps we believe the statement is in fact FALSE. De Morgan’s Theorem can help us with this. If Q is FALSE \lnot Q is true and by De Morgan

\lnot Q=(\lnot Q_1)\vee (\lnot Q_2)\vee (\lnot Q_3)\vee \cdots

is true. What this means is that at least one of these statements is true. That is, there exists an m such that \lnot Q_m is true aka Q_m is false.

So we search for a counterexample to the truth of Q_m; that is an m such that

m^2+m+41 is NOT a prime.

As it happens, Q_{40} says that

40^2+40+41=1681 is a prime number,

which is false, because 1681=41^2.

Therefore Q is false.

There exists no counterexample to P.