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

《离散数学第2章第3节.ppt》由会员分享，可在线阅读，更多相关《离散数学第2章第3节.ppt（52页珍藏版）》请在三一办公上搜索。

1、离 散 数 学Discrete Mathematics,山东科技大学信息科学与工程学院,上次课回顾,指导变元、作用域、约束变元、自由变元、闭式约束变元换名和自由变元代入有限论域客体变元的枚举谓词公式赋值、谓词公式等价、永真式、不可满足式、可满足式谓词公式的等价式和蕴含式,四、谓词演算的等价式和蕴含式,1、命题公式的推广,结论：命题演算中的等价公式表和蕴含公式表都可推广到谓词演算中使用。,命题演算的等价式,谓词演算的等价式,2、量词与联结词之间的关系,将量词前面的移到量词后面去时，存在量词改为全称量词，全称量词改为存在量词；反之，将量词后面的移到量词前面去时，也要做相应的改变。,(x)P(x)(

2、x)P(x),(x)P(x)(x)P(x),这里A(x)是任意包括个体变元x的谓词公式，B是不包括个体变元x的任意谓词公式。,3、量词扩张/收缩律(1),证明 当B为真时,左右两边都为真;否则,B为假,此时左右两边都等价于(x)A(x),证迄.,(x)A(x)B(x)(A(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(

3、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)A(x)(x)B(x)(x)(A(x)B(x),(x)(A(x)B(x)(x)A(x)(x)B(x),(x)A(x)(x)B(x)(x)(A(x)B(x),(x)(A(x)B(x)(x)A(x)(x)B(

4、x),(x)(A(x)B(x)(x)A(x)(x)B(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、多个量词的使用,考虑两个量词的情况。更多量词的使用方法与其类似。,对于二元谓词如果不考虑自由变元，可以有以下八种情况。,全称量词与存在量词在公式中出现的次序，不能随意更换。用双向箭头表示等

5、价，单向箭头表示蕴含，见它们之间的关系。,有两个等价关系：,具有两个量词的谓词公式有如下一些蕴含关系：,作业,P66:3,4,5 P72:2a),4,7,定义2-6.1 一个合式公式称为前束范式，如果它有如下形式：(Q1x1)(Q2x2)(Qkxk)A其中Qi(1ik)为或,A为不含有量词的谓词公式。特别地，若谓词公式中无量词，则该公式也看作是前束范式。前束范式的特点:所有量词均非否定地出现在公式最前面，且它的辖域一直延伸到公式之末。,一、前束范式,例如，(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)不是

6、前束范式。,定理2.6.1(前束范式存在定理)任意谓词公式A都有与之等价的前束范式。证明：,前束范式的求取方法,举例73页 例题1、例题2、例题3,例题2 化公式(x)(y)(z)(P(x,z)P(y,z)(u)Q(x,y,u)为前束范式,解 原公式(x)(y)(z)(P(x,z)P(y,z)(u)Q(x,y,u),(x)(y)(z)(P(x,z)P(y,z)(u)Q(x,y,u),(x)(y)(z)(u)(P(x,z)P(y,z)Q(x,y,u),解 第一步否定深入,原式,第二步改名，以便把量词提到前面。,例题3 把公式,将约束变元x改名为u，将约束变元y改名为z，,化为前束范式,练习,(x

7、)(y)(z)P(x,y,z)(u)Q(x,u)(v)Q(y,v)(x)(y)(z)P(x,y,z)(u)Q(x,u)(v)Q(y,v)(x)(y)(z)P(x,y,z)(u)Q(x,u)(v)Q(y,v)(x)(y)(z)(u)(v)(P(x,y,z)Q(x,u)Q(y,v),定义2-6.2 一个wffA称为前束合取范式，如果它有如下形式：(Q1x1)(Q2x2)(Qkxk)(A11A12A1l1)(A21A22A2l2)(Am1Am2Amlm)其中：Qi(1ik)为量词或，xi(i=1,2,n)是客体变元，Aij是原子公式或其否定。,二、前束合取范式,是前束合取范式,举例,定理2-6.2

8、每一个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)(Am1Am

9、2Amlm)其中:Qi(1ik)为量词或，xi(i=1,2,n)是客体变元，Aij是原子公式或其否定。,二、前束析取范式,举例,是前束析取范式。,),定理2-6.3 每一个wffA都可转化为与其等价的前束析取范式。证明：略。,例题4 将wffD：,转化为与其等价的前束析取范式。,解,求前束析取范式的方法,第一步：消去多余量词第二步：换名第三步：消去条件联结词第四步：将否定深入第五步：将量词推到左边第六步：化为析取范式,作业,P75:（1）b),（2）b、c),27 谓词演算的推理理论,谓词逻辑是命题逻辑的进一步深化和发展，谓词演算的推理方法，可以看作是命题演算推理方法的扩张。因此命题逻辑的推理

10、理论在谓词逻辑中几乎可以完全照搬，只不过这时涉及的公式是谓词逻辑的公式罢了。在谓词逻辑中，某些前提和结论可能受到量词的约束，为确立前提和结论之间的内部联系，有必要消去量词和添加量词，因此正确理解和运用有关量词规则是谓词逻辑推理理论中十分重要的关键所在。,回顾：约束变元、自由变元定义2.7.1 在谓词公式A(x)中，若x自由出现在量词(y)或(y)的辖域，则称A(x)对于y是自由的。由定义可知，若y在A(x)中不是约束出现，则A(x)对于y一定是自由的。,一、有关量词消去和添加规则,量词消去规则：(1)全称量词消去规则：称为全称指定规则，简称US规则(2)存在量词消去规则：称为存在指定规则，简称

11、ES规则量词产生规则：(3)存在量词产生规则：称为存在推广规则，简称EG规则(4)全称量词产生规则：称为全称推广规则，简称UG规则,量词消去规则：,(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)中出现

12、；,量词产生规则：,(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中推理实例 Lp的推理方法是Ls推理方法的扩展，因此在Lp中利用的推理规则也是T

13、规则、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）两条次序不能颠倒。,(x)(C(x)W(x)R(x)(x)(C(x)Q(x)(x)(Q(x)R(x),(

14、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

15、)(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（附

16、加前提）,(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),作业,P79:1b)d),2,3a)b),