1、6/8/2022 9:09 PM Discrete Math. 1离散数学离散数学Discrete MathematicsDiscrete Mathematics 6/8/2022 9:09 PM Discrete Math. 2第一章第一章 命题逻辑等值演算命题逻辑等值演算Chapter oneProposition Logic6/8/2022 9:09 PM Discrete Math. 32.1 等值式等值式2.2 析取范式与合取范式析取范式与合取范式2.3 联结词的完备集联结词的完备集等值式定义等值式定义基本等值式基本等值式等值演算（置换规则）等值演算（置换规则）简单析取（合取）式简单
2、析取（合取）式极大（小）项极大（小）项（主）析（合）取范式（主）析（合）取范式真值函数真值函数联结词完备集联结词完备集2.4 可满足性问题与消解法可满足性问题与消解法6/8/2022 9:09 PM Discrete Math. 4 设公式、中总共含有命题变项设公式、中总共含有命题变项p1, p2, pn，但或并，但或并不全含有这些变项。如果某个变项不全含有这些变项。如果某个变项未在未在公式中公式中出现出现，则称该，则称该变项为的变项为的哑元哑元。同样可定义的哑元。同样可定义的哑元。 在讨论与是否有相同的真值表时，应将哑元考虑在内，在讨论与是否有相同的真值表时，应将哑元考虑在内，即将、都看成含
3、所有即将、都看成含所有p1 , p2 , pn的命题公式，如果在所有的命题公式，如果在所有2n个赋值下，与的真值相同，则个赋值下，与的真值相同，则为重言式。为重言式。6/8/2022 9:09 PM Discrete Math. 5定义定义2.1 设设A ,B 是两个命题公式，若是两个命题公式，若A, B构成的构成的等价式等价式A B为为重言式重言式，则称，则称A与与B是是等值等值的的, 记为记为AB。例例2.1 判断公式判断公式(pq) (pq) 与与 pqpq是否等值。是否等值。解：用真值表法判断解：用真值表法判断, 如下：如下：p qppqqpqpq(pq)(pq)pqpq(pq)(pq
4、)(pq)pq)0 00 00 10 11 01 01 11 1注：注：A A与与B B等值当且仅当等值当且仅当A A与与B B的真值表相同。因此，检验的真值表相同。因此，检验A A与与B B是是否等值，也可通过检查否等值，也可通过检查A A与与B B的真值表是否相同来实现。的真值表是否相同来实现。从表中可见，从表中可见，(pq)(pq)与与pqpq等值。等值。1 11 10 01 11 11 11 10 01 10 00 01 10 01 11 10 00 01 10 00 01 10 00 01 16/8/2022 9:09 PM Discrete Math. 6 (1) p(qr) (1
5、) p(qr)与与(pq)r; (2)(pq)r (pq)r; (2)(pq)r 与与(pq)r(pq)r。解：所给的解：所给的4 4个公式的真值表如下：个公式的真值表如下：p q rp(qr)p(qr)(pq)r(pq)r(pq)r(pq)r0 0 00 0 00 0 10 0 10 1 00 1 00 1 10 1 11 0 01 0 01 0 11 0 11 1 01 1 01 1 11 1 1但但(pq)r(pq)r(pq)r.(pq)r.1 11 10 01 11 11 11 11 10 01 11 11 11 11 11 11 11 11 10 00 00 01 11 11 1由真
6、值表可见，由真值表可见，p(qr)p(qr)(pq)r(pq)r, ,例例2.2 判断下列两组公式是否等值：判断下列两组公式是否等值：6/8/2022 9:09 PM Discrete Math. 7 当命题公式中变项较多时，用上述方法判断两个公式是否当命题公式中变项较多时，用上述方法判断两个公式是否等值计算量很大。为此，人们将一组经检验为正确的等值式作等值计算量很大。为此，人们将一组经检验为正确的等值式作为为等值式模式等值式模式，通过公式间的，通过公式间的等值演算等值演算来判断两公式是否等值。来判断两公式是否等值。常用的常用的等值式模式等值式模式如下：如下： 1.1.双重否定律：双重否定律：
7、A A (A) 2. (A) 2.幂等律：幂等律：A AAA, AAA, AAAAA 3. 3.交换律交换律: AB: ABBA, ABBA, ABBABA 4. 4.结合律结合律: (AB)C: (AB)CA(BC), (AB)CA(BC), (AB)CA(BC)A(BC) 5. 5.分配律：分配律：A(BC)A(BC)(AB)(AC) (AB)(AC) (对对的分配律的分配律) ) A(BC) A(BC)(AB)(AC) (AB)(AC) (对对的分配律的分配律) ) 6. 6.德摩根律：德摩根律：(AB)(AB) AB, (AB) AB, (AB)ABAB 7. 7.吸收律：吸收律：A(
8、AB)A(AB)A, A(AB)A, A(AB)A A6/8/2022 9:09 PM Discrete Math. 88.8.零律：零律：A1A11, A01, A00 09. 9. 同一律：同一律：A0A0A, A1A, A1A A10. 10. 排中律：排中律：AAAA1 111. 11. 矛盾律：矛盾律：AAAA0 012. 12. 蕴含等值式：蕴含等值式：ABABABAB13. 13. 等价等值式等价等值式: (A: (AB)B)(AB)(BA)(AB)(BA)14. 14. 假言易位假言易位: AB: AB BA BA15. 15. 等价否定等值等价否定等值式式: A: AB BA
9、ABB16. 16. 归谬论归谬论: (AB)(AB) : (AB)(AB) A A6/8/2022 9:09 PM Discrete Math. 9 利用这利用这1616组组2424个等值式可以推演出更多的等值式。由已个等值式可以推演出更多的等值式。由已知的等值式推演出另一些等值式的过程称为知的等值式推演出另一些等值式的过程称为等值演算等值演算。在等。在等值演算中值演算中, ,经常用到如下置换规则。经常用到如下置换规则。置换规则置换规则: : 设设(A)(A)是含公式是含公式A A的命题公式，的命题公式，(B)(B)是用公式是用公式B B置换置换了了(A)(A)中中所有所有的的A A后所得的
10、公式。若后所得的公式。若B BA A, ,则则(B)(B)(A)(A)。 6/8/2022 9:09 PM Discrete Math. 10 例如，对公式例如，对公式(pq)r,(pq)r,如果用如果用pqpq置换置换其中的其中的pq,pq,则则得得(pq)r.(pq)r.由于由于pqpqpqpq，故，故(pq)r (pq)r (pq)r(pq)r。类似地，可进行如下类似地，可进行如下等值演算等值演算： (pq)r (pq)r (pq)r(pq)r (pq)r (pq)r (pq)r (pq)r (pr)(qr(pr)(qr) )为简便起见为简便起见, 以后凡用到置换规则时以后凡用到置换规则
11、时, 均不必标出。均不必标出。( (蕴含等值式，置换规则）蕴含等值式，置换规则）( (蕴含等值式，置换规则）蕴含等值式，置换规则）( (德摩根律，置换规则）德摩根律，置换规则）( (分配律，置换规则）分配律，置换规则）6/8/2022 9:09 PM Discrete Math. 11例例2.3 用等值演算证明用等值演算证明: (p: (pq)q)r (pr)(qr)(pr)(qr) 注：注：用等值演算证明等值式时，既可以从左向右推演，也可以用等值演算证明等值式时，既可以从左向右推演，也可以从右向左推演。从右向左推演。证：证：(pr)(qr(pr)(qr) )(pr)(qr(pr)(qr) )
12、(pq)r(pq)r(pq)r(pq)r(pq)r (pq)r ( (蕴含等值式蕴含等值式) )( (分配律分配律) )( (德摩根律德摩根律) )( (蕴含等值式蕴含等值式)6/8/2022 9:09 PM Discrete Math. 12 证明：证明：(pq)r (pq)r p(qr p(qr）. .方法三方法三: : 记记A=(pq)r, B= p(qr)A=(pq)r, B= p(qr)。先将。先将A,BA,B等值演算等值演算 化成易于观察真值的公式，再进行判断。化成易于观察真值的公式，再进行判断。 A=(pq)rA=(pq)r(pq)r(pq)r (pq)r (pq)r (pq)r
13、(pq)r B=p(qr) B=p(qr)p(qrp(qr) ) pqrpqr 易见，易见，000000，010010是是A A的成假赋值，而它们是的成假赋值，而它们是B B的成真赋值。的成真赋值。方法二：观察法。方法二：观察法。 (pq)r (pq)r p(qr p(qr) )。证证 方法一：真值表法。方法一：真值表法。故故 ( (蕴含等值式蕴含等值式) ) ( (蕴含等值式蕴含等值式) ) ( (德摩根律德摩根律) )( (蕴含等值式蕴含等值式) )( (结合律结合律) )6/8/2022 9:09 PM Discrete Math. 13(1)（pq)pq; (2) (p(pq)r; (
14、3) p(pq)p)q).解解: (1) （pq)pq (pq)pq (pq)p)q (pq)p)q (pq)p)q (pp)(qp)q (1(qp)q (qp)q (qq)p 1p 1 故故 (pq)pq是重言式。是重言式。用等值演算判断下列公式的类型用等值演算判断下列公式的类型(蕴含等值式蕴含等值式)(蕴含等值式蕴含等值式)(德摩根律德摩根律)(德摩根律德摩根律)(分配律分配律)(排中律排中律)(同一律）同一律）(交换律，结合律）交换律，结合律）（排中律）（排中律）（零律）（零律）6/8/2022 9:09 PM Discrete Math. 14(2) (2) (p(pq)r (ppq)
15、r (pp q)r (0q)r 0r 0 故故 (p(pq)r是矛盾式。是矛盾式。( (蕴含等值式，结合律）蕴含等值式，结合律） ( (德摩根律）德摩根律）( (矛盾律）矛盾律）( (零律零律) )( (零律）零律）6/8/2022 9:09 PM Discrete Math. 15(3) p(pq)p)q) p(pq)p)q) ( (蕴含等值式蕴含等值式) ) p(pp)(qp)q) ( (分配律分配律) ) p(0(qp)q) ( (矛盾律矛盾律) ) p(qp)q) ( (同一律同一律) ) p(qp)q) ( (德摩根律，双重否定律德摩根律，双重否定律) ) p(qq)p) ( (交换
16、律，结合律交换律，结合律) ) p(1p) （排中律）（排中律） p1 （零律）（零律） p （同一律）（同一律） 可见，（可见，（3 3）中公式不是重言式，因为）中公式不是重言式，因为0000，01 01 都是成假赋值；都是成假赋值；它也不是矛盾式，因为它也不是矛盾式，因为1010，11 11 都是其成真赋值，故它是可满足都是其成真赋值，故它是可满足式。式。6/8/2022 9:09 PM Discrete Math. 16例例2.6 在某次研讨会的休息时间，在某次研讨会的休息时间，3名与会者根据王教授的口音名与会者根据王教授的口音对他是哪个省市的人进行了判断：对他是哪个省市的人进行了判断：
17、 甲说王教授不是苏州人，是上海人。甲说王教授不是苏州人，是上海人。 乙说王教授不是上海人，是苏州人。乙说王教授不是上海人，是苏州人。 丙说王教授不是上海人，也不是杭州人。丙说王教授不是上海人，也不是杭州人。听完听完3人的判断，王教授笑着说，他们人的判断，王教授笑着说，他们3人中有一人说得全对，人中有一人说得全对，有一人说对了一半，有一人说得全不对。试用逻辑演算法分析有一人说对了一半，有一人说得全不对。试用逻辑演算法分析王教授到底是哪里的人？王教授到底是哪里的人？ 解解： 设命题设命题 p, q, r分别表示分别表示 ： 王教授是苏州、上海、杭州人。王教授是苏州、上海、杭州人。则则p, q, r
18、中必有一个真命题，两个假命题。要通过逻辑演算将中必有一个真命题，两个假命题。要通过逻辑演算将真命题找出来。真命题找出来。设：设： 甲的判断为：甲的判断为： A1= pq; 乙的判断为：乙的判断为：A2= pq; 丙的丙的判断为：判断为：A3= q r。 6/8/2022 9:09 PM Discrete Math. 17那么甲的判断全对：那么甲的判断全对： B1= A1= pq 甲的判断对一半：甲的判断对一半： B2=(pq)(pq) 甲的判断全错：甲的判断全错： B3=pq 乙的判断全对：乙的判断全对： C1= A2= pq 乙的判断对一半：乙的判断对一半： C2=(pq)(pq) 乙的判断
19、全错：乙的判断全错： C3=pq 丙的判断全对：丙的判断全对： D1= A3=qr 丙的判断对一半：丙的判断对一半： D2=(qr)(qr) 丙的判断全错：丙的判断全错： D3=qr 由王教授所说由王教授所说 E=(B1C2D3) (B1C3D2) (B2C1D3) (B2C3D1) (B3C1D2) (B3C2D1) 为真命题为真命题. 6/8/2022 9:09 PM Discrete Math. 18B1C2D3=(pq) (pq)(pq)(qr) (pqqr) (pqpr)0B1C3D2=(pq)(pq)(qr)(qr) (pqr) (pqqr) pqrB2C1D3=(pq)(pq)
20、(pq)(qr) (pppqqr) (pqqr) 0类似可得类似可得 B2C3D10, B3C1D2pqr, B3C2D10于是，由同一律可知于是，由同一律可知 E(pqr) (pqr)但因为王教授不能既是苏州人，又是杭州人，因而但因为王教授不能既是苏州人，又是杭州人，因而p,r必有一个为假命必有一个为假命题，即题，即pqr0 。于是于是 Epqr 为真命题，因而必有为真命题，因而必有p,r为假命题，为假命题，q为真命题，为真命题，即王教授为上海人，甲说得全对，丙说对了一半，而乙全说错啦。即王教授为上海人，甲说得全对，丙说对了一半，而乙全说错啦。 6/8/2022 9:09 PM Discre
21、te Math. 19定义定义2.22.2 命题变项及其否定统称作命题变项及其否定统称作文字文字。 仅由有限个文字构成的仅由有限个文字构成的析取式析取式称作称作简单析取式简单析取式； 仅由有限个文字构成的仅由有限个文字构成的合取式合取式称作称作简单合取式简单合取式。例如：例如：p p; p p; q qq q; pq; p pq qr r都是简单析取式都是简单析取式. p p; p p; q qq q; p pq qr r; p pppr r都是简单合取式。都是简单合取式。注：注：单个文字单个文字既是简单析取式又是简单合取式。既是简单析取式又是简单合取式。定理定理2.12.1 (1)一个简单析
22、取式是重言式当且仅当它同时含有某一个简单析取式是重言式当且仅当它同时含有某个命题变项及它的否定式；个命题变项及它的否定式；(2)一个简单合取式是矛盾式当且仅当它同时含有某个命题一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及其否定式。变项及其否定式。6/8/2022 9:09 PM Discrete Math. 20例如：例如：(p(pq)q)( (q qr)r)r r是一个析取范式，是一个析取范式， 而而 (p(pq qr)r)( (p pq)q)r r是一个合取范式。是一个合取范式。注：注：单个文字单个文字既是简单析取式又是简单合取式。既是简单析取式又是简单合取式。 因此形如因此形如
23、p pq qr r的公式既是由一个简单合取式构成的析的公式既是由一个简单合取式构成的析取范式，又是由三个简单析取式构成的合取范式。取范式，又是由三个简单析取式构成的合取范式。类似地，形如类似地，形如p pq qr r的公式既可看成析取范式也可看成的公式既可看成析取范式也可看成合取范式。合取范式。定义定义2.32.3 由有限个简单合取式构成的析取式称为由有限个简单合取式构成的析取式称为析取范式析取范式；由有限个简单析取式构成的合取式成为由有限个简单析取式构成的合取式成为合取范式合取范式；析取范式与合取范式统称为析取范式与合取范式统称为范式范式。6/8/2022 9:09 PM Discrete
24、Math. 21析取范式的一般形式：析取范式的一般形式： AA1 A2 An, 其中其中 Ai (i=1,n)是简单合取式；是简单合取式；合取范式的一般形式：合取范式的一般形式： AA1 A2 An, 其中其中 Ai (i=1,n)是简单析取式是简单析取式 。定理定理2.22.2 （1 1）一个析取范式是矛盾式当且仅当它的每个简一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式；单合取式都是矛盾式；（2）一个合取范式是重言式当且仅当它的每个简单析取式）一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。都是重言式。6/8/2022 9:09 PM Discrete Math. 22
25、定理定理2.32.3（范式存在定理）（范式存在定理）任一命题公式都存在着与之等值的析任一命题公式都存在着与之等值的析取范式与合取范式。取范式与合取范式。证明：首先由蕴含等值式和等价等值式可知：证明：首先由蕴含等值式和等价等值式可知：A AB BA AB, AB, AB B( (A AB)B)(A(AB)B)。由双重否定律和德摩根律可知：由双重否定律和德摩根律可知：A AA, (AB)A, (AB)AB, (AB)AB, (AB)ABAB。利用分配律，可得利用分配律，可得: : A(BC)A(BC)(AB)(AC)(AB)(AC)，A(BC)A(BC)(AB)(AC)(AB)(AC)。 使用这些
26、等值式，便可将任一使用这些等值式，便可将任一公式公式化成与之等值的析取化成与之等值的析取范范式式或合取或合取范范式。式。 6/8/2022 9:09 PM Discrete Math. 23求给定公式的求给定公式的范范式的步骤：式的步骤：(1) (1) 消去联结词消去联结词和和；(2) (2) 否定号否定号的消去的消去( (双重否定双重否定) ) 或内移或内移( (德摩根律德摩根律) )；(3)(3)利用利用对对的分配律求合取的分配律求合取范范式；式； 利用利用对对的分配律求析取的分配律求析取范范式。式。 6/8/2022 9:09 PM Discrete Math. 24解解: (1): (
27、1)合取合取范范式：式：(pq)r (pq) r (pq) r)(r(pq) (pq)r)(r(pq) (pq)r)(pqr) (pr)(qr)(pqr) (2) 析取范式析取范式(pq)r (pq)r)(pqr) (pqp)(pqq)(pqr)(rp)(rq)(rr) (pqr)(pr)(qr)(消去消去)(消去消去)(消去消去)(否定号内移否定号内移, 结合律结合律, 交换律交换律)(对对的分配律的分配律)(见上述第一至四步见上述第一至四步)(对对的分配律的分配律)(矛盾律和同一律矛盾律和同一律)求公式求公式(pq)(pq)r r的析取的析取范范式与合取式与合取范范式。式。6/8/2022
28、 9:09 PM Discrete Math. 25注：注：1. 在演算过程中，利用交换律，可使每个简单析取式或简单在演算过程中，利用交换律，可使每个简单析取式或简单合取式中命题变项都按字典序出现。合取式中命题变项都按字典序出现。2. 上述求析取范式的过程中，第二步和第三步结果都是析取上述求析取范式的过程中，第二步和第三步结果都是析取范式。这说明命题公式的析取范式是不唯一的。范式。这说明命题公式的析取范式是不唯一的。 同样，合取范式也是不唯一的。为了得到唯一的规范化形同样，合取范式也是不唯一的。为了得到唯一的规范化形式的范式，需要定义主析取范式和主合取范式。为此，先式的范式，需要定义主析取范式
29、和主合取范式。为此，先引入如下极小项和极大项概念。引入如下极小项和极大项概念。6/8/2022 9:09 PM Discrete Math. 26定义定义2.4 在含有在含有n个命题变项的个命题变项的简单合取式简单合取式 (简单析取式简单析取式) 中，中，若每个命题变项和它的否定式恰好若每个命题变项和它的否定式恰好出现一个且仅出现一次出现一个且仅出现一次，并，并且命题且命题变项或其否定式变项或其否定式按下标从小到大或按字典序排列按下标从小到大或按字典序排列)，则，则称该称该简单合取式简单合取式(简单析取式简单析取式)为为极小项极小项 (极大项极大项)。注：由于每个命题变项在极小项中以原形或否定
30、式形式注：由于每个命题变项在极小项中以原形或否定式形式出现且出现且仅出现一次仅出现一次，因而，因而n个命题变项共可产生个命题变项共可产生2n 个不同的极小项。个不同的极小项。每个极小项仅有一个成真赋值每个极小项仅有一个成真赋值，若一个极小项的，若一个极小项的成真赋值对应成真赋值对应的二进制数转化为十进制数为的二进制数转化为十进制数为i，则将该极小项记为，则将该极小项记为mi 。 类似地，类似地，n个命题变项可产生个命题变项可产生2n 个不同的极大项。每个极大项个不同的极大项。每个极大项只有一个只有一个成假赋值成假赋值。若一个极大项的成假赋值对应的。若一个极大项的成假赋值对应的十进制数十进制数为
31、为i，则将该极大项记为，则将该极大项记为Mi 。6/8/2022 9:09 PM Discrete Math. 27极小项极小项极大项极大项公式公式成真赋值成真赋值名称名称公式公式成假赋值成假赋值名称名称两个变项两个变项p、q形成的极小项与极大项形成的极小项与极大项 0 0m00 1m11 0m21 1m30 0M00 1M11 0M21 1M3变项取变项取1pqpqpqpqpqpqpqpq变项取变项取06/8/2022 9:09 PM Discrete Math. 28极小项极小项 极大项极大项 公式公式成真赋值成真赋值名称名称公式公式成假赋值成假赋值名称名称pqr0 0 0m0pqr0 0
32、 0M0pqr0 0 1m1pqr0 0 1M1pqr0 1 0m2pqr0 1 0M2pqr0 1 1m3pqr0 1 1M3pqr1 0 0m4pqr1 0 0M4pqr1 0 1m5pqr1 0 1M5pqr1 1 0m6pqr1 1 0M6pqr1 1 1m7pqr1 1 1M7三个变项三个变项p, q, r形成的极小项与极大项形成的极小项与极大项变项取变项取1变项取变项取06/8/2022 9:09 PM Discrete Math. 29定理定理2.4 设设mi 与与Mi 是命题变项是命题变项p p1, 1, p p2 2 ,p,pn n形成的极小项和极大形成的极小项和极大项，则项
33、，则 mi Mi， Mi mi 。证明：略，可从以上两表验证该定理。证明：略，可从以上两表验证该定理。定义定义2.5 如果由如果由n个命题变项构成的析取范式（合取范式）中所个命题变项构成的析取范式（合取范式）中所有的有的简单合取式简单合取式 (简单析取式简单析取式) 都是都是极小项（极大项极小项（极大项), 则称该析则称该析取式（合取式）为取式（合取式）为主析取范式（主合取范式）主析取范式（主合取范式）。定理定理2.5 任何命题公式都存在着与之等值的主析取范式和主合取任何命题公式都存在着与之等值的主析取范式和主合取范式，并且是唯一的。范式，并且是唯一的。证明：见教材证明：见教材26页。页。6/
34、8/2022 9:09 PM Discrete Math. 30注：注：主析取范式和主合取范式的主析取范式和主合取范式的求法求法：(1) 先通过等值推演将所给的命题公式化为析取范式（合取先通过等值推演将所给的命题公式化为析取范式（合取范式）；范式）；(2) 若某个简单合取式（简单析取式）若某个简单合取式（简单析取式）A中既不含变项中既不含变项pi, 又又不含变不含变 项项pi, 则通过：则通过： AA1 A(pipi ) (Api)(Api)或：或： AA0 A(pipi ) (Api) (Api)补齐变项。补齐变项。(3) (3) 消去重复变项和矛盾式，如用消去重复变项和矛盾式，如用p, m
35、i ,0 分别代替分别代替pp，mi mi 和和矛盾式，等。矛盾式，等。 6/8/2022 9:09 PM Discrete Math. 31解解: (1)主析取范式主析取范式 由例由例 2.7 知，知，(pq)r (pqr)(pr)(qr) (pr) p(qq)r (pqr)(pqr) m1m3 (qr) (pp)qr (pqr)(pqr) m3m7 （pq r) m4 (pq)r m1m3m4m7求公式求公式 (pq)r的主析的主析(合合)取范式。取范式。6/8/2022 9:09 PM Discrete Math. 32(2) 主合取范式主合取范式由例由例2.7 知，知，(pq)r (p
36、r)(qr)(pqr) (pr) p(qq)r (pqr)(pqr) M0M2 (qr) (pp)qr (pqr)(pqr) M2M6 (pqr) M5 ( (pq)r M0M2 M5M66/8/2022 9:09 PM Discrete Math. 33例例 2.9 求求pq 的主析取范式和主合取范式的主析取范式和主合取范式解解: (1) 主合取范式主合取范式 pq pq M2 (2) 主析取范式主析取范式 pq (pq ) (p(qq )(pp)q) (pq)(pq)(pq)(pq) (pq)(pq)(pq) m0m1m3 6/8/2022 9:09 PM Discrete Math. 3
37、4主析取范式和主合取范式的用途（以主析取范式为例主析取范式和主合取范式的用途（以主析取范式为例)。 1. 求公式的成真与成假赋值求公式的成真与成假赋值 对含有对含有n个变项的命题公式个变项的命题公式A，若其主析取范式含，若其主析取范式含s (0s22n n) )个极小项，则个极小项，则A A有有s s个成真赋值，它们是极小项个成真赋值，它们是极小项下标的二进制表示，其余下标的二进制表示，其余2 2n n ss个赋值都是成假赋值。个赋值都是成假赋值。 例如，在例例如，在例2.82.8中，中，(pq)rm1m3m4m7, 因因各极小项含三个文字，故各极小项下标的长为各极小项含三个文字，故各极小项下
38、标的长为3的二进制数的二进制数 001，011，100，111为该公式的成真赋值，而其余赋值为该公式的成真赋值，而其余赋值000，010，101，110为成假赋值。为成假赋值。 6/8/2022 9:09 PM Discrete Math. 35 2. 判断公式的类型判断公式的类型设公式设公式A中含中含n个变项，则个变项，则(1) A为为重言式重言式当且仅当当且仅当A的主析取范式含全部的主析取范式含全部2n 个极小项个极小项；(2) A为为矛盾式矛盾式当且仅当当且仅当A的主析取范式的主析取范式不含任取极小项不含任取极小项。(此此时，记时，记A的主析取范式为的主析取范式为0)。(3) A为可满足
39、式当且仅当为可满足式当且仅当A的主析取范式中至少含一个极小的主析取范式中至少含一个极小项。项。6/8/2022 9:09 PM Discrete Math. 36(1) (pq)q; (2) p(pq); (3) (pq)r解：解：(1) (pq)q (pq)q pqq 0. (2) p(pq) ppq (p(qq)(p(qq)(pp)q) (pq)(pq)(pq)(pq)(pq)(pq) (pq)(pq)(pq)(pq) m0m1m2m3利用公式的主析取范式判断公式的类型：利用公式的主析取范式判断公式的类型：注：另一种推演注：另一种推演：p(pq) ppq 1q 1 m0m1m2m3该主析取
40、范式含全部该主析取范式含全部22 个极小项，故个极小项，故p(pq)是重言式。是重言式。故故 (pq)q 是矛盾式是矛盾式。6/8/2022 9:09 PM Discrete Math. 37(3)（pq)r (pq)r (pq)r (pq(rr)(pp)(qq)r) (pqr)(pqr)(pqr) (pqr)(pqr)(pqr) m0 m1 m3 m5m7 故该公式是可满足式故该公式是可满足式, 但不是重言式。但不是重言式。 6/8/2022 9:09 PM Discrete Math. 383. 判断两公式是否等值判断两公式是否等值 设公式设公式A, B共有共有n个变项。按个变项。按n个变
41、项求出个变项求出A, B的主析取范式。的主析取范式。若若A与与B有相同的主析取范式，则有相同的主析取范式，则AB; 否则否则 AB。例例 2.11 判断下面两组公式是否等值。判断下面两组公式是否等值。 (1) p与与(pq)(pq); (2) (pq)r 与与 (pq)r解解: : (1) pp(qq)(pq)(pq)m2m3 而而 (pq)(pq) m2m3， 故故 p(pq)(pq(pq)(pq） (2) 因因(pq)(pq)rm1m3m4m5m7 而而(pq)(pq)rm0m1m2m3m4m5m7 故故 (pq)r(pq)r6/8/2022 9:09 PM Discrete Math.
42、39例例2.12 某单位欲从三人某单位欲从三人A,B,CA,B,C中挑选中挑选1 12 2人出国进修。由于工人出国进修。由于工作需要选派时要满足以下条件作需要选派时要满足以下条件(1)(1)若若A A去，则去，则C C同去；同去；(2)(2)若若B B去，去，则则C C不能去；不能去；(3)(3)若若C C不去，则不去，则A A或或B B可以去。问应如何选派？可以去。问应如何选派？解：设解：设p: p: 派派A A去；去；q q：派：派B B去；去；r: r: 派派C C去。由条件得：去。由条件得： (pr)(q (pr)(q r)(r(pq)r)(r(pq)经经演算演算得其主析取范式为：得其
43、主析取范式为：m1m2m5 m1= pqr; m2 = pqr ; m5 = pqr由此可知由此可知, 有有3种选派方案：种选派方案： (1) C去，去，A, B都不去；都不去；(2) B去，去，A, C都不去；都不去； (3) A,C同去，同去，B不去。不去。4.利用主析取范式和主合取式解决应用问题利用主析取范式和主合取式解决应用问题6/8/2022 9:09 PM Discrete Math. 401主合取范式可由主析取范式直接得到。主合取范式可由主析取范式直接得到。设公式设公式A含有含有n个变项，个变项，A的主析取范式为的主析取范式为12021,1,2, )lniiirAmmmirl（，
44、122,nljjjmmm，122nljjjAMMM未在主析取范式中出现的极小项设为未在主析取范式中出现的极小项设为事实上，因事实上，因则则A的主合取范式为：的主合取范式为：122A( A)()nljjjmmm 122nljjjMMM122Anljjjmmm，故故122 - n ljjjmmm 6/8/2022 9:09 PM Discrete Math. 41例例2.13 由公式的主析取范式，求主合取范式：由公式的主析取范式，求主合取范式：(1) Am1 m2, (A含两个变项含两个变项p, q);(2) Bm1m2m3 ，(B含三个变项含三个变项p, q, r)。解：解：(1) 主析取范式中
45、未出现的极小项为：主析取范式中未出现的极小项为：m0, m3, 故故A的主合取范式为：的主合取范式为： A M0M3。(2) 主析取范式中未出现的极小项为主析取范式中未出现的极小项为m0 , m4 , m5, m6, m7，故故A的主合取范式为：的主合取范式为：AM0M4M5M6M7。2 . 重言式与矛盾式的主合取范式重言式与矛盾式的主合取范式 重言式无成假赋值，因而其主合取范式不含任何极大项。重言重言式无成假赋值，因而其主合取范式不含任何极大项。重言式的主合取范式记为式的主合取范式记为1。 矛盾式无成真赋值，故其主合取范式含有所有矛盾式无成真赋值，故其主合取范式含有所有2n 个极大项。个极大
46、项。6/8/2022 9:09 PM Discrete Math. 421. 含含n个变项的所有公式，共有个变项的所有公式，共有22n种不同的主析取范式种不同的主析取范式(主主合取范式合取范式)。这是因为。这是因为n个变项共可产生个变项共可产生2n个极小项个极小项(极大极大项项)，因而可产生，因而可产生22n种主析取范式种主析取范式(主合取范式主合取范式) (因每个因每个极小项可以在主析取范式中出现或不出现极小项可以在主析取范式中出现或不出现)。2. AB当且仅当当且仅当A与与B有相同的真值表，又当且仅当有相同的真值表，又当且仅当A与与B有相同的主析取范式有相同的主析取范式(主合取范式主合取范
47、式)。可见，真值表与主。可见，真值表与主析取范式析取范式(主合取范式主合取范式)是描述命题公式标准形式的两种是描述命题公式标准形式的两种不同的等价形式。不同的等价形式。6/8/2022 9:09 PM Discrete Math. 43定义定义2.6 称映射称映射F: 0,1n 0,1为为n元真值函数。其中元真值函数。其中 0,1n 表示由表示由0，1组成的长为组成的长为 n 的字符串集合。的字符串集合。注：注：1元真值函数有元真值函数有22=4个；个；2元真值函数有元真值函数有 222=16个；个；3元元真值函数有真值函数有223=256个。个。4个一元真值函数个一元真值函数pF 0(1)F
48、1(1)F2(1)F3(1)01000110116/8/2022 9:09 PM Discrete Math. 44p qF0(2)F1(2)F2(2)F3(2)F4(2)F5(2)F6(2)F7(2)0 0000000000 1000011111 0001100111 101010101p qF8(2)F9(2)F10(2)F11(2)F12(2)F13(2)F14(2)F15(2)0 0111111110 1000011111 0001100111 1010101016/8/2022 9:09 PM Discrete Math. 45注：每个真值函数与唯一的主析取范式注：每个真值函数与唯一
49、的主析取范式(主合取范式主合取范式)）等值，）等值，而每个主析取范式而每个主析取范式(主合取范式主合取范式)对应无穷多个与之等值的命对应无穷多个与之等值的命题公式。因此每个真值函数对应无穷多个与之等值的命题公题公式。因此每个真值函数对应无穷多个与之等值的命题公式。另一方面，由定理式。另一方面，由定理2.5，每个命题公式都有唯一一个真值，每个命题公式都有唯一一个真值函数与之等值。函数与之等值。定义定义2.7 设设S是一个联结词集合。如果任何是一个联结词集合。如果任何n元元(n1)）真值函）真值函数都可以由仅含数都可以由仅含S中的联结词构成的公式表示，则称中的联结词构成的公式表示，则称S是是联结联
50、结词完备集词完备集。定理定理 2.6 S = ，是联结词完备集。是联结词完备集。证：因任何证：因任何n元真值函数都与唯一一个主析取范式等值，而元真值函数都与唯一一个主析取范式等值，而主析取范式中仅含联结词主析取范式中仅含联结词,故结论成立。故结论成立。6/8/2022 9:09 PM Discrete Math. 46(1) S1=, , , ; (2) S2 =, , , , ; (3) S3= , ; (4) S4= , ; (5) S5= , .证证: (1)、(2)显然显然(3) 因任何真值函数都可由只用完备集因任何真值函数都可由只用完备集S =, , 中的联中的联结词表示，而对任意公
