命题逻辑等值演算优秀课件.ppt

《命题逻辑等值演算优秀课件.ppt》由会员分享，可在线阅读，更多相关《命题逻辑等值演算优秀课件.ppt（53页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、命题逻辑等值演算命题逻辑等值演算第1页，本讲稿共53页q两公式什么时候代表了同一个命题呢？两公式什么时候代表了同一个命题呢？q抽象地看，两个公式在任何相同的赋值下有相同的真假时抽象地看，两个公式在任何相同的赋值下有相同的真假时即代表了相同的命题。即代表了相同的命题。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

2、.1 2.1 等值式等值式第2页，本讲稿共53页1 1 1 1、等值的定义及说明、等值的定义及说明定义定义2.12.1 设设A,BA,B是两个命题公式，若是两个命题公式，若A,BA,B构成的等价式构成的等价式A AB B为为重言式重言式,则称则称A A与与B B是是等值等值的的,记作记作A AB B。说明说明q注意注意与与的区别。的区别。qA A或或B B中可能有哑元出现。中可能有哑元出现。pq pq (pq)(pq)(rr)rr)r r为左边公式中的哑元。为左边公式中的哑元。q用真值表可以验证两个公式是否等值。用真值表可以验证两个公式是否等值。第3页，本讲稿共53页例例2.1 2.1 判断下

3、面两个公式是否等值判断下面两个公式是否等值(pq)pq)与与 pqpq 解答说明说明q在用真值表法判断在用真值表法判断A AB B是否为重言式时，真值表是否为重言式时，真值表的最后一列可以省略的最后一列可以省略。等值等值第4页，本讲稿共53页例题例题2.22.2 判断下列各组公式是否等值判断下列各组公式是否等值(1)p(qr)(1)p(qr)与与(pq)r pq)r(2)(2)(pq)rpq)r与与(pq)rpq)r 解答等值等值不等值不等值第5页，本讲稿共53页2 2、基本等值式、基本等值式、基本等值式、基本等值式1.1.双重否定律双重否定律A A A A2.2.幂等律幂等律A A AA,A

4、A,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)(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 第6页，本讲稿共53页 8.8.零律零律A1 A1 1,A0 1,A0 0 0

5、 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)(BA)14.14.假言易位假言易位AB AB BA BA15.15.等价否定等值式等价否定等值式 A AB B A ABB16.16.归谬论归谬论(AB)(AB)AB)(AB)A A 第7页，本讲稿共53页3 3 3 3、对偶原理、对偶原理一个逻辑等值式，如果只含有一个逻辑等值式，如果只含有、0 0、1 1那么同时那么同时

6、把把和和互换互换把把0 0和和1 1互换互换得到的还是等值式。得到的还是等值式。第8页，本讲稿共53页4 4、等值演算与置换规则、等值演算与置换规则q各等值式都是用元语言符号书写的，其中各等值式都是用元语言符号书写的，其中A,B,CA,B,C可以代表任意可以代表任意的公式，称这样的等值式为的公式，称这样的等值式为等值式模式等值式模式。q每个等值式模式都给出了无穷多个同类型的具体的等值式。每个等值式模式都给出了无穷多个同类型的具体的等值式。例如，在蕴涵等值式例如，在蕴涵等值式 ABABAB AB 中，中，取取A=pA=p，B=qB=q时，得等值式时，得等值式 pqpqpq pq 取取A=pqrA

7、=pqr，B=pqB=pq时，得等值式时，得等值式(pqr)(pq)pqr)(pq)(pqr)(pq)(pqr)(pq)q这些具体的等值式都被称为原来的等值式模式的这些具体的等值式都被称为原来的等值式模式的代入实例代入实例。q由已知的等值式推演出另外一些等值式的过程为由已知的等值式推演出另外一些等值式的过程为等值演算等值演算。q置换规则置换规则 设设(A)(A)是含公式是含公式A A的命题公式，的命题公式，(B)(B)是用公式是用公式B B置置换了换了(A)(A)中所有的中所有的A A后得到的命题公式，若后得到的命题公式，若B BA A，则，则(B)(B)(A)(A)。第9页，本讲稿共53页关

8、于等值演算的说明关于等值演算的说明q等值演算的基础等值演算的基础等值关系的性质：等值关系的性质：自反性：自反性：A AA A。对称性：若对称性：若A AB B，则，则B BA A。传递性：若传递性：若A AB B且且B BC C，则，则A AC C。基本的等值式基本的等值式置换规则置换规则q等值演算的应用等值演算的应用证明两个公式等值证明两个公式等值判断公式类型判断公式类型解判定问题解判定问题第10页，本讲稿共53页等值演算的应用举例等值演算的应用举例证明两个公式等值证明两个公式等值(pq)r pq)r (pr)(qr)pr)(qr)(pqpq)r)r (pq)(pq)rr（蕴含等值式、置换规

9、则）蕴含等值式、置换规则）(pq)pq)rr（蕴含等值式、置换规则）蕴含等值式、置换规则）(pq)pq)rr（德摩根律、置换规则）德摩根律、置换规则）(pr)(qr)pr)(qr)（分配律、置换规则）分配律、置换规则）说明说明q也可以从右边开始演算也可以从右边开始演算q因为每一步都用置换规则，故可不写出因为每一步都用置换规则，故可不写出q熟练后，基本等值式也可以不写出熟练后，基本等值式也可以不写出q通常不用等值演算直接证明两个公式不等值通常不用等值演算直接证明两个公式不等值解答第11页，本讲稿共53页例例2.32.3 用等值演算法验证等值式用等值演算法验证等值式(pq)r(pq)r (pr)(

10、qr)(pr)(qr)(p(pr)(qr)(qr)r)(p(prr)(q)(qrr)(蕴含等值式蕴含等值式)(pqpq)r)r(分配律分配律)(pq)r(pq)r(德摩根律德摩根律)(pq)r(pq)r(蕴含等值式蕴含等值式)解答第12页，本讲稿共53页例题例题2.2.4 4 用等值演算判断下列公式的类型：用等值演算判断下列公式的类型：（1 1）(p(pq)r(p(pq)r（2 2）p(pq)p)q)p(pq)p)q)（3 3）(pq)pq(pq)pq(1)(p(1)(p(pq)r(pq)r (ppq)r(ppq)r (ppppq)rq)r 00r r0 0故原公式为矛盾式故原公式为矛盾式(2

11、)p(pq)p)2)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 p故原公式为非重言式的可满足式故原公式为非重言式的可满足式解：第13页，本讲稿共53页(3)(3)(p(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

12、)q q （排中律）排中律）(qqqq)p)p（同一律）同一律）11p p（排中律）排中律）1 1 （零零 律律）公式为重言式公式为重言式第14页，本讲稿共53页定义定义1 1 命题变项及其否定统称作命题变项及其否定统称作文字文字。仅由有限个文字构成的析取式称作仅由有限个文字构成的析取式称作简单析取式简单析取式。仅由有限个文字构成的合取式称作仅由有限个文字构成的合取式称作简单合取式简单合取式。q简单析取式举例：简单析取式举例：p,qp,qpppp，pq pq pqr,pqrpqr,pqrq简单合取式举例：简单合取式举例：p,qp,qpppp，pqpqpqr,ppqpqr,ppq2.2 2.2

13、2.2 2.2 析取范式和合取范式析取范式和合取范式析取范式和合取范式析取范式和合取范式 1 1、简单析取式与简单合取式、简单析取式与简单合取式第15页，本讲稿共53页q一个文字既是简单析取式，又是简单合取式。一个文字既是简单析取式，又是简单合取式。q为讨论方便，有时用为讨论方便，有时用A A1 1,A,A2 2,A,As s表示表示s s个简单析取式或个简单析取式或s s个简单合取式。个简单合取式。q定理定理1 1 (1)(1)一个简单析取式是重言式当且仅当它同时含有某个命一个简单析取式是重言式当且仅当它同时含有某个命题变项及它的否定式。题变项及它的否定式。(2)(2)一个简单合取式是矛盾式

14、当且仅当它同时含有某个命一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及它的否定式。题变项及它的否定式。第16页，本讲稿共53页定义定义2 2(1)(1)由有限个简单合取式构成的析取式称为由有限个简单合取式构成的析取式称为析取范式析取范式。(2)(2)由有限个简单析取式构成的合取式称为由有限个简单析取式构成的合取式称为合取范式合取范式。(3)(3)析取范式与合取范式统称为析取范式与合取范式统称为范式范式。2 2 2 2、析取范式与合取范式、析取范式与合取范式q设设A Ai i(i=1,2,(i=1,2,s),s)为简单合取式，则为简单合取式，则A=AA=A1 1AA2 2AAs s为析为

15、析取范式。例如，取范式。例如，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,(i=1,2,s),s)为简单析取式，则为简单析取式，则A=AA=A1 1AA2 2AAs s为合为合取范式。例如，取取范式。例如，取A A1 1=pqr=pqr，A A2 2=pq=pq，A A3 3=r=r，则由，则由A A1 1,A,A2 2,A,A3 3组成的合取范式为组成的合取范式为A=AA

16、=A1 1AA2 2AA3 3=(pqr)(pq)r=(pqr)(pq)r第17页，本讲稿共53页q定理定理2 2 (1)(1)一个析取范式是矛盾式当且仅当它的每个简单合取式都是一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。矛盾式。(2)(2)一个合取范式是重言式当且仅当它的每个简单析取式都是一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。重言式。q定理定理3 3 任一命题公式都存在着与之等值的析取范式与合取范式。任一命题公式都存在着与之等值的析取范式与合取范式。3 3、析取范式和合取范式的性质、析取范式和合取范式的性质说明说明q研究范式的目的在于，将给定公式化成与之等值

17、的析取研究范式的目的在于，将给定公式化成与之等值的析取范式或合取范式，进而将公式化成与之等值的主析取范范式或合取范式，进而将公式化成与之等值的主析取范式或主合取范式。式或主合取范式。第18页，本讲稿共53页4 4、求给定公式范式的步骤、求给定公式范式的步骤(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)利用分配律：利用利用分配律：利用对对的分配律

18、求析取范式，的分配律求析取范式，对对的分配律求合取范式。的分配律求合取范式。A(BC)A(BC)(AB)(AC)(AB)(AC)A(BC)A(BC)(AB)(AC)(AB)(AC)第19页，本讲稿共53页例题例题1 1 求下面公式的析取范式与合取范式：求下面公式的析取范式与合取范式：(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)(pq

19、r)pr)(qr)(pqr)（对对分配律）分配律）解答第20页，本讲稿共53页(2)(2)求析取范式求析取范式 (pq)pq)r r (pq)pq)r)r)(p(pq qr)r)(pqp)(pqq)(pqr)pqp)(pqq)(pqr)(rp)(rq)(rr)(rp)(rq)(rr)(pqr)(pr)(qr)pqr)(pr)(qr)说明说明q由此例可知由此例可知，命题公式的析取范式不唯一。命题公式的析取范式不唯一。q同样同样，合取范式也是不唯一的。合取范式也是不唯一的。第21页，本讲稿共53页5 5、范式的规范化形式、范式的规范化形式、范式的规范化形式、范式的规范化形式q定义定义3 3 在含有

20、在含有n n个命题变项的简单合取式（简单析取式）中，个命题变项的简单合取式（简单析取式）中，若每个命题变项和它的否定式不同时出现，而二者之一必若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第出现且仅出现一次，且第i i个命题变项或它的否定式出现在个命题变项或它的否定式出现在从左算起的第从左算起的第i i位上（若命题变项无角标，就按字典顺序排位上（若命题变项无角标，就按字典顺序排列），称这样的简单合取式（简单析取式）为列），称这样的简单合取式（简单析取式）为极小项极小项（极极大项大项）。）。qn n个命题变项共可产生个命题变项共可产生2 2n n个不同的极小项。其中每个极

21、小项个不同的极小项。其中每个极小项都有且仅有一个成真赋值。若成真赋值所对应的二进制数都有且仅有一个成真赋值。若成真赋值所对应的二进制数转换为十进制数转换为十进制数i i，就将所对应极小项记作，就将所对应极小项记作mi 。q类似地，类似地，n n个命题变项共可产生个命题变项共可产生2 2n n个极大项，每个极大项只个极大项，每个极大项只有一个成假赋值，将其对应的十进制数有一个成假赋值，将其对应的十进制数i i做极大项的角标，做极大项的角标，记作记作Mi。第22页，本讲稿共53页表表1 1 p,q形成的极小项与极大项形成的极小项与极大项 P QPQPQPQPQ0 00 11 01 1 0 0 0

22、1 0 0 1 0 0 1 0 0 1 0 0 0P QPQPQPQPQ0 00 11 01 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0第23页，本讲稿共53页表表2 2 p,q,r形成的极小项与极大项形成的极小项与极大项 第24页，本讲稿共53页定理定理4 4 设设mi与与Mi是命题变项是命题变项p1,p2,pn形成的极小项和极大形成的极小项和极大项，则项，则 miMi，Mimi 定义定义4 4 设由设由n n个命题变项构成的析取范式（合取范式）中所有个命题变项构成的析取范式（合取范式）中所有的简单合取式（简单析取式）都是极小项（极大项），则的简单合取式（简单析取式）

23、都是极小项（极大项），则称该析取范式（合取范式）称该析取范式（合取范式）为主析取范式为主析取范式（主合取范式主合取范式）.定理定理5 5 任何命题公式都存在着与之等值的主析取范式和主合任何命题公式都存在着与之等值的主析取范式和主合取范式，并且是唯一的。取范式，并且是唯一的。第25页，本讲稿共53页定理定理5 5的证明的证明(1)(1)证明存在性。证明存在性。设设A A是任一含是任一含n n个命题变项的公式。个命题变项的公式。由定理由定理2.32.3可知，存在与可知，存在与A A等值的析取范式等值的析取范式A A，即，即A AA A，若，若A A的某个简单合取式的某个简单合取式A Ai i中既不

24、含命题变项中既不含命题变项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)继续这个过程，直到所有的简单合取式都含任意命题变项或它的继续这个过程，直到所有的简单合取式都含任意命题变项或它的否定式。否定式。若在演算过程中出现重复的命题变项以及极小项和矛盾式时，都若在演算过程中出现重复的命题变项以及极小项和矛盾式时，都应应“消去消去”：如用：如用p p代替代替pppp，m mi i代替代替m mi immi i，

25、0 0代替矛盾式等。代替矛盾式等。最后就将最后就将A A化成与之等值的主析取范式化成与之等值的主析取范式AA。第26页，本讲稿共53页(2)(2)证明唯一性。证明唯一性。假设某一命题公式假设某一命题公式A A存在两个与之等值的主析取范式存在两个与之等值的主析取范式B B和和C C，即即A AB B且且A AC C，则，则B BC C。由于由于B B和和C C是不同的主析取范式，不妨设极小项是不同的主析取范式，不妨设极小项m mi i只出现在只出现在B B中而不出现在中而不出现在C C中。中。于是，角标于是，角标i i的二进制表示为的二进制表示为B B的成真赋值，而为的成真赋值，而为C C的成假

26、赋的成假赋值。这与值。这与B BC C矛盾，因而矛盾，因而B B与与C C必相同。必相同。第27页，本讲稿共53页6 6、求公式、求公式、求公式、求公式A A的主析取范式的方法与步骤的主析取范式的方法与步骤方法一、等值演算法方法一、等值演算法(1)(1)化归为析取范式。化归为析取范式。(2)(2)除去析取范式中所有永假的析取项。除去析取范式中所有永假的析取项。(3)(3)将析取式中重复出现的合取项和相同的变元合并。将析取式中重复出现的合取项和相同的变元合并。(4)(4)对合取项补入没有出现的命题变元，即添加如对合取项补入没有出现的命题变元，即添加如(pp)pp)式，式，然后应用分配律展开公式。

27、然后应用分配律展开公式。方法二、真值表法方法二、真值表法(1)(1)写出写出A A的真值表。的真值表。(2)(2)找出找出A A的成真赋值。的成真赋值。(3)(3)求出每个成真赋值对应的极小项（用名称表示），按角标求出每个成真赋值对应的极小项（用名称表示），按角标从小到大顺序析取。从小到大顺序析取。第28页，本讲稿共53页方法一、等值演算法方法一、等值演算法(1)(1)化归为合取范式。化归为合取范式。(2)(2)除去合取范式中所有永真的合取项。除去合取范式中所有永真的合取项。(3)(3)将合取式中重复出现的析取项和相同的变元合并。将合取式中重复出现的析取项和相同的变元合并。(4)(4)对析取项

28、补入没有出现的命题变元，即添加如对析取项补入没有出现的命题变元，即添加如(pp)pp)式，式，然后应用分配律展开公式。然后应用分配律展开公式。方法二、真值表法方法二、真值表法(1)(1)写出写出A A的真值表。的真值表。(2)(2)找出找出A A的成假赋值。的成假赋值。(3)(3)求出每个成假赋值对应的极大项（用名称表示），按角标求出每个成假赋值对应的极大项（用名称表示），按角标从小到大顺序析取。从小到大顺序析取。7 7、求公式、求公式A A的主合取范式的方法与步骤的主合取范式的方法与步骤第29页，本讲稿共53页(1)(1)求主合取范式求主合取范式pq pq pq pq M M2 2(2)(2

29、)求析取范式求析取范式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 01011100111例例2 2 求命题公式求命题公式 pq pq 的主析取范式和主合取范式。的主析取范式和主合取范式。第30页，本讲稿共53页例例3 3 求求 的主析取范式和主合取范式。的主析取范式和主合取范式。解：解：(1)列真值表列真值表(2)成真赋值有010，100，101，110，111(3)成假赋值有000，001，011q主析取范式为主析

30、取范式为q主合取范式为主合取范式为q方法一、真值表法第31页，本讲稿共53页q方法二、等值演算法 主析取范式第32页，本讲稿共53页q方法二、等值演算法 主合取范式第33页，本讲稿共53页q已知一种主范式,求另一种主范式q分析分析:主析取范式中没有出现的极小项有主析取范式中没有出现的极小项有q主合取范式为主合取范式为第34页，本讲稿共53页主析取范式的用途主析取范式的用途 q求公式的成真赋值与成假赋值求公式的成真赋值与成假赋值q判断公式的类型判断公式的类型 q判断两个命题公式是否等值判断两个命题公式是否等值 q应用主析取范式分析和解决实际问题应用主析取范式分析和解决实际问题 第35页，本讲稿共

31、53页求公式的成真赋值与成假赋值求公式的成真赋值与成假赋值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,各极小项均含三各极小项均含三个文字，因而各极小项的角标均为长为个文字，因而各极小项的角标均为长为3 3的二进制数，它们的二进制

32、数，它们分别是分别是001001，011011，100100，111111，这四个赋值为该公式的成真，这四个赋值为该公式的成真赋值赋值,其余的为成假赋值。其余的为成假赋值。q在例在例2.92.9中，中，pq pq m m0 0mm1 1mm3 3，这三个极小项均含两个，这三个极小项均含两个文字，它们的角标的二进制表示文字，它们的角标的二进制表示0000，0101，1111为该公式的成为该公式的成真赋值，真赋值，1010是它的成假赋值。是它的成假赋值。第36页，本讲稿共53页判断公式的类型判断公式的类型设公式设公式A A中含中含n n个命题变项，容易看出：个命题变项，容易看出：qA A为重言式为

33、重言式当且仅当当且仅当A A的主析取范式含全部的主析取范式含全部2 2n n个极小项。个极小项。qA A为为矛盾式矛盾式当且仅当当且仅当A A的主析取范式不含任何极小项。的主析取范式不含任何极小项。此时，记此时，记A A的主析取范式为的主析取范式为0 0。qA A为为可满足式可满足式当且仅当当且仅当A A的主析取范式至少含一个的主析取范式至少含一个极小项。极小项。第37页，本讲稿共53页判断公式的类型判断公式的类型例例2.102.10 用公式的主析取范式判断公式的类型：用公式的主析取范式判断公式的类型：(1)(1)(pq)q pq)q (2)(2)p(pq)p(pq)(3)(3)(pq)rpq

34、)r解答(1)(1)(pq)q pq)q （pqpq）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 矛盾式矛盾式重言式重言式可满足式可满足式第38页，本讲稿共53页判断两个命题公式是否等值判断两个命题公式是否等值q设公式设公式A,BA,B共含有共含有n n个命题变项，按个命题变项，按n n个命题变项求出个命题变项求出A A与与B B的的主析取范式主析取范式A A与与B B。若。若A AB B,则则A AB B；否则，；否则，A A与与B B不

35、不等值。等值。例例2.112.11 判断下面两组公式是否等值：判断下面两组公式是否等值：(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 两公式不等值。两公式不等值。解答第39页，本讲稿共53页

36、应用主析取范式分析和解决实际问题应用主析取范式分析和解决实际问题例例2.122.12某科研所要从某科研所要从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)

37、写出由写出由(2)(2)中复合命题组成的合取式（前提）中复合命题组成的合取式（前提）(4)(4)将将(3)(3)中公式化成析取式（最好是主析取范式）中公式化成析取式（最好是主析取范式）(5)(5)这样每个小项就是一种可能产生的结果。这样每个小项就是一种可能产生的结果。去掉不符合题意的小项，即得结论。去掉不符合题意的小项，即得结论。第40页，本讲稿共53页应用主析取范式分析和解决实际问题应用主析取范式分析和解决实际问题设设 p:p:派派A A去，去，q:q:派派B B去，去，r:r:派派C C去去 由已知条件可得公式由已知条件可得公式 (pr)(qr)(r(pq)pr)(qr)(r(pq)经过演

38、算可得经过演算可得 (pr)(qr)(r(pq)pr)(qr)(r(pq)m m1 1mm2 2mm5 5 由于由于 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不去。不去。解答第41页，本讲稿共53页由公式的主析取范式求主合取范式由公式的主析取范式求主合取范式 设公式设公式A A含含n n个命题变项。个命题变项。A A的主析取范式含的主析取范式含s(0s2s

39、(0s2n n)个极小项，即个极小项，即没有出现的极小项设为没有出现的极小项设为它们的角标的二进制表示为它们的角标的二进制表示为A A的成真赋值，因而的成真赋值，因而A A的主析取范的主析取范式为式为第42页，本讲稿共53页例例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

40、 0MM4 4MM5 5MM6 6MM7 7 第43页，本讲稿共53页重言式与矛盾式的主合取范式重言式与矛盾式的主合取范式设设n n为公式中命题变项个数为公式中命题变项个数q矛盾式无成真赋值，因而矛盾式的主合取范式含矛盾式无成真赋值，因而矛盾式的主合取范式含2 2n n个极大个极大项。项。q重言式无成假赋值，因而主合取范式不含任何极大项。重言式无成假赋值，因而主合取范式不含任何极大项。q将重言式的主合取范式记为将重言式的主合取范式记为1 1。q可满足式的主合取范式中极大项的个数一定小于可满足式的主合取范式中极大项的个数一定小于2 2n n。第44页，本讲稿共53页真值表与范式的关系真值表与范式

41、的关系 qA AB B当且仅当当且仅当A A与与B B有相同的真值表，又当且仅当有相同的真值表，又当且仅当A A与与B B有有相同的主析取范式（主合取范式）。相同的主析取范式（主合取范式）。q真值表与主析取范式（主合取范式）是描述命题公式标真值表与主析取范式（主合取范式）是描述命题公式标准形式的两种不同的等价形式。准形式的两种不同的等价形式。n n个命题变项共可产生个命题变项共可产生2 2n n个极小项（极大项）个极小项（极大项）可以产生的主析取范式（主合取范式）数目为：可以产生的主析取范式（主合取范式）数目为：第45页，本讲稿共53页本章主要内容本章主要内容q等值式与等值演算。等值式与等值演

42、算。q基本的等值式，其中含：双重否定律、幂等律、交换律、基本的等值式，其中含：双重否定律、幂等律、交换律、结合律、分配律、德结合律、分配律、德摩根律、吸收律、零律、同一律、摩根律、吸收律、零律、同一律、排中律、矛盾律、蕴含等值式、等价等值式、假言易位、排中律、矛盾律、蕴含等值式、等价等值式、假言易位、等价否定等值式、归谬论。等价否定等值式、归谬论。q与主析取范式及主合取范式有关的概念：简单合取式、与主析取范式及主合取范式有关的概念：简单合取式、简单析取式、析取范式、合取范式、极小项、极大项、简单析取式、析取范式、合取范式、极小项、极大项、主析取范式、主合取范式。主析取范式、主合取范式。第46页

43、，本讲稿共53页本章学习要求本章学习要求 q深刻理解等值式的概念。深刻理解等值式的概念。q牢记牢记2424个基本等值式，这是等值演算的基础；能熟练地应用个基本等值式，这是等值演算的基础；能熟练地应用它们进行等值演算。它们进行等值演算。q了解简单析取式、简单合取式、析取范式、合取范式的概念。了解简单析取式、简单合取式、析取范式、合取范式的概念。q深刻理解极小项及极大项的定义及它们的名称，及名称下角深刻理解极小项及极大项的定义及它们的名称，及名称下角标与成真赋值的关系。标与成真赋值的关系。q熟练掌握求公式的主析取范式的方法。熟练掌握求公式的主析取范式的方法。q熟练掌握由公式的主析取范式求公式的主合

44、取范式的方法。熟练掌握由公式的主析取范式求公式的主合取范式的方法。q会用公式的主析取范式（主合取范式）求公式的成真赋值、会用公式的主析取范式（主合取范式）求公式的成真赋值、成假赋值。成假赋值。第47页，本讲稿共53页本章典型习题本章典型习题q用等值演算法证明重言式和矛盾式用等值演算法证明重言式和矛盾式q用等值演算法证明等值式用等值演算法证明等值式q求公式的主析取范式和主合取范式求公式的主析取范式和主合取范式q用主范式判断两个公式是否等值用主范式判断两个公式是否等值q求解实际问题求解实际问题第48页，本讲稿共53页求公式求公式(pq)(pr)pq)(pr)的主析取范式和主合取范式。的主析取范式和

45、主合取范式。解答pqr(pq)(pr)00000011010001111000101011011111主析取范式为主析取范式为(ppqr)(qr)(pqr)(pqpqr)(pqr)r)(pqr)pqr)主合取范式为主合取范式为 (pqr)(p(pqr)(pqr)(qr)(pqr)pqr)(pqpqr)r)第49页，本讲稿共53页甲、乙、丙、丁四个人有且只有两个人参加围棋比赛。关于谁甲、乙、丙、丁四个人有且只有两个人参加围棋比赛。关于谁参加比赛，下列四个判断都是正确的：参加比赛，下列四个判断都是正确的：(1)(1)甲和乙只有一人参加比赛。甲和乙只有一人参加比赛。(2)(2)丙参加，丁必参加。丙参

46、加，丁必参加。(3)(3)乙或丁至多参加一人。乙或丁至多参加一人。(4)(4)丁不参加，甲也不会参加。丁不参加，甲也不会参加。请推断出哪两个人参加围棋比赛。请推断出哪两个人参加围棋比赛。设设a a：甲参加了比赛。甲参加了比赛。b b：乙参加了比赛。乙参加了比赛。c c：丙参加了比赛。丙参加了比赛。d d：丁参加了比赛。丁参加了比赛。(1)(1)(aab)(b)(ab)ab)(2)(2)cdcd(3)(3)(bd)bd)(4)(4)d d a a 解答第50页，本讲稿共53页(aab)(b)(ab)ab)()(cdcd)()(bd)(bd)()(d d a a)(aabbcdcd)()(aabdbd)()(ababccd d)根据题意条件，有且仅有两人参赛，根据题意条件，有且仅有两人参赛，故故ababccd d为为0 0，所以，所以(aabbcdcd)()(aabdbd)为为1 1，即甲和丁参加了比赛。即甲和丁参加了比赛。(ab)(cd)ab)(cd)(ac)(bc)(ad)(bd)ac)(bc)(ad)(bd)说明说明第51页，本讲稿共53页本章作业本章作业习题二习题二4 4(3)(3)、7 7、8 8(1)(1)、9 9(2)(2)、2323、2929第52页，本讲稿共53页同学们学习愉快！下次课再见！第53页，本讲稿共53页