Discrete mathematics Yi li Software School Fudan University June20.2012
Discrete Mathematics Yi Li Software School Fudan University June 20, 2012 Yi Li (Fudan University) Discrete Mathematics June 20, 2012 1 / 15
Review o Soundness and completeness Theorem ● Compactness Theore o Size of model o Compactness theorem
Review Soundness and Completeness Theorem Compactness Theorem Size of model Compactness theorem Yi Li (Fudan University) Discrete Mathematics June 20, 2012 2 / 15
Or utline o Application of logic o Limitation of first Order logic
Outline Application of Logic Limitation of First Order Logic Yi Li (Fudan University) Discrete Mathematics June 20, 2012 3 / 15
Application Example(linear order) A structure A=< A, < is called an ordering if it is a model of the following sentences Solution )(-x<x) d。d=(x)(y)(z)(x<y∧y<z)→x<z (Vx)(y)(x<yvx=yvy<x)
Application Example (linear order) A structure A =< A, <> is called an ordering if it is a model of the following sentences: Solution. Φord = (∀x)(¬x < x), (∀x)(∀y)(∀z)((x < y ∧ y < z) → x < z), (∀x)(∀y)(x < y ∨ x = y ∨ y < x). Yi Li (Fudan University) Discrete Mathematics June 20, 2012 4 / 15
Application( Cont. Example(dense order) In order to describe dense linear orders we could add into linear order the following sentence vxvy(x<y→3z(x<z∧z<y)
Application(Cont.) Example (dense order) In order to describe dense linear orders, we could add into linear order the following sentence ∀x∀y(x < y → ∃z(x < z ∧ z < y)) Yi Li (Fudan University) Discrete Mathematics June 20, 2012 5 / 15