资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,the Foundations:Logic and Proof Guo Jian,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,the Foundations:Logic and Proof Guo Jian,*,2024/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,2024/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.,2024/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,2024/10/3,the Foundations:Logic and Proof Guo Jian,4,(5)In general,A statement of the form P(x,1,x,2,x,n,)is the value of the,propositional function,P at the,n-tuple,(x,1,x,2,x,n,),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.,2024/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.,2024/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.,2024/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)-,”,x,0,”,.,the domain-integers,Show x,P(x,)is false,Solution:giving a counterexample.X=0,(6)Further explanation,the domain-finite set x,1,x,2,x,n,x,P(x,)is the same as,P(x,1,)/P(x,2,)/./,P(x,n,),2024/10/3,the Foundations:Logic and Proof Guo Jian,9,(7)Example 11(page 35),P(x,)-,”,x,2,3,”,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),2024/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,2024/10/3,the Foundations:Logic and Proof Guo Jian,14,(4),If the domain is a finite set,i.e.,x,1,x,2,x,n,then,x,P(x,)is the same as,P(x,1,)/P(x,2,)/,/,P(x,n,),2024/10/3,the Foundations:Logic and Proof Guo Jian,15,(5)Example 16(page 37),P(x)-,”,x,2,10,”,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.,2024/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,2024/10/3,the Foundations:Logic and Proof Guo Jian,17,4.,Other quantifiers,The most often quantifier is,uniqueness quantifier,-denoted by!,xP(x,),or,1,x,P(x,),5.Quantifiers with restricted domains,(1)There is a condition after quantifier.,(2)Example x 0),y,0(y,3,0)and,z0(z,2,=2),if the domain is the real numbers.,(3)x 0)is the same as x(x 0),(4),z(z,0,z,2,=2),6.Precedence of Quantifiers:and have higher than all logical operators.,2024/10/3,the Foundations:Logic and Proof Guo Jian,18,7.,Binding Variables(,变量约束,),Bound Variable and Free Variable,(,约束变量和自由变量,),Example 18(page 38),(a),x,Q(x,y),x-bound variable,y-free variable,(b),x(,P(x,)/,Q(x,),/,x,R(x,),the scope of bound variable,2024/10/3,the Foundations:Logic and Proof Guo Jian,19,7.,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 variables in these propositional functions.,-notation:S,T,(2)Exa
展开阅读全文