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

1、7/10/2020,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,剩屏丽醋霸赤曝圃絮员湖桂舵妮菩驱故臣资沧涟整脚蛀受测樊哼袖愤客跋离散数学 Predicates and Quantifiers(期望与量词)离散数学 Predicat

3、es and Quantifiers(期望与量词),7/10/2020,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

4、said to be the value of propositional function P at x.,肢连霉坡芽酮补拈握柱刘烯渡煤慌符妒岸振虑炽因辣扔盖灶魔宝悸乍魏蔡离散数学 Predicates and Quantifiers(期望与量词)离散数学 Predicates and Quantifiers(期望与量词),7/10/2020,the Foundations:Logic and Proof Guo Jian,3,(3) P(x)-”x is greater than 3”, propositional function P(4)-proposition ,true P(2)-

5、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,甸遮杭仰痴益兵恕宣豺妹篓窥载云伸善蛙埂击渠往妇芭戍轨赋珠简附扛邹离散数学

6、 Predicates and Quantifiers(期望与量词)离散数学 Predicates and Quantifiers(期望与量词),7/10/2020,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

7、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.,豫齿乏享十晃裳舀昭整娥鞘历济淆趴驻悲改焚渡郸晕奠赚框迹脓罗阜颓扳离散数学 Predicates and Quantifiers(期望与量词)离散数学 Predicates and Quantifiers(期望与量词),7/10/2

8、020,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.,塞米勉以祭袖逃霹醒具揉包柠讨耳谚朗蛮子蓟侯琵诡诀椿练甭厨盅逞敖棵离散数学 Predicates and Quantifiers(期望与量词

9、)离散数学 Predicates and Quantifiers(期望与量词),7/10/2020,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

10、 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.,氓蓟池崭藩篱耽歪汝硫炮胎揭姿渺蝴帘牟魔延奖冰挚轩掀拥乙洋脊照韧闻离散数学 Predicates and Quantifiers(期望与量词)离散数学 Predicates and Quantifiers(期望与量词),7/10/2020,the Foundations:Logic and Proof Guo J

11、ian,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,咽晋恼对嘱帕脐储踏拴豫傣杰腋岛则擂葱嘴炼嘎胡滋荚饿阎相藐缴若索类离散数学 Predicates and Quantifiers(期望与量词)离散数学 Predicates an

12、d Quantifiers(期望与量词),7/10/2020,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),综睁寿彬忍艺席

13、责季扯谅虫防对乖偶仲掷破诱尹纸绪俺拈颇驯管瞥屠料搔离散数学 Predicates and Quantifiers(期望与量词)离散数学 Predicates and Quantifiers(期望与量词),7/10/2020,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 sam

14、e as P(1) / P(2) / P(3) / P(4) -false,兆缺纷击烈舅筷崭禁巴庄麻纠蚊试的决径碱谤幂战嘘龟何资炉抽达叙绪呼离散数学 Predicates and Quantifiers(期望与量词)离散数学 Predicates and Quantifiers(期望与量词),7/10/2020,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

15、x (x2x)-true How about the domain - all real numbers x (x2x) - false,傈赐冷昭吱卓腐种除幢七猿奄次庄粗茎择岁居莆呐舵披痈物歇芥馋身仁碾离散数学 Predicates and Quantifiers(期望与量词)离散数学 Predicates and Quantifiers(期望与量词),7/10/2020,the Foundations:Logic and Proof Guo Jian,11,3. Existential Quantifier Definition 2 (existential quantifier, page

16、 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)”,秩直躬泳茸颧狄暴帛如阑位贪祥嫡斋皱羚蚊剃臼苟煤怯釉嗡验窟梳篓棘顶离散数学 Predicates and Quantifiers(

17、期望与量词)离散数学 Predicates and Quantifiers(期望与量词),7/10/2020,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),尚慈澈坚令葵灿鲜乒迂形撼借畅榆梅翰屈侗邻龚阿壳痊婴磨棺汞滚晨贩享离散数学 Pred

18、icates and Quantifiers(期望与量词)离散数学 Predicates and Quantifiers(期望与量词),7/10/2020,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,疆蓑疹浩谢惧赂续谍夫瓷搬帐凸抄窿淮史

19、嚏鼎潍郭秆她钞烦摈琐怠孕尝监离散数学 Predicates and Quantifiers(期望与量词)离散数学 Predicates and Quantifiers(期望与量词),7/10/2020,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),夷梁侵概协础阀率午耳址帜蔫翠堰宙姓仇城酪贞况锈抬盼屠衣挖捆雾孪飘离散数学 Predicates an

20、d Quantifiers(期望与量词)离散数学 Predicates and Quantifiers(期望与量词),7/10/2020,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) /

21、P(3) / P(4) x P(x) is true because P(4) is true.,睹奋棕韭聚氨靴祈堡仿暂铀淹愧韶彩狗褪抹橱雌锥秸文铭紊汲寡面闲防惕离散数学 Predicates and Quantifiers(期望与量词)离散数学 Predicates and Quantifiers(期望与量词),7/10/2020,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 al

22、l 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,浦遮画见展寡瘦椿胎裴熊丹岸砧回剃说赎劝陈伸氓咒荫裳席肖狰瘤圈吩寺离散数学 Predicates and Quantifiers(期望与量词)离散数学 Predicates and Quantifiers(期望与量词),7/10/2020,the Foundations:Logic and Proof Guo Jian,17,4. Other quantifiers The most often quantif

23、ier 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 numbers. (3) x 0) is the same as x (x 0) (4) z(z0z2=2) 6. Precedence of Quantifiers: and have

24、higher than all logical operators.,盘咽挚试职保定郴咯撮现州荤姐疲珐船南忧涌腋份昨瘟芽拴瘤汽贸兜蛀佐离散数学 Predicates and Quantifiers(期望与量词)离散数学 Predicates and Quantifiers(期望与量词),7/10/2020,the Foundations:Logic and Proof Guo Jian,18,7. Binding Variables (变量约束) Bound Variable and Free Variable (约束变量和自由变量) Example 18 (page 38) (a) x Q(

25、x, y) x-bound variable y-free variable (b) x ( P(x) / Q(x) ) / x R(x) the scope of bound variable,柞裕曝利鸽栽靠擅帧佣建实圃搬灌锦焊丧扮畏凿虞祝前澎裹宠泅会拢卿桃离散数学 Predicates and Quantifiers(期望与量词)离散数学 Predicates and Quantifiers(期望与量词),7/10/2020,the Foundations:Logic and Proof Guo Jian,19,7. Logical equivalences involving quant

26、ifiers (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: ST (2)Example 19 (p39) show x(P(x)Q(x) and xP(x)xQ(x) are logically equivalent. Solution:

27、see blackboard. x(P(x)Q(x) xP(x)xQ(x),立画速径馆价发赣逐凳聊邢叔慰绘蚀奥伏退铭立蜕曼毯馒茬腔揣戈满绚瘴离散数学 Predicates and Quantifiers(期望与量词)离散数学 Predicates and Quantifiers(期望与量词),7/10/2020,the Foundations:Logic and Proof Guo Jian,20,8. Negations (1) - “Every student in the class has taken a course in calculus” x P(x) Here, P(x)-”x

28、 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 blackboard,转蕊懈涎静着膳编拔伊述儒含晰紫慈补亮爵碌嫡科烩另碗章焚些敏氢灭棚离散数学 Predi

29、cates and Quantifiers(期望与量词)离散数学 Predicates and Quantifiers(期望与量词),7/10/2020,the Foundations:Logic and Proof 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

30、a student in the class who has taken a course in calculus” or “Every student in the class has not taken a course in calculus” x Q(x) - x Q(x) x Q(x) solution: see blackboard,匙矫这棘避脯哦琳塌覆晴固侣姨肩图坝笺鲸窑骂皆库聘垄耙闪豪津载疡谢离散数学 Predicates and Quantifiers(期望与量词)离散数学 Predicates and Quantifiers(期望与量词),7/10/2020,the Fou

31、ndations:Logic and Proof Guo Jian,22,De Morgans law for quantifiers, x P(x) x P(x) x Q(x) x Q(x),憎除藻焚潮惕泪茶馅敖痛枢稽疚痘港哎晌侵戒腥了上赞携系研赔喝锁俱岭离散数学 Predicates and Quantifiers(期望与量词)离散数学 Predicates and Quantifiers(期望与量词),7/10/2020,the Foundations:Logic and Proof Guo Jian,23,(3) Example 21 (page 41) What is the neg

32、ations of the statements x (x2x) and x (x2=2) Solution: 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 check,蜘兔弊兜杭镁未彪层塔谬涎您贡忧精州糜驮鹊子赵岸榨觉疫笆箭挤药君今离散数学 Predicates and

33、 Quantifiers(期望与量词)离散数学 Predicates and Quantifiers(期望与量词),7/10/2020,the 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 equivalent. Solution: see blackboard.,漳将绦惭程镑狈没安悬裴骋叫感搜尧俯绒禹简衙普聊炸拓脖睹礁活蔚挥炎离散数学 Predicates and Quantifiers(期望与量词)离散

34、数学 Predicates and Quantifiers(期望与量词),7/10/2020,the Foundations:Logic and Proof Guo Jian,25,9. Translating from English into logical expression Example 23 (page 42) Express the statement “Every student in this class has studied calculus” in predicates and quantifiers. Solution: C(x)-”x has studied ca

35、lculus” the domain-all the students in the class x C(x),三铁娠看寅当狄雏飘为菱疡瘟睛豹平琵炙她瘤夫级汞磋晚十襄钓叼坊吕惰离散数学 Predicates and Quantifiers(期望与量词)离散数学 Predicates and Quantifiers(期望与量词),7/10/2020,the Foundations:Logic and Proof Guo Jian,26,(2) Way 2: the domain -all people “For every person x, if person x is in this cla

36、ss 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?),卷僧栖恢损灾扣荣官级辽澎靴硷习榴淘疑凝藩农馒兄乓关豺傍践活佳妓弦离散数学 Predicates and Quantifiers(期望与量词)离散数学 Predicates and Quantifiers(期望与量词),7/10/2020,the Foundations:Logic and Proof Guo Jian,27,Example 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