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