离散数学 Predicates and Quantifiers(期望与量词)

1、1.3 Predicates and QuantifiersIntroduction (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 t

2、he rules of propositional logic“There is a computer on the university network that is under attack by an intruder”.predicate logic: predicate, quantifiers2022/8/2811.predicate (1) Consider the statement “x is greater than 3”. xsubject of the statement “is greater than 3”predicate, property of the su

3、bject. (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. 2022/8/282(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 in

4、truder.” 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)true2022/8/283(5) In general, A statement of the form P(x1,x2,xn) is the value of the propositional function P at the n-tuple

5、 (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.Preconditionvalid inputPostconditionthe conditions that output should satisfy.2022/8/284(7) quantifiers(量词)a range of elementsuniversal

6、quantifiers(全称量词)existential quantifiers(存在量词)predicate calculus(谓词演算)the area of logic that deals with predicate and quantifiers.2022/8/2852. Universal Quantifier(1) domain (or Universe of Discourse )个体域 a set containing all the values of a variable(2) Definition 1 (page 34) The universal quantific

7、ation 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.2022/8/286 (3) Example 8(page 34) P(x)”x+1x” the domainall real numbers How about x P(x) ? Answer: x P(x) true(4) E

8、xample 9 (page 35) Q(x)”x0”. the domain integers Show x P(x) is falseSolution: 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) 2022/8/288(7) Example 11 (page 35) P(x)” x23” the domain all real numbers Consider x P(x) So

9、lution: x P(x) is true Why? (x can be 3.5, 4, ., which makes is P(x) is true)2022/8/2812(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 false2022/8/2813(4) If the domain is a finite set, i.e., x1,

10、 x2, , xn , then x P(x) is the same as P(x1) / P(x2) / P(xn)2022/8/2814(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 t

11、rue.2022/8/2815(6) SummaryStatement 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 2022/8/28164. Other quantifiersThe most often quantifier is uniqueness quantifierdenoted by !xP(x), or 1

12、x P(x)5. Quantifiers with restricted domains(1)There is a condition after quantifier.(2)Example x 0), y0(y3 0)and z0(z2=2), if the domain is the real numbers.(3) x 0) is the same as x (x 0)(4) z(z0z2=2)6. Precedence of Quantifiers: and have higher than all logical operators.2022/8/28177. Binding Var

13、iables (变量约束)Bound Variable and Free Variable (约束变量和自由变量)Example 18 (page 38) (a) x Q(x, y) xbound variable yfree variable (b) x ( P(x) / Q(x) ) / x R(x) the scope of bound variable2022/8/28187. Logical equivalences involving quantifiers(1)definition3iff they have the same truth value no matter whic

14、h predicates are substituted into these statements and which domain is used for the variables in these propositional functions.notation: ST(2)Example 19 (p39) show x(P(x)Q(x) and xP(x)xQ(x) are logically equivalent.Solution: see blackboard. x(P(x)Q(x) xP(x)xQ(x) 2022/8/28198. Negations(1) “Every stu

15、dent in the class has taken a course in calculus” x P(x) Here, P(x)”x has taken a course in calculus”The negation is “It is not the case that Every student in the class has taken a course in calculus” or “There is a student in the class who has not taken a course in calculus” x P(x) x P(x) x P(x) so

16、lution: see blackboard2022/8/2820(2) “There is a student in the class who has taken a course in calculus” x Q(x) Here, Q(x)”x has taken a course in calculus”The negation is “It is not the case that there is a student in the class who has taken a course in calculus” or “Every student in the class has

17、 not taken a course in calculus” x Q(x) x Q(x) x Q(x)solution: see blackboard2022/8/2821De Morgans law for quantifiers x P(x) x P(x) x Q(x) x Q(x)2022/8/2822(3) Example 21 (page 41) What is the negations of the statements x (x2x) and x (x2=2) Solution: x (x2x) x (x2x) x (x2x) .(1) x (x2=2) x (x2=2)

18、x (x22) .(2) The truth values of these statements depends on the domain. For (1), use 0.5, 3 and 2, 5 to check For (2), use 0,1 and 1,2 to check2022/8/2823(4) Example 22 (page 41) show that x (P(x)Q(x) and x (P(x) Q(x) are logically equivalent.Solution: see blackboard.2022/8/28249. Translating from

19、English into logical expressionExample 23 (page 42) Express the statement “Every student in this class has studied calculus” in predicates and quantifiers.Solution:C(x)”x has studied calculus” the domainall the students in the class x C(x)2022/8/2825(2) Way 2: the domain all people “For every person

20、 x, if person x is in this class then x has studied calculus.” S(x)person x is in this class C(x)person x has studied calculus x ( S(x)C(x) ) (correct) x ( S(x) / C(x) ) (wrong, why?)2022/8/2826Example 24 (page 42)Express the statements below in predicates and quantifiers. “Some students in this class has visited Mexico” (1) and “Every student in