Chapter 1 谓词逻辑推理理论 5.pdf

谓词逻辑推理理论 谓词逻辑推理理论 在谓词逻辑中，由前提A ，A ，…，A 推出结 1 2 n 论B 的形式结构仍然是A ∧A ∧…∧A →B 。如果此 1 2 n 式是永真式，则称由前提A ，A ，…，A 推出结论B 1 2 n 的推理正确，记作 A 1 ∧A2 ∧…∧An B或者 A ，A ，…，A B ，否则称推理不正确。 1 2 n 由于谓词演算是在命题演算的基础上，进 一步加入了谓词与量词的功能，因此容易想到， 命题演算中有关推理演绎的规则基本上适用于 谓词演算，即在命题逻辑中的各项推理规则在 谓词逻辑推理中仍然适用，当然也有些只适用 于谓词演算的概念与规则。 全称量词消去规则 （简称UI规则） Universal Instantiation (UI) xA(x ) A(t ) 规则成立的条件： （1）t是任意个体变项或常项。 （2 ）A （t ）中其它约束变元个数与A （x ） 中x 以外的约束变元个数相同。 全称量词引入规则（简称UG规则） Universal Generalization (UG) A(t ) xA(x ) 规则成立的条件： （1）A （t ）在任何解释I及I 中对t 的任何赋值下均 为真。此处t是自由变量 （2 ）x 不在A （t ）中约束出现。 存在量词引入规则（简称EG规则） Existential Generalization(EG) A(c ) xA(x ) 规则成立的条件： （1）c只需是某个特定的个体常量。 （2 ）x 不在A （c ）中出现。 存在量词消去规则（简称EI规则） Existential Instantiation (EI) xA(x ) 规则成立的条件： A(c ) （1）c是使A （c ）为真的某个特定的个体常元。 （2 ）xA （x ）是闭式，且c不在A （x ）中出现。 特别需要注意的是，使用这些规则的条件非 常重要，如在使用过程中违反了这些条件就可能导 致错误的结论。 【例1】证明推理所有的自然数均是实数，3是自 然数，因此，3是实数。正确。 解 设N （x ）：x 是自然数，R （x ）：x 是实数，则 推理形式化为： x （N （x ）→R （x ））, N （3 ）R （3 ） 下面进行证明。 （1）x （N （x ）→R （x ）） 前提引入 （2 ）N （3 ）→R （3 ） （1）UI （3 ）N