一阶逻辑的推理演算.docxVIP

一阶逻辑的推理演算这一讲我们学习一阶逻辑的自然推理系统。其功能是由若干前提推导出一条结论B。这相当于证明下列蕴含式是永真的：一阶逻辑的代入定理将永真命题公式中的各命题变元代换为任何一阶公式后，所得的一阶公式是永真的。例如，是永真命题公式。进行一阶公式代入p=F(x)，q=G(x)后得如下永真一阶公式：定理1.1（代入定理）任何永真命题公式在代入一阶公式后是永真一阶公式。证明 略。 证毕永真蕴含式和推理定律永真蕴含式：若A→B是永真式，则记为，称为永真蕴含式。将永真命题蕴含式中的变元视为取值为任何一阶公式的变元，则该永真命题蕴含式就变成一条推理定律。根据代入定理，推理定律表示一批形式相似的永真蕴含式。因此，推理定律是描述永真蕴含式的模式。由任何永真蕴含式可以得到对应的推理定律。例如，由永真蕴含式可得一阶逻辑的假言推理定律，其中变元A，B表示任何一阶公式。这条推理定律的含义是，对于任何一阶公式A和B，若(A→B)为真并且A为真，则B为真。因此，由前提(A→B)与A可得结论B。这是我们思维中最常用的一条推理规则，称为假言推理规则或者分离规则。因此，推理定律可以当作推理规则使用。再如，是永真蕴含式，由此可得推理定律，称为拒取式。命题逻辑的自然推理系统P中的所有9条推理定律都可以当作一阶逻辑推理定律来使用。量词消去与引入规则与命题逻辑的自然推理系统相比，这是一阶逻辑自然推理系统所特有的推理规则。见课本第75页。这是课程中的一个难点，我们可以借助于语义来理解其正确性。全称量词消去规则（简记为）（1）第一个竖式得出的结论是一个句型。适用条件： x不在y的量词辖域内自由出现。在这个推理规则中，结论A(y)是将A(x)中所有自由出现的x代换为y而得的公式。但是在一种情形下，这种代换会导致语义混淆。这个情形就是，x在y的量词辖域内自由出现。例如，令，则。在前一个公式中，x与y是可以指代不同的对象的，而在后一公式中两个位置上的y只能指代同一个对象。如果把B(x,y)解释为实数集合上的小于关系xy，则前提正确而结论错误。因此，应当禁止在这种情形下使用该推理规则。这就是上述适用条件的意义。推理规则的语义：若前提中没有出现y，则结论中的y指代论域中任何对象。此时，该推理规则的语义是，若所有对象x都有性质A，则任何对象y有性质A。若前提中有自由出现的y，则结论中的y与前提中的y的所指相同。此时，该推理规则的语义是，若所有对象x都有性质A，则对象y有性质A。注：上述推理规则中的适用条件可以改为，y不在A(x)中约束出现。若有y的约束出现的话，可以通过改名规则消除这些y的约束出现。由上述一般规则可得如下特殊规则这个规则的优点是没有适用条件，即无条件地永远成立。显然，结论中的x与前提中的x没有任何语义关系，各自指代任何对象。（2）第二个竖式所得的结论是语句或者句型。其中c是常元，A(c)是将A(x)中所有自由出现的x代换为c而得的公式。这一条规则除了要求结论中的符号c是常元之外，不需要任何其它适用条件。以下3组规则可做类似的分析和理解。全称量词引入规则（简记为）全称量词消去规则（简记为）全称量词引入规则（简记为）其中在前提A(y)中变元y不在x的量词的辖域中自由出现。 （理解该规则的含义！）其中在前提A(c)中常元c不在x的量词的辖域中出现。（理解该规则的含义！）由上述第一组规则可得如下特殊规则无条件成立：一阶逻辑自然推理系统包括如下3个部分：符号表：某一阶逻辑语言的符号表。合式公式：该一阶逻辑语言的合式公式。推理规则（共16条）：前提引入结论引入替换规则假言推理附加规则化简规则拒取式规则假言三段论析取三段论构造性二难推理破坏性二难推理合取引入规则规则规则规则规则例3.1 课本第77页例5.9。例3.2 课本第78页例5.11。4