2018/10/3,the Foundations:Logic and Proof Guo Jian,1,1.3 Predicates and Quantifiers Introduction (1) propositional logic cannot adequately express the meaning of statements “Every computer connected to the university network is functioning properly” Can not conclude “MATH3 is functioning properly” “CS is under attack by an intruder” Can not conclude using the rules of propositional logic “There is a computer on the university network that is under attack by an intruder”. -predicate logic: predicate, quantifiers,2018/10/3,the Foundations:Logic and Proof Guo Jian,2,1.predicate (1) Consider the statement “x is greater than 3”. x-subject of the statement “is greater than 3”-predicate, property of the subject. (2) P(x) - “x is greater than 3” P-”greater than 3”(predicate) P(x) is also said to be the value of propositional function P at x.,2018/10/3,the Foundations:Logic and Proof Guo Jian,3,(3) P(x)-”x is greater than 3”, propositional function P(4)-proposition ,true P(2)-proposition, false (3)Example2(p31) A(x)-”Computer x is under attack by an intruder.” CS2, MATH1 are under attack. A(CS1)-false A(CS2)-true A(MATH1)-true (4) Statements can involve more than 1 variable. Example 3 (page 31): Q(x,y)-”x=y+3” Q(1,2)-false Q(3,0)-true,2018/10/3,the Foundations:Logic and Proof Guo Jian,4,(5) In general, A statement of the form P(x1,x2,xn) is the value of the propositional function P at the n-tuple (x1,x2,xn) , and P is called a n-ary predicate. (6)Predicates are used in the verification that computer programs produce the desired output when given valid input. Precondition-valid input Postcondition-the conditions that output should satisfy.,2018/10/3,the Foundations:Logic and Proof Guo Jian,5,(7) quantifiers(量词)-a range of elements universal quantifiers(全称量词) existential quantifiers(存在量词) predicate calculus(谓词演算)-the area of logic that deals with predicate and quantifiers.,2018/10/3,the Foundations:Logic and Proof Guo Jian,6,2. Universal Quantifier (1) domain (or Universe of Discourse )个体域 -a set containing all the values of a variable (2) Definition 1 (page 34) The universal quantification of P(x) is the statement “P(x) for all values of x in the domain.” -x P(x) ,read “for all x P(x)”or “for every x P(x)” A counterexample of x P(x) :an element makes P(x) to be false.,2018/10/3,the Foundations:Logic and Proof Guo Jian,7,(3) Example 8(page 34) P(x)-”x+1x” the domain-all real numbers How about x P(x) ? Answer: x P(x) -true (4) Example 9 (page 35) Q(x)-”x2” the domain-all real numbers How about x Q(x) ? Answer: x Q(x) -false,2018/10/3,the Foundations:Logic and Proof Guo Jian,8,(5)Example 10 Let P(x) be “x20”. the domain - integers Show x P(x) is false Solution: giving a counterexample. X=0 (6) Further explanation the domain -finite set x1,x2,xn x P(x) is the same as P(x1) / P(x2) / / P(xn),2018/10/3,the Foundations:Logic and Proof Guo Jian,9,(7) Example 11 (page 35) P(x)-” x210 ” the domain -”the positive integers not exceeding 4” 1,2,3,4 How about x P(x) ? Solution: x P(x) is the same as P(1) / P(2) / P(3) / P(4) -false,2018/10/3,the Foundations:Logic and Proof Guo Jian,10,(7) Example 13 (page 36) x (x2x) the domain - all integers Solution: x2x iff x(x-1)0 iff x 1 or x0 x (x2x)-true How about the domain - all real numbers x (x2x) - false,2018/10/3,the Foundations:Logic and Proof Guo Jian,11,3. Existential Quantifier Definition 2 (existential quantifier, page 36) The existential Quantification of P(x) is the statement “There exists an element x in the domain such that P(x) is true” -denoted as x P(x) “There is an x such that P(x)” “There is at least one x such that P(x)” “For some x, P(x)”,2018/10/3,the Foundations:Logic and Proof Guo Jian,12,(2) Example 14 (page 36) P(x)-”x3” the domain -all real numbers Consider x P(x) Solution: x P(x) is true Why? (x can be 3.5, 4, ., which makes is P(x) is true),2018/10/3,the Foundations:Logic and Proof Guo Jian,13,(3) Example 15 (page 36) Q(x)-”x=x+1” the domain -all real numbers Consider x Q(x) Solution: For every real number x, Q(x) is false. Therefore, x Q(x) is false,2018/10/3,the Foundations:Logic and Proof Guo Jian,14,(4) If the domain is a finite set, i.e., x1, x2, , xn , then x P(x) is the same as P(x1) / P(x2) / P(xn),2018/10/3,the Foundations:Logic and Proof Guo Jian,15,(5) Example 16 (page 37) P(x)-”x210” the domain -”all the positive integers not exceeding 4” Consider x P(x) Solution: universe of discourse=1, 2, 3, 4 x P(x) is the same as P(1) / P(2) / P(3) / P(4) x P(x) is true because P(4) is true.,2018/10/3,the Foundations:Logic and Proof Guo Jian,16,(6) Summary Statement When True? When False x P(x) P(x) is true There is an x for for all x which P(x) is false x P(x) There is an x P(x) is false for for which P(x) every x is true,