Discrete Mathematics(II) Spring 2012 Lecture 12: Semantics of Predicated language Lecturer. yil 1 Overview n this lecture, we try to interpret the symbols of predicate language. In other words, we will assign the meaning or semantics to symbols which consist of predicate language It is the foundation of predicate language. Especially, we should handle sentence and formula lly Example 1. Consider a =r+ l in programming language. It is obvious that on different side does have different semantics Example 2. We first review some feature ofjava, a type of objected oriented programming language A string a+b is given, what's its meaning We may have many interpretations 2 Structure In general, a symbol may represent anything possible. However, structure just specifies them and make them fixed. In order to discuss truth of some sentences we first define a structure as following Definition 1. A structure A for a language L consists of a nonempty domain A, an assignment to each n-ary predicate symbol R of C, of an actual predicate RA on the n-tuples(n1, 72,. an from A, an assignment, to each constant symbol c of C, of an element ca of a and, to each n-ary function symbol f of f, an n-ary function f from A" to A Structure is composed of predicate language, domain and assignment to symbols in language Example 3. Now we have three structures of language P(a, y), f(a, y) 2.g,,f4(x,y)=x-y. For these simple symbols, we wan assign them many interpretations as possible as you can, which depends only on what you know. Term plays a very important role to discuss the truth of a sentence when quantifies are involved Definition 2(The interpretation of ground terms). Term is a recursively defined concept. It can be interpreted also recursively
Discrete Mathematics (II) Spring 2012 Lecture 12: Semantics of Predicated Language Lecturer: Yi Li 1 Overview In this lecture, we try to interpret the symbols of predicate language. In other words, we will assign the meaning or semantics to symbols which consist of predicate language. It is the foundation of predicate language. Especially, we should handle sentence and formula carefully. Example 1. Consider x = x + 1 in programming language. It is obvious that x on different side does have different semantics. Example 2. We first review some feature of java, a type of objected oriented programming language. A string a + b is given, what’s its meaning? We may have many interpretations. 2 Structure In general, a symbol may represent anything possible. However, structure just specifies them and make them fixed. In order to discuss truth of some sentences, we first define a structure as following. Definition 1. A structure A for a language L consists of a nonempty domain A, an assignment, to each n-ary predicate symbol R of L, of an actual predicate RA on the n-tuples (n1, n2, . . . , an) from A, an assignment, to each constant symbol c of L, of an element c A of A and, to each n-ary function symbol f of L, an n-ary function f A from An to A. Structure is composed of predicate language, domain and assignment to symbols in language. Example 3. Now we have three structures of language P(x, y), f(x, y): 1. N , ≤, f A(x, y) = x · y. 2. Q, , f A(x, y) = x − y. For these simple symbols, we wan assign them many interpretations as possible as you can, which depends only on what you know. Term plays a very important role to discuss the truth of a sentence when quantifies are involved. Definition 2 (The interpretation of ground terms). Term is a recursively defined concept. It can be interpreted also recursively. 1
1. each constant term c names the element ca 2. if the terms ti, . tn of f name the elements t1, .. t2 of A and f is an n-ary function symbol of C, then the term f(t1, .. t2)names the element f(t1, . . tn)=fA(t1, .. ta) of A xample 4. If we add the instance c, d into the language of last example, we can assign to element 9.c4=0:d4=-2. Example 5. Give ground terms f(a, d), f(d, f(d, d)). They name elements of the A as follows 1.f(c,d)4=0;f(d,f(d,d)4=1 2.f(c,d)4=3/2;f(d,f(d,d)4=2/3. 9.f(c,d)4=2;f(d,f(d,d)=-2 3 Semantics Given a sentence, its semantics depends on the structure. Here, we should pay attention. For convenience, we expand our language by adding enough constant symbols. After interpretatio every element in domain is named by a constant. With the help of these constants, we can"use every element in domain. Specially, when we add a"new"constant into language, before we fix its interpretation or meaning, it can be any element in domain as your wish. However, if you fix its interpretation, you can never change it Definition 3(Truth). The truth of a sentence op of l in a structure A in which every a E A is named by a ground term of l is defined by induction. 1. For an atomic sentence R(t1,., tn), AFR(t1,., tn)if and only if R A(t1, ...,tA AF-op+ it is not the case that Ahp( We also write as Akp. 3.4=(yVv)分A= p or AFy 4.AF(^v)分A= p and Aw 5.4=(→v)分 A p orA=v 6. AF(+0+(AFY and A Fa) or(ak o and Ak 7.AF Eop(u)+ for some ground term t, AFp(t) 8.A Vop(u)+ for all ground term t, AF p(t)
1. Each constant term c names the element c A. 2. if the terms t1, . . . , tn of L name the elements t A 1 , . . . , tA 2 of A and f is an n-ary function symbol of L, then the term f(t1, . . . , t2) names the element f(t1, . . . , tn) A = f A(t A 1 , . . . , tA n ) of A. Example 4. If we add the instance c, d into the language of last example, we can assign to element c A, dA as: 1. c A = 0; d A = 1. 2. c A = 1/2; d A = 2/3. 3. c A = 0; d A = −2. Example 5. Give ground terms f(x, d), f(d, f(d, d)). They name elements of the A as follows: 1. f(c, d) A = 0; f(d, f(d, d))A = 1. 2. f(c, d) A = 3/2; f(d, f(d, d))A = 2/3. 3. f(c, d) A = 2; f(d, f(d, d))A = −2. 3 Semantics Given a sentence, its semantics depends on the structure. Here, we should pay attention. For convenience, we expand our language by adding enough constant symbols. After interpretation, every element in domain is named by a constant. With the help of these constants, we can “use” every element in domain. Specially, when we add a “new” constant into language, before we fix its interpretation or meaning, it can be any element in domain as your wish. However, if you fix its interpretation, you can never change it. Definition 3 (Truth). The truth of a sentence ϕ of L in a structure A in which every a ∈ A is named by a ground term of L is defined by induction. 1. For an atomic sentence R(t1, . . . , tn), A R(t1, . . . , tn) if and only if RA(t A 1 , . . . , tA n ). 2. A |= ¬ϕ ⇔ it is not the case that A |= ϕ ( We also write as A 6|= ϕ.) 3. A |= (ϕ ∨ ψ) ⇔ A |= ϕ or A |= ψ. 4. A |= (ϕ ∧ ψ) ⇔ A |= ϕ and A |= ψ. 5. A |= (ϕ → ψ) ⇔ A 6|= ϕ or A |= ψ. 6. A |= (ϕ ↔ ψ) ⇔ (A |= ϕ and A |= ψ) or (A 6|= ϕ and A 6|= ψ). 7. A |= ∃vϕ(v) ⇔ for some ground term t, A |= ϕ(t). 8. A |= ∀vϕ(v) ⇔ for all ground term t, A |= ϕ(t). 2
An atomic sentence is a instance of a instantiated atomic formula. a atomic formula can taken as a relation. When you determine the truth of an atomic sentence you can ask whether (a1, a2,. an)E R if R is n-ary This definition just define how to determine the truth of a sentence other than any other else. A need get rid of them from outside to inside one by one as definition defined cur in a sentence, we sentence is a recursively constructed symbol sequence. When quantifiers o Example 6. Consider the structure A=.We have 2. . r)P(a, d)is true. 3.(Var)P(c, a )is true 4.(Vr)P(, d) is false 5.(Va)(P(, c), P(, d) is true 6. How about a)(Va)P(, y)? Determine its truth according to definition Once we can determine the truth of a sentence. We can extend the following concepts defined already in propositional logic Definition 4. Fir some language L 1. A sentence p of L is valid,F, if it is true in all structure for L 2. Given a set of sentences∑={a1,…), we say that a is a logic consequence of∑,∑Fa,i every structure in which all of the members of 2 8. A set of sentence 2=(a1,.. is satisfiable if there is a structure A in which all the members of 2 are true. Such a structure is called a model of 2. If t has no model. If o has no mode it s unsatisfiable Given a sentence. it could be true in a structure and be false in another structure. Consider the following example Example 7. Consider a language L specified by R(, y) and constants co, C1, C2, .. Here are two possible structures for L corresponding to two different interpretations of the language. 1.Let domain a consists of the natural numbers, let R a be usual relation < and co=0, c1 1,……(Vx)(彐y)fR(x,y) is true in this structure 2. Let domain A consists of the rational numbers @=[90, 91,., let RA again be <,and 0=90, CA=q1,..(V)(y)(R(, 3)+(3x)(R(, z)AR(2, m)))is true in this structure 3. The sentence in 2 is not true in 1. So it can not be valid At present, we only discussed how to determine the truth of a sentence. However, formula is more general than sentence according to lecture on syntax. Now, we define the truth of a general formula as follow
An atomic sentence is a instance of a instantiated atomic formula. A atomic formula can taken as a relation. When you determine the truth of an atomic sentence, you can ask whether (a1, a2, . . . , an) ∈ R if R is n-ary. This definition just define how to determine the truth of a sentence other than any other else. A sentence is a recursively constructed symbol sequence. When quantifiers occur in a sentence, we need get rid of them from outside to inside one by one as definition defined. Example 6. Consider the structure A =. We have 1. P(c, d) is true. 2. (∃x)P(x, d) is true. 3. (∀x)P(c, x) is true. 4. (∀x)P(x, d) is false. 5. (∀x)(P(x, c) → P(x, d)) is true. 6. How about (∃x)(∀x)P(x, y)? Determine its truth according to definition. Once we can determine the truth of a sentence. We can extend the following concepts defined already in propositional logic. Definition 4. Fix some language L. 1. A sentence ϕ of L is valid, |= ϕ, if it is true in all structure for L. 2. Given a set of sentences Σ = {α1, . . .), we say that α is a logic consequence of Σ, Σ |= α, if α is true in every structure in which all of the members of Σ are true. 3. A set of sentence Σ = {α1, . . .} is satisfiable if there is a structure A in which all the members of Σ are true. Such a structure is called a model of Σ. If Σ has no model. If σ has no model it s unsatisfiable. Given a sentence, it could be true in a structure and be false in another structure. Consider the following example. Example 7. Consider a language L specified by R(x, y) and constants c0, c1, c2, . . .. Here are two possible structures for L corresponding to two different interpretations of the language. 1. Let domain A consists of the natural numbers, let RA be usual relation <, and c A 0 = 0, cA 1 = 1, . . .. (∀x)(∃y)R(x, y) is true in this structure. 2. Let domain A consists of the rational numbers Q = {q0, q1, . . .}, let RA again be <, and c A 0 = q0, cA 1 = q1, . . .. (∀x)(∀y)(R(x, y) → (∃z)(R(x, z) ∧ R(z, y))) is true in this structure. 3. The sentence in 2 is not true in 1. So it can not be valid. At present, we only discussed how to determine the truth of a sentence. However, formula is more general than sentence according to lecture on syntax. Now, we define the truth of a general formula as follow: 3
Definition 5. A formula y of a language L with free variables v1,..., Un is valid in a structure A for l(also written Ahy if the universal closure of p, i. e, the sentence Vu u2, .. Vunp gotten by putting Vui in front of o for every free variable vi in p, is true in A The formula of language L is valid if it is valid in every structure of A Example 8. Consider the structure A=. Give these formula 1.P(c,x) 2.P(x,d) 3.P(d,x) It is obvious that the truth of a formula is determined by the value of a variable. In a structure, sometimes it is true, and sometimes it is false. Once we add universal closure of quantifier before it, its truth is determined. This definition is compatible with definition of truth of a sentence. Definition 6. A set 2 of formulas with free variables is satisfiable if there is a structure in which all of the formulas in 2 are valid Again such a structure is called a model of 2. If 2 has no models it is unsatisfiable Applications In this section, we will use two examples to show how to determine whether your translation from natural language to logic language is proper/right or not Example 9. All apples are bad Solution. The sentence is simple enough. We first give two possible candidates as following: 1.Vr(A(x)→B(x) 2.var(A(x)∧B(x) Here, we suppose the statement is true. However, not both two sentences are correct. You can tr to check the truth of them Remark 1. 1. Var(A() B()is correct 2. Var(A()A B(a) is wrong. Because it require everything is an apple Example 10. Some apples are bad Solution. Similarly, we also have two possible candidates
Definition 5. A formula ϕ of a language L with free variables v1, . . . , vn is valid in a structure A for L (also written A |= ϕ ) if the universal closure of ϕ, i.e., the sentence ∀v1∀v2, . . . , ∀vnϕ gotten by putting ∀vi in front of ϕ for every free variable vi in ϕ, is true in A. The formula of language L is valid if it is valid in every structure of A. Example 8. Consider the structure A =. Give these formula: 1. P(c, x). 2. P(x, d). 3. P(d, x). It is obvious that the truth of a formula is determined by the value of a variable. In a structure, sometimes it is true, and sometimes it is false. Once we add universal closure of quantifier before it, its truth is determined. This definition is compatible with definition of truth of a sentence. Definition 6. A set Σ of formulas with free variables is satisfiable if there is a structure in which all of the formulas in Σ are valid. Again such a structure is called a model of Σ. If Σ has no models it is unsatisfiable. 4 Applications In this section, we will use two examples to show how to determine whether your translation from natural language to logic language is proper/right or not. Example 9. All apples are bad. Solution. The sentence is simple enough. We first give two possible candidates as following: 1. ∀x(A(x) → B(x)). 2. ∀x(A(x) ∧ B(x)). Here, we suppose the statement is true. However, not both two sentences are correct. You can try to check the truth of them. Remark 1. 1. ∀x(A(x) → B(x) is correct. 2. ∀x(A(x) ∧ B(x) is wrong. Because it require everything is an apple. Example 10. Some apples are bad. Solution. Similarly, we also have two possible candidates: 4
1.彐x(A(x)∧B(x) 2.彐r(A(x)→B(x) In this case, the status exchanges Remark2.1.彐x(A(x)∧B(x) is correct 2. 3 c(A() B(a)) is improper. Because even every apple is good but the statement is still true if is something other than apple These two examples would be encountered many times. There are some patterns to express sen- 1. Va(*): Everything in a certain category has some property. 2. 3 x( A: There is some object/objects in the category and having the property 5 Connection between predicate and proposition logic of formula, open formula. All open atomic formula can be thought as a proposition letter ategory Proposition logic can be embedded into predicate language if we only consider very special ca Theorem 7. Let o be an open formula of predicate logic. We may view pp as formula pl of propositional logic by regarding every atomic subformula of yp as a propositional letter With this correspondence, p is a valid formula of predicate logic if and only if pl is valid in propositional Before proof, consider the following example regarding every atomic subformula of p as a propositional letter. For erampe ding proposition by Example 11. Consider an open formula p of predicate logic and a correspo 1.A(x)V=A(x), 2. AVA Here, you can establish a connection between the truth of an atomic formula and a proposition letter. Then you can compare them with their formation tree in further Exercises 1. Let L contain a constant c, a binary function f and a unary predicate P. Give two structures for C: one in which VrP(f(a, c)is true and one in which it is false
1. ∃x(A(x) ∧ B(x)). 2. ∃x(A(x) → B(x)). In this case, the status exchanges. Remark 2. 1. ∃x(A(x) ∧ B(x)) is correct. 2. ∃x(A(x) → B(x)) is improper. Because even every apple is good but the statement is still true if x is something other than apple. These two examples would be encountered many times. There are some patterns to express sentences. 1. ∀x( → ): Everything in a certain category has some property. 2. ∃x( ∧ ): There is some object/objects in the category and having the property. 5 Connection between predicate and proposition logic Proposition logic can be embedded into predicate language if we only consider very special category of formula, open formula. All open atomic formula can be thought as a proposition letter. Theorem 7. Let ϕ be an open formula of predicate logic. We may view ϕ as formula ϕ0 of propositional logic by regarding every atomic subformula of ϕ as a propositional letter. With this correspondence, ϕ is a valid formula of predicate logic if and only if ϕ0 is valid in propositional logic. Before proof, consider the following example. Example 11. Consider an open formula ϕ of predicate logic and a corresponding proposition by regarding every atomic subformula of ϕ as a propositional letter. For example 1. A(x) ∨ ¬A(x), 2. A ∨ ¬A. Here, you can establish a connection between the truth of an atomic formula and a proposition letter. Then you can compare them with their formation tree in further. Exercises 1. Let L contain a constant c, a binary function f and a unary predicate P. Give two structures for L: one in which ∀xP(f(x, c)) is true and one in which it is false. 5
2. Given an example of an unsatisfiable sentence. 3. Prove that A F 3. co(a)+AFVa-no(r) Does it matter if o has free variables other than 4. Prove that, for any sentence,Ah(v→3r(x)兮A=r(v→叭(x). What happens if al is a formula in which is free? 5. Prove that, for any sentence,Ah(彐ro(x)→v)分A=ar(o(x)→v). What happens if al is a formula in which is free? 6. Translate the following statements into predicates You can fool some of the people all of the time You can fool all of people some of the time You cant fool all of the people all of the time One or more of the above may be ambiguous, in which case you will need more than one translation 7. Prove Theorem 7
2. Given an example of an unsatisfiable sentence. 3. Prove that A |= ¬∃xφ(x) ⇔ A |= ∀x¬φ(x). Does it matter if φ has free variables other than x? 4. Prove that, for any sentence ψ, A |= (ψ → ∃xφ(x)) ⇔ A |= ∃x(ψ → φ(x)). What happens if ψ is a formula in which x is free? 5. Prove that, for any sentence ψ, A |= (∃xφ(x) → ψ) ⇔ A |= ∀x(φ(x) → ψ). What happens if ψ is a formula in which x is free? 6. Translate the following statements into predicates. • You can fool some of the people all of the time. • You can fool all of people some of the time. • You can’t fool all of the people all of the time. One or more of the above may be ambiguous, in which case you will need more than one translation. 7. Prove Theorem 7. 6