Four Flavours of De Morgan

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:

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:

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}$ :

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$ .

Comments feed for this article

	J.P. McCarthy on MATH6040: Spring 2022, Week…
	J.P. McCarthy on MATH6040: Spring 2022, Week…
	J.P. McCarthy on MATH7019: Winter 2020, Week…
	J.P. McCarthy on MATH7019: Winter 2020, Week…
	A Sufficient Conditi… on Almost All Trees have Quantum…

Four Flavours of De Morgan

Sets

The Collection of Objects

AND

OR

NOT

De Morgan’s Laws

Logic

The Collection of Objects

AND

OR

NOT

De Morgans’s Laws

Switches

The Collection of Objects

AND

OR

NOT

De Morgan’s Laws

Functions

Collection of Objects

Epilogue: Proofs and Counterexamples

Proofs

Counterexamples

Recent Comments

Categories

J.P. McCarthy Maths

Leave a comment

Leave a Reply Cancel reply

Four Flavours of De Morgan

Sets

The Collection of Objects

AND

OR

NOT

De Morgan’s Laws

Logic

The Collection of Objects

AND

OR

NOT

De Morgans’s Laws

Switches

The Collection of Objects

AND

OR

NOT

De Morgan’s Laws

Functions

Collection of Objects

Epilogue: Proofs and Counterexamples

Proofs

Counterexamples

Share this:

Like this:

Related

Recent Comments

Categories

J.P. McCarthy Maths

Leave a comment

Leave a Reply Cancel reply