逻辑学导论第四章.pptVIP

谓词逻辑的树形图是命题逻辑树形图的扩充，命题逻辑原有的关于联结词的九个画图规则仍然有效； 但需要增加关于全称量词?x和存在量词?x的四个画图规则： * * * * 谓词逻辑是不可判定的 即是说，不存在一种机械的、能行的办法，它适合于任一的谓词逻辑公式，将在有穷步内结束，并且就该公式是不是普遍有效式给出唯一确定的结果。不过，某些特殊类型的谓词逻辑公式，例如一元谓词逻辑公式，其普遍有效性是可判定的。在这个意义上，谓词逻辑是半可判定的。 * 证明非普遍有效性或可满足性的方法 要证明这样的一个公式不普遍有效，或者是可满足的，前者是要为该公式找一反模型，使得该公式在其中为假；后者是要为该公式找一模型，使得该公式在其中为真。这种方法叫做“解释方法”或“模型方法”。 * （一）QN推理规则 谓词逻辑自然推理QN是命题逻辑自然推理PN的扩充，所有PN的规则都是QN的规则；所有已经证明的PN定理和导出规则，都是QN的定理和导出规则，故在证明或推演中可以直接使用它们，无需另外证明。 在PN的基础上，QN增加了四条与量词有关的规则： * 1．全称量词消去规则，记为?－规则：从?xA(x)推出A(x/t)，其中代换x的t不会被A中原有的量词所约束。 * 2．全称量词引入规则，记为?＋规则：从A(x)推出?xA(x)，只要能够确保前提中的自由变项x是任意的。 * 若不能确保前提中的自由变项x是任意的，就要给该x加标记，其具体做法是：在一个证明或推演的某一步上，出现了含自由变项x的公式A，且不能保证其中的x是任意的，则在该公式的右边注明该公式来历的位置，写上x，表示该x可能不是任意的，不能对它使用?＋规则。以下三种情形需要给相应的自由变项加标记： （i）给定前提中的自由变项； （ii）根据假设引入规则所引入的假设中的自由变项； （iii）一个在前提或假设中是自由的变项，在从该前提或假设出发，根据QN的推演规则所得到的任意一行中也出现，那么，它在后面这些行的出现也应加标记。 * 3．存在量词消去规则，记为?－规则：从?xA(x)可以推出A(α)，这里要求 （i）α是先前没有出现过的特指常项； （ii）如果公式A含有x之外的自由变项y，应该用该y给特指常项做下标，写成αy。 * 4．存在量词引入规则，记为?＋规则：从A(x/t)可以推出?xA(x)，只要代换x的t不会被A原有的量词所约束，或者新引入的存在量词不会将A(x)中除x之外的其他自由变项一并加以约束。 * 量词规则总结 全称量词消去规则?－：从?xA(x)推出A(x/t)，其中代换x的t不会被A中原有的量词所约束，这包括以下情形： （1）t是一个个体常项； （2）A是一个原子公式，x是其中的自由变项，t是任一个体词； （3）A含有量词，但自由变项x不在这些量词的辖域之内，t是任一个体词； （4）A含有量词，且自由变项x在这些量词的辖域之内，则t必须是与已量化变项不同的变项。否则，称为t对于公式A中的自由变项x代入不自由。 * 全称量词引入规则?＋：从A(x)推出?xA(x)，只要能够确保前提中的自由变项x是任意的。以下情况下的自由变项不能确保是任意的，被称为“加标记变项”： （i）给定前提中的自由变项； （ii）根据假设引入规则所引入的假设中的自由变项； （iii）从该前提或假设出发，根据QN的推演规则所得到的的那些行中、与前提或假设中的自由变项相同的自由变项； （iv）给特指常项做下标的自由变项。对加标记变项，?＋规则不适用。 * 存在量词消去规则?－：从?xA(x)可以推出A(α)，这里要求（i）α是先前没有出现过的特指常项；（ii）如果公式A含有x之外的自由变项y，应该用该y给特指常项做下标，写成αy。 存在量词引入规则?＋：从A(x/t)可以推出?xA(x)，其中代换x的t不会被A中原有的量词所约束，或者新引入的存在量词不会将A中除x之外的其他自由变项一并加以约束。 * （二）QN有前提推演 * * （三）QN定理及其证明 ［1］?xA(x)???x?A(x) ［2］?x?A(x)???xA(x) ［3］??xA(x)??x?A(x) ［4］??xA(x)??x?A(x) ［5］A??xA，若x不在A中自由出现 ［6］A??xA，若x不在A中自由出现 ［7］A(x/t)??x A(x)，若t对于x代入自由 ［8］?xA(x)??xA(x) * * 第二组 ［9］?x(A(x)∧B(x))??xA(x)∧?xB(x) ［10］?x(A(x)∨B(x))??xA(x)∨?xB(x) ［11］?x(A∧B(x))?A∧?xB(x)，若x不在A中自由出现 ［12］?x(A∧B(x))?A∧?xB(x)，若x不在A中自由出现 ［13］?x(A∨B(x))?A∨?xB(x)，若x不在A中自由出现