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

第一章 命题逻辑1-7 对偶与范式1尽管命题公式的最小联结词组可为，但实际上一般出于方便的目的，命题公式常常包含，。从第15页的表1-4.8的命题定律中可以看出，很多常用等价式是成对出现的，只要将其中的“”和“”分别换成“”和“”，就可以由一个得到另一个。例如，将命题定律(PQ)RP(QR)中的“”换成“”就得到了命题定律(PQ)RP(QR)。这些成对出现的等价式反映了等价的对偶性等价的对偶性。我们将这样的公式称作具有对偶规律对偶规律。本节将先介绍对偶式和对偶原理。2一、对偶式与对偶原理定义1-7.1 在给定的命题公式A中，将联结词、分别换成、，若有特殊变元F和T亦相互对代，所得的公式称为公式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一、对偶式与对偶原理*关于对偶式有以下两个结论。定理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一、对偶式与对偶原理例题例题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，因为T的对偶式是F，由对偶原理知A*F。所以A*是矛盾式；设A是矛盾式，即A F，而F的对偶式是T，所以A*T。所以A*是重言式。9二、析取范式与合取范式每种数字标准形都能提供很多信息，如代数式的因式分解可判断代数式的根情况。逻辑公式在等值演算下也有标准形-范式，范式有两种：析取范式和合取范式。同一命题公式可以有各种相互等价的表达形式，范式可以实现命题公式的规范化 10二、析取范式与合取范式定义（补充）定义（补充）仅有有限个命题变元或其否定构成的合(析)取式称作简单合简单合(析析)取式取式。如：nP,Q等为一个文字一个文字(一个命题变元或它的否定称为文字一个命题变元或它的否定称为文字)构成的简单合取式，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 都是简单合取式简单合取式。如: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)(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 n n个命题变元的合取式，称作布布尔合取、小项或极小项尔合取、小项或极小项。其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。如：P，Q的构成的极小项为：PQ，PQ，PQ，PQ 练习：写出三个命题变元练习：写出三个命题变元P、Q、R构成的极小项。构成的极小项。16三、主析取范式由于每个命题变项在极小项中以原形或否定式形式出现且仅出现一次，因而n个命题变项共可产生2n个不同的极小项。其中没有两个极小项是相等价的，每个极小项都有且仅有一个成真指派每个极小项都有且仅有一个成真指派。以成真指派所对应的二进制数，就可将所对应极小项记作mi,（其中i为相应的二进制符号串）。17三、主析取范式两个命题变元的真值表、极小项、成真赋值和符号标记如下：真值表 PQPQPQPQPQ000001010010100100111000两个命题变元的极小项两个命题变元的极小项极小项极小项成真赋值成真赋值记作记作PQ00m00PQ01m01PQ10m10PQ11m1118三、主析取范式*可以看出，极小项与成真赋值的对应关系为：变元对应可以看出，极小项与成真赋值的对应关系为：变元对应1，而变元的否定对应，而变元的否定对应0。三个命题变元的极小项三个命题变元的极小项极小项极小项成真赋值成真赋值记作记作PQR000m000PQR001m001PQR010m010PQR011m011PQR100m100PQR101m101PQR110m110PQR111m11119三、主析取范式极小项有如下几个性质：n（1）每一个极小项当其真值指派与编码相同时，其真值为1，其它2n-1指派情况下均为0。n（2）任意两个不同极小项的合取式永假。例如：m001m100(PQR)(PQR)PQRPQR0n（3）全体小项的析取式永为真。记为：20三、主析取范式定义定义1-7.5 对于给定的命题公式，如果有一个它的等价公式，仅由极小项的析取所组成，称该公式为原公式的主析取范式主析取范式。定理定理1-7.3 在真值表中，一个公式的真值为T 的指派所对应的极小项的析取，即为此公式的主析取范式。定理1-7.3的证明 P3421三、主析取范式由定理1-7.3可知通过真值表求给定公式的主析取范式的步骤如下：n（1）构造命题公式的真值表。n（2）找出公式的成真赋值对应的极小项。n（3）这些极小项的析取就是此公式的主析取范式。例 用真值表法，求(PQ)R的主析取范式。22三、主析取范式解：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三、主析取范式除了用真值表方法外，也可利用等值演算法求得给定命题公式的主析取范式，即用基本等价公式推出。例题例题8 8：用等价演算法求(PQ)(PR)(QR)的主析取范式。解：(PQ)(PR)(QR)(PQ(RR)(PR(QQ)(QR(PP)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)m111m110m011m001例：例：P(PQ)PPQP(QQ)P(QQ)(PP)Q(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)m0m1m2m3（永真）25三、主析取范式用等值演算法求主析取范式的步骤如下：化归为析取范式。除去析取范式中所有永假的析取项。在析取式中，将重复出现的合取项和相同变 元合并。对合取项补入没有出现的命题变元，即添加(PP)，再用分配律展开，最后合并相同的极小项。26四、主合取范式与主析取范式类似的是主合取范式与主析取范式类似的是主合取范式定义定义1-7.6 n n个命题变元的析取式，称作布布尔析取、大项或极大项尔析取、大项或极大项。其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。如：P，Q构成的极大项为：PQ，PQ，PQ，PQ 练习：写出三个命题变元练习：写出三个命题变元P P、Q Q、R R构成的极大项。构成的极大项。27四、主合取范式与极小项类似地，n个命题变项共可产生2n个极大项，每个极大项只有一个成假赋值一个成假赋值，将其对应的二进制符号串i做极大项的角标，记作Mi（其中i为相应的二进制符号串）。28四、主合取范式两个命题变元的极大项、成假赋值两个命题变元的极大项、成假赋值和符号标记如下：和符号标记如下：两个命题变元的极大项两个命题变元的极大项极大项成假赋值名称PQ00M00PQ01M01PQ10M10PQ11M1129四、主合取范式三个命题变元的极大项、成假赋值三个命题变元的极大项、成假赋值和符号标记如下和符号标记如下：*可以看出，极大项与成假赋值的对应关系为：变元对应0，而变元的否定对应1。三个命题变元的极大项三个命题变元的极大项极大项成假赋值名称PQR000M000PQR001M001PQR010M010PQR011M011PQR100M100 PQR101M101PQR110M110PQR111M11130四、主合取范式极大项有如下几个性质：n（1）每一个极大项当其真值指派与编码相同时，其真值为0，其它2n-1指派情况下均为1。n（2）任意两个不同的极大项的析取式为永真式。n（3）全体极大项的合取式为永假式。记为：M0M1 0 31四、主合取范式定义定义1-7.7 对于给定的命题公式，如果有一个它的等价公式，仅由极大项的合取组成，则该等价式称为原公式的主合取范式主合取范式。定理定理1-7.4 在真值表中，一个公式的真值为F 的指派所对应的极大项的合取，即为此公式的主合取范式。32四、主合取范式由定理1-7.4可知通过真值表求给定公式的主析取范式的步骤如下：n（1）构造命题公式的真值表。n（2）找出公式的成假赋值对应的极大项。n（3）这些极大项的合取就是此公式的主合取范式。例 用真值表法，求(PQ)R的主合取范式33四、主合取范式解：1.(PQ)R的真值表如下：2.公式的成假赋值对应的极大项为：PQR(成假赋值为000)、PQR(成假赋值为010)、PQR(成假赋值为110)3.主合取范式为：(PQR)(PQR)(PQR)M000M010M110M0M2M6PQRPQ(PQ)R000100011101010011111000110101110101111134四、主合取范式与求主析取范式相似，除了用真值表方法外，也可利用等值演算法求得给定命题公式的主合取范式。其演算步骤如下：化归为合取范式。除去所有永真的合取项。在合取式中合并重复出现的析取项和相同的变元。对析取项补入没有出现的命题变元。即增加(PP)，然后，应用分配律展开公式，最后合并相同的极大项。35五、主析取范式与主合取范式的关系我们今后可用表示极小项的析取，i,j,k 即表示mimjmk可用表示大项的合取，i,j,k即表示MiMjMk例如：n(pqr)(pqr)(pqr)(pqr)(pqr)m111m101m100m011m0011，3，4，5，7n(pqr)(pqr)(pqr)M000M010M110 0，2，636五、主析取范式与主合取范式的关系可以证明如果命题公式P的主析取范式为 i1,i2,ik，则P的主合取范式为：0,1,2,i1-1,i1+1,ik-1,ik+1,2n-1例：(PQ)Q 1，3，4，5，70，2，6 37内容小结对偶式与对偶原理析取范式与合取范式主析取范式主合取范式主析取范式与主合取范式的关系38课后作业P39（4）a,c,e,f(可用真值表法或等值演算法)39