第2章命题逻辑等值演算课件.ppt
91页
1第第2 2章章 命题逻辑等值演算命题逻辑等值演算 离散数学离散数学 2本章说明本章说明本章说明本章说明q本章的主要内容本章的主要内容–等值式与基本的等值式等值式与基本的等值式–等值演算与置换规则等值演算与置换规则–析取范式与合取范式、主析取范式与主合取范式析取范式与合取范式、主析取范式与主合取范式–联结词完备集联结词完备集(不讲不讲)q本章与后续各章的关系本章与后续各章的关系–是第一章的抽象与延伸是第一章的抽象与延伸–是后续各章的现行准备是后续各章的现行准备 3q两公式什么时候代表了同一个命题呢？两公式什么时候代表了同一个命题呢？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.1 2.1 等值式等值式 4定义定义2.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中可能有哑元出现中可能有哑元出现p pq q ( ( p p q)q) ( ( r r r)r)r r为左边公式中的哑元为左边公式中的哑元q用真值表可以验证两个公式是否等值用真值表可以验证两个公式是否等值等值的定义及说明等值的定义及说明 5例例2.1 2.1 判断下面两个公式是否等值判断下面两个公式是否等值 ( (p p q) q) 与与 p pq q 解答解答说明说明q在用真值表法判断在用真值表法判断A AB B是否为重言式时，真值是否为重言式时，真值表的最后一列可以省略表的最后一列可以省略等值等值例题例题 6例题例题2.22.2 判断下列各组公式是否等值判断下列各组公式是否等值(1)p(1)p(q(qr)r)与与( (p p q)q)r r (2)((2)(p pq)q)r r与与( (p p q)q)r r 解答解答等值等值不等值不等值例题例题 71.1.双重否定律双重否定律A A A A2.2.幂等律幂等律A A A A A,A,A A A A A A 3.3.交换律交换律A A B B B B A A，，A A B B B B A A4.4.结合律结合律( (A A B)B) C C A A (B(B C)C) (A(A B)B) C C A A (B(B C) C) 5.5.分配律分配律 A A (B(B C) C) (A(A B)B) (A(A C) C) （（ 对对 的分配律）的分配律）A A (B(B C) C) (A(A B)B) (A(A C)C)（（ 对对 的分配律）的分配律）6.6.德德·摩根律摩根律 ( (A A B) B) A AB B (A(A B) B) A AB B 7.7.吸收律吸收律 A A (A(A B) B) A A，，A A (A(A B) B) A A 基本等值式基本等值式 8基本等值式基本等值式基本等值式基本等值式 8.8.零律零律 A A 1 1 1,A 1,A 0 0 0 0 9. 9.同一律同一律 A A 0 0 A A，，A A 1 1 A A 10.10.排中律排中律 A AA A 1 1 11.11.矛盾律矛盾律 A AA A 0 0 12.12.蕴涵等值式蕴涵等值式 A AB B A A B B13.13.等价等值式等价等值式 A AB B (A(AB)B) (B(BA)A)14.14.假言易位假言易位 A AB B B BA A15.15.等价否定等值式等价否定等值式 A AB B A AB B16.16.归谬论归谬论 ( (A AB)B) (A(AB) B) A A 9一个逻辑等值式，如果只含有一个逻辑等值式，如果只含有 、、 、、 、、0 0、、1 1那么同时那么同时把把 和和 互换互换把把0 0和和1 1互换互换得到的还是等值式。
得到的还是等值式对偶原理对偶原理 10q各等值式都是用元语言符号书写的，其中各等值式都是用元语言符号书写的，其中A,B,CA,B,C可以代表任意可以代表任意的公式，称这样的等值式为的公式，称这样的等值式为等值式模式等值式模式q每个等值式模式都给出了无穷多个同类型的具体的等值式每个等值式模式都给出了无穷多个同类型的具体的等值式例如，在蕴涵等值式例如，在蕴涵等值式 A AB B A A B B 中，中，取取A=pA=p，，B=qB=q时，得等值式时，得等值式 p pq q p p q q 取取A=pA=p q q r r，，B=pB=p q q时，得等值式时，得等值式( (p p q q r r) )( (p p q q) ) ( (p p q q r r) ) ( (p p q q) )q这些具体的等值式都被称为原来的等值式模式的这些具体的等值式都被称为原来的等值式模式的代入实例代入实例q由已知的等值式推演出另外一些等值式的过程为由已知的等值式推演出另外一些等值式的过程为等值演算等值演算。
q置换规则置换规则 设设Φ(A)Φ(A)是含公式是含公式A A的命题公式，的命题公式，Φ(B)Φ(B)是用公式是用公式B B置置换了换了Φ(A)Φ(A)中所有的中所有的A A后得到的命题公式，若后得到的命题公式，若B BA A，，则则Φ(B)Φ(B)Φ(A)Φ(A)等值演算与置换规则等值演算与置换规则 11q等值演算的基础等值演算的基础–等值关系的性质：等值关系的性质：自反性：自反性：A AA A对称性：若对称性：若A AB B，，则则B BA A传递性：若传递性：若A AB B且且B BC C，，则则A AC C–基本的等值式基本的等值式–置换规则置换规则q等值演算的应用等值演算的应用–证明两个公式等值证明两个公式等值–判断公式类型判断公式类型–解判定问题解判定问题关于等值演算的说明关于等值演算的说明 12证明两个公式等值证明两个公式等值( (p pq)q)r r ( (p p r)r) ( ( q q r)r)( (p pq q) )r r ( ( p p q)q)r r （（蕴含等值式、置换规则）蕴含等值式、置换规则） ( ( p p q)q) r r （（蕴含等值式、置换规则）蕴含等值式、置换规则） ( (p pq)q) r r（（德摩根律、置换规则）德摩根律、置换规则） ( (p p r)r) ( ( q q r)r)（（分配律、置换规则）分配律、置换规则）说明说明q也可以从右边开始演算也可以从右边开始演算q因为每一步都用置换规则，故可不写出因为每一步都用置换规则，故可不写出q熟练后，基本等值式也可以不写出熟练后，基本等值式也可以不写出q通常不用等值演算直接证明两个公式不等值通常不用等值演算直接证明两个公式不等值解答解答等值演算的应用举例等值演算的应用举例 13例例2.32.3 用等值演算法验证等值式用等值演算法验证等值式(p(p q)q)r r (p(pr)r) (q(qr) r) (p(pr)r) (q(qr) r) ( ( p p r r) ) ( ( q q r r) ) ( (蕴含等值式蕴含等值式) ) ( ( p pq q)∨r)∨r( (分配律分配律) ) (p(p q)q) r r( (德摩根律德摩根律) ) (p(p q)q)r r( (蕴含等值式蕴含等值式) ) 解答解答例题例题 14例例2.42.4 证明：证明：(p(pq)q)r r 与与 p p(q(qr) r) 不等值不等值方法一、方法一、真值表法。
真值表法 方法二、方法二、观察法易知，易知，010010是是(pq)r的成假赋值，而的成假赋值，而010010是是p(qr)的成真赋值，所以原不等值式成立的成真赋值，所以原不等值式成立 方法三、方法三、通过等值演算化成容易观察真值的情况，再进行判断通过等值演算化成容易观察真值的情况，再进行判断A=(pA=(pq)q)r r ( ( p p q)q)r r （蕴涵等值式）（蕴涵等值式） ( ( p p q)q) r r （蕴涵等值式）（蕴涵等值式） (p(pq)q) r r （德摩根律）（德摩根律） B=pB=p(q(qr) r) p p ( ( q q r r) ) （蕴涵等值式）（蕴涵等值式） p pq q r r （结合律）（结合律） 000 000，，010010是是A A的成假赋值，而它们是的成假赋值，而它们是B B的成真赋值。
的成真赋值 解答解答例题例题 15例题例题2.52.5 用等值演算判断下列公式的类型：用等值演算判断下列公式的类型：（（1 1））(p(pq)q) p pq q （（2 2））(p(p(p(p q))q)) r r （（3 3））p p (((p(((p q)q)p)p)q) q) 例题例题 16(1) (p(1) (pq)q) p pq q ( ( p p q)q) p pq q （（蕴涵等值式）蕴涵等值式） (((( p p q)q) p)p) q q （（蕴涵等值式）蕴涵等值式） ( ( ( ( p p q q) )p)p) q q （（德摩根律）德摩根律） ((((p pq)q)p p) ) q q （（德摩根律）德摩根律） ((((p pp p) ) ( ( q qp))p)) q q （（分配律）分配律） ( (1 1 ( ( q qp))p)) q q （（排中律）排中律） ( ( q q q q) )p p （（同一律）同一律） 1 1p p（（排中律）排中律） 1 1 （零律）（零律）例例2.5 2.5 解答解答 17例例例例2.5 2.5 2.5 2.5 解答解答解答解答(2) (2) (p(p(p(p q))q)) r r ( ( p p p p q)q) r r ( (p pp pq)q) r r 0 0 r r 0 0(3) (3) p p (((p(((p q)q)p)p)q) q) p p ( ( ((p((p q)q)p p)∨q) )∨q) p p ( ( ( ((p(pp)p) (q(qp))p)) q) q) p p ( ( ( (0 0 (q(qp))p)) q) q) p p ( ( q q p p q q) ) p p 1 1 p p 18在在某某次次研研讨讨会会的的中中间间休休息息时时间间，，3 3名名与与会会者者根根据据王王教教授授的的口口音对他是哪个省市的人进行了判断：音对他是哪个省市的人进行了判断：甲说王教授不是苏州人，是上海人。
甲说王教授不是苏州人，是上海人乙说王教授不是上海人，是苏州人乙说王教授不是上海人，是苏州人丙说王教授既不是上海人，也不是杭州人丙说王教授既不是上海人，也不是杭州人听听完完以以上上3 3人人的的判判断断后后，，王王教教授授笑笑着着说说，，他他们们3 3人人中中有有一一人人说说的的全全对对，，有有一一人人说说对对了了一一半半，，另另一一人人说说的的全全不不对对试试用逻辑演算法分析王教授到底是哪里人？用逻辑演算法分析王教授到底是哪里人？ 2.6 2.6 应用题应用题 19设命题设命题 p p：：王教授是苏州人王教授是苏州人 q q：：王教授是上海人王教授是上海人 r r：：王教授是杭州人王教授是杭州人p,q,rp,q,r中必有一个真命题，两个假命题，要通过逻辑演算将真中必有一个真命题，两个假命题，要通过逻辑演算将真命题找出来命题找出来设设甲的判断为甲的判断为A A1 1= = p p q q乙的判断为乙的判断为A A2 2=p=pq q 丙的判断为丙的判断为A A3 3= = q qr r 例例2.6 2.6 解答解答 20甲的判断全对甲的判断全对 B B1 1=A=A1 1= = p p q q甲的判断对一半甲的判断对一半 B B2 2=(=( p pq)q) (p(p q)q)甲的判断全错甲的判断全错 B B3 3=p=pq q乙的判断全对乙的判断全对 C C1 1=A=A2 2=p=pq q乙的判断对一半乙的判断对一半 C C2 2=(p=(p q)q) ( ( p pq)q)乙的判断全错乙的判断全错 C C3 3= = p p q q丙的判断全对丙的判断全对 D D1 1=A=A3 3= = q qr r丙的判断对一半丙的判断对一半 D D2 2=(q=(qr)r) ( ( q q r)r)丙的判断全错丙的判断全错 D D3 3=q=q r r例例2.6 2.6 解答解答 21由王教授所说由王教授所说E = (BE = (B1 1 C C2 2 D D3 3) ) (B(B1 1 C C3 3 D D2 2) ) (B(B2 2 C C1 1 D D3 3) ) (B(B2 2 C C3 3 D D1 1) ) (B(B3 3 C C1 1 D D2 2) ) (B(B3 3∧C∧C2 2∧D∧D1 1) )为真命题。
为真命题 经过等值演算后经过等值演算后, ,可得可得E E ( ( p p q qr)r) (p(pq q r) r) 由题设，王教授不能既是上海人，又是杭州人，因而由题设，王教授不能既是上海人，又是杭州人，因而p,rp,r中必中必有一个假命题，即有一个假命题，即p pq q r r0 0，于是，于是E E p p q qr r为真命题，因而必有为真命题，因而必有p,rp,r为假命题，为假命题，q q为真命题，即王教授是上为真命题，即王教授是上海人甲说的全对，丙说对了一半，而乙全说错了甲说的全对，丙说对了一半，而乙全说错了例例2.6 2.6 解答解答 22王教授只可能是其中一个城市的人或者三个城市都不是王教授只可能是其中一个城市的人或者三个城市都不是所以，丙至少说对了一半所以，丙至少说对了一半因此，可得甲或乙必有一人全错了因此，可得甲或乙必有一人全错了又因为，若甲全错了，则有又因为，若甲全错了，则有p pq q，，因此乙全对因此乙全对同理，乙全错则甲全对同理，乙全错则甲全对所以丙必是一对一错。
所以丙必是一对一错根据上述推理，可对公式根据上述推理，可对公式E E进行简化，方便等值演算进行简化，方便等值演算 (如何简化，请同学们课后思考如何简化，请同学们课后思考) )例例2.62.6的进一步思考的进一步思考 23定义定义2.22.2 命题变项及其否定统称作命题变项及其否定统称作文字（文字（letters））仅由有限个文字构成的析取式称作仅由有限个文字构成的析取式称作简单析取式简单析取式仅由有限个文字构成的合取式称作仅由有限个文字构成的合取式称作简单合取式简单合取式q简单析取式举例：简单析取式举例：p,┐qp,┐qp∨┐pp∨┐p，，┐p∨q ┐p∨q ┐┐p∨┐q∨r,p∨┐q∨rp∨┐q∨r,p∨┐q∨rq简单合取式举例：简单合取式举例：┐┐p,qp,q┐┐p∧pp∧p，，p∧┐qp∧┐qp∧q∧┐r,┐p∧p∧qp∧q∧┐r,┐p∧p∧q说明说明q一个文字既是简单析取式，又是简单合取式一个文字既是简单析取式，又是简单合取式2.2 2.2 析取范式和合取范式析取范式和合取范式 24q为讨论方便，有时用为讨论方便，有时用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 j∨∨ p pj j，则，则A Ai i为重言式为重言式q反之，若反之，若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中必同时含某个命题变项及它的否定式，中必同时含某个命题变项及它的否定式，反之亦然反之亦然 2.2 2.2 析取范式和合取范式析取范式和合取范式 25定理定理2.12.1(1)(1)一个简单析取式是重言式当且仅当它同时含有某个命题一个简单析取式是重言式当且仅当它同时含有某个命题变项及它的否定式。
变项及它的否定式2)(2)一个简单合取式是矛盾式当且仅当它同时含有某个命题一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及它的否定式变项及它的否定式 定义定义2.32.3 (1)(1)由有限个简单由有限个简单合取式合取式构成构成的析取的析取式称为式称为析取范式析取范式（（disjunctive normal form））2)(2)由有限个简单由有限个简单析取式析取式构成构成的合取的合取式称为式称为合取范式合取范式（（conjunctive normal form））3)(3)析取范式与合取范式统称为析取范式与合取范式统称为范式范式 2.2 2.2 析取范式和合取范式析取范式和合取范式 26q设设A Ai i(i=1,2,(i=1,2,…,s),s)为简单合取式，则为简单合取式，则A=AA=A1 1∨A∨A2 2∨∨…∨A∨As s为析取为析取范式例如，范式例如，A A1 1=p∧┐q=p∧┐q，，A A2 2=┐q∧┐r=┐q∧┐r，，A A3 3=p=p，，则由则由A A1 1,A,A2 2,A,A3 3构造的析取范式为构造的析取范式为A=AA=A1 1∨A∨A2 2∨A∨A3 3=(p∧┐q)∨(┐q∧┐r)∨p =(p∧┐q)∨(┐q∧┐r)∨p q设设A Ai i(i=1,2,(i=1,2,…,s),s)为简单析取式，则为简单析取式，则A=AA=A1 1∧A∧A2 2∧∧…∧A∧As s为合取为合取范式。
例如，取范式例如，取A A1 1=p∨q∨r=p∨q∨r，，A A2 2=┐p∨┐q=┐p∨┐q，，A A3 3=r=r，，则由则由A A1 1,A,A2 2,A,A3 3组成的合取范式为组成的合取范式为A=AA=A1 1∧A∧A2 2∧A∧A3 3=(p∨q∨r)∧(┐p∨┐q)∧r=(p∨q∨r)∧(┐p∨┐q)∧r说明说明q形如形如┐┐p∧q∧rp∧q∧r的公式既是一个简单合取式构成的析取的公式既是一个简单合取式构成的析取范式，又是由三个简单析取式构成的合取范式范式，又是由三个简单析取式构成的合取范式q形如形如p∨┐q∨rp∨┐q∨r的公式既是含三个简单合取式的析取范的公式既是含三个简单合取式的析取范式，又是含一个简单析取式的合取范式式，又是含一个简单析取式的合取范式2.2 2.2 析取范式和合取范式析取范式和合取范式 27定理定理2.22.2(1)(1)一个析取范式是矛盾式当且仅当它的每个简单合取式都是一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式2)(2)一个合取范式是重言式当且仅当它的每个简单析取式都是一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。
重言式 说明说明q研究范式的目的在于，将给定公式化成与之等值的析取研究范式的目的在于，将给定公式化成与之等值的析取范式或合取范式，进而将公式化成与之等值的主析取范范式或合取范式，进而将公式化成与之等值的主析取范式或主合取范式式或主合取范式析取范式和合取范式的性质析取范式和合取范式的性质 28q在范式中不会出现联结词在范式中不会出现联结词→→与与，，否则可使用等值式消除否则可使用等值式消除A→B A→B ┐A∨B ┐A∨BA AB B (┐A∨B)∧(A∨┐B) (┐A∨B)∧(A∨┐B)q在范式中不会出现形如在范式中不会出现形如┐┐┐┐A,┐(A∧B),┐(A∨B)A,┐(A∧B),┐(A∨B)的公式：的公式：┐┐┐┐A A A A┐(┐(A∧B) A∧B) ┐A∨┐B ┐A∨┐B ┐(┐(A∨B)A∨B)┐A∧┐B┐A∧┐Bq在析取范式中不会出现形如在析取范式中不会出现形如A∧(B∨C)A∧(B∨C)的公式：的公式：A∧(B∨C) A∧(B∨C) (A∧B)∨(A∧C) (A∧B)∨(A∧C)q在合取范式中不出现形在合取范式中不出现形A∨(B∧C)A∨(B∧C)的公式：的公式：A∨(B∧C) A∨(B∧C) (A∨B)∧(A∨C) (A∨B)∧(A∨C) q定理定理2.32.3 任一命题公式都存在着与之等值的析取范式与合取范式。
任一命题公式都存在着与之等值的析取范式与合取范式 范式存在的讨论范式存在的讨论 29(1(1) )消去联结词消去联结词→→、、( (若存在若存在) )A→B A→B ┐A∨B ┐A∨BA AB B (┐A∨B)∧(A∨┐B) (┐A∨B)∧(A∨┐B)(2)(2)否定号的消去否定号的消去( (利用双重否定律利用双重否定律) )或内移或内移( (利用德摩根律利用德摩根律) )┐┐┐┐A A A A┐(┐(A∧B) A∧B) ┐A∨┐B ┐A∨┐B┐(┐(A∨B)A∨B)┐A∧┐B┐A∧┐B(3)(3)利用分配律：利用利用分配律：利用∧∧对对∨∨的分配律求析取范式，的分配律求析取范式， ∨ ∨对对∧∧的分配律求合取范式的分配律求合取范式A∧(B∨C) A∧(B∨C) (A∧B)∨(A∧C) (A∧B)∨(A∧C)A∨(B∧C) A∨(B∧C) (A∨B)∧(A∨C) (A∨B)∧(A∨C)给定公式范式的步骤给定公式范式的步骤 30例题例题2.72.7 求下面公式的析取范式与合取范式：求下面公式的析取范式与合取范式：( (p→q)p→q) r r (1) (1) 求合取范式求合取范式 ( (p p→→q)q) r r (┐p∨q) (┐p∨q) r r （（消去消去→→）） ((┐((┐p∨q)p∨q)→→r)∧(rr)∧(r→→(┐p∨q)) (┐p∨q)) （（消去消去）） ( (┐┐(┐(┐p∨q)∨r)∧(┐r∨┐p∨q)p∨q)∨r)∧(┐r∨┐p∨q) （（消去消去→→）） ((((p∧┐q)p∧┐q)∨r∨r)∧(┐p∨q∨┐r))∧(┐p∨q∨┐r) （（否定号内移）否定号内移） ( (p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)（（∨∨对对∧∧分配律）分配律）解答解答例题例题 31例题例题例题例题(2) (2) 求析取范式求析取范式 ( (p→q)p→q) r r ( (( (p∧┐q)p∧┐q)∨∨r)r)∧∧(┐p(┐p∨∨q q∨∨┐r)┐r) ( (p∧┐q∧┐p)∨(p∧┐q∧q)∨(p∧┐q∧┐r)p∧┐q∧┐p)∨(p∧┐q∧q)∨(p∧┐q∧┐r) ∨(r∧┐p)∨(r∧q)∨(r∧┐r) ∨(r∧┐p)∨(r∧q)∨(r∧┐r) ( (p∧┐q∧┐r)∨(┐p∧r)∨(q∧r) p∧┐q∧┐r)∨(┐p∧r)∨(q∧r) 说明说明q由此例可知由此例可知，，命题公式的析取范式不唯一。
命题公式的析取范式不唯一q同样同样，，合取范式也是不唯一的合取范式也是不唯一的 32q定义定义2.42.4 在含有在含有n n个命题变项的简单合取式（简单析取式）个命题变项的简单合取式（简单析取式）中，若每个命题变项和它的否定式不同时出现，而二者之中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第一必出现且仅出现一次，且第i i个命题变项或它的否定式出个命题变项或它的否定式出现在从左算起的第现在从左算起的第i i位上（若命题变项无角标，就按字典顺位上（若命题变项无角标，就按字典顺序排列），称这样的简单合取式（简单析取式）为序排列），称这样的简单合取式（简单析取式）为极小项极小项（（极大项极大项））qn n个命题变项共可产生个命题变项共可产生2 2n n个不同的极小项其中每个极小项个不同的极小项其中每个极小项都有且仅有一个成真赋值若成真赋值所对应的二进制数都有且仅有一个成真赋值若成真赋值所对应的二进制数转换为十进制数转换为十进制数i i，，就将所对应极小项记作就将所对应极小项记作m mi i q类似地，类似地，n n个命题变项共可产生个命题变项共可产生2 2n n个极大项，每个极大项只个极大项，每个极大项只有一个成假赋值，将其对应的十进制数有一个成假赋值，将其对应的十进制数i i做极大项的角标，做极大项的角标，记作记作M Mi i。
范式的规范化形式范式的规范化形式 33表表2.3 p,q2.3 p,q形成的极小项与极大项形成的极小项与极大项 34表表2.4 p,q,r2.4 p,q,r形成的极小项与极大项形成的极小项与极大项 35范式的规范化形式范式的规范化形式定理定理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 m mi i 定义定义2.52.5 设由设由n n个命题变项构成的析取范式（合取范个命题变项构成的析取范式（合取范式）中所有的简单合取式（简单析取式）都是极式）中所有的简单合取式（简单析取式）都是极小项（极大项），则称该析取范式（合取范式）小项（极大项），则称该析取范式（合取范式）为主析取范式为主析取范式（（主合取范式主合取范式）） 定理定理2.52.5 任何命题公式都存在着与之等值的主析取任何命题公式都存在着与之等值的主析取范式和主合取范式，并且是范式和主合取范式，并且是唯一唯一的。
的 36定理定理2.52.5的证明的证明( (只证主析取范式的存在和唯一性只证主析取范式的存在和唯一性) )(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 i∧1 ∧1 A Ai i∧(p∧(pj j∨┐p∨┐pj j) ) (A(Ai i∧p∧pj j)∨(A)∨(Aj j∧┐p∧┐pj j) ) 继续这个过程，直到所有的简单合取式都含任意命题变项或它的继续这个过程，直到所有的简单合取式都含任意命题变项或它的否定式 若在演算过程中出现重复的命题变项以及极小项和矛盾式时，都若在演算过程中出现重复的命题变项以及极小项和矛盾式时，都应应“消去消去”：如用：如用p p代替代替p∧pp∧p，，m mi i代替代替m mi i∨m∨mi i，，0 0代替矛盾式等。
代替矛盾式等最后就将最后就将A A化成与之等值的主析取范式化成与之等值的主析取范式A''A'' 37定理定理2.52.5(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的成假赋的成假赋值这与B BC C矛盾，因而矛盾，因而B B与与C C必相同 38求公式求公式A A的主析取范式的方法与步骤的主析取范式的方法与步骤方法一、等值演算法方法一、等值演算法(1)(1)化归为析取范式化归为析取范式 (2)(2)除去析取范式中所有永假的析取项除去析取范式中所有永假的析取项3)(3)将析取式中重复出现的合取项和相同的变元合并将析取式中重复出现的合取项和相同的变元合并。
4)(4)对合取项补入没有出现的命题变元，即添加如对合取项补入没有出现的命题变元，即添加如( (p∨┐p)p∨┐p)式，式，然后应用分配律展开公式然后应用分配律展开公式方法二、真值表法方法二、真值表法(1)(1)写出写出A A的真值表的真值表2)(2)找出找出A A的成真赋值的成真赋值3)(3)求出每个成真赋值对应的极小项（用名称表示），按角标求出每个成真赋值对应的极小项（用名称表示），按角标从小到大顺序析取从小到大顺序析取 39求公式求公式求公式求公式A A A A的主合取范式的方法与步骤的主合取范式的方法与步骤的主合取范式的方法与步骤的主合取范式的方法与步骤方法一、等值演算法方法一、等值演算法(1)(1)化归为合取范式化归为合取范式 (2)(2)除去合取范式中所有永真的合取项除去合取范式中所有永真的合取项3)(3)将合取式中重复出现的析取项和相同的变元合并将合取式中重复出现的析取项和相同的变元合并4)(4)对析取项补入没有出现的命题变元，即添加如对析取项补入没有出现的命题变元，即添加如( (p∧┐p)p∧┐p)式，式，然后应用分配律展开公式然后应用分配律展开公式方法二、真值表法方法二、真值表法(1)(1)写出写出A A的真值表。
的真值表2)(2)找出找出A A的成假赋值的成假赋值3)(3)求出每个成假赋值对应的极大项（用名称表示），按角标求出每个成假赋值对应的极大项（用名称表示），按角标从小到大顺序析取从小到大顺序析取 40例题例题例题例题例例2.92.9 求命题公式求命题公式 p→q p→q 的主析取范式和主合取范式的主析取范式和主合取范式1)(1)求主合取范式求主合取范式p→q p→q ┐p∨q ┐p∨q M M2 2(2)(2)求析取范式求析取范式p→q p→q ┐p∨q┐p∨q （（┐p∧┐p∧（（┐q∨q┐q∨q）））） ∨ ∨ （（( (┐p∨p┐p∨p)∧q)∧q）） (┐(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q) p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q) (┐p∧┐q)∨(┐p∧q)∨(p∧q) (┐p∧┐q)∨(┐p∧q)∨(p∧q) m m0 0∨m∨m1 1∨m∨m3 3 解答解答pqp →q0 01011100111 41例例2.8 2.8 求例求例2.72.7中公式的主析取范式和主合取范式。
中公式的主析取范式和主合取范式1)(1)求主析取范式求主析取范式( (p→q)p→q)r r ( (p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)p∧┐q∧┐r p∧┐q∧┐r m m4 4┐p∧r ┐p∧r ┐┐p∧p∧（（┐q∨q┐q∨q））∧r ∧r (┐(┐p∧┐q∧r)∨(┐p∧q∧r) p∧┐q∧r)∨(┐p∧q∧r) m m1 1∨m∨m3 3 q∧r q∧r (┐p∨p)∧q∧r (┐p∨p)∧q∧r (┐(┐p∧q∧r)∨(p∧q∧r) p∧q∧r)∨(p∧q∧r) m m3 3∨m∨m7 7 ( (p→q)p→q)r r m m1 1∨m∨m3 3∨m∨m4 4∨m∨m7 7 42例例例例2.8 2.8 2.8 2.8 求例求例求例求例2.72.72.72.7中公式的主析取范式和主合取范式中公式的主析取范式和主合取范式中公式的主析取范式和主合取范式中公式的主析取范式和主合取范式2)(2)求主合取范式求主合取范式( (p→q)p→q)r r (p∨r)∧(┐q∨r)∧(┐p∨q∨┐r) (p∨r)∧(┐q∨r)∧(┐p∨q∨┐r) ┐p∨q∨┐r ┐p∨q∨┐r M M5 5 p∨r p∨r p∨(q∧┐q)∨r p∨(q∧┐q)∨r ( (p∨q∨r)∧(p∨┐q∨r) p∨q∨r)∧(p∨┐q∨r) M M0 0∧M∧M2 2 ┐q∨r┐q∨r (p∧┐p)∨┐q∨r (p∧┐p)∨┐q∨r ( (p∨┐q∨r)∧(┐p∨┐q∨r) p∨┐q∨r)∧(┐p∨┐q∨r) M M2 2∧M∧M6 6 ( (p→q)p→q)r r M M0 0∧M∧M2 2∧M∧M5 5∧M∧M6 6 43主析取范式的用途主析取范式的用途 q求公式的成真赋值与成假赋值求公式的成真赋值与成假赋值q判断公式的类型判断公式的类型 q判断两个命题公式是否等值判断两个命题公式是否等值 q应用主析取范式分析和解决实际问题应用主析取范式分析和解决实际问题 44求公式的成真赋值与成假赋值求公式的成真赋值与成假赋值q若公式若公式A A中含中含n n个命题变项，个命题变项，A A的主析取范式含的主析取范式含s(0≤s≤2s(0≤s≤2n n) )个个极小项，则极小项，则A A有有s s个成真赋值，它们是所含极小项角标的二个成真赋值，它们是所含极小项角标的二进制表示，其余进制表示，其余2 2n n-s-s个赋值都是成假赋值。
个赋值都是成假赋值q在例在例2.82.8中，中，( (p→q)p→q)r r m m1 1∨m∨m3 3∨m∨m4 4∨m∨m7 7, ,各极小项均含三各极小项均含三个文字，因而各极小项的角标均为长为个文字，因而各极小项的角标均为长为3 3的二进制数，它们的二进制数，它们分别是分别是001001，，011011，，100100，，111111，这四个赋值为该公式的成真，这四个赋值为该公式的成真赋值赋值, ,其余的为成假赋值其余的为成假赋值q在例在例2.92.9中，中，p→q p→q m m0 0∨m∨m1 1∨m∨m3 3，，这三个极小项均含两个这三个极小项均含两个文字，它们的角标的二进制表示文字，它们的角标的二进制表示0000，，0101，，1111为该公式的成为该公式的成真赋值，真赋值，1010是它的成假赋值是它的成假赋值 45判断公式的类型判断公式的类型设公式设公式A A中含中含n n个命题变项，容易看出：个命题变项，容易看出：qA A为为重言式重言式当且仅当当且仅当A A的主析取范式含全部的主析取范式含全部2 2n n个个极小项qA A为为矛盾式矛盾式当且仅当当且仅当A A的主析取范式不含任何极的主析取范式不含任何极小项。
此时，记小项此时，记A A的主析取范式为的主析取范式为0 0qA A为为可满足式可满足式当且仅当当且仅当A A的主析取范式至少含一的主析取范式至少含一个极小项个极小项 46判断公式的类型判断公式的类型例例2.102.10 用公式的主析取范式判断公式的类型：用公式的主析取范式判断公式的类型：(1) ┐((1) ┐(p→q)∧q p→q)∧q (2) (2) p→(p∨q) p→(p∨q) (3) ((3) (p∨q)→rp∨q)→r解答解答(1)┐((1)┐(p→q)∧q p→q)∧q ┐ ┐（（┐p∨q┐p∨q））∧q ∧q (p∧┐q)∧q (p∧┐q)∧q 0 0 (2)p→(p∨q) (2)p→(p∨q) m m0 0∨m∨m1 1∨m∨m2 2∨m∨m3 3 (3)((3)(p∨q)→r p∨q)→r m m0 0∨m∨m1 1∨m∨m3 3∨m∨m5 5∨m∨m7 7 矛盾式矛盾式重言式重言式可满足式可满足式 47判断两个命题公式是否等值判断两个命题公式是否等值q设公式设公式A,BA,B共含有共含有n n个命题变项，按个命题变项，按n n个命题变项求出个命题变项求出A A与与B B的的主析取范式主析取范式A A‘与与B B’。
若若A A‘＝＝B B’, ,则则A AB B；；否则，否则，A A与与B B不不等值例例2.112.11 判断下面两组公式是否等值：判断下面两组公式是否等值：(1) (1) p p与与( (p∧q)∨(p∧┐q) p∧q)∨(p∧┐q) (2)(2) ( (p→q)→rp→q)→r与与( (ｐｐ∧∧q)→r q)→r (1) (1) p p p∧(┐q∨q) p∧(┐q∨q) (p∧┐q)∨(p∧q) (p∧┐q)∨(p∧q) m m2 2∨m∨m3 3 ( (p∧q)∨(p∧┐q) p∧q)∨(p∧┐q) m m2 2∨m∨m3 3 两公式等值两公式等值2) (2) ( (p→q)→r p→q)→r m m1 1∨m∨m3 3∨m∨m4 4∨m∨m5 5∨m∨m7 7 ( (ｐｐ∧∧q)→r q)→r m m0 0∨m∨m1 1∨m∨m2 2∨m∨m3 3∨m∨m4 4∨m∨m5 5∨m∨m7 7 两公式不等值两公式不等值解答解答 48应用主析取范式分析和解决实际问题应用主析取范式分析和解决实际问题例例2.122.12 某科研所要从 某科研所要从3 3名科研骨干名科研骨干A,B,CA,B,C中挑选中挑选1 1～～2 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)(4) 将将(3)(3)中公式化成析取式（最好是主析取范式）中公式化成析取式（最好是主析取范式）(5)(5) 这样每个小项就是一种可能产生的结果这样每个小项就是一种可能产生的结果去掉不符合题意的小项，即得结论去掉不符合题意的小项，即得结论 49应用主析取范式分析和解决实际问题应用主析取范式分析和解决实际问题设设 p:p:派派A A去，去，q:q:派派B B去，去，r:r:派派C C去去 由已知条件可得公式由已知条件可得公式 ( (p→r)∧(q→┐r)∧(┐r→(p∨q)) p→r)∧(q→┐r)∧(┐r→(p∨q)) 经过演算可得经过演算可得 ( (p→r)∧(q→┐r)∧(┐r→(p∨q)) p→r)∧(q→┐r)∧(┐r→(p∨q)) m m1 1∨m∨m2 2∨m∨m5 5 由于由于 m m1 1=┐p∧┐q∧r, m=┐p∧┐q∧r, m2 2=┐p∧q∧┐r, m=┐p∧q∧┐r, m5 5=p∧┐q∧r=p∧┐q∧r可知，选派方案有可知，选派方案有3 3种：种：( (a)Ca)C去，而去，而A,BA,B都不去。
都不去 (b)Bb)B去，而去，而A,CA,C都不去 (c)A,Cc)A,C去，而去，而B B不去解答解答 50由公式的主析取范式求主合取范式由公式的主析取范式求主合取范式 设公式设公式A A含含n n个命题变项个命题变项A A的主析取范式含的主析取范式含s(0 项q重言式无成假赋值，因而主合取范式不含任何极大项重言式无成假赋值，因而主合取范式不含任何极大项q将重言式的主合取范式记为将重言式的主合取范式记为1 1q可满足式的主合取范式中极大项的个数一定小于可满足式的主合取范式中极大项的个数一定小于2 2n n 53真值表与范式的关系真值表与范式的关系 qA AB B当且仅当当且仅当A A与与B B有相同的真值表，又当且仅当有相同的真值表，又当且仅当A A与与B B有有相同的主析取范式（主合取范式）相同的主析取范式（主合取范式）q真值表与主析取范式（主合取范式）是描述命题公式标真值表与主析取范式（主合取范式）是描述命题公式标准形式的两种不同的等价形式准形式的两种不同的等价形式 n n个命题变项共可产生个命题变项共可产生2 2n n个极小项（极大项）个极小项（极大项）可以产生的可以产生的主析取范式（主合取范式）数目为：主析取范式（主合取范式）数目为： 54本章主要内容本章主要内容q等值式与等值演算等值式与等值演算q基本的等值式，其中含：双重否定律、幂等律、交基本的等值式，其中含：双重否定律、幂等律、交换律、结合律、分配律、德换律、结合律、分配律、德·摩根律、吸收律、零摩根律、吸收律、零律、同一律、排中律、矛盾律、蕴含等值式、等价律、同一律、排中律、矛盾律、蕴含等值式、等价等值式、假言易位、等价否定等值式、归谬论。 等值式、假言易位、等价否定等值式、归谬论q与主析取范式及主合取范式有关的概念：简单合取与主析取范式及主合取范式有关的概念：简单合取式、简单析取式、析取范式、合取范式、极小项、式、简单析取式、析取范式、合取范式、极小项、极大项、主析取范式、主合取范式极大项、主析取范式、主合取范式 55第三节第三节 联结词的完备集联结词的完备集真值函数真值函数q问题的提出问题的提出–问问: 含含n个命题变项的所有公式共产生多少个命题变项的所有公式共产生多少个互不相同的真值表？个互不相同的真值表？–答案为答案为 个个, 为什么？为什么？ 56q真值函数的定义真值函数的定义–称定义域为称定义域为{00{00…0, 000, 00…1, 1, …, 11, 11…1}, 1}, 值域为值域为{0, 1}{0, 1}的函数为的函数为n n元真值函数元真值函数, , 定义域中定义域中的元素为的元素为2 2n n个长为个长为n n的的0, 10, 1组成的符号串组成的符号串. . 常用常用F: {0, 1}F: {0, 1}n n{0, 1} {0, 1} 表示表示F F是是n n元真值函数元真值函数. . –易知易知, , 全体全体n n元函数共有元函数共有 个个. . 1元真值函数元真值函数 p 0 0 0 1 1 1 0 1 0 1 57q命题公式与真值函数命题公式与真值函数–对于任何一个含对于任何一个含n个命题变项的命题公式个命题变项的命题公式A, 都存在惟一的一个都存在惟一的一个n元真值函数元真值函数F为为A的真的真值表值表, 等值的公式对应的真值函数相同等值的公式对应的真值函数相同. 于于是解决了是解决了1提出的问题提出的问题. n=2时时, 每个命题公每个命题公式的真值表都可以在书上表式的真值表都可以在书上表2.6中找到中找到. 例例如如: pq, p q, ( p q)((pq) q), …, 都对表都对表2.6中的中的F13(2) 58p q0 00 11 01 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1p q0 00 11 01 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 12 2元真值函数元真值函数 59联结词的完备集联结词的完备集q定义定义–定义定义2.7 设设S是一个联结词集合是一个联结词集合, 如果任何如果任何n(n 1) 元真值函数都可以由仅含元真值函数都可以由仅含S中的联结中的联结词构成的公式表示词构成的公式表示, 则称则称S是联结词完备集是联结词完备集–说明说明: 若若S是联结词完备集是联结词完备集, 则任何命题公式则任何命题公式都可由都可由S中的联结词所表示中的联结词所表示q一些联结词完备集一些联结词完备集–定理定理2.6 S = { , , }是联结词完备集是联结词完备集–证明的关键证明的关键: 主析取主析取(主合取主合取)范式存在惟一性范式存在惟一性定理定理 60q推论推论 以下联结词集都是完备集以下联结词集都是完备集–(1)S1 = { , , , }–(2)S2 = { , , , , }–(3)S3 = { , }–(4)S4 = { , }–(5)S5 = { , }q证明线索证明线索: –若若S是完备集是完备集, 则则S中再加入新的联结词后所得中再加入新的联结词后所得S’仍为完备集仍为完备集, 因而因而(1), (2)得证得证q注意到注意到: – A B ( AB)–A B ( AB)– ABA B–(3), (4), (5)得证得证 61复合联结词复合联结词 与与 q定义定义2.8 设设p, q为两个命题为两个命题–p q (p q), 称为与非联结词称为与非联结词–p q (p q), 称为或非联结词称为或非联结词–我们可以称我们可以称 与与 为复合联结词为复合联结词q定理定理2.7 { }与与{ }为联结词完备集为联结词完备集. 62q证明线索证明线索: – { , , }为完备集为完备集, 而而– p pp (p p) p p ①①–p q ( pq) pq (p p) (q q) ②②–p q (p q) (p q) (p q) (p q) ③③ –由由①①, ②②, ③③作为归纳基础作为归纳基础, 可知可知{ }为完备集为完备集q{ }与与{ }在计算机硬件设计中均有应用在计算机硬件设计中均有应用 复合联结词复合联结词 与与 632.4 可满足性问题与消解法可满足性问题与消解法q不含任何文字的简单析取式称作不含任何文字的简单析取式称作空简单析取式空简单析取式, ,记作记作 ( ( ).).规定规定 是不可满是不可满足的足的. . q约定约定: :简单析取式不同时含某个命题变项和它的否定简单析取式不同时含某个命题变项和它的否定qS:合取范式合取范式, C:简单析取式简单析取式, l:文字文字, :赋值赋值, 带下角标或带下角标或 q文字文字l的补的补lc:若若l=p,则则lc= p;若若l= p,则则lc=p.qS S :S是可满足的当且仅当是可满足的当且仅当S 是可满足的是可满足的q定义定义2.9 设设C1=l C1 , C2=lc C2 , C1 和和C2 不含不含l和和lc, 称称C1C2 为为C1和和C2(以以l和和lc为为消解文字消解文字)的的消解式消解式或或消解结果消解结果, 记作记作Res(C1,C2)q例如例如, Res( p q r, p qs)= q rs 64消解规则消解规则q定理定理2.8 C1 C2 Res(C1,C2)q证证 记记C= Res(C1,C2)=C1C2 , 其中其中l和和lc为消解文字为消解文字, C1=l C1 , C2=lc C2 , 且且C1 和和C2 不含不含l和和lc. q 假设假设C1 C2是可满足的是可满足的, 是它的满足赋值是它的满足赋值, 不妨设不妨设 (l)=1. C2必含有文必含有文字字l l, lc且且 (l )=1. C中含有中含有l , 故故 满足满足C.q 反之反之, 假设假设C是可满足的是可满足的, 是它的满足赋值是它的满足赋值. C必有必有l 使得使得 (l )=1, 不不妨设妨设C1 含含l , 于是于是 满足满足C1. 把扩张到把扩张到l(和和lc)上上:q若若l=p, 则令则令 (p)=0; 若若lc=p, 则令则令 (p)=1. 恒有恒有 (lc)=1, 从而从而 满足满足C2. 得证得证C1 C2是可满足的是可满足的.q注意注意: C1 C2与与Res(C1,C2)有相同的可满足性有相同的可满足性, 但不一定等值但不一定等值. 65消解序列与合取范式的否证消解序列与合取范式的否证q定义定义2.10 设设S是一个合取范式是一个合取范式, C1,C2,,Cn是一个简单析取式序列是一个简单析取式序列. 如果如果对每一个对每一个i(1 i n), Ci是是S的一个简单析取式或者是的一个简单析取式或者是Res(Cj,Ck)(1 j 深刻理解等值式的概念q牢记牢记2424个基本等值式，这是等值演算的基础；能熟练地应用个基本等值式，这是等值演算的基础；能熟练地应用它们进行等值演算它们进行等值演算 q了解简单析取式、简单合取式、析取范式、合取范式的概念了解简单析取式、简单合取式、析取范式、合取范式的概念 q深刻理解极小项及极大项的定义及它们的名称，及名称下角深刻理解极小项及极大项的定义及它们的名称，及名称下角标与成真赋值的关系标与成真赋值的关系q熟练掌握求公式的主析取范式的方法熟练掌握求公式的主析取范式的方法q熟练掌握由公式的主析取范式求公式的主合取范式的方法熟练掌握由公式的主析取范式求公式的主合取范式的方法q会用公式的主析取范式（主合取范式）求公式的成真赋值、会用公式的主析取范式（主合取范式）求公式的成真赋值、成假赋值成假赋值 71本章典型习题本章典型习题q用等值演算法证明重言式和矛盾式用等值演算法证明重言式和矛盾式q用等值演算法证明等值式用等值演算法证明等值式q求公式的主析取范式和主合取范式求公式的主析取范式和主合取范式q用主范式判断两个公式是否等值用主范式判断两个公式是否等值q求解实际问题求解实际问题 72练习题练习题1.设设A与与B均为含均为含n个命题变项的公式个命题变项的公式, 判断下列命题是判断下列命题是否为真？否为真？①①AB当且仅当当且仅当A与与B有相同的主析取范式有相同的主析取范式n(1)为真为真, 这是显然的这是显然的②②若若A为重言式为重言式, 则则A的主合取范式为的主合取范式为0n(2)为假为假. 注意注意, 任何公式与它的主范式是等值任何公式与它的主范式是等值的的, 显然重言式不能与显然重言式不能与0等值等值. 重言式的主合取重言式的主合取范式不含极大项范式不含极大项, 因而主合取范式为因而主合取范式为1. 73③③若若A为矛盾式为矛盾式, 则则A的主析取范式为的主析取范式为1n(3)的分析类似于的分析类似于(2), 矛盾式的主合取范式为矛盾式的主合取范式为0.④④任何公式都能等值地化成任何公式都能等值地化成{ , }中的公式中的公式n(4)为假为假, 因为因为{ , }不是完备集不是完备集, 比如矛盾式比如矛盾式 (pq) q不能化成不能化成{ , }中的公式中的公式.⑤⑤任何公式都能等值地化成任何公式都能等值地化成{ , , }中的公式中的公式n(5)为真为真, 注意注意{ , , }的子集的子集{ , }为完备集为完备集.练习题练习题 74练习题练习题2.通过求主范式判公式类型通过求主范式判公式类型–(1)(pq)( qp)–(2) (pq) q–(3)(pq)p 75用等值演算法求解用等值演算法求解q(1) q (pq)( qp)q ( p q) (qp) (消去消去) ①①q (pq) (qp) ( 内移内移) ②②q (pq) ( p q) (p q) ( pq) ③③q m2 m1 m3 m0 ④④q m0 m1 m2 m3 ⑤⑤q 1 ⑥⑥q问由问由②②如何得如何得③③？？q⑤⑤为主析取范式为主析取范式, ⑥⑥为主合取范式为主合取范式q结论结论: (1)为重言式为重言式 76用等值演算法求解用等值演算法求解q(2)q (pq) ( p q) q ①①q pq q ②②q 0 ③③ q M0 M1 M2 M3 ④④q问问: 由由②②如何得如何得③③？？q③③为主析取范式为主析取范式, ④④为主合取范式为主合取范式q结论结论: (2)为矛盾式为矛盾式. 77用等值演算法求解用等值演算法求解q(3) q(pq)pq m0 m1 ①①q M2 M3 ②②q请自己等值演算得请自己等值演算得①①与与②②q结论结论: (3)为可满足式为可满足式q请用真值表再解此题请用真值表再解此题 78q已知命题公式已知命题公式A中含中含3个命题变项个命题变项p, q, r, 并知道它的成真并知道它的成真赋值为赋值为001, 010, 111, 求求A的主析取范式和主合取范式的主析取范式和主合取范式, 及及A对应的真值函数对应的真值函数.q答案答案–A的主析取范式为的主析取范式为m1 m2 m7–A的主合取范式为的主合取范式为M0 M3 M4 M5 M6 –设设A对应的真值函数为对应的真值函数为F, 则则–F(001)=F(010)=F(111)=1–F(000)=F(011)=F(100)=F(101)=F(110)=0–试说明以上得出答案的理由试说明以上得出答案的理由 79q在以下各联结词集中各求一个公式与在以下各联结词集中各求一个公式与 A = (pq) r等值等值. –(1){ , , }–(2){ , }–(3){ , }–(4){ , }–(5){ }–(6){ } 80–(1) (pq) r ( pq) r (满足要求满足要求)–(2) (pq) r (p q) r (满足要求满足要求)–(3) (pq) r ( pq) r ( ( pq)r) (满足要求满足要求)–(4)(pq) r ((pq)r) (满足要求满足要求)–(5) (pq) r (p q) r (p q) r ((p q) r) ((p q) r) (满足要求满足要求) 81–(6) (pq) r ( pq) r ( ( pq)r) ( pq)r ((p p) (q q) (r r) (满足要求满足要求)–说明说明: 以上各题答案不惟一以上各题答案不惟一–要求要求: 对每小题分别给出不同形式的答案对每小题分别给出不同形式的答案 82q某公司要从赵、钱、孙、李、周五名新毕业的大学生中选某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习派一些人出国学习. 选派必须满足以下条件选派必须满足以下条件: –若赵去若赵去, 钱也去钱也去.–李、周两人中必至少有一人去李、周两人中必至少有一人去–钱、孙两人中去仅去一人钱、孙两人中去仅去一人.–孙、李两人同去或同不去孙、李两人同去或同不去.–若周去若周去, 则赵、钱也去则赵、钱也去. q用等值演算法分析该公司如何选派他们出国？用等值演算法分析该公司如何选派他们出国？ 83q解此类问题的步骤应为解此类问题的步骤应为: ①①将简单命题符号化将简单命题符号化②②写出各复合命题写出各复合命题③③写出由写出由②②中复合命题组成的合取式中复合命题组成的合取式④④将将③③中公式化成析取式中公式化成析取式(最好是主析取范式最好是主析取范式) 84q解解q1. 设简单命题并符号化设简单命题并符号化q设设 p: 派赵去，派赵去，q: 派钱去，派钱去，r: 派孙去，派孙去，s: 派李去，派李去，u: 派周去派周去q2. 写出复合命题写出复合命题–(1) 若赵去，钱也去若赵去，钱也去 pq–(2) 李、周两人中至少有一人去李、周两人中至少有一人去 s u–(3) 钱、孙两人中去且仅去一人钱、孙两人中去且仅去一人 (qr) ( q r)–(4) 孙、李两人同去或同不去孙、李两人同去或同不去 (r s) ( rs)–(5) 若周去，则赵、钱也去若周去，则赵、钱也去 u(p q) 85q3. 设设(1)—(5)构成的合取式为构成的合取式为A– A = (pq) (s u) ((qr) ( q r)) ((r s) ( rs)) (u(p q))q4. 化成析取式化成析取式–A ( pq r su) (p qrs u)q结论结论: 由由④④可知可知, A的成真赋值为的成真赋值为00110与与11001, 因而派孙、因而派孙、李去李去(赵、钱、周不去赵、钱、周不去)或派赵、钱、周去或派赵、钱、周去(孙、李不去孙、李不去) 86qA的演算过程的演算过程–A ( p q) ((qr) ( q r)) –(s u) ( u (p q)) ((r s) ( rs)) (交换律交换律)q而而–B1=( p q) ((qr) ( q r))– (( p qr) ( pq r) (qr)) (分配律分配律)–B2=(s u) ( u (p q))– ((su) (p q s) (p q u)) (分配律分配律)q又又–B1 B2 ( p qr su) ( pq r su) – (qr su) (p qr s)– (p qr u) 87q再令再令 ((r s) ( rs))=B3q则则–B1 B2 B3 ( pq r su)– (p qrs u)q注意注意: 在以上演算中多次用矛盾律在以上演算中多次用矛盾律q要求要求: 自己演算一遍自己演算一遍 88例题例题求公式求公式( (p∧q)∨(┐p∧r)p∧q)∨(┐p∧r)的主析取范式和主合取范式。 的主析取范式和主合取范式解答解答p pq qr r( (p∧q)∨(┐p∧r)p∧q)∨(┐p∧r)0 00 00 00 00 00 01 11 10 01 10 00 00 01 11 11 11 10 00 00 01 10 01 10 01 11 10 01 11 11 11 11 1主析取范式为主析取范式为 ( (┐┐p∧p∧┐┐q∧r)∨(q∧r)∨(┐┐p∧q∧r)∨(p∧q∧p∧q∧r)∨(p∧q∧┐┐r)∨r)∨( (p∧q∧r)p∧q∧r) 主合取范式为主合取范式为 (p∨q∨r)∧(p∨(p∨q∨r)∧(p∨┐┐q∨r)∧(q∨r)∧(┐┐p∨q∨r)∧p∨q∨r)∧( (┐┐p∨q∨p∨q∨┐┐r)r) 89例题例题甲、乙、丙、丁四个人有且只有两个人参加围棋比赛关于谁甲、乙、丙、丁四个人有且只有两个人参加围棋比赛关于谁参加比赛，下列四个判断都是正确的：参加比赛，下列四个判断都是正确的：(1)(1)甲和乙只有一人参加比赛甲和乙只有一人参加比赛2)(2)丙参加，丁必参加丙参加，丁必参加3)(3)乙或丁至多参加一人乙或丁至多参加一人4)(4)丁不参加，甲也不会参加。 丁不参加，甲也不会参加请推断出哪两个人参加围棋比赛请推断出哪两个人参加围棋比赛 设设a a：：甲参加了比赛甲参加了比赛b b：：乙参加了比赛乙参加了比赛 c c：：丙参加了比赛丙参加了比赛d d：：丁参加了比赛丁参加了比赛1) ((1) (a∧a∧┐┐b)∨(b)∨(┐┐a∧b)a∧b)(2) (2) c→dc→d(3) (3) ┐┐( (b∧d)b∧d)(4) (4) ┐┐d→ d→ ┐┐a a 解答解答 90( (( (a∧a∧┐┐b)∨(b)∨(┐┐a∧b)a∧b))∧()∧(c→dc→d)∧()∧(┐┐(b∧d)(b∧d))∧()∧(┐┐d→ d→ ┐┐a a) )( (a∧a∧┐┐b∧b∧┐┐c∧dc∧d)∨()∨(a∧a∧┐┐b∧db∧d)∨()∨(┐┐a∧b∧a∧b∧┐┐c∧c∧┐┐d d) )根据题意条件，有且仅有两人参赛，根据题意条件，有且仅有两人参赛，故﹁故﹁a∧b∧a∧b∧﹁﹁c∧c∧﹁﹁d d为为0 0，，所以所以( (a∧a∧﹁﹁b∧b∧﹁﹁c∧dc∧d)∨()∨(a∧a∧﹁﹁b∧db∧d) )为为1 1，，即甲和丁参加了比赛。 即甲和丁参加了比赛 ( (a∨b)∧(c∨d) a∨b)∧(c∨d) ( (a∧c)∨(b∧c)∨(a∧d)∨(b∧d) a∧c)∨(b∧c)∨(a∧d)∨(b∧d) 说明说明 91本章作业本章作业习题二习题二4 4、、8 8、、1010、、2323、、2727、、3030 。
数学好玩2《搭配中的学问》课件 北师大三年级数学上册.pptx讲课资料以法治为保障铸牢中华民族共同体意识红色党政风深入学习中央民族工作会议党课PPT课件.pptx苍南县马站镇库下村生活污水处理工程施工组织设计.docx南宁大桥钢结构设计.ppt水利工程竣工验收资料编制顺序大全.doc合并财务报表分步合并与一次合并的差异探析.docx合同履约评价表模板.docx气体引射器的试验研究及应用.pdf浅谈中西医差异的根源及相关不同点.docx机器人协作与集成-洞察研究.docx双电源智能控制器 ATS022(new).pdf高中英语2025届高考完形填空高频短语（共308个）.doc
