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 statement
Discrete 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
Remark 1. 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….","al…."," anong….",and"only 4. A richer language is needed. Solution(Continue). However, the statements can be abstracted further like 1. P: All As have property B 2. Q: C is one of Follow this way, we could find a solution 4 Predicates and quantifiers 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. D Remark 2. 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 Solution( Continue). Consider a special instance of this statement. Suppose Andy is a student and Let's introduce some predicates, which asserts something has some property Now we have 1. S(Andy ) Andy is a student. 3. Y(Andy, Paul): Andy is younger than Paul. Remark 3. 1. There are many instances. Too many symbols are needed 2. Introduce variable, which can represent any students or instructors. 3. How about"every/all"and"some"? (a)3 means"there is", which is called existential quantifier (b )v means "for all", which is called universal quantifiers
Remark 1. 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. A richer language is needed. 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 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. 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. 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. 3. Y (Andy, P aul): Andy is younger than Paul. Remark 3. 1. There are many instances. Too many symbols are needed. 2. Introduce variable, which can represent any students or instructors. 3. How about ”every/all” and ”some”? (a) ∃ means ”there is”, which is called existential quantifier. (b) ∀ means ”for all”, which is called universal quantifiers. 2
Solution( Continue). Now it can be written as Var( s(r),3y(I(yAY(, 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 Example 4. Consider this sentence " Bobby's father can beat up the father of any other kid on the Solation. 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 2. f(a): ar's father, 3. B(a, y): a can beat up y, We have vx(K(x)→(-(x=b)→B(f(b),f(x)) To enhance the expressive power of PL, we introduce the following symbols predicat variables ● constant functions universal quantifier: V, for all existential quantifier: 3, there exists Now, we expand our language as followin Definition 1(Language). A language L consists of the following disjoint sets of distinct primitive 1. Variables: 9, o, 1, .., 90, y1,..(an infinite set) 2. Constants: c, d, co, do, ...(any set of th en 3. Connectives:∧,,V,→,分 4. Quantifiers:V,彐 PO.R. P1P 6. Function symbols: f, 9, h, fo, fi
Solution(Continue). 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 • 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, . . . 3
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 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) s also a term Definition 3(Ground term). Terms with no variables are called variable-free terms or ground 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 ti, .. tn are terms Definition 5 (Formula). Formalas 1. Every atomic formula is a formula 2. If a, B are formulas, then so are(oA B),(a>),a+B), a), (avB) 3. If v is a variable and a is a formula, then(vja)and((vu)a) are also formulas With predicate logic, many mathematical statement can be formalized. Consider the followin Example 5. Let the domain consist of all relational numbers @. Again p (a, y)=(a<y), f(a, y) +y, g(a, y)=a:y and a=0, b= l, c=2 are constants 1.(y(x,y)∧y(y,2) 2.(y)(y(x,y)∧y(y,2) (vx)(y(x,2)→(y)(yp(x,y)∧φ(y,2) 4.(x)(wy)(y(x,y)→(y(x,y(f(x,y),c)∧φ(g(f(x,y),c),y) 5.9(3,f(3,y)
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. 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)) 4
Exercises 1. Every set S can be(totally) ordered.(Hint: Use proposition to represent partial order and dichotomy, then try to apply compactness theorem. 2.Ex7/p46 3. 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 4. 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)→((y)→-(x<y)) Translate them back to english 5. Ex 2(c, e, f)/ page 88 6. Ex 3/ page 88
Exercises 1. Every set S can be (totally) ordered. (Hint: Use proposition to represent partial order and dichotomy, then try to apply compactness theorem.) 2. Ex 7/p46. 3. 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. 4. 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. 5. Ex 2(c, e, f)/ page 88 6. Ex 3/ page 88 5