《左孝凌离散数学课件2.6前束范式-2.7谓词演算的推理理论》由会员分享，可在线阅读，更多相关《左孝凌离散数学课件2.6前束范式-2.7谓词演算的推理理论（29页珍藏版）》请在金锄头文库上搜索。
1、1离散数学离散数学( (Discrete MathematicsDiscrete Mathematics) )2第二章第二章 谓词逻辑谓词逻辑2.1谓词的概念与表示 2.2命题函数与量词 2.3谓词公式与翻译 2.4变元的约束 2.5谓词演算的等价式与蕴含式 2.6前束范式 2.7谓词演算的推理理论32. 6前束范式在命题演算中，常常要将公式化成规范 形式，对于谓词演算也有类似情况。一个谓 词公式可以化为与它等价的范式。这里主要 介绍前束范式的基本概念及方法42. 6前束范式 定义:任何一个谓词公式A，如果具有如下形式：(x1) (x2) (xn)B 其中可能是量词或量词，xi（i=1， n）
2、是客体变 元，B是不含量词的谓词公式，则称A是前束范式。 说明: 前束范式的量词均在全式的开头 前束范式量词的作用域延伸到整个公式的末尾。 例1: 判断是否是前束范式xy（F(x)G(y)） H(x,y)）xy(F(x,y)G(y,z) x H(x,y,z)前束范式 52. 6前束范式前束范式的求法： 设谓词公式为W 将W等价转化为只含有联结词，的谓词公式 否定深入。即利用量词转化公式，把否定联结词深入到命题 变元和谓词填式的前面。 改名。即利用换名规则、代入规则更换一些变元的名称，以 便消除混乱。 量词前移。即利用量词辖域的收缩与扩张把量词移到前面这样便可求出与公式等价的前束范式。 定理:任
3、何一个谓词公式,均和一个前束范式等价。（x）（A(x)B）（x）A(x)B （x）（A(x)B）（x）A(x) B （x）（A(x)B）（x）A(x)B （x）（A(x)B）（x）A(x)B62. 6前束范式例2:求下列公式的前束范式。72. 6前束范式 解:x(A(x)B(x) x A(x) x B(x)92. 6前束范式自由 变元谓词不同，变 元名称冲突10第二章第二章 谓词逻辑谓词逻辑（Predicate LogicPredicate Logic）2. 6前束范式(Prenex normal form) ) 112. 6前束范式 定义:任何一个谓词公式A，如果具有如下形式则称为 前束合取
4、范式：(x1)(x2)(xn)(A11A12A1k1) (A21A22A2k2 )(Am1Am2Amkm) 其中n大于等于1,Aij(j=1, ,ki ,i=1,2,3,m)为原子谓词 公式或其否定,为量词或量词， xi（i=1， n）为 客体变元. 例如：前束合取范式122. 6前束范式 定义:任何一个谓词公式A，如果具有如下形式则称为 前束析取范式：(x1) (x2)(xn)(A11A12A1k1) (A21A22A2k2 )(Am1Am2Amkm) 其中n大于等于1,Aij(j=1, ,ki ,i=1,2,3,m)为原子谓词公 式或其否定,为量词或量词， xi（i=1， n）为客 体变元
5、. 例如： 前束析取范式例题4 将wff D： 转化为与其等价的前束合取范式。解 第一步取消多余量词第二步换名第三步消去条件联结词第四步将否定深入第五步将量词推到左边(x)(z)(w)(P(x)R(x,w)(Q(z,y)R(x,w)定理:每一个谓词公式都可以转化为与其等价的前束析(合)取范式.2. 6前束范式例题4 将wffD： 转化为与其等价的前束析取范式。解2. 6前束范式152. 6前束范式练习:求下列公式的前束析取范式和前束合取范式.解:162. 6前束范式小结：本节介绍了谓词公式的前束范式、前束 析取范式和前束合取范式.重点掌握前束析 取范式和前束合取范式求法。作业: P75 (2)
6、 b，d172.7谓词演算的推理理论2.7谓词演算的推理理论(Inference theory ofpredicate calculus)2.7.1推理规则(Rules of inference) ) 2.7.2证明举例 (Examples of proof) ) 182.7谓词演算的推理理论在谓词演算中，推理的形式结构仍为H1H2H3.HnC若 H1H2H3.HnC是永真式，则称由前提H1,H2,H3,.,Hn逻辑的推出结论C，但在谓词逻辑中, H1,H2,H3,.,Hn , C均为谓词公式。命题演算中的推理规则，可在谓词推理理论中应用。推理规则192.7谓词演算的推理理论1、全称指定规则（
7、US规则） 2、全称推广规则（UG规则） 3、存在指定规则（ES规则） 4、存在推广规则（EG规则）注意：只能对前束范式适用上述规则。与量词有关的四条重要推理规则：202.7谓词演算的推理理论 1. 全称指定规则（ US ）：x P(x) P(c) 使用此规则时要注意： （1）P是谓词 ； （2） c是论域中的某个任意的客体. 212.7谓词演算的推理理论 2.全称推广规则（UG）：P(y) x P(x)使用此规则时注意:(1) y在P(y)中自由出现，且y取任何值时P均为真。(2) x不在A(y)中约束出现. 222.7谓词演算的推理理论 3.存在指定规则(ES):x P(x) P(c) 注
8、:c是论域中的某些客体,c并不是任意的使用此规则时应注意：（1）c 是使P为真的特定客体；（2）如果P(x)中有其他自由变元出现，且x是随其他自由变元变化的，那么不能使用此规则 。232.7谓词演算的推理理论(4)存在推广规则(EG):P(c) x P(x)使用此规则时注意:(1) c是个体域中某个确定的个体。(2) 代替c的x不能已在A(c)中出现。242.7谓词演算的推理理论例1证明苏格拉底三段论:凡是人都是要死的。苏格拉底是 人。苏格拉底是要死的。 设：M(x):x是人。D(x):x 是要死的。a:苏格拉底。则： 前提：x(M(x)D(x)，M(a）. 结论： D(a) . 证明： x
9、(M(x)D(x) P M(a)D(a) US M(a) P D(a) T I11(直接证法)252.7谓词演算的推理理论例2:前提：x(F(x)G(x)， x G(x).结论： x F(x) . 证明： x G(x) P x G(x) T 置换规则 G(a) US x(F(x)G(x) P F(a)G(a) US F(a) T ,I x F(x) EG 262.7谓词演算的推理理论例3:前提： x (A(x)B(x)， x A(x)结论： x B(x) 证明： x A(x) P前提引入 A(c) ES x (A(x)B(x) P前提引入 A(c)B(c) US B(c) T x B(x) E
10、G 注意： 引入的顺序不可更改！ 272.7谓词演算的推理理论例4:前提：x(F(x)G(x), x( R(x) G(x), x R(x).结论： x F(x) .(归谬法) 证明： x F(x) P结论否定引入 x F(x) T F(a) ES x(F(x) G(x) P F(a) G(a) US G(a) T x( R(x) G(x) P R(a) G(a) US R(a) T x R(x) P(11) R(a) US (12) R(a) R(a) 矛盾式282.7谓词演算的推理理论例5:证明: x(P(x)Q(x)=(x)P(x) (x)Q(x) (附加前提法) 证明：(1) (x)P(x) P(附加前提) (2) (x)P(x) T(1) (3) P(c) ES(2) (4) x(P(x)Q(x) P (5) P(c)Q(c) US(4) (6) Q(c) T(3)(5) (7)(x)Q(x) EG(6) (8) (x)P(x) (x)Q(x) CP292.7谓词演算的推理理论小结：本节介绍了谓词演算的推理规则,并举例说明了它 们的应用. 重点:深刻理解四个推理规则,会应用它们推 理证明. 作业: P79 (1)d,(2) a,(3)a
