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 . When talking about people this might be the collection of all people. When talking about natural numbers this might be the set . When talking about real numbers this might be the set . When talking about curves it might be the set of subsets of the plane, , etc.

The collection of objects in this case is the set of subsets of , denoted .

Suppose, for the purposes of illustration, that

.

Consider the subsets , and .

in the obvious way.

### AND

Note that two objects are contained both in AND in . We call the set of such objects the *intersection *of AND , :

.

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

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

### OR

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

.

*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:

= (in A) OR (in B) OR (in both) = (in A) OR (in B) OR (in )

We can represent the union as follows:

### 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 . For example, Chuck Norris is NOT in the set — but we don’t chuck Chuck Norris into the complement of — only objects in the ambient set in which the objects in ‘live’.

For a set , we denote this set by and so, for example, for the instance of sitting in above:

.

We can also represent the complement using a Venn Diagram, for example, :

### De Morgan’s Laws

Now consider all the objects that are in :

.

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

, ,

the objects that are in AND are the intersection of these sets:

,

which is the same as so we have demonstrated that

.

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

.

## 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* . 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 and are sentences, then their *conjunction *is the sentence

The conjunction is true whenever AND are true and so the conjunction is AND.

For example, with and ,

() ()

is a false statement, while

() ()

is a true sentence.

Therefore the conjunction is AND.

### OR

The *disjunction *of sentences and is the sentence

,

which is true whenever OR is true (mathematical OR); that is is true if and only if

is true or is true.

### NOT

The *negation *of a sentence is a sentence , which is true whenever is false.

For example, where ,

()

is true, because () is false.

Indeed

(1 is an element of ) = (1 is *not *an element of ),

and so the negation is NOT.

### De Morgans’s Laws

Now consider for sentences the sentences:

.

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

, and ,

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

and .

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

and .

## Switches

### The Collection of Objects

Consider a set of switches.

.

Each switch may be ON OR OFF.

### AND

We can combine switches in *series:*

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

### OR

We can combine switch in *parallel*:

We denote such a switch by . The switch is on if is on OR is on.

### NOT

So consider the operation of flipping a switch: from on to off or vice versa. For example, if is on, then is off, that is:

.

### De Morgan’s Laws

Now ask the question: when is off, that is is on? This can only happen with both is off AND is off, that is when both is on and is on:

.

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

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

## Functions

### Collection of Objects

Consider the set and consider the collection of all 0-1 valued functions on .

For example, consider defined by

,

which we can write in ordered pair notation:

.

Consider also defined by:

.

We can combine elements and of in two particular ways.

The first is the *max *function defined by

.

For example,consider as above.

Well, anyway,

.

and we have:

.

Similarly we can define the *min *function , for example:

.

Consider for a function the function , given by:

,

so for example we have

,

so that is found by flipping the values .

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

, and

.

## Epilogue: Proofs and Counterexamples

### Proofs

Let be the statement that for fixed :

.

It is quite easy to find pairs such that is true. For example, is true because

.

In mathematics, when we say is true, as in

is true,

we actually mean the statement :

for any possible pair , is true.

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

### Counterexamples

Let be the statements that for :

is a prime number.

Again, it is quite easy to find numbers such that is true. For example, is true because:

is a prime number.

Consider the statement that

for any natural number, is true.

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

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 is FALSE is true and by De Morgan

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

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

is NOT a prime.

As it happens, says that

is a prime number,

which is false, because .

Therefore is false.

There exists no counterexample to .

## Leave a comment

Comments feed for this article