复旦大学：《离散数学 Discrete Mathematics》英文讲稿_10 Application of compactness theorem Limits of propositional logic Predicates and quantifiers

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