Introduction
In the 19th century, British mathematician and logician, Augustus De Morgan came up with notation to prove what the negation of a conjunction and the negation of a disjunction is equivalent to.
The equivalences he formed are today known as De Morgan's Laws. One of them shows how to negate a disjunction, while the other shows how to negate a conjunction. In this chapter, we shall understand De Morgan's Laws completely from natural intuition and then give a generalised version of both the laws.
First law — negating a disjunction
Let's say you were given the following proposition:
and were asked to write its negation precisely. What would you write?
First of realise that the given proposition is a disjunction of the two simpler statements 'The Java programming language was made in 1970s.' and 'The Java programming language was made in the 1980s.'.
In the actual proposition listed above, we don't repeat the starting block of words (i.e 'The Java programming language was made'), since that is implicitly implied in the context of the whole statement.
Anyways, coming back to the proposition, it says that either Java was made in 1970s or in 1980s, or maybe both (which might sound impractical, but is OK for now).
We now have to negate this statement? What to write?
Well, we just need to declare the opposite of what we said in the original statement. That's all!
So following from our understanding of the given proposition, its negation would mean that Java was not made in the 1970s, and it was also not made in the 1980s.
Expressed below is the negation:
Let's model this translation symbolically:
::p:: : Java was made in the 1970s.
::q:: : Java was made in the 1980s.
With these atomic propositions, the original proposition could be represented as follows:
And, similarly, its negation could be written as follows:
Let's check whether the negation of the original propositional formula (i.e ::\neg (p \vee q)::) is actually the same as the second formula (i.e ::\neg p \wedge \neg q::), using our old friend — a truth table.
| ::p:: | ::q:: | ::p \vee q:: | ::\neg (p \vee q):: | ::\neg p:: | ::\neg q:: | ::\neg p \wedge \neg q:: |
|---|---|---|---|---|---|---|
| ::\text T:: | ::\text T:: | ::\text T:: | ::\text F:: | ::\text F:: | ::\text F:: | ::\text F:: |
| ::\text T:: | ::\text F:: | ::\text T:: | ::\text F:: | ::\text F:: | ::\text T:: | ::\text F:: |
| ::\text F:: | ::\text T:: | ::\text T:: | ::\text F:: | ::\text T:: | ::\text F:: | ::\text F:: |
| ::\text F:: | ::\text F:: | ::\text F:: | ::\text T:: | ::\text T:: | ::\text T:: | ::\text T:: |
What sounds right, even works out right mathematically! Isn't this amazing?
Time to formally define the first law of De Morgan:
In words, this law states that the negation of a disjunction is the same as the conjunction of the negations.
Second law — negating a conjunction
Consider the proposition:
Stating the proposition fully, we get: 'Python supports object-oriented programming and Python supports procedural programming.'
Once again, to negate this statement, we ought to specify its opposite.
That is, the negation would mean that Python does not support both object-oritented and procedural programming. It might just support one or, in the worst case, none.
This can be said as follows:
See what this statement means — Python does not support object-oriented programming, or it does not support procedural programming, or does not support both. This is just what we wanted to express as the negation of the original statement.
As before, let's model all this symbolically:
::p:: : Python supports object-oriented programming.
::q:: : Python supports procedural programming.
By this means, the original statement would be expressed as:
While the negated statement shown above would be expressed as:
This asserts that the proposition ::\neg (p \wedge q):: is the same as ::\neg p \vee \neg q::. Why not confirm it using a truth table.
| ::p:: | ::q:: | ::p \wedge q:: | ::\neg (p \wedge q):: | ::\neg p:: | ::\neg q:: | ::\neg p \vee \neg q:: |
|---|---|---|---|---|---|---|
| ::\text T:: | ::\text T:: | ::\text T:: | ::\text F:: | ::\text F:: | ::\text F:: | ::\text F:: |
| ::\text T:: | ::\text F:: | ::\text F:: | ::\text T:: | ::\text F:: | ::\text T:: | ::\text T:: |
| ::\text F:: | ::\text T:: | ::\text F:: | ::\text T:: | ::\text T:: | ::\text F:: | ::\text T:: |
| ::\text F:: | ::\text F:: | ::\text F:: | ::\text T:: | ::\text T:: | ::\text T:: | ::\text T:: |
Intuitively, it turns out that our assertion was perfectly valid. Time to formally define this equivalence.
The second law of De Morgan states that:
In words, this law says that the negation of a conjunction is the same as the disjunction of the negations.
Generalised De Morgan's laws
Let's say we have the disjunction of three propositional variables ::p::, ::q:: and ::r::, and want to find its negation. What would it be?
Let's just compute it using the laws expressed above:
It turns out that we negate the disjunction of three variables similar to how we negate the disjunction of two variables.
In the negation, each variable gets negated itself, while the disjunction symbol (::\vee::) gets replaced by the conjunction symbol (::\wedge::).
In fact, this applies to the disjunction of ::n:: number of variables. This means that
Noting that ::p_{1} \vee p_{2} \vee \dots \vee p_{n}:: can be expressed as ::\bigvee^{n}_{i = 1}p_{i}::, we could state the generalised version of the first De Morgan's law as follows:
All the discussion above applies to conjunctions as well. Therefore, the second law can also be expressed in the same way:
