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