Discrete Mathematics(II) Spring 2012 Lecture 10: Predicates and Quantifiers Lecturer. yil 1 Overview n this lecture, we show you why a richer language should be introduced than propositional language PL in brief 2 Expressive power of PL As we learned in first half semester, propositional logic can express and, or, not, imply, and if and only if Example 1. If Socrates is a man then Socrates is mortal solution. This is a declarative statement. And we know it is true. It can be divided into two parts or two proposition letters 1. A: "Socrates is a man' 2. B: Socrates is mortal Then we can represent the previous statement as A,B. According to our deduction rules, if A is true. then we know b is true In the last class, we had learned how to apply proposition logic to find suspect of a murder case. And we also use proposition logic to prove k-colorable graph 3 Limits of pl Proposition logic is powerful. However there are some which cannot be described by it. Let's consider the following example d op ple 2. Given two statements: "All men are mortal"and"Socrates is a man". What can we Solution. We all know the following statement holding, "Socrates is mortal". If they are formalized as two propositions, nothing can be implied. Because we cannot express the relationship between Socrates and all men. It means simple way of proposition logic can not represent this statementDiscrete Mathematics (II) Spring 2012 Lecture 10: Predicates and Quantifiers Lecturer: Yi Li 1 Overview In this lecture, we show you why a richer language should be introduced than propositional language, PL in brief. 2 Expressive power of PL As we learned in first half semester, propositional logic can express and, or, not, imply, and if and only if. Example 1. If Socrates is a man then Socrates is mortal. solution. This is a declarative statement. And we know it is true. It can be divided into two parts or two proposition letters. 1. A: ”Socrates is a man”. 2. B: ”Socrates is mortal”. Then we can represent the previous statement as A → B. According to our deduction rules, if A is true, then we know B is true. In the last class, we had learned how to apply proposition logic to find suspect of a murder case. And we also use proposition logic to prove k-colorable graph. 3 Limits of PL Proposition logic is powerful. However there are some which cannot be described by it. Let’s consider the following example. Example 2. Given two statements:”All men are mortal” and ”Socrates is a man”. What can we do? Solution. We all know the following statement holding, ”Socrates is mortal”. If they are formalized as two propositions, nothing can be implied. Because we cannot express the relationship between Socrates and all men. It means simple way of proposition logic can not represent this statement. 1