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