离散数学-1-7对偶与范式.ppt
《离散数学-1-7对偶与范式.ppt》由会员分享,可在线阅读,更多相关《离散数学-1-7对偶与范式.ppt(39页珍藏版)》请在三一办公上搜索。
1、1,第一章 命题逻辑,1-7 对偶与范式,2,尽管命题公式的最小联结词组可为,但实际上一般出于方便的目的,命题公式常常包含,。从第15页的表1-4.8的命题定律中可以看出,很多常用等价式是成对出现的,只要将其中的“”和“”分别换成“”和“”,就可以由一个得到另一个。例如,将命题定律(PQ)RP(QR)中的“”换成“”就得到了命题定律(PQ)RP(QR)。这些成对出现的等价式反映了等价的对偶性。我们将这样的公式称作具有对偶规律。本节将先介绍对偶式和对偶原理。,3,一、对偶式与对偶原理,定义1-7.1 在给定的命题公式A中,将联结词、分别换成、,若有特殊变元F和T亦相互对代,所得的公式称为公式A的
2、对偶式,记为A*。*设A*是A的对偶式,将A*中的,F,T分别换成,T,F,就会得到A。即A是A*的对偶式,(A*)*A。所以说A*和A互为对偶式。例题1 写出下列表达式的对偶式1.(PQ)R2.(P Q)T3.(PQ)(P(Q S),4,一、对偶式与对偶原理,例题2 求PQ和PQ的对偶式。解:PQ(PQ)(PQ)的对偶式是(PQ)PQ 故PQ的对偶式是PQ;同样的方法可以证明PQ的对偶式是PQ。注意:根据例题2,对偶式概念可以推广为:在仅含有联结词,的命题公式中,将联结词,F,T分别换成,T,F,就得到了它的对偶式。,5,一、对偶式与对偶原理,*关于对偶式有以下两个结论。定理1-7.1 设A
3、*是A的对偶式,P1,P2,Pn是出现在A和A*中的原子变元,则 A(P1,P2,Pn)A*(P1,P2,Pn)A(P1,P2,Pn)A*(P1,P2,Pn)证明见P30:由德摩根律层层置换,即可层层推出。,6,一、对偶式与对偶原理,例:设命题公式A(P,Q,R)(PQ)R,试用此公式验证定理的有效性。证明:验证 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,Q,R)A*(P,Q,R)A(P,Q,R)(PQ)R(PQ)R)A*
4、(P,Q,R),7,一、对偶式与对偶原理,定理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叫做对偶原理。对偶原理是数理逻辑中最基本的规律之一。,8,一、对偶式与对偶原理,
5、例题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)使用真值表和对偶原理可以简化或推证一些命题公式。,9,一、对偶式与对偶原理,例:证明重言式的对偶式是矛盾式,矛盾式的对偶式是重言式。证明:设A是重言式,即AT,因为T的对偶式是F,由对偶原理知A*F。所以A*是矛盾式;设A是矛盾式,即A F,而F的对偶式是T,所以A*T。所以A*是重言式。,10,二、析取范式与合取范式
6、,每种数字标准形都能提供很多信息,如代数式的因式分解可判断代数式的根情况。逻辑公式在等值演算下也有标准形-范式,范式有两种:析取范式和合取范式。同一命题公式可以有各种相互等价的表达形式,范式可以实现命题公式的规范化,11,二、析取范式与合取范式,定义(补充)仅有有限个命题变元或其否定构成的合(析)取式称作简单合(析)取式。如:P,Q等为一个文字(一个命题变元或它的否定称为文字)构成的简单合取式,PP,PQ等为2个文字构成的简单合取,PQR,PPQ等为3个文字构成的简单合取式P,Q等为一个文字(一个变元或变元的否定)的简单析趋式,PP,PQ等为2个变元(或变元的否定)简单析取式,PQR,PQR等
7、为3个文字构成的简单析取式。,12,二、析取范式与合取范式,定义1-7.2 一个命题公式称为合取范式,当且仅当它具有形式:A1A2An(n 1)其中A1,A2,An 都是简单析取式。如:(PQR)(PQ)Q定义1-7.2 一个命题公式称为析取范式,当且仅当它具有形式:A1A2 An(n 1)其中A1,A2,An 都是简单合取式。如:P(PQ)(PQR),13,二、析取范式与合取范式,任何命题公式都可以化成与其等价的析取范式或合取范式。求析取范式和合取范式的步骤如下:消去联结词“”和“”,化归成、P Q P Q P Q(P Q)(P Q)(P Q)(Q P)(P Q)(Q P)(2)利用双重否定
8、律消去否定联结词“”或利用德摩根律将否定联结词“”移到各命题变元前(内移)利用分配律、结合律将公式归约为合取范式或析取范式。P(Q R)?,14,二、析取范式与合取范式,例:求命题公式(PQ)P的合取范式和析取范式。解:求合取范式(PQ)P(PQ)P)(P(PQ)(消去)(PQ)P)(P(PQ)(消去)(PQ)P)(P(PQ)(内移)(PP)(QP)(PPQ)(分配律,合取范式)1(QP)(1Q)1(QP)1(零律,合取范式)(QP)(同一律,合取范式)*由此例可以看出,公式的合取范式并不惟一。,15,二、析取范式与合取范式,求析取范式(PQ)P(PQ)P)(PQ)P)(消去)(PQ)P)(P
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 对偶 范式

链接地址:https://www.31ppt.com/p-6595589.html