离散数学26谓词演算的推理理论.ppt

离散数学 Discrete Mathematics,第6讲 27 谓词演算的推理理论,要求：熟练掌握谓词的推理理论与推理方法，会用谓词的推理理论与推理方法进行推理。 重点：应用谓词的推理理论与推理方法进行推理。 难点：正确理解和运用有关量词规则。,谓词逻辑是命题逻辑的进一步深化和发展，谓词演算的推理方法，可以看作是命题演算推理方法的扩张。因此命题逻辑的推理理论在谓词逻辑中几乎可以完全照搬，只不过这时涉及的公式是谓词逻辑的公式罢了。在谓词逻辑中，某些前提和结论可能受到量词的约束，为确立前提和结论之间的内部联系，有必要消去量词和添加量词，因此正确理解和运用有关量词规则是谓词逻辑推理理论中十分重要的关键所在。,下面在介绍有关量词规则之前做些必要准备。下面给出A(x)对y是自由的这个概念。其目的是，允许用y代入x后得到A(y)，它不改变原来公式A(x)的约束关系。 定义2.7.1 在谓词公式A(x)中，若x自由出现在量词(y)或(y)的辖域， 则称A(x)对于y是自由的。 由定义可知，若y在A(x)中不是约束出现，则A(x)对于y一定是自由的。,一、有关量词消去和添加规则 量词消去规则： (1) 全称量词消去规则(称为全称指定规则，简称UI或US规则) 有两种形式：(x)A(x)A(c) 其中c为任意个体常元 (x)A(x)A(y) A(x)对y是自由的,(2) 存在量词消去规则(称为存在指定规则，简称EI或ES规则) 有两种形式：(x)A(x)A(c) 其中c为特定个体常元 (x)A(x)A(y) 成立充分条件是： c或y不得在前提中或者居先推导公式中出现或自由出现； 若A(x)中有其它自由变元时，不能应用本规则。 值得注意的是，A(y)只是新引入的暂时假设，它不是对y的 一切值都是成立的。y是一个暂时的、表面上的自由变元。,量词产生规则： (3) 存在量词产生规则(称为存在推广规则，简称EG规则) 有两种形式：A(c)(y)A(y) 其中c为特定个体常元 A(x)(y)A(y) 成立充分条件：取代c的个体变元y不在A(c)中出现；A(x)对y 是自由的；若A(x)是推导行中的公式，且x是由使用EI引入的，那么不能用A(x)中除x外的个体变元作约束变元，或者说，y不得为A(x)中的个体变元。,(4) 全称量词产生规则(称为全称推广规则，简称UG规则) A(x)(y)A(y) 成立条件：前提A(x)对于x的任意取值都成立；A(x)对y是自由的；对于由于使用EI 规则所得到的公式中原约束变元及与其在同一个原子公式的自由变元，都不能使用本规则而成为指导变元，否则将产生错误推理。,二、Lp中推理实例 Lp的推理方法是Ls推理方法的扩展，因此在Lp中利用的推理规则也是T规则、P规则和CP规则，还有已知的等价式，蕴含式以及有关量词的消去和产生规则。使用的推理方法是直接构造法和间接证法。,例题1 证明苏格拉底论证： 所有的人都是要死的。 苏格拉底是人。 所以苏格拉底是要死的。,解 设 H(x)：x是一个人。 M(x)：x是要死的。 s：苏格拉底。 故苏格拉底论证可符号化为： (x)(H(x) M(x) H(s)M(s),证明,(1) (x)(H(x) M(x) P,(2) H(s)M(s) US(1),(3) H(s) P,(4) M(s) T(2)(3)I,例题2 证明,证明,注意（3）（4）两条次序不能颠倒。,练习 79页 （1）题,(x)(C(x)W(x)R(x)(x)(C(x)Q(x)(x)(Q(x)R(x),(1) (x)(C(x)W(x)R(x) P,(2) (x)(C(x)Q(x) P,(4) C(a)W(a)R(a) US(1),(3) C(a)Q(a) ES(2),(5) C(a) T(3)I,(6) W(a)R(a) T(4)(5)I,(7) Q(a) T(3)I,(8) R(a) T(6)I,(9) Q(a)R(a) T(7)(8)I,(10) (x)(Q(x)R(x) EG,例题3 证明,(x)(P(x)Q(x)(x)P(x)(x)Q(x),用间接证法。要证SC，即要证SCT，而SCSC， 所以SCT即SCT，亦就是(SC)F， SCF。假定C为T，推出矛盾。,(1) (x)P(x)(x)Q(x) P(附加前提),(2) (x)P(x)(x)Q(x) T(1)E,(3) (x)P(x) T(2)I,(4) (x)Q(x) T(2)I,(5) P(c) ES(3),(6) Q(c) US(4),(7) P(c)Q(c) T(5)(6)I,(8) (P(c)Q(c) T(7)E,(9) (x)(P(x)Q(x) P,(10) P(c)Q(c) US(9),(11) (P(c)Q(c) (P(c)Q(c) (矛盾)T(8)(10)I,证法2 本题可用CP规则,原题为,(x)(P(x)Q(x)(x)P(x)(x)Q(x),复习CP规则 要证SRC ，即要证S(RC)T,即S(RC)T, (SR)CT, (SR)CT,(SR)CT 也就是证明(SR)C。,(1) (x)P(x) P（附加前提）,(2) (x)P(x) T（1）E,(3) P(c) ES(2),(4) (x)(P(x)Q(x) P,(5) P(c)Q(c) US(3),(6) Q(c) T(3)(5)I,(7) (x)Q(x) EG(6),(8) (x)P(x)(x)Q(x) CP,例题4 构造下面推理的证明： 每个学术会的成员都是专家并且是工人，有些成员是青年人，所以有些成员是青年专家。,证明,设 P(x)： x是学术会的成员。 Q(x)： x是专家。 R(x) ：x是工人。 S(x) ：x是青年人。,证明过程如下：,则本题要证明： (x)(P(x)Q(x)R(x)，(x)(P(x)S(x)(x)(P(x)Q(x)S(x),(1) (x)(P(x)S(x) P,(2) P(a)S(a) ES(1),(3) P(a) T(2)I,(4) S(a) T(2)I,(5) (x)(P(x)Q(x)R(x) P,(6) P(a)Q(a)R(a) US(5),(7) Q(a)R(a) T(3)(6)I,(8) Q(a) T(7)I,(9) P(a)Q(a)S(a) T(3)(4)(8)I,(10) (x)(P(x)Q(x)S(x) EG(9),数理逻辑在计算机科学中的用途有两个：一个是作为知识表示的手段，因为