《二章命题逻辑等值演算》由会员分享，可在线阅读，更多相关《二章命题逻辑等值演算（70页珍藏版）》请在金锄头文库上搜索。
1、1第二章第二章:命题逻辑等值演算命题逻辑等值演算q主要内容：主要内容：l 等值式与基本的等值式等值式与基本的等值式l 等值演算与置换规则等值演算与置换规则l 析取范式与合取范式，主析取范式与主合取范式析取范式与合取范式，主析取范式与主合取范式l 联结词完备集联结词完备集q本章与其他各章的联系本章与其他各章的联系l 是第一章的抽象与延伸是第一章的抽象与延伸l 是后续各章的先行准备是后续各章的先行准备2 第一节：等值式第一节：等值式32.1 等值式等值式q若等价式若等价式AB是重言式，则称是重言式，则称A与与B等值，记等值，记作作AB，并称，并称AB是等值式是等值式 几点说明：几点说明：l定义中，
2、定义中，A, B, 均为元语言符号均为元语言符号lA或或B中可能有哑元出现中可能有哑元出现. 例如，在例如，在 (pq) ( p q) ( r r) 中，中，r为左边公式的哑元为左边公式的哑元. l用真值表可验证两个公式是否等值用真值表可验证两个公式是否等值42.1 等值式等值式pppp p01011011q例子例子v 判断判断pp 52.1 等值式等值式pqppqp q(pq) (p q)001111011111100001110111q例子例子v 判断判断 pq p q 62.1 等值式等值式q如果命题变项很多，怎么办？如果命题变项很多，怎么办？ - 利用已知的等值式通过代换得到新的等值式
3、利用已知的等值式通过代换得到新的等值式q命题：设命题：设A是一个命题公式，含有命题变项是一个命题公式，含有命题变项p1，p2，pn，又设，又设A1，A2，An是任意的命题是任意的命题公式公式. 对每个对每个i（i=1，2，n），把），把pi在在A中的中的所有出现都替换成所有出现都替换成Ai，所得到的新命题公式记作，所得到的新命题公式记作B. 那么，如果那么，如果A是重言式，则是重言式，则B也是重言式也是重言式.72.1 等值式等值式q否定律否定律v双重否定律双重否定律 ppv德摩根律德摩根律 (p q) p q (p q) p qq幂等律幂等律 p p p， p p pq交换律交换律 vp q
4、 q p vp q q p vp q q p82.1 等值式等值式q结合律结合律v(p q) r p (q r)v(p q) r p (q r)v(p q) r p (q r)q分配律分配律vp (q r) (p q) (p r)vp (q r) (p q) (p r)92.1 等值式等值式q常元律常元律v零律: p 1 1， p 0 0v同一律: p 0 p， p 1 pv排中律: p p 1v矛盾律: p p 0q吸收律吸收律vp (p q) pvp (p q) p102.1 等值式等值式q蕴涵等值式蕴涵等值式 p q p qq等价等值式等价等值式 p q (p q) (q p)q假言易位
5、假言易位 p q q pq等价否定等值式等价否定等值式 p q p qq归谬论归谬论 (p q ) (p q ) p 112.1 等值式等值式说明：说明： (1)16组等值模式都可以给出无穷多个同类型的具组等值模式都可以给出无穷多个同类型的具体的等值式。体的等值式。 (2)证明上述证明上述16组等值式的组等值式的代入实例代入实例方法可用真值方法可用真值表法，把表法，把改为改为所得的命题公式为永真式，则所得的命题公式为永真式，则成立。成立。122.1 等值式等值式q等值演算等值演算：由已知的等值式推演出另外一些等：由已知的等值式推演出另外一些等值式的过程值式的过程q置换规则置换规则：设：设(A)
6、是含公式是含公式A的命题公式，的命题公式， (B)是用公式是用公式B置换了置换了(A)中所有中所有A后得到的命后得到的命题公式，若题公式，若B ，则，则(A) (B) q说明：说明：v等值演算过程中遵循的重要规则等值演算过程中遵循的重要规则v一个命题公式一个命题公式A，经多次置换，所得到的新公式经多次置换，所得到的新公式与原公式等价与原公式等价132.1 等值式等值式1.用等值演算验证等值式用等值演算验证等值式 试证：试证：p(qr) (p q)r证明：证明：a.p(qr)p(qr) b.p(qr)pqr c.pqr(p q) rd.(p q) r (p q)r142.1 等值式等值式试证：试
7、证：(p q)(p(p q)(pq)左边左边 (p q) (p(p q) (p q) (p(p q) (p q) (p q) (p p q) (q p q) (p q)152.1 等值式等值式2. 用等值演算判断公式的类型用等值演算判断公式的类型证明：证明：(pq) (p (qr)(p q)(p r)为一为一永真式永真式证明：原式证明：原式 (pq) (p(q r)(pq)(pr) (pq) (pq) (pr)(pq) (pr) (pq) (pr)(pq) (pr) 1162.1 等值式等值式 3解判定问题解判定问题 在某次研讨会的中间休息时间，在某次研讨会的中间休息时间，3名与会者名与会者根
8、据王教授的口音对他是哪个省市的人判断如根据王教授的口音对他是哪个省市的人判断如下：下： 甲：王教授不是苏州人，是上海人甲：王教授不是苏州人，是上海人 乙：王教授不是上海人，是苏州人乙：王教授不是上海人，是苏州人 丙：王教授既不是上海人，也不是杭州人丙：王教授既不是上海人，也不是杭州人 听完这听完这3人的判断后，王教授笑着说，你们人的判断后，王教授笑着说，你们3人中有一人说得全对，有一人说对了一半，另人中有一人说得全对，有一人说对了一半，另一人说得全不对。试用逻辑演算分析王教授到一人说得全不对。试用逻辑演算分析王教授到底是哪里人。底是哪里人。17 第二节：析取范式与合取范式第二节：析取范式与合取
9、范式182.2 析取范式和合取范式析取范式和合取范式 q文字文字(literal): 命题变项及其否定命题变项及其否定q简单析取式简单析取式:仅由有限个文字构成的析取式仅由有限个文字构成的析取式q简单合取式简单合取式:仅由有限个文字构成的合取式仅由有限个文字构成的合取式q例：设例：设p、q为二个命题变元为二个命题变元vp，q，pp，qq，pq， q p，pq，p q 称为简单析取式称为简单析取式vp，q，pp，qq， pq， q p，pq，p q 称为简单合取式。称为简单合取式。192.2 析取范式和合取范式析取范式和合取范式q定理定理: 1)一个一个简单析取式简单析取式是是永真式永真式当且仅
10、当它同时含当且仅当它同时含某个命题变元及它的否定式某个命题变元及它的否定式 2)一个一个简单合取式简单合取式是是永假式永假式当且仅当它同时含当且仅当它同时含某个命题变元及它的否定式某个命题变元及它的否定式 202.2 析取范式和合取范式析取范式和合取范式q析取范式析取范式:由有限个简单合取式构成的析取式由有限个简单合取式构成的析取式vA1 An, Ai 为简单合取式为简单合取式v( p q) (p r)q合取范式合取范式:由有限个简单析取式构成的合取式由有限个简单析取式构成的合取式vA1 An, Ai 为简单析取式为简单析取式v( p q) (p r)q析取范式与合取范式统称为析取范式与合取范
11、式统称为范式范式212.2 析取范式和合取范式析取范式和合取范式q定理：定理：vAi 简单合取式，简单合取式， A1 An F 当且仅当当且仅当 Ai F，任意，任意AivAi 简单析取式，简单析取式， A1 An T 当且仅当当且仅当 Ai T，任意，任意Ai222.2 析取范式和合取范式析取范式和合取范式q范式存在定理范式存在定理: 任意命题公式都存在着与之等值的任意命题公式都存在着与之等值的析取范式与合取范式析取范式与合取范式方法：方法： 步骤一：步骤一：消去消去“”、“”联结词联结词步骤二：步骤二：消去双重否定符，内移否定符消去双重否定符，内移否定符步骤三：步骤三：使用分配律使用分配律
12、232.2 析取范式和合取范式q范式存在定理范式存在定理: 任意命题公式都存在着与之等值的任意命题公式都存在着与之等值的析取范式与合取范式析取范式与合取范式方法：方法： 步骤一：消去步骤一：消去“”、“”联结词联结词步骤二：消去双重否定符，内移否定符步骤二：消去双重否定符，内移否定符步骤三：使用分配律步骤三：使用分配律242.2 析取范式和合取范式q步骤一：利用等值公式：化去步骤一：利用等值公式：化去“”、“”联联结词结词v p q p qv p q (p q) (q p)252.2 析取范式和合取范式q范式存在定理范式存在定理: 任意命题公式都存在着与之等值的任意命题公式都存在着与之等值的析
13、取范式与合取范式析取范式与合取范式方法：方法： 步骤一：消去步骤一：消去“”、“”联结词联结词步骤二：消去双重否定符，内移否定符步骤二：消去双重否定符，内移否定符步骤三：使用分配律步骤三：使用分配律262.2 析取范式和合取范式q消去双重否定符，内移否定符消去双重否定符，内移否定符v德摩根律德摩根律 (p q) p q (p q) p qv双重否定律双重否定律 p p272.2 析取范式和合取范式q范式存在定理范式存在定理: 任意命题公式都存在着与之等值的任意命题公式都存在着与之等值的析取范式与合取范式析取范式与合取范式方法：方法： 步骤一：消去步骤一：消去“”、“”联结词联结词步骤二：消去双
14、重否定符，内移否定符步骤二：消去双重否定符，内移否定符步骤三：使用分配律步骤三：使用分配律282.2 析取范式和合取范式q利用利用“ ”对对“ ”的分配，将公式化成为析取范式的分配，将公式化成为析取范式vp (q r) (p q) (p r)q利用利用“ ”对对“ ”的分配，将公式化成为合取范式的分配，将公式化成为合取范式vp (q r) (p q) (p r)292.2 析取范式和合取范式q例：求例：求(p q) (p q)的析取范式的析取范式 1.化去化去 ( p q) (p q)2.“ ”对对“ ”分配，化为析取范式分配，化为析取范式 ( p p q) (q p q) 3.最简析取范式最
15、简析取范式 p q 302.2 析取范式和合取范式q例：求例：求(p q) r) p的析取范式和合取范式的析取范式和合取范式 (一一) 求析取范式求析取范式原式原式 ( (p q) r) p ( (p q) r) p ( (p q) r) p (p q) r) p (p r) (q r) p p (p r) (q r) p (q r)312.2 析取范式和合取范式(二二)求合取范式求合取范式原式原式 ( (p q) r) p ( (p q) r) p ( (p q) r) p (p q) r) p (p p q) (p r) (p q) (p r)322.2 析取范式和合取范式问题：问题：q一
16、个命题公式的析取范式是不是唯一的？一个命题公式的析取范式是不是唯一的？q同一命题公式的析取范式是不是等值的？同一命题公式的析取范式是不是等值的？332.2 析取范式和合取范式q极小项极小项(极大项极大项):含有含有n个命题变项的简单合取式个命题变项的简单合取式 (简单析取式简单析取式)，并满足，并满足v每个命题变元和它的否定式不同时出现，而二者之每个命题变元和它的否定式不同时出现，而二者之一必出现且仅出现一次一必出现且仅出现一次v第第i个命题变项或它的否定式出现在从左算起的第个命题变项或它的否定式出现在从左算起的第i位位上上(若无角标，则按字典顺序排列若无角标，则按字典顺序排列)q若有若有个命
17、题变项，则有个命题变项，则有2n个极小项（极大项）个极小项（极大项）q如果我们把不带否定符的命题变项取成如果我们把不带否定符的命题变项取成1，带否，带否定符的命题变项取成定符的命题变项取成0，那么每一个极小项都对，那么每一个极小项都对应一个二进制数，因而也对应一个十进制数应一个二进制数，因而也对应一个十进制数342.2 析取范式和合取范式q极小项的编码极小项的编码:对应成真赋值对应成真赋值三个变元三个变元p、q、r可构造可构造8个极小项：个极小项： pqr FFF 0 记作记作 m0 pqr FFT 1 记作记作 m1 pqr FTF 2 记作记作 m2 pqr FTT 3 记作记作 m3 p
18、qr TFF 4 记作记作 m4 pqr TFT 5 记作记作 m5 pqr TTF 6 记作记作 m6 pqr TTT 7 记作记作 m7352.2 析取范式和合取范式q极大项的编码极大项的编码:对应成假赋值对应成假赋值如三个变元如三个变元 p、q、r，其记法如下：其记法如下：pqr F F F 0 记作记作 M0p q r F F T 1 记作记作 M1p qr F T F 2 记作记作 M2p q r F T T 3 记作记作 M3 p q r T T T 7 记作记作 M7362.2 析取范式和合取范式q定定理理:设设mi和和Mi是是命命题题变变元元p1, p2 pn形形成成的的极极小
19、项和极大项，则：小项和极大项，则：(1) mi mj F, (ij)(2) Mi Mj T, (ij)(3) mi Mi； Mi mi372.2 析取范式和合取范式q 主析取范式主析取范式(主合取范式主合取范式)：由：由n个命题变项个命题变项构成的构成的析取范式析取范式(合取范式合取范式)中中所有的简单合所有的简单合取式取式(简单析取式简单析取式)都是极小项都是极小项(极大项极大项)q定理定理: 任何命题公式都存在着与其等值的主任何命题公式都存在着与其等值的主析取范式和主合取范式，并且是唯一的。析取范式和主合取范式，并且是唯一的。382.2 析取范式和合取范式q证法一证法一v在真值表中，使命题
20、公式的真值为在真值表中，使命题公式的真值为T的指派所对应的的指派所对应的极小项的析取，即为此公式的主析取范式极小项的析取，即为此公式的主析取范式证：证：给定一个命题公式给定一个命题公式A，使其为使其为T的真值指派所对的真值指派所对应的极小项为应的极小项为m1, m2, mk,这些极小项的析这些极小项的析取记为取记为B，为此要证为此要证AB，即要证即要证A与与B在相同在相同的指派下具有相同的真值。的指派下具有相同的真值。392.2 析取范式和合取范式首先对于使首先对于使A为为T的指派显然使的指派显然使B为为T对于使对于使A为为F的指派，它对应的极小项的指派，它对应的极小项(设为设为mj )不不包
21、含在包含在m1, m2, mk 中。所以中。所以 mj为使为使B为为F的指派的指派所以所以A B 得证得证402.2 析取范式和合取范式q一个公式的主析取范式即为令此公式的真值为一个公式的主析取范式即为令此公式的真值为T的指派所对应的极小项的析取。的指派所对应的极小项的析取。q一个命题公式的真值表是唯一的，因此一个命一个命题公式的真值表是唯一的，因此一个命题公式的主析取范式也是唯一的题公式的主析取范式也是唯一的412.2 析取范式和合取范式析取范式和合取范式p q r m1 m3 m5 m6 m7pqrpqrFFFFFFTTFTFFFTTTTFFFTFTTTTFTTTTTp q r的真值表的真
22、值表422.2 析取范式和合取范式析取范式和合取范式q证法二：构造法证法二：构造法v用等值演算方法求命题公式主析取范式的方法用等值演算方法求命题公式主析取范式的方法将命题公式化归为与其等值的析取范式将命题公式化归为与其等值的析取范式添变元添变元: 消去重复项消去重复项Ai (pj pj) (Ai pj) (Ai pj) 432.2 析取范式和合取范式q例：求例：求(p(pq)q的主析取范式的主析取范式解：解：原式原式(pp)(pq)q v-(1)化为析取范式化为析取范式 (pq)q v-(2)化简化简(pq)(q(pp)(pq)(pq)(pq) v-(3)添项添项(pq)(pq) m1 m3
23、v-(4)合并相同最小项合并相同最小项442.2 析取范式和合取范式q主合取范式主合取范式v任何一个命题公式都可求得它的主合取范式任何一个命题公式都可求得它的主合取范式v一个命题公式的主合取范式是唯一的一个命题公式的主合取范式是唯一的v在真值表中，令命题公式的真值为在真值表中，令命题公式的真值为“F”的的指派就对应其主合取范式的一个极大项指派就对应其主合取范式的一个极大项v构造法构造法452.2 析取范式和合取范式q例例:求求p(pq)q的主合取范式的主合取范式 解：原式解：原式 p( pq)q(p p)(pq)q(pq)q(pq) q(pq)(q(p p) (pq)( pq) M0 M2 p
24、q上式上式FFFFTTTFFTTT462.2 析取范式和合取范式q主析（合）取范式的用途讨论：主析（合）取范式的用途讨论：求公式的成真与成假赋值求公式的成真与成假赋值判断公式类型判断公式类型判断两个命题公式是否等值判断两个命题公式是否等值应用主析（合）取范式分析和解决实际问题应用主析（合）取范式分析和解决实际问题472.2 析取范式和合取范式q 1. 求公式的成真与成假赋值求公式的成真与成假赋值 例：例：(pq)r m1 m3 m5 m6 m7 成真赋值为成真赋值为001, 011, 101, 110, 111 成假赋值为成假赋值为000, 010, 100482.2 析取范式和合取范式q2.
25、 判断公式的类型判断公式的类型 设设A含含n个命题变项个命题变项 A为重言式为重言式 A的主析取范式含的主析取范式含2n个极小项个极小项 A的主合取范式为的主合取范式为1 A为矛盾式为矛盾式 A的主析取范式为的主析取范式为0 A的主合析取范式含的主合析取范式含2n个极大项个极大项 A为非重言式的可满足式为非重言式的可满足式 A的主析取范式中至少含一个（但不是全部）的主析取范式中至少含一个（但不是全部）极小项极小项 A的主合取范式中至少含一个（但不是全部）的主合取范式中至少含一个（但不是全部）极大项极大项492.2 析取范式和合取范式q2. 判断公式的类型判断公式的类型 例：例： 用公式的主析取
26、范式判断下述公式的类型：用公式的主析取范式判断下述公式的类型： （1） ( p q) q （2）p( p q) （3）( p q) r502.2 析取范式和合取范式q3. 判断两个命题公式是否等值判断两个命题公式是否等值 例：例： 用主析取范式判两个公式是否等值用主析取范式判两个公式是否等值 p(qr) 与与 (p q)r p(qr) 与与 (pq)r 解：解： p(qr) m0 m1 m2 m3 m4 m5 m7 (p q)r m0 m1 m2 m3 m4 m5 m7 (pq)r m1 m3 m4 m5 m7 显见，显见，中的两公式等值，而中的两公式等值，而的不等值的不等值. 512.2 析
27、取范式和合取范式q例：某研究所要从例：某研究所要从3名科研骨干名科研骨干A，B，C中挑中挑选选12名出国进修，由于工作需要，选派时要名出国进修，由于工作需要，选派时要满足以下条件：满足以下条件：若若A去，则去，则C同去。同去。若若B去，则去，则C不能去。不能去。若若C不去，则不去，则A或或B可以去。可以去。解解:设设p：派：派A去；去；q：派：派B去；去；r：派：派C去。去。则则(pr) (qr)(r (pq) 522.2 析取范式和合取范式经演算可得：经演算可得：(pr) (qr)(r (pq) m1m2m5可知选派方案有三种：可知选派方案有三种：C去，去，A，B都不去。都不去。B去，去，A
28、，C不去。不去。A，C去，去，B不去。不去。532.2 析取范式和合取范式 主合取范式与主析取范式转换主合取范式与主析取范式转换q公式公式: A = mi1 mi2 misv A = mj1 mj2 mjt ，t=2n-sv A A (mj1 mj2 mjt ) mj1 mj2 mjt Mj1 Mj2 Mjt 542.2 析取范式和合取范式q讨讨论论：具具有有n个个变变项项的的命命题题公公式式有有多多少少个个不不同同的的主主析取范式？析取范式？q对对于于含含有有个个变变项项的的命命题题公公式式，必必定定可可写写出出22n个个主主析取范式析取范式(包括包括0)。q同同理理，含含有有个个变变项项的
29、的命命题题公公式式，也也可可写写出出22n个个主主合取范式合取范式(包括包括1)。55 第三节：联结词的完备集第三节：联结词的完备集562.3 联结词的完备集“与非与非”联结词：联结词：符号符号“”(pq)读作：读作：“p与与q的的否定否定”q(pq)(pq)pqpqFFTFTTTFTTTF572.3联结词的完备集q“或非或非”联结词：联结词： 符号：符号：“” (pq)读作：读作：“p或或q的否定的否定” (pq) (pq)pqpqFFTFTFTFFTTF582.3 联结词的完备集联结词的完备集q真值函数真值函数F: 0,1n 0,1q联结词完备集联结词完备集S: vS是一个联结词集合是一个
30、联结词集合v每一个真值函数都可以由仅含每一个真值函数都可以由仅含S中的联结词构成中的联结词构成的公式表示的公式表示q定理定理: S = ， ， 是联结词完备集是联结词完备集 证明：证明：任何一个任何一个n（n 1）元真值函数都与唯）元真值函数都与唯一的一个主析取范式等值，而主析取范式仅含一的一个主析取范式等值，而主析取范式仅含 ， ， 592.3 联结词的完备集联结词的完备集q推论推论: S = ， 是联结词完备集是联结词完备集 证明：证明：p q (p q) ( p q) 602.3 联结词的完备集联结词的完备集q定理定理: ， 是联结词完备集是联结词完备集证明：证明：首先，首先， p (p
31、 p) pp其次，其次，p q (p q) (pq) (pq) (pq) p q (pp) (qq) (pq) (p q)61第二章第二章 习题课习题课q主要内容主要内容l等值式与等值演算等值式与等值演算l基本等值式（基本等值式（1616组，组，2424个公式）个公式）l主析取范式与主合取范式主析取范式与主合取范式l联结词完备集联结词完备集62基本要求基本要求l深刻理解等值式的概念深刻理解等值式的概念l牢记基本等值式的名称及它们的内容牢记基本等值式的名称及它们的内容l熟练地应用基本等值式及置换规则进行等值演算熟练地应用基本等值式及置换规则进行等值演算l理解文字、简单析取式、简单合取式、析取范式
32、、合取范理解文字、简单析取式、简单合取式、析取范式、合取范式的概念式的概念l深刻理解极小项、极大项的概念、名称及下角标与成真、深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系成假赋值的关系l熟练掌握求主范式的方法（等值演算、真值表等）熟练掌握求主范式的方法（等值演算、真值表等）l会用主范式求公式的成真赋值、成假赋值、判断公式的类会用主范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值型、判断两个公式是否等值l会将公式等值地化成指定联结词完备集中的公式会将公式等值地化成指定联结词完备集中的公式l会用命题逻辑的概念及运算解决简单的应用问题会用命题逻辑的概念及运算解
33、决简单的应用问题63练习练习1:概念概念1. 设设A与与B为含为含n个命题变项的公式，判断下列命题是个命题变项的公式，判断下列命题是否为真？否为真？(1) AB当且仅当当且仅当A与与B有相同的主析取范式有相同的主析取范式(2) 若若A为重言式，则为重言式，则A的主合取范式为的主合取范式为0(3) 若若A为矛盾式，则为矛盾式，则A的主析取范式为的主析取范式为1(4) 任何公式都能等值地化成任何公式都能等值地化成 , 中的公式中的公式(5) 任何公式都能等值地化成任何公式都能等值地化成 , , 中的公式中的公式说明说明:(2) 重言式的主合取范式不含任何极大项，为重言式的主合取范式不含任何极大项，
34、为1. (3) 矛盾式的主析取范式不含任何极小项矛盾式的主析取范式不含任何极小项, 为为0. (4) , 不是完备集，如矛盾式不能写成不是完备集，如矛盾式不能写成 , 中的公式中的公式. (5) , 是完备集是完备集. 真真假假假假假假真真64练习练习2：联结词完备集联结词完备集2将将A = (pq) r改写成下述各联结词集中的公式改写成下述各联结词集中的公式: (1) , , (2) , (3) , (4) , (5) (6) 解解 (1) (pq) r ( pq) r (2) (pq) r (p q) r (3) (pq) r ( pq) r ( ( pq)r)65练习练习2 解答解答 (
35、4) (pq) r ( (pq)r) (pq)r) (5) (pq) r (p q) r (p q) r (p q) r) (p q) r) (p q) r) (6) (pq) r ( pq) r ( ( pq)r) ( pq)r (p p) (q q) (r r) 说明：答案不惟一说明：答案不惟一66练习练习3：应用题：应用题3. 某公司要从赵、钱、孙、李、周五名新毕业的大某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习学生中选派一些人出国学习. 选派必须满足以下选派必须满足以下条件：条件：(1) 若赵去，钱也去若赵去，钱也去(2) 李、周两人中至少有一人去李、周两人中至少
36、有一人去(3) 钱、孙两人中去且仅去一人钱、孙两人中去且仅去一人(4) 孙、李两人同去或同不去孙、李两人同去或同不去(5) 若周去，则赵、钱也去若周去，则赵、钱也去用等值演算法分析该公司如何选派他们出国？用等值演算法分析该公司如何选派他们出国？67练习练习3解答解答解此类问题的步骤：解此类问题的步骤：1.设简单命题并符号化设简单命题并符号化2. 用复合命题描述各条件用复合命题描述各条件3. 写出由复合命题组成的合取式写出由复合命题组成的合取式4. 将合取式化成主范式将合取式化成主范式5. 求成真赋值求成真赋值, 并做出解释和结论并做出解释和结论68练习练习3解答解答解解1. 设简单命题并符号化
37、设简单命题并符号化设设 p: 派赵去，派赵去，q: 派钱去，派钱去，r: 派孙去，派孙去，s: 派李去，派李去，u: 派周去派周去2. 写出复合命题写出复合命题(1) 若赵去，钱也去若赵去，钱也去 pq(2) 李、周两人中至少有一人去李、周两人中至少有一人去 s u(3) 钱、孙两人中去且仅去一人钱、孙两人中去且仅去一人 (qr) ( q r)(4) 孙、李两人同去或同不去孙、李两人同去或同不去 (r s) ( rs)(5) 若周去，则赵、钱也去若周去，则赵、钱也去 u(p q) 693. 设设(1)(5)构成的合取式为构成的合取式为A A = (pq) (s u) (qr) ( q r) (r s) ( rs) (u(p q)4. 化成析取式化成析取式 A ( pq r su) (p qrs u)结论：由上述析取式可知，结论：由上述析取式可知，A的成真赋值为的成真赋值为00110与与11001， 派孙、李去（赵、钱、周不去）派孙、李去（赵、钱、周不去） 派赵、钱、周去（孙、李不去）派赵、钱、周去（孙、李不去）练习练习3解答解答70作业作业q5（2）q6（2）q15q27q29
