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

《离散数学03谓词和量词.ppt》由会员分享，可在线阅读，更多相关《离散数学03谓词和量词.ppt（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章 基础：逻辑和证明1.3 谓词和量词11.3.1 引言(命题逻辑的局限 1)l含变量的陈述句不是命题？！含变量的陈述句不是命题？！教室教室 x 正在上课正在上课l命题函数命题函数 P(x)谓词谓词主语主语(x)：变量，谓语：变量，谓语(P)：x 具有的性质具有的性质变量被赋值后，谓词变量被赋值后，谓词 命题命题谓词本身不是命题！谓词本身不是命题！例例 121.3.1 引言(命题逻辑的局限 1)l谓词谓词 P(x)可以有多个变量：可以有多个变量：多元谓词多元谓词例例2,例例3l有有 n 个变量的谓词个变量的谓词记为记为 P(x1,x2,xn)n 元谓词元谓词31.3.1 引言(命题逻辑的局

2、限 1)l程序中的谓词程序中的谓词谓词谓词 P(x)：x0l程序验证中的谓词程序验证中的谓词前置条件前置条件 P(x,y)：x=x0,y=y0后置条件后置条件 Q(x,y)：x=y0,y=x0例例 7temp=xx=yy=temp例例 6if(x0)x=x+141.3.1 引言(命题逻辑的局限 1)l含变量的陈述句：主语含变量的陈述句：主语个体词个体词，谓语，谓语谓词谓词变量变量个体变量个体变量，陈述句，陈述句命题函数命题函数P(x)：x 3l变量赋值后的陈述句变量赋值后的陈述句变量值变量值个体常量个体常量，陈述句，陈述句命题命题P(2)：2 35命题逻辑的局限性 2l三段论三段论每个人都要死

3、每个人都要死张三是人张三是人张三要死张三要死l实际中经常使用的推理方式实际中经常使用的推理方式在命题逻辑系统中应如何表示？在命题逻辑系统中应如何表示？6命题逻辑的局限性 2l命题逻辑符号化命题逻辑符号化每个人都要死每个人都要死张三是人张三是人张三要死张三要死l在符号化后的形式结构中，看不到推理在符号化后的形式结构中，看不到推理pqr7命题逻辑的局限性 2l复合命题复合命题 p q rp(每个人都要死每个人都要死)，q(张三是人张三是人)，r(张三要死张三要死)p、q、r 是是 3 个独立命题个独立命题明显地，明显地，3 句话之间存在关联句话之间存在关联进一步，是进一步，是 3 句话的内部成分之

4、间有关联句话的内部成分之间有关联命题逻辑无法表示出这些内部成分及其关系！命题逻辑无法表示出这些内部成分及其关系！8命题逻辑的局限性l因为：命题逻辑中原子命题是不可分的因为：命题逻辑中原子命题是不可分的现在需要分解，才能找出相互之间的关系现在需要分解，才能找出相互之间的关系l引入命题函数引入命题函数(个体词谓词个体词谓词)如如 P(x)：x 是人，是人，Q(x)：x 要死要死x张三张三 P(张三张三)：张三是人，：张三是人，Q(张三张三)：张三要死：张三要死“每个人都要死每个人都要死”如何表示？如何表示？9命题逻辑的局限性l命题函数：展现出语句的内部结构命题函数：展现出语句的内部结构P(x)：x

5、 是人，是人，Q(x)：x 要死要死P(张三张三)：张三是人，：张三是人，Q(张三张三)：张三要死：张三要死l“每个人都要死每个人都要死”？与上述两个命题函数之间的关联？与上述两个命题函数之间的关联？如果是人，那么要死：如果是人，那么要死：P(x)Q(x)“每个人每个人”呢？呢？101.3.3 量词(quantifier)lEx.以下公式中以下公式中 x 属于整数属于整数(Z)(x+1)2=x2+2x+1任意整数代入均正确：任意整数代入均正确：x 的的取值范围取值范围=Zx+1=5只有只有 1 个整数代入才正确：个整数代入才正确：x 的的取值范围取值范围=4 0 x+13，则，则3y，G(x,

6、y)：xy231.3.10 翻译语句l王强是大学生李华也是大学生王强是大学生李华也是大学生论域论域所有大学生所有大学生令令F(x)：x是大学生是大学生令令a：王强，：王强，b：李华：李华F(a)F(b)241.3.10 翻译语句l中国代表团访问朝鲜中国代表团访问朝鲜论域所有国家论域所有国家F(x,y)：x 访问访问 ya：中国代表团，：中国代表团，b：朝鲜：朝鲜F(a,b)251.3.10 翻译语句l这座大楼建成了这座大楼建成了论域所有楼宇论域所有楼宇F(x)：x建成了建成了G(x)：x是大的是大的H(x)：x是楼是楼a：这个：这个F(a)G(a)H(a)261.3.10 翻译语句l这个人正在

7、看那本红皮面的书这个人正在看那本红皮面的书论域全总论域论域全总论域F(x,y)：x正在看正在看yG(x)：x是人是人H(y)：y是红皮面的是红皮面的U(y)：y是书是书a：这个，：这个，b：那本：那本F(a,b)G(a)H(b)U(b)271.3.10 翻译语句l实例：将下面命题符号化实例：将下面命题符号化1.论域：人类集合论域：人类集合人都爱美人都爱美有人用左手写字有人用左手写字2.论域：全总论域论域：全总论域人都爱美人都爱美有人用左手写字有人用左手写字281.3.10 翻译语句l论域：人类集合论域：人类集合人都爱美：人都爱美：xG(x)G(x)：x爱美爱美有人用左手写字：有人用左手写字：x

8、G(x)G(x)：x用左手写字用左手写字29解答l论域：全总论域论域：全总论域(个体变量可以是任意事物个体变量可以是任意事物)人都爱美人都爱美 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 左手写字左手写字30三段论l3 个命题组成的推理链个命题组成的推理链前前2个命题：前提个命题：前提(premises)最后最后1个命题：结论个命题：结论(conclusion)3个命题整体：论证个命题整体：论证(arg

9、ument)l例例26、例、例27为什么这样的推理是有效的为什么这样的推理是有效的?31补充：系统规范l所有大于所有大于1MB的邮件将被压缩的邮件将被压缩l如果有一个用户被激活，至少要有一个如果有一个用户被激活，至少要有一个可用网络连接可用网络连接32补充：系统规范l所有大于所有大于1MB的邮件将被压缩的邮件将被压缩论域论域=所有邮件所有邮件 S(x)：x大于大于1MBC(x)：x被压缩被压缩 x(S(x)C(x)33补充：系统规范l如果有一个用户被激活，至少要有一个如果有一个用户被激活，至少要有一个可用网络连接可用网络连接论域论域所有用户所有用户所有网络连接所有网络连接A(u)：用户：用户u

10、被激活被激活S(i)：网络连接：网络连接i可用可用 u A(u)i S(i)341.4 嵌套量词(quantifier)l出现在其他量词作用域内的量词出现在其他量词作用域内的量词给出表达式中的量词、谓词含义给出表达式中的量词、谓词含义整理含义，争取用简单句子表示整理含义，争取用简单句子表示l嵌套量词嵌套量词多重循环多重循环例例 1、2351.4.2 量词的顺序l当不同类型量词交叉嵌套时，顺序很重要当不同类型量词交叉嵌套时，顺序很重要、交叉嵌套交叉嵌套l两个变量的嵌套顺序两个变量的嵌套顺序表表1-24(注意：注意：与与 不能随意交换不能随意交换)例例 3,4,5361.4.2 量词的顺序l练习：

11、设论域为实数域，将下面命题符号化练习：设论域为实数域，将下面命题符号化对每一个数对每一个数x，都存在一个数，都存在一个数y，使得，使得xy x yL(x,y)，L(x,y)：xy存在一个数存在一个数x，使得对每一个数，使得对每一个数y，都有，都有xy x yL(x，y)，L(x，y)：xy37翻译语句为逻辑表达式(1.4.3,1.4.5)l数学语句数学语句谓词逻辑表达式谓词逻辑表达式例例 6、7、8量词隐含在语句中量词隐含在语句中l日常语句日常语句谓词逻辑表达式谓词逻辑表达式例例 11、12、13论域的范围决定量词的使用论域的范围决定量词的使用38翻译逻辑表达式为语句(1.4.4)l谓词逻辑表达式谓词逻辑表达式日常语句日常语句例例 9、10注意：尽量简化语句注意：尽量简化语句391.4.6 否定嵌套量词l连续地应用否定连续地应用否定量词前没有否定词量词前没有否定词例例14、15、1640作业3lP30 9 a)c)e)、14 a)b)c)lP36 3 a)b)c)、5 a)b)c)d)e)41