[updated on 2014.04.12]
Instructor: Larry Moss (Indiana University)
Title: Natural Logic
(A) An overview.
This is a course on ‘surface reasoning’ in natural language. The overall goal is to study logical systems which are based on natural language rather than (say) first-order logic. Most of the systems are complete and decidable, the class will see a lot of technical work in this direction. At the same time, the work is elementary. One needs to be comfortable with informal proofs, but only a small logic background is needed to follow the course.
Specific topics include: extended syllogistic logics; logics including verbs, relative clauses, and relative size quantifiers; the limits of syllogistic logics, monotonicity calculi; and algorithms, complexity, and implementations. Time permitting, the course will also touch on proof-theoretic semantics, and on the relation of natural logic to textual entailment.
The topic of natural logic lends itself to philosophical reflections on the nature of semantics and is arguably something all formally-minded linguists and linguistically-minded logicians should know about.
(B) Outline of what the lectures will cover.
Here is my plan at this point:
(1) Introduction to the course and to the problem of inference in natural language. Syllogistic logic, including the completeness results for it. Historical results on syllogistic logics and on their modern reconstructions. Computer implementations, with a special emphasis on the underlying algorithms.
(2) Further syllogistic systems: logics with verbs, relative clauses, and intersective adjectives. For each of these systems we again want to study the logics, the completeness results, and the algorithms.
(3) This lecture will have two parts. First, I will discuss logics that go beyond syllogistic logics: why they are needed, and how one formulates them in such a way as to have decidability and completeness. In addition, I’ll discuss proof search and tableaux for them. Second, I’ll discuss logics that are syllogistic but go beyond first-order logic due to quantifiers like “Most X” or to sentences of the form “There are at least as many X as Y”. This material is rather combinatorial.
(4) Monotonicity in natural language and in ordinary mathematics. Monotonicity and polarity. Then, an introduction to categorial grammar and the way that the typed-lambda calculus is used in the semantics. This material is already a kind of crash course on categorial grammar. We then put categorial grammar together with monotonicity to get new type systems, and we introduce a formalization of van Benthem’s monotonicity calculus. Finally, we want to study “logic without grammar”, that is, logical reasoning based on sentences in real life, with connections to the problem of textual entailment.
(5) Usually at a summer school I don’t plan a last day, but instead use it to finish topics that were started on one of the previous days, or to say more on one or two days’ lectures, depending on student interest. I also will go over some of the homework problems that will have been given earlier in the course. Finally, I present some specific open problems and topics of research that students might want to get involved in.
These plans might change, of course.
One should be interested in the topics in the outline. One also should be comfortable with mathematical proofs. The best specific preparation would be completeness proofs for propositional logic and first-order logic, or even modal logic. This is mostly important for the first three days. Days 4 and 5 rely less on this, and it would be possible to attend them without some of the more technical material of the first three lectures.
Here are my slides from ESSLLI 2010:
I will update these with my EASLLC slides later.
Here is a relevant paper for the first two lectures: http://arxiv.org/abs/0808.0521
For the lecture on monotonicity, see my paper with Thomas Icard at
Finally, I’ll try to make a book-length presentation of the course.