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

上传人:本田雅阁 文档编号:2071763 上传时间:2019-02-10 格式:PPT 页数:41 大小:242.01KB
返回 下载 相关 举报
离散数学03谓词和量词.ppt_第1页
第1页 / 共41页
离散数学03谓词和量词.ppt_第2页
第2页 / 共41页
离散数学03谓词和量词.ppt_第3页
第3页 / 共41页
亲,该文档总共41页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

《离散数学03谓词和量词.ppt》由会员分享,可在线阅读,更多相关《离散数学03谓词和量词.ppt(41页珍藏版)》请在三一文库上搜索。

1、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 后置条

2、件 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 句话之间存在关联 进一步,是 3 句话的内部成分之间有关联 命题逻辑无法表示出这些内部成分及其关系!,9,命题逻辑的局限性,因为:命题逻辑中原子命题是不可分的 现在需要分解,才能找出相互之间的关系 引入命题函数(个体词谓词) 如 P(x):x 是人,Q(x):x 要死 x张三 P(张三):张三是人,Q(张三):张三要死 “每个人都要死” 如何表示?,10,命题逻辑的局限性,命题函数:展现出语句的内部结构 P(x):x 是人,Q(x):x 要死 P(张三):张三是人,Q(张三):张三要死 “每个人都要死”? 与上述两个命题函数之间的关联? 如果是人,那么要死:P(x)

4、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) 表示个体变量取值范围的(特殊)符号 量化(quanificatio

5、n) 将个体变量的取值范围进行符号化,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(

6、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

7、 量词的否定,练习:将下面命题符号化 没有不呼吸的人 不是所有的人都喜欢吃糖,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(

8、):论域实数 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 翻译语句,

9、这个人正在看那本红皮面的书 论域全总论域 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

10、(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

11、(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,

12、都存在一个数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),

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 其他


经营许可证编号:宁ICP备18001539号-1