Discrete mathematics Yi li Software school Fudan University May9,2012
Discrete Mathematics Yi Li Software School Fudan University May 9, 2012 Yi Li (Fudan University) Discrete Mathematics May 9, 2012 1 / 22
Review o Deduction from promises o Compactness theorem Application
Review Deduction from promises Compactness theorem Application Yi Li (Fudan University) Discrete Mathematics May 9, 2012 2 / 22
utline Application of compactness theorem o Limits of propositional logic o Predicates and quantifiers
Outline Application of compactness theorem Limits of propositional logic Predicates and quantifiers Yi Li (Fudan University) Discrete Mathematics May 9, 2012 3 / 22
Application of compactness theorem am dle Given an infinite planar graph. If its every finite subgraph is k-colorable, then the graph itself is also k-colorable
Application of compactness theorem Example Given an infinite planar graph. If its every finite subgraph is k-colorable, then the graph itself is also k-colorable. Yi Li (Fudan University) Discrete Mathematics May 9, 2012 4 / 22
Application of compactness theorem Solution: Let pa i represent vertex a is colored with i We can formulate a graph which is k-colorable with the following propositions ③paVp:2V…Vp3k, for every a∈V. It means every vertex could be colored with at least one of k CO olors 0-(pa;∧p3),1≤j<j≤ k for all a∈V. It means C;∩C;=0 (pa;∧Pb),i=1,…, k for all aeb. It means no neighbors have the same color
Application of compactness theorem Solution: Let pa,i represent vertex a is colored with i. We can formulate a graph which is k-colorable with the following propositions. 1 pa,1 ∨ pa,2 ∨ · · · ∨ pa,k , for every a ∈ V. It means every vertex could be colored with at least one of k colors. 2 ¬(pa,i ∧ pa,j), 1 ≤ i < j ≤ k for all a ∈ V. It means Ci ∩ Cj = ∅. 3 ¬(pa,i ∧ pb,i), i = 1, . . . , k for all aEb. It means no neighbors have the same color . Yi Li (Fudan University) Discrete Mathematics May 9, 2012 5 / 22
Application of compactness theorem Example Every set S can be(totally) ordered
Application of compactness theorem Example Every set S can be (totally) ordered. Yi Li (Fudan University) Discrete Mathematics May 9, 2012 6 / 22
Application of compactness theorem 「 Theorem An infinite tree with finite branch has an infinite path
Application of compactness theorem Theorem An infinite tree with finite branch has an infinite path. Yi Li (Fudan University) Discrete Mathematics May 9, 2012 7 / 22
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 9, 2012 8 / 22
Expressive Power of PL Ramp dle If Socrates is a man then socrates is mortal Solution( Propositional Logic) Q A: Socrates is a man Q B: Socrates is mortal o We can represent the previous statement as a-b o IfA is true, then we know B is true
Expressive Power of PL Example If Socrates is a man then Socrates is mortal. Solution (Propositional Logic) 1 A: ”Socrates is a man”. 2 B: ”Socrates is mortal”. 3 We can represent the previous statement as A → B. 4 If A is true, then we know B is true. Yi Li (Fudan University) Discrete Mathematics May 9, 2012 9 / 22
Limits of pl Xam dle Socrates is a man". What can we do>aP" and Given two statements: "Al men are mort Solution o We all know the following statement holding Socrates is mortal o If they are formalized as two proposition, nothing can be implied
Limits of PL Example Given two statements:”All men are mortal” and ”Socrates is a man”. What can we do? Solution 1 We all know the following statement holding, ”Socrates is mortal”. 2 If they are formalized as two proposition, nothing can be implied. Yi Li (Fudan University) Discrete Mathematics May 9, 2012 10 / 22