非形式的谓词演算

非形式的谓词演算5非形式的谓词演算我们首先来看下面一个论证：所有的人都是会死的，苏格拉底是人，苏格拉底是会死的。这个是一个直觉上有效的推理。但是，按照前面所讲的方法来分析，它的形式是：p,q所以r。显然，从命题演算的角度来看这不是一个有效的推理。原因在哪里呢？这种情况下，推理的有效性不是依赖于作为简单命题的前提和结论之间的关系，而依赖于命题各个组成部分之间的关系、依赖于这些命题本身的形式。第2页,共53页，2024年2月25日，星期天5非形式的谓词演算一般来说，我们可以把它分析成以下形式：所有的A是B,a是A,所以,a是A。在这个推理形式中，有几个值得我们注意的地方：谓词变元A、B，个体变元a和量词“所有的”。一般的简单命题都具有“主词”和“谓词”，主词是命题要加以断定的事物，而谓词是指该事物具有的“属性”。我们来分析下列命题：第3页,共53页，2024年2月25日，星期天5非形式的谓词演算在下列各命题中，主词是用红字标记的，余下的部分是谓词：（a）苏格拉底是人。（b）我写书。（c）平方为－1的数不是实数。（d）世界给人以生存。以后，我们用大写的英文字母A,B,C,…表示谓词，用小写的英文字母a,b,c,…表示主词。相应地，以上命题(a)可以表示为H(s):H表示“是人”，s代表苏格拉底。命题(b)可以表示为B(i):B表示“写书”，i代表我。命题(c)可以表示为

R(j):R表示“是实数”，j代表平方为－1的数。命题(d)可以表示为L(w):L表示“给人以生存”，i代表世界。第4页,共53页，2024年2月25日，星期天5非形式的谓词演算只要我们知道了简单命题如何按照这种形式翻译成符号语言，加上前面的知识，我们自然也就知道了复合命题如何翻译成这种符号语言。现在的问题是：对于“所有人都是会死的”，这样的命题我们怎么办？这类命题的主词不是指称单个的对象，而是用量词“所有”赋予多个对象以某个性质。我们参考数学符号体系中的常用方法。例如，说“每个整数都有素因子”就被翻译成“对于所有的x来说，如果x是整数，那么x就有素因子。”类似地，“所有人都是会死的”也被翻译成“对于所有的x来说，如果x是人，那么x是会死的。”第5页,共53页，2024年2月25日，星期天5非形式的谓词演算以后，为了记法上的方便，我们把这个命题记为“

x(MxDx)”。其中：（1）谓词M、D分别表示“是人”和“是会死的”。（2）“

”是全称量词符号，表示所有的意思。（3）x是个体变元，当它没有被量词约束时，它表示不确定的主体，这个时候我们一般也称之为自由变元。自由变元的论域是不确定的。（4）单个的全称量词符号是不完整的，当它和自由变元结合成“

x”这样的形式，我们就表示自由变元x被全称量词“

”约束了。在这里x就成为了约束变元，约束变元的论域是确定的。我们可以指定一个特定的论域，例如“全体自然数”。当没有指定特定论域时，我们就把论域看成是全域，即万事万物。第6页,共53页，2024年2月25日，星期天5非形式的谓词演算（5）但是，仅仅是“

x”仍然不是完整的公式，它仅仅表示“所有的事物”或“所有的数”。显然这样还不能完整地构成一个公式，从而表达一个全称命题。只有当它和谓词变元结合在一起才构成合式公式。例如：“

xMx”表示“所有的事物是人”。或者限定x的论域是全体整数，我们用“

xAx”表示“所有的整数都有素因子”，其中“A”表示“有素因子”。请大家注意：如果x是全域中的不确定个体的话，那么这句话“所有的整数都有素因子”就翻译成“

x(IxAx)”,其中“I”和“A”分别表示“是整数和”“有素因子”。第7页,共53页，2024年2月25日，星期天5非形式的谓词演算一般来说，还有一个量词在我们把自然语言翻译成谓词符号语言时也是需要的：例如：“有些猪是有翅膀的”。我们一般可以把它看成：“至少存在有一个x使得x是一头猪并且x有翅膀”。同样地，我们可以将这个命题翻译成：“

x(PxWx)”，其中“P”和“W”分别表示“是一头猪”和“有翅膀”。一般来说，“全称量词＋普通名词＋属性”翻译时我们使用蕴含联结词把前后两个谓词符号联结起来。“存在量词＋普通名词＋属性”翻译时我们使用合取联结词把前后两个谓词符号联结起来。第8页,共53页，2024年2月25日，星期天5非形式的谓词演算请大家把以下自然语言翻译成谓词符号语言：(1)所有的鸟都会飞。(2)并非所有的鸟都会飞。(3)所有的鸟都不会飞。(4)并非所有的鸟都不会飞。(5)至少有一只鸟会飞。(6)并非至少有一只鸟会飞。(7)至少有一只鸟不会飞。(8)并非至少有一只鸟不会飞。(9)有一个整数大于其他所有整数。(10)所有的马都是动物，所以所有的马头都是动物头。(1)-(8)论域是全域，B——鸟，F——会飞。(1)x(BxFx)；(2)x(BxFx)；(3)x(BxFx)；(4)x(BxFx)；第9页,共53页，2024年2月25日，星期天5非形式的谓词演算(5)x(BxFx)；(6)x(BxFx)；(7)x(BxFx)；(8)x(BxFx)；(9)论域为全域，I——整数，LI(x,y)——xy。

x(Ixy(IyLI(x,y))(10)首先，我们把后面那句话等价地翻译为“对于所有的x而言，如果存在有一个y，y是马并且x是y(马)的头，那么也存在有一个z,z是动物并且x是z(动物)的头。”论域为全域，H——马，A——动物，T(x,y)——x是y的头。

x(HxAx)x(y(HyT(x,y))z(AzT(x,z))。第10页,共53页，2024年2月25日，星期天5非形式的谓词演算课后作业：请把“没有一个人尊重不自重的人，并且没有一个人信任他不尊重的人。所以，一个不受尊重的人是不受任何人信任的。”翻译成谓词符号语言。其中，论域为全域，M——是人，R(x,y)——x尊重y，（注：R(x,x)——表示x自重），H(x,y)——x信任y。第11页,共53页，2024年2月25日，星期天5非形式的谓词演算现在我们来进一步考察(1)－(8)：直觉上，我们是用(7)“至少有一只鸟不会飞”来证实(2)“并非所有的鸟会飞。”即

x(BxFx)x(BxFx)

根据前面的知识，x(BxFx)x(BxFx)2.2.4.(12)＋等值置换

x(BxFx)2.2.4.(1)＋等值置换

x(BxFx)2.2.4.(6a)＋等值置换现在，我们比较“

x(BxFx)”和“

x(BxFx)”，我们发现：后者与前者的区别仅在于“

x”代替了“

x”。这样我们据明白一个道理：“

x”可以替换“

x”；另一方面，“

x”也可以替换“

x”。第12页,共53页，2024年2月25日，星期天5非形式的谓词演算因为直观上：(1)“并非所有的x都不具有属性P”(xPx)等价于“存在有某个x具有属性P”(xPx)。(2)“并非存在有某个x不具有属性P”(xPx)等价于“所有的x都具有属性P”(xPx)。于是，存在量词和全称量词只需要有一个，另一个可以借助否定联结词相应地定义出来。同样的道理:(1)x(BxFx)(8)x(BxFx)(3)x(BxFx)(6)x(BxFx)

(4)x(BxFx)(5)x(BxFx)

上面的证明，大家任意选做一个，写清楚理由！第13页,共53页，2024年2月25日，星期天5非形式的谓词演算课后作业：把下列各命题写成符号形式。先不用存在量词，然后不用全称量词。（任意选择两个做）（1）并非所有的汽车都是三只轮子。（2）有些人或者是懒惰的，或者是愚蠢的。（3）没有一只耗子比任何一只象重。（4）每个数或者是负的或者有一平方根。要求：把论域和谓词符号所代表的含义写清楚。第14页,共53页，2024年2月25日，星期天5.1一阶语言一阶符号语言由下列7类符号构成：（1）个体变元符号：x1,x2,…,xn,…。（2）联结词符号：，。（3）量词符号：。（4）技术符号：(，)。（5）个体常元：a1,a2,…,an(,…)。（6）函数符号：（7）谓词符号：注1：以后我们用表示苏格拉底是人。其中个体常元表示苏格拉底，而一元谓词表示性质“是人”。第15页,共53页，2024年2月25日，星期天5.1一阶语言注2：谓词符号的上标表明了谓词是几元谓词。如果是1就表示一个性质，如果是2就表示一个二元关系，如果是3就表示一个三元关系，如此类推。注：函数符号的上标和谓词符号的上标解释差不多，表示函数所带参数的个数。不过请大家区别函数符号和谓词符号。谓词符号可以看成这样一个函数：而函数符号则应看成：第16页,共53页，2024年2月25日，星期天5.1一阶语言一般地，所有的个体变元的集合记为Var，所有的个体常元集记为Con。由(5)-(7)中的符号构成的集合称为L的特征符号集。一般情况下，我们固定(1)-(4)，而随着情况不同改变(5)-(7)。给定了一个特征符号集也就给定了一个语言的初始符号集。我们在后面常常使用下列元语言符号：x,y,z表示个体变元；P,Q,R表示谓词符号；F,G,H表示函数符号；c,d,e表示个体常元。第17页,共53页，2024年2月25日，星期天5.2一阶语言L中项和原子公式的定义为了定义一阶语言L中的合式公式，我们首先必须定义L中的项：（1）变元和个体常元是项；（2）如果是L中的函数符号，且是L中的项，则也是L中的项。（3）所有的项都是按照（1）和（2）生成的。项在形式语言中将被解释为对象，即函数作用于其上的事物，具有某种属性的事物，对之作出某种断定的事物。以后在元语言中，我们用t和u表示项。L中的原子公式定义为：如果是L中的一个谓词符号，是L中的项，则是L中的原子公式。第18页,共53页，2024年2月25日，星期天5.2L中合式公式的定义注：原子公式是语言中可断定的最简单的公式。例如，某些对象具有某种性质。这里“原子”一词当然是表示不能再分解了。L中的一个合式公式的定义如下：（1）L中的每个原子公式是L中的合式公式。（2）如果A和B是L中的合式公式，则

A，AB，xiA(其中xi是任意个体变元)也是合式公式。（3）L中的所有合式公式都是按照(1)和(2)生成的。注1：

xiA并不要求A中一定有个体变元xi的出现。第19页,共53页，2024年2月25日，星期天5.2L中合式公式的定义注2：我们规定：

xiA是xiA的缩写。

AB是(AB)的缩写。

AB是AB的缩写。注3：我们要注意xi(AB)和xiAB之间的区别。为此，我们需要再引入一些相关的定义。定义：在公式xiA中，我们称A是量词的辖域。更一般地，当xiA作为子公式出现在B中时，我们称这个量词在B中的辖域是A。定义：变元xi在一个公式中的出现称为约束的，如果它出现在公式中的xi的辖域之内，或者xi在xi中。如果一个变元的出现不是约束的，那么我们就称它是自由的。第20页,共53页，2024年2月25日，星期天5.2辖域、约束变元和自由变元例：请说明下列公式中量词的辖域，以及个体变元的每一次出现是约束的还是自由的。第21页,共53页，2024年2月25日，星期天5.2辖域、约束变元和自由变元当我们仅仅对公式中的变元感兴趣时，我们常常有这种写法：A(x1)或B(x1,…,xn)。在这种情况中，我们一般指其中的变元是自由出现的。如果xi在A中确实是自由出现，那么对于任何项t，A(t)将指对xi的每次自由出现都代入t后所得到的结果。下面我们解释一个比较重要的概念：令A是L中的任意公式，我们称项t对A中的个体变元xi是自由的，如果xi并不自由地出现在A的一个

xj的辖域中，这里的xj是指出现在t中的任何变元。粗略地说，所谓项对个体变元的自由指的是——项可以代入A中的xi每个自由出现，而不引起和A中的量词相互作用。第22页,共53页，2024年2月25日，星期天项对个体变元的代入举例来说，（1）x3对公式中的x2是自由的，而x1对公式中的x2则是不自由的。因为x2自由地出现在

x1的辖域中，而x2并没有自由地出现在x3的辖域中（在这里有两个意思：或者x2没有出现在x3的辖域中，或者x2出现在x3的辖域中，但是x2的出现是不自由的）。对于（1）中所举的例子来说，是因为x2没有出现在x3的辖域中。（2）也有可能出现x2约束地出现在x3的辖域中的情况，例如x3对公式中的x2是自由的。因为在这个公式中没有x2的自由出现。第23页,共53页，2024年2月25日，星期天项对个体变元的代入由上不难看出，项t对公式A中的变元x是自由的，主要是看t对x在A中的自由出现进行代入是不是自由的。而对x的约束出现进行代入则没有太多的意义。就好像（2）中例子所看到的那样。第24页,共53页，2024年2月25日，星期天课后作业：第25页,共53页，2024年2月25日，星期天项对公式的替换定义第26页,共53页，2024年2月25日，星期天项对公式的替换定义——举例第27页,共53页，2024年2月25日，星期天课后作业：第28页,共53页，2024年2月25日，星期天5.3解释定义5.3.1：L的一个解释I是由以下几部分内容构成的：（1）一个非空集DI（I的论域）；（2）一个特别的元素集{(a1)’,(a2)’,…,}；（3）一个在DI上的函数集（4）一个在DI上的关系集我们的意图是：L中的变元将会被解释为“对象”，而集合DI将被解释为变元在其上取值的论域。特别的元素集将对应L中个体常元的取值。DI上的函数和关系将分别对应L中函数和关系的解释。注：以后为了方便，在不会引起混淆的情况下，我们不区分a1与(a1)’第29页,共53页，2024年2月25日，星期天5.3解释一阶语言：如果一个语言的解释中，量词仅仅作用于将被解释为“对象”的个体变元之上。二阶语言：如果一个语言的解释中，量词不仅可以作用于将被解释为“对象”的个体变元之上，还可以作用于将被解释为对象关系的谓词变元之上。N阶语言：如果一个语言的解释中，量词可以作用于将被解释为N－1阶关系之间的关系之上。一阶符号语言系统又可称为一阶逻辑，二阶以上的符号语言系统统称为高阶逻辑。在本课程中，我们只讨论一阶逻辑。第30页,共53页，2024年2月25日，星期天5.3解释举例：（1）用一阶语言表示有关自然数的算术命题。解释I：论域DI

＝{0,1,2,…}；特别元素只有一个0，它将被解释为个体常元a1所对应的对象；于是，在这样一个解释I下，公式（1）将被解释为：对于所有的自然数x,y来说，并非对所有的自然数z，都有x+yz。第31页,共53页，2024年2月25日，星期天5.3解释另一方面，我们知道上述公式逻辑等值于：这个公式将被解释为：对于所有的自然数x,y来说，存在有一个自然数z，使得x+y=z。但是，我们要注意到一阶语言不能表达这样的算术命题“每个非空的自然数集都有一个最小数”，显然在描述这个命题是，我们不得不将全称量词作用于自然数集，这样的表述将成为二阶语言中的一个公式。只有当一个语言被给定一个解释之后，我们才能对有关公式的意义说些什么。也就是说，只有在第32页,共53页，2024年2月25日，星期天5.3解释一个解释下，才能考察这个公式的真假。上述公式（1）在解释I下显然是假的。但是，我们可以给这个公式另一种解释I’使得它为真。在解释I’下DI’是正有理数，这样，公式（1）将会被解释为：对任意的有理数x,y来说，存在有有理数z使得xy=z.显然这个命题是真的。第33页,共53页，2024年2月25日，星期天5.3解释课后作业：第34页,共53页，2024年2月25日，星期天5.4满足和真正如命题逻辑系统PC中的讨论一样（只有对命题公式中的命题变元指派真值，命题公式才会有真假），在谓词逻辑中，一阶公式只有在一个具体的解释下才有真假。在这里，解释相当于命题逻辑系统中所介绍的赋值（指派）。令I是以DI为论域的语言L上的一个解释。定义5.4.1：I上的一个赋值是一个从L的项集到集DI具有下列性质的一个函数v：（1）v(ai)=(ai)’,对于L中的每个个体常元ai；（2）第35页,共53页，2024年2月25日，星期天5.4满足和真赋值是这样一个规则：它给语言L中的每一个项指派了DI中的一个对象作为它的解释。注记：（1）在一个给定的解释下，将有多种不同的赋值。因为对于个体变元总有不同赋值的可能。（2）一给定的赋值将对L中的每一个变元xi指派DI中的一个元素。因此，如果对L中个体变元的赋值被确定了，那么这个赋值也被确定下来了。这是因为个体常元和复杂项都在5.4.1.(1)和(2)中被指派了DI中的一个元素。其中(2)是对复杂项的指派的归纳定义。下面我们介绍一个后面经常会用到的定义——i-等值：称两个赋值v和v’是i-等值，如果v(xj)=v’(xj)，对每个ij.即：两个赋值只有在xi上可能不同（也可能相同，一般情况下是不同的）。第36页,共53页，2024年2月25日，星期天5.4满足和真现在我们来考察在一个解释和赋值之下，一阶公式的满足。定义5.4.2:令A是L的一个公式，I是L的一个解释。I中的一个赋值v称为满足A，记为vI(A)=1(在不混淆的情况下记为v(A)=1)，如果(1)如果A是原子公式(2)如果A是“

B”这样的形式，那么v(A)=1当且仅当v(B)1（这也就是说，v不满足B，当且仅当v就满足B）(3)如果A是“BC”这样的形式，那么v(BC)=1，当且仅当，或者v(B)1或者v(C)=1

（即或者v不满足B或者v满足C）。第37页,共53页，2024年2月25日，星期天5.4满足和真(4)解释I中的一个赋值v满足当且仅当，每个i-等值于v的赋值v’满足B,注：我们有必要对(4)做出一些解释：首先，我们说I中的赋值v满足一个公式是这个意思：对于任意DI中的对象d’，I中的赋值v都会满足公式，其中对象d’是个体常元d在I下的解释。但是，怎么表示DI中的任意对象d’，这就得要引入前面的与vi-等值的赋值v’了。由于v和v’的唯一区别是在xi的赋值上有不同，因此引入v’的意图就在于可以给xi赋值不同的DI中的对象，而其他第38页,共53页，2024年2月25日，星期天5.4满足和真的情况则保持不变。如果在任意的与vi-等值的赋值v’下，公式都有（其中个体常元c替换个体变元xi表示在赋值v’下xi将被解释为论域中的对象c’

。当然我们也可以选择a,b,e,…替换xi

，这正是其他与vi-等值的赋值所干的事情。）假如所有的与vi-等值的赋值都有使得（d*表示某个个体常元），则我们前面所说的意思已经充分地表达出来了。第39页,共53页，2024年2月25日，星期天5.4满足和真例：（1）算术解释N：论域DI

＝{0,1,2,…}；个体常元a1被解释为0；在解释N的一个赋值v下:v(x1)=2,v(x1)=6,v(x1)=3,v(x1)=4。显然，赋值下v满足公式（1）因为2×6＝3×4.第40页,共53页，2024年2月25日，星期天5.4满足和真例2：在解释N中被解释为：对任意的自然数n，nm=mn。这显然是一个真命题。现在我们面对的一个问题是：公式（2）是可以从公式（1）中可推导出来的，或者说，公式（1）是否逻辑蕴涵公式（2）呢？分析步骤1：令v是N中的任意一个赋值，显然v(x1)和v(x2)是自然数，因此公式（1）被解释为v(x1)×v(x2)＝v(x2)×v(x1)，而这显然是真的。分析步骤2：对任意与v1-等值的赋值v’来说，v’无非是要改变v对于x1的赋值。但是，无论如何第41页,共53页，2024年2月25日，星期天5.4满足和真v’(x1)仍然是一个自然数，因此v’(x1)×v(x2)＝v(x2)×v’(x1)仍然是真的。这意味着对任意与v1-等值的赋值v’，都有成立，所以根据定义5.4.2.(4)我们有结论：赋值v在解释N下满足公式（2），再由于赋值v的任意性，解释N下所有的赋值都满足公式（2）。同理可证，在解释N下的所有赋值都满足这个公式。第42页,共53页，2024年2月25日，星期天5.4满足和真例3：在解释N下是什么意思，请大家思考解释N下是否有赋值v是否满足公式。不难发现，以后用另外的项或者变元去替代一个变元是经常用到的技巧，因此，以下定理是必须的。第43页,共53页，2024年2月25日，星期天5.4有穷指派引理1命题逻辑中的有穷指派引理：令{p1,…,pn}是命题公式A中出现的所有命题变元所构成的集合，假如v和u分别是对A的任意两组真值指派(赋值函数)，并且有v(p1)=u(p1),…,v(pn)=u(pn)，那么v(A)=u(A)。证明思路：施归纳于公式A的结构易证。其中我们会用到赋值函数的定义。这个证明比较简单，请同学们作为课后作业完成。有穷指派引理旨在说明：一个赋值函数对于命题公式A的真值的影响仅仅在于它给A中出现的命题变元指派怎样的真值，而与A中不出现的命题变元被指派什么真值无关。第44页,共53页，2024年2月25日，星期天5.4有穷指派引理循着这样的思路，我们试图考察对一阶公式是不是也存在有类似的有穷指派引理呢？谓词逻辑中的有穷指派引理旨在表明：在一个确定的解释下，一个赋值函数v是否满足一阶公式A，仅仅取决于v给A中出现的自由变元的赋值是什么，而与A中不出现的自由变元或A中约束出现的自由变元无关。第45页,共53页，2024年2月25日，星期天5.4有穷指派引理定理5.4.3：令I是L的一个解释，A是L的一个公式。如果v和w都是赋值，并且对A中的每个自由变元xi，有v(xi)=w(xi)，那么v满足A，当且仅当，w满足A.证明：对A中的联结词和量词的数目施归纳。基础步骤：A是一个原子公式，例如A(t1,…,tn)。赋值v和w对出现在A中的所有自由变元和个体常元赋值都是一样的，所以对任意项ti(n

i1)，有v(ti)=w(ti)(为什么？请同学们在课后作业中证明)。又因为v和w对谓词A的赋值是一样的，所以v满足A，当且仅当，w满足A.第46页,共53页，2024年2月25日，星期天5.4有穷指派引理归纳步骤：情形1：A是

B情形2：A是BC

情形1，2易证，请同学们在课后作业中完成。情形3：A是xiB

假设v满足A，那么对于所有的与vi-等值的v’都满足B。现在，我们对赋值w，我们任意选择一个与wi-等值的赋值函数w’。由于xi在

xiB中不自由出现，所以只要个体变元y在xiB是自由的，就有w’(y)=v(y)。现在，我们对任意的w’，相应地构造v’如下：第47页,共53页，2024年2月25日，星期天5.4有穷指派引理

(1)v’(xi)=w’(xi)在xi这一点上

(2)v’(xj)=w’(xj)(ji)在xi这一点之外显然，对于B中出现的任意自由变元y，我们有w’(y)=v’(y)。（因为对

xiB

中出现的自由变元，我们已经有w’(y)=v(y)=v’(y)。所以。对于公式B来说，最多无非多增加一个自由变元xi

，但是根据v’的构造（1），显然我们就有了以上结论。）进一步，根据前面的结论——v’都是满足B的，根据归纳假设(条件1B中出现的任意自由变元y，我们有w’(y)=v’(y);条件2B比

xiB

结构简单)，有w’也，满足B。再根据w’的任意性和满足的定义，我们有w满足

xiB

。用类似方法可以证明：w满足

xiB

v满足

xiB。

第48页,共53页，2024年2月25日，星期天5.4有穷指派引理定理5.4.4：令A(xi