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

1、第二章第二章 命题逻辑等值演算命题逻辑等值演算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.12.1 设设A,BA,B是两个命题公式，若是两个命题公式，若A,BA,B构成的等价式构成的等价式A AB B为为重言式重言式,则称则称A A与与B B是是等值等值的的,记作记作A AB B。说说明明q注意注意与与的区别。的区别。qA A或或B B中可能有哑元出现。中可能有哑元出现。pqpq (pqpq)()(rrrr)r r为左边公式中的哑元。为左边公式中的哑元。q用真值表可以验证两个公式是否等值。用真值表可以验证两个公式是否等值。例例2.1 2.1 判断下面两个公式是否等值判断下面两个公式是否等值(pqpq)与与 pqpq 解答解答说说明明q在用真值表法判断在用真值表法判断A AB

3、 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)C AB)C A(BC)A(BC)(AB)C(AB)C A(BC)A(BC)5.5.分配律分配律 A(

4、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 1 11.11.矛盾律矛盾律 AA AA 0 0 12.12.蕴涵等值式蕴涵等值式 AB AB AB AB13.13.等价等值式等

5、价等值式 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互换互换得到的还是等值式。得到的还是等值式。q 各等值式都是用元语言符号书写的，其中各等值式都是用元语言符号书写的，其中A,B,CA,B,C可以代表任可以代表任意的公式，称这样的等值式为意的公式，称这样的等值式为等值式模式等值式模式。q 每个

6、等值式模式都给出了无穷多个同类型的具体的等值式。每个等值式模式都给出了无穷多个同类型的具体的等值式。例如，在蕴涵等值式例如，在蕴涵等值式 ABABAB AB 中，中，取取A=A=p p，B B=q=q时，得等值式时，得等值式 pqpqpqpq 取取A=A=pqrpqr，B B=pqpq时，得等值式时，得等值式(pqr)(pqpqr)(pq)(pqr)(pqpqr)(pq)q 这些具体的等值式都被称为原来的等值式模式的这些具体的等值式都被称为原来的等值式模式的代入实例代入实例。q 由已知的等值式推演出另外一些等值式的过程为由已知的等值式推演出另外一些等值式的过程为等值演算等值演算。q 置换规则置

7、换规则 设设(A)(A)是含公式是含公式A A的命题公式，的命题公式，(B)(B)是用公式是用公式B B置换了置换了(A)(A)中所有的中所有的A A后得到的命题公式，若后得到的命题公式，若B BA A，则则(B)(B)(A)(A)。关于等值演算的说明关于等值演算的说明q 等值演算的基础等值演算的基础等值关系的性质：等值关系的性质：自反性：自反性：A AA A。对称性：若对称性：若A AB B，则则B BA A。传递性：若传递性：若A AB B且且B BC C，则则A AC C。基本的等值式基本的等值式置换规则置换规则q 等值演算的应用等值演算的应用证明两个公式等值证明两个公式等值判断公式类型

8、判断公式类型解判定问题解判定问题等值演算的应用举例等值演算的应用举例证明两个公式等值证明两个公式等值(pq)rpq)r (pr)(qrpr)(qr)(pqpq)r)r (pq)pq)rr（蕴含等值式、置换规则）蕴含等值式、置换规则）(pq)pq)rr（蕴含等值式、置换规则）蕴含等值式、置换规则）(pq)pq)rr（德摩根律、置换规则）德摩根律、置换规则）(pr)(qrpr)(qr)（分配律、置换规则）分配律、置换规则）说说明明q 也可以从右边开始演算也可以从右边开始演算q 因为每一步都用置换规则，故可不写出因为每一步都用置换规则，故可不写出q 熟练后，基本等值式也可以不写出熟练后，基本等值式也

9、可以不写出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.2.4 4 用等值演算判断下列公式的类型：用等值演算判断下列公式的类型：（1 1）(p(pq)rp(pq)r （2 2）p(pq)p)qp(pq)p)q)（3 3）(pq)

10、pqpq)pq(1)(1)(p p(pq)r(pq)r (ppq)rppq)r (ppppq)rq)r 00r r0 0故原公式为矛盾式故原公式为矛盾式(2)2)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 p故原公式为非重言式的可满足式故原公式为非重言式的可满足式解：解：(3)(3)(p pq)pqq)pq (pq)ppq)pq q （蕴涵等值式）蕴涵等值式）(pq)p)pq)p)qq （蕴涵等值式）蕴涵等值式）(pq)pq)p)qp)q （德摩根律

11、）德摩根律）(pq)pq)pp)q)q（德摩根律）德摩根律）(pppp)(qp)q)(qp)q （分配律）分配律）(11(q qp)p)q q （排中律）排中律）(qqqq)p)p （同一律）同一律）11p p（排中律）排中律）1 1 （零 律）（零 律）公式为重言式公式为重言式定义定义1 1 命题变项及其否定统称作命题变项及其否定统称作文字文字。仅由有限个文字构成的析取式称作仅由有限个文字构成的析取式称作简单析取式简单析取式。仅由有限个文字构成的合取式称作仅由有限个文字构成的合取式称作简单合取式简单合取式。q 简单析取式举例：简单析取式举例：p,qp,qpppp，pqpq pqr,pqrpq

12、r,pqrq 简单合取式举例：简单合取式举例：p,qp,qpppp，pqpqpqr,ppqpqr,ppqq 一个文字既是简单析取式，又是简单合取式。一个文字既是简单析取式，又是简单合取式。q 为讨论方便，有时用为讨论方便，有时用A A1 1,A,A2 2,A,As s表示表示s s个简单析取式或个简单析取式或s s个简单合取式。个简单合取式。q 定理定理1 1 (1)(1)一个简单析取式是重言式当且仅当它同时含有某个命一个简单析取式是重言式当且仅当它同时含有某个命题变项及它的否定式。题变项及它的否定式。(2)(2)一个简单合取式是矛盾式当且仅当它同时含有某个命一个简单合取式是矛盾式当且仅当它同

13、时含有某个命题变项及它的否定式。题变项及它的否定式。定义定义2 2(1)(1)由有限个简单合取式构成的析取式称为由有限个简单合取式构成的析取式称为析取范式析取范式。(2)(2)由有限个简单析取式构成的合取式称为由有限个简单析取式构成的合取式称为合取范式合取范式。(3)(3)析取范式与合取范式统称为析取范式与合取范式统称为范式范式。q 设设A Ai i(i(i=1,2,=1,2,s),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

14、 2,A,A3 3构造的析取范式为构造的析取范式为A=AA=A1 1AA2 2AA3 3=(=(pq)(qr)ppq)(qr)p q 设设A Ai i(i(i=1,2,=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=A1 1AA2 2AA3 3=(=(pqr)(pq)rpqr)(pq)rq 定理定理2 2 (1)(1)一个析取范式是矛盾式当且仅当它

15、的每个简单合取式都是一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。矛盾式。(2)(2)一个合取范式是重言式当且仅当它的每个简单析取式都是一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。重言式。q 定理定理3 3 任一命题公式都存在着与之等值的析取范式与合取范式。任一命题公式都存在着与之等值的析取范式与合取范式。说说明明q 研究范式的目的在于，将给定公式化成与之等值的析研究范式的目的在于，将给定公式化成与之等值的析取范式或合取范式，进而将公式化成与之等值的主析取范式或合取范式，进而将公式化成与之等值的主析取范式或主合取范式。取范式或主合取范式。(1(1)消去联结词消去联结词

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

17、(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)说说明明q 由此例可

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

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

20、i。表表1 1 p,q形成的极小项与极大项形成的极小项与极大项 P QPQP Q PQ P Q0 00 00 10 11 01 01 11 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0P QPQP Q PQ P Q0 00 00 10 11 01 01 11 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0表表2 2 p,q,r形成的极小项与极大项形成的极小项与极大项 定理定理4 4 设设mi与与Mi是命题变项是命题变项p1,p

21、2,pn形成的极小项和极大形成的极小项和极大项，则项，则 mi Mi，Mi mi 定义定义4 4 设由设由n n个命题变项构成的析取范式（合取范式）中所有个命题变项构成的析取范式（合取范式）中所有的简单合取式（简单析取式）都是极小项（极大项），则的简单合取式（简单析取式）都是极小项（极大项），则称该析取范式（合取范式）称该析取范式（合取范式）为主析取范式为主析取范式（主合取范式主合取范式）.定理定理5 5 任何命题公式都存在着与之等值的主析取范式和主合任何命题公式都存在着与之等值的主析取范式和主合取范式，并且是唯一的。取范式，并且是唯一的。定理定理5 5的证明的证明(1)(1)证明存在性。证明

22、存在性。设设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)继续这个过程，直到所有的简单合取式都含任意命题变项或它的继续这个过程，直到所有的简单合取式都含任

23、意命题变项或它的否定式。否定式。若在演算过程中出现重复的命题变项以及极小项和矛盾式时，都若在演算过程中出现重复的命题变项以及极小项和矛盾式时，都应应“消去消去”：如用：如用p p代替代替pppp，m mi i代替代替m mi immi i，0 0代替矛盾式等代替矛盾式等。最后就将。最后就将A A化成与之等值的主析取范式化成与之等值的主析取范式AA。(2)(2)证明唯一性。证明唯一性。假设某一命题公式假设某一命题公式A A存在两个与之等值的主析取范式存在两个与之等值的主析取范式B B和和C C，即即A AB B且且A AC C，则则B BC C。由于由于B B和和C C是不同的主析取范式，不妨设

24、极小项是不同的主析取范式，不妨设极小项m mi i只出现在只出现在B B中而不出现在中而不出现在C C中。中。于是，角标于是，角标i i的二进制表示为的二进制表示为B B的成真赋值，而为的成真赋值，而为C C的成假赋的成假赋值。这与值。这与B BC C矛盾，因而矛盾，因而B B与与C C必相同。必相同。方法一、等值演算法方法一、等值演算法(1)(1)化归为析取范式。化归为析取范式。(2)(2)除去析取范式中所有永假的析取项。除去析取范式中所有永假的析取项。(3)(3)将析取式中重复出现的合取项和相同的变元合并。将析取式中重复出现的合取项和相同的变元合并。(4)(4)对合取项补入没有出现的命题变

25、元，即添加如对合取项补入没有出现的命题变元，即添加如(pppp)式式，然后应用分配律展开公式。，然后应用分配律展开公式。方法二、真值表法方法二、真值表法(1)(1)写出写出A A的真值表。的真值表。(2)(2)找出找出A A的成真赋值。的成真赋值。(3)(3)求出每个成真赋值对应的极小项（用名称表示），按角标求出每个成真赋值对应的极小项（用名称表示），按角标从小到大顺序析取。从小到大顺序析取。方法一、等值演算法方法一、等值演算法(1)(1)化归为合取范式。化归为合取范式。(2)(2)除去合取范式中所有永真的合取项。除去合取范式中所有永真的合取项。(3)(3)将合取式中重复出现的析取项和相同的变

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

27、qpq （pp（qqqq）（(pppp)q)q）(pq)(pq)(pq)(pqpq)(pq)(pq)(pq)(pq)(pq)(pqpq)(pq)(pq)m m0 0mm1 1mm3 3 解答解答pqp q001011100111例例2 2 求命题公式求命题公式 pqpq 的主析取范式和主合取范式。的主析取范式和主合取范式。例例3 3 求求 的主析取范式和主合取范式。的主析取范式和主合取范式。Apqrp解：解：(1)列真值表列真值表(2)成真赋值有010，100，101，110，111(3)成假赋值有000，001，011q 主析取范式为主析取范式为24567mmmmmq 主合取范式为主合取范式

28、为310MMMq 方法一、真值表法方法一、真值表法q 方法二、等值演算法方法二、等值演算法 主析取范式主析取范式 qrpp pqqrr()()qrpqrp ()()pqrpqr()()pqrpqr ()()prqrpprq)(24567mmmmmApqrpprqp)(prqp)(q 方法二、等值演算法方法二、等值演算法 主合取范式主合取范式()()prqrpprq)(Apqrpprqp)(prqp)()()(rpqp)()()()(qqrprrqp)()()()(rqprqprqprqp310MMMq 已知一种主范式已知一种主范式,求另一种主范式求另一种主范式Apqrp24567mmmmmq

29、分析分析:主析取范式中没有出现的极小项有主析取范式中没有出现的极小项有310MMM310,mmm)(310mmmAq 主合取范式为主合取范式为主析取范式的用途主析取范式的用途 q求公式的成真赋值与成假赋值求公式的成真赋值与成假赋值q判断公式的类型判断公式的类型 q判断两个命题公式是否等值判断两个命题公式是否等值 q应用主析取范式分析和解决实际问题应用主析取范式分析和解决实际问题 求公式的成真赋值与成假赋值求公式的成真赋值与成假赋值q 若公式若公式A A中含中含n n个命题变项，个命题变项，A A的主析取范式含的主析取范式含s(0s2s(0s2n n)个极小项，则个极小项，则A A有有s s个成

30、真赋值，它们是所含极小项角标的个成真赋值，它们是所含极小项角标的二进制表示，其余二进制表示，其余2 2n n-s-s个赋值都是成假赋值。个赋值都是成假赋值。q 在例在例2.82.8中，中，(pq)pq)r r m m1 1mm3 3mm4 4mm7 7,各极小项均含各极小项均含三个文字，因而各极小项的角标均为长为三个文字，因而各极小项的角标均为长为3 3的二进制数，它的二进制数，它们分别是们分别是001001，011011，100100，111111，这四个赋值为该公式的成，这四个赋值为该公式的成真赋值真赋值,其余的为成假赋值。其余的为成假赋值。q 在例在例2.92.9中，中，pqpq m m

31、0 0mm1 1mm3 3，这三个极小项均含两个这三个极小项均含两个文字，它们的角标的二进制表示文字，它们的角标的二进制表示0000，0101，1111为该公式的成为该公式的成真赋值，真赋值，1010是它的成假赋值。是它的成假赋值。判断公式的类型判断公式的类型设公式设公式A A中含中含n n个命题变项，容易看出：个命题变项，容易看出：qA A为为重言式重言式当且仅当当且仅当A A的主析取范式含全部的主析取范式含全部2 2n n个个极小项。极小项。qA A为为矛盾式矛盾式当且仅当当且仅当A A的主析取范式不含任何极的主析取范式不含任何极小项。此时，记小项。此时，记A A的主析取范式为的主析取范式

32、为0 0。qA A为为可满足式可满足式当且仅当当且仅当A A的主析取范式至少含一的主析取范式至少含一个极小项。个极小项。判断公式的类型判断公式的类型例例2.102.10 用公式的主析取范式判断公式的类型：用公式的主析取范式判断公式的类型：(1)(1)(pq)qpq)q (2)(2)p(pqp(pq)(3)(3)(pq)rpq)r解答解答(1)(1)(pq)qpq)q （pqpq）qq (pq)qpq)q 0 0(2)p(pq)(2)p(pq)m m0 0mm1 1mm2 2mm3 3 (3)(3)(pq)rpq)r m m0 0mm1 1mm3 3mm5 5mm7 7 矛盾式矛盾式重言式重言式

33、可满足式可满足式判断两个命题公式是否等值判断两个命题公式是否等值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 判断下面两组公式是否等值：判断下面两组公式是否等值：(1)(1)p p与与(pq)(pqpq)(pq)(2)(2)(pq)rpq)r与与(q)rq)r (1)(1)p p p(qqp(qq)(pq)(pqpq)(pq)m m2 2mm3 3 (pq)(pqpq)(pq)m

34、m2 2mm3 3 两公式等值。两公式等值。(2)(2)(pq)rpq)r m m1 1mm3 3mm4 4mm5 5mm7 7 (q)rq)r m m0 0m m1 1m m2 2m m3 3m m4 4m m5 5m m7 7 两公式不等值。两公式不等值。解答解答应用主析取范式分析和解决实际问题应用主析取范式分析和解决实际问题例例2.122.12某科研所要从某科研所要从3 3名科研骨干名科研骨干A,B,CA,B,C中挑选中挑选1 12 2名出国进名出国进修。由于工作原因，选派时要满足以下条件：修。由于工作原因，选派时要满足以下条件：(1)(1)若若A A去，则去，则C C同去。同去。(2)

35、(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)这样每个小项就是一种可能产生的结果。这样每个小项就是一种可能产生的结果。去掉不符合题意的小项，即得结论。去掉不符合题意的小项，即得结论。

36、应用主析取范式分析和解决实际问题应用主析取范式分析和解决实际问题设设 p:p:派派A A去，去，q:q:派派B B去，去，r:r:派派C C去去 由已知条件可得公式由已知条件可得公式 (pr)(qr)(r(pqpr)(qr)(r(pq)经过演算可得经过演算可得 (pr)(qr)(r(pqpr)(qr)(r(pq)m m1 1mm2 2mm5 5 由于由于 m m1 1=pqrpqr,m,m2 2=pqrpqr,m,m5 5=pqrpqr可知，选派方案有可知，选派方案有3 3种：种：(a)Ca)C去，而去，而A,BA,B都不去。都不去。(b)Bb)B去，而去，而A,CA,C都不去。都不去。(c)

37、A,Cc)A,C去，而去，而B B不去。不去。解答解答由公式的主析取范式求主合取范式由公式的主析取范式求主合取范式 设公式设公式A A含含n n个命题变项。个命题变项。A A的主析取范式含的主析取范式含s(0s2s(0s2n n)个极小项，即个极小项，即sjimmmAnjiiis,2,1,120,21没有出现的极小项设为没有出现的极小项设为snjjjmmm221,它们的角标的二进制表示为它们的角标的二进制表示为A A的成真赋值，因而的成真赋值，因而A A的主的主析取范式为析取范式为snjjjmmmA221)(221snjjjmmmAA)221snjjjmmm)221snjjjMMM例例2.13

38、2.13 由公式的主析取范式，求主合取范式：由公式的主析取范式，求主合取范式：(1)(1)A A m m1 1mm2 2(A(A中含两个命题变项中含两个命题变项p,qp,q)(2)B(2)B m m1 1mm2 2mm3 3(B(B中含两个命题变项中含两个命题变项p,q,rp,q,r)解答解答(1)(1)A A M M0 0MM3 3 (2)B(2)B M M0 0MM4 4MM5 5MM6 6MM7 7 重言式与矛盾式的主合取范式重言式与矛盾式的主合取范式设设n n为公式中命题变项个数为公式中命题变项个数q 矛盾式无成真赋值，因而矛盾式的主合取范式含矛盾式无成真赋值，因而矛盾式的主合取范式含

39、2 2n n个极大个极大项。项。q 重言式无成假赋值，因而主合取范式不含任何极大项。重言式无成假赋值，因而主合取范式不含任何极大项。q 将重言式的主合取范式记为将重言式的主合取范式记为1 1。q 可满足式的主合取范式中极大项的个数一定小于可满足式的主合取范式中极大项的个数一定小于2 2n n。真值表与范式的关系真值表与范式的关系 q A AB B当且仅当当且仅当A A与与B B有相同的真值表，又当且仅当有相同的真值表，又当且仅当A A与与B B有相同的主析取范式（主合取范式）。有相同的主析取范式（主合取范式）。q 真值表与主析取范式（主合取范式）是描述命题公式真值表与主析取范式（主合取范式）是

40、描述命题公式标准形式的两种不同的等价形式。标准形式的两种不同的等价形式。n n个命题变项共可产生个命题变项共可产生2 2n n个极小项（极大项）个极小项（极大项）可以产生的主析取范式（主合取范式）数目为：可以产生的主析取范式（主合取范式）数目为：nnnnnCCC22212022本章主要内容本章主要内容q等值式与等值演算。等值式与等值演算。q基本的等值式，其中含：双重否定律、幂等律、基本的等值式，其中含：双重否定律、幂等律、交换律、结合律、分配律、德交换律、结合律、分配律、德摩根律、吸收律、摩根律、吸收律、零律、同一律、排中律、矛盾律、蕴含等值式、零律、同一律、排中律、矛盾律、蕴含等值式、等价等

41、值式、假言易位、等价否定等值式、归谬等价等值式、假言易位、等价否定等值式、归谬论。论。q与主析取范式及主合取范式有关的概念：简单合与主析取范式及主合取范式有关的概念：简单合取式、简单析取式、析取范式、合取范式、极小取式、简单析取式、析取范式、合取范式、极小项、极大项、主析取范式、主合取范式。项、极大项、主析取范式、主合取范式。本章学习要求本章学习要求 q 深刻理解等值式的概念。深刻理解等值式的概念。q 牢记牢记2424个基本等值式，这是等值演算的基础；能熟练地应用个基本等值式，这是等值演算的基础；能熟练地应用它们进行等值演算。它们进行等值演算。q 了解简单析取式、简单合取式、析取范式、合取范式

42、的概念了解简单析取式、简单合取式、析取范式、合取范式的概念。q 深刻理解极小项及极大项的定义及它们的名称，及名称下角深刻理解极小项及极大项的定义及它们的名称，及名称下角标与成真赋值的关系。标与成真赋值的关系。q 熟练掌握求公式的主析取范式的方法。熟练掌握求公式的主析取范式的方法。q 熟练掌握由公式的主析取范式求公式的主合取范式的方法。熟练掌握由公式的主析取范式求公式的主合取范式的方法。q 会用公式的主析取范式（主合取范式）求公式的成真赋值、会用公式的主析取范式（主合取范式）求公式的成真赋值、成假赋值。成假赋值。本章典型习题本章典型习题q用等值演算法证明重言式和矛盾式用等值演算法证明重言式和矛盾

43、式q用等值演算法证明等值式用等值演算法证明等值式q求公式的主析取范式和主合取范式求公式的主析取范式和主合取范式q用主范式判断两个公式是否等值用主范式判断两个公式是否等值q求解实际问题求解实际问题求公式求公式(pq)(prpq)(pr)的主析取范式和主合取范式。的主析取范式和主合取范式。解答解答p pq qr r(pq)(prpq)(pr)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主析取范式为主析取范式为(ppqr)(qr)(pqr)pqr)(pq

44、(pqr r)(pqrpqr)主合取范式为主合取范式为 (pqr)(ppqr)(pqr)qr)(pqrpqr)(pqpqr r)甲、乙、丙、丁四个人有且只有两个人参加围棋比赛。关于谁甲、乙、丙、丁四个人有且只有两个人参加围棋比赛。关于谁参加比赛，下列四个判断都是正确的：参加比赛，下列四个判断都是正确的：(1)(1)甲和乙只有一人参加比赛。甲和乙只有一人参加比赛。(2)(2)丙参加，丁必参加。丙参加，丁必参加。(3)(3)乙或丁至多参加一人。乙或丁至多参加一人。(4)(4)丁不参加，甲也不会参加。丁不参加，甲也不会参加。请推断出哪两个人参加围棋比赛。请推断出哪两个人参加围棋比赛。设设a a：甲参

45、加了比赛。甲参加了比赛。b b：乙参加了比赛。乙参加了比赛。c c：丙参加了比赛。丙参加了比赛。d d：丁参加了比赛。丁参加了比赛。(1)(1)(aab)(b)(abab)(2)(2)cdcd(3)(3)(bdbd)(4)(4)d d a a 解答解答(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)说说明明本章作业本章作业习题二习题二4 4(3)(3)、7 7、8 8(1)(1)、9 9(2)(2)、2323、2929同学们学习愉快！同学们学习愉快！下次课再见！下次课再见！