离散数学17对偶与范式ppt课件

1、第一章 命题逻辑1-7 对偶与范式尽管命题公式的最小联结词组可为，但实际上一般出于方便的目的，命题公式常常包含， 。从第15页的表1-4.8的命题定律中可以看出，很多常用等价式是成对出现的，只要将其中的“”和“”分别换成“”和“”，就可以由一个得到另一个。例如，将命题定律(PQ)RP(QR)中的“”换成“”就得到了命题定律(PQ)RP(QR)。这些成对出现的等价式反映了等价的对偶性。我们将这样的公式称作具有对偶规律。本节将先介绍对偶式和对偶原理。一、对偶式与对偶原理 定义1-7.1 在给定的命题公式A中，将联结词、分别换成、 ，若有特殊变元F和T亦相互对代，所得的公式称为公式A的对偶式，记为A

2、*。 *设A*是A的对偶式，将A*中的，F，T分别换成，T，F，就会得到A。即A是A*的对偶式，(A*)*A。所以说A*和A互为对偶式。 例题1 写出下列表达式的对偶式 1.（ PQ）R 2. （ P Q）T 3. （ PQ）（ P（Q S） 一、对偶式与对偶原理 例题2 求PQ和PQ的对偶式。 解： PQ(PQ) (PQ)的对偶式是(PQ)PQ 故PQ的对偶式是PQ；同样的方法可以证明PQ的对偶式是PQ。 留意：根据例题2，对偶式概念可以推广为：在仅含有联结词，的命题公式中，将联结词，F，T分别换成 ，T，F，就得到了它的对偶式。一、对偶式与对偶原理*关于对偶式有以下两个结论。 定理1-7.

3、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：由德摩根律层层置换，即可层层推出。一、对偶式与对偶原理例：设命题公式例：设命题公式A(P,Q,R)A(P,Q,R)(PQ)R(PQ)R，试用此公，试用此公式验证定理式验证定理1.7.11.7.1的有效性。的有效性。 证明：证明：验证验证 A(P,Q,R) A(P,Q,R)A A* *(P, Q, R)(P, Q, R) A(P,Q,R) A(P,Q,R)(PQ)R(PQ)R A(P,Q,R)A(P,Q,R)(P

4、Q)R)(PQ)R)(PQ)R(PQ)R A A* *(P,Q,R)(P,Q,R)(PQ)R(PQ)R A A* *(P, Q, R)(P, Q, R)( PQ)R( PQ)R 所以，所以，A(P,Q,R) A(P,Q,R) A A* *(P,Q,R)(P,Q,R)验证验证 A(P,Q,R) A(P,Q,R)AA* *(P,Q,R)(P,Q,R) A(P,Q,R) A(P,Q,R)(PQ)R(PQ)R (PQ)R)(PQ)R)AA* *(P,Q,R)(P,Q,R)一、对偶式与对偶原理 定理1-7.2 设P1，P2，Pn是出现在公式A和B中的所有原子变元，如果AB，则A*B*。 证明： 由于 A

5、B, 所以 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叫做对偶原理。对偶原理是数理逻辑中最基本的规律之一。 一、对偶式与对偶原理例题例题4:如果如果A(P,Q,R)是是P(Q(R P)，求它，求它的对偶式的对偶式A*(P,Q,R)。并求。并求A及及A*的等价，但

6、仅的等价，但仅包含联结词包含联结词“”、“”及及“”的公式。的公式。解：解： 因因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)使用真值表和对偶原理可以简化或推证一些命题使用真值表和对偶原理可以简化或推证一些命题公式。公式。一、对偶式与对偶原理例：证明重言式的对偶式是矛盾式，矛盾例：证明重言式的对偶式是矛盾式，矛盾式的对偶式是重言式。式的对偶式是重言式。 证明：设证明：设A是重言式，即是重言式，即AT，因为，因为T的对的对偶式是偶式是F，由对偶原理知，由对偶原理知A*F。所以。所以A

7、* 是矛盾式；是矛盾式； 设设A是矛盾式，即是矛盾式，即A F ，而，而F的的对偶式是对偶式是T ，所以，所以A* T 。所以。所以A*是重言是重言式。式。二、析取范式与合取范式每种数字标准形都能提供很多信息，如代数式的因式分解可判断代数式的根情况。逻辑公式在等值演算下也有标准形-范式，范式有两种：析取范式和合取范式。同一命题公式可以有各种相互等价的表达形式，范式可以实现命题公式的规范化 二、析取范式与合取范式定义补充仅有有限个命题变元或其否定义补充仅有有限个命题变元或其否定构成的合定构成的合( (析析) )取式称作简单合取式称作简单合( (析析) )取式。取式。 如：如： P,QP,Q等为一

8、个文字等为一个文字( (一个命题变元或它的一个命题变元或它的否定称为文字否定称为文字) )构成的简单合取式，构成的简单合取式，PPPP，PQPQ等为等为2 2个文字构成的简单合取，个文字构成的简单合取，PQR,PPQPQR,PPQ等为等为3 3个文字构成的个文字构成的简单合取式简单合取式P,QP,Q等为一个文字一个变元或变元的否等为一个文字一个变元或变元的否定的简单析趋式，定的简单析趋式，PPPP，PQPQ等为等为2 2个变元或变元的否定简单析取式，个变元或变元的否定简单析取式，PQR,PQRPQR,PQR等为等为3 3个文字构成个文字构成的简单析取式。的简单析取式。二、析取范式与合取范式定义

9、定义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)二、析取范式与合取范式 任何命题公式都可以化成与其等价的析取范式或合取范式。求析取范式和合取范式的步骤如下： 消去联结词“”和“”，化归成、

10、P Q P Q P Q (P Q) (P Q) (P Q) (Q P)(P Q) ( Q P) (2)利用双重否定律消去否定联结词“”或利用德摩根律将否定联结词“”移到各命题变元前(内移) 利用分配律、结合律将公式归约为合取范式或析取范式。 P (Q R) ?二、析取范式与合取范式例：求命题公式(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) (同一律，合取范式

11、) *由此例可以看出，公式的合取范式并不惟一。二、析取范式与合取范式求析取范式 (PQ)P (PQ)P)(PQ)P) (消去) (PQ)P)(PQ)P) (内移) P(PQP) (吸收律，析取范式) P(PPQ) (交换律) P(PQ) (幂等律，析取范式) *由此例可以看出，命题公式的析取范式也不惟一。三、主析取范式上述范式不唯一，下面追求一种更严格的范式-主范式，它是存在且唯一的。 定义1-7.4 n个命题变元的合取式，称作布尔合取、小项或极小项。其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。 如： P，Q的构成的极小项为： PQ，PQ，PQ，PQ 练习：写出三个命题变元

12、P、Q、R构成的极小项。三、主析取范式由于每个命题变项在极小项中以原形或否定式形式出现且仅出现一次，因而n个命题变项共可产生2n个不同的极小项。其中没有两个极小项是相等价的，每个极小项都有且仅有一个成真指派。以成真指派所对应的二进制数，就可将所对应极小项记作mi,（其中i为相应的二进制符号串）。三、主析取范式两个命题变元的真值表、极小项、成真赋值和符号标记如下：真值表 PQPQPQPQPQ000001010010100100111000两个命题变元的极小项两个命题变元的极小项极小项成真赋值成真赋值记作PQ00m00PQ01m01PQ10m10PQ11m11三、主析取范式*可以看出，极小项与成真

13、赋值的对应关系为：变元对应1，而变元的否定对应0。三个命题变元的极小项三个命题变元的极小项极小项成真赋值记作PQR000m000PQR001m001PQR010m010PQR011m011PQR100m100PQR101m101PQR110m110PQR111m111三、主析取范式极小项有如下几个性质：（1每一个极小项当其真值指派与编码相同时，其真值为1，其它2n-1指派情况下均为0。（2任意两个不同极小项的合取式永假。 例如： m001m100 (PQR)(PQR) PQRPQR0（3全体小项的析取式永为真。记为：Tmmmmnnii1212010三、主析取范式定义定义1-7.5 对于给定的命

14、题公式，如果有对于给定的命题公式，如果有一个它的等价公式，仅由极小项的析取所一个它的等价公式，仅由极小项的析取所组成，称该公式为原公式的主析取范式。组成，称该公式为原公式的主析取范式。定理定理1-7.3 在真值表中，一个公式的真值在真值表中，一个公式的真值为为T 的指派所对应的极小项的析取，即为的指派所对应的极小项的析取，即为此公式的主析取范式。此公式的主析取范式。定理定理1-7.3的证明的证明 P34三、主析取范式由定理1-7.3可知通过真值表求给定公式的主析取范式的步骤如下：（1构造命题公式的真值表。 （2找出公式的成真赋值对应的极小项。（3这些极小项的析取就是此公式的主析取范式。例 用真

15、值表法，求(PQ)R的主析取范式。三、主析取范式解： 1.(PQ)R的真值表如下：2.公式的成真赋值对应的极小项为：PQR(成真赋值为001)、 PQR(成真赋值为011)、 PQR (成真赋值为100)、 PQR(成真赋值为101) 、PQR (成真赋值为111)PQRPQ(PQ)R0001000111010100111110001101011101011111三、主析取范式3. (PQ)R的主析取范式为： (PQR)(PQR)(PQR) (PQR)(PQR) m111m101m100m011m001 m7m5m4m3m1*真值表成真指派中对变元的指派为0，对应的极小项中出现该命题变元的否定

16、，若指派1则对应变元本身。三、主析取范式除了用真值表方法外，也可利用等值演算法求得给定命题公式的主析取范式，即用基本等价公式推出。例题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) PPQ P(QQ) P(QQ)(PP)Q (PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ) m0m1m2m3 （永真） 三、主析取范式 用等值演算法

17、求主析取范式的步骤如下： 化归为析取范式。 除去析取范式中所有永假的析取项。 在析取式中，将重复出现的合取项和相同变 元合并。 对合取项补入没有出现的命题变元，即添加(PP)，再用分配律展开，最后合并相同的极小项。四、主合取范式与主析取范式类似的是主合取范式与主析取范式类似的是主合取范式定义定义1-7.6 n个命题变元的析取式，称作布个命题变元的析取式，称作布尔析取、大项或极大项。其中每个变元与尔析取、大项或极大项。其中每个变元与它的否定不能同时存在，但两者必须出现它的否定不能同时存在，但两者必须出现且仅出现一次。且仅出现一次。 如：如：P，Q构成的极大项为：构成的极大项为： PQ，PQ，PQ

18、，PQ 练习：写出三个命题变元练习：写出三个命题变元P、Q、R构成的构成的极大项。极大项。四、主合取范式与极小项类似地，n个命题变项共可产生2n个极大项，每个极大项只有一个成假赋值，将其对应的二进制符号串i做极大项的角标，记作Mi （其中i为相应的二进制符号串）。 四、主合取范式两个命题变元的极大项、成假赋值和符号标记如下：两个命题变元的极大项、成假赋值和符号标记如下：两个命题变元的极大项两个命题变元的极大项极大项成假赋值称号PQ00M00PQ01M01PQ10M10PQ11M11四、主合取范式三个命题变元的极大项、成假赋值和符号标记如下：三个命题变元的极大项、成假赋值和符号标记如下：*可以看

19、出，极大项与成假赋值的对应关系为：变元对应可以看出，极大项与成假赋值的对应关系为：变元对应0，而变元的，而变元的否定对应否定对应1。三个命题变元的极大项三个命题变元的极大项极大项成假赋值称号PQR000M000PQR001M001PQR010M010PQR011M011PQR100M100 PQR101M101PQR110M110PQR111M111四、主合取范式极大项有如下几个性质：（1每一个极大项当其真值指派与编码相同时，其真值为0，其它2n-1指派情况下均为1。（2任意两个不同的极大项的析取式为永真式。 （3全体极大项的合取式为永假式。记为：120niiMM0M1 0 四、主合取范式定义

20、定义1-7.7 对于给定的命题公式，如果有对于给定的命题公式，如果有一个它的等价公式，仅由极大项的合取组一个它的等价公式，仅由极大项的合取组成，则该等价式称为原公式的主合取范式。成，则该等价式称为原公式的主合取范式。定理定理1-7.4 在真值表中，一个公式的真值在真值表中，一个公式的真值为为F 的指派所对应的极大项的合取，即为的指派所对应的极大项的合取，即为此公式的主合取范式。此公式的主合取范式。四、主合取范式由定理1-7.4可知通过真值表求给定公式的主析取范式的步骤如下：（1构造命题公式的真值表。 （2找出公式的成假赋值对应的极大项。（3这些极大项的合取就是此公式的主合取范式。例 用真值表法，求(PQ)R的主合取范式四、主合取范式解： 1.(P