第一章命题逻辑(2)

1、例如例如:公式公式,Apq Bpq Cpq p qA BC 0 0 111 0 1 111 1 0 000 1 1 111n个命题变元共产生个命题变元共产生 个不同赋值个不同赋值,在每个赋值在每个赋值下下,命题公式的值只有命题公式的值只有0和和1两个值两个值.于是于是n个命题变元的真值表共有个命题变元的真值表共有 种不同情种不同情况况. 2n22n注注：关于：关于n个命题变元个命题变元 ,可以构造多少个可以构造多少个真值表呢真值表呢?12,nppp许多公式有相同的真值表许多公式有相同的真值表等值式等值式n个命题变元个命题变元-形成的无穷个命题公式中不等形成的无穷个命题公式中不等值的有值的有 个

2、个22n一、等值式的概念一、等值式的概念 定义定义1.3.1 设设A, B为两个命题公式，若为两个命题公式，若A, B构成的构成的等价式等价式 为重言式，则称为重言式，则称A与与B是等值的，是等值的，记作记作 ABAB如上例如上例永永真真式式例如例如:公式公式,Apq Bpq Cpq p qA BC ABBCAC 0 0 111111 0 1 111111 1 0 000111 1 1 111111A与与B等值等值, ,记为记为AB 判断等值式有如下方法：判断等值式有如下方法： 1.真值表真值表 2.等值演算等值演算 3.范式范式 注意注意 , ，= 的区别的区别 的性质的性质二、用真值表判断

3、公式的等值二、用真值表判断公式的等值 例例1.3.1 判断下面两个公式是否等值：判断下面两个公式是否等值： 与与 pqpq 解解 :用真值表法判断用真值表法判断 是否为重言式是否为重言式.pqpq p q p q(p q) (p q) p q (p q) ( p q) 0 0 110111 0 1 101001 1 0 011001 1 1 001001从表中可知它是重言式，因而从表中可知它是重言式，因而 与与 等值，即等值，即pqpq pqpq 例例1.3.2 判断下列各组公式是否等值：判断下列各组公式是否等值： （1） 与与 （2） 与与pqrpqrpqrpqr解解: 下表为下表为 3个公

4、式的真值表个公式的真值表p q r0 0 01100 0 11110 1 01100 1 11111 0 01111 0 11111 1 00001 1 1111pqrpqrpqr 与与 等值，等值， 与与 不等值不等值pqrpqrpqrpqr三、等值演算三、等值演算 16组重要的等值式组重要的等值式,公式中出现的公式中出现的A,B,C仍然是元语言符号，仍然是元语言符号，它们代表任意的命题公式它们代表任意的命题公式1. 双重否定律双重否定律 AA 2. 幂等律幂等律,AAA AAA3. 交换律交换律,ABBA ABBA 4. 结合律结合律 ABCABCABCABC5. 分配律分配律 A(BC)

5、 (AB)(AC)A(BC) (AB)(AC)6. 德摩根律德摩根律()()ABABABAB 7. 吸收律吸收律 A(AB) A ， A(AB) A 8. 零律零律A1 1 ， A0 09. 同一律同一律A0 A ， A1 A 10. 排中律排中律1AA (11)矛盾律矛盾律 0AA (12)蕴涵等值式蕴涵等值式ABAB (13)等价等值式等价等值式()()ABABBA()()ABABA (16)归谬论归谬论 (14)假言易位假言易位 ABBA ABAB (15)等价否定等值式等价否定等值式 置换定理置换定理: : 设设 是含公式是含公式 的命题公式，的命题公式， 是用公式是用公式 置换了置换

6、了 中所有的中所有的 后得后得到的命题公式，若到的命题公式，若 则则 AA BB BA AABA例：例： (置换规则置换规则)pqr (蕴涵等值式蕴涵等值式)pqr 例例1.3.2 判断下列各组公式是否等值：判断下列各组公式是否等值： （1） 与与 pqrpqr解解: 下表为下表为 3个公式的真值表个公式的真值表p q r0 0 0110 0 1110 1 0110 1 1111 0 0111 0 1111 1 0001 1 111pqrpqr 与与 等值等值 pqrpqr解：解： (置换规则置换规则)pqr (蕴涵等值式蕴涵等值式)pqr pqr (蕴涵等值式蕴涵等值式)pqr (结合律结合

7、律)pqr （德摩根律）（德摩根律）pqr (蕴涵等值式蕴涵等值式)例例1.3.1 判断下面两个公式是否等值：判断下面两个公式是否等值： 与与 pqpq 解解 :用真值表法判断用真值表法判断 是否为重言式是否为重言式.pqpq p q p q(p q) (p q) p q (p q) ( p q) 0 0 110111 0 1 101001 1 0 011001 1 1 001001从表中可知它是重言式，因而从表中可知它是重言式，因而 与与 等值，即等值，即pqpq pqpq 例例1.3.3 用等值演算法验证等值式：用等值演算法验证等值式： (pq)r (pr)(qr) 证明证明: (pr)(

8、qr) (pr) (qr) (蕴涵等值式蕴涵等值式) (p q)r (分配律分配律) (p q)r (德摩根律德摩根律) (p q) r (蕴涵等值式蕴涵等值式)例例1.3.4 用等值演算判断下列公式的类型：用等值演算判断下列公式的类型： （1）(pq)pq （2）(p(pq)r （3）p(pq)p)q) 解解: : (1）(pq)pq 最后结果说明（最后结果说明（1）中公式是）中公式是重言式重言式. (pq)pq (pq)p)q (pq)p)q (pq)p)q (pp)(qp)q (1(qp)q (qq)p 1p 1 （2）(p(pq)r 最后结果说明最后结果说明（2）中公式是中公式是矛盾式

9、矛盾式. . 0r (ppq)r 0 (ppq)r （3）p p(p pq q)p p)q q) ) 最后结果说明最后结果说明（3）中公式不是重言式，中公式不是重言式，00，01都是成都是成假赋值假赋值. .并且也不是矛盾式，因为并且也不是矛盾式，因为1010，1111都是成真赋值都是成真赋值. . p p(pp)(qq)q) p(qpq) p(0(qp)q) p(pq)p)q) p1 1.4 联结词全功能集联结词全功能集 一、一、n元真值函数元真值函数 一般地，函数一般地，函数F : 0,1n 0,1称为称为n元真值元真值函数函数 n元真值函数共有元真值函数共有 个个. .22n 每个真值函

10、数对应无穷多个与之等值的命每个真值函数对应无穷多个与之等值的命题公式题公式. .每个命题公式对应唯一的与之等值的真每个命题公式对应唯一的与之等值的真值函数值函数. . 对于含有两个命题变元的公式，理论上讲可以书写对于含有两个命题变元的公式，理论上讲可以书写出无穷多个公式，但互不等值的公式恰有出无穷多个公式，但互不等值的公式恰有 =16个。对应着个。对应着16个不同的真值表（真值表共有个不同的真值表（真值表共有 4行，行，行上的每个记入值又可在行上的每个记入值又可在0、1中任取其一，因此构中任取其一，因此构成成 个不同的真值表），亦即对应着个不同的真值表），亦即对应着16个真值函个真值函数数Fi

11、（i=0，1，15），），其中其中Fi：00，01，10，110，1，如下表所示，如下表所示222222下表下表2元真值函数元真值函数 定义定义1.4.1 设设p、q为两个为两个命题命题，复合命题复合命题“如果如果 p 则则 q的否定的否定”称作称作p , q蕴含蕴含的否的否定。定。记作记作p q, , 称为称为蕴含蕴含的否定联结词的否定联结词. . p q为真当且仅当为真当且仅当p 为真为真q q为假为假. . 即即 p q (p q) CCCC逻辑设计中常用这些联结词逻辑设计中常用这些联结词 定义定义1.4.2 设设p、q为两个为两个命题命题，复合命题复合命题“ “ p , q中恰有一个成

12、立中恰有一个成立”称作称作p , q的的排斥排斥或或或或异或异或, , 记作记作p q, , 称为称为排斥或排斥或或或异异或或联结词联结词. . p q为真当且仅当为真当且仅当p , q中恰有一个为真中恰有一个为真. . 即即 p q (pq)(pq) (p q) (p q) pq(1)(2)()()(3)()()(4)0(5)0(6)1A BBAA BCAB CAB CABA AAAAA ()AC异或有以下性质：异或有以下性质：定义定义1.4.3 设设p、q为两个命题，复合命题为两个命题，复合命题“p与与q的否定式的否定式” ” 称作称作p ,q的的与非式与非式，记作，记作 p q .符号符

13、号 称作称作与非联结词与非联结词. .p q为假当且仅为假当且仅当当p与与q同时为真同时为真. . 即即 p q (pq） 定义定义1.4.4 设设p、q为两个命题，复合命题为两个命题，复合命题“p或或q的否定式的否定式” ” 称作称作p ,q的的或非式或非式，记作，记作 p q .符号符号 称作称作或非联结词或非联结词. .p q为真当且仅为真当且仅当当p与与q同时为假同时为假. . p q (pq） 二、联结词全功能集二、联结词全功能集 定义定义1.4.5 设设S是一个联结词集合，如果任何是一个联结词集合，如果任何n(n1)元真值函数都可以由仅含元真值函数都可以由仅含S中的联结中的联结词构

14、成的公式表示，则称词构成的公式表示，则称S是联结词完备集是联结词完备集或全功能集或全功能集. . 定理定理1.4.1 S=,是联结词全功能集是联结词全功能集. . 定义定义1.4.6 对于一个联结词集合来说，如果集对于一个联结词集合来说，如果集合中的某个联结词可由集合中的其他联结词合中的某个联结词可由集合中的其他联结词来定义，则称此联结词为来定义，则称此联结词为冗余的联结词冗余的联结词。定义定义1.4.7 不含冗余联结词的全功能集称为不含冗余联结词的全功能集称为极极小全功能集小全功能集 证证: : (1)，(2)的成立是显然的的成立是显然的. . (1)(2)中含有冗中含有冗余的联结词余的联结

15、词(3)(4)(5)中不中不含有冗余的联含有冗余的联结词结词, , 是极小是极小全功能集全功能集推论推论 以下联结词集都是完备集以下联结词集都是完备集-全功能集全功能集： 11,S 22,S 33,S 44,S 55,S (3) 由于由于 是联结词完备集，因而任何真值函是联结词完备集，因而任何真值函数都可以由仅含数都可以由仅含S中的联结词的公式表示中的联结词的公式表示.同时对于任同时对于任意公式意公式因而任意真值函数都可以由仅含因而任意真值函数都可以由仅含 中的联结词的公中的联结词的公式表示，所以式表示，所以 是联结词完备集是联结词完备集., ,S , ,A B ABABAB 3S3S 45A

16、BABABAB 定理定理1.4.2 都是联结词完备集都是联结词完备集. . pq ( pq) ( pq) (pq)(pq) 而而p (pp） pp 证证: : 已知已知,为联结词完备集，因而只需证为联结词完备集，因而只需证明其中的每个联结词都可以由明其中的每个联结词都可以由定义即可定义即可. . ,由上可知是联结词完备集，类似可证是联结由上可知是联结词完备集，类似可证是联结词完备集词完备集 pq ( pq) (pq) pq (p p)(q q) 例例1.4.1：将公式将公式 化成仅含化成仅含 的的公式形式公式形式pq, 解：解：pqpq pq pq pqqpqpq pq pq pqpq ppq

17、ppq1.5 对偶与范式对偶与范式在在1.3节基本公式中多数是成对出现的节基本公式中多数是成对出现的, ,如如: :结合律结合律一、对偶式一、对偶式A BCAB CA BCAB C这些公式是对偶的这些公式是对偶的.定义定义1.5.1 在仅含在仅含 、 的命题公式的命题公式A中中, ,将将换成换成, , 换成换成, ,若若A中含有中含有0或或1, ,就就将将0换成换成1, ,1换成换成0, ,所得命题公式称为所得命题公式称为A的的对对偶式偶式, ,记为记为A*.性质性质: : (A*)*=A.如如:(1) pq 与与 pq (2) pqr 与与 pqr (3) (pq)1 与与 (pq)0 互为

18、对偶式互为对偶式定理定理1.5.1 设设A和和A*互为对偶式互为对偶式, ,p1, p2 , pn是是出现在出现在A和和A*中的全部命题变元中的全部命题变元. .若将若将A和和A*写成写成n元函数形式元函数形式, ,则则同理同理*, ,ApqrAp q r *12121,nnA p ppAppp *12122,nnApppAp pp于是于是 *, ,A p q rApqr*,Apqrpqr , ,A p q rpqr *, ,Ap q rpqr 如如: :, ,A p q rpqr 推论推论: : A为重言式为重言式 当且仅当当且仅当 A*为矛盾式为矛盾式. . 每种数字标准形都能提供很多信息

19、，如代每种数字标准形都能提供很多信息，如代数式的因式分解可判断代数式的根情况数式的因式分解可判断代数式的根情况. .逻逻辑公式在等值演算下也有标准形辑公式在等值演算下也有标准形-范式，范式，范式有两种：析取范式和合取范式范式有两种：析取范式和合取范式. .定理定理1.5.2 ( (对偶原理对偶原理) )设设A, ,B为两个命题公为两个命题公式式. .若若A B, ,则则A* B* 二二 简单合取式和简单析取式简单合取式和简单析取式定义定义1.5.2 命题变项及其否定统称作命题变项及其否定统称作文字文字. .仅有有限仅有有限个文字构成的析取式称作个文字构成的析取式称作简单析取式简单析取式. .仅

20、有有限个仅有有限个文字构成的合取式称作文字构成的合取式称作简单合取式简单合取式. . p , q等为一个文字构成简单析取式等为一个文字构成简单析取式 pp ，pq等为等为2个文字构成的简单析取式个文字构成的简单析取式 pqr , pqr等为等为3个文字构成的简单析个文字构成的简单析取式取式 p, q等为一个文字构成的简单合取式等为一个文字构成的简单合取式 pp，pq等为等为2个文字构成的简单合取式个文字构成的简单合取式 pqr,ppq等为等为3个文字构成的简单合取个文字构成的简单合取式式 应该注意，一个文字既是简单析取式，又是简应该注意，一个文字既是简单析取式，又是简单合取式单合取式. .为方

21、便起见，有时用为方便起见，有时用 表示表示s个简单析取式或个简单析取式或s个简单合取式个简单合取式. . 12,SA AA定理定理1.5.1 （1）一个简单析取式是）一个简单析取式是重言式重言式当且仅当它当且仅当它同时含某个命题变项及它的否定式同时含某个命题变项及它的否定式. （2）一个简单合取式是）一个简单合取式是矛盾式矛盾式当且仅当它当且仅当它同时含有某个命题变项及它的否定式同时含有某个命题变项及它的否定式.三三 范式范式 析取范式和合取范析取范式和合取范式式定义定义1.5.3 （1）析取范式：析取范式：由有限个简单合取式构成的析由有限个简单合取式构成的析取式取式. .（2）合取范式合取范

22、式：由有限个简单析取式构成的合由有限个简单析取式构成的合取式取式. .（3）范式范式：析取范式与合取范式的统称析取范式与合取范式的统称. . 设设Ai(i=1,2,s)为简单合取式，为简单合取式， 则则A=A1A2As为析取范式为析取范式. 例如，例如，A1=pq，A2=qr，A3=p，则由，则由A1, A2, A3构造的析取范式为构造的析取范式为 A=A1A2A3=(pq)(qr)p 设设Ai(i=1,2,s)为简单析取式，则为简单析取式，则A=A1A2As为合取范式为合取范式. . 例如，取例如，取A1=pqr，A2=pq，A3=r，则由，则由A1, A2, A3组成的合取范式为组成的合取

23、范式为 A=A1A2A3=(pqr)(pq)r 形如形如pqr的公式既是一个简单合取的公式既是一个简单合取式构成的析取范式，又是由三个简单析取式式构成的析取范式，又是由三个简单析取式构成的合取范式构成的合取范式. 类似地，形如类似地，形如pqr的公式既是含三的公式既是含三个简单合取式的析取范式，又是含一个简个简单合取式的析取范式，又是含一个简单析取式的合取范式单析取式的合取范式. 定理定理1.5.2 （1 1）一个析取范式是）一个析取范式是矛盾式矛盾式当且仅当它的每当且仅当它的每个简单合取式都是矛盾式个简单合取式都是矛盾式. .（2 2）一个合取范式是）一个合取范式是重言式重言式当且仅当它的每

24、当且仅当它的每个简单析取式都是重言式个简单析取式都是重言式. . 定理定理1.4.3 （范式存在定理）任一命题公式都（范式存在定理）任一命题公式都存在着与之等值的析取范式与合取范式存在着与之等值的析取范式与合取范式. . 证明证明 : :首先，我们观察到在范式中不出现联结词首先，我们观察到在范式中不出现联结词 与与 ，由蕴涵等值式与等价等值式可知，由蕴涵等值式与等价等值式可知 其次，在范式中不出现如下形式的公式：其次，在范式中不出现如下形式的公式： 对其利用双重否定律和德摩根律，可得对其利用双重否定律和德摩根律，可得 ,ABABABABAB 因而在等值的条件下，可消去任何公式中的联结词因而在等

25、值的条件下，可消去任何公式中的联结词 和和 . . ,AABABAAABABABAB 再次，在析取范式中不出现如下形式的公式：再次，在析取范式中不出现如下形式的公式： A(BC) 在合取范式中不出现如下形式的公式：在合取范式中不出现如下形式的公式： A(BC) 利用分配律，可得利用分配律，可得 A(BC) (AB)(AC) A(BC) (AB)(AC) 综合上述综合上述3步，可将任一公式化成与之等值的析取范步，可将任一公式化成与之等值的析取范式或合取范式式或合取范式. .求范式可使用如下步骤：求范式可使用如下步骤： 1.消去联结词消去联结词 , 2.否定号的消去（利用双重否定律）或内移否定号的

26、消去（利用双重否定律）或内移（利用德摩根律）（利用德摩根律）. 3.利用分配律：利用利用分配律：利用对对的分配律求析取范的分配律求析取范式，式，对对的分配律求合取范式的分配律求合取范式. 例例1.5.1 求下面公式的析取范式与合取范式求下面公式的析取范式与合取范式: : (pq)r)(pqr) (否定号内移）否定号内移） (pr)(qr)(pqr) （对对分配律）分配律） 合合取取范范式式解解:(1):(1)先求合取范式先求合取范式 (p q) r (p q) r (pq)r)(rpq) (消去消去 ） (pq) r)(r (pq) （消去（消去 ） (pq) r (消去消去 ） （2）求析取

27、范式求析取范式 求析取范式与求合取范式的前两步是相求析取范式与求合取范式的前两步是相同的，只是在利用分配律时有所不同同的，只是在利用分配律时有所不同. .因而可以用因而可以用（1）中前四步的结果，接中前四步的结果，接着进行着进行对对分配律演算分配律演算. .析取范式析取范式命题公式的析取范式是不唯一的命题公式的析取范式是不唯一的. .同样，同样，合取范式也是不唯一的合取范式也是不唯一的. .(pq)r)(pqr)(pqr)(pr)(qr)(pqp)(pqq)(pqr)(rp)(rq)(rr)(p q) r四四 主范式主范式: :主析取范式和主合取范式主析取范式和主合取范式 定义定义1.5.4

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

29、 ,r r 形成的极小项与极大项形成的极小项与极大项一般情况下一般情况下: :n个个命题变项共可产命题变项共可产生生2n个不同的个不同的极极小小项项 ( (极大项极大项).).其其中每个极小项中每个极小项( (极极大项大项) )都有且仅有都有且仅有一个成真赋值一个成真赋值( (成成假赋值假赋值).).若成真若成真赋值赋值( (成假赋值成假赋值) )所对应的二进制所对应的二进制数转换为十进制数转换为十进制数数i，就将所对应，就将所对应极小项极小项( (极大项极大项) )记作记作mi (Mi ). 定理定理1.5.4 设设 与与 是命题变项是命题变项 形成的极小项和极大项，则形成的极小项和极大项，

30、则 定义定义1.5.5 设由设由n个命题变项构成的析取范式个命题变项构成的析取范式（合取范式）中所有的简单合取式（简单析取（合取范式）中所有的简单合取式（简单析取式）都是极小项（极大项），则称该析取范式式）都是极小项（极大项），则称该析取范式（合取范式）（合取范式）为主析取范式（主合取范式为主析取范式（主合取范式).). imiM12,nppp,iimM,iiMm定理定理1.5.5 任何命题公式都存在着与之等值任何命题公式都存在着与之等值的的主析取范式主析取范式和和主合取范式主合取范式，并且是，并且是唯一唯一的的. .例例1.5.2 求例求例1.51中公式的主析取范式和主合中公式的主析取范式和

31、主合取范式取范式. . 解解: : （1 1）求主析取范式）求主析取范式 在例在例1.5.1中已给出的公式的析取范式，即中已给出的公式的析取范式，即 （p q） r (pqr)(pr)(qr) m1m3m4m7 在此析取范式中，简单合取式在此析取范式中，简单合取式pr，qr都都不是极小项不是极小项.下面分别求出它们派生的极小项下面分别求出它们派生的极小项. （pr） p（qq）r (pqr)(pqr) m1m3 qr (pp)qr (pqr）(pqr) m3m7001,011,100,111为其成真为其成真赋值赋值注意注意, ,因为因为公式含三个公式含三个命题变项，命题变项，所以极小项所以极小

32、项均由三个文均由三个文字组成字组成. . ( (2) )再求主合取范式再求主合取范式. . 由例由例1.5.1已求出公式的合取范式，即已求出公式的合取范式，即 (p q） r (pr)(qr)(pqr) M0M2M5M6 (pr) (p(qq)r) (pqr)(pqr) M0M2(qr) (pp)qr) (pqr)(pqr) M2M6 000,010,101,110为其为其成假赋值成假赋值主析取范式的用途主析取范式的用途: : 1 1求公式的成真赋值与成假赋值求公式的成真赋值与成假赋值- -真值表真值表 若公式若公式A中含中含n个个命题变项命题变项，A的主析取范式的主析取范式含含s(0s )个

33、个极小项极小项，则，则A有有s个个成真赋值成真赋值，它们是所含极小项角标的二进制表示，其余它们是所含极小项角标的二进制表示，其余 -s个赋值都是成假赋值个赋值都是成假赋值.在例在例1.4.2中，（中，（p q） r m1m3m4m7,各极小项均含三个文字，各极小项均含三个文字，因而各极小项的角标均为长为因而各极小项的角标均为长为3的二进制数，的二进制数，它们分别是它们分别是001，011，100，111，这四个赋，这四个赋值为该公式的成真赋值值为该公式的成真赋值,其余的为成假赋值其余的为成假赋值.2n2n已知命题公式已知命题公式A的主析取范式的主析取范式, ,立刻可写出立刻可写出A的真值表的真

34、值表, ,反之亦然反之亦然. .例例1.5.3 已知已知A=pqr的真值表如下的真值表如下, ,求求A的的主析取范式和主合取范式主析取范式和主合取范式 p q r p pq qp pq qr r 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1A m1m3m5m6m7A M0M2M42判断公式的类型判断公式的类型 设公式设公式A中含中含n个命题变项，容易看出：个命题变项，容易看出： （1） A为为重言式重言式当且仅当当且仅当A的主析取范式含全的主析取范式含全部部2n个极小项个极小项.

35、. （2） A为为矛盾式矛盾式当且仅当当且仅当A的主析取范式不含的主析取范式不含任何极小项任何极小项. .此时，记此时，记A的主析取范式为的主析取范式为0. . （3） A为为可满足式可满足式当且仅当当且仅当A的主析取范式至的主析取范式至少含一个极小项少含一个极小项. . 例例1.5.4 用公式的用公式的主析取范式主析取范式判断公式的类型：判断公式的类型： （1） (p q)q （2） (pq) r 解解 : :（1） (p q)q （pq）q (pq) q 0 这说明（这说明（1）中公式是矛盾式）中公式是矛盾式 (2) (pq) r 该公式是可满足的，但不是重言式该公式是可满足的，但不是重言

36、式. . m0m1m3m5m7 (pqr)(pqr)(pqr)(pqr)(pqr) (pq(rr)(pp)(qq) r) (pq)r (pq)r pq 的的成真赋值为成真赋值为000,001-m0,m1r 的成真赋值为的成真赋值为001,011,101,111-m1,m3,m5,m73判断两个命题公式是否等值判断两个命题公式是否等值 例例1.5.5 判断下面两组公式是否等值：判断下面两组公式是否等值： （1）(pq)r与（与（q）r设公式设公式A, ,B共含有共含有n个命题变项，按个命题变项，按n个命题变个命题变项求出与的主析取范式项求出与的主析取范式 与与 . .若若 , ,则则 ；否则，；

37、否则，与与不等值不等值. . AABB（1）两公式都含命题变项）两公式都含命题变项 p , q , r，因而极，因而极小项含三个文字小项含三个文字. .经过演算得到经过演算得到 所以所以 (p q) r 与与(q) r 不等值不等值 (pq) r m0m1m2m3m4m5m7 (p q) r m1m3m4m5m7 4应用主析取范式分析和解决实际问题应用主析取范式分析和解决实际问题 例例1.5.6某科研所要从某科研所要从3名科研骨干名科研骨干A, B, C中挑中挑选选1-2名出国进修名出国进修. .由于工作原因，选派时要满由于工作原因，选派时要满足以下条件：足以下条件： （）若（）若A去，则去，

38、则C同去同去. . （）若（）若B去，则去，则C不能去不能去. . （）若（）若C不去，则不去，则A或或B可以去可以去. . 问应如何选派他们去？问应如何选派他们去？ 解解: :设设p: :派派A去去; ;q: :派派B去去; ;r: :派派C去去 . .由已知条件由已知条件可得公式可得公式 （p r）(q r)(r (pq)经过演算可得经过演算可得 (p r)(q r)(r (pq) m1m2m5由于由于 m1 = pqr, m2 = pqr, m5 = pqr 可知，选派方案有可知，选派方案有3种：种： （a）C去，而去，而A,B 都不去都不去. （b）B去，而去，而A,C 都不去都不去.

39、 （c）A,C去，而去，而B 不去不去. 几点注意几点注意 1. 由公式的主析取范式求主合取范式由公式的主析取范式求主合取范式 设公式设公式A含含n个个命题变项命题变项. A的的主析取范式主析取范式 S (0S )个个极小项极小项，即，即2n12;021,1,2,sniiijAmmmijs没出现的极小项没出现的极小项为为 , 它们的它们的角标的二进制表示为角标的二进制表示为 的成真赋值，因而的成真赋值，因而 的主析的主析取范式为取范式为 122,nsjjjmmm122nsjjjAmmmAA于是于是 由公式的主析取范式，即可求出它的主合取范式由公式的主析取范式，即可求出它的主合取范式122122122nsnsnsjjjjjjjjjAAmmmmmmMMM 2重言式与矛盾式的主合取范式重言式与矛盾式的主合取范式 矛盾式矛盾式无成真赋值，因而矛盾式的无成真赋值，因而矛盾式的主合取范主合取范式式含含2n（n为公式中命题变项个数）个为公式中命题变项个数）个极大项极大项. . 重言式无成假赋值，因而主合取范式不含任重言式