离散数学17对偶与范式资料教程.ppt

单击此处编辑母版标题样式单击此处编辑母版副标题样式*1第一章 命题逻辑n1-7 对偶与范式n 尽管命题公式的最小联结词组可为，但实际上一般出于方便的目的，命题公式常常包含， n 从第15页的表1-4.8的命题定律中可以看出，很多常用等价式是成对出现的，只要将其中的“”和“”分别换成“”和“”，就可以由一个得到另一个n 例如，将命题定律(PQ)RP(QR)中的“”换成“”就得到了命题定律(PQ)RP(QR)这些成对出现的等价式反映了等价的对偶性我们将这样的公式称作具有对偶规律n 本节将先介绍对偶式和对偶原理2一、对偶式与对偶原理 定义1-7.1 在给定的命题公式A中，将联结词、分别换成、 ，若有特殊变元F和T亦相互对代，所得的公式称为公式A的对偶式，记为A*设A*是A的对偶式，将A*中的，F，T分别换成，T，F，就会得到A即A是A*的对偶式，(A*)*A所以说A*和A互为对偶式 n例题1 写出下列表达式的对偶式n1.（ PQ）Rn2. （ P Q）Tn3. （ PQ）（ P（Q S） 3一、对偶式与对偶原理*关于对偶式有以下两个结论n 定理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,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叫做对偶原理对偶原理是数理逻辑中最基本的规律之一 7一、对偶式与对偶原理n 例题4:如果A(P,Q,R)是P(Q(R P)，求它的对偶式A*(P,Q,R)。

并求A及A*的等价，但仅包含联结词“”、“”及“”的公式n 解： 因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)n 使用真值表和对偶原理可以简化或推证一些命题公式8一、对偶式与对偶原理n例：证明重言式的对偶式是矛盾式，矛盾式的对偶式是重言式 n 证明：设A是重言式，即AT，因为T的对偶式是F，由对偶原理知A*F所以A* 是矛盾式； 设A是矛盾式，即A F ，而F的对偶式是T ，所以A* T 所以A*是重言式9二、析取范式与合取范式n每种数字标准形都能提供很多信息，如代数式的因式分解可判断代数式的根情况逻辑公式在等值演算下也有标准形-范式，范式有两种：析取范式和合取范式n同一命题公式可以有各种相互等价的表达形式，范式可以实现命题公式的规范化 10二、析取范式与合取范式n定义（补充）仅有有限个命题变元或其否定构成的合(析)取式称作简单合(析)取式 如： nP,Q等为一个文字(一个命题变元或它的否定称为文字)构成的简单合取式，PP，PQ等为2个文字构成的简单合取，PQR,PPQ等为3个文字构成的简单合取式nP,Q等为一个文字（一个变元或变元的否定）的简单析趋式，PP，PQ等为2个变元（或变元的否定）简单析取式，PQR,PQR等为3个文字构成的简单析取式。

11二、析取范式与合取范式n 定义1-7.2 一个命题公式称为合取范式，当且仅当它具有形式： A1A2An (n 1) 其中A1，A2，An 都是简单析取式 如: (PQR)(PQ)Qn 定义1-7.2 一个命题公式称为析取范式，当且仅当它具有形式： A1A2 An (n 1) 其中A1，A2，An 都是简单合取式 如: 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二、析取范式与合取范式n例：求命题公式(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) (同一律，合取范式) *由此例可以看出，公式的合取范式并不惟一。

14二、析取范式与合取范式求析取范式 (PQ)P (PQ)P)(PQ)P) (消去) (PQ)P)(PQ)P) (内移) P(PQP) (吸收律，析取范式) P(PPQ) (交换律) P(PQ) (幂等律，析取范式) *由此例可以看出，命题公式的析取范式也不惟一15三、主析取范式n上述范式不唯一，下面追求一种更严格的范式-主范式，它是存在且唯一的 n定义1-7.4 n个命题变元的合取式，称作布尔合取、小项或极小项其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次 如： P，Q的构成的极小项为： PQ，PQ，PQ，PQ 练习：写出三个命题变元P、Q、R构成的极小项16三、主析取范式n 由于每个命题变项在极小项中以原形或否定式形式出现且仅出现一次，因而n个命题变项共可产生2n个不同的极小项其中没有两个极小项是相等价的，每个极小项都有且仅有一个成真指派以成真指派所对应的二进制数，就可将所对应极小项记作mi,（其中i为相应的二进制符号串）17三、主析取范式n 两个命题变元的真值表、极小项、成真赋值和符号标记如下：真值表 PQPQPQPQPQ000001010010100100111000两个命题变元的极小项极小项成真赋值记作PQ00m00PQ01m01PQ10m10PQ11m1118三、主析取范式n *可以看出，极小项与成真赋值的对应关系为：变元对应1，而变元的否定对应0。

三个命题变元的极小项极小项成真赋值记作PQR000m000PQR001m001PQR010m010PQR011m011PQR100m100PQR101m101PQR110m110PQR111m11119三、主析取范式n极小项有如下几个性质：n（1）每一个极小项当其真值指派与编码相同时，其真值为1，其它2n-1指派情况下均为0n（2）任意两个不同极小项的合取式永假 例如： m001m100 (PQR)(PQR) PQRPQR0n（3）全体小项的析取式永为真记为：20三、主析取范式n定义1-7.5 对于给定的命题公式，如果有一个它的等价公式，仅由极小项的析取所组成，称该公式为原公式的主析取范式n定理1-7.3 在真值表中，一个公式的真值为T 的指派所对应的极小项的析取，即为此公式的主析取范式n定理1-7.3的证明 P3421三、主析取范式n由定理1-7.3可知通过真值表求给定公式的主析取范式的步骤如下：n（1）构造命题公式的真值表 n（2）找出公式的成真赋值对应的极小项n（3）这些极小项的析取就是此公式的主析取范式n例 用真值表法，求(PQ)R的主析取范式22三、主析取范式n解： 1.(PQ)R的真值表如下：2.公式的成真赋值对应的极小项为：PQR(成真赋值为001)、 PQR(成真赋值为011)、 PQR (成真赋值为100)、 PQR(成真赋值为101) 、PQR (成真赋值为111)PQRPQ(PQ)R000100011101010011111000110101110101111123三、主析取范式3. (PQ)R的主析取范式为： (PQR)(PQR)(PQR) (PQR)(PQR) m111m101m100m011m001 m7m5m4m3m1*真值表成真指派中对变元的指派为0，对应的极小项中出现该命题变元的否定，若指派1则对应变元本身。

24三、主析取范式n 除了用真值表方法外，也可利用等值演算法求得给定命题公式的主析取范式，即用基本等价公式推出例题8：用等价演算法求(PQ)(PR)(QR)的主析取范式 解：(PQ)(PR)(QR) (PQ(RR)(PR()(QR(PP) (PQR)(PQR)(PQR)(PQR) (PQR)(PQR) (PQR)(PQR)(PQR)(PQR) m111m110m011m001例：P(PQ)PPQP() P()(PP)Q (PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ) m0m1m2m3 （永真） 25三、主析取范式 用等值演算法求主析取范式的步骤如下： 化归为析取范式 除去析取范式中所有永假的析取项 在析取式中，将重复出现的合取项和相同变 元合并 对合取项补入没有出现的命题变元，即添加(PP)，再用分配律展开，最后合并相同的极小项26四、主合取范式n与主析取范式类似的是主合取范式n定义1-7.6 n个命题变元的析取式，称作布尔析取、大项或极大项其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次 如：P，Q构成的极大项为： PQ，PQ，PQ，PQ n 练习：写出三个命题变元P、Q、R构成的极大项。

27四、主合取范式n 与极小项类似地，n个命题变项共可产生2n个极大项，每个极大项只有一个成假赋值，将其对应的二进制符号串i做极大项的角标，记作Mi （其中i为相应的二进制符号串） 28四、主合取范式n 两个命题变元的极大项、成假赋值和符号标记如下：两个命题变元的极大项极大项成假赋值名称PQ00M00PQ01M01PQ10M10PQ11M1129四、主合取范式n 三个命题变元的极大项、成假赋值和符号标记如下： *可以看出，极大项与成假赋值的对应关系为：变元对应0，而变元的否定对应1三个命题变元的极大项极大项成假赋值名称PQR000M000PQR001M001PQR010M010PQR011M011PQR100M100 PQR101M101PQR110M110PQR111M11130四、主合取范式n极大项有如下几个性质：n（1）每一个极大项当其真值指派与编码相同时，其真值为0，其它2n-1指派情况下均为1n（2）任意两个不同的极大项的析取式为永真式 n（3）全体极大项的合取式为永假式记为：M0M1 0 31四、主合取范式n定义1-7.7 对于给定的命题公式，如果有一个它的等价公式，仅由极大项的合取组成，则该等价式称为原公式的主合取范式。

n定理1-7.4 在真值表中，一个公式的真值为F 的指派所对应的极大项的合取，即为此公式的主合取范式32四、主合取范式n由定理1-7.4可知通过真值表求给定公式的主析取范式的步骤如下：n（1）构造命题公式的真值表 n（2）找出公式的成假赋值对应的极大项n（3）这些极大项的合取就是此公式的主合取范式n例 用真值表法，求(PQ)R的主合取范式33四、主合取范式n解： 1.(PQ)R的真值表如下：2.公式的成假。