离散数学1-7.ppt

1、离散数学Discrete Mathematics,第一章 命题逻辑第5讲17 对偶与范式,要求：掌握对偶与范式，会求命题公式的主析取范式和主合取范式。 重点和难点：求命题公式的主析取范式和主合取范式。,一、对偶式 1. 复习命题定律。见15页表1-4.8,我们从表1-4.8可以看到命题定律除对合律外都是成对出现的，其不同的只是和互换。我们把这样的公式称作具有对偶规律。 定义1-7.1 在给定的命题公式中，将联结词换成， 将换成 ，若有特殊变元F和T亦相互取代，所 得公式A*称作A的对偶式。 显然A也是A*的对偶式。,2. 对偶式的定义,例题1 写出下列表达式的对偶式。,(P Q) R (P Q

2、) F (P Q) (P (Q S),（a）(PQ) R （b）(PQ) T （c）(P Q) (P (Q S),A,A*,定理1-7.1 p30 设A和A*是对偶式，P1， P2 ，Pn是出现在A和A*中的原子变元，则 A（ P1， P2 ，Pn ） A*（ P1， P2 ，Pn ） A（ P1， P2 ，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 ）,例题3p30 设A*（S，W，R）是 S

3、 (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.2p30 设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,

4、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),同一命题公式可以有各种相互等价的表达形式,为了把命题公式规范化,下面讨论命题公式的范式问题。,2、合取范式的定义 定义1-7.2 p31 一个命题公式称为合取范式， 当且仅当它具有形式： A1 A2 An， （n1） 其中A1，A2，An都是由命题变元或其否定所组成的 析

5、取式。 Ai . 例如(P Q R) (PQ) Q,3、析取范式的定义 定义1-7.3p31 一个命题公式称为析取范式， 当且仅当它具有形式： A1 A2 An， （n1） 其中A1，A2，An都是由命题变元或其否定所组成的 合取式。 Ai 例如 P (P Q )(P Q R)是析取范式。,4、求一个命题公式的合取或析取范式的三个步骤：,（1）将公式中的联结词化归成、及。,（2）利用德摩根定律将否定符号直接移到各个命题变 元之前。,（3）利用分配律、结合律将公式归纳为合取范式或析 取范式。,例题5 p32 求(P ( Q R) S的合取范式。,解 (P ( Q R) S, (P (Q R) S

6、, P (Q R) S,(P S) (Q R),(P S Q ) (P S R), (P P )(Q P ) (P Q )(Q Q ) F F (Q P ) (PQ )F (Q P ) (P 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、小项 为了使任意一个命题公式，化成唯一的等价命题 的标准形式，下面给出主范式的有关概念。 定义1-7.4 (

7、 P32)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及其小项的真值表：P33,从上表可以看到，没有两个小项是等价的，且每个小项都只对应P和Q的一组真值指派，使得该小项的真值为T。,三个命题变元P、Q、R及其小项的真值表（真值T和F分别记为1和0）：,按照三个命题变元P、Q、

8、R及其小项的真值表可以作出一种编码： m000= PQ R=m0 ，m100= PQ R=m4 m001= PQ R =m1， m101=PQ R =m5 m010= PQ R =m2 ， m110=PQ R =m6 m011= PQ R =m3， m111=PQR =m7,2、小项的编码,将这种编码方法推广到n个变元，可以使n个变元的小项很快写出来。,3、小项的性质P34,小项有如下几个性质： （1）每一个小项当其真值指派与编码相同时，其真 值为T，在其余2n-1种指派情况下均为F。 （2）任意两个不同小项的合取式永假。 （3）全体小项的析取式永为真，记为： m0m1m2n-1 T,定义1-

9、7.5 对于给定的命题公式，如果有一个等价公式，它仅由小 项的析取所组成，则该等价式称作原式的主析取范式。 如(PQ )(PQ)的主析取范式为 (PQ ) (PQ) (PQ )(PQ) (PQ )(PQ) (PP)(PQ ) (Q P) (Q Q) (PQ ) (PQ),4、主析取范式P34,（1） 真值表法 定理1-7.3 P34 在真值表中,一个公式的真值为T的指派所对应的小项的析取,即为此公式的主析取范式。 证明 设给定公式为A，其真值为T的指派所对应的小项为m1，m2，mk，这些小项的析取式记为B。要证A B，只要证A与B在相应指派下具有相同真值。 首先对A为T的某一指派，其对应的小项

10、为mi，则因为mi为T，而m1，m2，mi-1mi+1，mk均为F，故B为T。 其次，对A为F的某一指派，其对应的小项不包含在B中，即m1，m2，mk均为F，故B为F。 因此A B。,5、求一个命题公式的主析取范式的方法,例题6P34 求公式P Q，P Q，和 (P Q ）的主析取范式。 解 三公式的真值表如下：,故 P Q (P Q )(P Q ) (P Q)= m00 m01 m11,P Q (P Q )(P Q ) (P Q)= m01 m10 m11, (P Q) (P Q )(P Q ) (P Q),例题7 p35 设一个公式A的真值表如下,求公式A的主析取范式。,公式A的主析取范式

11、为： A (P Q R ) (P Q R )(P Q R) =m000 m100 m111= m0 m4 m7,求一个命题公式的主析取范式的方法 (2) 利用基本等价公式推出 例题8p35 求 (PQ ) (PR) (QR)的主析取范式。, (PQR) (PQR) ) (PR Q ) (PR Q) ) (QR P) (QR P), (PQR) (PQR) (PQ R ) (P Q R),例题9p35 试求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)

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

13、布尔析取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。 例如，两个命题变元P和Q，其大项为： PQ，PQ，PQ，PQ。,6、大项,三个命题变元P、Q、R，其大项为： PQR， PQ R ， PQR ， PQ R ， PQR ， PQ R ， PQ R ，PQ R 。 n个命题变元共有2n个大项。,每个大项可用n位二进制予以编码： 若n=2 M00= PQ ， M01= PQ M10= PQ ， M11= PQ 若n=3 M000= PQ R ， M100= PQ R M001= PQ R， M101=PQ R M010= PQ R ， M110=PQ R M011=

14、PQ R， M111=PQR,7、大项的编码,两个命题变元P和Q及其大项的真值表：,从上表可以看到，没有两个大项是等价的，且每个大项都只对应P和Q的一组真值指派，使得该大项的真值为F。,三个命题变元P、Q、R及其大项的真值表（真值T和F分别记为1和0）：,（1）每一个大项当其真值指派与编码相同时，其真 值为F，在其余2n-1种指派情况下均为T。,8、大项的性质p37,（3）全体大项的合取式必为永假，记为： M0M1M2n-1 F,（ 2）任意两个不同大项的析取式为永真。 MiMj T （ij）,大项有如下性质：,定义1-7.7 对于给定的命题公式，如果有一个 等价公式，它仅由大项的合取所组成，

15、则 该等价式称作原式的主合取范式。 如(PQ )(PQ)的主合取范式为 (PQ ) (PQ),9、主合取范式p37,10、求一个命题公式的主合取范式的方法 （1） 真值表法 定理1-7.4 在真值表中,一个公式的真值为F的指 派所对应的大项的合取,即为此公式的主合取范式。 证明与定理1-7.3相同。,例题10p37 利用真值表技术求(P Q ) (P R )的主合 取范式与主析取范式。 解 公式(P Q ) (P R )的真值表如下：,主合取范式为： (P Q ) (P R ) (P Q R ) (P Q R) (P Q R) (P QR) =M101 M100 M010 M000= M0 M

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

17、R)(PQR)= M101 M100 M010 M000 =0，2，4，5, (QPR)(QPR)(PRQ) (PRQ)(QRP)(QRP), (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、主析取范式与主合取范式之间的关系： 由于主范式是由小项或大项构成，从小项和大项的定义，可知两者有下列关系： miMi Mimi 因此，主析取范式和主合取范式有着“互补”关 系，即是由给定公式的主析取范式可以求出其 主合取范式。,为了使主析取范式和主合取范式

18、表达简洁，今后用表示小项的析取,用表示大项的合取， (P Q ) (P R ) m001m011m110m111= 1，3，6，7 (P Q ) (P 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,如 (PQ)Qm1m3，则(PQ)QM0M2。,五、小结 本节主要内容 对偶式 在给定的命题公式中，将联结词换成，将换成 ，若有特殊变元F和T亦相互取代，所得公式A*称作A的对偶式。 合取范式 一个命题公式称为合取范式，当且仅当它具有形式：

19、 A1 A2 An， （n1） 其中A1，A2，An都是由命题变元或其否定所组成的析取式。 析取范式 一个命题公式称为析取范式，当且仅当它具有形式： A1 A2 An， （n1） 其中A1，A2，An都是由命题变元或其否定所组成的合取式。,小项 n个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。 大项 n个命题变元的析取式，称作布尔析取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。 小项性质： （1）每一个小项当其真值指派与编码相同时，其真值为T，在其余2n-1种指派情况下均为F。 （2）任意两个不同小项的合取式

20、永为F。 （3）全体小项的析取式永为T。 大项性质： （1）每一个大项当其真值指派与编码相同时，其真值为F，在其余2永-1种指派情况下均为T。 （2）任意两个不同大项的析取式为永T。 （3）全体大项的合取式必为永为F。,主析取范式 对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取范式。 主合取范式 对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式的主合取范式。,定理1-7.1 设A和A*是对偶式，P1， P2 ，Pn是出 现在A和A*中的原子变元，则 A( P1， P2 ，Pn ) A*( P1， P2 ，Pn ) A( P1， P