《离散数学 第2版 教学课件 ppt 作者 王元元 离散第13讲 谓词演算基本概念》由会员分享，可在线阅读，更多相关《离散数学 第2版 教学课件 ppt 作者 王元元 离散第13讲 谓词演算基本概念（32页珍藏版）》请在金锄头文库上搜索。
1、,计算机专业基础课程,授课人：王元元 单位：计算机理论教研室,指挥自动化学院计算机系,PowerPoint Template_Sub,谓词演算基本概念,谓词演算永真式,谓词演算基本概念,离散数学第13讲,Page 48 to 54,-4-,第13讲 谓词演算基本概念,内容提要,谓词演算基本概念 个体、个体域 谓词 全称量词、存在量词 约束变元、自由变元 谓词公式 自然语句的形式化,-5-,第13讲 谓词演算基本概念,命题演算的局限,所有人都是要死的，苏格拉底是人，那么苏格拉底也是要死的。 p：所有人都是要死的 q：苏格拉底是人 r：苏格拉底是要死的 pqr：pqr为永真式吗？,命题推理能力的局
2、限性,-6-,第13讲 谓词演算基本概念,命题演算的局限,p：所有人都是要死的 q：苏格拉底是人 r：苏格拉底是要死的,(所有人都)是要死的 (苏格拉底)是人 (苏格拉底)是要死的,1、命题演算将对确定对象进行判断的具有明确真值的陈述句作为一个整体进行分析和处理，忽略了陈述句内部的结构 2、上述句子讨论事物的性质，并涉及所讨论的对象在全体和个体上的联系 性质1：是要死的：所有人都具有“要死的”性质 性质2：是人： 苏格拉底 “是人” 两种主体：苏格拉底是所有人的组成部分，因此也具有“要死的”性质,-7-,第13讲 谓词演算基本概念,示例,2是偶数 3是偶数 p: 2是偶数;q:3是偶数 p、q
3、是两个独立的原子命题 模式是：（ ）是偶数 O(x)：x是偶数 p: 2是偶数，可以表示成：O（2） q: 3是偶数，可以表示成：O（3）,-8-,第13讲 谓词演算基本概念,示例,6大于4 5大于3 2大于5 三个独立的原子命题，在命题演算中不能再分解 模式是：（ ）大于（ ）,大于是两个数之间的关系 L（x，y）：“x大于y” 6大于4 ，可以表示成：L（6，4） 5大于3 ，可以表示成： L（5，3） 2大于5 ，可以表示成： L（2，5）,-9-,第13讲 谓词演算基本概念,示例,3+2=5 2+4=6 两个独立的原子命题，在命题演算中不能再分解 模式是：（ ）+（ ）=（ ） 刻画的
4、是三个数之间的关系 S（x，y，z）：x + y=z 3+2=5 ，可以表示成： S（3，2，5） 2+4=6 ，可以表示成： S（2，4，6）,-10-,第13讲 谓词演算基本概念,个体与个体域、个体项,出现在空位处的量或变元叫做个体（或客体），它是谓词演算中讨论的对象 不确定的个体称为个体变元（variables），如x，y，z，确定的称为个体常元（常个体）（constants），例如张华，5，3，,-11-,第13讲 谓词演算基本概念,个体与个体域、个体项,讨论对象个体的全体称为个体域（domain of individuals），常用字母D表示。约定任何D都至少含有一个成员 当讨论对象
5、遍及一切客体时，个体域特称为全总域（universe），用字母U表示 表示个体域上个体间运算的运算符与个体常元、变元组成个体项（terms），例如a+b、x2+2、f(x)等,-12-,第13讲 谓词演算基本概念,谓词 （predicate）,刻画个体（或客体）的性质，或个体之间的关系的模式称之为谓词 谓词是由谓语和空位所组成的，一个空位是一元谓词，两个空位是二元谓词，三个空位是三元谓词 为增强可读性，常用变元来代替空位，如H(x)，L（x，y），S（x，y，z）等，这些式子叫做谓词命名式，简称谓词 谓词命名式中的变元仅仅是谓词形式表示的一部分，没有独立意义,-13-,第13讲 谓词演算基本概
6、念,谓词填式,在谓词的空位处填入具体的个体常元或变元后得到一个关于该个体的语句，这时它被称为谓词填式，如M(scorates)，R(x)等 当谓词填式中所填个体都是常元时，得到一个命题，有确定的真值 H(x): x是学生 H（张华）：张华是学生； R(x,y,z): x+y=z R(1,2,3)：“1+2=3”，命题为真 谓词是以个体域或它的一部分为定义域，以0，1为值域的一个函数,-14-,第13讲 谓词演算基本概念,问题,P(x): x2 = 0 P(0)、P(1)、P(2)、P(3)都为真 所有的不超过3的自然数x都有x2 = 0 P(0)P(1)P(2)P(3) 所有的自然数x都有x2
7、 = 0 P(0)P(1)P(2)P(3) ,-15-,第13讲 谓词演算基本概念,问题,P(x): x2 = 6 P(0)、P(1)、P(2)为假，P(3)为真 存在不超过3的自然数x，使x2 = 6 P(0)P(1)P(2)P(3) 存在自然数x，使x2 = 6 P(0)P(1)P(2)P(3) ,-16-,第13讲 谓词演算基本概念,量词,全称量词：个体域中任一个体常元x，都使P(x)为真，记为xP(x),全称量词,指导变元,约束变元,存在量词：在个体域中（至少）有一个体常元x，使P(x)为真，记为xP(x),存在量词,指导变元,约束变元,-17-,第13讲 谓词演算基本概念,全称量词(
8、universal quantifier),所有的人都是要死的 D(x): x是要死的 当x的个体域是人类时 xD(x) 当x的个体域是所有对象的集合(全总域)时 H(x)：x是人 x(H(x)D(x) x(H(x)D(x),-18-,第13讲 谓词演算基本概念,全称量词(universal quantifier),如果x的个体域包含不超过4的正整数，P(x)表示“x2=0)的真值； 如果个体域是复数集合，求x(x2=0)的真值,-19-,第13讲 谓词演算基本概念,存在量词(existential quantifier),有的人不怕死 F(x): x怕死 当x的个体域是人类时 x F(x)
9、当x的个体域是所有对象(全总域)时 H(x)：x是人 x(H(x)F(x) x(H(x)F(x),-20-,第13讲 谓词演算基本概念,存在量词(existential quantifier),如果x的个体域是整数，P(x)表示“x=x+1”，求xP(x)的真值 如果x的个体域是实数集合，求x(x20)的真值； 如果个体域是复数集合，求x(x20)的真值,-21-,第13讲 谓词演算基本概念,谓词公式（predicate formula）,定义：以下条款规定的符号串称谓词公式，简称公式 (1)谓词填充式是公式，命题常元是公式(看作零元谓词)； (2)如果A，B是公式，x为任一变元，那么(A)，
10、(AB)，(xA)，(x A) 当使用五个联结词时还有(AB)，(AB)，(AB)都是公式； (3)只有有限步使用(1)，(2)条款所形成的符号串是公式 括号省略原则同命题公式： 省掉最外面的括号 联结词的结合能力强弱为、(、)、 结合能力平等的联结词从左到右运算,-22-,第13讲 谓词演算基本概念,谓词公式,x(P(x) Q(x) xS(x) T(x),对x(P(x) Q(x) ： 全称量词：；指导变元：x，作用域：P(x)Q(x)，其中x为约束变元 对确定的个体域和谓词P、Q， x(P(x) Q(x)是一个命题：个体域中的任一对象，都具有谓词P和Q定义的性质 (P(x1) Q(x1) (
11、P(x2) Q(x2) (P(xn) Q(xn),对xS(x) ： 存在量词： ；指导变元：x，作用域：S(x) ，其中x为约束变元 对确定的个体域和谓词S， xS(x)是一个命题：个体域中有一个对象，具有谓词S定义的性质 S(x1) S(x2) S(xn),对T(x) ：x没有任何量词约束，且x是个体变元，称为自由变元,1、给定了个体域和谓词的意义，那么谓词公式的真值只取决于自由变元的取值，与约束变元无关。 2、给谓词公式中每一自由变元都指定具体的个体时，谓词公式成为关于个体域的一个命题，可判定其真值,-23-,第13讲 谓词演算基本概念,谓词公式的真值,设D为实数域，E(x，y)表示D上的
12、关系“x=y”，L(x，y)表示“x y”，则有,（1）xL(0, x2+1) 表示：所有的实数x，满足0x2+1 真值：真,（2） xE(x2-2x-1,0) 表示：有一个实数x，满足x2-2x-1=0 真值：真,（3） xE(x2+x+1,0) 表示：有一个实数x，满足x2+x+1=0 真值：假,（4） xE(x2,y) 表示：有一个实数x，满足x2=y 真值：当y大于等于0时，为真；当y小于0时，为假；,yL(0, y2+1),xE(y2-2y-1,0),yE(y2+x+1,0),yE(y2-2y-1,0),yE(y2+y+1,0),yE(y2,y),zE(z2,y),-24-,第13讲
13、 谓词演算基本概念,否定,每个同学都学过高等数学 P(x)：x学过高等数学；xP(x),不是每个同学都学过高等数学 xP(x),有的同学没有学过高等数学 x P(x),有的同学学过高等数学 P(x)：x学过高等数学； xP(x),并没有同学学过高等数学 xP(x),所有同学都没有学过高等数学 xP(x),-25-,第13讲 谓词演算基本概念,谓词公式的表述,P(x)：x每天花2小时学习英语，x的个体域是学生的集合 xP(x) xP(x) xP(x) xP(x) xP(x) xP(x),有的学生每天花2小时学习英语,有的学生每天不花2小时学习英语,所有学生每天都花2小时学习英语,所有学生每天都不
14、花2小时学习英语,没有学生每天花2小时学习英语,不是所有的学生每天花2小时学习英语,-26-,第13讲 谓词演算基本概念,谓词的自然语句形式化,没有不犯错误的人 F(x)：x犯错误 M(x)：x是人 x (M(x)F(x) x (M(x)F(x) 凡是实数，不是大于0，就是等于0或小于0 R(x)：x是实数 x (R(x)x0x=0x0) 尽管有人聪明，但未必一切人都聪明 S(x)：x聪明 M(x)：x是人 x (M(x) S(x) x (M(x) S(x),-27-,第13讲 谓词演算基本概念,谓词的自然语句形式化,所有步行的、骑马的或乘车的人，凡是口渴的，都喝泉水 M(x)：x是人；P(x
15、)：x步行；Q(x)：x骑马； R(x)：x乘车；T(x)：x口渴；S(x)：x喝泉水 x(M(x)(P(x)Q(x)R(x) (T(x)S(x) 有且仅有一个偶质数 P(x)：x是偶数；Q(x)：x是质数 !x (P(x)Q(x) !也是一个存在量词，其含义是“存在唯一的一个”，用法与存在量词的用法相同，即特性谓词也要作为合取项加入。,-28-,第13讲 谓词演算基本概念,多元谓词的自然语言形式化,对于所有的自然数x，均有 x + 1 x N(x)：x是自然数 M(x,y)：x+y=x x (N(x) M(x,1) 我为人人，人人为我 M(x)：x是人 H(x,y)：x为(帮助)y x (M(x)H(我,y) x (M(x)H(x,我),-29-,第13讲 谓词演算基本概念,量词的嵌套,设D为实数域，则有 xy(x+y=y+x) xy(x+y=x*y) xy(x+y=0) yx(x+y=0) yx(x*y=0) xy(x*y=0),任意两个实数x和y，有x+y=y+x,存在两个实数x和y，使x+y=y+x,对任一实数x，存在一个实数y，使x+y=0,存在一个实数x，对任一实数y，使x+y=0,存在一个实数x，对任一实数y，使x*y=0,对任一实数x，存在一个实数y，使x*y=0,-30-,
