2014级离散第1章离散数学

1、离散数学Discrete Mathematics第一章 命题逻辑第5讲17 对偶与范式 要求：掌握对偶与范式，会求命题公式的主析取范式和主合取范式。 重点和难点：求命题公式的主析取范式和主合取范式。一、对偶式1. 复习命题定律。见15页表1-4.8对合律P P1幂等律PP P，PP P2结合律(PQ）R P（QR）(PQ）R P（QR）3交换律PQ QPPQ QP4分配律P（QR） （PQ）（PR）P（QR） （PQ）（PR）5吸收律P（PQ） PP（PQ） P6德摩根律(PQ) PQ(PQ) PQ7同一律PF P，PT P8零律PT T，PF F9否定律PP T，PP F10 我们从表1-4

2、.8可以看到命题定律除对合律外都是成对出现的，其不同的只是和互换。我们把这样的公式称作具有对偶规律。 定义1-7.1 在给定的命题公式中，将联结词换成，将换成 ，若有特殊变元F和T亦相互取代，所得公式A*称作A的对偶式。 显然A也是A*的对偶式。2. 对偶式的定义例题1 写出下列表达式的对偶式。(P Q) R(P Q) F(P Q) (P (Q S)（a）(PQ) R（b）(PQ) T（c）(P Q) (P (Q S)AA*定理1-7.1 设A和A*是对偶式，P1， P2 ，Pn是出现在A和A*中的原子变元，则A（ P1， P2 ，Pn ） A*（ P1， P2 ，Pn ）A（ P1， P2

3、，Pn ） A*（ P1， P2 ，Pn ） 证明 由德摩根定律 (PQ) (P Q)， (P Q) (P Q) 故 A（ P1， P2 ，Pn ） A*（ P1， P2 ，Pn ）同理 A*（ P1， P2 ，Pn ） A（ P1， P2 ，Pn ）例题3 设A*（S，W，R）是 S (W R) ，证明 A*（S， W， R） A（S，W，R）.所以 A*（S， W， R） A（S，W，R）证明 由于A*（S，W，R）是 S (W R) ，则 A*（S， W， R）是 S (W R)，但 A（S，W，R）是 S (W R) ，故 A（S，W，R）是 (S (W R) S (W R)定理1-7

4、.2 设P1， P2 ，Pn是出现在公式A和B中的所有原子变元，如果A B，则A* B*。 证明 因为A B，即 是一个重言式，故也是一个重言式。即由定理1-7.1得因此 A* B*A(p1,p2,L,pn) B(p1,p2,L,pn)A(p1, p2,L, pn) B(p1, p2,L, pn)二、范式的概念1、举例 将命题公式(P Q) R化成仅包含联结词“”、“”、及“”的公式。解 (P Q) R (P Q) R P Q R P ( Q Q) Q ( R R)R ( P P) (P Q) (P Q)(Q R ) (Q R) (R P) (R P) 同一命题公式可以有各种相互等价的表达形式

5、,为了把命题公式规范化,下面讨论命题公式的范式问题。2、合取范式的定义 定义1-7.2 一个命题公式称为合取范式，当且仅当它具有形式： A1 A2 An， （n1） 其中A1，A2，An都是由命题变元或其否定所组成的析取式。 例如(P Q R) (PQ) Q 3、析取范式的定义 定义1-7.3 一个命题公式称为析取范式，当且仅当它具有形式： A1 A2 An， （n1） 其中A1，A2，An都是由命题变元或其否定所组成的合取式。 例如P (P Q )(P Q R)是析取范式。 4、求一个命题公式的合取或析取范式的三个步骤：（1）将公式中的联结词化归成、及。（2）利用德摩根定律将否定符号直接移到

6、各个命题变元之前。（3）利用分配律、结合律将公式归纳为合取范式或析取范式。例题5 求(P ( Q R) S的合取范式。 解 (P ( Q R) S (P (Q R) S P (Q R) S(P S) (Q R) (P S Q ) (P S R) (PQPQ) (P P )(Q P ) (P Q )(Q Q )解 因为有公式 (PQPQ) (P Q) (P Q)A B （AB） （ A B）练习 39页四、主范式一个命题公式的合取范式或析取范式并不是唯一的。例如P(Q R)是一个析取范式，但它亦可以写成 P(Q R) ( PQ) (PR) (P P) (PR) (QP) (QR) 1、小项 为了

7、使任意一个命题公式，化成唯一的等价命题的标准形式，下面给出主范式的有关概念。 定义1-7.4 n个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。 例如，两个命题变元P和Q，其小项为： PQ，PQ，PQ，PQ。 三个命题变元P、Q、R，其小项为： PQR， PQ R ，PQ R ，PQ R ，PQ R ， PQ R ， PQ R ，PQ R 。 n个命题变元共有2n个小项。两个命题变元P和Q及其小项的真值表： P Q PQPQPQPQ T T T F F F T F F T F F F T F F T F F F F F F T从上表可以看

8、到，没有两个小项是等价的，且每个小项都只对应P和Q的一组真值指派，使得该小项的真值为T。三个命题变元P、Q、R及其小项的真值表（真值T和F分别记为1和0）：PQRPQ RPQ R PQ RPQ R000 1 0 0 0001 0 1 0 0010 0 0 1 0011 0 0 0 1100 0 0 0 0101 0 0 0 0110 0 0 0 0111 0 0 0 0PQR PQ R PQ R PQ R PQR000 0 0 0 0001 0 0 0 0010 0 0 0 0011 0 0 0 0100 1 0 0 0101 0 1 0 0110 0 0 1 0111 0 0 0 1 按照三

9、个命题变元P、Q、R及其小项的真值表可以作出一种编码：m000= PQ R m100= PQ Rm001= PQ R m101=PQ Rm010= PQ R m110=PQ Rm011= PQ R m111=PQR2、小项的编码将这种编码方法推广到n个变元，可以使n个变元的小项很快写出来。3、小项的性质 小项有如下几个性质：（1）每一个小项当其真值指派与编码相同时，其真值为T，在其余2n-1种指派情况下均为F。（2）任意两个不同小项的合取式永假。（3）全体小项的析取式永为真，记为： m0m1m2n-1 T定义1-7.5 对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式

10、称作原式的主析取范式。如(PQ )(PQ)的主析取范式为 (PQ ) (PQ)4、主析取范式（1） 真值表法 定理1-7.3 在真值表中,一个公式的真值为T的指派所对应的小项的析取,即为此公式的主析取范式。 证明 设给定公式为A，其真值为T的指派所对应的小项为m1，m2，mk，这些小项的析取式记为B。要证A B，只要证A与B在相应指派下具有相同真值。 首先对A为T的某一指派，其对应的小项为mi，则因为mi为T，而m1，m2，mi-1mi+1，mk均为F，故B为T。 其次，对A为F的某一指派，其对应的小项不包含在B中，即m1，m2，mk均为F，故B为F。 因此A B。5、求一个命题公式的主析取范

11、式的方法例题7 求公式P Q，P Q，和 (P Q ）的主析取范式。解 三公式的真值表如下： 故P Q (P Q )(P Q ) (P Q)PQP QP Q (P Q ）TT T T FTF F T TFT T T TFF T F TP Q (P Q )(P Q ) (P Q) (P Q) (P Q )(P Q ) (P Q)例题8 设一个公式A的真值表如下,求公式A的主析取范式。 P Q R A T T T T T T F F T F T F T F F T F T T F F T F F F F T F F F F T公式A的主析取范式为：A (P Q R ) (P Q R )(P Q R

12、)求一个命题公式的主析取范式的方法 (2) 利用基本等价公式推出例题9 求 (PQ ) (PR) (QR)的主析取范式。 (PQR) (PQR) ) (PR Q ) (PR Q) ) (QR P) (QR P) 解 原式 (PQ ) (PR )(QR ) (R R)(Q Q)(P P) (PQR) (PQR) ) (PQ R ) (P Q R) )例题10 试求P (P Q) ( Q P)的主析取范式。解 P (P Q) ( Q P) P (P Q) ( QP) P (P QP) (Q QP) (化为析取范式) P (Q P) （除去永假项） P (Q Q ) (Q P) （补入变元） (P

13、Q) (P Q ) (P Q)（分配率展开） 由基本等价公式推出一个命题公式的主析取范式的推演步骤如下：（4）对合取项补入没有出现的命题变元，即添加(P P)式,然后,应用分配率展开公式。（3）将析取式中重复出现的合取项和相同的命题变元合并。（2）除去析取范式中所有永假的析取项。（1）化归为析取范式。 对于一个命题公式的主析取范式，如将其命题变元的个数及出现次序固定后，则此公式的主析取范式便是唯一的，因此，给定任两个公式，由主析取范式可以方便地看出两个公式是否等价。 与主析取范式类似的是主合取范式。 定义1-7.5 n个命题变元的析取式，称作布尔析取或大项，其中每个变元与它的否定不能同时存在，

14、但两者必须出现且仅出现一次。 例如，两个命题变元P和Q，其大项为： PQ，PQ，PQ，PQ。 三个命题变元P、Q、R，其大项为： PQR，PQ R ， PQR ， PQ R ，PQR ， PQ R ， PQ R ，PQ R 。 n个命题变元共有2n个大项。6、大项每个大项可用n位二进制予以编码：若n=2M00= PQ ， M01= PQ M10= PQ ， M11=PQ R若n=3M000= PQ R ， M100= PQ RM001= PQ R， M101=PQ RM010= PQ R ， M110=PQ RM011= PQ R， M111=PQR7、大项的编码两个命题变元P和Q及其大项的真

15、值表： P Q PQPQPQPQ T T T T T F T F T T F T F T T F T T F F F T T T从上表可以看到，没有两个大项是等价的，且每个大项都只对应P和Q的一组真值指派，使得该大项的真值为F。三个命题变元P、Q、R及其大项的真值表（真值T和F分别记为1和0）：PQR P Q R P Q R P Q R P Q R000 0 1 1 1001 1 0 1 1010 1 1 0 1011 1 1 1 0100 1 1 1 1101 1 1 1 1110 1 1 1 1111 1 1 1 1PQR P Q R P Q R P Q R P Q R000 1 1 1

16、1001 1 1 1 1010 1 1 1 1011 1 1 1 1100 0 1 1 1101 1 0 1 1110 1 1 0 1111 1 1 1 0（1）每一个大项当其真值指派与编码相同时，其真值为F，在其余2n-1种指派情况下均为T。8、大项的性质（3）全体大项的合取式必为永假，记为： M0M1M2n-1 F（2）任意两个不同大项的析取式为永真。 MiMj T （ij）大项有如下性质：定义1-7.7 对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式的主合取范式。如(PQ )(PQ)的主合取范式为 (PQ ) (PQ)9、主合取范式10、求一个命题公式

17、的主合取范式的方法 （1） 真值表法 定理1-7.4 在真值表中,一个公式的真值为F的指派所对应的大项的合取,即为此公式的主合取范式。 证明与定理1-7.3相同。 例题11 利用真值表技术求(P Q ) (P R )的主合取范式与主析取范式。解 公式(P Q ) (P R )的真值表如下：PQ RP QP R (P Q ) (P R ) T T T T F T T T F T F T T F T F F F T F F F F F F T T F T T F T F F F F F F T F T T F F F F F F主合取范式为： (P Q ) (P R ) (P Q R ) (P Q

18、 R) (P Q R) (P QR)主析取范式为：(P Q ) (P R ) (P Q R ) (P Q R) (P Q R) (P Q R) 由基本等价公式推出一个命题公式的主合取范式的推演步骤如下：（1）化归为合取范式。（2）除去合取范式中所有永真的合取项。（3）合并相同的析取项和相同的变元。（4）对析取项补入没有出现的命题变元，即添加(P P)式，然后，应用分配率展开公式。求一个命题公式的主合取范式的方法 (2) 利用基本等价公式推出例题12 化 (PQ ) (PR) 为主合取范式。 (P Q R) (P Q R)(P Q R)(P Q R) (Q P R) (Q P R)(P R Q)

19、 (P R Q)(Q R P)(Q R P) (Q P (RR)(P R (QQ) (Q R (PP) (Q P)(P R)(Q R) (P P)(Q P)(P R)(Q R) (PQ) P)(PQ) R)解 (PQ ) (PR)11、主析取范式与主合取范式之间的关系： 由于主范式是由小项或大项构成，从小项和大项的定义，可知两者有下列关系： 因此，主析取范式和主合取范式有着“互补”关系，即是由给定公式的主析取范式可以求出其主合取范式。为了使主析取范式和主合取范式表达简洁，今后用表示小项的析取,用表示大项的合取，由这样的约定，例题11可以表达为：(P Q ) (P R ) (P Q R) (P

20、Q R) (P Q R) ( P Q R ) m001m011m110m111= 1，3，6，7 (P Q ) (P R ) (P QR) (P Q R) (P Q R ) (P Q R) M000M010 M100 M101= 0，2，4，5如果命题P的主析取范式为： i1，i2，ik则P的主合取范式为： 0,1,2,i1-1, i1+1, , ik-1, ik+1, ,2n-1五、小结 本节主要内容 对偶式 在给定的命题公式中，将联结词换成，将换成 ，若有特殊变元F和T亦相互取代，所得公式A*称作A的对偶式。 合取范式 一个命题公式称为合取范式，当且仅当它具有形式： A1 A2 An， （

21、n1） 其中A1，A2，An都是由命题变元或其否定所组成的析取式。 析取范式 一个命题公式称为析取范式，当且仅当它具有形式： A1 A2 An， （n1） 其中A1，A2，An都是由命题变元或其否定所组成的合取式。 小项 n个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。 大项 n个命题变元的析取式，称作布尔析取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。 小项性质：（1）每一个小项当其真值指派与编码相同时，其真值为T，在其余2n-1种指派情况下均为F。（2）任意两个不同小项的合取式永为F。（3）全体小项的析取式永为T。 大项性质：（1）每一个大项当其真值指派与编码相同时，其真值为F，在其余2n-1种指派情况下均为T。（2）任意两个不同大项的析取式为永T。（3）全体大项的合取式必为永为F。 主析取范式 对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取范式。 主合取范式 对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式的主合取范式。定理1-7.1 设A和A*是对偶式，P1， P2 ，Pn是出现在A和A*中