Negation
By Robert Laing
It is a very common mistake to imagine that the denial of a proposition gives the right to affirm the contrary; whereas it should be that the affirmation of a proposition gives a right to deny the contrary.— First Notions of Logic, Augustus De Morgan
In logic, negation is a unary operator which toggles whichever of the two values a variables holds — I’m using 1 or 0, but it could be true or false, ⊤ or ⊥, yes or no, on or off, … — to the other.
| p | p |
|---|---|
| 1 | 0 |
| 0 | 1 |
Of the many notations for NOT, I favour p over ¬p to avoid confusion with arithmetic’s minus sign. Whereas AND in logic algebra is nearly identical to product and OR is nearly identical to sum, -p is meaningless when p can only be 1 or 0.
Translating logic negation to set complement is full of traps for the unwary.
For instance thinking that when φ is a = b as in P = σa = b(R), it means we can get Pc by simply φ as in σa != b(R) is a mistake most people will make on their first attempt at writing a database query for “Which students have not applied for CS?” used in the next section NOT. I suggest trying to write the correct query in SQL or Prolog yourself before proceeding to get an idea of the spiked pitfalls that await.
The Law of Excluded Middle
p + p = 1
Logic’s law of the excluded middle says that p or not p is a tautology, ie always true. That is, something is either true or false; there is no middle ground.
By negating both sides of the above equation and then using De Morgan’s Law on the left-hand side, the law of excluded middle can alternatively be written:
p · p = 0
We need the above in equivalence to get from (p + q) · (q + p) to p · q + p · q.
I discovered the word casuistry — the use of clever but unsound reasoning — reading old logic textbooks, and I’d say confusing people by stating p and then suggesting a misleading p is a common form of this.
An example is the barber puzzle, associated with Russell’s Paradox. Betrand Russel used it as an illustration to simplify why he didn’t share Gottlob Frege’s conviction that all of mathematics could be boiled down to boolean functions, the φ in what relational algebra calls selection σφ(R).
I can’t claim to fully understand Russell’s Paradox, but the barber puzzle in no ways makes me think Frege was wrong.
The barber puzzle
A town’s barber claims to shave everyone who does not shave himself. So who shaves the barber?
I’d say the conundrum relies on a slight of hand to trick people into thinking if p = “shaved by the barber” then p = “self-shaved”, whereas “not shaved by the barber” and “self-shaved” are separate propositions.
The puzzle encourages us to jump to the wrong conclusion that we are looking at diagram 5 where “shaved by the barber” and “self-shaved” are disjointed sets.
Actually, it’s diagram 4. We can think of the left-hand set as σ“Shaved by the barber”(P) and the right-hand set as σ“Self-shaved”(Q). The barber could pass both tests, making him the sole element of σ“Shaved by the barber”(P) ∩ σ“Self-shaved”(Q) without contradicting the law of the excluded middle.
That’s assuming the barber is a clean shaven man. Why are we sure the barber isn’t a woman?
Set Complement
It’s easy to forget circular sets have surrounding rectangles, and the town won’t just consist of cleanly shaven men.
Forgetting the surrounding rectangle, E, is a trap that awaits in getting “Which students have not applied for CS?” right.
Negation as failure
Prolog follows a convention called negation as failure (NAF to its friends) which tripped me up initially, and I suspect will most other people learning the language.
To illustrate NAF, lets quickly return to our simple query for “Which studends applied for ‘CS’?” and let me repeat the way this data is stored in Prolog:
%! apply(?SID:integer, ?CName:text, ?Major:text, ?Decision:text) is nondet
apply(123, 'Stanford', 'CS', 'Y').
apply(123, 'Stanford', 'EE', 'N').
apply(123, 'Berkeley', 'CS', 'Y').
apply(123, 'Cornell', 'EE', 'Y').
apply(234, 'Berkeley', 'biology', 'N').
apply(345, 'MIT', 'bioengineering', 'Y').
apply(345, 'Cornell', 'bioengineering', 'N').
apply(345, 'Cornell', 'CS', 'Y').
apply(345, 'Cornell', 'EE', 'N').
apply(678, 'Stanford', 'history', 'Y').
apply(987, 'Stanford', 'CS', 'Y').
apply(987, 'Berkeley', 'CS', 'Y').
apply(876, 'Stanford', 'CS', 'N').
apply(876, 'MIT', 'biology', 'Y').
apply(876, 'MIT', 'marine biology', 'N').
apply(765, 'Stanford', 'history', 'Y').
apply(765, 'Cornell', 'history', 'N').
apply(765, 'Cornell', 'psychology', 'Y').
apply(543, 'MIT', 'CS', 'N').
Querying the above with apply(SID, _, 'CS', _). will cause Prolog to run
through the above facts in the provided order, matching 123 twice, then 345 etc.
I initially assumed the query “Which studends have not applied for ‘CS’?” could be
done by negating the first query, ie \+ apply(SID, _, 'CS', _).
But it turns out the negated version doesn’t run throug the facts to check each value
of SID — negated Prolog queries don’t give meaningful results if they are given
unset variables. Personally, I think an
ERROR: Arguments are not sufficiently instantiated...
would be more helpful than false. But the NAF convention is to reply to
ambiguous questions with false rather than throw errors.
Before using negated statements, we have to instantiate (ie lookup and set) all the variables they contain to avoid simply getting a meaningless false. Spoiling the next subsection not we can find “Which studends have not applied for ‘CS’?” like so:
student(SID, _, _, _),
\+ apply(SID, _, 'CS', _).
Note the above two statements will only work in that order. If you put the negated statement first, NAF causes it to simply return false — one of many examples of how claiming Prolog is a declarative programming language (one where control flow doesn’t matter because anded together statements are supposedly commutative and associative) just causes confusion, a discussion I’ll take further in series.
Next, lets write a query for “Which students have not applied for CS?”