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, yDiscrete 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 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 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