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 we
Discrete 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
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. D Remark 1. Wht does PL fail here? 1. There is no relation between P and Q 2."is/in"relationship can not be expressed by PL 3. Similarly, there are" there exists….","al…."," anong….",and"only…." The conclusion is that a richer language other than PL is needed to overwhelm the troubles just Solution( Continue). However, the statements can be abstracted further like 1. P: All As have property B 2. Q: C is one of As. Follow this way, we could find a solution 4 Predicates and quantifiers In last section, we still leave some unsolved troubles, for example, how to express"all". Consider the following example Example 3. 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. L Remark 2. However, the statement can not be expressed clearly by just a proposition 1. 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 Solution( Continue). Consider a special instance of this statement. Suppose Andy is a student and Paul is a instructo 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
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. Remark 1. Wht does PL fail here? 1. There is no relation between P and Q. 2. ”is/in” relationship can not be expressed by PL. 3. Similarly, there are ”there exists ...”, ”all ...”, ”among ...”, and ”only ...”. The conclusion is that a richer language other than PL is needed to overwhelm the troubles just faced. Solution(Continue). However, the statements can be abstracted further like 1. P: All As have property B. 2. Q: C is one of As. Follow this way, we could find a solution. 4 Predicates and quantifiers In last section, we still leave some unsolved troubles, for example, how to express “all”. Consider the following example. Example 3. 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 2. However, the statement can not be expressed clearly by just a proposition. 1. 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. 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(P aul):Paul is an instructor. 2
3. Y(Andy, Paul): Andy is younger than Paul With these propositions, we can represent an instance of our statement Remark 3. Examining the instance and sentence in detail, we worry about 1. There are many instances. Too many symbols are needed 2. How about "every/all"and"some"? Solution( Continue). We introduce new concepts 1. Variable, which can represent any students or instructors 2. Quantifiers (a)3 means"there is", which is called existential quantifier (b)V means"for all", which is called universal quantifiers Now it can be written as vr(S(x)→y(I(y)∧Y(x,y) As we pointed out in class, this sentence could be interpreted as there is an instructor who is elder than all students. The logic expression should be written as another one, which is left as exercise block-ple 4. Consider this sentence"Bobby's father can beat up the father of any other kid on the Solution. Here the point is that how to express the connection between child and father. Function is proper than predicate because a child can determine his father. Let 1. K(): a is a child on the block and b means bobby 3.B(x,y) beat. up y, We have x(K(x)→(-(x=b)→B(f(b),f(x) To enhance the expressive power of PL, we introduce the following symbols predicates variables constants
3. Y (Andy, P aul): Andy is younger than Paul. With these propositions, we can represent an instance of our statement. Remark 3. Examining the instance and sentence in detail, we worry about: 1. There are many instances. Too many symbols are needed. 2. How about ”every/all” and ”some”? Solution(Continue). We introduce new concepts: 1. Variable, which can represent any students or instructors. 2. Quantifiers: (a) ∃ means ”there is”, which is called existential quantifier. (b) ∀ means ”for all”, which is called universal quantifiers. Now it can be written as ∀x(S(x) → ∃y(I(y) ∧ Y (x, y))). As we pointed out in class, this sentence could be interpreted as there is an instructor who is elder than all students. The logic expression should be written as another one, which is left as an exercise. Example 4. Consider this sentence ”Bobby’s father can beat up the father of any other kid on the block”. Solution. Here the point is that how to express the connection between child and father. Function is proper than predicate because a child can determine his father. Let 1. K(x): x is a child on the block and b means Bobby. 2. f(x): x’s father, 3. B(x, y): x can beat up y, We have ∀x(K(x) → (¬(x = b) → B(f(b), f(x)))). To enhance the expressive power of PL, we introduce the following symbols. • predicates • variables • constants 3
functions universal quantifier: V, " for all existential quantifier: 3, there exists Now, we expand our language as following Definition 1(Language). A language L consists of the following disjoint sets of distinct primitive symbols: 1. Variables: 9, o, r1,..., 90, 91,..(an infinite set) 2. Constants: c, d, co, do, ...(any set of them) Connectives:∧,→,V,→,分 4. Quantifiers:V,彐 5. Predicate symbols: P,Q, R,P, P2, 6. Function symbols: f, 9, h, fo, f1 7. Punctuation: the comma, and (right and left) parentheses ),( As predicate is the most important one, it is called predicate logic. It is named first order logic together with proposition logic. In the latter, we will show you that proposition logic can be embedded into predicate logic. In another word, proposition logic is a subset of predicate logic To formalize the examples shown to introduce predicate logic, we define the following definitions Definition 2(Term). Terms 1. Every variable is a term 2. Every constants symbol is a term. 3. If f is an n-ary function symbol (n= 1, 2, ...) and t1, .. tn are terms, then f(t1,., tn) is also a term Definition 3(Ground term). Terms with no variables are called variable-free terms or ground terms Definition 4(Atomic formula). An atomic formala is an expression of the form R(t1,.,tn where r is an n-ary predicate symbol and t1,.. tn are terms Definition 5(Formula). Formulas 1. Every atomic formula is a formula 2. If a, B are formulas, then so are(aAB),(a-B),a+B), a),( avB) 3. If v is a variable and a is a formala, then((u)a) and((Vu))are also formulas
• functions • universal quantifier : ∀, ”for all”. • existential quantifier : ∃, there exists Now, we expand our language as following: Definition 1 (Language). A language L consists of the following disjoint sets of distinct primitive symbols: 1. Variables: x, y, x0, x1, . . . , y0, y1, . . . (an infinite set) 2. Constants: c, d, c0, d0, . . . (any set of them). 3. Connectives: ∧, ¬, ∨, →, ↔ 4. Quantifiers: ∀, ∃ 5. Predicate symbols: P, Q, R, P1, P2, . . . 6. Function symbols: f, g, h, f0, f1, . . . 7. Punctuation: the comma , and (right and left) parentheses ), ( As predicate is the most important one, it is called predicate logic. It is named first order logic together with proposition logic. In the latter, we will show you that proposition logic can be embedded into predicate logic. In another word, proposition logic is a subset of predicate logic. To formalize the examples shown to introduce predicate logic, we define the following definitions. Definition 2 (Term). Terms. 1. Every variable is a term 2. Every constants symbol is a term. 3. If f is an n-ary function symbol ( n = 1, 2, . . . ) and t1, . . . , tn are terms, then f(t1, . . . , tn) is also a term. Definition 3 (Ground term). Terms with no variables are called variable-free terms or ground terms. Definition 4 (Atomic formula). An atomic formula is an expression of the form R(t1, . . . , tn) where R is an n-ary predicate symbol and t1, . . . , tn are terms. Definition 5 (Formula). Formulas. 1. Every atomic formula is a formula. 2. If α, β are formulas, then so are (α ∧ β),(α → β),(α ↔ β),(¬α),(α ∨ β). 3. If v is a variable and α is a formula, then ((∃v)α) and ((∀v)α) are also formulas. 4
With predicate logic, many mathematical statement can be formalized. Consider the following Example 5. Let the domain consist of all relational numbers @. Again (a, y)=(a<y), f(a, y) +y, g(, y)=r:y and a=0, b=1,c=2 are constant 1.(y(x,y)Ag2(y,2) 2.(y)(y(x,y)∧g(y,2) 3.(yx)(y(x,2)→((y)(y(x,y)∧y(y,z) 4.(x)(wy)(y(x,y)→(y(x,9(f(x,y),c)^g(9(f(x,y),c),y))) 5. p(y, f(y, y)) 5 Conclusion In this section. we show some limits of pl and introduce some new tools to overwhelm the troubles Finally, we extend PL to predicated logic to express much finer statement. This is a typical pattern n practice, we program code based on existing code other than from scratch. For example, we modify existing data structure or inherit a class by introducing new member and methods. It is important" don't try to build your own wheels unless there is no choice Exercises 1. Translate the following into predicates (a) Neither a or b is a member of every set (b) If horse are animals, then heads of horse are heads of animals (c) If some trains are late then all trains are late. (d)There is no set of which every set is a member 2. Assume that we have a language with the following parameters: N, intended to mean"is a number"1, intended to mean"is interesting;<, intended to mean"is less than". Give (vx)(N(x)→(I(x)→=(vy)(N(y)→(I(y)→-(x<y) Translate them back to english 3. Ex 2(c, e, f)/ page 88 4. Ex 3/ page 8
With predicate logic, many mathematical statement can be formalized. Consider the following example. Example 5. Let the domain consist of all relational numbers Q. Again φ(x, y) = (x < y), f(x, y) = x + y, g(x, y) = x ÷ y and a = 0, b = 1, c = 2 are constants. 1. (φ(x, y) ∧ φ(y, z)) 2. ((∃y)(φ(x, y) ∧ φ(y, z))) 3. ((∀x)(φ(x, z) → ((∃y)(φ(x, y) ∧ φ(y, z)))) 4. ((∀x)((∀y)(φ(x, y) → (φ(x, g(f(x, y), c)) ∧ φ(g(f(x, y), c), y))))) 5. φ(y, f(y, y)) 5 Conclusion In this section, we show some limits of PL and introduce some new tools to overwhelm the troubles. Finally, we extend PL to predicated logic to express much finer statement. This is a typical pattern. In practice, we program code based on existing code other than from scratch. For example, we modify existing data structure or inherit a class by introducing new member and methods. It is important “don’t try to build your own wheels unless there is no choice.” Exercises 1. Translate the following into predicates (a) Neither a or b is a member of every set. (b) If horse are animals, then heads of horse are heads of animals. (c) If some trains are late then all trains are late. (d) There is no set of which every set is a member. 2. Assume that we have a language with the following parameters: N, intended to mean “is a number”; I, intended to mean “is interesting”; <, intended to mean “is less than”. Give (∀x)(N(x) → (I(x) → ¬(∀y)(N(y) → (I(y) → ¬(x < y))))). Translate them back to English. 3. Ex 2(c, e, f)/ page 88 4. Ex 3/ page 88 5
