Discrete mathematics Yi li Software School Fudan University June9.2013
. . Discrete Mathematics Yi Li Software School Fudan University June 9, 2013 Yi Li (Fudan University) Discrete Mathematics June 9, 2013 1 / 15
Re eview o Soundness and Completeness theorem o Compactness Theorem 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 9, 2013 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 9, 2013 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 9, 2013 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 9, 2013 5 / 15