离散数学PPT学习教案

1、会计学1离散数学离散数学第1页/共52页四、谓词演算的等价式和蕴含式四、谓词演算的等价式和蕴含式1、命题公式的推广、命题公式的推广v结论结论：命题演算中的等价公式表和蕴含公式表都：命题演算中的等价公式表和蕴含公式表都可推广到谓词演算中使用。可推广到谓词演算中使用。PQPQ ()( ( )( )()( )( )x P xQ xxP xQ x () ( )() ( , )( ()( ( )() ( , )x P xy R x yx P xy R x y ()PQPQ PPF()( , )()( , )x H x yx H x yF 命题演算的等价式命题演算的等价式谓词演算的等价式谓词演算的等价式第

2、2页/共52页2、量词与联结词、量词与联结词之间的关系之间的关系v将量词前面将量词前面的移到量词后面去时，存在量的移到量词后面去时，存在量词改为全称量词，全称量词改为存在量词；词改为全称量词，全称量词改为存在量词；v反之，将量词后面的反之，将量词后面的移到量词前面去时，移到量词前面去时，也要做相应的改变。也要做相应的改变。( x)P(x) ( x)P(x)( x)P(x) ( x)P(x)第3页/共52页 这里这里A(x)是任意包括个体变元是任意包括个体变元x的谓词公式的谓词公式，B是不包括个体变元是不包括个体变元x的任意谓词公式。的任意谓词公式。3、量词扩张、量词扩张/收缩律收缩律(1)第4

3、页/共52页( ( x)Ax)A(x)B (x)B ( ( x)(Ax)(A(x)B)(x)B)第5页/共52页3、量词扩张、量词扩张/收缩律收缩律(2)() ( )()( ( )x A xBxA xB () ( )()( ( )x A xBxA xB () ( )()( )Bx A xx BA x () ( )()( )Bx A xx BA x 这里这里A(x)是任意包括个体变元是任意包括个体变元x的谓词公式的谓词公式，B是不包括个体变元是不包括个体变元x的任意谓词公式。的任意谓词公式。第6页/共52页第7页/共52页第8页/共52页4、量词与命题联结词之间的一些等价式、量词与命题联结词之间

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)第9页/共52页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)(A

5、x)(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)第10页/共52页n故故( x)A(x)( x)B(x)( x)(A(x)B(x)第11页/共52页 表表 2 1 谓词演算中常用的等价式和蕴含式谓词演算中常用的等价式和蕴含式第12页/共52页6、多个量词的使用、多个量词的使用考虑两个量词的情况。更多量词的使用方法与其类似。考虑两个量词的情况。更多量词的使用方法与其类似。对

6、于二元谓词如果不考虑自由变元，可以有以下八种情况。对于二元谓词如果不考虑自由变元，可以有以下八种情况。()() ( , )xy A x y()() ( , )yx A x y()() ( , )yx A x y()() ( , )yx A x y()() ( , )xy A x y()() ( , )xy A x y()() ( , )xy A x y()() ( , )yx A x y 全称量词与存在量词在公式中出现的次序，不能随意更换。全称量词与存在量词在公式中出现的次序，不能随意更换。用双向箭头表示等价，单向箭头表示蕴含，见它们之间的关系。用双向箭头表示等价，单向箭头表示蕴含，见它们之间

7、的关系。第13页/共52页()() ( , )()() ( , )xy A x yyx A x y ()() ( , )()() ( , )xy A x yyx A x y 有两个等价关系：有两个等价关系：第14页/共52页()() ( , )()() ( , )xy A x yyx A x y ()() ( , )()() ( , )yx A x yxy A x y ()() ( , )()() ( , )yx A x yxy A x y ()() ( , )()() ( , )xy A x yyx A x y ()() ( , )()() ( , )yx A x yxy A x y ()(

8、) ( , )()() ( , )xy A x yyx A x y 具有两个量词的谓词公式有如下一些蕴含关系：具有两个量词的谓词公式有如下一些蕴含关系：第15页/共52页第16页/共52页第17页/共52页第18页/共52页第19页/共52页第20页/共52页举例举例73页 例题1、例题2、例题3第21页/共52页例题例题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)

9、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)第22页/共52页()() ( , )()() ( , )()( ( , )( , )xy A x yxy B x yy A y xB x y () () ( , )()() ( , )()( ( , )(

10、 , )xy A x yxy B x yy A y xB x y ()() ( , ) ()()( , ) () ( ( , )( , )xy A x yxyB x yyA y xB x y 解解 第一步否定深入第一步否定深入原式原式第二步改名，以便把量词提到前面。第二步改名，以便把量词提到前面。()() ( , )()()( , )() ( ( , )( , )xy A x yuvB u vzA z uB u z ()()()()() ( , ) ( , )( ( , )( , )xyuvzA x yB u vA z uB u z 例题例题3 把公式把公式将约束变元x改名为u，将约束变元y改

11、名为z，化为前束范式化为前束范式第23页/共52页第24页/共52页第25页/共52页()()()()() ( )()xzyPxazbQ yab ( )()( )( ( )( ) ( ( )( , ) ( , )( ) ( , )( , )xuz P xPuP xQ y zQx yPuQx yQ y z 是前束合取范式是前束合取范式第26页/共52页定理定理2-6.2 每一个每一个wffA都可转化为与其等价的前束合都可转化为与其等价的前束合取范式。取范式。证明：略。证明：略。第27页/共52页例题例题4 将将wffD： 转化为与其等价的前束合取范式。转化为与其等价的前束合取范式。()() (

12、)() ( , )() ( , )xy P xz Q z yy R x y () ( ) () ( , )() ( , )Dx P xz Q z yy R x y () ( ) () ( , )() ( , )Dx P xz Q z ywR x w 解解 第一步取消多余量词第一步取消多余量词第二步换名第二步换名第三步消去条件联结词第三步消去条件联结词第四步将否定深入第四步将否定深入第五步将量词推到左边第五步将量词推到左边() ( ( ) () ( , )() ( , )DxP xz Q z yw R x w ()( ) ( )( , ) ()( , )DxP xzQ z yw R x w ()

13、()()( )( , )( , )DxzwP xQ z yR x w D( x)( z)( w)(P(x)R(x,w)(Q(z,y)R(x,w)第六步化为合取范式第六步化为合取范式第28页/共52页第29页/共52页第30页/共52页举例举例是前束是前束析析取范式。取范式。()()()( ( )( , )( ( )( , )xuzP xQ x yP uQ y z)第31页/共52页定理定理2-6.3 每一个每一个wffA都可转化为与其等价的前束都可转化为与其等价的前束析取范式。析取范式。证明：略。证明：略。第32页/共52页例题例题4 将将wffD： 转化为与其等价的前束析取范式。转化为与其等

14、价的前束析取范式。()( ( )( , )() ( )() ( , )x P xQ x yy P yz Q y z ()( )( , ) () ( ) () ( , )DxP xQ x yy P yz Q y z ()( ( )( , ) () ( ) () ( , )x P xQ x yu P uz Q y z ()()()( ( )( , ) ( ( )( , )xuz P xQ x yP uQ y z 解解第33页/共52页第34页/共52页第35页/共52页第36页/共52页第37页/共52页量词消去规则：量词消去规则：(1)全称量词消去规则：称为全称指定规则，简称全称量词消去规则：称

15、为全称指定规则，简称US规则规则(2)存在量词消去规则：称为存在指定规则，简称存在量词消去规则：称为存在指定规则，简称ES规则规则量词产生规则：量词产生规则：(3)存在量词产生规则：称为存在推广规则，简称存在量词产生规则：称为存在推广规则，简称EG规则规则(4)全称量词产生规则：称为全称推广规则，简称全称量词产生规则：称为全称推广规则，简称UG规则规则第38页/共52页全称（U）存在（E）消去规则消去规则USES产生规则产生规则UGEG第39页/共52页(1) 全称量词消去规则全称量词消去规则(称为全称指定规则，简称称为全称指定规则，简称US规规则则)( x)A(x)A(c) ，其中，其中c为

16、任意个体常元为任意个体常元第40页/共52页(2)存在量词消去规则存在量词消去规则(称为存在指定规则，简称称为存在指定规则，简称ES规规则则)( x)A(x)A(c)，其中，其中c为特定个体常元为特定个体常元成立充分条件是：成立充分条件是：c不得在前提中或者居先推导公式中出现或不得在前提中或者居先推导公式中出现或自由出现；自由出现；第41页/共52页(3) 存在量词产生规则存在量词产生规则(称为存在推广规则，简称称为存在推广规则，简称EG规规则则)A(c)( y)A(y)，其中，其中c为特定个体常元为特定个体常元 成立充分条件：取代成立充分条件：取代c的个体变元的个体变元y不在不在A(c)中出

17、中出现；现；第42页/共52页(4) 全称量词产生规则全称量词产生规则(称为全称推广规则，简称称为全称推广规则，简称UG规则规则)A(x)( y)A(y)成立条件：必须能够证明前提成立条件：必须能够证明前提A(x)对于对于x的任意取的任意取值都成立；值都成立；第43页/共52页第44页/共52页第45页/共52页解解 设设 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(

18、1)(3) H(s) P(4) M(s) T(2)(3)I第46页/共52页例题例题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)

19、R(x) EG第47页/共52页例题例题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第48页/共52页证法证法2 本题可用本题可用CP规则规则原题为原题为( x)(P(x)Q(x)( x)P(x)( x x)Q(x)复习复习CPCP规则规则要证要证S SR RC C ，