《《逻辑学》(第二版)-第4章-谓词逻辑课件.ppt》由会员分享，可在线阅读，更多相关《《逻辑学》(第二版)-第4章-谓词逻辑课件.ppt（68页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、逻辑学（第二版）第四章 谓词逻辑李娜 教授马克思主义理论研究和建设工程重点教材目 录第一节 个体词、谓词和量词第二节 谓词逻辑的形式语言第三节 基本语法概念第四节 谓词逻辑的语义第四章第四章 谓词逻辑谓词逻辑 命题逻辑是关于命题联结词用法的逻辑理论。在命题逻辑中，简单命题不含任何命题联结词，因此它们用字母p、q、r等表示；每个复合命题都是从简单命题运用命题联结词构造起来的。真值表方法能够用来判定一个仅仅涉及命题联结词的推理是否有效，命题逻辑的自然演绎系统能够证明任何命题逻辑的有效推理形式。但是，还有一些有效的推理形式是命题逻辑不能处理的，例如下面的三段论：第四章 谓词逻辑 猫科动物都是哺乳动物
2、。（p）老虎都是猫科动物。（q）所以，老虎都是哺乳动物。（r）这个推理是正确的。但是从命题逻辑的观点看，这个推理的前提和结论分别是三个简单命题p、q和r。在命题逻辑中，从p和q不能推出r。虽然传统三段论是有效的，但是传统三段论的推理形式是有限的，无法处理一些更复杂的推理，第四章第四章 谓词逻辑谓词逻辑比如：有一个人所有人都爱他。所以，对每个人来说，都有一个他所爱的人。这个推理从直觉上看是正确的，但是却无法使用三段论来分析，也无法在命题逻辑中证明它的有效性。为了研究简单命题的内部结构，需要对简单命题进行进一步的分析，分离出表达个体的个体词第四章第四章 谓词逻辑谓词逻辑、表达性质或关系的谓词、表达
3、数量的量词，从而对简单命题的逻辑结构进行描述。由此建立起来的逻辑称为谓词逻辑，也称作一阶逻辑或者量化逻辑。第一节 个体词、谓词和量词 在自然语言中，有一些词是代表个体的，有些词是代表性质或关系的，还有一些词代表满足一些性质或关系的个体数量。我们区分个体词、谓词和量词，分别加以说明，而且用符号来表示它们。第一节 个体词、谓词和量词一、个体词 个体词是代表个体的词。这样的词有很多。自然语言中最容易识别的个体词是专名（专有名词）。常见的人名、地名等都是专名。例如，北京、天安门、太阳、长江，等等。为了最终能够写出命题的形式，我们用符号来代表专名，这样的符号我们称之为个体常元：第一节 个体词、谓词和量词
4、（1）个体常元：c,c1,c2,（可以没有）为方便起见，我们用a、b、c等字母表示任意个体常元。另一种个体词是在数学中常用的，称为个体变元：（2）个体变元：x,x1,x2,第一节 个体词、谓词和量词 一般地说，一个n元函数符号是带有n个个体变元的函数符号，记为f(x1,xn)。这样我们得到构成第三种个体词的符号：（3）对于每个大于等于1的自然数n，n元函数符号：fn,gn,hn,（可以没有）我们用f、g、h等表示任意n元函数符号。注意每个函数符号都是有元数的。在书写具体命题的形式时，我们根据需要来确定函数的元数。第一节 个体词、谓词和量词 构造项的符号有三种：个体常元：c,c1,c2,；个体变
5、项：x,x1,x2,；n（1自然数）元函数符号：fn,gn,hn,。我们用s、t等代表任何项。项是按如下规则构造的表达式：（T1）每个个体变元x是项。（T2）每个个体常元c是项。（T3）如果t1,tn是项并且f是一个n元函数符号，那么f(t1,tn)是项。（T4）只有按照（T1）-（T3）构造的表达式才是项。第一节 个体词、谓词和量词 谈论个体的范围叫作论域，一般用D、W等表示，它是非空的。二、谓词二、谓词 谓词是用来表达个体的性质或者个体之间的关系的词。只带有一个项的谓词称为一元谓词。二元谓词表示两个项所代表的个体之间的二元关系。第一节 个体词、谓词和量词 谓词符号包括：对每个大于或者等于1
6、的自然数n，Pn,Qn,Hn,（可以没有）。我们也用P、Q、R、H等符号表示任意谓词符号。每个谓词符号都有一个固定的自然数n作为它的元数（这里n0）。第一节 个体词、谓词和量词三、量词三、量词 对于一个论域D，用符号x表示“论域D中所有个体”；用符号x表示“论域D中存在一个个体”，这里x的取值范围是D，符号x意思是“对x在论域D中所有取值”；x意思是“对x在论域D中的至少一个取值”。第二节 谓词逻辑的形式语言 本节引入谓词逻辑的形式语言，主要包括一些本节引入谓词逻辑的形式语言，主要包括一些初始符号和公式的形成规则。运用谓词逻辑的形式初始符号和公式的形成规则。运用谓词逻辑的形式语言可以将自然语言
7、中的一些命题符号化，本节还语言可以将自然语言中的一些命题符号化，本节还将讲解符号化的操作过程。将讲解符号化的操作过程。第二节 谓词逻辑的形式语言一、谓词逻辑的公式一、谓词逻辑的公式 谓词逻辑的形式语言的初始符号如下：（1）个体常元：c,c1,c2,（可以没有）（2）个体变元：x,x1,x2,（3）n(1的自然数)元函数符号：fn,gn,hn,（可以没有）（4）n(1的自然数)元谓词符号：Pn,Qn,Hn,（可以没有）第二节 谓词逻辑的形式语言（5）命题联结词：、（6）量词：、（7）等词：（可以没有）（8）括号：),(,在没有（1）（3）（4）的语言中，一定要有（7）。第二节 谓词逻辑的形式语言
8、定义定义1 1 谓词逻辑的公式是按如下规则形成的表达式：（F1）P(t1,tn)是公式，其中P是一个n元谓词符 号，t1,tn是项。（F2）t1t2是公式，其中t1,t2是项。（F3）如果A是公式，那么A是公式。（F4）如果A和B是公式，那么(AB)、(AB)、(AB)、(AB)都是公式。（F5）如果A是公式，那么xA和xA是公式。（F6）只有按照（F1）-（F5）形成的表达式才是公 式。第二节 谓词逻辑的形式语言 为了以后讨论的方便，我们约定：最外层的括号可以省略；对于连续出现的或者或者或者，我们采用右结合的方法；五个联结词的结合力依、递减。第二节 谓词逻辑的形式语言二、命题的符号化二、命题
9、的符号化（一）直言命题 （1）单称肯定命题：a是P。（2）单称否定命题：a不是P。单称肯定命题“a是P”符号化的结果是 “P(a)”。单称否定命题“a不是P”符号化的结果是 “P(a)”。第二节 谓词逻辑的形式语言 按照如下给出的模型将给出的命题符号化：论域：所有人 a：曹雪芹 b：红楼梦 c：江宁 f(x)：x的父亲 g(x)：x的作者 P(x,y)：x是y的织造府官员 Q(x)：x是清朝人 第二节 谓词逻辑的形式语言 例1 红楼梦的作者是清朝人。符号化过程如下：1 g(b)是清朝人2 Q(g(b)例2 曹雪芹的祖父是江宁的织造府官员。符号化过程如下：1 f(f(a)是江宁的织造府官员。2
10、P(f(f(a),c)第二节 谓词逻辑的形式语言（3）全称肯定命题：所有S是P。（4）全称否定命题：所有S都不是P。全称肯定命题“所有S都是P”符号化的结果是 x(S(x)P(x)。全称否定命题“所有S都不是P”符号化的结果是 x(S(x)P(x)。第二节 谓词逻辑的形式语言（5）特称肯定命题：有的S是P。（6）特称否定命题：有的S不是P。特称肯定命题“有的S是P”符号化的结果是 x(S(x)P(x)。特称否定命题“有的S不是P”符号化的结果是 x(S(x)P(x)。第二节 谓词逻辑的形式语言 全称肯定命题“所有阔叶植物是落叶的”的符号化过程如下：1 对所有x，如果x是阔叶植物，那么x是落叶的
11、。2 x(S(x)P(x)全称否定命题“所有阔叶植物都不是落叶的”的符号化过程如下：1 对所有x，如果x是阔叶植物，那么x不是落叶的。2 x(S(x)(x是落叶的)3 x(S(x)P(x)第二节 谓词逻辑的形式语言 特称肯定命题“有的阔叶植物是落叶的”的符号化过程如下：1 存在x使得x是阔叶植物并且x是落叶的。2 x(x是阔叶植物并且x是落叶的)3 x(S(x)并且P(x)4 x(S(x)P(x)第二节 谓词逻辑的形式语言 特称否定命题“有的阔叶植物不是落叶的”的符号化过程如下：1 存在x使得x是阔叶植物并且x不是落叶的。2 x(S(x)并且(x是落叶的)3 x(S(x)并且P(x)4 x(S
12、(x)P(x)第二节 谓词逻辑的形式语言（二）嵌套量词 在自然语言中还有一类含有多个量词的命题，这样的命题一般比较复杂，涉及推理时应仔细加以分析。例 考虑下面的模型：论域：所有动物 P(x)：x是人 L(x,y)：x爱y第二节 谓词逻辑的形式语言（1）每个人都爱某些人。符号化如下：1 对任何x，如果x是人，那么x爱某些人。2 对任何x，如果x是人，那么存在y(y是人并且x 爱y)。3 x(P(x)y(P(y)L(x,y)（2）有些人爱所有人。符号化如下：1 存在x(x是人并且x爱所有人)。2 存在x(P(x)并且(对任何y，如果y是人，那么x 爱y)3 x(P(x)y(P(y)L(x,y)第二
13、节 谓词逻辑的形式语言（3）没有人爱所有人。符号化如下：1 不存在x(x是人并且x爱所有人)。2 不存在x(P(x)并且(对任何y，如果y是人，那 么x爱y)3 x(P(x)y(P(y)L(x,y)（4）有些人不爱任何人。符号化如下：1 存在x(x是人并且x不爱任何人)。2 存在x(P(x)并且(对任何y，如果y是人，那么x 不爱y)3 x(P(x)y(P(y)L(x,y)第二节 谓词逻辑的形式语言（三）数量命题 我们考虑“至少有n个”、“至多有n个”和“恰好有n个”三个数量词，它们在谓词逻辑的形式语言中是能够被定义的，而且要使用等词来定义。在下面的表述中，我们用“s t”表示“(s t)”。
14、在论域D中：第二节 谓词逻辑的形式语言（1）至少有n个个体。至少有1个个体：x(xx)至少有2个个体：xy(xy)至少有3个个体：xyz(xyxzyz)至少有n个个体：x1x2xn(x1x2x1xnxn-1xn)第二节 谓词逻辑的形式语言（2）至多有n个个体。至多有1个个体：xy(xy)至多有2个个体：xyz(xyxzyz)至多有3个个体：xyzu(xyxzxuyzyuzu)至多有n个个体：x1x2xn+1(x1x2x1xn+1xnxn+1)第二节 谓词逻辑的形式语言（3）恰好有n个个体。令A表示至少有n个个体，B表示至多有n个个体。那么AB表示恰好有n个个体。（4）至少有n个S是P。至少有1
15、个S是P：x(S(x)P(x)至少有2个S是P：xy(xyS(x)P(x)S(y)P(y)至少有3个S是P：xyz(xyxzyzS(x)P(x)S(y)P(y)S(z)P(z)依次类推，可以表达“至少有n个S是P”。第二节 谓词逻辑的形式语言（5）至多有n个S是P。至多有1个S是P：xy(S(x)P(x)S(y)P(y)xy)至多有2个S是P：xyz(S(x)P(x)S(y)P(y)S(z)P(z)(xyxzyz)至多有3个S是P：xyzu(S(x)P(x)S(y)P(y)S(z)P(z)S(u)P(u)(xyxzxuyzyuzu)依次类推，可以表达“至多有n个个体”。第二节 谓词逻辑的形式语
16、言（6）恰好有n个S是P。令A表示至少有n个S是P，B表示至多有n个S是P。那么AB表示恰好有n个S是P。第二节 谓词逻辑的形式语言 将下面的推理符号化：读过至少两本金庸小说的人都喜欢黄蓉。所有喜欢金庸小说的人都至少读过两本金庸小说。张三喜欢金庸小说。所以，张三喜欢黄蓉。为了使这个推理符号化，我们先要给出一个模型：论域：所有人和金庸小说 a：黄蓉 b：张三 S(x)：x是金庸小说 L(x,y)：x喜欢y D(x,y)：x读过y P(x)：x是人第二节 谓词逻辑的形式语言（1）读过至少两本金庸小说的人都喜欢黄蓉。1 x(x是人并且x读过至少两本金庸小说x喜 欢黄蓉)2 x(P(x)x读过至少两本
17、金庸小说L(x,a)3 x(P(x)yz(yzy是金庸小说 z是金庸小说x读过yx读过z)L(x,a)4 x(P(x)yz(yzS(y)S(z)D(x,y)D(x,z)L(x,a)第二节 谓词逻辑的形式语言（2）所有喜欢金庸小说的人都至少读过两本金庸小说。1 x(x是人x喜欢金庸小说x读过至少两本 金庸小说)2 x(P(x)y(y是金庸小说x喜欢y)zu(zuz是金庸小说u是金庸小说 x读过zx读过u)3 x(P(x)y(S(y)L(x,y)zu(zuS(z)S(u)D(x,z)D(x,u)第二节 谓词逻辑的形式语言（3）张三喜欢金庸小说。1 x(x是金庸小说 b喜欢x)2 x(S(x)L(b
18、,x)（4）张三喜欢黄蓉。1 L(b,a)第二节 谓词逻辑的形式语言 上述推理符号化的结果是：x(P(x)yz(yzS(y)S(z)D(x,y)D(x,z)L(x,a),x(P(x)y(S(y)L(xy)zu(zuS(z)S(u)D(x,z)D(x,u),x(S(x)L(b,x)L(b,a)。第三节 基本语法概念 为了第四节介绍谓词逻辑的语义，在这一节中，首先介绍几个基本的语法概念。第三节 基本语法概念一、自由变元与约束变元一、自由变元与约束变元 在一个公式中，量词的管辖范围就是它的辖域。例12 量词的辖域：（1）x(S(x)P(x)S(z)量词的辖域是x(S(x)P(x)。（2）xS(x)(
19、xP(x)xS(x,a)量词的辖域是xS(x)，量词第一次出现的辖域是xP(x)，量词第二次出现的辖域是xS(x,a)。第三节 基本语法概念定义定义2 2 对任何公式A，称个体变元x在A中的一次出现为约束出现，如果x的这一次出现是在A的某个量词或的辖域中。称变元x在A中的一次出现为自由出现，如果它不是约束出现。称一个变元x是公式A的约束变元，如果它至少在A中有一次约束出现；称x为A的自由变元，如果它至少在A中有一次自由出现。在一个公式A中，一个变元可能既是约束的，又是自由的。第三节 基本语法概念例例1313 个体变元的约束出现和自由出现：（1）x(S(x)P(x)S(z)x的所有出现都是约束的
20、，z的出现是自由的。（2）xS(x)(yP(f(x),g(y)xS(x,y)x的第三次出现是自由的，其余出现是约束的。y的第三次出现是自由的，其余出现是约束的。第三节 基本语法概念 对任何公式A，如果A中没有自由变元，那么称A为闭公式；反之，如果A中至少有一个自由变元，那么称A为开公式。第三节 基本语法概念二、代入二、代入定义定义3 3 对任何项t、s和个体变元x，定义t(s/x)如下：c(s/x)=c x(s/x)=s y(s/x)=y，其中y不是x。f(t1,tn)(s/x)=f(t1(s/x),tn(s/x)第三节 基本语法概念定义定义4 4 对任何公式A、项t和个体变元x，定义A(t/
21、x)如下：P(s1,sn)(t/x)=P(s1(t/x),sn(t/x)(s1s2)(t/x)=s1(t/x)s2(t/x)(A)(t/x)=A(t/x)(AB)(t/x)=A(t/x)B(t/x)(AB)(t/x)=A(t/x)B(t/x)(AB)(t/x)=A(t/x)B(t/x)(AB)(t/x)=A(t/x)B(t/x)第三节 基本语法概念 (xA)(t/x)=xA 如果x不是y，t中不包含变元y，那么 (yA)(t/x)=yA(t/x)如果x不是y，t中含变元y，那么 (yA)(t/x)=zA(t/x,z/y)其中，z是不在A和t中出现的下标最 小的那个个体变元。第三节 基本语法概念
22、 (xA)(t/x)=xA 如果x不是y，t中不包含变元y，那么 (yA)(t/x)=yA(t/x)如果x不是y，t中含变元y，那么 (yA)(t/x)=zA(t/x,z/y)其中，z是不在A和t中出现的下标最小的 那个个体变元。第三节 基本语法概念定义定义5 5 对任何公式A、项t和变元x，称t对A中x可自由代入，若x在A中不自由出现于某个y或者y的辖域中。这里的y是出现于t中的一个变项。例例 令A是公式xR(x,y)那么（1）y对A中x不可自由代入。（2）x对A中y不可自由代入。（3）c对A中y可自由代入。（4）任意项t对A中x不可自由代入。第三节 基本语法概念定义定义6 6 对任何公式A
23、，假设y不在A中自由出现，并且y对A中x可自由代入。那么称公式yA(y/x)为xA的易字，称公式yA(y/x)为xA的易字。第四节 谓词逻辑的语义一、模型和赋值一、模型和赋值定义定义7 7 一个模型是一个二元组M=(D,I)，其中D是一个论域（非空集合），I是对所有个体常元符号、函数符号和谓词符号的解释：（1）对每个个体常元符号c，c在M中的解释I(c)（也记为cM）是D中的某个元素。（2）对每个n元函数符号f，f在M中的解释I(f)（也 记为fM）是M上的一个n元函数。（3）对每个n元谓词符号P，P在M中的解释I(P)（也 记为PM）是Dn的一个子集。第四节 谓词逻辑的语义 令Var是所有个
24、体变元的集合。定义定义8 8 任何模型M=(D,I)中的一个赋值是一个函数:VarD，即从所有个体变元的集合到D的一个函数。一个赋值对每个个体变元指定论域中的一个元素作为它的值。第四节 谓词逻辑的语义定义定义9 9 对任何模型M=(D,I)和M中的一个赋值，一个项t在M中下的解释（记作：t）定义如下：c=cM x=(x)(f(t1,tm)=fM(t1,tm)第四节 谓词逻辑的语义定义定义10 10 对任何模型M=(D,I)、M中的赋值和论域中的个体dD，定义一个新的赋值(d/x):VarD如下：(d/x)(y)=(y)，其中y不是x。(d/x)(x)=d。第四节 谓词逻辑的语义定义定义11 1
25、1 对任何模型M=(D,I)和M中的一个赋值，一个公式A在M中下真（记号：M,A）定义如下：M,P(t1,tn)当且仅当(t1,tn)PM M,t1t2当且仅当t1=t2 M,A当且仅当M,A第四节 谓词逻辑的语义 M,AB当且仅当M,A并且M,B M,AB当且仅当M,A或者M,B M,AB当且仅当M,A或者M,B M,AB当且仅当M,A并且M,B，或者M,A并且M,B M,xA当且仅当对所有dD都有M,(d/x)A M,xA当且仅当存在dD使得M,(d/x)A。第四节 谓词逻辑的语义 在这个定义中，M,A表示“M,A”不成立，即A是假的。在有些情况下，如果M,A，也称在模型M中满足A；如果M
26、,A，也称在模型M中不满足A。称一个公式A是可满足的，如果存在一个模型M=(D,I)和M中的一个赋值使得M,A。第四节 谓词逻辑的语义结论结论1 1 对任何公式A和变元x，假设x不在A中自由出现。那么对任何模型M=(D,I)和M中的任何赋值，对任何dD，都有 M,A当且仅当M,(d/x)A。结论结论2 2 对任何公式A和模型M=(D,I)，如果两个赋值和对A中所有自由变元的赋值相同，那么 M,A当且仅当M,A。结论结论3 3 假设t对A中x可自由代入。那么 M,(t/x)A当且仅当M,A(t/x)。第四节 谓词逻辑的语义 称公式A与B是逻辑等值的，如果对任何模型M和M中的任何赋值，都有M,A当
27、且仅当M,B。如下公式是逻辑等值的：（1）x(AB)与xAxB逻辑等值。（2）x(AB)与xAxB逻辑等值。第四节 谓词逻辑的语义（3）对任何公式A，假设x不在A中自由出现。那么 x(AB)与AxB逻辑等值；x(AB)与 AxB逻辑等值。（4）对任何公式A，假设y不在A中自由出现，并且y 对A中x可自由代入，那么yA(y/x)与xA逻辑 等值并且yA(y/x)与xA逻辑等值。第四节 谓词逻辑的语义（5）xA与xA逻辑等值；xA与xA逻辑等值。（6）xyA与yxA逻辑等值；xyA与yxA逻辑等值。（7）假设x不在A中自由出现，那么 A与xA逻辑等值；A与xA逻辑等值。第四节 谓词逻辑的语义二、有
28、效公式与有效推理二、有效公式与有效推理定义定义12 12 称一个谓词逻辑公式A在模型M=(D,I)中是有效的（记号：MA），如果对M中任何赋值都有M,A。称一个谓词逻辑公式A是有效的（记号：A），如果对任何模型M都有MA。第四节 谓词逻辑的语义 如下公式都是有效的：（1）x(AB)(xAxB)（2）xAxA（3）xAA(t/x)，其中t对A中x可自由代入。（4）xyAyxA第四节 谓词逻辑的语义定义定义13 13 对任何公式集和公式A，称A是的一个逻辑后承（记号：A），如果对任何模型M=(D,I)和M中的任何赋值，如下条件成立：对所有B，如果M,B，那么M,A。第四节 谓词逻辑的语义 如下逻辑后承关系成立：（1）x(S(x)P(x),S(a)P(a)（2）x(S(x)P(x),P(a)S(a)（3）xS(x),yP(y)z(S(z)P(z)第四节 谓词逻辑的语义 一般地，对于逻辑后承关系来说，有如下结论：结论结论4 4 对任何公式集和公式A、B，,AB当且仅当AB。这个结论可以直接从定义得到证明。由此可知，两个公式A和B逻辑等值当且仅当AB。