2-67 前束范式及推理理论

2-6前束范式定义2-6.1前束范式：一个公式如果量词均包含在全式的开头，它们的作用域延伸到整个公式的末尾，则该公式叫做前束范式。设A是一个谓词公式，如果A具有如下形式：(Q1x1)(Q2x2)…(Qnxn)B，其中Qi(1≤i≤n）为或，xi为客体变元，B为不含量词的谓词公式，则称A是前束范式。2-6前束范式定理2-6.1：任意一个谓词公式，均与一个前束范式等价。转化方法：1.利用量词转化公式，把否定深入到命题变元和谓词公式的前面。2.换名，利用量词作用域的扩张和收缩等价式，把量词提到前面。前束合取范式定义2-6.2前束合取范式：一个wffA如果具有如下形式，则称为前束合取范式：(Q1x1)(Q2x2)…(Qnxn)[(A11A12A1k1)(A21A22A2k2)(Am1Am2Amkm)]其中Qi(1≤i≤n）为或，xi为客体变元，Aij是原子变元或其否定。前束合取范式定理2-6.2：每一个wffA都可转化为与其等价的前束合取范式。转化方法：1.取消多余量词。2.换名3.消去条件联结词。4.利用量词转化公式，把否定深入到命题变元和谓词填式的前面。5.利用量词作用域的扩张和收缩等价式，把量词提到前面。前束析取范式定义2-6.3前束析取范式：一个wffA如果具有如下形式，则称为前束析取范式：(Q1x1)(Q2x2)…(Qnxn)[(A11A12A1k1)(A21A22A2k2)(Am1Am2Amkm)]其中Qi(1≤i≤n）为或，xi为客体变元，Aij是原子变元或其否定。前束析取范式定理2-6.3：每一个wffA都可转化为与其等价的前束析取范式。转化方法同前。例题分析见P74例42-7谓词演算的推理理论在谓词逻辑中，如果A1∧A2∧…∧An→B是逻辑有效式，则称B是A1,A2,…，An的有效结论，记作A1∧A2∧…∧AnBAB当且仅当AB是永真式例如：(x)F(x)(x)F(x)2-7谓词演算的推理理论谓词演算的推理，是命题演算推理的扩张，命题演算中的推理规则，如P,T和CP规则同样可以在谓词演算的推理中使用。但是在谓词推理中，前提和结论可能会受到量词的限制。所以需要在在适当时候利用消去和添加量词的规则，使得谓词演算的推理过程类似于命题演算的推理那样进行。(1)全称指定规则（universalinstantiation）全称量词消去规则，简称US规则。(x)P(x)P(c)，P是谓词，c为个体域中某个任意的客体。举例说明：P76例１(2)全称推广规则（universalgeneralization）全称量词引入规则，简称UG规则。P(x)(x)P(x)如果能够证明对论域中每一个客体c，命题P(c)都成立，则全称推广规则可得到结论(x)P(x)成立。在应用本规则时，必须能够证明前提P(x)对论域中每一可能的x是真。(3)存在指定规则（existentialinstantiation）存在量词消去规则，简称ES规则。(x)P(x)P(c),这里c是论域中的某些客体。必须注意，应用存在指定规则，其指定的客体c不是任意的。举例说明：(x)P(x)和(x)Q(x)都为真，则对于某些c和d，可以断定P(c)Q(d)必定为真，但不能断定P(c)Q(c)是真。(4)存在推广规则（existentialgeneralization）存在量词引入规则，简称EG规则。P(c)(x)P(x)，这里c是论域中的一个客体，这个规则比较明显，对于某些客体c，若P(c)为真，则在论域中必有(x)P(x)为真。举例说明：例１：前提:(x)(F(x)G(x))，F(a)结论:G(a)证明:(1)F(a)P(2)(x)(F(x)G(x))P(3)F(a)G(a)US(2)(4)G(a)T(1)(3)I例２：前提:(x)(F(x)G(x))，(x)F(x)结论:(x)G(x)证明:(1)(x)F(x)P(2)F(c)ES(1)(3)(x)(F(x)G(x))P(4)F(c)G(c)US(3)(5)G(c)T(2)(4)I(6)(x)G(x)EG(5)注意证明过程为：“先ES，后US”证明:(1)(x)(F(x)G(x))P(2)F(c)G(c)US(2)(3)(x)F(x)P(4)F(c)ES(3)注意：这个证明是错的.(3)(4)应当在(1)(2)之前，(4)中的c是特定的，(2)中的c是任意的。例３前提:¬(x)(F(x)∧H(x)),(x)(G(x)H(x)),结论:(x)(G(x)¬F(x))证明:(1)¬(x)(F(x)∧H(x))P(2)(x)(¬F(x)∨¬H(x))T(1)E(3)(x)(H(x)¬F(x))T(2)E(4)H(y)¬F(y)US(3)(5)(x)(G(x)H(x))P(6)G(y)H(y)US(5)(7)G(y)¬F(y)T(4)(6)I(8)(x)(G(x)¬F(x))UG(7)作业：(2-6,2-7)P75(1)b),(2)a)P79(1)a)