《离散数学 Predicates and Quantifiers(期望与量词).ppt》由会员分享，可在线阅读，更多相关《离散数学 Predicates and Quantifiers(期望与量词).ppt（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2022/12/29the Foundations:Logic and Proof Guo Jian 11.3 Predicates and QuantifierslIntroduction (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
2、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,quantifiers2022/12/29the Foundations:Logic and Proof Guo Jian 21.predicate (1)Consider the statement “x is
3、 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.2022/12/29the Foundations:Logic and Proof Guo Jian 3(3)P(x)-”x is greater than
4、 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)
5、-true2022/12/29the 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 outp
6、ut when given valid input.Precondition-valid inputPostcondition-the conditions that output should satisfy.2022/12/29the Foundations:Logic and Proof Guo Jian 5(7)quantifiers(量词)-a range of elementsuniversal quantifiers(全称量词)existential quantifiers(存在量词)predicate calculus(谓词演算)-the area of logic that
7、deals with predicate and quantifiers.2022/12/29the Foundations:Logic and Proof Guo Jian 62.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
8、 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/12/29the 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)-”x0”.
9、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/12/29the Foundations:Logic and Proof Guo Jian 9(7)Example 11(page 35)P(x)-”x23”the domain -all real numbers Consider x P(x)Sol
10、ution:x P(x)is true Why?(x can be 3.5,4,.,which makes is P(x)is true)2022/12/29the 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 false2022/12/29the Foundations:Logic
11、 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)2022/12/29the 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,
12、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.2022/12/29the Foundations:Logic and Proof Guo Jian 16(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
13、 true 2022/12/29the Foundations:Logic and Proof Guo Jian 174.Other quantifiersThe most often quantifier is uniqueness quantifier-denoted by!xP(x),or 1x 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 num
14、bers.(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/12/29the Foundations:Logic and Proof Guo Jian 187.Binding Variables(变量约束)(1)Bound Variable and Free Variable (约束变量和自由变量)Example 18(page 38)(a)x Q(x,y)x-bound variable y-free varia
15、ble (b)x(P(x)/Q(x)/x R(x)the scope of bound variable2022/12/29the Foundations:Logic and Proof Guo Jian 197.Logical equivalences involving quantifiers(1)definition3-iff they have the same truth value no matter which predicates are substituted into these statements and which domain is used for the var
16、iables 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/12/29the Foundations:Logic and Proof Guo Jian 208.Negations(1)-“Every student in the class has taken a course in calculus”x P(x
17、)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)solution:see blackboard2022/12/29the Foundations:Logic and Pr
18、oof Guo Jian 21(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 not taken a course
19、in calculus”x Q(x)-x Q(x)x Q(x)solution:see blackboard2022/12/29the Foundations:Logic and Proof Guo Jian 22De Morgans law for quantifiers x P(x)x P(x)x Q(x)x Q(x)2022/12/29the Foundations:Logic and Proof Guo Jian 23(3)Example 21(page 41)What is the negations of the statements x(x2x)and x(x2=2)Soluti
20、on:x(x2x)x(x2x)x(x2x).(1)x(x2=2)x(x2=2)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/12/29the Foundations:Logic and Proof Guo Jian 24(4)Example 22(page 41)show that x(P(x)Q(x)and x(P(x)Q(x)are logically equ
21、ivalent.Solution:see blackboard.2022/12/29the Foundations:Logic and Proof Guo Jian 259.Translating from English into logical expressionExample 23(page 42)Express the statement“Every student in this class has studied calculus”in predicates and quantifiers.Solution:(1)C(x)-”x has studied calculus”the
22、domain-all the students in the class x C(x)2022/12/29the Foundations:Logic and Proof Guo Jian 26(2)Way 2:the domain -all people “For every person 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(
23、x)(wrong,why?)2022/12/29the Foundations:Logic and Proof Guo Jian 27Example 24(page 42)Express the statements below in predicates and quantifiers.“Some students in this class has visited Mexico”-(1)and “Every student in this class has visited Canada or Mexico”-(2)2022/12/29the Foundations:Logic and P
24、roof Guo Jian 28“Some students in this class has visited Mexico”Solution:(a)Way 1:M(x)-x has visited Mexico.the domain -all the students in this class x M(x)Way 2:the domain-all people S(x)-”x is a student in this class”x(S(x)/M(x)-correct x(S(x)M(x)-wrong2022/12/29the Foundations:Logic and Proof Gu
25、o Jian 29For“Every student in this class has visited Canada or Mexico”Way 1:C(x)-”x has visited Canada.”M(x)-”x has visited Mexico”the domain -”all the students in this class”x(C(x)/M(x)2022/12/29the Foundations:Logic and Proof Guo Jian 30 Way 2:the domain -”all people”S(x)-”x is a student in this class.”C(x)-”x has visited Canada.”M(x)-”x has visited Mexico”x(S(x)(C(x)/M(x)