第五章：非形式的谓词演算.ppt

第五章：非形式的谓词演算荣立武5 非形式的谓词演算n我们首先来看下面一个论证：所有的人都是会死的，苏格拉底是人，苏格拉底是会死的。这个是一个直觉上有效的推理。但是，按照前面所讲的方法来分析，它的形式是：p,q所以r。显然，从命题演算的角度来看这不是一个有效的推理。原因在哪里呢？这种情况下，推理的有效性不是依赖于作为简单命题的前提和结论之间的关系，而依赖于命题各个组成部分之间的关系、依赖于这些命题本身的形式。5 非形式的谓词演算n一般来说，我们可以把它分析成以下形式：所有的A是B,a是A,所以,a是A。在这个推理形式中，有几个值得我们注意的地方：谓词变元A、B，个体变元a和量词“所有的”。一般的简单命题都具有“主词”和“谓词”，主词是命题要加以断定的事物，而谓词是指该事物具有的“属性”。我们来分析下列命题：5 非形式的谓词演算n在下列各命题中，主词是用红字标记的，余下的部分是谓词：n（a）苏格拉底苏格拉底是人。n（b）我我写书。n（c）平方为平方为1的数的数不是实数。n（d）世界世界给人以生存。n以后，我们用大写的英文字母A,B,C,表示谓词，用小写的英文字母a,b,c,表示主词。n相应地，以上命题(a)可以表示为H(s):H表示“是人”，s代表苏格拉底。命题(b)可以表示为B(i):B表示“写书”，i代表我。命题(c)可以表示为R(j):R表示“是实数”，j代表平方为1的数。命题(d)可以表示为L(w):L表示“给人以生存”，i代表世界。5 非形式的谓词演算n只要我们知道了简单命题如何按照这种形式翻译成符号语言，加上前面的知识，我们自然也就知道了复合命题如何翻译成这种符号语言。n现在的问题是：对于“所有人都是会死的”，这样的命题我们怎么办？这类命题的主词不是指称单个的对象，而是用量词“所有”赋予多个对象以某个性质。n我们参考数学符号体系中的常用方法。例如，说“每个整数都有素因子”就被翻译成“对于所有的x来说，如果x是整数，那么x就有素因子。”n类似地，“所有人都是会死的”也被翻译成“对于所有的x来说，如果x是人，那么x是会死的。”5 非形式的谓词演算n以后，为了记法上的方便，我们把这个命题记为“x(MxDx)”。其中：n（1）谓词M、D分别表示“是人”和“是会死的”。n（2）“”是全称量词符号，表示所有的意思。n（3）x是个体变元，当它没有被量词约束时，它表示不确定的主体，这个时候我们一般也称之为自由变元。自由变元的论域是不确定的。n（4）单个的全称量词符号是不完整的，当它和自由变元结合成“x”这样的形式，我们就表示自由变元x被全称量词“”约束了。在这里x就成为了约束变元，约束变元的论域是确定的。我们可以指定一个特定的论域，例如“全体自然数”。当没有指定特定论域时，我们就把论域看成是全域，即万事万物。5 非形式的谓词演算n（5）但是，仅仅是“x”仍然不是完整的公式，它仅仅表示“所有的事物”或“所有的数”。显然这样还不能完整地构成一个公式，从而表达一个全称命题。只有当它和谓词变元结合在一起才构成合式公式。例如：“xMx”表示“所有的事物是人”。或者限定x的论域是全体整数，我们用“xAx”表示“所有的整数都有素因子”，其中“A”表示“有素因子”。n请大家注意：如果x是全域中的不确定个体的话，那么这句话“所有的整数都有素因子”就翻译成“x(IxAx)”,其中“I”和“A”分别表示“是整数和”“有素因子”。5 非形式的谓词演算n一般来说，还有一个量词在我们把自然语言翻译成谓词符号语言时也是需要的：n例如：“有些猪是有翅膀的”。n我们一般可以把它看成：“至少存在有一个x使得x是一头猪并且x有翅膀”。n同样地，我们可以将这个命题翻译成：“x(PxWx)”，其中“P”和“W”分别表示“是一头猪”和“有翅膀”。n一般来说，“全称量词普通名词属性”翻译时我们使用蕴含联结词把前后两个谓词符号联结起来。“存在量词普通名词属性”翻译时我们使用合取联结词把前后两个谓词符号联结起来。5 非形式的谓词演算n请大家把以下自然语言翻译成谓词符号语言：(1)所有的鸟都会飞。(2)并非所有的鸟都会飞。(3)所有的鸟都不会飞。(4)并非所有的鸟都不会飞。(5)至少有一只鸟会飞。(6)并非至少有一只鸟会飞。(7)至少有一只鸟不会飞。(8)并非至少有一只鸟不会飞。(9)有一个整数大于其他所有整数。(10)所有的马都是动物，所以所有的马头都是动物头。n(1)-(8)论域是全域，B鸟，F会飞。(1)x(BxFx)；(2)x(BxFx)；(3)x(BxFx)；(4)x(BxFx)；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)。5 非形式的谓词演算n课后作业：n请把“没有一个人尊重不自重的人，并且没有一个人信任他不尊重的人。所以，一个不受尊重的人是不受任何人信任的。”翻译成谓词符号语言。n其中，论域为全域，M是人，R(x,y)x尊重y，（注：R(x,x)表示x自重），H(x,y)x信任y。5 非形式的谓词演算n现在我们来进一步考察(1)(8)：n直觉上，我们是用(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)等值置换n现在，我们比较“x(BxFx)”和“x(BxFx)”，我们发现：后者与前者的区别仅在于“x”代替了“x”。n这样我们据明白一个道理：“x”可以替换“x”；另一方面，“x”也可以替换“x”。5 非形式的谓词演算n因为直观上：n(1)“并非所有的x都不具有属性P”(xPx)等价于“存在有某个x具有属性P”(xPx)。n(2)“并非存在有某个x不具有属性P”(xPx)等价于“所有的x都具有属性P”(xPx)。n于是，存在量词和全称量词只需要有一个，另一个可以借助否定联结词相应地定义出来。n同样的道理:(1)x(BxFx)(8)x(BxFx)(3)x(BxFx)(6)x(BxFx)(4)x(BxFx)(5)x(BxFx)上面的证明，大家任意选做一个，写清楚理由！5 非形式的谓词演算n课后作业：把下列各命题写成符号形式。先不用存在量词，然后不用全称量词。（任意选择两个做）n（1）并非所有的汽车都是三只轮子。n（2）有些人或者是懒惰的，或者是愚蠢的。n（3）没有一只耗子比任何一只象重。n（4）每个数或者是负的或者有一平方根。n要求：把论域和谓词符号所代表的含义写清楚。5.1 一阶语言n 一阶符号语言由下列7类符号构成：（1）个体变元符号：x1,x2,xn,。（2）联结词符号：，。（3）量词符号：。（4）技术符号：(，)。（5）个体常元：a1,a2,an(,)。（6）函数符号：（7）谓词符号：注1：以后我们用 表示苏格拉底是人。其中个体常元表示苏格拉底，而一元谓词表示性质“是人”。5.1 一阶语言n注2：谓词符号的上标表明了谓词是几元谓词。如果是1就表示一个性质，如果是2就表示一个二元关系，如果是3就表示一个三元关系，如此类推。n注：函数符号的上标和谓词符号的上标解释差不多，表示函数所带参数的个数。不过请大家区别函数符号和谓词符号。n谓词符号可以看成这样一个函数：而函数符号则应看成：5.1 一阶语言n一般地，所有的个体变元的集合记为Var，所有的个体常元集记为Con。由(5)-(7)中的符号构成的集合称为L的特征符号集。一般情况下，我们固定(1)-(4)，而随着情况不同改变(5)-(7)。给定了一个特征符号集也就给定了一个语言的初始符号集。n我们在后面常常使用下列元语言符号：x,y,z表示个体变元；P,Q,R表示谓词符号；F,G,H表示函数符号；c,d,e表示个体常元。5.2 一阶语言L中项和原子公式的定义n为了定义一阶语言L中的合式公式，我们首先必须定义L中的项：（1）变元和个体常元是项；（2）如果 是L中的函数符号，且 是L中的项，则 也是L中的项。（3）所有的项都是按照（1）和（2）生成的。n项在形式语言中将被解释为对象，即函数作用于其上的事物，具有某种属性的事物，对之作出某种断定的事物。以后在元语言中，我们用t和u表示项。nL中的原子公式定义为：如果 是L中的一个谓词符号，是L中的项，则 是L中的原子公式。5.2 L中合式公式的定义n注：原子公式是语言中可断定的最简单的公式。例如，某些对象具有某种性质。这里“原子”一词当然是表示不能再分解了。nL中的一个合式公式的定义如下：（1）L中的每个原子公式是L中的合式公式。（2）如果A和B是L中的合式公式，则A，AB，xiA(其中xi是任意个体变元)也是合式公式。（3）L中的所有合式公式都是按照(1)和(2)生成的。注1：xiA 并不要求A中一定有个体变元xi的出现。5.2 L中合式公式的定义n注2：我们规定：xiA 是xiA 的缩写。AB是(AB)的缩写。AB是AB的缩写。n注3：我们要注意xi(AB)和xiAB之间的区别。为此，我们需要再引入一些相关的定义。n定义：在公式 xiA中，我们称A是量词的辖域辖域。更一般地，当xiA作为子公式出现在B中时，我们称这个量词在B中的辖域是A。n定义：变元xi在一个公式中的出现称为约束约束的，如果它出现在公式中的xi的辖域之内，或者xi在xi中。如果一个变元的出现不是约束的，那么我们就称它是自由自由的。5.2 辖域、约束变元和自由变元n例：请说明下列公式中量词的辖域，以及个体变元的每一次出现是约束的还是自由的。5.2 辖域、约束变元和自由变元n当我们仅仅对公式中的变元感兴趣时，我们常常有这种写法：A(x1)或B(x1,xn)。在这种情况中，我们一般指其中的变元是自由出现的。如果xi在A中确实是自由出现，那么对于任何项t，A(t)将指对xi的每次自由出现都代入t后所得到的结果。n下面我们解释一个比较重要的概念：令A是L中的任意公式，我们称项项t对对A中的个体变元中的个体变元xi是自由的是自由的，如果xi并不自由地出现在A的一个xj的辖域中，这里的xj是指出现在t中的任何变元。n粗略地说，所谓项对个体变元的自由指的是项可以代入A中的xi每个自由出现，而不引起和A中的量词相互作用。项对个体变元的代入n举例来说，（1）x3对公式 中的x2是自由的，而x1对公式中的x2则是不自由的。因为x2自由地出现在x1的辖域中，而x2并没有自由地出现在x3的辖域中（在这里有两个意思：或者x2没有出现在x3的辖域中，或者 x2出现在x3的辖域中，但是x2的出现是不自由的）。对于（1）中所举的例子来说，是因为x2没有出现在x3的辖域中。（2）也有可能出现x2约束地出现在x3的辖域中的情况，例如x3对公式 中的x2是自由的。因为在这个公式中没有x2的自由出现。项对个体变元的代入n由上不难看出，项t对公式A中的变元x是自由的，主要是看t对x在A中的自由出现进行代入是不是自由的。而对x的约束出现进行代入则没有太多的意义。就好像（2）中例子所看到的那样。课后作业：项对公式的替换定义项对公式的替换定义举例课后作业：5.3 解释n定义5.3.1：L的一个解释I是由以下几部分内容构成的：n（1）一个非空集DI（I的论域）；n（2）一个特别的元素集(a1),(a2),；n（3）一个在DI上的函数集 n（4）一个在DI上的关系集n我们的意图是：L中的变元将会被解释为“对象”，而集合DI将被解释为变元在其上取值的论域。特别的元素集将对应L中个体常元的取值。DI上的函数和关系将分别对应L中函数和 关系的解释。n注：以后为了方便，在不会引起混淆的情况下，我们不区分a1与(a1)5.3 解释n一阶语言：如果一个语言的解释中，量词仅仅作用于将被解释为“对象”的个体变元之上。n二阶语言：如果一个语言的解释中，量词不仅可以作用于将被解释为“对象”的个体变元之上，还可以作用于将被解释为对象关系的谓词变元之上。nN阶语言：如果一个语言的解释中，量词可以作用于将被解释为N1阶关系之间的关系之上。n一阶符号语言系统又可称为一阶逻辑，二阶以上的符号语言系统统称为高阶逻辑。在本课程中，我们只讨论一阶逻辑。5.3 解释n举例：n（1）用一阶语言表示有关自然数的算术命题。n解释I：论域DI 0,1,2,；特别元素只有一个0，它将被解释为个体常元a1所对应的对象；n于是，在这样一个解释I下，公式（1）n 将被解释为：对于所有的自然数x,y来说，并非对所有的自然数z，都有x+yz。5.3 解释n另一方面，我们知道上述公式逻辑等值于：n这个公式将被解释为：对于所有的自然数x,y来说，存在有一个自然数z，使得x+y=z。n但是，我们要注意到一阶语言不能表达这样的算术命题“每个非空的自然数集都有一个最小数”，显然在描述这个命题是，我们不得不将全称量词作用于自然数集，这样的表述将成为二阶语言中的一个公式。n只有当一个语言被给定一个解释之后，我们才能对有关公式的意义说些什么。也就是说，只有在5.3 解释n一个解释下，才能考察这个公式的真假。上述公式（1）在解释I下显然是假的。但是，我们可以给这个公式另一种解释I使得它为真。n在解释I下DI是正有理数，n这样，公式（1）将会被解释为：对任意的有理数x,y来说，存在有有理数z使得xy=z.显然这个命题是真的。5.3 解释n课后作业：5.4 满足和真n正如命题逻辑系统PC中的讨论一样（只有对命题公式中的命题变元指派真值，命题公式才会有真假），在谓词逻辑中，一阶公式只有在一个具体的解释下才有真假。在这里，解释相当于命题逻辑系统中所介绍的赋值（指派）。n令I是以DI为论域的语言L上的一个解释。n定义5.4.1：I上的一个赋值是一个从L的项集到集DI具有下列性质的一个函数v：（1）v(ai)=(ai),对于L中的每个个体常元ai；（2）5.4 满足和真n赋值是这样一个规则：它给语言L中的每一个项指派了DI中的一个对象作为它的解释。n注记：（1）在一个给定的解释下，将有多种不同的赋值。因为对于个体变元总有不同赋值的可能。（2）一给定的赋值将对L中的每一个变元xi指派DI中的一个元素。因此，如果对L中个体变元的赋值被确定了，那么这个赋值也被确定下来了。这是因为个体常元和复杂项都在5.4.1.(1)和(2)中被指派了DI中的一个元素。其中(2)是对复杂项的指派的归纳定义。n下面我们介绍一个后面经常会用到的定义i-等值：等值：称两个赋值v和v是i-等值，如果v(xj)=v(xj)，对每个ij.即：两个赋值只有在xi上可能不同（也可能相同，一般情况下是不同的）。5.4 满足和真n现在我们来考察在一个解释和赋值之下，一阶公式的满足。n定义5.4.2:n令A是L的一个公式，I是L的一个解释。I中的一个赋值v称为满足A，记为vI(A)=1(在不混淆的情况下记为v(A)=1)，如果n(1)如果A是原子公式n(2)如果A是“B”这样的形式，那么v(A)=1当且仅当v(B)1（这也就是说，v不满足B，当且仅当v就满足B）n(3)如果A是“BC”这样的形式，那么v(BC)=1，当且仅当，或者v(B)1或者v(C)=1（即或者v不满足B或者v满足C）。5.4 满足和真n(4)解释I中的一个赋值v满足当且仅当，每个i-等值于v的赋值v满足B,注：我们有必要对(4)做出一些解释：首先，我们说I中的赋值v满足一个公式 是这个意思：对于任意DI中的对象d，I中的赋值v都会满足公式 ，其中对象d是个体常元d在I下的解释。但是，怎么表示DI中的任意对象d，这就得要引入前面的与v i-等值的赋值v了。由于v和v的唯一区别是在xi的赋值上有不同，因此引入v的意图就在于可以给xi赋值不同的DI中的对象，而其他5.4 满足和真n的情况则保持不变。如果在任意的与v i-等值的赋值v下，公式 都有 （其中个体常元c替换个体变元xi表示在赋值v下xi将被解释为论域中的对象c。当然我们也可以选择a,b,e,替换xi，这正是其他与v i-等值的赋值所干的事情。）假如所有的与v i-等值的赋值都有使得 （d*表示某个个体常元），则我们前面所说的意思已经充分地表达出来了。5.4 满足和真n例：n（1）算术解释N：论域DI 0,1,2,；个体常元a1被解释为0；在解释N的一个赋值v下:v(x1)=2,v(x1)=6,v(x1)=3,v(x1)=4。显然，赋值下v满足公式（1）因为2634.5.4 满足和真n例2：在解释N中被解释为：对任意的自然数n，nm=mn。这显然是一个真命题。现在我们面对的一个问题是：公式（2）是可以从公式（1）中可推导出来的，或者说，公式（1）是否逻辑蕴涵公式（2）呢？n分析步骤1：令v是N中的任意一个赋值，显然v(x1)和v(x2)是自然数，因此公式（1）被解释为v(x1)v(x2)v(x2)v(x1)，而这显然是真的。n分析步骤2：对任意与v 1-等值的赋值v来说，v无非是要改变v对于x1的赋值。但是，无论如何5.4 满足和真nv(x1)仍然是一个自然数，因此v(x1)v(x2)v(x2)v(x1)仍然是真的。这意味着对任意与v 1-等值的赋值v，都有 成立，所以根据定义5.4.2.(4)我们有结论：赋值v在解释N下满足公式（2），再由于赋值v的任意性，解释N下所有的赋值都满足公式（2）。n同理可证，在解释N下的所有赋值都满足这个公式。5.4 满足和真n例3：在解释N下是什么意思，请大家思考解释N下是否有赋值v是否满足公式 。n不难发现，以后用另外的项或者变元去替代一个变元是经常用到的技巧，因此，以下定理是必须的。5.4 有穷指派引理n1 命题逻辑中的有穷指派引理：令p1,pn是命题公式A中出现的所有命题变元所构成的集合，假如v和u分别是对A的任意两组真值指派(赋值函数)，并且有v(p1)=u(p1),v(pn)=u(pn)，那么v(A)=u(A)。证明思路：施归纳于公式A的结构易证。其中我们会用到赋值函数的定义。这个证明比较简单，请同学们作为课后作业完成。有穷指派引理旨在说明：一个赋值函数对于命题公式A的真值的影响仅仅在于它给A中出现的命题变元指派怎样的真值，而与A中不出现的命题变元被指派什么真值无关。5.4 有穷指派引理n循着这样的思路，我们试图考察对一阶公式是不是也存在有类似的有穷指派引理呢？n谓词逻辑中的有穷指派引理旨在表明：在一个确定的解释下，一个赋值函数v是否满足一阶公式A，仅仅取决于v给A中出现的自由变元的赋值是什么，而与A中不出现的自由变元或A中约束出现的自由变元无关。5.4 有穷指派引理n定理5.4.3：令I是L的一个解释，A是L的一个公式。如果v和w都是赋值，并且对A中的每个自由变元xi，有v(xi)=w(xi)，那么v满足A，当且仅当，w满足A.n证明：对A中的联结词和量词的数目施归纳。n基础步骤：A是一个原子公式，例如A(t1,tn)。赋值v和w对出现在A中的所有自由变元和个体常元赋值都是一样的，所以对任意项ti(ni1)，有v(ti)=w(ti)(为什么？请同学们在课后作业中证明)。又因为v和w对谓词A的赋值是一样的，所以v满足A，当且仅当，w满足A.5.4 有穷指派引理n归纳步骤：n情形1：A是Bn情形2：A是BC 情形1，2易证，请同学们在课后作业中完成。n情形3：A是xiB 假设v满足A，那么对于所有的与v i-等值的v都满足B。现在，我们对赋值w，我们任意选择一个与w i-等值的赋值函数w。由于xi在xiB中不自由出现，所以只要个体变元y在xiB是自由的，就有w(y)=v(y)。现在，我们对任意的w，相应地构造v如下：5.4 有穷指派引理 (1)v(xi)=w(xi)在xi这一点上 (2)v(xj)=w(xj)(ji)在xi这一点之外n显然，对于B中出现的任意自由变元y，我们有w(y)=v(y)。（因为对xiB 中出现的自由变元，我们已经有w(y)=v(y)=v(y)。所以。对于公式B来说，最多无非多增加一个自由变元xi，但是根据v的构造（1），显然我们就有了以上结论。）n进一步，根据前面的结论v都是满足B的，根据归纳假设(条件1 B中出现的任意自由变元y，我们有w(y)=v(y);条件2 B比xiB 结构简单)，有w也，满足B。再根据w的任意性和满足的定义，我们有w满足xiB。n用类似方法可以证明：w满足xiB v满足xiB。5.4 有穷指派引理n定理5.4.4：令A(xi)是L中的一个公式，其中xi自由出现，并且令t是对A(xi)中的xi自由的项。假设v是一赋值，并且v是i-等值于v的赋值，并且有v(xi)=v(t)。那么v满足A(xi/t)当且仅当 v满足A(xi)。n这个定理可以看成是5.4.3的一个推论，它的意思是如果有v(xi)=v(t)，即令所有的与v i-等值的那些赋值函数v让它们对自由变元xi的赋值都等于v(t)；那么这样的v(固定了xi在其中的解释是v(t)是否满足公式A(xi)(xi在A自由出现)，当且仅当，v是否满足公式A(xi/t)(在这个公式中已经没有了自由变元xi，它被t全部替代了，显然t在v下的解释是v(t).5.4 有穷指派引理n这个证明会比5.4.3显得更复杂，我们略过不讲。有兴趣的同学课自己课后证明。5.4 满足和真n定义5.5.5:一个公式A在解释I中称为真的，如果I中的每个赋值都满足A。一个公式A在解释I中称为假的，如果不存在有I中的任何一个赋值使得它满足A。n记法：I|=A，表示A在I中为真。I|A，表示A在I中不为真，但不一定就表示A在I中就一定是假的，可能A在I中即不真也不假。n注记：（1）有些公式在I中即不真又不假。（2）一个解释的论域是非空的，因而给定的赋值也是非空的。根据赋值定义，一个赋值或者满足A或者不满足A。因此，一个公式在I中不可能是即真又假的5.4 满足和真n注记：（3）在一个给定的解释中，一公式A为假，当且仅当A是真的。根据真和赋值的定义显然。（4）在一给定解释I中，AB为假，当且仅当，A真并且B假。“”AB为假。对于I下的任何赋值v都不满足AB，即v(AB)=0。根据赋值的定义5.4.2.(3)，有v(A)=1且v(B)=0。再根据v的任意性，有A在I下为真且B在I下为假。“”以上证明步骤都是当且仅当关系，所以逆转就是另外一个方向的证明。5.4 满足和真n一阶语义中的MP规则（这为一阶语言中引入MP这个推导规则提供了语义上的理由）：n定理5.5.6：如果在一特殊解释I下，公式A和AB都是真的，那么B也是真的。n易证，请同学们课后自己在课后作业中完成。n一阶语义中的全称添加规则（这为一阶语言中引入全称添加这个推导规则提供了语义上的理由）n定理5.5.7：令A是L中的一个公式，并且；令I是L的一个解释，那么I|=A，当且仅当，I|=xiA，其中xi是任意个体变元。