Discrete Mathematics(ID) Spring 2013 Lecture 11: Predicates and Quantifiers 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 olution. This is a declarative statement. And we know it is true. It can be divided into two parts or two proposition letters A:” Socrates is a mar 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 Chip design is based on small part of proposition logic And we also use proposition logic to prove k-colorable graph, any set is able to be totally ordered and kobig lemma. They are hard to prove in their original domain. But once it is transformed into proposition logic form, it is easy to prove by applying compactness theorem 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 weDiscrete Mathematics (II) Spring 2013 Lecture 11: 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. Chip design is based on small part of proposition logic. And we also use proposition logic to prove k-colorable graph, any set is able to be totally ordered, and k¨obig lemma. They are hard to prove in their original domain. But once it is transformed into proposition logic form, it is easy to prove by applying compactness theorem. 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? 1