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

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

这就是命题逻辑的局限性三段论P: 计算机学院学生学习离散数学计算机学院学生学习离散数学Q: 王明是计算机学院学生王明是计算机学院学生R: 王明学习离散数学王明学习离散数学 (P Q)R该推理是正确的，但该推理是正确的，但P QR却不是重言式，却不是重言式，第三章 谓词演算基础3.1 谓词与个体谓词与个体 3.1.1 个体个体 3.1.2 谓词谓词3.2 函数与量词函数与量词3.3 自由变元和约束变元自由变元和约束变元 3.4 永真性和可满足性永真性和可满足性3.5 唯一性量词与摹状词唯一性量词与摹状词3.1.1 个体个体(1)个体个体：个体是指具有独立意义、独立存在的东西个体是指具有独立意义、独立存在的东西 也称为常个体或实体也称为常个体或实体 用用a、、b、、c…等表示2)个体域个体域：由个体组成的集合称为个体域由个体组成的集合称为个体域 个体域常用个体域常用I、、J、、K…等表示3)全总个体域全总个体域：： 所有个体不管是何种类型的个体综合在一起组成的个所有个体不管是何种类型的个体综合在一起组成的个体域称为全总个体域。

用体域称为全总个体域用U表示个体变元、项个体变元、项(4)个体变元个体变元：以个体域：以个体域I为为变域变域的变元称为个体域的变元称为个体域I上的个体变元上的个体变元 用用x、、y、、z、、…等表示5)项项：：包括实体、变量符号和函数符号等包括实体、变量符号和函数符号等, 是构成原子公式的一部分是构成原子公式的一部分 (原子公式的定义详见第原子公式的定义详见第28页第页第-5行行)特定个体特定个体a、泛指个体、泛指个体x、、个体的函数个体的函数 f(x)第三章 谓词演算基础3.1 谓词与个体谓词与个体 3.1.1 个体个体 3.1.2 谓词谓词3.2 函数与量词函数与量词3.3 自由变元和约束变元自由变元和约束变元 3.4 永真性和可满足性永真性和可满足性3.5 唯一性量词与摹状词唯一性量词与摹状词一、有关概念一、有关概念把语句中表示把语句中表示 个体性质和关系的语言成分（通常是谓语）个体性质和关系的语言成分（通常是谓语）称为称为谓词谓词（（predicate）谓词是指个体所具有的性质或若干个体之间的关系。

例例 (谓词：表示个体性质或个体间关系谓词：表示个体性质或个体间关系)l “苏格拉底是人苏格拉底是人”中的中的 “…是人是人”l “苏格拉底是要死的苏格拉底是要死的”中的中的“…是要死的是要死的”l “张三生于北京张三生于北京”中的中的“…生于生于…” l “3+2=5”中的中的“…+…=…”谓词的元数谓词的元数——谓词所携空位的数目谓词携有可以放置个体的空位，当空位上填谓词携有可以放置个体的空位，当空位上填入个体后便产生一个关于这些个体的语句，入个体后便产生一个关于这些个体的语句，它断言个体具有谓词所表示的性质和关系它断言个体具有谓词所表示的性质和关系例例 (一元谓词、二元谓词、三元谓词一元谓词、二元谓词、三元谓词)l “苏格拉底是人苏格拉底是人”中的中的 “…是人是人”l “苏格拉底是要死的苏格拉底是要死的”中的中的“…是要死的是要死的”l “张三生于北京张三生于北京”中的中的“…生于生于…” l “3+2=5”中的中的“…+…=…”谓词命名式谓词命名式: 携有空位的大写字母携有空位的大写字母 M（）表示（）表示“…是人是人” D（）表示（）表示“…是要死的是要死的”。

B（（ ，）表示，）表示“…生于生于…” ADD（（ ，， ，， ）表示）表示“…+…=…”可读性差！可读性差！ 可用变元来代替空位因此，上述谓词可以表可用变元来代替空位因此，上述谓词可以表示为：示为：M(x)，，D(x)，，B(x,y)，，ADD(x, y, z)谓词填式谓词填式——谓词的空位上填入个体后所产生的语句谓词的空位上填入个体后所产生的语句例如：例如： M（（苏格拉底苏格拉底）表示）表示“苏格拉底苏格拉底是人是人” D（（苏格拉底苏格拉底）表示）表示“苏格拉底苏格拉底是要死的是要死的” B（张三，北京）表示（张三，北京）表示“张三生于北京张三生于北京” ADD（（3，，2，，5）表示）表示“3+2=5”单个谓词不构成完整的意思，只有当谓词填单个谓词不构成完整的意思，只有当谓词填以个体后才能够构成完整的意义以个体后才能够构成完整的意义谓词命名式与谓词填式谓词命名式与谓词填式同形，但它们表示不同的意义同形，但它们表示不同的意义例如，例如，lM(x)作为命名式时，它只是作为命名式时，它只是M()的另一写法，的另一写法，与与x无关，改为无关，改为M(y)意义照旧；意义照旧；lM(x)作为填式时，它表示作为填式时，它表示“x是人是人”，改为，改为M(y)后其意义后其意义“y是人。

是人谓词：从个体域到真值集的映射谓词：从个体域到真值集的映射当谓词填式中所填个体都是常元时，它是一当谓词填式中所填个体都是常元时，它是一个命题，因而有确定的真值个命题，因而有确定的真值例如：例如： M（（苏格拉底苏格拉底）为真，）为真， M（孔子）为真，（孔子）为真， M（孙悟空）为假，（孙悟空）为假， M（北京）为假北京）为假一元谓词的数目与个体域的大小有关一元谓词的数目与个体域的大小有关谓词：从个体域到真值集的映射谓词：从个体域到真值集的映射例如：例如： 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)表示表示“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与两个实体与两个实体 Shakespeare和和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分别在三个域上变化。

分别在三个域上变化谓词变元的定义谓词变元的定义u以某个个体域以某个个体域I为定义域、以真假为值为定义域、以真假为值域的谓词称作域的谓词称作个体域个体域I上上的的谓词谓词u以某个个体域以某个个体域I上的谓词为上的谓词为变域变域的变元的变元称作称作个体域个体域I上的上的谓词变元谓词变元个体域个体域{a}上的一元谓词上的一元谓词 单个体的一元谓词单个体的一元谓词A(e)如下图所示如下图所示: 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单单个体的二个体的二元元谓词谓词有有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个。

个谓词数目谓词数目一元谓词一元谓词二元谓词二元谓词三元谓词三元谓词m元谓词元谓词2个个体个个体41625622m3个个体个个体851213421772823mh个个体个个体2h2h22h32hm第三章 谓词演算基础3.1 谓词与个体谓词与个体 3.1.1 个体个体 3.1.2 谓词谓词3.2 函数与量词函数与量词3.3 自由变元和约束变元自由变元和约束变元 3.4 永真性和可满足性永真性和可满足性3.5 唯一性量词与摹状词唯一性量词与摹状词。