1、第第2 2章章 命题逻辑等值演算命题逻辑等值演算 聊城大学重点课程聊城大学重点课程 离散数学离散数学1/60本章说明本章说明本章说明本章说明q本章主要内容本章主要内容等值式与基本等值式等值式与基本等值式等值演算与置换规则等值演算与置换规则析取范式与合取范式、主析取范式与主合取范式析取范式与合取范式、主析取范式与主合取范式联结词完备集联结词完备集(不讲不讲)q本章与后续各章关系本章与后续各章关系是第一章抽象与延伸是第一章抽象与延伸是后续各章现行准备是后续各章现行准备2/60q两公式什么时候代表了同一个命题呢？两公式什么时候代表了同一个命题呢？q抽象地看，它们真假取值完全相同时即代表抽象地看，它们
2、真假取值完全相同时即代表了相同命题。了相同命题。q设公式设公式A,BA,B共同含有共同含有n n个命题变项，可能对个命题变项，可能对A A或或B B有哑元，若有哑元，若A A与与B B有相同真值表，则说明在有相同真值表，则说明在2 2n n个赋值每个赋值下，个赋值每个赋值下，A A与与B B真值都相同。于是真值都相同。于是等价式等价式A AB B应为重言式。应为重言式。2.1 2.1 等值式等值式3/60定义定义2.12.1 设设A,BA,B是两个命题公式，若是两个命题公式，若A,BA,B组成等价组成等价式式A AB B为重言式为重言式，则称，则称A A与与B B是是等值等值，记作，记作A A
3、B B。说明说明q定义中定义中,A,B,A,B,都是都是元语言符号元语言符号。qA A或或B B中可能有哑元出现。中可能有哑元出现。pq pq (pq)(pq)(rr)rr)r r为左边公式中哑元。为左边公式中哑元。q用真值表能够验证两个公式是否等值。用真值表能够验证两个公式是否等值。等值定义及说明等值定义及说明4/60例例2.1 2.1 判断下面两个公式是否等值判断下面两个公式是否等值(pq)pq)与与 pqpq 解答解答说明说明q在用真值表法判断在用真值表法判断A AB B是否为重言式时，真值是否为重言式时，真值表最终一列能够省略表最终一列能够省略。等值等值例题例题5/60例题例题2.22
4、.2 判断以下各组公式是否等值判断以下各组公式是否等值(1)p(qr)(1)p(qr)与与(pq)r pq)r(2)(2)(pq)rpq)r与与(pq)rpq)r 解答解答等值等值不等值不等值例题例题6/601.1.双重否定律双重否定律A A A A2.2.幂等律幂等律A A AA,AA,A A AA AA 3.3.交换律交换律AB AB BA BA，AB AB BA BA4.4.结合律结合律(AB)C AB)C A(BC)A(BC)(AB)C(AB)C A(BC)A(BC)5.5.分配律分配律A(BC)A(BC)(AB)(AC)(AB)(AC)（对对分配律）分配律）A(BC)A(BC)(AB
5、)(AC)(AB)(AC)（对对分配律）分配律）6.6.德德摩根律摩根律(AB)AB)AB AB(AB)(AB)AB AB 7.7.吸收律吸收律A(AB)A(AB)A A，A(AB)A(AB)A A 基本等值式基本等值式7/60基本等值式基本等值式基本等值式基本等值式 8.8.零律零律A1 A1 1,A0 1,A0 0 0 9.9.同一律同一律A0 A0 A A，A1 A1 A A 10.10.排中律排中律AA AA 1 1 11.11.矛盾律矛盾律AA AA 0 0 12.12.蕴涵等值式蕴涵等值式 AB AB AB AB13.13.等价等值式等价等值式A AB B (AB)(BA)(AB)
6、(BA)14.14.假言易位假言易位AB AB BA BA15.15.等价否定等值式等价否定等值式A AB B A ABB16.16.归谬论归谬论(AB)(AB)AB)(AB)A A 8/60一个逻辑等值式，假如只含有一个逻辑等值式，假如只含有、0 0、1 1那么同时那么同时把把和和交换交换把把0 0和和1 1交换交换得到还是等值式。得到还是等值式。对偶原理对偶原理9/60q各等值式都是用元语言符号书写，其中各等值式都是用元语言符号书写，其中A,B,CA,B,C能够代表任意公能够代表任意公式，称这么等值式为式，称这么等值式为等值式模式等值式模式。q每个等值式模式都给出了无穷多个同类型详细等值式
7、。每个等值式模式都给出了无穷多个同类型详细等值式。比如，在蕴涵等值式比如，在蕴涵等值式 ABABAB AB 中，中，取取A=pA=p，B=qB=q时，得等值式时，得等值式 pqpqpq pq 取取A=pqrA=pqr，B=pqB=pq时，得等值式时，得等值式(pqr)(pq)pqr)(pq)(pqr)(pq)(pqr)(pq)q这些详细等值式都被称为原来等值式模式这些详细等值式都被称为原来等值式模式代入实例代入实例。q由已知等值式推演出另外一些等值式过程为由已知等值式推演出另外一些等值式过程为等值演算等值演算。q置换规则置换规则 设设(A)(A)是含公式是含公式A A命题公式，命题公式，(B)
8、(B)是用公式是用公式B B置换置换了了(A)(A)中全部中全部A A后得到命题公式，若后得到命题公式，若B BA A，则则(B)(B)(A)(A)。等值演算与置换规则等值演算与置换规则10/60q等值演算基础等值演算基础等值关系性质：等值关系性质：自反性：自反性：A AA A。对称性：若对称性：若A AB B，则则B BA A。传递性：若传递性：若A AB B且且B BC C，则则A AC C。基本等值式基本等值式置换规则置换规则q等值演算应用等值演算应用证实两个公式等值证实两个公式等值判断公式类型判断公式类型解判定问题解判定问题关于等值演算说明关于等值演算说明11/60证实两个公式等值证实
9、两个公式等值(pq)r pq)r (pr)(qr)pr)(qr)(pqpq)r)r (pq)(pq)rr（蕴含等值式、置换规则）蕴含等值式、置换规则）(pq)pq)rr（蕴含等值式、置换规则）蕴含等值式、置换规则）(pq)pq)rr（德摩根律、置换规则）德摩根律、置换规则）(pr)(qr)pr)(qr)（分配律、置换规则）分配律、置换规则）说明说明q也能够从右边开始演算也能够从右边开始演算q因为每一步都用置换规则，故可不写出因为每一步都用置换规则，故可不写出q熟练后，基本等值式也能够不写出熟练后，基本等值式也能够不写出q通常不用等值演算直接证实两个公式不等值通常不用等值演算直接证实两个公式不等
10、值解答解答等值演算应用举例等值演算应用举例12/60例例2.32.3 用等值演算法验证等值式用等值演算法验证等值式(pq)r(pq)r (pr)(qr)(pr)(qr)(p(pr)(qr)(qr)r)(p(prr)(q)(qrr)(蕴含等值式蕴含等值式)(pqpq)r)r(分配律分配律)(pq)r(pq)r(德摩根律德摩根律)(pq)r(pq)r(蕴含等值式蕴含等值式)解答解答例题例题13/60例例2.42.4 证实：证实：(pq)r(pq)r 与与 p(qr)p(qr)不等值不等值方法一、方法一、真值表法。真值表法。方法二、方法二、观察法。观察法。易知，易知，010010是是(pq)r(pq
11、)r成假赋值，而成假赋值，而010010是是p(qr)p(qr)成真赋值，所以原不等值式成立。成真赋值，所以原不等值式成立。方法三、方法三、经过等值演算化成轻易观察真值情况，再进行判断。经过等值演算化成轻易观察真值情况，再进行判断。A=(pA=(pq)r q)r (pq)(pq)r r（蕴涵等值式）（蕴涵等值式）(pq)(pq)r r（蕴涵等值式）（蕴涵等值式）(pq)r(pq)r （德摩根律）（德摩根律）B=pB=p(q(qr)r)pp(qrqr)（蕴涵等值式）（蕴涵等值式）pqr pqr （结合律）（结合律）000 000，010010是是A A成假赋值，而它们是成假赋值，而它们是B B成
12、真赋值。成真赋值。解答解答例题例题14/60例题例题2.52.5 用等值演算判断以下公式类型：用等值演算判断以下公式类型：（1 1）(pq)pq(pq)pq（2 2）(p(pq)r(p(pq)r（3 3）p(pq)p)q)p(pq)p)q)例题例题15/60(1)(p(1)(pq)pq q)pq (pq)p(pq)pq q（蕴涵等值式）蕴涵等值式）(pq)p)pq)p)q q（蕴涵等值式）蕴涵等值式）(pq)pq)p)q p)q（德摩根律）德摩根律）(pq)pq)pp)q)q（德摩根律）德摩根律）(pppp)(qp)q)(qp)q（分配律）分配律）(11(q qp)p)q q （排中律）排中律
13、）(qqqq)p)p（同一律）同一律）11p p（排中律）排中律）1 1 （零律）（零律）例例2.5 2.5 解答解答16/60例例例例2.5 2.5 2.5 2.5 解答解答解答解答(2)(p(2)(p(pq)r(pq)r (ppq)r(ppq)r (ppppq)rq)r 00r r 0 0(3)(3)p(pq)p)p(pq)p)q)q)p(pq)p(pq)pp)q)q)p(p(pp)(pp)(qp)q)(qp)q)p(p(00(qp)q)(qp)q)p(p(qqppq q)p1 p1 p p17/60在在某某次次研研讨讨会会中中间间休休息息时时间间，3 3名名与与会会者者依依据据王王教教授
14、授口口音音对对他是哪个省市人进行了判断：他是哪个省市人进行了判断：甲说王教授不是苏州人，是上海人。甲说王教授不是苏州人，是上海人。乙说王教授不是上海人，是苏州人。乙说王教授不是上海人，是苏州人。丙说王教授既不是上海人，也不是杭州人。丙说王教授既不是上海人，也不是杭州人。听听完完以以上上3 3人人判判断断后后，王王教教授授笑笑着着说说，他他们们3 3人人中中有有一一人人说说全全对对，有有一一人人说说对对了了二二分分之之一一，另另一一人人说说全全不不对对。试试用用逻辑演算法分析王教授到底是哪里人？逻辑演算法分析王教授到底是哪里人？2.6 2.6 应用题应用题18/60设命题设命题 p p：王教授是
15、苏州人。王教授是苏州人。q q：王教授是上海人。王教授是上海人。r r：王教授是杭州人。王教授是杭州人。p,q,rp,q,r中必有一个真命题，两个假命题，要经过逻辑演算将真中必有一个真命题，两个假命题，要经过逻辑演算将真命题找出来。命题找出来。设设甲判断为甲判断为A A1 1=pq=pq乙判断为乙判断为A A2 2=pq=pq 丙判断为丙判断为A A3 3=qr =qr 例例2.6 2.6 解答解答19/60甲判断全对甲判断全对 B B1 1=A=A1 1=pq=pq甲判断对二分之一甲判断对二分之一 B B2 2=(pq)(pq)=(pq)(pq)甲判断全错甲判断全错 B B3 3=pq=pq
16、乙判断全对乙判断全对 C C1 1=A=A2 2=pq=pq乙判断对二分之一乙判断对二分之一 C C2 2=(pq)(pq)=(pq)(pq)乙判断全错乙判断全错 C C3 3=pq=pq丙判断全对丙判断全对 D D1 1=A=A3 3=qr=qr丙判断对二分之一丙判断对二分之一 D D2 2=(qr)(qr)=(qr)(qr)丙判断全错丙判断全错 D D3 3=qr=qr例例2.6 2.6 解答解答20/60由王教授所说由王教授所说E=(BE=(B1 1CC2 2DD3 3)(B)(B1 1CC3 3DD2 2)(B)(B2 2CC1 1DD3 3)(B (B2 2CC3 3DD1 1)(B
17、)(B2 2CC1 1DD2 2)(B)(B3 3CC2 2DD1 1)为真命题。为真命题。经过等值演算后经过等值演算后,可得可得E E (pqr)(pqr)(pqr)(pqr)由题设，王教授不能既是上海人，又是杭州人，因而由题设，王教授不能既是上海人，又是杭州人，因而p,rp,r中必中必有一个假命题，即有一个假命题，即pqrpqr0 0，于是，于是E E pqr pqr为真命题，因而必有为真命题，因而必有p,rp,r为假命题，为假命题，q q为真命题，即王教授是上为真命题，即王教授是上海人。甲说全对，丙说对了二分之一，而乙全说错了。海人。甲说全对，丙说对了二分之一，而乙全说错了。例例2.6
18、2.6 解答解答21/60王教授只可能是其中一个城市人或者三个城市都不是。王教授只可能是其中一个城市人或者三个城市都不是。所以，丙最少说对了二分之一。所以，丙最少说对了二分之一。所以，可得甲或乙必有一人全错了。所以，可得甲或乙必有一人全错了。又因为，若甲全错了，则有又因为，若甲全错了，则有pqpq，所以乙全对。所以乙全对。同理，乙全错则甲全对。同理，乙全错则甲全对。所以丙必是一对一错。所以丙必是一对一错。依据上述推理，可对公式依据上述推理，可对公式E E进行简化，方便等值演算。进行简化，方便等值演算。(怎样简化，请同学们课后思索怎样简化，请同学们课后思索)例例2.62.6深入思索深入思索22/
19、60定义定义2.22.2 命题变项及其否定统称作命题变项及其否定统称作文字（文字（letters）。仅由有限个文字组成析取式称作仅由有限个文字组成析取式称作简单析取式简单析取式。仅由有限个文字组成合取式称作仅由有限个文字组成合取式称作简单合取式简单合取式。q简单析取式举例：简单析取式举例：p,qp,qpppp，pq pq pqr,pqrpqr,pqrq简单合取式举例：简单合取式举例：p,qp,qpppp，pqpqpqr,ppqpqr,ppq说明说明q一个文字既是简单析取式，又是简单合取式。一个文字既是简单析取式，又是简单合取式。2.2 2.2 析取范式和合取范式析取范式和合取范式23/60q为
20、讨论方便，有时用为讨论方便，有时用A A1 1,A,A2 2,A,As s表示表示s s个简单析取式或个简单析取式或s s个简个简单合取式。单合取式。q设设A Ai i是含是含n n个文字简单析取式，若个文字简单析取式，若A Ai i中既含某个命题变项中既含某个命题变项p pj j，又含它否定式又含它否定式p pj j，即即p pj jp pj j，则，则A Ai i为重言式。为重言式。q反之，若反之，若A Ai i为重言式，则它必同时含某个命题变项和它否定为重言式，则它必同时含某个命题变项和它否定式，不然，若将式，不然，若将A Ai i中不带否定符号命题变项都取中不带否定符号命题变项都取0
21、0值，带否值，带否定号命题变项都取定号命题变项都取1 1值，此赋值为值，此赋值为A Ai i成假赋值，这与成假赋值，这与A Ai i是重是重言式相矛盾。言式相矛盾。q类似讨论可知，若类似讨论可知，若A Ai i是含是含n n个命题变项简单合取式，且个命题变项简单合取式，且A Ai i为为矛盾式，则矛盾式，则A Ai i中必同时含某个命题变项及它否定式，反之亦中必同时含某个命题变项及它否定式，反之亦然。然。2.2 2.2 析取范式和合取范式析取范式和合取范式24/60定理定理2.12.1(1)(1)一个简单析取式是重言式当且仅当它同时含有某个命题一个简单析取式是重言式当且仅当它同时含有某个命题变
22、项及它否定式。变项及它否定式。(2)(2)一个简单合取式是矛盾式当且仅当它同时含有某个命题一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及它否定式。变项及它否定式。定义定义2.32.3 (1)(1)由有限个简单合取式组成析取式称为由有限个简单合取式组成析取式称为析取范式析取范式（disjunctive normal form）。(2)(2)由有限个简单析取式组成合取式称为由有限个简单析取式组成合取式称为合取范式合取范式（conjunctive normal form）。(3)(3)析取范式与合取范式统称为析取范式与合取范式统称为范式范式。2.2 2.2 析取范式和合取范式析取范式和合取范
23、式25/60q设设A Ai i(i=1,2,s)(i=1,2,s)为简单合取式，则为简单合取式，则A=AA=A1 1AA2 2AAs s为析取为析取范式。比如，范式。比如，A A1 1=pq=pq，A A2 2=qr=qr，A A3 3=p=p，则由则由A A1 1,A,A2 2,A,A3 3结构析取范式为结构析取范式为A=AA=A1 1AA2 2AA3 3=(pq)(qr)p=(pq)(qr)p q设设A Ai i(i=1,2,s)(i=1,2,s)为简单析取式，则为简单析取式，则A=AA=A1 1AA2 2AAs s为合取为合取范式。比如，取范式。比如，取A A1 1=pqr=pqr，A
24、A2 2=pq=pq，A A3 3=r=r，则由则由A A1 1,A,A2 2,A,A3 3组成合取范式为组成合取范式为A=AA=A1 1AA2 2AA3 3=(pqr)(pq)r=(pqr)(pq)r说明说明q形如形如pqrpqr公式既是一个简单合取式组成析取范式，公式既是一个简单合取式组成析取范式，又是由三个简单析取式组成合取范式。又是由三个简单析取式组成合取范式。q形如形如pqrpqr公式既是含三个简单合取式析取范式，公式既是含三个简单合取式析取范式，又是含一个简单析取式合取范式。又是含一个简单析取式合取范式。2.2 2.2 析取范式和合取范式析取范式和合取范式26/60定理定理2.22
25、.2(1)(1)一个析取范式是矛盾式当且仅当它每个简单合取式都是矛一个析取范式是矛盾式当且仅当它每个简单合取式都是矛盾式。盾式。(2)(2)一个合取范式是重言式当且仅当它每个简单析取式都是重一个合取范式是重言式当且仅当它每个简单析取式都是重言式。言式。说明说明q研究范式目标在于，将给定公式化成与之等值析取范式研究范式目标在于，将给定公式化成与之等值析取范式或合取范式，进而将公式化成与之等值主析取范式或主或合取范式，进而将公式化成与之等值主析取范式或主合取范式。合取范式。析取范式和合取范式性质析取范式和合取范式性质27/60q在范式中不会出现联结词在范式中不会出现联结词与与，不然可使用等值式消除
26、不然可使用等值式消除AB AB AB ABA AB B (AB)(AB)(AB)(AB)q在范式中不会出现形如在范式中不会出现形如A,(AB),(AB)A,(AB),(AB)公式：公式：A A A A(AB)AB)AB AB(AB)AB)ABABq在析取范式中不会出现形如在析取范式中不会出现形如A(BC)A(BC)公式：公式：A(BC)A(BC)(AB)(AC)(AB)(AC)q在合取范式中不出现形在合取范式中不出现形A(BC)A(BC)公式：公式：A(BC)A(BC)(AB)(AC)(AB)(AC)q定理定理2.32.3 任一命题公式都存在着与之等值析取范式与合取范式。任一命题公式都存在着与
27、之等值析取范式与合取范式。范式存在讨论范式存在讨论28/60(1(1)消去联结词消去联结词、(若存在若存在)。AB AB AB ABA AB B (AB)(AB)(AB)(AB)(2)(2)否定号消去否定号消去(利用双重否定律利用双重否定律)或内移或内移(利用德摩根律利用德摩根律)。A A A A(AB)AB)AB AB(AB)AB)ABAB(3)(3)利用分配律：利用利用分配律：利用对对分配律求析取范式，分配律求析取范式，对对分配律求合取范式。分配律求合取范式。A(BC)A(BC)(AB)(AC)(AB)(AC)A(BC)A(BC)(AB)(AC)(AB)(AC)给定公式范式步骤给定公式范式
28、步骤29/60例题例题2.72.7 求下面公式析取范式与合取范式：求下面公式析取范式与合取范式：(pq)pq)r r (1)(1)求合取范式求合取范式 (p pq)q)r r (pq)(pq)r r （消去消去）(pq)pq)r)(rr)(r(pq)(pq)（消去消去）(pq)r)(rpq)pq)r)(rpq)（消去消去）(pq)pq)rr)(pqr)(pqr)（否定号内移）否定号内移）(pr)(qr)(pqr)pr)(qr)(pqr)（对对分配律）分配律）解答解答例题例题30/60例题例题例题例题(2)(2)求析取范式求析取范式 (pq)pq)r r (pq)pq)r)r)(p(pq qr)
29、r)(pqp)(pqq)(pqr)pqp)(pqq)(pqr)(rp)(rq)(rr)(rp)(rq)(rr)(pqr)(pr)(qr)pqr)(pr)(qr)说明说明q由此例可知由此例可知，命题公式析取范式不唯一。命题公式析取范式不唯一。q一样一样，合取范式也是不唯一。合取范式也是不唯一。31/60q定义定义2.42.4 在含有在含有n n个命题变项简单合取式（简单析取式）中，个命题变项简单合取式（简单析取式）中，若每个命题变项和它否定式不一样时出现，而二者之一必若每个命题变项和它否定式不一样时出现，而二者之一必出现且仅出现一次，且第出现且仅出现一次，且第i i个命题变项或它否定式出现在从个
30、命题变项或它否定式出现在从左算起第左算起第i i位上（若命题变项无角标，就按字典次序排列），位上（若命题变项无角标，就按字典次序排列），称这么简单合取式（简单析取式）为称这么简单合取式（简单析取式）为极小项极小项（极大项极大项）。qn n个命题变项共可产生个命题变项共可产生2 2n n个不一样极小项。其中每个极小项个不一样极小项。其中每个极小项都有且仅有一个成真赋值。若成真赋值所对应二进制数转都有且仅有一个成真赋值。若成真赋值所对应二进制数转换为十进制数换为十进制数i i，就将所对应极小项记作就将所对应极小项记作m mi i。q类似地，类似地，n n个命题变项共可产生个命题变项共可产生2 2n
31、 n个极大项，每个极大项只个极大项，每个极大项只有一个成假赋值，将其对应十进制数有一个成假赋值，将其对应十进制数i i做极大项角标，记作做极大项角标，记作M Mi i。范式规范化形式范式规范化形式32/60表表2.3 p,q2.3 p,q形成极小项与极大项形成极小项与极大项33/60表表2.4 p,q,r2.4 p,q,r形成极小项与极大项形成极小项与极大项34/60范式规范化形式范式规范化形式定理定理2.42.4 设设m mi i与与M Mi i是命题变项是命题变项p p1 1,p,p2 2,p,pn n形成极形成极小项和极大项，则小项和极大项，则 m mi i M Mi i，M Mi i
32、m mi i 定义定义2.52.5 设由设由n n个命题变项组成析取范式（合取范式）个命题变项组成析取范式（合取范式）中全部简单合取式（简单析取式）都是极小项中全部简单合取式（简单析取式）都是极小项（极大项），则称该析取范式（合取范式）（极大项），则称该析取范式（合取范式）为主为主析取范式析取范式（主合取范式主合取范式）。定理定理2.52.5 任何命题公式都存在着与之等值主析取范任何命题公式都存在着与之等值主析取范式和主合取范式，而且是唯一。式和主合取范式，而且是唯一。35/60定理定理2.52.5证实证实(只证主析取范式存在和唯一性只证主析取范式存在和唯一性)(1)(1)证实存在性。证实存在
33、性。设设A A是任一含是任一含n n个命题变项公式。个命题变项公式。由定理由定理2.32.3可知，存在与可知，存在与A A等值析取范式等值析取范式A A，即即A AA A，若若A A某某个简单合取式个简单合取式A Ai i中既不含命题变项中既不含命题变项p pj j，也不含它否定式也不含它否定式p pj j，则则将将A Ai i展成以下形式：展成以下形式：A Ai i A Ai i1 1 A Ai i(p(pj jppj j)(A(Ai ippj j)(A)(Aj jppj j)继续这个过程，直到全部简单合取式都含任意命题变项或它否定继续这个过程，直到全部简单合取式都含任意命题变项或它否定式。
34、式。若在演算过程中出现重复命题变项以及极小项和矛盾式时，都应若在演算过程中出现重复命题变项以及极小项和矛盾式时，都应“消去消去”：如用：如用p p代替代替pppp，m mi i代替代替m mi immi i，0 0代替矛盾式等。最代替矛盾式等。最终就将终就将A A化成与之等值主析取范式化成与之等值主析取范式AA。36/60定理定理2.52.5(2)(2)证实唯一性。证实唯一性。假设某一命题公式假设某一命题公式A A存在两个与之等值主析取范式存在两个与之等值主析取范式B B和和C C，即即A AB B且且A AC C，则则B BC C。因为因为B B和和C C是不一样主析取范式，不妨设极小项是不
35、一样主析取范式，不妨设极小项m mi i只出现在只出现在B B中而不出现在中而不出现在C C中。中。于是，角标于是，角标i i二进制表示为二进制表示为B B成真赋值，而为成真赋值，而为C C成假赋值。这成假赋值。这与与B BC C矛盾，因而矛盾，因而B B与与C C必相同。必相同。37/60求公式求公式A A主析取范式方法与步骤主析取范式方法与步骤方法一、等值演算法方法一、等值演算法(1)(1)化归为析取范式。化归为析取范式。(2)(2)除去析取范式中全部永假析取项。除去析取范式中全部永假析取项。(3)(3)将析取式中重复出现合取项和相同变元合并。将析取式中重复出现合取项和相同变元合并。(4)
36、(4)对合取项补入没有出现命题变元，即添加如对合取项补入没有出现命题变元，即添加如(pp)pp)式，式，然后应用分配律展开公式。然后应用分配律展开公式。方法二、真值表法方法二、真值表法(1)(1)写出写出A A真值表。真值表。(2)(2)找出找出A A成真赋值。成真赋值。(3)(3)求出每个成真赋值对应极小项（用名称表示），按角标从求出每个成真赋值对应极小项（用名称表示），按角标从小到大次序析取。小到大次序析取。38/60求公式求公式求公式求公式A A A A主合取范式方法与步骤主合取范式方法与步骤主合取范式方法与步骤主合取范式方法与步骤方法一、等值演算法方法一、等值演算法(1)(1)化归为合
37、取范式。化归为合取范式。(2)(2)除去合取范式中全部永真合取项。除去合取范式中全部永真合取项。(3)(3)将合取式中重复出现析取项和相同变元合并。将合取式中重复出现析取项和相同变元合并。(4)(4)对析取项补入没有出现命题变元，即添加如对析取项补入没有出现命题变元，即添加如(pp)pp)式，式，然后应用分配律展开公式。然后应用分配律展开公式。方法二、真值表法方法二、真值表法(1)(1)写出写出A A真值表。真值表。(2)(2)找出找出A A成假赋值。成假赋值。(3)(3)求出每个成假赋值对应极大项（用名称表示），按角标从求出每个成假赋值对应极大项（用名称表示），按角标从小到大次序析取。小到大
38、次序析取。39/60例题例题例题例题例例2.92.9 求命题公式求命题公式 pq pq 主析取范式和主合取范式。主析取范式和主合取范式。(1)(1)求主合取范式求主合取范式pq pq pq pq M M2 2(2)(2)求析取范式求析取范式pq pq pqpq （pp（qqqq）（(pppp)q)q）(pq)(pq)(pq)(pq)pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)(pq)m m0 0mm1 1mm3 3 解答解答pqp q0 0101110011140/60例例2.8 2.8 求例求例2.72.7中公式主析取范式和主合取范式。中公式主析取范式和主合取范式。
39、(1)(1)求主析取范式求主析取范式(pq)pq)r r (pqr)(pr)(qr)pqr)(pr)(qr)pqr pqr m m4 4pr pr pp（qqqq）r r (pqr)(pqr)pqr)(pqr)m m1 1mm3 3 qr qr (pp)qr (pp)qr (pqr)(pqr)pqr)(pqr)m m3 3mm7 7 (pq)pq)r r m m1 1mm3 3mm4 4mm7 741/60例例例例2.8 2.8 2.8 2.8 求例求例求例求例2.72.72.72.7中公式主析取范式和主合取范式。中公式主析取范式和主合取范式。中公式主析取范式和主合取范式。中公式主析取范式和主
40、合取范式。(2)(2)求主合取范式求主合取范式(pq)pq)r r (pr)(qr)(pqr)(pr)(qr)(pqr)pqr pqr M M5 5 pr pr p(qq)r p(qq)r (pqr)(pqr)pqr)(pqr)M M0 0MM2 2 qrqr(pp)qr (pp)qr (pqr)(pqr)pqr)(pqr)M M2 2MM6 6 (pq)pq)r r M M0 0MM2 2MM5 5MM6 6 42/60主析取范式用途主析取范式用途 q求公式成真赋值与成假赋值求公式成真赋值与成假赋值q判断公式类型判断公式类型 q判断两个命题公式是否等值判断两个命题公式是否等值 q应用主析取范
41、式分析和处理实际问题应用主析取范式分析和处理实际问题 43/60求公式成真赋值与成假赋值求公式成真赋值与成假赋值q若公式若公式A A中含中含n n个命题变项，个命题变项，A A主析取范式含主析取范式含s(0s2s(0s2n n)个极个极小项，则小项，则A A有有s s个成真赋值，它们是所含极小项角标二进制个成真赋值，它们是所含极小项角标二进制表示，其余表示，其余2 2n n-s-s个赋值都是成假赋值。个赋值都是成假赋值。q在例在例2.82.8中，中，(pq)pq)r r m m1 1mm3 3mm4 4mm7 7,各极小项均含三各极小项均含三个文字，因而各极小项角标均为长为个文字，因而各极小项
42、角标均为长为3 3二进制数，它们分别二进制数，它们分别是是001001，011011，100100，111111，这四个赋值为该公式成真赋值，这四个赋值为该公式成真赋值,其其余为成假赋值。余为成假赋值。q在例在例2.92.9中，中，pq pq m m0 0mm1 1mm3 3，这三个极小项均含两个这三个极小项均含两个文字，它们角标二进制表示文字，它们角标二进制表示0000，0101，1111为该公式成真赋值，为该公式成真赋值，1010是它成假赋值。是它成假赋值。44/60判断公式类型判断公式类型设公式设公式A A中含中含n n个命题变项，轻易看出：个命题变项，轻易看出：qA A为为重言式重言式
43、当且仅当当且仅当A A主析取范式含全部主析取范式含全部2 2n n个极个极小项。小项。qA A为为矛盾式矛盾式当且仅当当且仅当A A主析取范式不含任何极小主析取范式不含任何极小项。此时，记项。此时，记A A主析取范式为主析取范式为0 0。qA A为为可满足式可满足式当且仅当当且仅当A A主析取范式最少含一个主析取范式最少含一个极小项。极小项。45/60判断公式类型判断公式类型例例2.102.10 用公式主析取范式判断公式类型：用公式主析取范式判断公式类型：(1)(1)(pq)q pq)q(2)(2)p(pq)p(pq)(3)(3)(pq)rpq)r解答解答(1)(1)(pq)q pq)q （p
44、qpq）q q (pq)q(pq)q 0 0(2)p(pq)(2)p(pq)m m0 0mm1 1mm2 2mm3 3 (3)(3)(pq)r pq)r m m0 0mm1 1mm3 3mm5 5mm7 7 矛盾式矛盾式重言式重言式可满足式可满足式46/60判断两个命题公式是否等值判断两个命题公式是否等值q设公式设公式A,BA,B共含有共含有n n个命题变项，按个命题变项，按n n个命题变项求出个命题变项求出A A与与B B主主析取范式析取范式AA与与BB。若若AAB,B,则则A AB B；不然，不然，A A与与B B不等不等值。值。例例2.112.11 判断下面两组公式是否等值：判断下面两组
45、公式是否等值：(1)(1)p p与与(pq)(pq)pq)(pq)(2)(2)(pq)rpq)r与与(q)r q)r(1)(1)p p p(qq)p(qq)(pq)(pq)(pq)(pq)m m2 2mm3 3 (pq)(pq)pq)(pq)m m2 2mm3 3 两公式等值。两公式等值。(2)(2)(pq)r pq)r m m1 1mm3 3mm4 4mm5 5mm7 7 (q)r q)r m m0 0mm1 1mm2 2mm3 3mm4 4mm5 5mm7 7 两公式不等值。两公式不等值。解答解答47/60应用主析取范式分析和处理实际问题应用主析取范式分析和处理实际问题例例2.122.12
46、某科研所要从某科研所要从3 3名科研骨干名科研骨干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能够去。能够去。问应怎样选派他们去？问应怎样选派他们去？分析：分析：(1)(1)将简单命题符号化将简单命题符号化(2)(2)写出各复合命题写出各复合命题(3)(3)写出由写出由(2)(2)中复合命题组成合取式（前提）中复合命题组成合取式（前提）(4
47、)(4)将将(3)(3)中公式化成析取式（最好是主析取范式）中公式化成析取式（最好是主析取范式）(5)(5)这么每个小项就是一个可能产生结果。这么每个小项就是一个可能产生结果。去掉不符合题意小项，即得结论。去掉不符合题意小项，即得结论。48/60应用主析取范式分析和处理实际问题应用主析取范式分析和处理实际问题设设 p:p:派派A A去，去，q:q:派派B B去，去，r:r:派派C C去去 由已知条件可得公式由已知条件可得公式 (pr)(qr)(r(pq)pr)(qr)(r(pq)经过演算可得经过演算可得 (pr)(qr)(r(pq)pr)(qr)(r(pq)m m1 1mm2 2mm5 5 因
48、为因为 m m1 1=pqr,m=pqr,m2 2=pqr,m=pqr,m5 5=pqr=pqr可知，选派方案有可知，选派方案有3 3种：种：(a)Ca)C去，而去，而A,BA,B都不去。都不去。(b)Bb)B去，而去，而A,CA,C都不去。都不去。(c)A,Cc)A,C去，而去，而B B不去。不去。解答解答49/60由公式主析取范式求主合取范式由公式主析取范式求主合取范式 设公式设公式A A含含n n个命题变项。个命题变项。A A主析取范式含主析取范式含s(0s2s(0s2n n)个极小项，即个极小项，即没有出现极小项设为没有出现极小项设为它们角标二进制表示为它们角标二进制表示为A A成真赋
49、值，因而成真赋值，因而A A主析取范式主析取范式为为50/60例题例题例例2.132.13 由公式主析取范式，求主合取范式：由公式主析取范式，求主合取范式：(1)(1)A A m m1 1mm2 2(A(A中含两个命题变项中含两个命题变项p,q)p,q)(2)B(2)B m m1 1mm2 2mm3 3(B(B中含两个命题变项中含两个命题变项p,q,r)p,q,r)解答解答(1)(1)A A M M0 0MM3 3 (2)B(2)B M M0 0MM4 4MM5 5MM6 6MM7 7 51/60重言式与矛盾式主合取范式重言式与矛盾式主合取范式设设n n为公式中命题变项个数为公式中命题变项个数
50、q矛盾式无成真赋值，因而矛盾式主合取范式含矛盾式无成真赋值，因而矛盾式主合取范式含2 2n n个极大项。个极大项。q重言式无成假赋值，因而主合取范式不含任何极大项。重言式无成假赋值，因而主合取范式不含任何极大项。q将重言式主合取范式记为将重言式主合取范式记为1 1。q可满足式主合取范式中极大项个数一定小于可满足式主合取范式中极大项个数一定小于2 2n n。52/60真值表与范式关系真值表与范式关系 qA AB B当且仅当当且仅当A A与与B B有相同真值表，又当且仅当有相同真值表，又当且仅当A A与与B B有相有相同主析取范式（主合取范式）。同主析取范式（主合取范式）。q真值表与主析取范式（主
