《离散数学 predicates and quantifiers(期望与量词)》由会员分享，可在线阅读，更多相关《离散数学 predicates and quantifiers(期望与量词)（30页珍藏版）》请在金锄头文库上搜索。
1、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” “
2、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 s
3、tatement “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,(
4、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
5、 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 verificatio
6、n 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 quantifie
7、rs(存在量词) 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 universa
8、l 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-al
9、l 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: giv
10、ing 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) ? S
11、olution: 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
12、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 lea
13、st 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
14、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
15、 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,
