离散数学第2章第3节.ppt

离离 散散 数数 学学Discrete Mathematics 山东科技大学山东科技大学信息科学与工程学院信息科学与工程学院.上次课回顾上次课回顾v指导变元、作用域、约束变元、自由变元、闭式指导变元、作用域、约束变元、自由变元、闭式v约束变元换名和自由变元代入约束变元换名和自由变元代入v有限论域客体变元的枚举有限论域客体变元的枚举v谓词公式赋值、谓词公式等价、永真式、不可满足谓词公式赋值、谓词公式等价、永真式、不可满足式、可满足式式、可满足式v谓词公式的等价式和蕴含式谓词公式的等价式和蕴含式.四、谓词演算的等价式和蕴含式四、谓词演算的等价式和蕴含式1、命题公式的推广、命题公式的推广v结论结论：命题演算中的等价公式表和蕴含公式表都：命题演算中的等价公式表和蕴含公式表都可推广到谓词演算中使用。可推广到谓词演算中使用。命题演算的等价式命题演算的等价式谓词演算的等价式谓词演算的等价式.2、量词与联结词、量词与联结词之间的关系之间的关系v将量词前面将量词前面的移到量词后面去时，存在量词的移到量词后面去时，存在量词改为全称量词，全称量词改为存在量词；改为全称量词，全称量词改为存在量词；v反之，将量词后面的反之，将量词后面的移到量词前面去时，也移到量词前面去时，也要做相应的改变。要做相应的改变。(x)P(x)(x)P(x)(x)P(x)(x)P(x).这里这里A(x)是任意包括个体变元是任意包括个体变元x的谓词公式，的谓词公式，B是不包括个体变元是不包括个体变元x的任意谓词公式。的任意谓词公式。3、量词扩张、量词扩张/收缩律收缩律(1).证明证明 当当B为真时为真时,左右两边都为真左右两边都为真;否则否则,B为假为假,此时左右此时左右两边都等价于两边都等价于(x)Ax)A(x)(x),证迄证迄.(x)Ax)A(x)B(x)B (x)(Ax)(A(x)B)(x)B).3、量词扩张、量词扩张/收缩律收缩律(2)这里这里A(x)是任意包括个体变元是任意包括个体变元x的谓词公式，的谓词公式，B是不包括个体变元是不包括个体变元x的任意谓词公式。的任意谓词公式。.证明证明(x)A(x)B(x)(A(x)B)(B不含不含x)证证 (x)A(x)B (x)A(x)B 条件表达式条件表达式 (x)A(x)B 量词否定量词否定 (x)(A(x)B)量词辖域扩张量词辖域扩张 (x)(A(x)B)条件表达式条件表达式.证明证明 B(x)A(x)(x)(BA(x)(B不含不含x)证证 B(x)A(x)B(x)A(x)条件表达式条件表达式 (x)(BA(x)量词辖域扩张量词辖域扩张 (x)(BA(x)条件表达式条件表达式.4、量词与命题联结词之间的一些等价式、量词与命题联结词之间的一些等价式量词分配律量词分配律(x)(A(x)B(x)(x)A(x)(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x).5、量词与命题联结词之间的一些蕴含式、量词与命题联结词之间的一些蕴含式(x)Ax)A(x)(x)(x)x)B(x)B(x)(x)(Ax)(A(x)(x)B B(x)(x)(x)(Ax)(A(x)B(x)(x)B(x)(x)Ax)A(x)(x)(x)Bx)B(x)(x)(x)Ax)A(x)(x)(x)x)B(x)B(x)(x)(Ax)(A(x)(x)B B(x)(x)(x)(Ax)(A(x)(x)B(x)B(x)(x)Ax)A(x)(x)(x)Bx)B(x)(x)(x)(Ax)(A(x)(x)B(x)B(x)(x)Ax)A(x)(x)(x)Bx)B(x)(x).用分析法证明用分析法证明(x)A(x)(x)B(x)(x)(A(x)B(x)。证明证明 若若(x)(A(x)B(x)为为假假,则则必必有有个个体体a,使使A(a)B(a)为假为假;因此因此A(a),B(a)皆为假皆为假,所以所以(x)A(x)和和(x)B(x)为假，为假，即即(x)A(x)(x)B(x)为假。为假。故故(x)A(x)(x)B(x)(x)(A(x)B(x).表表 2 1 谓词演算中常用的等价式和蕴含式谓词演算中常用的等价式和蕴含式.6、多个量词的使用、多个量词的使用考虑两个量词的情况。更多量词的使用方法与其类似。考虑两个量词的情况。更多量词的使用方法与其类似。对于二元谓词如果不考虑自由变元，可以有以下八种情况。对于二元谓词如果不考虑自由变元，可以有以下八种情况。全称量词与存在量词在公式中出现的次序，不能随意更换。全称量词与存在量词在公式中出现的次序，不能随意更换。用双向箭头表示等价，单向箭头表示蕴含，见它们之间的关系。用双向箭头表示等价，单向箭头表示蕴含，见它们之间的关系。.有两个等价关系：有两个等价关系：.具有两个量词的谓词公式有如下一些蕴含关系：具有两个量词的谓词公式有如下一些蕴含关系：.作业P66:3,4,5 P72:2a),4,7.定义定义2-6.1 一个合式公式称为前束范式，如果它有如下一个合式公式称为前束范式，如果它有如下形式：形式：(Q1x1)(Q2x2)(Qkxk)A其中其中Qi(1ik)为为 或或,A为不含有量词的谓词公式。为不含有量词的谓词公式。v特别地，若谓词公式中无量词，则该公式也看作特别地，若谓词公式中无量词，则该公式也看作是前束范式。是前束范式。v前束范式的特点前束范式的特点:所有量词均非否定地出现在公式所有量词均非否定地出现在公式最前面，且它的辖域一直延伸到公式之末。最前面，且它的辖域一直延伸到公式之末。一、前束范式一、前束范式.例如，例如，(x)(y)(z)(P(x,y)Q(y,z)R(x,y)都是前束范式，都是前束范式，而而(x)P(x)(y)Q(y)，(x)(P(x)(y)Q(x,y)不是前束范式。不是前束范式。.定理定理2.6.1 (前束范式存在定理前束范式存在定理)任意谓词公式任意谓词公式A都有与都有与之等价的前束范式。之等价的前束范式。证明：证明：.前束范式的求取方法前束范式的求取方法.举例举例73页 例题1、例题2、例题3.例题例题2 化公式化公式(x x)(y y)()(z)(P(x,z)z)(P(x,z)P(y,z)P(y,z)(u)Q(x,y,u)u)Q(x,y,u)为前束为前束范式范式解解 原公式原公式(x x)(y y)()(z)(P(x,z)z)(P(x,z)P(y,z)P(y,z)(u)Q(x,y,u)u)Q(x,y,u)(x x)(y y)()(z)(z)(P(x,z)P(x,z)P(y,z)P(y,z)(u)Q(x,y,u)u)Q(x,y,u)(x x)(y y)()(z)z)(u)u)(P(x,z)P(x,z)P(y,z)P(y,z)Q(x,y,u)Q(x,y,u).解解 第一步否定深入第一步否定深入原式原式第二步改名，以便把量词提到前面。第二步改名，以便把量词提到前面。例题例题3 把公式把公式将约束变元x改名为u，将约束变元y改名为z，化为前束范式化为前束范式.定义定义2-6.2 一个一个wffA称为前束合取范式，如果它有如下称为前束合取范式，如果它有如下形式：形式：(Q1x1)(Q2x2)(Qkxk)(A11A12A1l1)(A21A22A2l2)(Am1Am2Amlm)其中：其中：vQi(1ik)为量词为量词 或或，vxi(i=1,2,n)是客体变元，是客体变元，vAij是原子公式或其否定。是原子公式或其否定。二、前束合取范式二、前束合取范式.是前束合取范式是前束合取范式举例举例.定理定理2-6.2 每一个每一个wffA都可转化为与其等价的前束合都可转化为与其等价的前束合取范式。取范式。证明：略。证明：略。.例题例题4 将将wffD：转化为与其等价的前束合取范式。转化为与其等价的前束合取范式。解解 第一步取消多余量词第一步取消多余量词第二步换名第二步换名第三步消去条件联结词第三步消去条件联结词第四步将否定深入第四步将否定深入第五步将量词推到左边第五步将量词推到左边D(x)(z)(w)(P(x)R(x,w)(Q(z,y)R(x,w)第六步化为合取范式第六步化为合取范式.求前束合取范式的方法求前束合取范式的方法第一步：消去多余量词第一步：消去多余量词第二步：换名第二步：换名第三步：消去条件联结词第三步：消去条件联结词第四步：将否定深入第四步：将否定深入第五步：将量词推到左边第五步：将量词推到左边第六步：化为合取范式第六步：化为合取范式.定义定义2-6.3 一个一个wffA称为前束析取范式，如果它有称为前束析取范式，如果它有如下形式：如下形式：(Q1x1)(Q2x2)(Qkxk)(A11A12A1l1)(A21A22A2l2)(Am1Am2Amlm)其中其中:Qi(1ik)为量词为量词 或或，xi(i=1,2,n)是客体变元，是客体变元，Aij是原子公式或其否定。是原子公式或其否定。二、前束析取范式二、前束析取范式.举例举例是前束是前束析析取范式。取范式。).定理定理2-6.3 每一个每一个wffA都可转化为与其等价的前束都可转化为与其等价的前束析取范式。析取范式。证明：略。证明：略。.例题例题4 将将wffD：转化为与其等价的前束析取范式。转化为与其等价的前束析取范式。解解.求前束析取范式的方法求前束析取范式的方法第一步：消去多余量词第一步：消去多余量词第二步：换名第二步：换名第三步：消去条件联结词第三步：消去条件联结词第四步：将否定深入第四步：将否定深入第五步：将量词推到左边第五步：将量词推到左边第六步：化为第六步：化为析析取范式取范式.作业P75:（1）b),（2）b、c).27 谓词演算的推理理论谓词演算的推理理论v谓词逻辑是命题逻辑的进一步深化和发展，谓词演谓词逻辑是命题逻辑的进一步深化和发展，谓词演算的推理方法，可以看作是命题演算推理方法的扩算的推理方法，可以看作是命题演算推理方法的扩张。因此命题逻辑的推理理论在谓词逻辑中几乎可张。因此命题逻辑的推理理论在谓词逻辑中几乎可以完全照搬，只不过这时涉及的公式是谓词逻辑的以完全照搬，只不过这时涉及的公式是谓词逻辑的公式罢了。公式罢了。v在谓词逻辑中，某些前提和结论可能受到量词的约在谓词逻辑中，某些前提和结论可能受到量词的约束，为确立前提和结论之间的内部联系，有必要消束，为确立前提和结论之间的内部联系，有必要消去量词和添加量词，因此正确理解和运用有关量词去量词和添加量词，因此正确理解和运用有关量词规则是谓词逻辑推理理论中十分重要的关键所在。规则是谓词逻辑推理理论中十分重要的关键所在。.一、有关量词消去和添加规则一、有关量词消去和添加规则量词消去规则：量词消去规则：(1)全称量词消去规则：称为全称指定规则，简称全称量词消去规则：称为全称指定规则，简称US规则规则(2)存在量词消去规则：称为存在指定规则，简称存在量词消去规则：称为存在指定规则，简称ES规则规则量词产生规则：量词产生规则：(3)存在量词产生规则：称为存在推广规则，简称存在量词产生规则：称为存在推广规则，简称EG规则规则(4)全称量词产生规则：称为全称推广规则，简称全称量词产生规则：称为全称推广规则，简称UG规则规则.全称（U）存在（E）消去规则消去规则USES产生规则产生规则UGEG.量词消去规则：量词消去规则：(1)全称量词消去规则全称量词消去规则(称为全称指定规则，简称称为全称指定规则，简称US规规则则)(x)A(x)A(c)，其中，其中c为任意个体常元为任意个体常元.量词消去规则：量词消去规则：(2)存在量词消去规则存在量词消去规则(称为存在指定规则，简称称为存在指定规则，简称ES规规则则)(x)A(x)A(c)，其中，其中c为特定个体常元为特定个体常元成立充分条件是：成立充分条件是：c不得在前提中或者居先推导公式中出现或不得在前提中或者居先推导公式中出现或自由出现；自由出现；.量词产生规则：量词产生规则：(3)存在量词产生规则存在量词产生规则(称为存在推广规则，简称称为存在推广规则，简称EG规规则则)A(c)(y)A(y)，其中，其中c为特定个体常元为特定个体常元 成立充分条件：取代成立充分条件：取代c的个体变元的个体变元y不在不在A(c)中出现；中出现；.量词产生规则：量词产生规则：(4)全称量词产生规则全称量词产生规则(称为全称推广规则，简称称为全称推广规则，简称UG规规则则)A(x)(y)A(y)成立条件：必须能够证明前提成立条件：必须能够证明前提A(x)对于对于x的任意取值的任意取值都成立；都成立；.真值表法：前真：看后真；后假：前至少有一个假。直接证法：由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式，推演得到有效的结论。间接证法要证明H1 H2 Hn C，只要证明H1，H2，Hn与是C是不相容的。要证明H1 H2 Hn(R C)。如能证明H1 H2 Hn R C，即证得H1 H2 Hn(RC)。这个证明称为CP规则。命题推理方法.二、二、Lp中推理实例中推理实例v Lp的推理方法是的推理方法是Ls推理方法的扩展，因此在推理方法的扩展，因此在Lp中利用的推理规则也是中利用的推理规则也是T规则、规则、P规则和规则和CP规则，还有已知的等价式，蕴含式以及有规则，还有已知的等价式，蕴含式以及有关量词的消去和产生规则。关量词的消去和产生规则。v使用的推理方法是直接构造法和间接证法。使用的推理方法是直接构造法和间接证法。.例题例题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）两条次序不能颠倒。(x)(C(x)W(x)R(x)(x x)(C(x)Q(x)(x x)(Q(x)R(x)(1)(x)(C(x)W(x)R(x)P(2)(x 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 x)(Q(x)R(x)EG.例题例题3 证明证明(x)(P(x)Q(x)(x)P(x)(x x)Q(x)用间接证法。要证用间接证法。要证S SC C，即要证即要证S SC CT T，而而S SC CS SC C，所以所以S SC CT T即即S SC CT T，亦就是亦就是(S SC)C)F F，S SC CF F。假定假定C C为为T T，推出矛盾。推出矛盾。(1)(x)P(x)(x x)Q(x)P(附加前附加前提提)(2)(x x)P(x)(x)Q(x)T(1)E(3)(x 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 x)Q(x)复习复习CPCP规则规则要证要证S SR RC C ，即要证即要证S S(R RC)C)T,T,即即S S(R RC)C)T,T,(S SR)R)C CT,T,(S SR)R)C CT,T,(S SR)R)C CT T也就是证明也就是证明(S SR)R)C 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 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 x)(P(x)S(x)(x x)(P(x)Q(x)S(x)(1)(x 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 x)(P(x)Q(x)S(x)EG(9).作业P79:1b)d),2,3a)b).