量词转换律

第二章谓词逻辑第四讲两个谓词公式的个体变元必须有相同的个体域才能讨论其是否等价。回顾定义2-13两个有相同个体域E的谓词公式A和B，若对两个谓词公式所有变元的任一组赋值，所得命题真值相同，则称这两个谓词公式在指定个体域E上等价。记为。BA（一）命题公式的推广BABA)()()()(xQxPxQxPBABA)()()())()((xQxPxQxPBABA)()()()(xxQxxPxxQxxPBABA)()()())()((xxQxxPxxQxxP（二）量词转换律)()(xPxxxP)()(xPxxxP我们将否定符移到量词后面时，全称量词变为存在量词，存在量词变为全称量词。反之，量词后面的否定符移到量词的前面时，也要作相应的改变，这种量词与否定的关系是普遍成立的，人们习惯称之为量词转换律（三）量词辖域的扩张和收缩（1）若量词辖域中是合取式或析取式，则不受约束的谓词公式可以直接进入和退出该辖域。（2）若量词辖域是条件命题的前件，则作为后件的不受约束的谓词公式不能直接进出该辖域。（3）若量词辖域是条件命题后件，则作为前件不受约束的谓词公式可以直接进出该辖域。))(()(BxAxBxxA))(()(BxAxBxxA（四）含量词的合取式、析取式的等价式（1）全称量词可以对合取式进行分配.)()())()((xxBxxAxBxAx（2）存在量词可对析取式进行分配。)()())()((xxQxxPxQxPx【说明】全称量词可以合取式进行分配，存在量词可以对析取式进行分配，但全称量词不能对析取式进行分配，存在量词不能对合取式进行分配。由以上四点我们可以得到一组常用的谓词等价公式如下：)()(xPxxxP)()(xPxxxP)()())()((xxBxxAxBxAx)()())()((xxQxxPxQxPxBxxABxAx)())((BxxABxAx)())((BxxABxAx)())((BxxABxAx)())(())(()(BxAxBxxA))(()(BxAxBxxA))(()(xABxxxAB))(()(xABxxxABE16E17E18E19E20E21E22E23E24E25E26E27下求下列各式的真值。在一元谓词个体域为：：设解释练习IxxRxxGxxFDI;7:)(,5:)(,3:)(;6,3,21)()()3()()()2()()()1(xGxFxxFxRxxGxFx)()()()(21naFaFaFxxF)()()()(21naFaFaFxxF下的真值：试求下列公式在是如下一个解释：：设练习IGGGGFFffaDI;1)3,3(,1)2,3(,1)3,2(,1)2,2(,1)3(,0)2(,2)3(,3)2(,2;3,22),()()1(axGxFx)(,)()2(xfxGxfFx公式的量词：消去下列：已知个体域练习},,,{3cbaD)).()(()3));()(()2);()()1xQxPxxSxRxxxSxxR课后作业•P54：2.6（2）•2.10（1）•2.12（1）2.5谓词演算中的永真蕴含公式定义2-18设P、Q为谓词公式，若P→Q为永真式，则称P永真蕴含Q，简称为P蕴含Q，记为P⇒Q。前面介绍了全称量词可以对合取式进行分配，存在量词可以对析取式进行分配。我们不觉要问，全称量词对析取式、存在量词对合取式究竟有什么关系呢？（1）存在量词对合取式的蕴含式证明：假设前件∃x(P(x)∧Q(x))为真，则论域中至少存在一个个体c，使得P(c)∧Q(c)为真。所以P(c)为真、Q(c)也为真。即∃xP(x)为真、∃xQ(x)也为真。因此，∃xP(x)∧∃xQ(x)为真。)()())()((xxQxxPxQxPx例如设论域为自然数。因为存在一个自然数2，2既是偶数又是素数，所以公式成立。反之若设则∃xP(x)∧∃xQ(x)为真，但论域中不存在一个自然数既是偶数又是奇数，使得∃x(P(x)∧Q(x))为真，所以不成立。是偶数：xxP)(是素数：xxQ)(是偶数：xxP)(是奇数：xxQ)())()(()()(xQxPxxxQxxP))()(()()(xQxPxxxQxxP，所以因为)()())()((xxQxxPxQxPx为真。)()())()((xxQxxPxQxPx))()(())()((xQxPxxxQxxP))()(())()((xQxPxxxQxxP))()(())()((xQxPxxxQxxP))()(())()((xQxPxxQxxPx))()(())()((xQxPxxQxxPx，得和替换分别用)()()()(xQxPx、BxA为真。))()(())()((xBxAxxxBxxA))()(()()(xBxAxxxBxxA（2）全称量词对析取式的蕴含式证明：又有原命题与逆否命题等价，故为真。（3）其它蕴含式证明：设论域为D，∀xP(x)若为真，则对于论域中的任一个体c，P(c)为真。根据定义∃xP(x)为真。所以蕴含式成立。例2-14证明证明：（4）多重量化及其等价式和蕴含式谓词公式中往往不只包含一个个体变元，为了使命题函数成为命题，必须对各个个体变元进行量化，这样便出现多重量化的问题。如何解决多重量化问题，我们以两重量化为例加以说明，多重量化与此类同。对于二元谓词如果不考虑自由变元，可以有以下八种情况：)()(xxPxxP))()(()()(xBxAxxxBxxA)()()()(xxBxxAxxBxxA)()(xxBxAx))()((xBxAx))()((xBxAx),(yxyPx),(yxxPy),(yxyPx),(yxxPy),(yxyPx),(yxxPy),(yxxPy),(yxyPx其中和含义相同，和含义相同。后面四种情况经过换名后实际上只有两种情况。即和。例如设x的个体域为甲班，y的个体域为乙班。：表示同姓。则),(yxyPx),(yxxPy),(yxyPx),(yxxPy),(yxyPx),(yxyPx),(yxP),(yxyPx),(yxxPy：表示甲班每个人和乙班所有人同姓。：表示乙班每个人和甲班所有人同姓。所以甲班和乙班所有人同姓，即同理可得：),(),(yxxPyyxyPx),(),(yxxPyyxyPx仍以上述例子讨论其它两种情况：：甲班每个人在乙班中可以找到同姓的人。：甲班有人与乙班中所有人同姓。此时乙班所有人都同姓。从上述例子中可知，相同量词的出现顺序可以交换，而不同量词出现的顺序不可以交换，但它们之间存在着蕴含关系。证明：设为真，则至少存在一个个体，使得对于所有为真。即为真，所以为真，为真。该公式的逆反命题为：),(yxyPx),(yxyPx),(),(yxxPyyxyPx),(yxyPxcx),(,yxPy),(ycP),(ycyP),(yxxPy),(),(yxyPxyxxPy所以有两个量词的谓词公式有如下的蕴含关系：),(),(),(),(),(),(),(),(),(),(),(),(yxyPxyxxPyyxxPyyxyPxyxxPyyxyPxyxyPxyxxPyyxyPxyxxPyyxxPyyxyPx谓词演算中常用的等价式和蕴含式)()(xPxxxP)()(xPxxxP)()())()((xxBxxAxBxAx)()())()((xxQxxPxQxPxBxxABxAx)())((BxxABxAx)())((BxxABxAx)())((BxxABxAx)())(())(()(BxAxBxxA))(()(BxAxBxxA))(()(xABxxxAB))(()(xABxxxAB))()(()()(xQxPxxxQxxP)()())()((xxQxxPxQxPx))()(()()(xBxAxxxBxxAE16E17E18E19E20E21E22E23E24E25E26E27I14I15I16例2-15用谓词演算的等价式和蕴含式证明（1）（2）（3）（4）证明(1)：证明(2)：)()())()((xxQxxPxQxPx)()())()((yyQxxPyQxPyx)()())()((xxQxxPxQxPx))()(()()(xQxPxxxQxPx))()((xQxPx))()((xQxPx)()(xxQxPx)()(xxQxxP)()(xxQxxP))()((yQxPyx))()((yQxPyx)()(yyQxPx)()(yyQxxP)()(yyQxxP证明(3)：要证明，只须证明为真即可。)()())()((xxQxxPxQxPx))()(())()((xxQxxPxQxPx))()(())()((xxQxxPxQxPx))()(())()((xxQxxPxQxPx))()(())()((xxQxxPxQxPx))()(())()((xxQxxPxQxPx))()(())()((xxQxPxxQxPx)())())()(((xxQxPxxQxPx)())())()(((xxQxPxQxPx)())()((xxQxQxPx)()()(xxQxQxxPx)()()(xxQxxQxPx1证明(4)：)()(xxQxPx)()(xxQxPx)()(xxQxxP))()((xQxPx))()(()()()4(xQxPxxxQxPx2．6谓词演算的推理理论谓词演算可以看作命题演算的推广，因为谓词演算的等价式和蕴含式很多是命题演算中有关公式的推广，所以命题演算中的推理规则，如P、T和CP规则在谓词演算中仍适用。由于谓词逻辑中存在量词，所以在谓词演算中的某些前提和结论可能受到量词的约束。为了使谓词演算的推理过程使用命题逻辑有关的等价式和蕴含式，使整个推理过程按命题演算的推理过程进行，必须在谓词演算过程中消去和添加量词，这样就必须有相应的规则。（1）全称指定规则（US）该规则中，c是个体域D中的任意一个个体。该推理规则的横线下面是结论A(c)。该规则表明，如果个体域D中全部个体都满足A(x)，则对个体域D中的某个个体c，c肯定满足A(x)。)()(cAxxA（2）全称推广规则（UG）如果论域D中的任意一个个体c，都能使A(c)成立，则由该规则可得结论成立。注意，此时的个体c不是论域中某一特定的个体，而是泛指论域中所有的个体。（3）存在指定规则（ES）该规则中，c是个体域D中使A(x)为真的个体，而不是任意取的一个个体。（4）存在推广规则（EG）该规则的前提中的c是个体域D中使A(x)为真的个体，即只要个体D中至少存在一个个体使得为真，则为真。)()(