复旦大学：《离散数学 Discrete Mathematics》英文讲稿_12 Structure Interpretation Truth Satisfiable Consequence

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