Ling 726: Mathematical Linguistics, Logic, Section 2: Predicate Logic V. Borschev and B. Partee, October 7, 2004 p. 1 Lecture 6. Logic. Section 2: Predicate Logic. 1. Predicate Logic........................................................................................................................................... 1 1.0. Informal introduction........................................................................................................................... 1 1.1. Syntax.................................................................................................................................................. 4 1.2. Semantics............................................................................................................................................. 5 2. Axioms and theories. ................................................................................................................................. 8 2.1. Tautologies, contradictions and contingencies .................................................................................... 8 2.2. Logical equivalence and laws of Predicate Logic................................................................................ 8 2.3. Axioms and theories ............................................................................................................................ 8 Homework 7. for Thurs October 14 ............................................................................................................ 10 Reading: Predicate Logic: Chapter 7: 7.1 – 7.2, Chapter13: 13.1.2 of PMW, pp. 135 –152, 321-331. Axioms and theories: Chapter 8: 8.1 (179-183), 8.5.1-8.5.4 (198 – 205). 1. Predicate Logic 1.0. Informal introduction Predicate Logic (or Predicate Calculus) is the most well known and in a sense the prototypical example of a formal language. On the other hand, Predicate Logic (PL) was not just invented by logicians. It was in a way extracted from the natural language as some special and important part of it. But for a long time it was used mostly for purposes of mathematics (and metamathematics) and was elaborated as a formal language. In studying Predicate Logic we would like to demonstrate features of formal languages which are most important for us: the notions of model and model-theoretic semantics, and the Principle of Compositionality (which we used already in Statement Logic). We begin with some examples and remarks. More exact definitions are given below. The sentences John loves Mary and Everyone whom Mary loves is happy can be represented as formulas of PL: John loves Mary love (John, Mary) Everyone whom Mary loves is happy ∀x(love(Mary, x) → happy(x)) The formula ∃x(even(x) & (x > 1)) says that there are even numbers greater than 1. Formulas and other expressions of PL are built from individual constants (or simply “constants”), (individual) variables, predicate constants (or predicate symbols), logical connectives (the same as in statement logic) and quantifiers. Each expression belongs to a certain type. The type structure of PL is very simple: individuals, relations of different arities, and truth-values. In our examples we use the following expressions:Ling 726: Mathematical Linguistics, Logic, Section 2: Predicate Logic V. Borschev and B. Partee, October 7, 2004 p. 2 Expressions Types ========================================================= John, Mary, 1, 2, … constants  individuals  terms x, y, z, x1, y1, z1, x2, ... variables  individuals happy, even unary predicate constants unary relations love, > binary predicate constants binary relations love (John, Mary)  love(Mary, x)  happy(x)  even(x)  formulas truth-values (x > 1)  ∀x(love(Mary, x) → happy(x))  ∃x(even(x) & (x > 1))  The first five formulas are examples of atomic formulas. Four of them are written in prefix notation and the formula (x > 1) is in infix notation. The prefix notation will be our legal one but we will use sometimes the infix notation for examples like our arithmetic one where it is traditional. We can consider Predicate logic as an extension of Statement Logic (in fact, it is better to consider Statement Logic as a very simple but important part of Predicate Logic). Atomic formulas of Predicate Logic such as love (John, Mary) or even(x) can be considered as representations of atomic statements of Statement Logic (although to evaluate atomic formulas we need to evaluate variables). Complex formulas of PL are constructed from more simple ones with the help the same connectives as in SL and also with the help of quantifiers. Expressions of Predicate Logic are interpreted in models. The structure common to all of the models in which a given language is interpreted (the model structure for the model-theoretic interpretation of the given language) reflects certain basic presuppositions about the “structure of the world” that are implicit in the language. For PL, any given model consists of the set of truth values {1,0}, a domain D which is some set of objects (or entities), and some n-ary relations on this set. A model, or interpreted model, consists of a model structure plus a (“lexical”, or “basic”) interpretation function I which assigns semantic values to all constants. M = <D, I>Ling 726: Mathematical Linguistics, Logic, Section 2: Predicate Logic V. Borschev and B. Partee, October 7, 2004 p. 3 So models of PL presuppose a very simple structure of the world. Objects of such a model have no inner structure, they are just “points” of the domain, and relations are collections of tuples of these objects. The interpretation function I links individual constants with elements of domain and predicate symbols with relations. An interpretation ║║M , built up recursively on the basis of the basic interpretation function I, assigns to every expression α its semantic value ║α║M in a given model M. (More precisely, ║α║M,g, where g is an assignment function, evaluating variables). These semantic values must correspond to the types of the expressions. Thus, in our examples, to the individual constants John and Mary are assigned certain objects, individual variables take their values in the set of objects (entities), to the predicate constant