非形式的谓词演算.ppt

《非形式的谓词演算.ppt》由会员分享，可在线阅读，更多相关《非形式的谓词演算.ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、非形式的谓词演算现在学习的是第1页，共53页5 非形式的谓词演算n我们首先来看下面一个论证：所有的人都是会死的，苏格拉底是人，苏格拉底是会死的。这个是一个直觉上有效的推理。但是，按照前面所讲的方法来分析，它的形式是：p,q所以r。显然，从命题演算的角度来看这不是一个有效的推理。原因在哪里呢？这种情况下，推理的有效性不是依赖于作为简单命题的前提和结论之间的关系，而依赖于命题各个组成部分之间的关系、依赖于这些命题本身的形式。现在学习的是第2页，共53页5 非形式的谓词演算n一般来说，我们可以把它分析成以下形式：所有的A是B,a是A,所以,a是A。在这个推理形式中，有几个值得我们注意的地方：谓词变元

2、A、B，个体变元a和量词“所有的”。一般的简单命题都具有“主词”和“谓词”，主词是命题要加以断定的事物，而谓词是指该事物具有的“属性”。我们来分析下列命题：现在学习的是第3页，共53页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代表我。命题

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

4、被翻译成“对于所有的x来说，如果x是人，那么x是会死的。”现在学习的是第5页，共53页5 非形式的谓词演算n以后，为了记法上的方便，我们把这个命题记为“x(MxDx)”。其中：n（1）谓词M、D分别表示“是人”和“是会死的”。n（2）“”是全称量词符号，表示所有的意思。n（3）x是个体变元，当它没有被量词约束时，它表示不确定的主体，这个时候我们一般也称之为自由变元。自由变元的论域是不确定的。n（4）单个的全称量词符号是不完整的，当它和自由变元结合成“x”这样的形式，我们就表示自由变元x被全称量词“”约束了。在这里x就成为了约束变元，约束变元的论域是确定的。我们可以指定一个特定的论域，例如“全体

5、自然数”。当没有指定特定论域时，我们就把论域看成是全域，即万事万物。现在学习的是第6页，共53页5 非形式的谓词演算n（5）但是，仅仅是“x”仍然不是完整的公式，它仅仅表示“所有的事物”或“所有的数”。显然这样还不能完整地构成一个公式，从而表达一个全称命题。只有当它和谓词变元结合在一起才构成合式公式。例如：“xMx”表示“所有的事物是人”。或者限定x的论域是全体整数，我们用“xAx”表示“所有的整数都有素因子”，其中“A”表示“有素因子”。n请大家注意：如果x是全域中的不确定个体的话，那么这句话“所有的整数都有素因子”就翻译成“x(IxAx)”,其中“I”和“A”分别表示“是整数和”“有素因子

6、”。现在学习的是第7页，共53页5 非形式的谓词演算n一般来说，还有一个量词在我们把自然语言翻译成谓词符号语言时也是需要的：n例如：“有些猪是有翅膀的”。n我们一般可以把它看成：“至少存在有一个x使得x是一头猪并且x有翅膀”。n同样地，我们可以将这个命题翻译成：“x(PxWx)”，其中“P”和“W”分别表示“是一头猪”和“有翅膀”。n一般来说，“全称量词普通名词属性”翻译时我们使用蕴含联结词把前后两个谓词符号联结起来。“存在量词普通名词属性”翻译时我们使用合取联结词把前后两个谓词符号联结起来。现在学习的是第8页，共53页5 非形式的谓词演算n请大家把以下自然语言翻译成谓词符号语言：(1)所有的

7、鸟都会飞。(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)；现在学习的是第9页，共53页5 非形式的谓词演算(5)x(BxFx)；(6)x(BxFx)；(7)x(BxFx)；(8)x(BxFx)；(9)论域为全域，I整数，LI(x,y)xy。x(I

8、xy(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页5 非形式的谓词演算n课后作业：n请把“没有一个人尊重不自重的人，并且没有一个人信任他不尊重的人。所以，一个不受尊重的人是不受任何人信任的。”翻译成谓词符号语言。n其中，论域为全域，M是人，R(x,y)x尊重y，（注：R(x,x)表示x自重），H(x,y)x信任y。现在学习

9、的是第11页，共53页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”。现在学习的是第12页，共53页5 非形式的谓词演算n因为直观上：

10、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)上面的证明，大家任意选做一个，写清楚理由！现在学习的是第13页，共53页5 非形式的谓词演算n课后作业：把下列各命题写成符号形式。先不用存在量词，然后不用全称量词。（任意选择两个做）n（1）并非所有的汽

11、车都是三只轮子。n（2）有些人或者是懒惰的，或者是愚蠢的。n（3）没有一只耗子比任何一只象重。n（4）每个数或者是负的或者有一平方根。n要求：把论域和谓词符号所代表的含义写清楚。现在学习的是第14页，共53页5.1 一阶语言n 一阶符号语言由下列7类符号构成：（1）个体变元符号：x1,x2,xn,。（2）联结词符号：，。（3）量词符号：。（4）技术符号：(，)。（5）个体常元：a1,a2,an(,)。（6）函数符号：（7）谓词符号：注1：以后我们用 表示苏格拉底是人。其中个体常元表示苏格拉底，而一元谓词表示性质“是人”。112233121212,.,.,.,.ffffff11223312121

12、2,.,.,.,.A AAAA A111()Aa现在学习的是第15页，共53页5.1 一阶语言n注2：谓词符号的上标表明了谓词是几元谓词。如果是1就表示一个性质，如果是2就表示一个二元关系，如果是3就表示一个三元关系，如此类推。n注：函数符号的上标和谓词符号的上标解释差不多，表示函数所带参数的个数。不过请大家区别函数符号和谓词符号。n谓词符号可以看成这样一个函数：而函数符号则应看成：12:(,.,)0,1nmnAbbb12:(,.,)nmnifb bbbi其中为任意自然数现在学习的是第16页，共53页5.1 一阶语言n一般地，所有的个体变元的集合记为Var，所有的个体常元集记为Con。由(5)

13、-(7)中的符号构成的集合称为L的特征符号集。一般情况下，我们固定(1)-(4)，而随着情况不同改变(5)-(7)。给定了一个特征符号集也就给定了一个语言的初始符号集。n我们在后面常常使用下列元语言符号：x,y,z表示个体变元；P,Q,R表示谓词符号；F,G,H表示函数符号；c,d,e表示个体常元。现在学习的是第17页，共53页5.2 一阶语言L中项和原子公式的定义n为了定义一阶语言L中的合式公式，我们首先必须定义L中的项：（1）变元和个体常元是项；（2）如果 是L中的函数符号，且 是L中的项，则 也是L中的项。（3）所有的项都是按照（1）和（2）生成的。n项在形式语言中将被解释为对象，即函数

14、作用于其上的事物，具有某种属性的事物，对之作出某种断定的事物。以后在元语言中，我们用t和u表示项。nL中的原子公式定义为：如果 是L中的一个谓词符号，是L中的项，则 是L中的原子公式。kjA1,.,nttnif1,.,ktt1(,.,)ninftt1(,.,)kjkA tt现在学习的是第18页，共53页5.2 L中合式公式的定义n注：原子公式是语言中可断定的最简单的公式。例如，某些对象具有某种性质。这里“原子”一词当然是表示不能再分解了。nL中的一个合式公式的定义如下：（1）L中的每个原子公式是L中的合式公式。（2）如果A和B是L中的合式公式，则A，AB，xiA(其中xi是任意个体变元)也是合

15、式公式。（3）L中的所有合式公式都是按照(1)和(2)生成的。注1：xiA 并不要求A中一定有个体变元xi的出现。现在学习的是第19页，共53页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中。如果一个变元的出现不是约束的

16、，那么我们就称它是自由自由的。现在学习的是第20页，共53页5.2 辖域、约束变元和自由变元n例：请说明下列公式中量词的辖域，以及个体变元的每一次出现是约束的还是自由的。1112211211212211112212(1)();(2)(,)();(3)(,)().x A xxxAx xA xx Ax xx A x 现在学习的是第21页，共53页5.2 辖域、约束变元和自由变元n当我们仅仅对公式中的变元感兴趣时，我们常常有这种写法：A(x1)或B(x1,xn)。在这种情况中，我们一般指其中的变元是自由出现的。如果xi在A中确实是自由出现，那么对于任何项t，A(t)将指对xi的每次自由出现都代入t后

17、所得到的结果。n下面我们解释一个比较重要的概念：令A是L中的任意公式，我们称项项t对对A中的个体变元中的个体变元xi是自由的是自由的，如果xi并不自由地出现在A的一个xj的辖域中，这里的xj是指出现在t中的任何变元。n粗略地说，所谓项对个体变元的自由指的是项可以代入A中的xi每个自由出现，而不引起和A中的量词相互作用。现在学习的是第22页，共53页项对个体变元的代入n举例来说，（1）x3对公式 中的x2是自由的，而x1对公式中的x2则是不自由的。因为x2自由地出现在x1的辖域中，而x2并没有自由地出现在x3的辖域中（在这里有两个意思：或者x2没有出现在x3的辖域中，或者 x2出现在x3的辖域中

18、，但是x2的出现是不自由的）。对于（1）中所举的例子来说，是因为x2没有出现在x3的辖域中。（2）也有可能出现x2约束地出现在x3的辖域中的情况，例如x3对公式 中的x2是自由的。因为在这个公式中没有x2的自由出现。1112()x A x13212()xx A x 现在学习的是第23页，共53页项对个体变元的代入n由上不难看出，项t对公式A中的变元x是自由的，主要是看t对x在A中的自由出现进行代入是不是自由的。而对x的约束出现进行代入则没有太多的意义。就好像（2）中例子所看到的那样。2211123231211422121141222322232223122113131(,)(,)(,)(,)(

19、,)(,)(,)Ax Ax xx Ax xfx xxxxfx xxfx xxxxxfx xxxxxfx xx令 则对 是不自由的（自由地出现在的辖域中）对 是自由的；对 是自由的（没有自由地出现在或的辖域中）对 是不自由的；对 是自由的（注意 仅自由出现一次）；对 是不自由的。现在学习的是第24页，共53页课后作业：12221121211313121121121112112222221112112321221132(,)(,).()(,).()(,).(4)(,),)(,(,).(,)ixxAxxAxaAxxx Axxax Axx AxxxAfxxxx AxfxxfxxxA x 1.下列公式中

20、的哪些出现是自由的，哪些是约束的。（1）（(2)(3)项对哪些公式中的是自由的。2.令()是L中ijijiiijjjiijxxA xxA xxxA xxA xA xxx一公式，其中 自由出现，令是在公式()中并不自由出现的一变元。证明：如果对()中是自由的，那么对()中也是自由的。其中，()是对()中的每次自由出现代入后得到的结果。现在学习的是第25页，共53页项对公式的替换定义11111111111111,.,.,(/,.,/),.,.,(,.,),(/,.,/)(/,.,/,.,/,.,/),nnnnnnnnnnnnnnxxttAA xtxtttAxxAP uuA xtxtP uxtxtu

21、xtxtAB 令两 两 不 同，令是 项，且 令是 公 式。我 们 用表 示 用同 时 替 换中的 所 有 自 由 出 现 而 得 到 的 结 果。（1）若则 （）（）（2）若111111111111(/,.,/)(/,.,/).,.,(/,.,/)/,.,/(1),.,(/,.,/)nnnnnnnnniinnnA xtxtB xtxtABCAxBxxxA xtxtxB xtxtAx BinxxxA xtxt则 的 情 况 也 是 如 此。（3）若且则 （）.（4）若即则 111111/,.,/,/,.,/iiiiinniix B xtxtxtxtx Bx（）(也 就 是 说，对 公 式中出

22、现 的 地 方 不 进 行 替 换)。现在学习的是第26页，共53页项对公式的替换定义举例22112211221121(,(,)(/(),/,/)(/(),/,/),(/(),/,/),(/(),/,/)(),(,)(/(),/,/)(/,/)(,)Px Fz yx G yy z z yPx x G yy z z y Fz x G yy z z yy x G yy z z yP G y Fy zx G yy z z yy y z z yzyyPx yxQ （1）注意：中的替换仅对符合的情况替换一次，不要重复进行。例如而不是。（2）(3123112311(,)(/,/,/)(,)(/,/,/)(

23、,)(/,/,/)(,)(,)x y zx z y x z uy Px yx z y x z ux Qx y zx z y x z uyPz yxQx x u 现在学习的是第27页，共53页课后作业：1211312212121121111131311113211231123312111123()(,).(),(,(,)()()()()(,)(,(),)A xtfxxA ttxx AxfxxAxxxAxAxx Afxx AxxxxAxfxxx A 1.在 下 列 情 况 中，令是 给 定 的 公 式，并 且 令 是 项 写 出 公 式并 且 判 定，在 每 种 情 况 下，对 给 定 公 式 中

24、 的是 否 自 由。(1)(2)(3)(4)12111323211131123(,)2.(,)(,)fxxxxfaxfxxx对 下 面 的 项 重 做 练 习 1（a）(b)(c)(d)现在学习的是第28页，共53页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中函数和 关系的

25、解释。n注：以后为了方便，在不会引起混淆的情况下，我们不区分a1与(a1)0,0niAin()，其中0,0nifin()，其中()nnnniiiiffAA与()，以及与。但是，我们要记住：前者是对象语言中的符号，而后者是元语言中的符号。现在学习的是第29页，共53页5.3 解释n一阶语言：如果一个语言的解释中，量词仅仅作用于将被解释为“对象”的个体变元之上。n二阶语言：如果一个语言的解释中，量词不仅可以作用于将被解释为“对象”的个体变元之上，还可以作用于将被解释为对象关系的谓词变元之上。nN阶语言：如果一个语言的解释中，量词可以作用于将被解释为N1阶关系之间的关系之上。n一阶符号语言系统又可称

26、为一阶逻辑，二阶以上的符号语言系统统称为高阶逻辑。在本课程中，我们只讨论一阶逻辑。现在学习的是第30页，共53页5.3 解释n举例：n（1）用一阶语言表示有关自然数的算术命题。n解释I：论域DI 0,1,2,；特别元素只有一个0，它将被解释为个体常元a1所对应的对象；n于是，在这样一个解释I下，公式（1）n 将被解释为：对于所有的自然数x,y来说，并非对所有的自然数z，都有x+yz。21112212Afff解释为“”，将被解释为后继函数，将被解释为“”，将被解释为“”.2212311132(,),)xxxAfxxx现在学习的是第31页，共53页5.3 解释n另一方面，我们知道上述公式逻辑等值于

27、：n这个公式将被解释为：对于所有的自然数x,y来说，存在有一个自然数z，使得x+y=z。n但是，我们要注意到一阶语言不能表达这样的算术命题“每个非空的自然数集都有一个最小数”，显然在描述这个命题是，我们不得不将全称量词作用于自然数集，这样的表述将成为二阶语言中的一个公式。n只有当一个语言被给定一个解释之后，我们才能对有关公式的意义说些什么。也就是说，只有在2212311132(,),)xxx Afx xx 现在学习的是第32页，共53页5.3 解释n一个解释下，才能考察这个公式的真假。上述公式（1）在解释I下显然是假的。但是，我们可以给这个公式另一种解释I使得它为真。n在解释I下DI是正有理数

28、，n这样，公式（1）将会被解释为：对任意的有理数x,y来说，存在有有理数z使得xy=z.显然这个命题是真的。21122121aAff是 的解释，解释为“”，将被解释为“”，将被解释为“/”现在学习的是第33页，共53页5.3 解释n课后作业：221222212211212122122,(,),0LafAxx A fx xaA x xafA 11令 是一阶语言，特征符号包括个体常元函数字母和谓词字母.现在有公式（2）：（）（）现在给定一个解释如下：定义域是整数集，被解释为，解释为减号，被解释为小于关系。请问这个公式在这个解释下为真还是为假？请构造另一个解释使得这个公式取相反的真值。现在学习的是第

29、34页，共53页5.4 满足和真n正如命题逻辑系统PC中的讨论一样（只有对命题公式中的命题变元指派真值，命题公式才会有真假），在谓词逻辑中，一阶公式只有在一个具体的解释下才有真假。在这里，解释相当于命题逻辑系统中所介绍的赋值（指派）。n令I是以DI为论域的语言L上的一个解释。n定义5.4.1：I上的一个赋值是一个从L的项集到集DI具有下列性质的一个函数v：（1）v(ai)=(ai),对于L中的每个个体常元ai；（2）11(,.,)()(),.,().nnininv fttfv tv t,.,;:;nnnniiiiiinnniIiIIiIafAIafAi aDfDDADn在 中的解释将分别指()

30、()()其中，对任意()()()是上的 元关系。现在学习的是第35页，共53页5.4 满足和真n赋值是这样一个规则：它给语言L中的每一个项指派了DI中的一个对象作为它的解释。n注记：（1）在一个给定的解释下，将有多种不同的赋值。因为对于个体变元总有不同赋值的可能。（2）一给定的赋值将对L中的每一个变元xi指派DI中的一个元素。因此，如果对L中个体变元的赋值被确定了，那么这个赋值也被确定下来了。这是因为个体常元和复杂项都在5.4.1.(1)和(2)中被指派了DI中的一个元素。其中(2)是对复杂项的指派的归纳定义。n下面我们介绍一个后面经常会用到的定义i-等值：等值：称两个赋值v和v是i-等值，如

31、果v(xj)=v(xj)，对每个ij.即：两个赋值只有在xi上可能不同（也可能相同，一般情况下是不同的）。现在学习的是第36页，共53页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不满

32、足B或者v满足C）。11(,.,),()(),.,()()1,nnjnjnIA ttAv tv tDv A在中为真,当且仅当现在学习的是第37页，共53页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中的对象，而其

33、他()1)iix Bvx B即()1ivx Bix B(/)iB xd现在学习的是第38页，共53页5.4 满足和真n的情况则保持不变。如果在任意的与v i-等值的赋值v下，公式 都有 （其中个体常元c替换个体变元xi表示在赋值v下xi将被解释为论域中的对象c。当然我们也可以选择a,b,e,替换xi，这正是其他与v i-等值的赋值所干的事情。）假如所有的与v i-等值的赋值都有使得 （d*表示某个个体常元），则我们前面所说的意思已经充分地表达出来了。(/)iB xc(/)1iv B xc(/*)1iv B xd现在学习的是第39页，共53页5.4 满足和真n例：n（1）算术解释N：论域DI 0

34、,1,2,；个体常元a1被解释为0；在解释N的一个赋值v下:v(x1)=2,v(x1)=6,v(x1)=3,v(x1)=4。显然，赋值下v满足公式（1）因为2634.211122122221212234(,),(,)AfffAfx xfx x解释为“”，将被解释为后继函数，将被解释为“”，将被解释为“”.对于公式（1）来说：现在学习的是第40页，共53页5.4 满足和真n例2：在解释N中被解释为：对任意的自然数n，nm=mn。这显然是一个真命题。现在我们面对的一个问题是：公式（2）是可以从公式（1）中可推导出来的，或者说，公式（1）是否逻辑蕴涵公式（2）呢？n分析步骤1：令v是N中的任意一个赋

35、值，显然v(x1)和v(x2)是自然数，因此公式（1）被解释为v(x1)v(x2)v(x2)v(x1)，而这显然是真的。n分析步骤2：对任意与v 1-等值的赋值v来说，v无非是要改变v对于x1的赋值。但是，无论如何22211212221(,),(,)x Afxxfxx公式（2）现在学习的是第41页，共53页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同理可

36、证，在解释N下的所有赋值都满足这个公式。2221212221(,),(,)Afx xfx x222121212221(,),(,)xx Afxxfxx现在学习的是第42页，共53页5.4 满足和真n例3：在解释N下是什么意思，请大家思考解释N下是否有赋值v是否满足公式 。n不难发现，以后用另外的项或者变元去替代一个变元是经常用到的技巧，因此，以下定理是必须的。2111(,)Ax a21111(,)x A x a现在学习的是第43页，共53页5.4 有穷指派引理n1 命题逻辑中的有穷指派引理：令p1,pn是命题公式A中出现的所有命题变元所构成的集合，假如v和u分别是对A的任意两组真值指派(赋值函

37、数)，并且有v(p1)=u(p1),v(pn)=u(pn)，那么v(A)=u(A)。证明思路：施归纳于公式A的结构易证。其中我们会用到赋值函数的定义。这个证明比较简单，请同学们作为课后作业完成。有穷指派引理旨在说明：一个赋值函数对于命题公式A的真值的影响仅仅在于它给A中出现的命题变元指派怎样的真值，而与A中不出现的命题变元被指派什么真值无关。现在学习的是第44页，共53页5.4 有穷指派引理n循着这样的思路，我们试图考察对一阶公式是不是也存在有类似的有穷指派引理呢？n谓词逻辑中的有穷指派引理旨在表明：在一个确定的解释下，一个赋值函数v是否满足一阶公式A，仅仅取决于v给A中出现的自由变元的赋值是

38、什么，而与A中不出现的自由变元或A中约束出现的自由变元无关。现在学习的是第45页，共53页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.现在学习

39、的是第46页，共53页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如下：现在学习的是第47页，共53页5.4 有穷指派引理 (1)v(xi)=w(xi)在xi这一点上 (2)v(xj)=w(xj)(ji)在xi这一点之外n显然，对于B中出现的任意自由变元y，我们有w(

40、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。现在学习的是第48页，共53页5.4 有穷指派引理n定理5.4.4：令A(xi)是L中的一个公式，其中xi自由出现，并且令t是对A(xi)中的x

41、i自由的项。假设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).现在学习的是第49页，共53页5.4 有穷指派引理n这个证明会比5.4.3显得更复杂，我

42、们略过不讲。有兴趣的同学课自己课后证明。现在学习的是第50页，共53页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中不可能是即真又假的现在学习的是第51页，共53页5.4 满足和真n注记：（

43、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下为假。“”以上证明步骤都是当且仅当关系，所以逆转就是另外一个方向的证明。现在学习的是第52页，共53页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是任意个体变元。现在学习的是第53页，共53页