02命题逻辑等值演算.ppt

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

1、第第2 2章章 命题逻辑等值演算命题逻辑等值演算离离 散散 数数 学学中国地质大学本科生课程中国地质大学本科生课程本章说明本章说明本章说明本章说明q本章的主要内容本章的主要内容等值式与基本的等值式等值式与基本的等值式等值演算与置换规则等值演算与置换规则析取范式与合取范式、主析取范式与主合取范式析取范式与合取范式、主析取范式与主合取范式联结词完备集联结词完备集(不讲不讲)可满足性问题与消解法（不讲）可满足性问题与消解法（不讲）q本章与后续各章的关系本章与后续各章的关系是第一章的抽象与延伸是第一章的抽象与延伸是后续各章的现行准备是后续各章的现行准备2.1 2.1 2.1 2.1 等值式等值式等值式

2、等值式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

3、.12.1 设设A,BA,B是两个命题公式，若是两个命题公式，若A,BA,B构成的等构成的等价式价式A AB B为重言式为重言式，则称，则称A A与与B B是是等值等值的的，记作，记作A AB B。说说明明q定义中定义中,A,B,A,B,都是都是元语言符号元语言符号。qA A或或B B中可能有哑元出现。中可能有哑元出现。pqpq (pqpq)()(rrrr)r r为左边公式中的哑元。为左边公式中的哑元。q用真值表可以验证两个公式是否等值。用真值表可以验证两个公式是否等值。例题例题例题例题例例2.1 2.1 判断下面两个公式是否等值判断下面两个公式是否等值(pqpq)与与 pqpq 解答解答说说

4、明明q在用真值表法判断在用真值表法判断A AB B是否为重言式时，真值是否为重言式时，真值表的最后一列可以省略表的最后一列可以省略。等值等值例题例题例题例题例题例题2.22.2 判断下列各组公式是否等值判断下列各组公式是否等值(1)p(qr)(1)p(qr)与与(pq)rpq)r (2)(2)(pq)rpq)r与与(pq)rpq)r 解答解答等值等值不等值不等值基本等值式基本等值式基本等值式基本等值式1.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)

5、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 基本等值式基本等值式基本等值式基本等值式 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

6、 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 对偶原理对偶原理对偶原理对偶原理一个逻辑等值式，如果只含有一个逻辑等值式，如果只含有、0 0、1 1那么同时那么同时把把和和互换互换把把0 0和和1 1互换互换得到的还是等值式。得到的还是等值式。等值演算与置换规则等值演算与置换规则等值演算

7、与置换规则等值演算与置换规则q各等值式都是用元语言符号书写的，各等值式都是用元语言符号书写的，其中其中A,B,CA,B,C可以代表任意可以代表任意的公式，称这样的等值式为的公式，称这样的等值式为等值式模式等值式模式。q每个等值式模式都给出了无穷多个同类型的具体的等值式。每个等值式模式都给出了无穷多个同类型的具体的等值式。例如，在蕴涵等值式例如，在蕴涵等值式 ABABAB AB 中，中，取取A=A=p p，B B=q=q时，得等值式时，得等值式 pqpqpqpq 取取A=A=pqrpqr，B B=pqpq时，得等值式时，得等值式(pqr)(pqpqr)(pq)(pqr)(pqpqr)(pq)q这

8、些具体的等值式都被称为原来的等值式模式的这些具体的等值式都被称为原来的等值式模式的代入实例代入实例。q由已知的等值式推演出另外一些等值式的过程为由已知的等值式推演出另外一些等值式的过程为等值演算等值演算。q置换规则置换规则 设设(A)(A)是含公式是含公式A A的命题公式，的命题公式，(B)(B)是用公式是用公式B B置置换了换了(A)(A)中所有的中所有的A A后得到的命题公式，若后得到的命题公式，若B BA A，则则(B)(B)(A)(A)。关于等值演算的说明关于等值演算的说明关于等值演算的说明关于等值演算的说明q等值演算的基础等值演算的基础等值关系的性质：等值关系的性质：自反性：自反性：

9、A AA A。对称性：若对称性：若A AB B，则则B BA A。传递性：若传递性：若A AB B且且B BC C，则则A AC C。基本的等值式基本的等值式置换规则置换规则q等值演算的应用等值演算的应用证明两个公式等值证明两个公式等值判断公式类型判断公式类型解判定问题解判定问题例题例题例题例题利用基本的等价关系，完成如下工作：利用基本的等价关系，完成如下工作：（1 1）判断公式的类型：）判断公式的类型：证明证明 ()()()()()是一个永真公式。是一个永真公式。（2 2）证明公式之间的等价关系：）证明公式之间的等价关系：证明证明()=()=()（3 3）化简公式：）化简公式：证明证明(P(

10、P(R)(R)(R)(PR)=R R)(PR)=R 等值演算的应用举例等值演算的应用举例等值演算的应用举例等值演算的应用举例证明两个公式等值证明两个公式等值(pq)rpq)r (pr)(qrpr)(qr)(pqpq)r)r (pq)pq)rr（蕴含等值式、置换规则）蕴含等值式、置换规则）(pq)pq)rr（蕴含等值式、置换规则）蕴含等值式、置换规则）(pq)pq)rr（德摩根律、置换规则）德摩根律、置换规则）(pr)(qrpr)(qr)（分配律、置换规则）分配律、置换规则）说说明明q也可以从右边开始演算也可以从右边开始演算q因为每一步都用置换规则，故可不写出因为每一步都用置换规则，故可不写出q

11、熟练后，基本等值式也可以不写出熟练后，基本等值式也可以不写出q通常不用等值演算直接证明两个公式不等值通常不用等值演算直接证明两个公式不等值解答解答例题例题例题例题例例2.32.3 用等值演算法验证等值式用等值演算法验证等值式(pq)rpq)r (pr)(qrpr)(qr)(p pr)(qr)(qr r)(p prr)(q)(qrr)(蕴含等值式蕴含等值式)(pqpq)r)r(分配律分配律)(pq)rpq)r(德摩根律德摩根律)(pq)rpq)r(蕴含等值式蕴含等值式)解答解答例题例题例题例题例例2.42.4 证明：证明：(pq)rpq)r 与与 p(qrp(qr)不等值不等值方法一、方法一、真

12、值表法。真值表法。方法二、方法二、观察法。观察法。易知，易知，010010是是(pq)rpq)r的成假赋值，而的成假赋值，而010010是是p(qrp(qr)的成真赋值，所以原不等值式成立。的成真赋值，所以原不等值式成立。方法三、方法三、通过等值演算化成容易观察真值的情况，再进行判断。通过等值演算化成容易观察真值的情况，再进行判断。A=(A=(p pq)rq)r (pq)pq)r r （蕴涵等值式）（蕴涵等值式）(pq)pq)rr （蕴涵等值式）（蕴涵等值式）(pq)rpq)r （德摩根律）（德摩根律）B=B=p p(q(qr r)pp(qrqr)（蕴涵等值式）（蕴涵等值式）pqrpqr （结

13、合律）（结合律）000 000，010010是是A A的成假赋值，而它们是的成假赋值，而它们是B B的成真赋值。的成真赋值。解答解答例题例题例题例题 例题例题2.52.5 用等值演算判断下列公式的类型：用等值演算判断下列公式的类型：（1 1）(pq)pqpq)pq （2 2）(p(pq)rp(pq)r （3 3）p(pq)p)qp(pq)p)q)例例例例2.5 2.5 2.5 2.5 解答解答解答解答(1)(1)(p pq)pqq)pq (pq)ppq)pq q （蕴涵等值式）蕴涵等值式）(pq)p)pq)p)qq （蕴涵等值式）蕴涵等值式）(pq)pq)p)qp)q （德摩根律）德摩根律）(

14、pq)pq)pp)q)q（德摩根律）德摩根律）(pppp)(qp)q)(qp)q （分配律）分配律）(11(q qp)p)q q （排中律）排中律）(qqqq)p)p （同一律）同一律）11p p（排中律）排中律）1 1 （零律）（零律）例例例例2.5 2.5 2.5 2.5 解答解答解答解答(2)(2)(p p(pq)r(pq)r (ppq)rppq)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

15、p p例例例例2.6 2.6 2.6 2.6 应用题应用题应用题应用题在在某某次次研研讨讨会会的的中中间间休休息息时时间间，3 3名名与与会会者者根根据据王王教教授授的的口口音对他是哪个省市的人进行了判断：音对他是哪个省市的人进行了判断：甲说王教授不是苏州人，是上海人。甲说王教授不是苏州人，是上海人。乙说王教授不是上海人，是苏州人。乙说王教授不是上海人，是苏州人。丙说王教授既不是上海人，也不是杭州人。丙说王教授既不是上海人，也不是杭州人。听听完完以以上上3 3人人的的判判断断后后，王王教教授授笑笑着着说说，他他们们3 3人人中中有有一一人人说说的的全全对对，有有一一人人说说对对了了一一半半，另

16、另一一人人说说的的全全不不对对。试试用逻辑演算法分析王教授到底是哪里人？用逻辑演算法分析王教授到底是哪里人？例例例例2.6 2.6 2.6 2.6 解答解答解答解答设命题设命题 p p：王教授是苏州人。王教授是苏州人。q q：王教授是上海人。王教授是上海人。r r：王教授是杭州人。王教授是杭州人。p,q,rp,q,r中必有一个真命题，两个假命题，要通过逻辑演算将真中必有一个真命题，两个假命题，要通过逻辑演算将真命题找出来。命题找出来。设设甲的判断为甲的判断为A A1 1=pqpq乙的判断为乙的判断为A A2 2=pqpq 丙的判断为丙的判断为A A3 3=qrqr 例例例例2.6 2.6 2.

17、6 2.6 解答解答解答解答甲的判断全对甲的判断全对B B1 1=A=A1 1=pqpq甲的判断对一半甲的判断对一半 B B2 2=(=(pq)(pqpq)(pq)甲的判断全错甲的判断全错 B B3 3=pqpq乙的判断全对乙的判断全对 C C1 1=A=A2 2=pqpq乙的判断对一半乙的判断对一半 C C2 2=(=(pq)(pqpq)(pq)乙的判断全错乙的判断全错 C C3 3=pqpq丙的判断全对丙的判断全对 D D1 1=A=A3 3=qrqr丙的判断对一半丙的判断对一半 D D2 2=(=(qr)(qrqr)(qr)丙的判断全错丙的判断全错 D D3 3=qrqr例例例例2.6

18、2.6 2.6 2.6 解答解答解答解答由王教授所说由王教授所说E=(BE=(B1 1CC2 2DD3 3)(B)(B1 1CC3 3DD2 2)(B)(B2 2CC1 1DD3 3)(B (B2 2CC3 3DD1 1)(B(B3 3C C1 1DD2 2)(B)(B3 3CC2 2DD1 1)为真命题。为真命题。经过等值演算后经过等值演算后,可得可得E E (pqr)(pqrpqr)(pqr)由题设，王教授不能既是上海人，又是杭州人，因而由题设，王教授不能既是上海人，又是杭州人，因而p,rp,r中必中必有一个假命题，即有一个假命题，即pqrpqr0 0，于是，于是E E pqrpqr为真命

19、题，因而必有为真命题，因而必有p,rp,r为假命题，为假命题，q q为真命题，即王教授是上为真命题，即王教授是上海人。甲说的全对，丙说对了一半，而乙全说错了。海人。甲说的全对，丙说对了一半，而乙全说错了。例例例例2.62.62.62.6的进一步思考的进一步思考的进一步思考的进一步思考王教授只可能是其中一个城市的人或者三个城市都不是。王教授只可能是其中一个城市的人或者三个城市都不是。所以，丙至少说对了一半。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有又因为，若甲全错了，则有pqpq，因此乙全对。因此乙全对。同理，乙全错则甲全对。

20、同理，乙全错则甲全对。所以丙必是一对一错。所以丙必是一对一错。根据上述推理，可对公式根据上述推理，可对公式E E进行简化，方便等值演算。进行简化，方便等值演算。(如何简化，请同学们课后思考如何简化，请同学们课后思考)命题公式的应用命题公式的应用命题公式的应用命题公式的应用q 例例1.1.利用基本的等价关系，化简下列电路图利用基本的等价关系，化简下列电路图&1 11 1&T TS SR RQ QP PR RP PS SQ QP PS SP PQ QR RP P解：上述电路图可描述为：解：上述电路图可描述为：（1 1）(PQR)(PQS)(PR)(PS)(PQR)(PQS)(PR)(PS)（2 2

21、）(PQR)(PQS)(PST)(PQR)(PQS)(PST)1.1.1.1.（续）（续）（续）（续）利用利用1616个基本等价关系，化简公式个基本等价关系，化简公式(1)(1)、(2)(2)可得：可得：（1 1）(PQR)(PQS)(PR)(PS)(PQR)(PQS)(PR)(PS)=(PQ(RS)(P(RS)=(PQ(RS)(P(RS)=PQ(RS)=PQ(RS)；（2 2）(PQR)(PQS)(PST)(PQR)(PQS)(PST)=(PQS)(PST)=(PQS)=(PQS)(PST)=(PQS)。S SR RQ QP PP PS SQ Q1 1例例例例2 2 2 2将下面程序语言进行

22、化简。将下面程序语言进行化简。If A then if B then X else Y else if B then X else Y If A then if B then X else Y else if B then X else Y T TF FF FT TF FT TStartStartA AX XY YEndEndB BB B 解：解：执行执行X X的条件为：的条件为：()()()执行执行Y Y的条件为：的条件为：()()()例例例例2(2(2(2(续）续）续）续）执行执行X X的条件可化简为：的条件可化简为：()()()()执行执行Y Y的条件可化简为：的条件可化简为：()()(

23、)()T TX XY YEndEndStartStartB BF F程序可简化为：程序可简化为：If B then X else YIf B then X else Y 例例例例3 3 3 3有一逻辑学家误入某部落，被拘于劳狱，酋长意欲放行，他有一逻辑学家误入某部落，被拘于劳狱，酋长意欲放行，他对逻辑学家说：对逻辑学家说：“今有两门，一为自由，一为死亡，你可任意开启一门。今有两门，一为自由，一为死亡，你可任意开启一门。为协助你脱逃，今加派两名战士负责解答你所提的任何问为协助你脱逃，今加派两名战士负责解答你所提的任何问题。惟可虑者，此两战士中一名天性诚实，一名说谎成性，题。惟可虑者，此两战士中一

24、名天性诚实，一名说谎成性，今后生死由你自己选择。今后生死由你自己选择。”逻辑学家沉思片刻，即向一战士发问，然后开门从容离逻辑学家沉思片刻，即向一战士发问，然后开门从容离去。该逻辑学家应如何发问？去。该逻辑学家应如何发问？解：解：解：解：P:P:被问战士是诚实人；被问战士是诚实人；Q:Q:被问战士的回答是被问战士的回答是“是是”R:R:另一名战士的回答是另一名战士的回答是“是是”S:S:这扇门是死亡门。这扇门是死亡门。P QP QR R S S 0 00 01 11 1 0 10 10 00 0 1 01 00 01 1 1 11 11 10 0逻辑学家手指一门问身旁的一名战士说逻辑学家手指一门

25、问身旁的一名战士说:“:“这扇门是死亡门，他这扇门是死亡门，他(指另一名指另一名战士战士)将回答将回答是是,对吗？对吗？”当被问战士回答当被问战士回答“对对”,则逻辑学家则逻辑学家开启所指的门从容离去。开启所指的门从容离去。当被问的战士回答当被问的战士回答“否否”,则逻辑学家则逻辑学家开启另一扇门从容离去。开启另一扇门从容离去。逻辑学家能够从容离去吗？逻辑学家能够从容离去吗？例例例例4 4 4 4q一家航空公司，为了保证安全，用计算机一家航空公司，为了保证安全，用计算机复核飞行计划。每台计算机能给出飞行计复核飞行计划。每台计算机能给出飞行计划正确或有误的回答。由于计算机也有可划正确或有误的回答

26、。由于计算机也有可能发生故障，因此采用三台计算机同时复能发生故障，因此采用三台计算机同时复核。由所给答案，再根据核。由所给答案，再根据“少数服从多数少数服从多数”的原则作出判断，试将结果用命题公式的原则作出判断，试将结果用命题公式表示，并加以简化，画出电路图。表示，并加以简化，画出电路图。解：解：解：解：设设C C1 1，C C2 2，C C3 3分别表示三台计分别表示三台计算机的答案。算机的答案。S S表示判断结果。表示判断结果。C1 1C2 2C3 3S00000010010001111000101111011111真值表真值表则根据真值表，利用联结则根据真值表，利用联结词的定义，词的定义

27、，S S可用可用C C1 1，C C2 2，C C3 3所对应的命题公式表示出所对应的命题公式表示出来，来，同时可画出该命题公同时可画出该命题公式所对应的电路图。式所对应的电路图。解解解解：（：（：（：（续）续）续）续）S=(S=(C1C2C3)(C1C1C2C3)(C1 C2C3)C2C3)(C1C2 (C1C2 C3)(C1C2C3)C3)(C1C2C3)=(C1 =(C1 C1)C2C3)(C1(C2C1)C2C3)(C1(C2 C2)C2)C3)(C1C2(C3 C3)(C1C2(C3 C3)C3)=(C2C3)(C1C3)(C1C2)=(C2C3)(C1C3)(C1C2)C C1 1

28、C C2 2C C3 3S S&1 11 12.2 2.2 2.2 2.2 析取范式和合取范式析取范式和合取范式析取范式和合取范式析取范式和合取范式 定义定义2.22.2 命题变项及其否定统称作命题变项及其否定统称作文字（文字（letters）。仅由有限个文字构成的析取式称作仅由有限个文字构成的析取式称作简单析取式简单析取式。仅由有限个文字构成的合取式称作仅由有限个文字构成的合取式称作简单合取式简单合取式。q简单析取式举例：简单析取式举例：p,qp,qpppp，pqpq pqr,pqrpqr,pqrq简单合取式举例：简单合取式举例：p,qp,qpppp，pqpqpqr,ppqpqr,ppq说说

29、明明q一个文字既是简单析取式，又是简单合取式。一个文字既是简单析取式，又是简单合取式。2.2 2.2 2.2 2.2 析取范式和合取范式析取范式和合取范式析取范式和合取范式析取范式和合取范式q为讨论方便，有时用为讨论方便，有时用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反之，

30、若反之，若A Ai i为重言式，则它必同时含某个命题变项和它的否为重言式，则它必同时含某个命题变项和它的否定式，否则，若将定式，否则，若将A Ai i中的不带否定符号的命题变项都取中的不带否定符号的命题变项都取0 0值，值，带否定号的命题变项都取带否定号的命题变项都取1 1值，此赋值为值，此赋值为A Ai i的成假赋值，这的成假赋值，这与与A Ai i是重言式相矛盾。是重言式相矛盾。q类似的讨论可知，若类似的讨论可知，若A Ai i是含是含n n个命题变项的简单合取式，且个命题变项的简单合取式，且A Ai i为矛盾式，则为矛盾式，则A Ai i中必同时含某个命题变项及它的否定式，中必同时含某个

31、命题变项及它的否定式，反之亦然。反之亦然。2.2 2.2 2.2 2.2 析取范式和合取范式析取范式和合取范式析取范式和合取范式析取范式和合取范式定理定理2.12.1(1)(1)一个简单析取式是重言式当且仅当它同时含有某个命题一个简单析取式是重言式当且仅当它同时含有某个命题变项及它的否定式。变项及它的否定式。(2)(2)一个简单合取式是矛盾式当且仅当它同时含有某个命题一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及它的否定式。变项及它的否定式。定义定义2.32.3 (1)(1)由有限个简单合取式构成的析取式称为由有限个简单合取式构成的析取式称为析取范式析取范式（disjunctive n

32、ormal form）。(2)(2)由有限个简单析取式构成的合取式称为由有限个简单析取式构成的合取式称为合取范式合取范式（conjunctive normal form）。(3)(3)析取范式与合取范式统称为析取范式与合取范式统称为范式范式。2.2 2.2 2.2 2.2 析取范式和合取范式析取范式和合取范式析取范式和合取范式析取范式和合取范式q设设A Ai i(i(i=1,2,s)=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

33、,A,A2 2,A,A3 3构造的析取范式为构造的析取范式为A=AA=A1 1AA2 2AA3 3=(=(pq)(qr)ppq)(qr)p q设设A Ai i(i(i=1,2,s)=1,2,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=A1 1AA2 2AA3 3=(=(pqr)(pq)rpqr)(pq)r说说明明q形如形如pqrpqr的公式既是一个简单合取式构

34、成的析取的公式既是一个简单合取式构成的析取范式，又是由三个简单析取式构成的合取范式。范式，又是由三个简单析取式构成的合取范式。q形如形如pqrpqr的公式既是含三个简单合取式的析取范的公式既是含三个简单合取式的析取范式，又是含一个简单析取式的合取范式。式，又是含一个简单析取式的合取范式。析取范式和合取范式的性质析取范式和合取范式的性质析取范式和合取范式的性质析取范式和合取范式的性质定理定理2.22.2(1)(1)一个析取范式是矛盾式当且仅当它的每个简单合取式都是一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。矛盾式。(2)(2)一个合取范式是重言式当且仅当它的每个简单析取式都是一个合

35、取范式是重言式当且仅当它的每个简单析取式都是重言式。重言式。说说明明q研究范式的目的在于，将给定公式化成与之等值的析取研究范式的目的在于，将给定公式化成与之等值的析取范式或合取范式，进而将公式化成与之等值的主析取范范式或合取范式，进而将公式化成与之等值的主析取范式或主合取范式。式或主合取范式。范式存在的讨论范式存在的讨论范式存在的讨论范式存在的讨论q在范式中不会出现联结词在范式中不会出现联结词与与，否则可使用等值式消除否则可使用等值式消除AB AB AB ABA AB B (AB)(AB)(AB)(AB)q在范式中不会出现形如在范式中不会出现形如A,(AB),(AB)A,(AB),(AB)的公

36、式：的公式：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 任一命题公式都存在着与之等值的析取范式与合取范式。任一命题公式都存在着与之等值的析取范式与合取范式。求给定公式范式的步骤求给定公式范式的步骤求给定公式范式的步骤求给定公式范式的步骤 (1(1)消去联结词消去联结词、(若存在若存在)。AB

37、 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)例题例题例题例题例题例题2.72.7 求下面公式的析取范式与合取范式：求下面公式的析取范式与合取范式：(pqpq)r r (1)(

38、1)求合取范式求合取范式 (p pq q)r r (pqpq)r r （消去消去）(pq)pq)r)(rr)(r(pq(pq)（消去消去）(pq)r)(rpqpq)r)(rpq)（消去消去）(pq)pq)rr)(pqr)(pqr)（否定号内移）否定号内移）(pr)(qr)(pqrpr)(qr)(pqr)（对对分配律）分配律）解答解答例题例题例题例题(2)(2)求析取范式求析取范式 (pqpq)r r (pq)pq)r)r)(p(pq qrr)(pqp)(pqq)(pqrpqp)(pqq)(pqr)(rp)(rq)(rrrp)(rq)(rr)(pqr)(pr)(qrpqr)(pr)(qr)说说明

39、明q由此例可知由此例可知，命题公式的析取范式不唯一。命题公式的析取范式不唯一。q同样同样，合取范式也是不唯一的。合取范式也是不唯一的。范式的规范化形式范式的规范化形式范式的规范化形式范式的规范化形式q定义定义2.42.4 在含有在含有n n个命题变项的简单合取式（简单析取式）个命题变项的简单合取式（简单析取式）中，若每个命题变项和它的否定式不同时出现，而二者之中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第一必出现且仅出现一次，且第i i个命题变项或它的否定式出个命题变项或它的否定式出现在从左算起的第现在从左算起的第i i位上（若命题变项无角标，就按字典顺位上（若命

40、题变项无角标，就按字典顺序排列），称这样的简单合取式（简单析取式）为序排列），称这样的简单合取式（简单析取式）为极小项极小项（极大项极大项）。qn n个命题变项共可产生个命题变项共可产生2 2n n个不同的极小项。其中每个极小项个不同的极小项。其中每个极小项都有且仅有一个成真赋值。若成真赋值所对应的二进制数都有且仅有一个成真赋值。若成真赋值所对应的二进制数转换为十进制数转换为十进制数i i，就将所对应极小项记作就将所对应极小项记作m mi i。q类似地，类似地，n n个命题变项共可产生个命题变项共可产生2 2n n个极大项，每个极大项只个极大项，每个极大项只有一个成假赋值，将其对应的十进制数有

41、一个成假赋值，将其对应的十进制数i i做极大项的角标，做极大项的角标，记作记作M Mi i。表表表表2.3 2.3 2.3 2.3 p,qp,qp,qp,q形成的极小项与极大项形成的极小项与极大项形成的极小项与极大项形成的极小项与极大项 表表表表2.4 2.4 2.4 2.4 p,q,rp,q,rp,q,rp,q,r形成的极小项与极大项形成的极小项与极大项形成的极小项与极大项形成的极小项与极大项 范式的规范化形式范式的规范化形式范式的规范化形式范式的规范化形式定理定理2.42.4 设设m mi i与与M Mi i是命题变项是命题变项p p1 1,p,p2 2,p pn n形成的形成的极小项和极

42、大项，则极小项和极大项，则 m mi i M Mi i，M Mi i m mi i 定义定义2.52.5 设由设由n n个命题变项构成的析取范式（合取范个命题变项构成的析取范式（合取范式）中所有的简单合取式（简单析取式）都是极式）中所有的简单合取式（简单析取式）都是极小项（极大项），则称该析取范式（合取范式）小项（极大项），则称该析取范式（合取范式）为主析取范式为主析取范式（主合取范式主合取范式）。定理定理2.52.5 任何命题公式都存在着与之等值的主析取任何命题公式都存在着与之等值的主析取范式和主合取范式，并且是唯一的。范式和主合取范式，并且是唯一的。定理定理定理定理2.52.52.52.5

43、的证明的证明的证明的证明(只证主析取范式的存在和唯一性只证主析取范式的存在和唯一性)(1)(1)证明存在性。证明存在性。设设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

44、 jppj j)继续这个过程，直到所有的简单合取式都含任意命题变项或它的继续这个过程，直到所有的简单合取式都含任意命题变项或它的否定式。否定式。若在演算过程中出现重复的命题变项以及极小项和矛盾式时，都若在演算过程中出现重复的命题变项以及极小项和矛盾式时，都应应“消去消去”：如用：如用p p代替代替pppp，m mi i代替代替m mi immi i，0 0代替矛盾式等。代替矛盾式等。最后就将最后就将A A化成与之等值的主析取范式化成与之等值的主析取范式AA。定理定理定理定理2.52.52.52.5(2)(2)证明唯一性。证明唯一性。假设某一命题公式假设某一命题公式A A存在两个与之等值的主析取

45、范式存在两个与之等值的主析取范式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的成假赋的成假赋值。这与值。这与B BC C矛盾，因而矛盾，因而B B与与C C必相同。必相同。需要说明需要说明需要说明需要说明q求任何一个公式的主析取范式和主合求任何一个公式的主析取范式和主合取范式不仅要取决于取范式不仅要取决于该公式该公

46、式，而且取，而且取决于该公式所包含的决于该公式所包含的命题变元命题变元。如公式：如公式：G G1 1=(PQ)Q=(PQ)Q，G G2 2(P,Q,R)=(PQ)Q(P,Q,R)=(PQ)Q。前者是依赖于两个命题变元的，后者应依赖于三个前者是依赖于两个命题变元的，后者应依赖于三个命题变元。命题变元。求主析取范式和主合取范式的方法求主析取范式和主合取范式的方法求主析取范式和主合取范式的方法求主析取范式和主合取范式的方法公式转换法公式转换法利用基本等价公利用基本等价公式进行变换式进行变换主范式主范式真值表技术真值表技术对公式的真值结对公式的真值结果进行分解，分果进行分解，分解成等价的极小解成等价的

47、极小项的析取或者极项的析取或者极大项的合取大项的合取求公式求公式求公式求公式A A A A的主析取范式的方法与步骤的主析取范式的方法与步骤的主析取范式的方法与步骤的主析取范式的方法与步骤方法一、等值演算法方法一、等值演算法(1)(1)化归为析取范式。化归为析取范式。(2)(2)除去析取范式中所有永假的析取项。除去析取范式中所有永假的析取项。(3)(3)将析取式中重复出现的合取项和相同的变元合并。将析取式中重复出现的合取项和相同的变元合并。(4)(4)对合取项补入没有出现的命题变元，即添加如对合取项补入没有出现的命题变元，即添加如(pppp)式，式，然后应用分配律展开公式。然后应用分配律展开公式

48、。方法二、真值表法方法二、真值表法(1)(1)写出写出A A的真值表。的真值表。(2)(2)找出找出A A的成真赋值。的成真赋值。(3)(3)求出每个成真赋值对应的极小项（用名称表示），按角标求出每个成真赋值对应的极小项（用名称表示），按角标从小到大顺序析取。从小到大顺序析取。求公式求公式求公式求公式A A A A的主合取范式的方法与步骤的主合取范式的方法与步骤的主合取范式的方法与步骤的主合取范式的方法与步骤方法一、等值演算法方法一、等值演算法(1)(1)化归为合取范式。化归为合取范式。(2)(2)除去合取范式中所有永真的合取项。除去合取范式中所有永真的合取项。(3)(3)将合取式中重复出现的

49、析取项和相同的变元合并。将合取式中重复出现的析取项和相同的变元合并。(4)(4)对析取项补入没有出现的命题变元，即添加如对析取项补入没有出现的命题变元，即添加如(pppp)式，式，然后应用分配律展开公式。然后应用分配律展开公式。方法二、真值表法方法二、真值表法(1)(1)写出写出A A的真值表。的真值表。(2)(2)找出找出A A的成假赋值。的成假赋值。(3)(3)求出每个成假赋值对应的极大项（用名称表示），按角标求出每个成假赋值对应的极大项（用名称表示），按角标从小到大顺序析取。从小到大顺序析取。例例例例2.8 2.8 2.8 2.8 求例求例求例求例2.72.72.72.7中公式的主析取范

50、式和主合取范式。中公式的主析取范式和主合取范式。中公式的主析取范式和主合取范式。中公式的主析取范式和主合取范式。(1)(1)求主析取范式求主析取范式(pq)pq)r r (pqr)(pr)(qrpqr)(pr)(qr)pqrpqr m m4 4prpr pp（qqqq）rr (pqr)(pqrpqr)(pqr)m m1 1mm3 3 qrqr (pp)qrpp)qr (pqr)(pqrpqr)(pqr)m m3 3mm7 7 (pq)pq)r r m m1 1mm3 3mm4 4mm7 7例例例例2.8 2.8 2.8 2.8 求例求例求例求例2.72.72.72.7中公式的主析取范式和主合取