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