复旦大学：《离散数学》习题课讲义（李弋）12 Structure Interpretation Truth Satisfiable Consequence

Discrete mathematics Software school Fudan University May28,2013

. . Discrete Mathematics Yi Li Software School Fudan University May 28, 2013 Yi Li (Fudan University) Discrete Mathematics May 28, 2013 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 28, 2013 2 / 27

utline Structure Interpretation o Truth o Satisfiable o Consequence

Outline Structure Interpretation Truth Satisfiable Consequence Yi Li (Fudan University) Discrete Mathematics May 28, 2013 3 / 27

Semantics: meaning and Truth o 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 28, 2013 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:∧,一,,→>,+ o 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 28, 2013 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 oNwith≤andf(x,y)=x·y. 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 28, 2013 6 / 27

St ructure amp dle Consider this sentence bobby' s father can beat up the father of any other kid on the block

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 28, 2013 7 / 27

St ructure amp dle Consider this sentence bobby' s father can beat up the father of any other kid on the block Solution Let

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 28, 2013 7 / 27

St ructure amp dle Consider this sentence bobby' s 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

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 28, 2013 7 / 27

St ructure amp dle Consider this sentence bobby' s 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):xs father

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 28, 2013 7 / 27