Discrete Mathematics(ID) Spring 2013 Lecture 13: Semantics of Predicated Language 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 languag It is the foundation of predicate language. Especially, we should handle sentence and formula Example 1. Consider a 3+ l in programming language. It is obvious that a 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 Actually, a sentence of some natural language is a sequence of many symbols. Its meaning depends on many factors, such as context, culture, and location et al.. Chinese characters are widely used in east Asia. The same word in Mandarin, Cantonese, traditional Chinese, Korean, and Japanese has different meaning It is similar between American and British english 2 Structure In previous lecture, we have a predicate sentence Va(K(a)( (a=b)+B((b, f(a))) in an example of previous lecture. When you first read it. You have no idea about this sentence. Actually it represents"Bobby's father can beat up the father of any other kid on the block". You may find many interpretations of it. This sentence just characterize a structure of all your interpretations In general, a symbol may represent anything possible. The proper meaning of a sentence is deter mined in a specific context. Similarly, we need define something like context for predicate language Structure is introduced to specify 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 R a on the n-tuples(a1, a2,. 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 L, an n-ary function f from A" to 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
Discrete Mathematics (II) Spring 2013 Lecture 13: 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. Actually, a sentence of some natural language is a sequence of many symbols. Its meaning depends on many factors, such as context, culture, and location et al.. Chinese characters are widely used in east Asia. The same word in Mandarin, Cantonese, traditional Chinese, Korean, and Japanese has different meaning. It is similar between American and British English. 2 Structure In previous lecture, we have a predicate sentence ∀x(K(x) → (¬(x = b) → B(f(b), f(x)))) in an example of previous lecture. When you first read it. You have no idea about this sentence. Actually, it represents “Bobby’s father can beat up the father of any other kid on the block”. You may find many interpretations of it. This sentence just characterize a structure of all your interpretations. In general, a symbol may represent anything possible. The proper meaning of a sentence is determined in a specific context. Similarly, we need define something like context for predicate language. Structure is introduced to specify 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 (a1, a2, . . . , 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
1.N,≤,f(x,y)=x·y 2.Q,,f4(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 Each constant term c names the element c 2. if the terms ti,. tn of c name the elements tA,..., t a of A and f is an n-ary function symbol of C, then the term f(t1,., t2) names the element f(t1, .. tn)=f(t1,.,tA) of a Example 4. If we add the instance c, d into the language of last example, we can assign to element c4=1/2;d4=2/3 Example 5. Give ground terms f(a, d), f(d, f(d, d)). They name elements of the A as follows 1.f(,d)4=0;f(d,f(d,d)4=1 2.f(c,d)4=3/2;f(d,f(d,d)4=2/ 9.f(c,d)4=2;f(d,f(d,d)4 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 p 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), AF R(t1,., tn) if and only if R (t,.,tA)
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. 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
2. AFmo+ it is not the case that Ahp(We also write as Ap. 3.4=(Vv)分 AFp or y 4.AF(y∧v)分 Fo and F=v. 5.4F(→v)分 Ap orAL 6.AF(9v)兮( AFp andAh yl)or(A≠ p and y) 7. AF3up(u)+ for some ground term t, AFp(t) 8. AF Voo(u)+ for all ground term t, AFp(t) An atomic sentence is a instance of a instantiated atomic formula. a atomic formula can taken as relation. When you determine the truth of an atomic sentence, you can ask whether(a1, a2, .. an) R if R is n-ary We have known that all ground terms just name all element of a domain. So some and all ground term(s)can represent any element of a domain, which are 3 and V expected. Given a little bit complicated sentence like 3zVy R(a, m), its truth can be determined recursively according to our definition. First, we just try to find some ground term ti to make Vy R(t1, y) true. Then, we just verify that R(t1, t2) is true for t2 visits all elements of A 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. 3.(V)P(c, a) is true 4. Va)P(a, d)is false 5.(Var)(P(,c)->P(, d))is true 6. How about r)(r)P(, ) 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 pp of L is valid, Hp, if it is true in all structure for L 2. Given a set of sentences 2=a1,..., we say that a is a logic consequence of E,2ha, if a is true in every structure in which all of the members of are true
2. A |= ¬φ ⇔ it is not the case that A |= φ ( We also write as A ̸|= φ.) 3. A |= (φ ∨ ψ) ⇔ A |= φ or A |= ψ. 4. A |= (φ ∧ ψ) ⇔ A |= φ and A |= ψ. 5. A |= (φ → ψ) ⇔ A ̸|= φ or A |= ψ. 6. A |= (φ ↔ ψ) ⇔ (A |= φ and A |= ψ) or (A ̸|= φ and A ̸|= ψ). 7. A |= ∃vφ(v) ⇔ for some ground term t, A |= φ(t). 8. A |= ∀vφ(v) ⇔ for all ground term t, A |= φ(t). 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. We have known that all ground terms just name all element of a domain. So some and all ground term(s) can represent any element of a domain, which are ∃ and ∀ expected. Given a little bit complicated sentence like ∃x∀yR(x, y), its truth can be determined recursively according to our definition. First, we just try to find some ground term t1 to make ∀yR(t1, y) true. Then, we just verify that R(t1, t2) is true for t2 visits all elements of A. 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
3. 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 2 has no model. If o 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 possible structures for L corresponding to two different interpretations of the language e are two Example 7. Consider a language L specified by R(, y) and constants co, C1, c2, ...Her 1. Let domain A consists of the natural numbers, let Ra be usual relation . Give these formula 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 2 are valid Again such a structure is called a model of 2. If 2 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
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 . 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. 4
Example 9. All apples are bad Solution. The sentence is simple enough. We first give two possible candidates as following 1.Vx(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 try to check the truth of them Remark 1. 1. V(A(),B()is correct 2. Var(A(r)A B(r)is wrong. Because it require everything is an apple Example 10. Some apples are bad. Solution. Similarly, we also have two possible candidates 1.彐x(A(x)∧B(x) 2.彐r(A(x)→B(x) In this case, the status exchanges Remark2.1.彐r(A(x)∧B(x) is correct 2. 3c(A(),B(a)) is improper. Because even every apple is good but the statement is still true if a is something other than apple These two examples would be encountered many times. There are some patterns to express sen- tences 1. Va(-,): Everything in a certain category has some property 2. 3x( A: 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
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: 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. 5
Theorem 7. Let p be an open formula of predicate logic. We may view p as formula or of propositional logic by regarding every atomic subformula of y as a propositional letter. With this correspondence, yp is a valid formula of predicate logic if and only if ypl is valid in propositional logic Before proof, consider the following example mple 11. Consider an open formula p of predicate logic and a corresponding proposition by rding every atomic subformula of p as a propositional letter. For example 1.A(x)V=A(x), 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 V. P(f(a,c)is true and one in which it is fal 2. Given an example of an unsatisfiable sentence. 3. Prove that A F 3. co(r)+A Varno(r). Does it matter if o has free variables other than 4. Prove that, for any sentence y,Ah(v→彐ro(x)分A上彐(→叭(x). What happens if v is a formula in which a is free? 5. Prove that, for any sentence v, A Fro()v)+AF Va(o(r),v). What happens if a is a formula in which a 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
Theorem 7. Let φ be an open formula of predicate logic. We may view φ as formula φ′ 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 φ′ 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. 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