离散数学03谓词和量词.ppt

1,第1章 基础：逻辑和证明,1.3 谓词和量词,2,1.3.1 引言(命题逻辑的局限 1),含变量的陈述句不是命题？！ 教室 x 正在上课 命题函数 P(x)谓词 主语(x)：变量，谓语(P)：x 具有的性质 变量被赋值后，谓词 命题 谓词本身不是命题！,例 1,3,1.3.1 引言(命题逻辑的局限 1),谓词 P(x) 可以有多个变量：多元谓词 例2, 例3 有 n 个变量的谓词 记为 P(x1, x2, , xn),n 元谓词,4,1.3.1 引言(命题逻辑的局限 1),程序中的谓词 谓词 P(x)：x0 程序验证中的谓词 前置条件 P(x, y)： x = x0, y = y0 后置条件 Q(x, y)： x = y0, y = x0,5,1.3.1 引言(命题逻辑的局限 1),含变量的陈述句：主语个体词，谓语谓词 变量个体变量，陈述句命题函数 P(x)：x 3 变量赋值后的陈述句 变量值个体常量，陈述句命题 P(2)：2 3,6,命题逻辑的局限性 2,三段论 每个人都要死 张三是人 张三要死 实际中经常使用的推理方式 在命题逻辑系统中应如何表示？,7,命题逻辑的局限性 2,命题逻辑符号化 每个人都要死 张三是人 张三要死 在符号化后的形式结构中，看不到推理,8,命题逻辑的局限性 2,复合命题 p q r p(每个人都要死)，q(张三是人)，r(张三要死) p、q、r 是 3 个独立命题 明显地，3 句话之间存在关联 进一步，是 3 句话的内部成分之间有关联 命题逻辑无法表示出这些内部成分及其关系！,9,命题逻辑的局限性,因为：命题逻辑中原子命题是不可分的 现在需要分解，才能找出相互之间的关系 引入命题函数(个体词谓词) 如 P(x)：x 是人，Q(x)：x 要死 x张三 P(张三)：张三是人，Q(张三)：张三要死 “每个人都要死” 如何表示？,10,命题逻辑的局限性,命题函数：展现出语句的内部结构 P(x)：x 是人，Q(x)：x 要死 P(张三)：张三是人，Q(张三)：张三要死 “每个人都要死”？ 与上述两个命题函数之间的关联？ 如果是人，那么要死：P(x)Q(x),“每个人”呢？,11,1.3.3 量词(quantifier),Ex. 以下公式中 x 属于整数(Z) (x+1)2=x2+2x+1 任意整数代入均正确：x 的取值范围=Z x+1=5 只有 1 个整数代入才正确：x 的取值范围= 4 0x+15 有 4 个整数代入会正确：x 的取值范围=0,1,2,3,12,1.3.3 量词(quantifier),论域(domain)：个体变量的取值范围 有限论域、无限论域 全总论域：包含世界的万事万物,13,1.3.3 量词(quantifier),量词(quantifier) 表示个体变量取值范围的(特殊)符号 量化(quanification) 将个体变量的取值范围进行符号化,14,1.3.3 量词(quantifier),全称量词(universal quantifier) x：论域中“所有的”x 全称量化(universal quanification) x P(x)：对论域中“所有的”x，P(x) 都为真 例：x ( (x+1)2=x2+2x+1 ),“每个人都要死” 如何表示？,15,1.3.3 量词(quantifier),P(x)：x 是人，Q(x)：x 要死 P(张三)：张三是人，Q(张三)：张三要死 “每个人都要死”？ 如果是人，那么要死 对每个 x：如果 x 是人，那么 x 要死,P(x)Q(x),x ( P(x)Q(x) ),16,1.3.3 量词(quantifier),存在量词(existential quantification) x：论域中存在一个 x 存在量化(existential quantification) x P(x)：论域中存在一个 x，使 P(x) 为真 例：x ( x+1=5 ),17,1.3.7 绑定变量,绑定变量 取值范围被量词绑定(binding) 作用域(scope) 量词的作用范围 注意！量词优先级高于逻辑运算符,自由(free)变量？,18,1.3.9 量词的否定,表 1-23(量词的否定定义) 否定入内、量词反转 注意！只在量词作用域内有效,19,1.3.9 量词的否定,练习：将下面命题符号化 没有不呼吸的人 不是所有的人都喜欢吃糖,20,练习,没有不呼吸的人 约定：论域 所有事物 F(x): x是人, G(x): x呼吸 x ( F(x) G(x) ) x ( F(x) G(x) ),为什么？,21,练习,不是所有的人都喜欢吃糖 论域全总论域 F(x): x是人, G(x): x喜欢吃糖 x(F(x)G(x) x(F(x)G(x),22,1.3.10 翻译语句,用谓词将命题符号化 墨西哥位于南美洲 若 是无理数，则 是有理数 如果23，则34,23,解答,在谓词逻辑中： F(a)：论域所有国家 a：墨西哥，F(x)：x位于南美洲 F( )G( )：论域实数 F(x)：x是无理数，G(x)：x是有理数 F(2, 3)G(3, 4)：论域整数 F(x, y)：xy，G(x, y)：xy,24,1.3.10 翻译语句,王强是大学生李华也是大学生 论域所有大学生 令F(x)：x是大学生 令a：王强，b：李华 F(a)F(b),25,1.3.10 翻译语句,中国代表团访问朝鲜 论域所有国家 F(x, y)：x 访问 y a：中国代表团，b：朝鲜 F(a, b),26,1.3.10 翻译语句,这座大楼建成了 论域所有楼宇 F(x)：x建成了 G(x)：x是大的 H(x)：x是楼 a：这个 F(a)G(a)H(a),27,1.3.10 翻译语句,这个人正在看那本红皮面的书 论域全总论域 F(x,y)：x正在看y G(x)：x是人 H(y)：y是红皮面的 U(y)：y是书 a：这个，b：那本 F(a,b)G(a)H(b)U(b),28,1.3.10 翻译语句,实例：将下面命题符号化 论域：人类集合 人都爱美 有人用左手写字 论域：全总论域 人都爱美 有人用左手写字,29,1.3.10 翻译语句,论域：人类集合 人都爱美：xG(x) G(x)：x爱美 有人用左手写字：xG(x) G(x)：x用左手写字,30,解答,论域：全总论域 (个体变量可以是任意事物) 人都爱美 F(x) x ( F(x)G(x) ) 错误的表示！x ( F(x) G(x) ) 有人左手写字 F(x) x ( F(x) G(x) ) 错误的表示！x ( F(x)G(x) ),x 是人，G(x)：x 爱美,x 是人，G(x)：x 左手写字,31,三段论,3 个命题组成的推理链 前2个命题：前提(premises) 最后1个命题：结论(conclusion) 3个命题整体：论证(argument) 例26、例27 为什么这样的推理是有效的?,32,补充：系统规范,所有大于1MB的邮件将被压缩 如果有一个用户被激活，至少要有一个可用网络连接,33,补充：系统规范,所有大于1MB的邮件将被压缩 论域 = 所有邮件 S(x)：x大于1MB C(x)：x被压缩 x(S(x)C(x),34,补充：系统规范,如果有一个用户被激活，至少要有一个可用网络连接 论域所有用户×所有网络连接 A(u)：用户u被激活 S(i)：网络连接i可用 u A(u)i S(i),35,1.4 嵌套量词(quantifier),出现在其他量词作用域内的量词 给出表达式中的量词、谓词含义 整理含义，争取用简单句子表示 嵌套量词多重循环,例 1、2,36,1.4.2 量词的顺序,当不同类型量词交叉嵌套时，顺序很重要 、 交叉嵌套 两个变量的嵌套顺序 表1-24 (注意：与不能随意交换),例 3, 4, 5,37,1.4.2 量词的顺序,练习：设论域为实数域，将下面命题符号化 对每一个数x，都存在一个数y，使得xy xyL(x,y)，L(x,y)：xy 存在一个数x，使得对每一个数y，都有xy xyL(x，y)，L(x，y)：xy,38,翻译语句为逻辑表达式(1.4.3, 1.4.5),数学语句谓词逻辑表达式 例 6、7、8 量词隐含在语句中 日常语句谓词逻辑表达式 例 11、12、13 论域的范围决定量词的使用,39,翻译逻辑表达式为语句(1.4.4),谓词逻辑表达式日常语句 例 9、10 注意：尽量简化语句,40,1.4.6 否定嵌套量词,连续地应用否定 量词前没有否定词 例14、15、16,41,作业3,P30 9 a) c) e)、14 a) b) c) P36 3 a) b) c)、5 a) b) c) d) e),