Sunday, 22 February 2009

"The Sheffer stroke problem."

Wikipedia is wrong.
This recent revelation has come as quite a shock to me. Obviously hundreds of people deride Wikipedia for its bias and its inaccuracies which, when uncorrected, can grow exponentially. But I’ve always relied on Wikipedia nonetheless: it’s my default place to go to for information; I have a search bar that links to it in the corner of my Firefox window; I trusted it.
Yesterday I discovered that it is completely and utterly wrong about the Sheffer stroke. The Sheffer stroke is a piece of logical notation which Blogger won't allow me to show you because it doesn't have the font set (I'll use the forward slash instead: /). It is used in logical formulae such as the kind in Wittgenstein’s Tractatus where, in 5.1311, Wittgenstein claims that all the other logical constants can be defined from it. The Sheffer stroke means ‘neither _ nor _’ which is expressed in computer science as a NOR function. Therefore (p v q)(p or q) can be defined as ((p/q) /(p/q))(Not (not p or q) or (not p or q).
Wikipedia claims that the Sheffer stroke means NAND ie. ‘not _ and _’ where the not operator has scope over the whole formula not the first variable.
Logicians beware: common usage and Wikipedia has transformed the Sheffer stroke into a NAND operator. It is not to be confused with the Pierce arrow. Here is a discussion regarding this widespread logical misuse and here (for those with access to JSTOR) is the original Sheffer article with the catchy title “A Set of Five Independent Postulates for Boolean Algebras, with Application to Logical Constants”. On page 487, he clearly defines his stroke as ‘neither nor’.
Both the NAND and the NOR interpretations are fine as long the notation makes it clear how it is being used: it appears that the language of logic, just like ordinary languages, is constantly fluctuating and evolving based upon the dictates of custom. However the traditionalist NOR interpretation is technically the correct one based on what Sheffer wrote.
Now that I can no longer trust Wikipedia, my knowledge base crumbles. Now, I know nothing except the fact of my ignorance.


Momo said...

More than two years later, the error is still there.

Nao said...

Sheffers definition from page 487;
" p /\ q = ~ ( p \/ q ) "

From the 7th footnote on page 487 of sheffer's paper;
"** By analogy with subject and object, we may call p /\ q the reject of p and q"

In the modern day, we use \/ for the disjunction, but the original paper used it as a conjunction, and /\ (and | ) for his stroke. He clearly states this in the footnote. He also says that it means the same as "neither p nor q", but that's not the same as "not ( p or q )".

You are a moron for not doing enough research even to read to the bottom of the page you yourself cite.

Simon Barron said...

Hi there! Thanks for the comment.

You're right and it comes down to the fact that the natural language formulation 'neither p nor q' means NAND rather than NOR (which I wrongly read it as when I wrote this 2 years ago). Which would mean that in this instance, contrary to my previous interpretation, Wikipedia is right and Wittgenstein in the Tractatus is wrong (he definitely uses it as NOR).

Feels good to do some reading on formal logic problems again.

Anonymous said...

Dear logicians,
"Neither nor" is usually translated as as a conjunction of negations, which is the negation of disjuncts "not either"(see all the elementary books of Introduction to Logic take P. Hurley Intro ). If there is anything to discuss here at all it is only one part of it that "neither" should be translated as "not either" and not otherwise.
There is definitely a mistake in the post about conjunction being a negation of a disjunction. Conjunction of negations is the negation of a disjunction
As for special signs for logic you may substitute "and" by & which is widely used in most of the logical books.
Last, but mot least, Sheffer stroke is usually considered to be not the conjunction of negations but the disjunction of negations or the negation of conjuncts, whatever you prefer.
It would be helpful also to explain why this Sheffer stroke matters at all...
Disjunction is a well formed formula A v B (A or B)
Conjunction is a well formed formula A & B (A and B)