The Semantics of Predicate Logic

The Semantics of Predicate Logic 1. The Interpretation Function This handout is a continuation of the previous handout and deals exclusively with the semantics of Predicate Logic. When you feel comfortable with the syntax of Predicate Logic, I urge you to read these notes carefully. The business of semantics, as I have stated in class, is to determine the truth-conditions of a proposition and, in so doing, describe the models in which a proposition is true (and those in which it is false). Although we’ve extended our logical language, our goal remains the same. By adopting a more sophisticated logical language with a lexicon that includes elements below the sentence-level, we now need a more sophisticated semantics, one that derives the meaning of the proposition from the meaning of its constituent individuals, predicates, and variables. But the essentials are still the same. Propositions correspond to states of affairs in the outside world (Correspondence Theory of Truth). For example, the proposition in (1) is true if and only if it correctly describes a state of affairs in the outside world in which the object corresponding to the name Aristotle has the property of being a man. (1) MAN(a) Aristotle is a man The semantics of Predicate Logic does two things. It assigns a meaning to the individuals, predicates, and variables in the syntax. It also systematically determines the meaning of a proposition from the meaning of its constituent parts and the order in which those parts combine (Principle of Compositionality). For the sentence in (1), the semantics assigns a meaning to the individual a and the predicate MAN and systematically determines the truth-conditions of MAN(a) from the order in which these meanings combine, illustrated in (2). (2) MAN(a) qp MAN a What about the meaning of the individual constant a and the predicate constant MAN? The idea is this. The outside world is, among other things, a collection of objects. So we can represent it as a set, called the Domain of Discourse D, whose elements correspond to objects in the outside world. To reflect this correspondence, the elements in D are called entities. Whenever we say something about an entity 1 in D, we are saying something about the unique object it is associated to in the outside world. In other words, you can think of the set D is an abstract representation of the outside world. In Predicate Logic, individual constants denote entities in D. This captures the intuition that a proper name like Aristotle refers to a thing in the world, one we can point to and say ‘that’s Aristotle’. The Venn Diagram in (3) illustrates how this looks. (3) D          The set D represents the set of objects in the outside world        Individual constants denotes distinct entities in D   There are three distinct levels of representations now: (i) the proper name Aristotle, used in the object language; (ii) the individual constant a, used in the metalanguage, and (iii) the entity , used in the semantic representation of the world. Since you don’t have time to draw pictures or find icons online, there are other ways of distinguishing these three representations. For example: (i) Aristotle, (ii) aristotle', and (iii) a. I’m not picky about which notation you use as long as you keep the representations distinct. Here are three options. (4) Proper Name (object language - sentence) Individual Constant (metalanguage - proposition) Entity (semantics – outside world) a. Aristotle a b. Aristotle a' a c. Aristotle aristotle' a Individual constants denote entities. What do predicate constants denote? A predicate denotes a set of entities, i.e., a subset of D. This captures the intuition that a verb phrase like is a man refers to a collection of things in the outside world, each of which we can point to and say ‘that is a man’. Please keep in mind that this is not the sense of the expression is a man, but its extension in the outside world. This is illustrated in (5). (5) D      A predicate constant denotes a subset of D       2 So far I have described two things: how to represent the world using set theory and how to represent the meaning of individuals and predicates also using set theory. The function that associates individuals and predicates to the their meanings is called the Interpretation Function I. The interpretation function is at the heart of our semantics. It associates each individual constant to a unique entity and it associates each predicate constant to a unique fixed set of entities. Examples are given in (6). (6) a. I(a) = Aristotle b. I(n) = Nietzsche c. I(b) = Bob Dylan d. I(MAN) = { , , } is a man The truth-conditions for the proposition MAN(a) can now be stated in terms of the meaning of its constituent parts, i.e., in terms of I(MAN) and I(a). These truth-conditions are presented in (7), followed by three equivalent ways of stating these truth-conditions. (7) MAN(a) is true if and only if I(a) ∈ I(MAN) i. The proposition MAN(a) is true if and only if the interpretation of the individual a is an element of the interpretation of the predicate MAN ii. The proposition MAN(a) is true if and only if the entity denoted by the individual a is an element of the set denoted by the predicate MAN iii. The proposition MAN(a) is true if and only if the object corresponding to the individual a has the property corresponding the predicate MAN in the outside world Although I have been talking about these concepts with respect to the world as a whole, we want to restrict our attention to a small, completely specified piece of the world called a model M. The reasons were given when we looked at Propositional Logic. A model in Predicate Logic consists of a Domain of Discourse D and an Interpretation Function I. The model M1 in (8) is a small version of the world. It specifies a restricted set of entities (D). It also specifies the association between individuals and entities and between the predicates and subsets of entities (I). If you are ever asked to provide a model in Predicate Logic, then these are the two pieces of information you must provide. 3 (8) Model M1 D1 = { , , } , I1(a) = Aristotle I1(n) = Nietzsche I1(b) = Bob Dylan I1(r) = Rover I1(MAN) = { I1(SINGER) = { , } , } , I1(PHILOSOPER) = { is a man is a singer } , is a philosopher Given a specific model, like M1, the truth value of the proposition MAN(a) can be verified. In M1, we have I1(a) = and I1(MAN) = { , , }. It follows that ∈{ , , }. In other words, I1(a) ∈ I1(MAN). So in M1, the proposition MAN(a) is true. It is also possible to verify that the proposition PHILOSOPHER(r) is false in M1. We know that I1(r) = 2. and I1(PHILOSOPER) = { , }. It follows that ∉{ , }. Ordered Pairs and Relations The discussion in the previous section involved 1-place predicates, like MAN, which denote sets of entities. What about 2-place predicates? 3-place predicates? Etc. There are certainly plenty of verbs that translate into 2- and 3-place predicates so they cannot be ignored. Verbs like kiss and give. So what is the interpretation of a 2-place predicate like KISS? I.e., what is I(KISS)? There is an important characteristic n-place predicates have that is not relevant to 1-place predicates. Order. Consider the contrast in (9). 4 (9) a. Aristotle kissed Rover b. Rover kissed Aristotle Loosely speaking, it is possible for the first sentence in (9) to be true in the world and for the second to be false. In other words, the proposition expressed by the first sentence correctly describes the state of affairs in the world, whereas the proposition expressed by the second does not. The respective propositions are provided in (10). (10) a. KISS(a,r) b. KISS(r,a) The only difference between (10a) and (10b) is the order of the arguments, a and r. The order of the arguments clearly affects their truth-conditions. The lesson learned from this example is that the interpretation of the predicate KISS must be sensitive to the order of its arguments. Currently, we have a way of capturing this sensitivity to order. Relations. An ordered pair is a sequence of two elements, α and β. We write these elements between angled brackets, 〈α,β〉. This notation represents the fact that the first element in the sequence is α and the second is β. You can think of an ordered pair as a pair of coordinates, like the coordinates on a map: α is the first coordinate and β is the second. There are crucial differences between ordered pairs and sets. In an ordered pair, the order of the elements matters. So if the elements α and β are different, then 〈α,β〉 ≠ 〈β,α〉. Furthermore, even if the elements are the same, each element is treated as a distinct coordinate of the ordered pair, i.e., 〈α,α〉 ≠ 〈α〉. (11) Ordered Pairs a. 〈 b. 〈 (12) 〉 ≠ 〈 , , 〉 , 〉 ≠ 〈 〉 Sets a. { b. { , } = { , } = { } , } A relation is a set of ordered pairs. 5 Ordered pairs provide a way to distinguish between Aristotle kissed Rover and Rover kissed Aristotle. If we interpret the 2-place predicate KISS as a relationship of kissing between two entities, where one entity does the kissing and the other receives the kiss, this should capture the difference between (10a) and (10b). Here is an informal sketch of the semantics for KISS. Afterwards, I will give a formal definition of relations. The 2-place predicate KISS denotes a relation, i.e., a set of ordered pairs, corresponding to those objects in the world that are related by kissing, where the first member of the pair kissed the second member of the pair. An example is provided in (13). (13) I(KISS) = { 〈 , 〉, 〈 , 〉, 〈 , 〉} This example corresponds to a state of affairs in the world in which Aristotle kissed Rover, Bob kissed Nietzsche, and Rover kissed Bob. Furthermore, no one else kissed or was kissed. So this example does not correspond to Rover kissing Aristotle. Consider the proposition in (14). (14) KISS(a,r) It is now possible to give different truth-conditions for this proposition. If the predicate KISS denotes the relation I(KISS) and its arguments denote the ordered pair 〈I(a), I(r)〉, then the truth-conditions for (14) are given in (15). (15) KISS(a,r) is true if and only if 〈I(a), I(r)〉 ∈ I(KISS) The proposition KISS(a,r) is true if and only if the ordered pair of entities denoted by (a,r) is in the relation denoted by KISS. The formal definition of a relation follows. Given any two sets, A and B, an ordered pair 〈α,β〉 is formed by combining an element from each set, α ∈ A and β ∈ B. The set of all such ordered pairs is the Cartesian Product of A and B, written A × B. (16) Cartesian Product of A and B A × B = { 〈α,β〉 | α ∈ A and β ∈ B } Any set R ⊆ A × B is called a relation. A more restricted version of (16), one in which A = B, is given in (17). This is what we will use from now on. 6 (17) Cartesian Product of A with itself A × A = { 〈α,β〉 | α ∈ A and β ∈ A } The next example illustrates the Cartesian Product of the Domain of Discourse, i.e., D × D. Suppose D corresponds to a small world that contains four objects, Aristotle, Nietzsche, Bob Dylan, and Rover. The Cartesian Product D × D is the set of all ordered pairs made up of Aristotle, Nietzsche, Bob Dylan, and Rover. (18) Let D = { D×D={ , , }. Then, , 〈 , 〉, 〈 , 〉, 〈 , 〉, 〈 , 〉, 〈 , 〉, 〈 , 〉, 〈 , 〉, 〈 , 〉, 〈 〉, , 〈 〈 〉, , 〉, , 〈 〈 〉, , 〉, , 〈 〈 〉, , 〉, , 〈 〉 } , The interpretation of a 2-place predicate is carved out of D × D. I.e., it is a subset of D × D. (This is sometimes written D2.) (19) D×D={ 〈 , 〉, 〈 , 〉, 〈 , 〉, 〈 , 〉, 〈 , 〉, 〈 , 〉, 〈 , 〉, 〈 , 〉, 〈 〈 〉, , , 〈 〉, 〈 〉, , , 〈 〉, 〈 〉, , , 〈 〉, 〈 〉, , , 〉 } Everything said so far can be generalized from a sequence of two elements (an ordered pair) to a sequence of n elements (an ordered n-tuple). For instance, an ordered triplet is a sequence of three elements, written 〈α, β, γ〉; while an ordered quadruple is a sequence of four elements, written 〈α, β, γ, δ〉. And so forth. We can extend this to n sets, illustrated in (20). (20) Dn = { 〈α1, α2, …, αn〉 | α1 ∈ D, α2 ∈ D, …., and αn ∈ D } 7 A subset of (20) is called an n-ary relation on D. We won’t need this amount of abstraction but it helps to know how general this operation is. The predicates that we use to represent English will never be more than 4-place predicates so at the very worst we will look at ordered sequences of four elements. Whenever you represent a relation, keep in mind that it is a set of objects. The objects contained in a relation are ordered pairs (or sometimes ordered triples, quadruples, etc). If an ordered pair 〈x,y〉 is an element of the relation R, I write 〈x,y〉 ∈ R. This clearly shows that we are dealing with a set. Some textbooks use the predicate notation and write R(x,y). I find this sloppy. A relation is a set and part of the semantics, not a predicate, which is part of the syntax. Some math textbooks use another way of representing 〈x,y〉 ∈ R. They write x R y to mean x stands in the relation R with y. Relations can be studied in terms of their formal properties. As noted above, Aristotle kissed Rover is not equivalent to Rover kissed Aristotle. This turns out to be a semantic property of the word kiss. If we look at the expression is married to, we find that Aristotle is married to Sue is indeed equivalent to Sue is married to Aristotle. We need to capture this difference in our semantics. The formal properties of relations are listed in (21). (21) For a relation R ⊆ D × D i. R is reflexive if and only if for all x ∈ D, 〈x,x〉 ∈ R ii. R is symmetric if and only if for every x, y ∈ D, if 〈x,y〉 ∈ R then 〈y,x〉 ∈ R iii. R is transitive if and only if for every x, y, z ∈ D, if 〈x,y〉 ∈ R and 〈y,z〉 ∈ R then 〈x,z〉 ∈ R iv. R' is the converse of R if and only if for every x, y ∈ D, if 〈x,y〉 ∈ R then 〈y,x〉 ∈ R' and vice versa To simplify the discussion below, I am going to directly refer to natural language expressions as if they were relations. For example, I am going to talk about the relation as big as. This is just a shorthand. By now I expect you all to know that a natural language expression is part of the object language, is translated into the metalanguage, and denotes a relation in the semantics. So there should be no confusion. You can do this too, as long as you are clear about the difference. Examples of reflexive relations include as big as, identical to, the same age as. It necessarily follows for every entity that it is as big as itself, that it is identical to itself, and that it is the same age as itself. In 8 contrast, the relation smarter than is not reflexive. Sue is smarter than herself is clearly never true. In fact, no entity is smarter than itself. The relation satisfied with is not reflexive either. It may or may not be true of an entity, depending on the outside world. In other words, John is satisfied with himself may or may not be true of the outside world. Reflexivity can be a bit tricky: keep in mind that for a relation to be reflexive, it must be true for every x (not just in one model but any conceivable model). (22) a. John is as big as himself reflexive b. # Sue is smarter than herself not reflexive c. # John is satisfied with himself not reflexive Examples of symmetric relations include be as tall as, be in the same room as. For any two entities, x and y, if x is as tall as y, then it follows that y is as tall as x. So if John is as tall as Sue then it follows that Sue is as tall as John. In contrast, the relation be taller than is not symmetric. It is never the case that if John is taller than Sue, then Sue is taller than John. The relation be the brother of is also not symmetric. For instance, if John is the brother of Sue, it does not follow that Sue is the brother of John. (23) a. John is married to Sue. So Sue is married to John. symmetric b. # John is taller than Sue. So Sue is taller than John. not symmetric c. # John is the brother of Sue. So Sue is the brother of John. not symmetric Examples of transitive relations include older than, in the same room as. For any three entities, x, y, and z, that if x is older than y and y is older than z, it follows that x is older than z. In other words, if John is older than Sue and Sue is older than Bill, it follows that John is older than Bill. In contrast, the relation father of is not transitive. It is never the case that if John is the father of Bill and Bill is the father of Sue, then John is the father of Sue. (24) a. John is older than Sue. Sue is older than Bill. So John is older than Bill. transitive b. # John is the father of Bill. Bill is the father of Sue. So John is the father of Sue not transitive You might wonder why these properties are useful. They encode a series of entailments arising from the lexical meaning of these relations. The lexical meaning of as big as, which is reflexive, symmetric, and transitive, carries the properties in (21). These properties determine entailments. I don’t have to tell you that John is as big as himself because it logically follows from the meaning of the relation as big as. You infer it. 9 Also, if you know John is as big as Sue, then I don’t have to tell you that Sue is as big as John. Again, you can infer this. Finally, if I tell you that John is as big as Sue and Sue is as big as Bill, I don’t have to tell you that John is as big as Bill. This too can be inferred from the semantic properties of the relation as big as. 3. Variables and Quantifiers In sum, we have a way of expressing the truth-conditions for any n-place predicate, as long as its arguments are all there and as long as its arguments are all individual constants. (25) Aristotle punched Nietzsche Let Aristotle = a, Nietzsche = n, punch = PUNCH PUNCH(a, n) is true in a model M if and only if 〈I(a), I(n)〉 ∈ I(PUNCH) in M If we have a particular model M, it is straightforward to compute the values for I(a), for I(n), and for I(PUNCH), and then verify whether or not the sentence is true in M. For example, in the model M2 in (26), the sentence Aristotle punched Nietzsche is false. (26) Model M2 D2 = { , , } , I2(a) = Aristotle I2(n) = Nietzsche I2(b) = Bob Dylan I2(r) = Rover I2(PERSON) = { , } , I2(SLEEP) = { , , I2(SINGER) = { , } } , is sleeping is a singer I2(PHILOSOPER) = { , , I2(PUNCH) = { 〈 〉, 〈 , , is a person } 〉} is a philosopher punched 10 So far so good. But at this point, there’s no procedure to interpret variables and quantification (and also free pronouns). Consider the sentences in (27). (27) a. He is a philosopher b. Everyone is sleeping c. Nietzsche punched someone What are the truth-conditions for these sentences? The sentence in (27a) is missing a crucial piece of information, namely, who the pronoun he refers to. Without knowing who he is, it is impossible to tell if this sentence is true. In other words, (27a) does not express a proposition. However, if the context were to furnish this information, then it would express a proposition. For example, suppose you’re talking to a friend about Bob Dylan. Your friend utters: he is a philosopher. In this context, the pronoun he refers to the same person in the world that the proper name Bob Dylan refers to. Suppose the next day, you watch a documentary about Aristotle and the announcer says: he is a philosopher. In this context, the pronoun he refers to the same person in the world that the proper name Aristotle refers to. The context determines the meaning of the pronoun he. Out of blue, the sentence in (27a) is meaningless precisely because there is no context to provide the pronoun he with a meaning. In Predicate Logic, we express the pronoun he as a variable. Like a variable, the pronoun he has no meaning of its own. It only stands in for something else. To represent this, the sentence in (27a) is expressed as the well-formed formula in (28). Note that the wff in (28) is not a proposition because it has a free variable in it. (28) PHILOSOPHER(x) What comes next is the tricky bit, so please read it over carefully. In order to express the meaning of an individual constant and a predicate constant, I defined the interpretation function I in the last section. The function I associates each individual to an entity and each nplace predicate to a relation. Now in order to express the meaning of a variable, I need to define another function, called the variable assignment function g. This new function g associates each variable x, y, z, …with an entity in U. This is illustrated in (29). 11 (29) The variable assignment function g U x y z …  g(x) =   g(y) =  g(z) = … The variable assignment function g is different from I in three ways. First, it operates on variables (not individuals). Second, it can associate more than one variable to the same entity. Third, it is not part of the model so it is not uniquely specified by the model. There are many g functions, a whole family of them, one for every imaginable association. Here’s another example. (30) The variable assignment function g' D x y z …  g(x) =   g(y) =  g(z) = … 12 Using the assignment function g, we can express the truth-conditions for the formula in (31). The truth-conditions look exactly like the ones with the interpretation function in the last section. (31) PHILOSOPHER(x) is true if and only if g(x) ∈ I(PHILOSOPHER) This is not as straightforward as it looks. The truth-conditions in (31) depend on the value of g(x). But what is the value of g(x)? I just finished saying there is a family of assignment functions g, one for every possible association. So without knowing the particular function g, the value could be anything. That’s where the context comes in. The context can specify g. For example, suppose you’re talking to a friend about Bob Dylan. Your friend utters: he is a philosopher. The context provides the function g such that g(x) = and the truth-conditions in (31) become: ∈ I(PHILOSOPHER). Suppose the next day, you watch a documentary about Aristotle and the announcer says: he is a philosopher. The new context provides the assignment function g such that g(x) = truth-conditions in (31) become: and the ∈ I(PHILOSOPHER). This entire discussion buys us the rule in (32). It states the truth-conditions for an open formula with respect to the variable assignment function g. (32) For any predicate P and variable x, P(x) is true if and only if g(x) ∈ I(P) This rule will help us to figure out the truth-conditions for the sentence in (33), which expresses a proposition made up of a quantifier ∀x and its scope (PERSON(x) → SLEEP(x)). (33) Everyone is sleeping ∀x (PERSON(x) → SLEEP(x)) The truth-conditions for (33) are intuitively clear. It is true if and only if every person in the world is sleeping. This statement can be verified by examining every entity in the world and making sure that if it is person then it is sleeping. Suppose the world has four entities: Aristotle, Nietzsche, Bob Dylan, and Rover. The sentence everyone is sleeping is true on the condition that if Aristotle is a person then, Aristotle is sleeping and if Nietzsche is a person, then Nietzsche is sleeping and if Bob Dylan is a person, then Bob Dylan is sleeping, and if Rover is a person, then Rover is sleeping. The open formula (PERSON(x) → SLEEP(x)) expresses the meaning if it is a person, then it is sleeping. The truth-conditions for this are obtained using the rule in (32) and are illustrated in (34). 13 (34) (PERSON(x) → SLEEP(x)) is true iff g(x) ∉ I(PERSON) or g(x) ∈ I(SLEEP) The variable x is not assigned an entity e that is a person or the variable x is assigned an entity e that is sleeping. These truth-conditions are expressed in terms of the assignment function g, which assigns an element in D to the variable x. In other words, g(x) ∈ D. When we combine the truth-conditions in (34) with the universal quantifier ∀x, their meaning is (35). (35) ∀x (PERSON(x) → SLEEP(x)) is true iff for every entity e in D: the variable x is assigned the value e and (PERSON(x) → SLEEP(x)) is true. iff for every entity e in D: g(x) = e, and g(x) ∉ I(PERSON) or g(x) ∈ I(SLEEP) iff for every e ∈ D: e ∉ I(PERSON) or e ∈ I(SLEEP) ASIDE: The truth-conditions in (35) are simplified. The full story goes something like this. The context provides an assignment function g. For every entity e in D, there is an assignment function g' that is identical to g except that g' assigns e to the variable x, i.e., g'(x) = e. While it is easier to see what this assignment function is by writing it out as g'(x) = e, it is also misleading. For every entity e in D, there will be a different function. So rather than write them g', g'', g''', etc., we usually write g[x/e]. This notation represents a family of functions, one for every entity e. This is a subtle point and might take a while to absorb. Look at a concrete example. Suppose the domain D = { (36) , , , }. ∀x (PERSON(x) → SLEEP(x)) is true iff for every e ∈ U: e ∉ I(PERSON) or e ∈ I(SLEEP) iff ( and ( and ( and ( ∉ I(PERSON) or ∈ I(SLEEP) ) ∉ I(PERSON) or ∉ I(PERSON) or ∉ I(PERSON) or ∈ I(SLEEP) ) ∈ I(SLEEP) ) ∈ I(SLEEP) ) 14 In (36), the formula is repeated for every entity in D and since there is a conjunction between each term, they all have to be true. That’s exactly what the quantifier ∀x means. It means for every possible value of x, its scope (ϕ) is true. The generalization is given in (37). (37) For a wff ϕ, ∀x ϕ is true if and only if for every entity e in D: the function g[x/e] assigns e to x and ϕ is true under this assignment. Finally, the sentence in (38) expresses a proposition made up of a quantifier ∃x and its scope (PERSON(x) ∧ PUNCH(n,x)). (38) Nietzsche punched someone ∃x (PERSON(x) ∧ PUNCH(n,x)) The truth-conditions for (38) are intuitively clear. It is true if and only if there is one person such that Nietzsche punched him or her. This can be verified by examining every object in the world and checking to see that it is a person and it was punched by Nietzsche. Suppose we are considering the entities: Aristotle, Nietzsche, Bob Dylan, and Rover. The sentence Nietzsche punched someone is true if and only if either Aristotle is a person and Nietzsche punched him or Bob Dylan is a person and Nietzsche punched him or Nietzsche is a person and Nietzsche punched himself or Rover is a person and Nietzsche punched him. The open formula (PERSON(x) ∧ PUNCH(n,x)) expresses the meaning it is a person and Nietzsche punched it. The truth-conditions for this are illustrated in (39). (39) (PERSON(x) ∧ PUNCH(n,x)) is true iff g(x) ∈ I(PERSON) and 〈I(n),g(x)〉 ∈ I(PUNCH) The variable x is assigned an entity e that is a person and the variable x is assigned an entity e in the punch relation with Nietzsche (as the punchee) These truth-conditions are expressed in terms of the assignment function g, which assigns an element in U to the variable x. When we combine the truth-conditions in (39) with the existential quantifier ∃x, their meaning is (40). 15 (40) ∃x (PERSON(x) ∧ PUNCH(n,x)) is true iff for some entity e in D: the variable x is assigned the value e and (PERSON(x) ∧ PUNCH(n,x)) is true. iff for some entity e in D: g(x) = e, and g(x) ∈ I(PERSON) and 〈I(n),g(x)〉 ∈ I(PUNCH) iff for some e ∈ D: e ∈ I(PERSON) and 〈I(n), e〉 ∈ I(PUNCH) Look at a concrete example. Suppose the domain D = { (41) , , , }. ∃x (PERSON(x) ∧ PUNCH(n,x)) is true iff for some e ∈ D: e ∈ I(PERSON) or 〈n, e〉 ∈ I(PUNCH) iff ( or ( or ( or ( ∈ I(PERSON) and 〈 〉 ∈ I(PUNCH) ) , ∈ I(PERSON) and 〈 ∈ I(PERSON) and 〈 ∈ I(PERSON) and 〈 〉 ∈ I(PUNCH) ) , , 〉 ∈ I(PUNCH) ) , 〉 ∈ I(PUNCH) ) In (41), the formula is repeated for every entity in U and since there is a disjunction between each term, only one needs to be true. That’s exactly what the quantifier ∃x means. It means for at least one value of x, its scope (ϕ) is true. The generalization is given in (42). (42) For a wff ϕ, ∃x ϕ is true if and only if for some entity e in D: the function g[x/e] assigns e to x and ϕ is true under this assignment. 4. Valuation and Denotation In Propositional Logic, the valuation function V assigns a truth-value to every wff. In addition, the valuation function obeys semantic rules that allow us to systematically compute the meaning of a compound proposition from the meaning of its constituent atomic propositions. In Predicate Logic, there are no atomic propositions but we still want the same mechanism to compute the truth-value of a compound wff from its constituents. I’ve been doing this intuitively throughout these notes but at this point we need to settle on a formal system of rules. This just means borrowing the valuation function V into Predicate Logic along with the rules in (43). 16 (43) Semantic Rules1 i. VM,g(¬ϕ) = 1 iff VM,g(ϕ) = 0 ii. VM,g(ϕ ∧ ψ) = 1 iff VM,g(ϕ) = 1 and VM,g(ψ) = 1 iii. VM,g(ϕ ∨ ψ) = 1 iff VM,g(ϕ) = 1 or VM,g(ψ) = 1 iv. VM,g(ϕ → ψ) = 1 iff VM,g(ϕ) = 0 or VM,g(ψ) = 1 v. VM,g(ϕ ↔ ψ) = 1 iff VM,g(ϕ) = VM,g(ψ) In Predicate Logic, we are no longer dealing with atomic propositions but the valuation function is still useful because it allows us to reduce a compound wff into more basic wffs. An example is given in (44). (44) a. John likes Sue and Sue likes Bill (LIKE(j,s) ∧ LIKE(s,b)) b. VM,g(LIKE(j,s) ∧ LIKE(s,b)) =1 iff VM,g(LIKE(j,s)) = 1 and VM,g(LIKE(s,b)) =1 The valuation function determines the truth-value of the compound wff (LIKE(j,s) ∧ LIKE(s,b)) from the values of its constituent wffs, LIKE(j,s) and LIKE(s,b). At the moment, we have no rule that determines VM,g(LIKE(j,s)) = 1 or VM,g(LIKE(s,b)) = 1. But we already know what this signifies. The valuation function V assigns a value of 1 to an expression α if and only if it corresponds to the outside world. We already know that LIKE(j,s) is true of the outside world if and only if 〈I(j), I(s)〉 ∈ I(LIKE). In a similar fashion, the truth-conditions for the sentence in (46) can be computed by recalling that LIKE(x,s) is true of the outside world if and only if given an assignment function g, 〈g(x), I(s)〉 ∈ I(LIKE). (46) a. He likes Sue and Sue likes Bill (LIKE(x,s) ∧ LIKE(s,b)) b. VM,g(LIKE(x,s) ∧ LIKE(s,b)) =1 iff VM,g(LIKE(x,s)) = 1 and VM,g(LIKE(s,b)) =1 I will write a general rule capturing these steps shortly but to make it easier to write such a rule, I need to tidy things up. The interpretation function I associates individuals and predicates to D. The variable assignment function g associates variables to D. Life would be simpler if there were one function to handle 1 You’ll notice that the valuation function is relative to both a model M and an variable assignment function g. This is not a minor point. The reasons for this will become evident later. 17 everything, but because individuals and predicates are so different from variables, this is not an option. Both functions are necessary. Nevertheless, it will prove useful to define a general meaning function that represents the meaning of an expression α with respect to a model M and an assignment function g. This function is written αM,g and is called the denotation function. It is defined in (47). (47) The Denotation Function For some expression α, i. If α is an individual constant or a predicate constant, then αM,g = I(α) ii. If α is an individual variable, then αM,g = g(α) You can think of the denotation function as a comprehensive function. It is equal to the function I(α) whenever the expression α is an individual or a predicate; and it is equal to the function g(α) whenever α is a variable. Instead of writing I(α) or g(α), we simply write αM,g to represent the denotation of α with respect to a model M and assignment function g. Now we can formulate a general rule for the valuation function V in terms of the function I and g. (48) Additional Semantic Rules for the Valuation Function If X is an n-place predicate and t1,…,tn are terms, such that X(t1,…,tn) is a wff, then i. VM,g(X(t1,…,tn)) = 1 iff 〈t1M,g,…, tnM,g〉 ∈ XM,g ii. VM,g(t1 = t2) = 1 iff t1M,g = t2M,g What does this mean? The two rules in (48) allow us to express the truth-conditions of a wff in terms of its individuals, predicates, and variables. This is illustrated in (49). (49) a. John likes Sue and Sue likes Bill VM,g(LIKE(j,s) ∧ LIKE(s,b)) =1 iff VM,g(LIKE(j,s)) = 1 and VM,g(LIKE(s,b)) =1 iff 〈jM,g, sM,g 〉 ∈ LIKEM,g and 〈sM,g, bM,g 〉 ∈ LIKEM,g b. He likes Sue and Sue likes Bill VM,g(LIKE(x,s) ∧ LIKE(s,b)) =1 iff VM,g(LIKE(x,s)) = 1 and VM,g(LIKE(s,b)) =1 iff 〈xM,g, sM,g 〉 ∈ LIKEM,g and 〈sM,g, bM,g 〉 ∈ LIKEM,g 18 If you look at the bottom line of each derivation in (49), you’ll notice that they look the same. Don’t be fooled. Remember that jM,g = I(j)—the interpretation of the individual constant j. And xM,g = g(x)—the assignment of the variable x to an entity in D. These are applications of different functions. We’re not done yet. We also need to add the quantifier rules from the discussion in section 3, which I have appended to the bottom of (50). These rules now form a complete system. (50) Semantic Rules If X is an n-place predicate and t1,…,tn are individuals or variables, such that X(t1,…,tn) is a wff, then i. VM,g(X(t1,…,tn)) = 1 iff 〈t1M,g,…, tnM,g〉 ∈ XM,g ii. VM,g(t1 = t2) = 1 iff t1M,g = t2M,g iii. VM,g(¬ϕ) = 1 iff VM,g(ϕ) = 0 iv. VM,g(ϕ ∧ ψ) = 1 iff VM,g(ϕ) = 1 and VM,g(ψ) = 1 v. VM,g(ϕ ∨ ψ) = 1 iff VM,g(ϕ) = 1 or VM,g(ψ) = 1 vi. VM,g(ϕ → ψ) = 1 iff VM,g(ϕ) = 0 or VM,g(ψ) = 1 vii. VM,g(ϕ ↔ ψ) = 1 iff VM,g(ϕ) = VM,g(ψ) viii. VM,g(∀xϕ) = 1 iff for every entity e ∈ D, VM,g[x/e](ϕ) = 1 ix. iff for some entity e ∈ D, VM,g[x/e](ϕ) = 1 VM,g(∃xϕ) = 1 At this point, the semantics of Predicate Logic is a lot messier than the semantics of Propositional Logic, but that was to be expected. Predicate Logic includes three basic elements and quantifiers. To interpret these elements and assign truth-values, three functions are needed: the interpretation function (I), the variable assignment function (g), and the valuation function (V). (51) Semantic Functions i. Interpretation Function I Associates each individual to an element of D Associates each predicate to a relation on D ii. Assignment Function g Assigns an element of D to each variable iii. Valuation Function V Assigns a truth-value to each wff To simplify things earlier, I introduced the denotation function ⟦α⟧M,g, which merged I and g into one comprehensive function. Now that we have three functions, we can do exactly the same thing by extending the definition of αM,g. This is done in (52). 19 (52) The Denotation Function For some expression α, i. If α is an individual constant or a predicate constant, then αM,g = I(α) ii. If α is an individual variable, then αM,g = g(α) iii. If α is a wff, then αM,g = VM,g(α) Once we adopt this definition, there is no longer any need to write the semantic rules using I, g, or V. These functions are still part of our semantics. They are simply hidden in the background as part of the value of the denotation function αM,g. Our rules now looked more streamlined. (53) Semantic Rules Let ϕ and ψ be wffs, let X be an n-place predicate, and let t1,…,tn be terms i. X(t1,…,tn)M,g = 1 iff 〈t1M,g,…, tnM,g〉 ∈ XM,g ii. t1 = t2M,g = 1 iff t1M,g = t2M,g iii. ¬ϕM,g = 1 iff ϕM,g = 0 iv. ϕ ∧ ψM,g = 1 iff ϕM,g = 1 and ψM,g = 1 v. ϕ ∨ ψM,g = 1 iff ϕM,g = 1 or ψM,g = 1 vi. ϕ → ψM,g = 1 iff ϕM,g = 0 or ψM,g = 1 vii. ϕ ↔ ψM,g = 1 iff ϕM,g = ψM,g viii. ∀x ϕM,g = 1 iff for every entity e ∈ D, ϕM,g[x/e] = 1 ∃x ϕM,g = 1 iff for some entity e ∈ D, ϕM,g[x/e] = 1 ix. The following example illustrates a step-by-step derivation of the truth-conditions of a sentence. (54) Everyone is sleeping ∀x (PERSON(x) → SLEEP(x)) ∀x (PERSON(x) → SLEEP(x)) qp ∀x (PERSON(x) → SLEEP(x)) qgp PERSON(x) → SLEEP(x) ty ty PERSON x SLEEP x 20 (55) ∀x (PERSON(x) → SLEEP(x))M,g = 1 iff for every e ∈ D: [1] (PERSON(x) → SLEEP(x))M,g[x/e] = 1 iff for every e ∈ D: PERSON(x) iff M,g[x/e] [2] = 0 or SLEEP(x)) M,g[x/e] =1 for every e ∈ D: [3] xM,g[x/e] ∉ PERSONM,g[x/e] or xM,g[x/e] ∈ SLEEPM,g[x/e] iff for every e ∈ D: [4] e ∉ PERSONM,g[x/e] or e ∈ SLEEPM,g[x/e] Steps [1] is obtained by applying rule (viii), which interprets the quantifier. [2] is obtained from [1] by applying rule (vi), which interprets the logical connective →. [3] is obtained from [2] by applying rule (i) to PERSON(x)M,g[x/e] = 0 and SLEEP(x))M,g[x/e] = 1 [4] is obtained from [3] by evaluating xM,g[x/e] = g[x/e](x). g[x/e] is the variable assignment function that associates the variable x to the entity e; in other words, g[x/e](x) = e. So xM,g[x/e] = g[x/e](x) = e. The sentence everyone is sleeping is true if and only if for every entity e in D, e is not a person or e is sleeping. Put another way, every entity e in D that is a person is sleeping. The derivation below is identical to the one above, except it explicitly uses the functions V, I, and g. (56) VM,g(∀x (PERSON(x) → SLEEP(x))) = 1 iff for every e ∈ D: VM,g[x/e]((PERSON(x) → SLEEP(x))) = 1 iff for every e ∈ D: VM,g[x/e](PERSON(x)) = 0 or VM,g[x/e](SLEEP(x))) = 1 iff for every e ∈ D: g[x/e](x) ∉ VM,g[x/e](PERSON) or g[x/e](x) ∈ VM,g[x/e](SLEEP) iff for every e ∈ D: e ∉ I(PERSON) or e ∈ I(SLEEP) 21 I suggest you stick with the denotation function αM,g, unless you really feel that (56) is clearer to you than (55). At all times, keep in mind that the denotation function is just a short-hand for (57). (57) The Denotation Function For some expression α, i. If α is an individual constant or a predicate constant, then αM,g = I(α) ii. If α is an individual variable, then αM,g = g(α) iii. If α is a wff, then αM,g = VM,g(α) 22 5. Summary (58) THE SEMANTICS OF PREDICATE LOGIC I. Model A model M consists of a Domain of Discourse D and an interpretation function I II. Interpretation, Assignment, Valuation - The interpretation function I associates to each individual constant an entity in D and to each n-place predicate constant a subset of Dn, i.e., its reference in the outside world. - A variable assignment function g associates variables to entities in D. When it is written g[x/e], it represents a function that assigns the value e to x so that g[x/e](x) = e. - III. The valuation function VM,g assigns a truth value of 1 or 0 to every wff α. Denotation The denotation function αM,g is defined in (i)-(iii) and obeys the semantic rules in IV. i. if α is an individual constant or a predicate constant, αM,g = I(α) ii. if α is an individual variable, αM,g = g(α) iii. if α is a wff, αM,g = VM,g(α) IV. Semantic Rules Let ϕ and ψ be wffs, let X be an n-place predicate, and let t1,…,tn be terms i. X(t1,…,tn)M,g = 1 iff 〈t1M,g,…, tnM,g〉 ∈ XM,g ii. t1 = t2M,g = 1 iff t1M,g = t2M,g iii. ¬ϕM,g = 1 iff ϕM,g = 0 iv. ϕ ∧ ψM,g = 1 iff ϕM,g = 1 and ψM,g = 1 v. ϕ ∨ ψM,g = 1 iff ϕM,g = 1 or ψM,g = 1 vi. ϕ → ψM,g = 1 iff ϕM,g = 0 or ψM,g = 1 vii. ϕ ↔ ψM,g = 1 iff ϕM,g = ψM,g viii. ∀x ϕM,g = 1 iff for every entity e ∈ D, ϕM,g[x/e] = 1 ∃x ϕM,g = 1 iff for some entity e ∈ D, ϕM,g[x/e] = 1 ix. 23