Discrete mathematics Software school Fudan University May7,2013
. . Discrete Mathematics Yi Li Software School Fudan University May 7, 2013 Yi Li (Fudan University) Discrete Mathematics May 7, 2013 1 / 20
Review Deduction from promises Compactness theorem Application
Review Deduction from promises Compactness theorem Application Yi Li (Fudan University) Discrete Mathematics May 7, 2013 2 / 20
utline o Limits of propositional logic o Predicates and quantifiers o Language of predicate logic
Outline Limits of propositional logic Predicates and quantifiers Language of predicate logic Yi Li (Fudan University) Discrete Mathematics May 7, 2013 3 / 20
Power of pl am dle iven an infinite planar graph. If its every finite subgraph is k-colorable, then the graph itself is also k-colorable Example Every set S can be(totally) ordered Theorem An infinite tree with finite branches has an infinite path
Power of PL . Example . . Given an infinite planar graph. If its every finite subgraph is k-colorable, then the graph itself is also k-colorable. . Example . .Every set S can be (totally) ordered. . Theorem . .An infinite tree with finite branches has an infinite path. Yi Li (Fudan University) Discrete Mathematics May 7, 2013 4 / 20
Expressive Power of PL not nd S Declarative sentences
Expressive Power of PL 1. not. 2. and. 3. or. 4. if . . . then . . . . 5. Declarative sentences. Yi Li (Fudan University) Discrete Mathematics May 7, 2013 5 / 20