离散数学第三章谓词演算基础-谓词与个体.ppt

《离散数学第三章谓词演算基础-谓词与个体.ppt》由会员分享，可在线阅读，更多相关《离散数学第三章谓词演算基础-谓词与个体.ppt（32页珍藏版）》请在三一办公上搜索。

1、目录（数理逻辑）,第一章 命题演算基础（6学时）第二章 命题演算的推理理论（4学时）第三章 谓词演算基础（5学时）第四章 谓词演算的推理理论（5学时）第五章 递归函数论（4学时）,第三章 谓词演算基础,在命题演算中，把不可剖开或分解为更简单命题的原子命题作为基本单元。将对原子命题内部结构进一步剖析，分解为 个体 谓词,苏格拉底三段论,P：凡人要死 Q：苏格拉底是人 R：苏格拉底要死此三段论表示为:(PQ)R此三段论是正确的，但PQR却不是重言式，这就是命题逻辑的局限性。,三段论,P:计算机学院学生学习离散数学Q:王明是计算机学院学生R:王明学习离散数学(PQ)R该推理是正确的，但PQR却不是重

2、言式，,第三章 谓词演算基础,3.1 谓词与个体 3.1.1 个体 3.1.2 谓词3.2 函数与量词3.3 自由变元和约束变元 3.4 永真性和可满足性3.5 唯一性量词与摹状词,个体,(1)个体：个体是指具有独立意义、独立存在的东西。也称为常个体或实体。用a、b、c等表示。(2)个体域：由个体组成的集合称为个体域。个体域常用I、J、K等表示。(3)全总个体域：所有个体不管是何种类型的个体综合在一起组成的个体域称为全总个体域。用U表示。,个体变元、项,(4)个体变元：以个体域I为变域的变元称为个体域I上的个体变元。用x、y、z、等表示。(5)项：包括实体、变量符号和函数符号等,是构成原子公式

3、的一部分(原子公式的定义详见第28页第-5行),特定个体a、泛指个体x、个体的函数 f(x),第三章 谓词演算基础,3.1 谓词与个体 3.1.1 个体 3.1.2 谓词3.2 函数与量词3.3 自由变元和约束变元 3.4 永真性和可满足性3.5 唯一性量词与摹状词,一、有关概念,把语句中表示 个体性质和关系的语言成分（通常是谓语）称为谓词（predicate）。,谓词是指个体所具有的性质或若干个体之间的关系。,例(谓词：表示个体性质或个体间关系),“苏格拉底是人”中的“是人”。“苏格拉底是要死的”中的“是要死的”。“张三生于北京”中的“生于”。“3+2=5”中的“+=”。,谓词的元数,谓词所

4、携空位的数目谓词携有可以放置个体的空位，当空位上填入个体后便产生一个关于这些个体的语句，它断言个体具有谓词所表示的性质和关系。,例(一元谓词、二元谓词、三元谓词),“苏格拉底是人”中的“是人”。“苏格拉底是要死的”中的“是要死的”。“张三生于北京”中的“生于”。“3+2=5”中的“+=”。,谓词命名式:携有空位的大写字母,M（）表示“是人”。D（）表示“是要死的”。B（，）表示“生于”。ADD（，）表示“+=”。可读性差！可用变元来代替空位。因此，上述谓词可以表示为：M(x)，D(x)，B(x,y)，ADD(x,y,z),谓词填式,谓词的空位上填入个体后所产生的语句。例如：M（苏格拉底）表示“

5、苏格拉底是人”。D（苏格拉底）表示“苏格拉底是要死的”。B（张三，北京）表示“张三生于北京”。ADD（3，2，5）表示“3+2=5”。,单个谓词不构成完整的意思，只有当谓词填以个体后才能够构成完整的意义。,谓词命名式与谓词填式,同形，但它们表示不同的意义。例如，M(x)作为命名式时，它只是M()的另一写法，与x无关，改为M(y)意义照旧；M(x)作为填式时，它表示“x是人”，改为M(y)后其意义“y是人。,谓词：从个体域到真值集的映射,当谓词填式中所填个体都是常元时，它是一个命题，因而有确定的真值。例如：M（苏格拉底）为真，M（孔子）为真，M（孙悟空）为假，M（北京）为假。,一元谓词的数目与个

6、体域的大小有关。,谓词：从个体域到真值集的映射,例如：D（苏格拉底）为真，D（孙悟空）为假，B（苏格拉底，希腊）为真 B（苏格拉底，中国）为假，ADD（1，1，2）为真，ADD（3，2，5）为真，ADD（3，2，6）为假。,谓词变元,以谓词组成的集合为变域的变元称为谓词变元。已经描述过:大写字母A、B、C等表示特定的谓词，小写字母a、b、c表示特定的个体或实体。现在约定用大写字母X、Y、Z等表示谓词变元，小写字母x、y、z等表示个体变元。,二、谓词语句的符号化,动词、系动词、形容词、集合名词均可以表达成谓词。,例1 我送他这本书。,解：令 A(e1，e2，e3)表示“e1送e3给e2”；B(e

7、)表示“e为书”；a表示“我”；b表示“他”；c表示“这”；则原句译为：A(a，b，c)B(c),例2 这只大红书柜摆满了那些古书。,解：令,A(e1，e2)表示“e1摆满了e2；B(e)表示“e为大的”；C(e)表示“e为红的”；D(e)表示“e为书柜”；E(e)表示“e为古书”；a表示“这只”；b表示“那些”；则原句译为：A(a，b)B(a)C(a)D(a)E(b),例 Shakespeare wrote“Hamlet”。,解：令 WRITE(x,y)表示x写了y。则原语句可以符号化为：WRITE(Shakespeare，Hamlet)此表达式表示常谓词WRITE与两个实体 Shakesp

8、eare和Hamlet之间的关系。,特定的谓词,基于个体变元上的谓词,进一步考察：WRITE(x，y)其中x,y为变量符号项。此式表示x和y的关系是WRITE，即作者x写了书y。此时x可在个体域I(表示作者的集合)上变化；y可在个体域J(表示书名的集合)上变化。,谓词变元,一般地，考察 A(x，y)其中x,y为变量符号项、A为谓词变元。此式表示x和y具有关系A。注意：x，y，A分别在三个域上变化。,谓词变元的定义,以某个个体域I为定义域、以真假为值域的谓词称作个体域I上的谓词。以某个个体域I上的谓词为变域的变元称作个体域I上的谓词变元。,个体域a上的一元谓词,单个体的一元谓词A(e)如下图所示

9、:,e A1 A2 a T F,一元谓词共有两个。,个体域a，b上的一元谓词,两个个体的一元谓词A(e)如下图所示:,e A1 A2 A3 A4a T F T Fb T T F F,两个个体的一元谓词共有22=4个。,个体域a，b，c上的一元谓词,三个个体的一元谓词A(e)如下图所示:,e A1 A2 A3 A4 A5 A6 A7 A8a T F T T F T F F b T T F T F F T Fc T T T F T F F F,三个个体的一元谓词共有23=8个。,个体域a上的二元谓词,单个体的二元谓词A(e1，e2)如下图所示:,e1 e2 A1 A2 a a T F,单个体的二元

10、谓词有2个。,个体域a，b上的二元谓词,两个个体的二元谓词A(e1，e2)如下图所示:,两个个体的二元谓词A(e1，e2)共有24=16个。,e1 e2 A0 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15,a a T F T T T F F F T T T T F F F F a b T T F T T F T T F F T F T F F F b a T T T F T T F T F T F F F T F F b b T T T T F T T F T F F F F F T F,谓词数目,不难验证，h个个体组成的个体域I上的一元谓词有2h个，二元谓词共有2h2个，m元谓词共有2hm个。,第三章 谓词演算基础,3.1 谓词与个体 3.1.1 个体 3.1.2 谓词3.2 函数与量词3.3 自由变元和约束变元 3.4 永真性和可满足性3.5 唯一性量词与摹状词,