离散数学-1-7 对偶与范式.ppt

《离散数学-1-7 对偶与范式.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章命题逻辑1-7对偶与范式陶轻僳猎狞跳嘶般扛搓倪屠赊镁恕陌颊拆灵恶柬订操箍难喧菇讥懈播但倚离散数学-1-7对偶与范式离散数学-1-7对偶与范式1尽管命题公式的最小联结词组可为¬，∧，¬，∨，↑，↓，但实际上一般出于方便的目的，命题公式常常包含¬，∧，∨。从第15页的表1-4.8的命题定律中可以看出，很多常用等价式是成对出现的，只要将其中的“∧”和“∨”分别换成“∨”和“∧”，就可以由一个得到另一个。例如，将命题定律(P∨Q)∨RP∨(Q∨R)中的“∨”换成“∧”就得到了命题定律(P∧Q)∧RP∧(Q∧

2、R)。这些成对出现的等价式反映了等价的对偶性。我们将这样的公式称作具有对偶规律。本节将先介绍对偶式和对偶原理。迷痊赴卉彻骡倪海腊斜冈浴梗北态檀州纫转戳贡引役暖驻升坚槛少颖氮整离散数学-1-7对偶与范式离散数学-1-7对偶与范式2一、对偶式与对偶原理定义1-7.1在给定的命题公式A中，将联结词∨、∧分别换成∧、∨，若有特殊变元F和T亦相互对代，所得的公式称为公式A的对偶式，记为A*。*设A*是A的对偶式，将A*中的∨，∧，F，T分别换成∧，∨，T，F，就会得到A。即A是A*的对偶式，(A*)*A。所以说A*和A互为对偶式。例题1

3、写出下列表达式的对偶式1.（P∨Q）∧R2.（P∧Q）∨T3.（P∨Q）∧（P∨（Q∧S））鸥万叉本碧眨所钝皿粪面院结优郭腑辊临余掣捉诊突贯粮斯愿蚂酵琶艳倡离散数学-1-7对偶与范式离散数学-1-7对偶与范式3一、对偶式与对偶原理例题2求P↑Q和P↓Q的对偶式。解：P↑Q¬(P∧Q)¬(P∧Q)的对偶式是¬(P∨Q)P↓Q故P↑Q的对偶式是P↓Q；同样的方法可以证明P↓Q的对偶式是P↑Q。注意：根据例题2，对偶式概念可以推广为：在仅含有联结词¬，∧，∨，↑，↓的命题公式中，将联结词∨，∧，↑，↓，F，T分别换成∧，∨，

4、↓，↑，T，F，就得到了它的对偶式。红详恼皖哮吮效摩链拯胡羹淋呵靛懒诡区锰肤鸟谬墙昂仗攒酞医请襟豢衰离散数学-1-7对偶与范式离散数学-1-7对偶与范式4一、对偶式与对偶原理*关于对偶式有以下两个结论。定理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、学-1-7对偶与范式离散数学-1-7对偶与范式5一、对偶式与对偶原理例：设命题公式A(P,Q,R)(P∨Q)∧R，试用此公式验证定理1.7.1的有效性。证明：⑴验证¬A(P,Q,R)A*(¬P,¬Q,¬R)A(P,Q,R)(P∨Q)∧R¬A(P,Q,R)¬((P∨Q)∧R)(¬P∧¬Q)∨¬RA*(P,Q,R)(P∧Q)∨RA*(¬P,¬Q,¬R)(¬P∧¬Q)∨¬R所以，¬A(P,Q,R)A*(¬P,¬Q,¬R)⑵验证A(¬P,¬Q,¬R)¬A*(P,Q,R)A(¬P,¬Q,¬R)(¬P∨¬Q)∧¬R¬(

6、(P∧Q)∨R)¬A*(P,Q,R)禄弗伪呜斧悟符醚曼紧步疾锋耪弊处搀该龟瘸罗崇改奇纪位狞十症尧沙欺离散数学-1-7对偶与范式离散数学-1-7对偶与范式6一、对偶式与对偶原理定理1-7.2设P1，P2，…，Pn是出现在公式A和B中的所有原子变元，如果AB，则A*B*。证明：因为AB,所以A(P1，P2，…，Pn)↔B(P1，P2，…，Pn)是重言式根据定理1-5.2(P19)，在上述重言式中用¬Pi置换Pi，i＝1,…,n，所得的公式仍为重言式，即A(¬P1，¬P2，…，¬Pn)↔B(¬P1，¬P2，…，¬Pn)是重言式

7、。所以A(¬P1，¬P2，…，¬Pn)B(¬P1，¬P2，…，¬Pn)由定理1-7.1¬A*(P1，P2，…，Pn)¬B*(P1，P2，…，Pn)即¬A*¬B*因此A*B**定理1.7.2叫做对偶原理。对偶原理是数理逻辑中最基本的规律之一。颁霞维亨井疗缸猪冯拐杨农甫蓝再乒赐托枪妆辅彰殴漳宝佯帧媳枫斥胎午离散数学-1-7对偶与范式离散数学-1-7对偶与范式7一、对偶式与对偶原理例题4:如果A(P,Q,R)是P↑(Q∧¬(R↓P))，求它的对偶式A*(P,Q,R)。并求A及A*的等价，但仅包含联结词“∧”、“∨”及“¬”的公

8、式。解：因A(P,Q,R)是P↑(Q∧¬(R↓P))所以A*是P↓(Q∨¬(R↑P))而P↑(Q∧¬(R↓P))¬(P∧(Q∧(R∨P))故P↓(Q∨¬(R↑P))¬(P∨(Q∨(R∧P))使用真值表和对偶原理可以简化或推证一些命题公式。潜绘淹棍笑炬员批搐否