Discrete mathematics Yi li Software school Fudan University May29,2012
Discrete Mathematics Yi Li Software School Fudan University May 29, 2012 Yi Li (Fudan University) Discrete Mathematics May 29, 2012 1 / 27
Review o Predicates and quantifiers Language: Terms and Formulas o Formation Trees and structures
Review Predicates and Quantifiers Language: Terms and Formulas Formation Trees and Structures Yi Li (Fudan University) Discrete Mathematics May 29, 2012 2 / 27
utline o Structure Interpretation Truth o Satisfiable o Consequence
Outline Structure Interpretation Truth Satisfiable Consequence Yi Li (Fudan University) Discrete Mathematics May 29, 2012 3 / 27
Semantics: meaning and Truth What is language? o What is the meaning of language?
Semantics: meaning and Truth What is language? What is the meaning of language? Yi Li (Fudan University) Discrete Mathematics May 29, 2012 4 / 27
Language finition(Language A language L consists of the following disjoint sets of distinct primitive symbols o Variables: x, y, xo, x1,..., yo, y1, ...(an infinite set) O Constants: c, d, co, do, ...(any set of them) Connectives:∧,一,,→>,+ Quantifiers:V,彐 o Predicate symbols: P, Q, R, P1, P2 o Function symbols: f, g, h, fo, fi O Punctuation:, and),(
Language Definition (Language) A language L consists of the following disjoint sets of distinct primitive symbols: 1 Variables: x, y, x0, x1, . . . , y0, y1, . . . (an infinite set) 2 Constants: c, d, c0, d0, . . . (any set of them). 3 Connectives: ∧, ¬, ∨,→,↔ 4 Quantifiers: ∀, ∃ 5 Predicate symbols: P, Q, R, P1, P2, . . . 6 Function symbols: f , g, h, f0, f1, . . . 7 Punctuation: , and ), ( Yi Li (Fudan University) Discrete Mathematics May 29, 2012 5 / 27
languange( Cont) am e Consider the language with one predicate P(x, y)and function f(x, y). We can view them as o w with and f(x,y)=xy o Q with and f(x,y)=x:y o Z with and f(x,y)=x-y
Languange(Cont.) Example Consider the language with one predicate P(x, y) and function f (x, y). We can view them as: 1 N with ≤ and f (x, y) = x · y. 2 Q with and f (x, y) = x − y. Yi Li (Fudan University) Discrete Mathematics May 29, 2012 6 / 27
St ructure amp dle Consider this sentence Bobbys father can beat up the father of any other kid on the block Solution Let O K(x): x is a child on the block and b means Bobby o f(x): x's father, O B(,y): x can beat up y o Finally, Vx(K(x)→(-(X=b)→B(f(b),f(x)
Structure Example Consider this sentence ”Bobby’s father can beat up the father of any other kid on the block”. Solution Let 1 K(x): x is a child on the block and b means Bobby. 2 f (x): x’s father, 3 B(x, y): x can beat up y, 4 Finally, ∀x(K(x) → (¬(x = b) → B(f (b), f (x)))). Yi Li (Fudan University) Discrete Mathematics May 29, 2012 7 / 27
Structure( Cont Definition A structure A for a language l consists of nonempty domain A o an assignment to each n-ary predicate symbol r of L, of an actual predicate r on the n-tuples n) from A O an assignment, to each constant symbol c of L, of an element cA of A and, to each n-ary function symbol f of L o an n-ary function fa from an to A
Structure(Cont.) Definition A structure A for a language L consists of 1 a nonempty domain A, 2 an assignment, to each n-ary predicate symbol R of L, of an actual predicate R A on the n-tuples (n1, n2, . . . , an) from A, 3 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, 4 an n-ary function f A from A n to A. Yi Li (Fudan University) Discrete Mathematics May 29, 2012 8 / 27
Structure( Cont am e Now we have three structures of language P(x, y), f(x, y) oN,≤,f4(x,y)=x:y g,,f(x,y)=x-y
Structure(Cont.) Example 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. Yi Li (Fudan University) Discrete Mathematics May 29, 2012 9 / 27
Interpretation Definition(The interpretation of ground terms) o Each constant term c names the element c O if the terms ti,..., tn of l name the elements ti,..., t of A and f is an n-ary function symbol of L, then the term f(,.., t2) names the element f(th,,tn)4=f(t1,……,th)ofA
Interpretation Definition (The interpretation of ground terms) 1 Each constant term c names the element c A. 2 if the terms t1, . . . ,tn of L name the elements t A 1 , . . . ,t A 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 , . . . ,t A n ) of A. Yi Li (Fudan University) Discrete Mathematics May 29, 2012 10 / 27
