复旦大学：《离散数学》习题课讲义（李弋）10 Limits of propositional logic Predicates and quantifiers Language of predicate logic

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

Expressive Power of PL Ramp dle If Socrates is a man then Socrates is mortal Solution(Propositional Logic) O A: Socrates is a man B: Socrates is mortal We can represent the previous statement as A-,B o If A 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 7, 2013 6 / 20

Limits of pl Xam dle Given two statements: "All men are mortal"and Socrates is a man". What can we do 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 7, 2013 7 / 20

Limits of pl Example The previous example can be abstracted further like O P: All as have property b O Q: C is one of As Remark o There is no relation between P and Q o The flaw is that"is/in"relationship can not be expressed by pl O Consider" there exists….","all∴."," among….", and / on y Yi Li(Fu

Limits of PL . Example . . The previous example can be abstracted further like 1. P: All As have property B. 2. Q: C is one of As. . Remark . . 1. There is no relation between P and Q. 2. The flaw is that ”is/in” relationship can not be expressed by PL. 3. Consider ”there exists ...”, ”all ...”, ”among ...”, and ”only ...”. 4. Conclusion: a richer language is needed. Yi Li (Fudan University) Discrete Mathematics May 7, 2013 8 / 20

Limits of pl Example Consider a simple sentence, every student is younger than some instructor Solution It is a declarative statement, which can be expressed by a proposition letter, say P Remark O However, it means being a students, being a instructor and being younger than somebody else o P fails to reflect the finer logic structure of it

Limits of PL . Example . . Consider a simple sentence, every student is younger than some instructor. . Solution . . It is a declarative statement, which can be expressed by a proposition letter, say P. . Remark . . 1. However, it means being a students, being a instructor and being younger than somebody else. 2. P fails to reflect the finer logic structure of it. Yi Li (Fudan University) Discrete Mathematics May 7, 2013 9 / 20

Limits of pl Solution(Continue) Consider a special instance of this statement. Suppose Andy is a student and paul is a instructor Lets introduce some predicates, which asserts something has some property. Now we have S(Andy ) Andy is a student o/(Paul): Paul is an instructor. O Y(Andy, Paul: Andy is younger than Paul

Limits of PL . Solution (Continue) . . Consider a special instance of this statement. Suppose Andy is a student and Paul is a instructor. Let’s introduce some predicates,which asserts something has some property. Now we have 1. S(Andy): Andy is a student. 2. I(Paul):Paul is an instructor. 3. Y (Andy, Paul): Andy is younger than Paul. Yi Li (Fudan University) Discrete Mathematics May 7, 2013 10 / 20