离散数学-1-7 对偶与范式.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《离散数学-1-7 对偶与范式.ppt》由会员分享,可在线阅读,更多相关《离散数学-1-7 对偶与范式.ppt(39页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第一章 命题逻辑1-7 对偶与范式1尽管命题公式的最小联结词组可为,但实际上一般出于方便的目的,命题公式常常包含,。从第15页的表1-4.8的命题定律中可以看出,很多常用等价式是成对出现的,只要将其中的“”和“”分别换成“”和“”,就可以由一个得到另一个。例如,将命题定律(PQ)RP(QR)中的“”换成“”就得到了命题定律(PQ)RP(QR)。这些成对出现的等价式反映了等价的对偶性等价的对偶性。我们将这样的公式称作具有对偶规律对偶规律。本节将先介绍对偶式和对偶原理。2一、对偶式与对偶原理定义1-7.1 在给定的命题公式A中,将联结词、分别换成、,若有特殊变元F和T亦相互对代,所得的公式称为公式
2、A的对偶式,记为A*。*设A*是A的对偶式,将A*中的,F,T分别换成,T,F,就会得到A。即A是是A*的的对对偶偶式式,(A*)*A。所以说A*和和A互为对偶式互为对偶式。例题1 写出下列表达式的对偶式n1.(PQ)Rn2.(P Q)Tn3.(PQ)(P(Q S)3一、对偶式与对偶原理例题2 求PQ和PQ的对偶式。解:PQ(PQ)(PQ)的对偶式是(PQ)PQ 故PQ的对偶式是PQ;同样的方法可以证明PQ的对偶式是PQ。注注意意:根据例题2,对对偶偶式式概概念念可可以以推推广广为为:在仅含有联结词,的命题公式中,将联结词,F F,T T分别换成,T T,F,就得到了它的对偶式。4一、对偶式与
3、对偶原理*关于对偶式有以下两个结论。定理1-7.1 设A*是A的对偶式,P1,P2,Pn是出现在A和A*中的原子变元,则 A(P1,P2,Pn)A*(P1,P2,Pn)A(P1,P2,Pn)A*(P1,P2,Pn)证明见证明见P30:由德摩根律层层置换,即可层层推出。5一、对偶式与对偶原理例例:设命题公式A(P,Q,R)(PQ)R,试用此公式验证定理1.7.1的有效性。证明:验证 A(P,Q,R)A*(P,Q,R)A(P,Q,R)(PQ)R A(P,Q,R)(PQ)R)(PQ)R A*(P,Q,R)(PQ)R A*(P,Q,R)(PQ)R 所以,A(P,Q,R)A*(P,Q,R)验证 A(P,
4、Q,R)A*(P,Q,R)A(P,Q,R)(PQ)R (PQ)R)A*(P,Q,R)6一、对偶式与对偶原理定理1-7.2 设P1,P2,Pn是出现在公式A和B中的所有原子变元,如果AB,则A*B*。证明:因为 AB,所以 A(P1,P2,Pn)B(P1,P2,Pn)是重言式 根据定理1-5.2(P19),在上述重言式中用Pi置换 Pi,i1,n,所得的公式仍为重言式,即 A(P1,P2,Pn)B(P1,P2,Pn)是重言 式。所以 A(P1,P2,Pn)B(P1,P2,Pn)由定理1-7.1A*(P1,P2,Pn)B*(P1,P2,Pn)即 A*B*因此 A*B*定理1.7.2叫做对对偶偶原原
5、理理。对偶原理是数理逻辑中最基本的规律之一。7一、对偶式与对偶原理例题例题4:如果A(P,Q,R)是P(Q(R P),求它的对偶式A*(P,Q,R)。并求A及A*的等价,但仅包含联结词“”、“”及“”的公式。解:因A(P,Q,R)是P(Q(R P)所以 A*是 P(Q(R P)而 P(Q(R P)(P(Q(RP)故 P(Q(R P)(P(Q(RP)使用真值表和对偶原理可以简化或推证一些命题公式。使用真值表和对偶原理可以简化或推证一些命题公式。8一、对偶式与对偶原理例例:证明重言式的对偶式是矛盾式,矛盾式的对重言式的对偶式是矛盾式,矛盾式的对偶式是重言式。偶式是重言式。证明:设A是重言式,即AT
6、,因为T的对偶式是F,由对偶原理知A*F。所以A*是矛盾式;设A是矛盾式,即A F,而F的对偶式是T,所以A*T。所以A*是重言式。9二、析取范式与合取范式每种数字标准形都能提供很多信息,如代数式的因式分解可判断代数式的根情况。逻辑公式在等值演算下也有标准形-范式,范式有两种:析取范式和合取范式。同一命题公式可以有各种相互等价的表达形式,范式可以实现命题公式的规范化 10二、析取范式与合取范式定义(补充)定义(补充)仅有有限个命题变元或其否定构成的合(析)取式称作简单合简单合(析析)取式取式。如:nP,Q等为一个文字一个文字(一个命题变元或它的否定称为文字一个命题变元或它的否定称为文字)构成的
7、简单合取式,PP,PQ等为2个文字构成的简单合取,PQR,PPQ等为3个文字构成的简单合取式nP,Q等为一个文字一个文字(一个变元或变元的否定)的简单析趋式,PP,PQ等为2个变元(或变元的否定)简单析取式,PQR,PQR等为3个文字构成的简单析取式。11二、析取范式与合取范式定义定义1-7.2 一个命题公式称为合取范式合取范式,当且仅当它具有形式:A1A2An (n 1)其中A1,A2,An 都是简单析取式简单析取式。如:(PQR)(PQ)Q定义定义1-7.2 一个命题公式称为析取范式析取范式,当且仅当它具有形式:A1A2 An (n 1)其中A1,A2,An 都是简单合取式简单合取式。如:
8、P(PQ)(PQR)12二、析取范式与合取范式任何命题公式都可以化成与其等价的析取范式或合取范式。求析取范式和合取范式的步骤如下:消去联结词“”和“”,化归成、P Q P Q P Q(P Q)(P Q)(P Q)(Q P)(P Q)(Q P)(2)利用双重否定律消去否定联结词“”或利用德摩根律将否定联结词“”移到各命题变元前(内移)利用分配律、结合律将公式归约为合取范式或析取范式。P(Q R)?13二、析取范式与合取范式例:求命题公式(PQ)P的合取范式和析取范式。解:求合取范式 (PQ)P (PQ)P)(P(PQ)(消去)(PQ)P)(P(PQ)(消去)(PQ)P)(P(PQ)(内移)(PP
9、)(QP)(PPQ)(分配律,合取范式)1(QP)(1Q)1(QP)1 (零律,合取范式)(QP)(同一律,合取范式)*由此例可以看出,公式的合取范式并不惟一。由此例可以看出,公式的合取范式并不惟一。14二、析取范式与合取范式求析取范式 (PQ)P (PQ)P)(PQ)P)(消去)(PQ)P)(PQ)P)(内移)P(PQP)(吸收律,析取范式)P(PPQ)(交换律)P(PQ)(幂等律,析取范式)*由此例可以看出,命题公式的析取范式也不惟一。由此例可以看出,命题公式的析取范式也不惟一。15三、主析取范式上述范式不唯一,下面追求一种更严格的范式-主范式主范式,它是存在且唯一的。定义定义1-7.4
10、n n个命题变元的合取式,称作布布尔合取、小项或极小项尔合取、小项或极小项。其中每个变元与它的否定不能同时存在,但两者必须出现且仅出现一次。如:P,Q的构成的极小项为:PQ,PQ,PQ,PQ 练习:写出三个命题变元练习:写出三个命题变元P、Q、R构成的极小项。构成的极小项。16三、主析取范式由于每个命题变项在极小项中以原形或否定式形式出现且仅出现一次,因而n个命题变项共可产生2n个不同的极小项。其中没有两个极小项是相等价的,每个极小项都有且仅有一个成真指派每个极小项都有且仅有一个成真指派。以成真指派所对应的二进制数,就可将所对应极小项记作mi,(其中i为相应的二进制符号串)。17三、主析取范式
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学-1-7 对偶与范式 离散数学 对偶 范式
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内