离散数学第2章-命题逻辑等值演算ppt课件.ppt
《离散数学第2章-命题逻辑等值演算ppt课件.ppt》由会员分享,可在线阅读,更多相关《离散数学第2章-命题逻辑等值演算ppt课件.ppt(49页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、6/20/2022 3:02 PM Discrete Math. , Chen Chen1离散数学离散数学Discrete MathematicsDiscrete Mathematics 6/20/2022 3:02 PM Discrete Math. , Chen Chen2第二章第二章 命题逻辑等值演算命题逻辑等值演算Chapter TwoProposition Logic6/20/2022 3:02 PM Discrete Math. , Chen Chen32.1 等值式等值式2.2 析取范式与合取范式析取范式与合取范式2.3 联结词的完备集联结词的完备集等值式定义等值式定义基本等值式
2、基本等值式等值演算(置换规则)等值演算(置换规则)简单析取(合取)式简单析取(合取)式极大(小)项极大(小)项(主)析(合)取范式(主)析(合)取范式真值函数真值函数联结词完备集联结词完备集2.4 可满足性问题与消解法可满足性问题与消解法6/20/2022 3:02 PM Discrete Math. , Chen Chen4 设公式、中总共含有命题变项设公式、中总共含有命题变项p1, p2, pn,但或并,但或并不全含有这些变项。如果某个变项不全含有这些变项。如果某个变项未在未在公式中公式中出现出现,则称该,则称该变项为的变项为的哑元哑元。同样可定义的哑元。同样可定义的哑元。 在讨论与是否有
3、相同的真值表时,应将哑元考虑在内,在讨论与是否有相同的真值表时,应将哑元考虑在内,即将、都看成含所有即将、都看成含所有p1 , p2 , pn的命题公式,如果在所有的命题公式,如果在所有2n个赋值下,与的真值相同,则个赋值下,与的真值相同,则为重言式。为重言式。6/20/2022 3:02 PM Discrete Math. , Chen Chen5定义定义2.1 设设A ,B 是两个命题公式,若是两个命题公式,若A, B构成的构成的等价式等价式A B为为重言式重言式,则称,则称A与与B是是等值等值的的, 记为记为AB。例例2.1 判断公式判断公式(pq) (pq) 与与 pqpq是否等值。是
4、否等值。解:用真值表法判断解:用真值表法判断, 如下:如下:p qppqqpqpq(pq)(pq)pqpq(pq)(pq)(pq)pq)0 00 00 10 11 01 01 11 1注:注:A A与与B B等值当且仅当等值当且仅当A A与与B B的真值表相同。因此,检验的真值表相同。因此,检验A A与与B B是是否等值,也可通过检查否等值,也可通过检查A A与与B B的真值表是否相同来实现。的真值表是否相同来实现。从表中可见,从表中可见,(pq)(pq)与与pqpq等值。等值。1 11 10 01 11 11 11 10 01 10 00 01 10 01 11 10 00 01 10 00
5、 01 10 00 01 16/20/2022 3:02 PM Discrete Math. , Chen Chen6 (1) p(qr) (1) p(qr)与与(pq)r; (2)(pq)r (pq)r; (2)(pq)r 与与(pq)r(pq)r。解:所给的解:所给的4 4个公式的真值表如下:个公式的真值表如下:p q rp(qr)p(qr)(pq)r(pq)r(pq)r(pq)r0 0 00 0 00 0 10 0 10 1 00 1 00 1 10 1 11 0 01 0 01 0 11 0 11 1 01 1 01 1 11 1 1但但(pq)r(pq)r(pq)r.(pq)r.1
6、11 10 01 11 11 11 11 10 01 11 11 11 11 11 11 11 11 10 00 00 01 11 11 1由真值表可见,由真值表可见,p(qr)p(qr)(pq)r(pq)r, ,例例2.2 判断下列两组公式是否等值:判断下列两组公式是否等值:6/20/2022 3:02 PM Discrete Math. , Chen Chen7 当命题公式中变项较多时,用上述方法判断两个公式是否当命题公式中变项较多时,用上述方法判断两个公式是否等值计算量很大。为此,人们将一组经检验为正确的等值式作等值计算量很大。为此,人们将一组经检验为正确的等值式作为为等值式模式等值式模
7、式,通过公式间的,通过公式间的等值演算等值演算来判断两公式是否等值。来判断两公式是否等值。常用的常用的等值式模式等值式模式如下:如下: 1.1.双重否定律:双重否定律:A A (A) 2. (A) 2.幂等律:幂等律:A AAA, AAA, AAAAA 3. 3.交换律交换律: AB: ABBA, ABBA, ABBABA 4. 4.结合律结合律: (AB)C: (AB)CA(BC), (AB)CA(BC), (AB)CA(BC)A(BC) 5. 5.分配律:分配律:A(BC)A(BC)(AB)(AC) (AB)(AC) (对对的分配律的分配律) ) A(BC) A(BC)(AB)(AC) (
8、AB)(AC) (对对的分配律的分配律) ) 6. 6.德摩根律:德摩根律:(AB)(AB) AB, (AB) AB, (AB)ABAB 7. 7.吸收律:吸收律:A(AB)A(AB)A, A(AB)A, A(AB)A A6/20/2022 3:02 PM Discrete Math. , Chen Chen88.8.零律:零律:A1A11, A01, A00 09. 9. 同一律:同一律:A0A0A, A1A, A1A A10. 10. 排中律:排中律:AAAA1 111. 11. 矛盾律:矛盾律:AAAA0 012. 12. 蕴含等值式:蕴含等值式:ABABABAB13. 13. 等价等值
9、式等价等值式: (A: (AB)B)(AB)(BA)(AB)(BA)14. 14. 假言易位假言易位: AB: AB BA BA15. 15. 等价否定等值等价否定等值式式: A: AB BAABB16. 16. 归谬论归谬论: (AB)(AB) : (AB)(AB) A A6/20/2022 3:02 PM Discrete Math. , Chen Chen9 利用这利用这1616组组2424个等值式可以推演出更多的等值式。由已个等值式可以推演出更多的等值式。由已知的等值式推演出另一些等值式的过程称为知的等值式推演出另一些等值式的过程称为等值演算等值演算。在等。在等值演算中值演算中, ,经
10、常用到如下置换规则。经常用到如下置换规则。置换规则置换规则: : 设设(A)(A)是含公式是含公式A A的命题公式,的命题公式,(B)(B)是用公式是用公式B B置换置换了了(A)(A)中中所有所有的的A A后所得的公式。若后所得的公式。若B BA A, ,则则(B)(B)(A)(A)。 6/20/2022 3:02 PM Discrete Math. , Chen Chen10 例如,对公式例如,对公式(pq)r,(pq)r,如果用如果用pqpq置换置换其中的其中的pq,pq,则则得得(pq)r.(pq)r.由于由于pqpqpqpq,故,故(pq)r (pq)r (pq)r(pq)r。类似地
11、,可进行如下类似地,可进行如下等值演算等值演算: (pq)r (pq)r (pq)r(pq)r (pq)r (pq)r (pq)r (pq)r (pr)(qr(pr)(qr) )为简便起见为简便起见, 以后凡用到置换规则时以后凡用到置换规则时, 均不必标出。均不必标出。( (蕴含等值式,置换规则)蕴含等值式,置换规则)( (蕴含等值式,置换规则)蕴含等值式,置换规则)( (德摩根律,置换规则)德摩根律,置换规则)( (分配律,置换规则)分配律,置换规则)6/20/2022 3:02 PM Discrete Math. , Chen Chen11例例2.3 用等值演算证明用等值演算证明: (p:
12、 (pq)q)r (pr)(qr)(pr)(qr) 注:注:用等值演算证明等值式时,既可以从左向右推演,也可以用等值演算证明等值式时,既可以从左向右推演,也可以从右向左推演。从右向左推演。证:证:(pr)(qr(pr)(qr) )(pr)(qr(pr)(qr) )(pq)r(pq)r(pq)r(pq)r(pq)r (pq)r ( (蕴含等值式蕴含等值式) )( (分配律分配律) )( (德摩根律德摩根律) )( (蕴含等值式蕴含等值式)6/20/2022 3:02 PM Discrete Math. , Chen Chen12 证明:证明:(pq)r (pq)r p(qr p(qr). .方法
13、三方法三: : 记记A=(pq)r, B= p(qr)A=(pq)r, B= p(qr)。先将。先将A,BA,B等值演算等值演算 化成易于观察真值的公式,再进行判断。化成易于观察真值的公式,再进行判断。 A=(pq)rA=(pq)r(pq)r(pq)r (pq)r (pq)r (pq)r(pq)r B=p(qr) B=p(qr)p(qrp(qr) ) pqrpqr 易见,易见,000000,010010是是A A的成假赋值,而它们是的成假赋值,而它们是B B的成真赋值。的成真赋值。方法二:观察法。方法二:观察法。 (pq)r (pq)r p(qr p(qr) )。证证 方法一:真值表法。方法一
14、:真值表法。故故 ( (蕴含等值式蕴含等值式) ) ( (蕴含等值式蕴含等值式) ) ( (德摩根律德摩根律) )( (蕴含等值式蕴含等值式) )( (结合律结合律) )6/20/2022 3:02 PM Discrete Math. , Chen Chen13(1)(pq)pq; (2) (p(pq)r; (3) p(pq)p)q).解解: (1) (pq)pq (pq)pq (pq)p)q (pq)p)q (pq)p)q (pp)(qp)q (1(qp)q (qp)q (qq)p 1p 1 故故 (pq)pq是重言式。是重言式。用等值演算判断下列公式的类型用等值演算判断下列公式的类型(蕴含
15、等值式蕴含等值式)(蕴含等值式蕴含等值式)(德摩根律德摩根律)(德摩根律德摩根律)(分配律分配律)(排中律排中律)(同一律)同一律)(交换律,结合律)交换律,结合律)(排中律)(排中律)(零律)(零律)6/20/2022 3:02 PM Discrete Math. , Chen Chen14(2) (2) (p(pq)r (ppq)r (pp q)r (0q)r 0r 0 故故 (p(pq)r是矛盾式。是矛盾式。( (蕴含等值式,结合律)蕴含等值式,结合律) ( (德摩根律)德摩根律)( (矛盾律)矛盾律)( (零律零律) )( (零律)零律)6/20/2022 3:02 PM Discre
16、te Math. , Chen Chen15(3) p(pq)p)q) p(pq)p)q) ( (蕴含等值式蕴含等值式) ) p(pp)(qp)q) ( (分配律分配律) ) p(0(qp)q) ( (矛盾律矛盾律) ) p(qp)q) ( (同一律同一律) ) p(qp)q) ( (德摩根律,双重否定律德摩根律,双重否定律) ) p(qq)p) ( (交换律,结合律交换律,结合律) ) p(1p) (排中律)(排中律) p1 (零律)(零律) p (同一律)(同一律) 可见,(可见,(3 3)中公式不是重言式,因为)中公式不是重言式,因为0000,01 01 都是成假赋值;都是成假赋值;它也
17、不是矛盾式,因为它也不是矛盾式,因为1010,11 11 都是其成真赋值,故它是可满足都是其成真赋值,故它是可满足式。式。6/20/2022 3:02 PM Discrete Math. , Chen Chen16例例2.6 在某次研讨会的休息时间,在某次研讨会的休息时间,3名与会者根据王教授的口音名与会者根据王教授的口音对他是哪个省市的人进行了判断:对他是哪个省市的人进行了判断: 甲说王教授不是苏州人,是上海人。甲说王教授不是苏州人,是上海人。 乙说王教授不是上海人,是苏州人。乙说王教授不是上海人,是苏州人。 丙说王教授不是上海人,也不是杭州人。丙说王教授不是上海人,也不是杭州人。听完听完3
18、人的判断,王教授笑着说,他们人的判断,王教授笑着说,他们3人中有一人说得全对,人中有一人说得全对,有一人说对了一半,有一人说得全不对。试用逻辑演算法分析有一人说对了一半,有一人说得全不对。试用逻辑演算法分析王教授到底是哪里的人?王教授到底是哪里的人? 解解: 设命题设命题 p, q, r分别表示分别表示 : 王教授是苏州、上海、杭州人。王教授是苏州、上海、杭州人。则则p, q, r中必有一个真命题,两个假命题。要通过逻辑演算将中必有一个真命题,两个假命题。要通过逻辑演算将真命题找出来。真命题找出来。设:设: 甲的判断为:甲的判断为: A1= pq; 乙的判断为:乙的判断为:A2= pq; 丙的
19、丙的判断为:判断为:A3= qr。 6/20/2022 3:02 PM Discrete Math. , Chen Chen17那么甲的判断全对:那么甲的判断全对: B1= A1= pq 甲的判断对一半:甲的判断对一半: B2=(pq)(pq) 甲的判断全错:甲的判断全错: B3=pq 乙的判断全对:乙的判断全对: C1= A2= pq 乙的判断对一半:乙的判断对一半: C2=(pq)(pq) 乙的判断全错:乙的判断全错: C3=pq 丙的判断全对:丙的判断全对: D1= A3=qr 丙的判断对一半:丙的判断对一半: D2=(qr)(qr) 丙的判断全错:丙的判断全错: D3=qr 由王教授所
20、说由王教授所说 E=(B1C2D3) (B1C3D2) (B2C1D3) (B2C3D1) (B3C1D2) (B3C2D1) 为真命题为真命题. 6/20/2022 3:02 PM Discrete Math. , Chen Chen18B1C2D3=(pq) (pq)(pq)(qr) (pqqr) (pqpr)0B1C3D2=(pq)(pq)(qr)(qr) (pqr) (pqqr) pqrB2C1D3=(pq)(pq) (pq)(qr) (pppqqr) (pqqr) 0类似可得类似可得 B2C3D10, B3C1D2pqr, B3C2D10于是,由同一律可知于是,由同一律可知 E(pq
21、r) (pqr)但因为王教授不能既是苏州人,又是杭州人,因而但因为王教授不能既是苏州人,又是杭州人,因而p,r必有一个为假命必有一个为假命题,即题,即pqr0 。于是于是 Epqr 为真命题,因而必有为真命题,因而必有p,r为假命题,为假命题,q为真命题,为真命题,即王教授为上海人,甲说得全对,丙说对了一半,而乙全说错啦。即王教授为上海人,甲说得全对,丙说对了一半,而乙全说错啦。 6/20/2022 3:02 PM Discrete Math. , Chen Chen19定义定义2.22.2 命题变项及其否定统称作命题变项及其否定统称作文字文字。 仅由有限个文字构成的仅由有限个文字构成的析取式
22、析取式称作称作简单析取式简单析取式; 仅由有限个文字构成的仅由有限个文字构成的合取式合取式称作称作简单合取式简单合取式。例如:例如:p p; p p; q qq q; pq; p pq qr r都是简单析取式都是简单析取式. p p; p p; q qq q; p pq qr r; p pppr r都是简单合取式。都是简单合取式。注:注:单个文字单个文字既是简单析取式又是简单合取式。既是简单析取式又是简单合取式。定理定理2.12.1 (1)一个简单析取式是重言式当且仅当它同时含有某一个简单析取式是重言式当且仅当它同时含有某个命题变项及它的否定式;个命题变项及它的否定式;(2)一个简单合取式是矛
23、盾式当且仅当它同时含有某个命题一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及其否定式。变项及其否定式。6/20/2022 3:02 PM Discrete Math. , Chen Chen20例如:例如:(p(pq)q)( (q qr)r)r r是一个析取范式,是一个析取范式, 而而 (p(pq qr)r)( (p pq)q)r r是一个合取范式。是一个合取范式。注:注:单个文字单个文字既是简单析取式又是简单合取式。既是简单析取式又是简单合取式。 因此形如因此形如p pq qr r的公式既是由一个简单合取式构成的析的公式既是由一个简单合取式构成的析取范式,又是由三个简单析取式构成的合
24、取范式。取范式,又是由三个简单析取式构成的合取范式。类似地,形如类似地,形如p pq qr r的公式既可看成析取范式也可看成的公式既可看成析取范式也可看成合取范式。合取范式。定义定义2.32.3 由有限个简单合取式构成的析取式称为由有限个简单合取式构成的析取式称为析取范式析取范式;由有限个简单析取式构成的合取式成为由有限个简单析取式构成的合取式成为合取范式合取范式;析取范式与合取范式统称为析取范式与合取范式统称为范式范式。6/20/2022 3:02 PM Discrete Math. , Chen Chen21析取范式的一般形式:析取范式的一般形式: AA1 A2 An, 其中其中 Ai (
25、i=1,n)是简单合取式;是简单合取式;合取范式的一般形式:合取范式的一般形式: AA1 A2 An, 其中其中 Ai (i=1,n)是简单析取式是简单析取式 。定理定理2.22.2 (1 1)一个析取范式是矛盾式当且仅当它的每个简一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式;单合取式都是矛盾式;(2)一个合取范式是重言式当且仅当它的每个简单析取式)一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。都是重言式。6/20/2022 3:02 PM Discrete Math. , Chen Chen22定理定理2.32.3(范式存在定理)(范式存在定理)任一命题公式都存在着与
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 命题逻辑 等值 演算 ppt 课件
限制150内