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. 3 Z 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 o2,>,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. 3 Z, >, f A(x, y) = x − y. Yi Li (Fudan University) Discrete Mathematics May 29, 2012 9 / 27