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

《离散数学26谓词演算的推理理论.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学DiscreteMathematics第6讲§2—7谓词演算的推理理论要求：熟练掌握谓词的推理理论与推理方法，会用谓词的推理理论与推理方法进行推理。重点：应用谓词的推理理论与推理方法进行推理。难点：正确理解和运用有关量词规则。谓词逻辑是命题逻辑的进一步深化和发展，谓词演算的推理方法，可以看作是命题演算推理方法的扩张。因此命题逻辑的推理理论在谓词逻辑中几乎可以完全照搬，只不过这时涉及的公式是谓词逻辑的公式罢了。在谓词逻辑中，某些前提和结论可能受到量词的约束，为确立前提和结论之间的内部联系，有必要消去量词和添加量词，因此正确理

2、解和运用有关量词规则是谓词逻辑推理理论中十分重要的关键所在。下面在介绍有关量词规则之前做些必要准备。下面给出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)其

3、中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)

4、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规则所得到的公式中原约束变元及与其在同一个原子公式的自由变元，都不能使用本规则而成为指导

5、变元，否则将产生错误推理。二、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)

6、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)(

7、Q(x)∧R(x))EG例题3证明(x)(P(x)∨Q(x))(x)P(x)∨(x)Q(x)用间接证法。要证SC，即要证SCT，而SC┐S∨C，所以SCT即┐S∨CT，亦就是┐(┐S∨C)F，S∧┐CF。假定┐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、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