Language and logic

Asked “Would you like tea or coffee?”, you answer “both”. The host is taken aback; the logician smiles.

Is “both” a correct answer according to logic? And is the statement “If 2 > 4, then Prague is in Brazil” true?

• “Or”: in speech often exclusive (“tea or coffee?”), in logic and in code inclusive.
• “If”: in speech we expect a link of cause and effect, in logic we don’t.
• Precedence: language expresses it with intonation and commas, a formal language with brackets and rules. That is why AND binds more tightly than OR, and why it pays to use brackets in conditions.

Logic has always rested on the question of what a sentence says. That is why, throughout its history, it was moved forward by people who studied language. Logic and linguistics were born together, parted ways and met again in the computer. This page is an insert to the chapter Logic.

Who decides that “Is it raining?” is not a statement – the grammarian or the logician?

The Stoics were grammarians too. The same people who invented the statement and the connectives (Chrysippus and his school, see the chapter Logic) also worked out the theory of grammatical cases and parts of speech.

We still carry a trace of this today. The Greek ptōsis means “a fall”; the Romans translated it as casus, and English took it over as case. Whenever you talk about the nominative or the genitive case, you are using a Stoic word.

The Stoic grammatical works have not survived in full; we know their teaching mainly from later authors, for example Diogenes Laertius (Lives of the Eminent Philosophers, Book VII).

Question, command, wish, address, declaration: grammar distinguishes many kinds of sentences. Logic chose only those of which it makes sense to ask “does it hold?”, and called them statements.

In the sentence “A man is running” and in the sentence “Man is a species” the same word appears. Does it point to the same thing in both?

At the universities of Paris and Oxford in the 13th and 14th centuries, logic was taught as the foundation of all study. Medieval logicians (for example Peter of Spain in the 13th century or William of Ockham in the 14th) investigated what exactly a word refers to in a given sentence. They called it suppositio, “standing for”: a word in a sentence stands for certain things, and which ones depends on the sentence.

Alongside them worked the Modistae, grammarians who looked for general “modes” (modi) of expression common to all languages. The best-known Modist work, the Grammatica speculativa of Thomas of Erfurt (early 14th century), is one of the first attempts at a universal grammar.

• Personal (suppositio personalis): “A man is running.” The word stands for individuals.
• Simple (suppositio simplex): “Man is a species.” The word stands for a concept.
• Material (suppositio materialis): “Man is a noun.” The word stands for itself.

This is a forerunner of today’s distinction between variable and value. A programmer does the same thing every day:

// personal: a concrete value
  man.run()
  // simple: a type, a concept
  class Man { }
  // material: the word itself, a string
  "man".length   // 3

“Every student doesn’t know Python.” Does that mean that nobody knows it, or that somebody doesn’t?

Gottlob Frege (1848–1925), professor of mathematics in Jena, distrusted language. He considered natural language imprecise and ambiguous, and so he created an artificial concept script (Begriffsschrift) – the first formal language with the quantifiers “for all” and “there exists”. Today’s predicate logic comes from it.

The symbols ∀ and ∃ are not Frege’s. Frege wrote two-dimensionally, with lines and hooks; the reversed E (∃) was introduced by Giuseppe Peano, and the inverted A (∀) caught on only in the 20th century.

“Every” and “some” are not names of things, but instructions for going through all things: ∀x “for every x it holds that…”, ∃x “there exists an x for which…”. With them the ambiguity disappears from the question:

nobody knows it:  ∀x (S(x) ⇒ ¬P(x))
somebody doesn’t know it:  ¬∀x (S(x) ⇒ P(x))

In code you meet quantifiers as every() and some():

people.every(x => !student(x) || python(x))  // ∀x (S(x) ⇒ P(x))
  people.some(x => student(x) && !python(x))   // ∃x (S(x) ∧ ¬P(x))

The sentence “The Nothing itself nothings” is grammatically fine: subject, verb. But does it say anything at all?

The Vienna Circle, a group of philosophers, mathematicians and physicists in Vienna in the 1920s and 1930s, wanted to “clean up” the language of science: to keep only sentences that are either logically true or verifiable by experience. One of its leading members was Rudolf Carnap (1891–1970), who taught at the German University in Prague from 1931 to 1935.

In 1932 he wrote the article The Elimination of Metaphysics through Logical Analysis of Language. It is famous for its attack on Martin Heidegger’s sentence “The Nothing itself nothings” (from the lecture What Is Metaphysics?, 1929): according to Carnap the sentence looks grammatically correct but violates logical syntax, because it turns “nothing” into a noun.

Carnap’s Logical Syntax of Language treated language as a calculus: an alphabet (which signs we may write), formation rules (which strings are well-formed) and rules of inference (what follows from what). That is exactly how a programming language is built: characters, grammar, evaluation rules.

Carnap’s analysis of Heidegger’s sentence can be shown with an ordinary conversation. “What is outside?” – “Nothing.” Logically this means that there is nothing outside, no x: ¬∃x outside(x). Here “nothing” is not the name of a thing but the negation of a quantifier. Whoever makes it a subject, nothings(Nothing), treats it like a thing, and the sentence loses its meaning even though the grammar is fine.

Programmers know this: code that gets through the parser but fails type checking. Syntactically correct, and still nonsense.

How many rules are enough to produce all correct English sentences, and no incorrect ones?

Noam Chomsky (born 1928) reversed the direction. Frege and Carnap wanted to replace or clean up language; Chomsky, in 1956–57, did the opposite and used formal grammars to describe natural language, ranking the grammars by their power (the Chomsky hierarchy). Computer scientists adopted it at once: regular expressions, the grammars of programming languages and the parsers in compilers are built directly on it.

The same book contains the famous sentence “Colorless green ideas sleep furiously”. It is grammatically correct, and yet it makes no sense: the same boundary between form and meaning that Carnap saw.

A formal grammar is a set of rewriting rules. The rule S → ( S ) S | ε says: replace the symbol S either with a pair of brackets with another S inside and after it, or with nothing. A single rule, and out of it come all correctly bracketed expressions.

Why can’t a regular expression do this? A regular grammar remembers only finitely many states, so it cannot count arbitrarily deep nesting. That is why neither HTML nor code can be parsed reliably with regular expressions, and why compilers need a context-free grammar.

Can every English sentence be translated into logic so that a computer can tell what follows from it?

Richard Montague (1930–1971), a logician at the University of California, Los Angeles, argued in papers from 1970 (English as a Formal Language, Universal Grammar) that there is no important theoretical difference between natural and formal languages. English can be described just as precisely as the language of logic. He thus founded formal semantics, which computer processing of language draws on today.

Where Frege abandoned language and Carnap wanted to clean it up, Montague claimed that no cleaning was needed: it is enough to find the rules by which the meaning of a sentence is composed from the meanings of its parts.

This principle is called compositionality (it is often attributed to Frege). Translating a sentence into logic is then a matter of composition: each word gets its symbol, and the structure of the sentence determines how to combine them. And the structure is exactly where mistakes can happen: try it.