离散数学2.ppt

离散数学2CHAPTER TWOCHAPTER TWO第一章第一章命题逻辑等值演算命题逻辑等值演算ChapteronePropositionLogic2021/5/222Discrete Math.CHAPTER TWOCHAPTER TWO2.1等值式等值式2.2析取范式与合取范式析取范式与合取范式2.3联结词的完备集联结词的完备集等值式定义等值式定义基本等值式基本等值式等值演算（置换规则）等值演算（置换规则）简单析取（合取）式简单析取（合取）式极大（小）项极大（小）项（主）析（合）取范式（主）析（合）取范式真值函数真值函数联结词完备集联结词完备集2.4可满足性问题与消解法可满足性问题与消解法第一章内容第一章内容2021/5/223Discrete Math.CHAPTER TWOCHAPTER TWO设设公公式式、中中总总共共含含有有命命题题变变项项p1,p2,pn，但但或或并并不不全全含含有有这这些些变变项项。如如果果某某个个变变项项未未在在公公式式中中出出现现，则则称称该该变项为的变项为的哑元哑元。同样可定义的哑元。同样可定义的哑元。在在讨讨论论与与是是否否有有相相同同的的真真值值表表时时，应应将将哑哑元元考考虑虑在在内内，即即将将、都都看看成成含含所所有有p1,p2,pn的的命命题题公公式式，如如果果在在所所有有2n个赋值下，与的真值相同，则个赋值下，与的真值相同，则为重言式。为重言式。哑元哑元2021/5/224Discrete Math.CHAPTER TWOCHAPTER TWO定定义义2.1设设A,B是是两两个个命命题题公公式式，若若A,B构构成成的的等等价价式式AB为为重言式重言式，则称，则称A与与B是是等值等值的的,记为记为AB。例例2.1 判断公式判断公式(pq)(pq)与与 pq pq是否等值。是否等值。解：用真值表法判断解：用真值表法判断,如下：如下：pqppqqpqpq(pq)(pq)pqpq(pq)(pq)(pqpq)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 1定义定义2021/5/225Discrete Math.CHAPTER TWOCHAPTER TWO(1)p(qr)(1)p(qr)与与(pq)r;(2)(pq)r(pq)r;(2)(pq)r 与与(pq)r(pq)r。解：所给的解：所给的4 4个公式的真值表如下：个公式的真值表如下：pqrp(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由真值表可见，由真值表可见，p(qr)p(qr)(pq)r,(pq)r,例例2.2 判断下列两组公式是否等值：判断下列两组公式是否等值：2021/5/226Discrete Math.CHAPTER TWOCHAPTER TWO 当当命命题题公公式式中中变变项项较较多多时时，用用上上述述方方法法判判断断两两个个公公式式是是否否等等值值计计算算量量很很大大。为为此此，人人们们将将一一组组经经检检验验为为正正确确的的等等值值式式作作为为等等值值式式模模式式，通通过过公公式式间间的的等等值值演演算算来来判判断断两两公公式式是是否否等等值值。常用的常用的等值式模式等值式模式如下：如下：1.1.双重否定律：双重否定律：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(AB)A(AB)A,A(AB)A,A(AB)A A等值式模式等值式模式2021/5/227Discrete Math.CHAPTER TWOCHAPTER TWO8.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 BAABB16.16.归谬论归谬论:(AB)(AB):(AB)(AB)A A等值式模式（续）等值式模式（续）2021/5/228Discrete Math.CHAPTER TWOCHAPTER TWO 利用这利用这1616组组2424个等值式可以推演出更多的等值式。由已个等值式可以推演出更多的等值式。由已知的等值式推演出另一些等值式的过程称为知的等值式推演出另一些等值式的过程称为等值演算等值演算。在等。在等值演算中值演算中,经常用到如下置换规则。经常用到如下置换规则。置置换换规规则则:设设(A)(A)是是含含公公式式A A的的命命题题公公式式，(B)(B)是是用用公公式式B B置置 换换 了了(A)(A)中中 所所 有有 的的 A A后后 所所 得得 的的 公公 式式。若若 B BA A,则则(B)(B)(A)(A)。等值演算等值演算2021/5/229Discrete Math.CHAPTER TWOCHAPTER TWO 例例如如，对对公公式式(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)为简便起见为简便起见,以后凡用到置换规则时以后凡用到置换规则时,均不必标出。均不必标出。(蕴含等值式，置换规则）蕴含等值式，置换规则）(蕴含等值式，置换规则）蕴含等值式，置换规则）(德摩根律，置换规则）德摩根律，置换规则）(分配律，置换规则）分配律，置换规则）等值演算等值演算-例子例子2021/5/2210Discrete Math.CHAPTER TWOCHAPTER TWO例例2.3 用等值演算证明用等值演算证明:(p:(pq)q)r(pr)(qr)(pr)(qr)注：注：用等值演算证明等值式时，既可以从左向右推演，也可以用等值演算证明等值式时，既可以从左向右推演，也可以从右向左推演。从右向左推演。证：证：(pr)(qr)(pr)(qr)(pr)(qr)(pr)(qr)(pq)r(pq)r(pq)r(pq)r(pq)r(pq)r (蕴含等值式蕴含等值式)(分配律分配律)(德摩根律德摩根律)(蕴蕴 含含 等等 值值 式式)例例2.32021/5/2211Discrete Math.CHAPTER TWOCHAPTER TWO证明：证明：(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)r A=(pq)r(pq)r(pq)r (pq)r(pq)r (pq)r(pq)r B=p(qr)B=p(qr)p(qr)p(qr)pqrpqr易见，易见，000000，010010是是A A的成假赋值，而它们是的成假赋值，而它们是B B的成真赋值。的成真赋值。方法二：观察法。方法二：观察法。(pq)r (pq)r p(qr)p(qr)。证证方法一：真值表法。方法一：真值表法。故故(蕴含等值式蕴含等值式)(蕴含等值式蕴含等值式)(德摩根律德摩根律)(蕴含等值式蕴含等值式)(结合律结合律)例例242021/5/2212Discrete Math.CHAPTER TWOCHAPTER TWO(1)（pq)pq;(2)(p(pq)r;(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)p1p1故故(pq)pq是重言式。是重言式。用等值演算判断下列公式的类型用等值演算判断下列公式的类型(蕴含等值式蕴含等值式)(蕴含等值式蕴含等值式)(德摩根律德摩根律)(德摩根律德摩根律)(分配律分配律)(排中律排中律)(同一律）同一律）(交换律，结合律）交换律，结合律）（排中律）（排中律）（零律）（零律）例例2.52021/5/2213Discrete Math.CHAPTER TWOCHAPTER TWO(2)(2)(p(pq)r(ppq)r (ppq)r (0q)r 0r 0 故故 (p(pq)r是矛盾式。是矛盾式。(蕴含等值式，结合律）蕴含等值式，结合律）(德摩根律）德摩根律）(矛盾律）矛盾律）(零律零律)(零律）零律）例例2.5（续）（续）2021/5/2214Discrete Math.CHAPTER TWOCHAPTER TWO(3)p(pq)p)q)(4)p(pq)p)q)(蕴含等值式蕴含等值式)(5)p(pp)(qp)q)(分配律分配律)(6)p(0(qp)q)(矛盾律矛盾律)(7)p(qp)q)(同一律同一律)(8)p(qp)q)(德德摩摩根根律律，双双重重否否定定律律)(9)p(qq)p)(交换律，结合律交换律，结合律)(10)p(1p)（排中律）排中律）(11)p1 （零律）零律）(12)p （同一律）同一律）(13)(13)可可见见，（3 3）中中公公式式不不是是重重言言式式，因因为为0000，01 01 都都是是成成假假赋赋值值；它它也也不不是是矛矛盾盾式式，因因为为1010，11 11 都都是是其其成成真真赋赋值值，故故它它是是可可满足式。满足式。例例2.5（续）（续）2021/5/2215Discrete Math.CHAPTER TWOCHAPTER TWO例例2.6在某次研讨会的休息时间，在某次研讨会的休息时间，3名与会者根据王教授的口音名与会者根据王教授的口音对他是哪个省市的人进行了判断：对他是哪个省市的人进行了判断：甲说王教授不是苏州人，是上海人。甲说王教授不是苏州人，是上海人。乙说王教授不是上海人，是苏州人。乙说王教授不是上海人，是苏州人。丙说王教授不是上海人，也不是杭州人。丙说王教授不是上海人，也不是杭州人。听完听完3人的判断，王教授笑着说，他们人的判断，王教授笑着说，他们3人中有一人说得全对，人中有一人说得全对，有一人说对了一半，有一人说得全不对。试用逻辑演算法分析有一人说对了一半，有一人说得全不对。试用逻辑演算法分析王教授到底是哪里的人？王教授到底是哪里的人？解解：设命题设命题p,q,r分别表示分别表示：王教授是苏州、上海、杭州人。王教授是苏州、上海、杭州人。则则p,q,r中必有一个真命题，两个假命题。要通过逻辑演算将真中必有一个真命题，两个假命题。要通过逻辑演算将真命题找出来。命题找出来。设：设：甲的判断为：甲的判断为：A1=pq;乙的判断为：乙的判断为：A2=pq;丙的丙的判断为：判断为：A3=qr。例例2.62021/5/2216Discrete Math.CHAPTER TWOCHAPTER TWO那么甲的判断全对：那么甲的判断全对：B1=A1=pq甲的判断对一半：甲的判断对一半：B2=(pq)(pq)甲的判断全错：甲的判断全错：B3=pq乙的判断全对：乙的判断全对：C1=A2=pq乙的判断对一半：乙的判断对一半：C2=(pq)(pq)乙的判断全错：乙的判断全错：C3=pq丙的判断全对：丙的判断全对：D1=A3=qr丙的判断对一半：丙的判断对一半：D2=(qr)(qr)丙的判断全错：丙的判断全错：D3=qr由王教授所说由王教授所说E=(B1C2D3)(B1C3D2)(B2C1D3)(B2C3D1)(B3C1D2)(B3C2D1)为真命题为真命题.例例2.6（续）（续）2021/5/2217Discrete Math.CHAPTER TWOCHAPTER TWOB1C2D3=(pq)(pq)(pq)(qr)(pqqr)(pqpr)0B1C3D2=(pq)(pq)(qr)(qr)(pqr)(pqqr)pqrB2C1D3=(pq)(pq)(pq)(qr)(pppqqr)(pqqr)0类似可得类似可得B2C3D10,B3C1D2pqr,B3C2D10于是，由同一律可知于是，由同一律可知E(pqr)(pqr)但因为王教授不能既是苏州人，又是杭州人，因而但因为王教授不能既是苏州人，又是杭州人，因而p,r必有一个为假命必有一个为假命题，即题，即pqr0。于是于是Epqr为真命题，因而必有为真命题，因而必有p,r为假命题，为假命题，q为真命题，为真命题，即王教授为上海人，甲说得全对，丙说对了一半，而乙全说错啦。即王教授为上海人，甲说得全对，丙说对了一半，而乙全说错啦。例例2.6（续）（续）2021/5/2218Discrete Math.CHAPTER TWOCHAPTER TWO定义定义2.22.2 命题变项及其否定统称作命题变项及其否定统称作文字文字。仅由有限个文字构成的仅由有限个文字构成的析取式析取式称作称作简单析取式简单析取式；仅由有限个文字构成的仅由有限个文字构成的合取式合取式称作称作简单合取式简单合取式。2.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)一个简单析取式是重言式当且仅当它同时含有某一个简单析取式是重言式当且仅当它同时含有某个命题变项及它的否定式；个命题变项及它的否定式；(2)一一个个简简单单合合取取式式是是矛矛盾盾式式当当且且仅仅当当它它同同时时含含有有某某个个命命题题变项及其否定式。变项及其否定式。2021/5/2219Discrete Math.CHAPTER TWOCHAPTER TWO例如：例如：(p(pq)q)(q qr)r)r r是一个析取范式，是一个析取范式，而而(p(pq qr)r)(p pq)q)r r是一个合取范式。是一个合取范式。注：注：单个文字单个文字既是简单析取式又是简单合取式。既是简单析取式又是简单合取式。因因此此形形如如p pq qr r的的公公式式既既是是由由一一个个简简单单合合取取式式构构成成的的析析取范式，又是由三个简单析取式构成的合取范式。取范式，又是由三个简单析取式构成的合取范式。类类似似地地，形形如如p pq qr r的的公公式式既既可可看看成成析析取取范范式式也也可可看看成成合取范式。合取范式。定义定义2.32.3 由有限个简单合取式构成的析取式称为由有限个简单合取式构成的析取式称为析取范式析取范式；由有限个简单析取式构成的合取式成为由有限个简单析取式构成的合取式成为合取范式合取范式；析取范式与合取范式统称为析取范式与合取范式统称为范式范式。定义定义2021/5/2220Discrete Math.CHAPTER TWOCHAPTER TWO析取范式的一般形式：析取范式的一般形式：AA1 A2 An,其中其中Ai(i=1,n)是简单合取式；是简单合取式；合取范式的一般形式：合取范式的一般形式：AA1 A2 An,其中其中Ai(i=1,n)是简单析取式是简单析取式。定定理理2.22.2 （1 1）一一个个析析取取范范式式是是矛矛盾盾式式当当且且仅仅当当它它的的每每个个简简单合取式都是矛盾式；单合取式都是矛盾式；（2）一一个个合合取取范范式式是是重重言言式式当当且且仅仅当当它它的的每每个个简简单单析析取取式式都是重言式。都是重言式。范式的一般形式范式的一般形式2021/5/2221Discrete Math.CHAPTER TWOCHAPTER TWO定定理理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)。使使用用这这些些等等值值式式，便便可可将将任任一一公公式式化化成成与与之之等等值值的的析析取取范范式式或合取或合取范范式。式。范式存在定理范式存在定理2021/5/2222Discrete Math.CHAPTER TWOCHAPTER TWO求给定公式的求给定公式的范范式的步骤：式的步骤：(1)(1)消去联结词消去联结词和和；(2)(2)否定号否定号的消去的消去(双重否定双重否定)或内移或内移(德摩根律德摩根律)；(3)(3)利用利用对对的分配律求合取的分配律求合取范范式；式；利用利用对对的分配律求析取的分配律求析取范范式。式。求范式的步骤求范式的步骤2021/5/2223Discrete Math.CHAPTER TWOCHAPTER TWO解解:(1):(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)(消去消去)(消去消去)(消去消去)(否定号内移否定号内移,结合律结合律,交换律交换律)(对对的分配律的分配律)(见上述第一至四步见上述第一至四步)(对对的分配律的分配律)(矛盾律和同一律矛盾律和同一律)例例2.7求公式求公式(pq)(pq)r r的析取的析取范范式与合取式与合取范范式。式。2021/5/2224Discrete Math.CHAPTER TWOCHAPTER TWO注：注：1.在在演演算算过过程程中中，利利用用交交换换律律，可可使使每每个个简简单单析析取取式式或或简简单单合取式中命题变项都按字典序出现。合取式中命题变项都按字典序出现。2.上上述述求求析析取取范范式式的的过过程程中中，第第二二步步和和第第三三步步结结果果都都是是析析取取范式。这说明命题公式的析取范式是不唯一的。范式。这说明命题公式的析取范式是不唯一的。3.同同样样，合合取取范范式式也也是是不不唯唯一一的的。为为了了得得到到唯唯一一的的规规范范化化形形式式的的范范式式，需需要要定定义义主主析析取取范范式式和和主主合合取取范范式式。为为此此，先引入如下极小项和极大项概念。先引入如下极小项和极大项概念。范式的注解范式的注解2021/5/2225Discrete Math.CHAPTER TWOCHAPTER TWO定定义义2.4在在含含有有n个个命命题题变变项项的的简简单单合合取取式式(简简单单析析取取式式)中中，若若每每个个命命题题变变项项和和它它的的否否定定式式恰恰好好出出现现一一个个且且仅仅出出现现一一次次，并并且且命命题题变变项项或或其其否否定定式式按按下下标标从从小小到到大大或或按按字字典典序序排排列列)，则则称称该该简单合取式简单合取式(简单析取式简单析取式)为为极小项极小项(极大项极大项)。注注：由由于于每每个个命命题题变变项项在在极极小小项项中中以以原原形形或或否否定定式式形形式式出出现现且且仅仅出出现现一一次次，因因而而n个个命命题题变变项项共共可可产产生生2n个个不不同同的的极极小小项项。每每个个极极小小项项仅仅有有一一个个成成真真赋赋值值，若若一一个个极极小小项项的的成成真真赋赋值值对对应应的二进制数转化为十进制数为的二进制数转化为十进制数为i，则将该极小项记为，则将该极小项记为mi。类类似似地地，n个个命命题题变变项项可可产产生生2n个个不不同同的的极极大大项项。每每个个极极大大项项只只有有一一个个成成假假赋赋值值。若若一一个个极极大大项项的的成成假假赋赋值值对对应应的的十十进进制制数数为为i，则将该极大项记为，则将该极大项记为Mi。极大、小项定义极大、小项定义2021/5/2226Discrete Math.CHAPTER TWOCHAPTER TWO极小项极小项极大项极大项公式公式成真赋值成真赋值名称名称公式公式成假赋值成假赋值名称名称两个变项两个变项p、q形成的极小项与极大项形成的极小项与极大项00m001m110m211m300M001M110M211M3变项取变项取1pqpqpqpqpqpqpqpq变项取变项取0极大、小项真值表极大、小项真值表2021/5/2227Discrete Math.CHAPTER TWOCHAPTER TWO极小项极小项极大项极大项公式公式成真赋值成真赋值名称名称公式公式成假赋值成假赋值名称名称pqr000m0pqr000M0pqr001m1pqr001M1pqr010m2pqr010M2pqr011m3pqr011M3pqr100m4pqr100M4pqr101m5pqr101M5pqr110m6pqr110M6pqr111m7pqr111M7三个变项三个变项p,q,r形成的极小项与极大项形成的极小项与极大项变项取变项取1变项取变项取0极大、小项真值表（续）极大、小项真值表（续）2021/5/2228Discrete Math.CHAPTER TWOCHAPTER TWO定定理理2.4设设mi与与Mi是是命命题题变变项项p p1,1,p p2 2,p,pn n形形成成的的极极小小项项和和极极大大项，则项，则mi Mi，Mi mi。证明：略，可从以上两表验证该定理。证明：略，可从以上两表验证该定理。定定义义2.5如如果果由由n个个命命题题变变项项构构成成的的析析取取范范式式（合合取取范范式式）中中所所有有的的简简单单合合取取式式(简简单单析析取取式式)都都是是极极小小项项（极极大大项项),则则称称该该析析取式（合取式）为取式（合取式）为主析取范式（主合取范式）主析取范式（主合取范式）。定定理理2.5任任何何命命题题公公式式都都存存在在着着与与之之等等值值的的主主析析取取范范式式和和主主合合取取范式，并且是唯一的。范式，并且是唯一的。证明：见教材证明：见教材26页。页。主范式定义主范式定义2021/5/2229Discrete Math.CHAPTER TWOCHAPTER TWO注：注：主析取范式和主合取范式的主析取范式和主合取范式的求法求法：(1)先先通通过过等等值值推推演演将将所所给给的的命命题题公公式式化化为为析析取取范范式式（合合取取范式）；范式）；(2)若若某某个个简简单单合合取取式式（简简单单析析取取式式）A中中既既不不含含变变项项pi,又又不含变不含变项项pi,则通过：则通过：AA1A(pipi)(Api)(Api)或：或：AA0A(pipi)(Api)(Api)补齐变项。补齐变项。(3)(3)消消去去重重复复变变项项和和矛矛盾盾式式，如如用用p,mi,0分分别别代代替替pp，mimi和和矛盾式，等。矛盾式，等。主范式求法主范式求法2021/5/2230Discrete Math.CHAPTER TWOCHAPTER TWO解解:(1)主析取范式主析取范式由由例例2.7知知，(pq)r(pqr)(pr)(qr)(pr)p(qq)r(pqr)(pqr)m1m3(qr)(pp)qr(pqr)(pqr)m3m7（pqr)m4 (pq)rm1m3m4m7求公式求公式(pq)r的主析的主析(合合)取范式。取范式。例例例例2.82.82021/5/2231Discrete Math.CHAPTER TWOCHAPTER TWO(2)主合取范式主合取范式由例由例2.7知，知，(pq)r(pr)(qr)(pqr)(pr)p(qq)r(pqr)(pqr)M0M2(qr)(pp)qr(pqr)(pqr)M2M6(pqr)M5(pq)rM0M2M5M6例例例例2.82.8（续）（续）（续）（续）2021/5/2232Discrete Math.CHAPTER TWOCHAPTER TWO例例2.9求求pq的主析取范式和主合取范式的主析取范式和主合取范式解解:(1)主合取范式主合取范式pqpqM2(2)主析取范式主析取范式pq(pq)(p(qq)(pp)q)(pq)(pq)(pq)(pq)(pq)(pq)(pq)m0m1m3例例例例2.92.92021/5/2233Discrete Math.CHAPTER TWOCHAPTER TWO主析取范式和主合取范式的用途（以主析取范式为例主析取范式和主合取范式的用途（以主析取范式为例)。1.求公式的成真与成假赋值求公式的成真与成假赋值对对含含有有n个个变变项项的的命命题题公公式式A，若若其其主主析析取取范范式式含含s(0s22n n)个个极极小小项项，则则A A有有s s个个成成真真赋赋值值，它它们们是是极极小小项项下下标标的二进制表示，其余的二进制表示，其余2 2n n ss个赋值都是成假赋值。个赋值都是成假赋值。例例如如，在在例例2.82.8中中，(pq)rm1m3m4m7,因因各各极极小小项项含含三三个个文文字字，故故各各极极小小项项下下标标的的长长为为3的的二二进进制制数数001，011，100，111为为该该公公式式的的成成真真赋赋值值，而而其其余余赋赋值值000，010，101，110为成假赋值。为成假赋值。范式的用途范式的用途12021/5/2234Discrete Math.CHAPTER TWOCHAPTER TWO2.判断公式的类型判断公式的类型设公式设公式A中含中含n个变项，则个变项，则(1)A为为重言式重言式当且仅当当且仅当A的主析取范式含全部的主析取范式含全部2n个极小项个极小项；(2)A为为矛矛盾盾式式当当且且仅仅当当A的的主主析析取取范范式式不不含含任任取取极极小小项项。(此此时，记时，记A的主析取范式为的主析取范式为0)。(3)A为为可可满满足足式式当当且且仅仅当当A的的主主析析取取范范式式中中至至少少含含一一个个极极小小项。项。范式的用途范式的用途22021/5/2235Discrete Math.CHAPTER TWOCHAPTER TWO(1)(pq)q;(2)p(pq);(3)(pq)r解：解：(1)(pq)q(pq)qpqq 0.(2)p(pq)ppq(p(qq)(p(qq)(pp)q)(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)m0m1m2m3利用公式的主析取范式判断公式的类型：利用公式的主析取范式判断公式的类型：注：另一种推演注：另一种推演：p(pq)ppq1q1m0m1m2m3该主析取范式含全部该主析取范式含全部22个极小项，故个极小项，故p(pq)是重言式。是重言式。故故(pq)q是矛盾式是矛盾式。例例例例2.102.102021/5/2236Discrete Math.CHAPTER TWOCHAPTER TWO(3)（pq)r(pq)r(pq)r(pq(rr)(pp)(qq)r)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m0m1m3m5m7故该公式是可满足式故该公式是可满足式,但不是重言式。但不是重言式。例例例例2.102.10（续）（续）（续）（续）2021/5/2237Discrete Math.CHAPTER TWOCHAPTER TWO3.判断两公式是否等值判断两公式是否等值设设公公式式A,B共共有有n个个变变项项。按按n个个变变项项求求出出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)r范式的用途范式的用途32021/5/2238Discrete Math.CHAPTER TWOCHAPTER TWO例例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)经经演算演算得其主析取范式为：得其主析取范式为：m1m2m5m1=pqr;m2=pqr;m5=pqr由此可知由此可知,有有3种选派方案：种选派方案：(1)C去去，A,B都都不不去去；(2)B去去，A,C都都不不去去；(3)A,C同同去去，B不去。不去。4.利用主析取范式和主合取式解决应用问题利用主析取范式和主合取式解决应用问题范式的用途范式的用途42021/5/2239Discrete Math.CHAPTER TWOCHAPTER TWO1主合取范式可由主析取范式直接得到。主合取范式可由主析取范式直接得到。设公式设公式A含有含有n个变项，个变项，A的主析取范式为的主析取范式为未在主析取范式中出现的极小项设为未在主析取范式中出现的极小项设为事实上，因事实上，因则则A的主合取范式为：的主合取范式为：故故关于主合取范式的两点说明关于主合取范式的两点说明12021/5/2240Discrete Math.CHAPTER TWOCHAPTER TWO例例2.13由公式的主析取范式，求主合取范式：由公式的主析取范式，求主合取范式：(1)Am1m2,(A含两个变项含两个变项p,q);(2)Bm1m2m3，(B含三个变项含三个变项p,q,r)。解：解：(1)主析取范式中未出现的极小项为：主析取范式中未出现的极小项为：m0,m3,故故A的主合取范式为：的主合取范式为：AM0M3。(2)主析取范式中未出现的极小项为主析取范式中未出现的极小项为m0,m4,m5,m6,m7，故故A的主合取范式为：的主合取范式为：AM0M4M5M6M7。2.重言式与矛盾式的主合取范式重言式与矛盾式的主合取范式重言式无成假赋值，因而其主合取范式不含任何极大项。重言重言式无成假赋值，因而其主合取范式不含任何极大项。重言式的主合取范式记为式的主合取范式记为1。矛盾式无成真赋值，故其主合取范式含有所有矛盾式无成真赋值，故其主合取范式含有所有2n个极大项。个极大项。关于主合取范式的两点说明关于主合取范式的两点说明22021/5/2241Discrete Math.CHAPTER TWOCHAPTER TWO1.含含n个个变变项项的的所所有有公公式式，共共有有22n种种不不同同的的主主析析取取范范式式(主主合合取取范范式式)。这这是是因因为为n个个变变项项共共可可产产生生2n个个极极小小项项(极极大大项项)，因因而而可可产产生生22n种种主主析析取取范范式式(主主合合取取范范式式)(因因每每个个极小项可以在主析取范式中出现或不出现极小项可以在主析取范式中出现或不出现)。2.AB当当且且仅仅当当A与与B有有相相同同的的真真值值表表，又又当当且且仅仅当当A与与B有有相相同同的的主主析析取取范范式式(主主合合取取范范式式)。可可见见，真真值值表表与与主主析析取取范范式式(主主合合取取范范式式)是是描描述述命命题题公公式式标标准准形形式式的的两两种种不同的等价形式。不同的等价形式。本节结束语本节结束语2021/5/2242Discrete Math.CHAPTER TWOCHAPTER TWO定定义义2.6称称映映射射F:0,1n0,1为为n元元真真值值函函数数。其其中中0,1n表示由表示由0，1组成的长为组成的长为n 的字符串集合。的字符串集合。注注：1元元真真值值函函数数有有22=4个个；2元元真真值值函函数数有有222=16个个；3元元真真值函数有值函数有223=256个。个。4个一元真值函数个一元真值函数pF0(1)F1(1)F2(1)F3(1)01000110112.3 联结词的完备集联结词的完备集2021/5/2243Discrete Math.CHAPTER TWOCHAPTER TWOpqF0(2)F1(2)F2(2)F3(2)F4(2)F5(2)F6(2)F7(2)0000000000010000111110001100111101010101pqF8(2)F9(2)F10(2)F11(2)F12(2)F13(2)F14(2)F15(2)0011111111010000111110001100111101010101真值函数真值函数2021/5/2244Discrete Math.CHAPTER TWOCHAPTER TWO注注：每每个个真真值值函函数数与与唯唯一一的的主主析析取取范范式式(主主合合取取范范式式)）等等值值，而而每每个个主主析析取取范范式式(主主合合取取范范式式)对对应应无无穷穷多多个个与与之之等等值值的的命命题题公公式式。因因此此每每个个真真值值函函数数对对应应无无穷穷多多个个与与之之等等值值的的命命题题公公式式。另另一一方方面面，由由定定理理2.5，每每个个命命题题公公式式都都有有唯唯一一一一个个真真值值函数与之等值。函数与之等值。定定义义2.7设设S是是一一个个联联结结词词集集合合。如如果果任任何何n元元(n1)）真真值值函函数数都都可可以以由由仅仅含含S中中的的联联结结词词构构成成的的公公式式表表示示，则则称称S是是联联结结词完备集词完备集。定理定理2.6S=，是联结词完备集。是联结词完备集。证证：因因任任何何n元元真真值值函函数数都都与与唯唯一一一一个个主主析析取取范范式式等等值值，而而主主析取范式中仅含联结词析取范式中仅含联结词,故结论成立。故结论成立。联结词完备集联结词完备集2021/5/2245Discrete Math.CHAPTER TWOCHAPTER TWO(1)S1=,;(2)S2=,;(3)S