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

《离散数学03谓词和量词.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章基础：逻辑和证明1.3谓词和量词11.3.1引言(命题逻辑的局限1)含变量的陈述句不是命题？！教室x正在上课命题函数P(x)≡谓词主语(x)：变量，谓语(P)：x具有的性质变量被赋值后，谓词命题谓词本身不是命题！！！例121.3.1引言(命题逻辑的局限1)谓词P(x)可以有多个变量：多元谓词例2,例3有n个变量的谓词记为P(x1,x2,…,xn)n元谓词31.3.1引言(命题逻辑的局限1)程序中的谓词谓词P(x)：x＞0程序验证中的谓词前置条件P(x,y)：{x=x0,y=y0}后置条件Q(x,y)：{x=

2、y0,y=x0}例7temp=xx=yy=temp例6if(x＞0)x=x+141.3.1引言(命题逻辑的局限1)含变量的陈述句：主语个体词，谓语谓词变量个体变量，陈述句命题函数P(x)：x＞3变量赋值后的陈述句变量值个体常量，陈述句命题P(2)：2＞35命题逻辑的局限性2三段论每个人都要死张三是人张三要死实际中经常使用的推理方式在命题逻辑系统中应如何表示？6命题逻辑的局限性2命题逻辑符号化每个人都要死张三是人张三要死在符号化后的形式结构中，看不到推理pqr7命题逻辑的局限性2复合命题pqrp(每个

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

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

5、ifier)量词(quantifier)表示个体变量取值范围的(特殊)符号量化(quanification)将个体变量的取值范围进行符号化131.3.3量词(quantifier)全称量词(universalquantifier)x：论域中“所有的”x全称量化(universalquanification)xP(x)：对论域中“所有的”x，P(x)都为真例：x((x+1)2=x2+2x+1)“每个人都要死”如何表示？141.3.3量词(quantifier)P(x)：x是人，Q(x)：x要死P(张三)：张三是

6、人，Q(张三)：张三要死“每个人都要死”？如果是人，那么要死对每个x：如果x是人，那么x要死P(x)Q(x)x(P(x)Q(x))151.3.3量词(quantifier)存在量词(existentialquantification)x：论域中存在一个x存在量化(existentialquantification)xP(x)：论域中存在一个x，使P(x)为真例：x(x+1=5)161.3.7绑定变量绑定变量取值范围被量词绑定(binding)作用域(scope)量词的作用范围注意！量词优先级高于逻辑运算

7、符自由(free)变量？171.3.9量词的否定表1-23(量词的否定定义)否定入内、量词反转注意！只在量词作用域内有效181.3.9量词的否定练习：将下面命题符号化没有不呼吸的人不是所有的人都喜欢吃糖19练习没有不呼吸的人约定：论域＝{所有事物}F(x):x是人,G(x):x呼吸x(F(x)G(x))x(F(x)G(x))为什么？20练习不是所有的人都喜欢吃糖论域＝全总论域F(x):x是人,G(x):x喜欢吃糖x(F(x)G(x))x(F(x)G(x))211.3.10翻译语句用谓词将命

8、题符号化墨西哥位于南美洲若是无理数，则是有理数如果2>3，则3<422解答在谓词逻辑中：F(a)：论域＝{所有国家}a：墨西哥，F(x)：x位于南美洲F()G()：论域＝{实数}F(x)：x是无理数，G(x)：x是有理数F(2,3)G(3,4)：论域＝{整数}F(x,y)：x>y，G(x,y)：x