1、第二章:命题逻辑等值演算,主要内容： 等值式与基本的等值式 等值演算与置换规则 析取范式与合取范式，主析取范式与主合取范式 联结词完备集本章与其他各章的联系 是第一章的抽象与延伸 是后续各章的先行准备,第一节：等值式,2.1 等值式,若等价式AB是重言式，则称A与B等值，记作AB，并称AB是等值式 几点说明：定义中，A, B, 均为元语言符号A或B中可能有哑元出现. 例如，在 (pq) (pq) (rr) 中，r为左边公式的哑元. 用真值表可验证两个公式是否等值,2.1 等值式,例子 判断pp,2.1 等值式,例子 判断 pq pq,2.1 等值式,如果命题变项很多，怎么办？ - 利用已知的等
2、值式通过代换得到新的等值式命题：设A是一个命题公式，含有命题变项p1，p2，pn，又设A1，A2，An是任意的命题公式. 对每个i（i=1，2，n），把pi在A中的所有出现都替换成Ai，所得到的新命题公式记作B. 那么，如果A是重言式，则B也是重言式.,2.1 等值式,否定律双重否定律 pp德摩根律 (p q) p q (p q) p q幂等律 p p p， p p p交换律 p q q p p q q p p q q p,2.1 等值式,结合律(p q) r p (q r)(p q) r p (q r)(p q) r p (q r)分配律p (q r) (p q) (p r)p (q r)
3、(p q) (p r),2.1 等值式,常元律零律: p 1 1， p 0 0同一律: p 0 p， p 1 p排中律: p p 1矛盾律: p p 0吸收律p (p q) pp (p q) p,2.1 等值式,蕴涵等值式 p q p q等价等值式 p q (p q) (q p)假言易位 p q q p等价否定等值式 p q p q归谬论 (p q ) (p q ) p,2.1 等值式,说明： (1)16组等值模式都可以给出无穷多个同类型的具体的等值式。 (2)证明上述16组等值式的代入实例方法可用真值表法，把改为所得的命题公式为永真式，则成立。,2.1 等值式,等值演算：由已知的等值式推演出
4、另外一些等值式的过程置换规则：设(A)是含公式A的命题公式， (B)是用公式B置换了(A)中所有A后得到的命题公式，若B ，则(A) (B) 说明：等值演算过程中遵循的重要规则一个命题公式A，经多次置换，所得到的新公式与原公式等价,2.1 等值式,1.用等值演算验证等值式 试证：p(qr) (p q)r证明：p(qr)p(qr) p(qr)pqr pqr(p q) r(p q) r (p q)r,2.1 等值式,试证：(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),2.1 等值式,
5、2. 用等值演算判断公式的类型证明：(pq) (p (qr)(pq)(p r)为一永真式证明：原式 (pq) (p(q r)(pq)(pr) (pq) (pq) (pr)(pq) (pr) (pq) (pr)(pq) (pr) 1,2.1 等值式,3解判定问题 在某次研讨会的中间休息时间，3名与会者根据王教授的口音对他是哪个省市的人判断如下： 甲：王教授不是苏州人，是上海人 乙：王教授不是上海人，是苏州人 丙：王教授既不是上海人，也不是杭州人 听完这3人的判断后，王教授笑着说，你们3人中有一人说得全对，有一人说对了一半，另一人说得全不对。试用逻辑演算分析王教授到底是哪里人。,第二节：析取范式与
6、合取范式,2.2 析取范式和合取范式,文字(literal): 命题变项及其否定简单析取式:仅由有限个文字构成的析取式简单合取式:仅由有限个文字构成的合取式例：设p、q为二个命题变元p，q，pp，qq，pq， q p，pq，p q 称为简单析取式p，q，pp，qq， pq， q p，pq，p q 称为简单合取式。,2.2 析取范式和合取范式,定理: 1)一个简单析取式是永真式当且仅当它同时含某个命题变元及它的否定式2)一个简单合取式是永假式当且仅当它同时含某个命题变元及它的否定式,2.2 析取范式和合取范式,析取范式:由有限个简单合取式构成的析取式A1 An, Ai 为简单合取式(p q) (
7、p r)合取范式:由有限个简单析取式构成的合取式A1 An, Ai 为简单析取式(p q) (p r)析取范式与合取范式统称为范式,2.2 析取范式和合取范式,定理：Ai 简单合取式， A1 An F 当且仅当 Ai F，任意AiAi 简单析取式， A1 An T 当且仅当 Ai T，任意Ai,2.2 析取范式和合取范式,范式存在定理: 任意命题公式都存在着与之等值的析取范式与合取范式方法： 步骤一：消去“”、“”联结词步骤二：消去双重否定符，内移否定符步骤三：使用分配律,2.2 析取范式和合取范式,范式存在定理: 任意命题公式都存在着与之等值的析取范式与合取范式方法： 步骤一：消去“”、“”
8、联结词步骤二：消去双重否定符，内移否定符步骤三：使用分配律,2.2 析取范式和合取范式,步骤一：利用等值公式：化去“”、“”联结词 p q p q p q (p q) (q p),2.2 析取范式和合取范式,范式存在定理: 任意命题公式都存在着与之等值的析取范式与合取范式方法： 步骤一：消去“”、“”联结词步骤二：消去双重否定符，内移否定符步骤三：使用分配律,2.2 析取范式和合取范式,消去双重否定符，内移否定符德摩根律 (p q) p q (p q) p q双重否定律 p p,2.2 析取范式和合取范式,范式存在定理: 任意命题公式都存在着与之等值的析取范式与合取范式方法： 步骤一：消去“”
9、、“”联结词步骤二：消去双重否定符，内移否定符步骤三：使用分配律,2.2 析取范式和合取范式,利用“”对“”的分配，将公式化成为析取范式p (q r) (p q) (p r)利用“”对“”的分配，将公式化成为合取范式p (q r) (p q) (p r),2.2 析取范式和合取范式,例：求(p q) (p q)的析取范式 化去 ( p q) (p q)“”对“”分配，化为析取范式 ( p p q) (q p q) 最简析取范式 p q,2.2 析取范式和合取范式,例：求(p q) r) p的析取范式和合取范式 (一) 求析取范式原式 (p q) r) p (p q) r) p ( (p q)
10、r) p (p q) r) p (p r) (q r) p p (p r) (q r) p (q r),2.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),2.2 析取范式和合取范式,问题：一个命题公式的析取范式是不是唯一的？同一命题公式的析取范式是不是等值的？,2.2 析取范式和合取范式,极小项(极大项):含有n个命题变项的简单合取式 (简单析取式)，并满足每个命题变元和它的否定式不同时出现，而二者之一必出现且仅出现一次第i个命题变项或它的否定式出现在
11、从左算起的第i位上(若无角标，则按字典顺序排列)若有个命题变项，则有2n个极小项（极大项）如果我们把不带否定符的命题变项取成1，带否定符的命题变项取成0，那么每一个极小项都对应一个二进制数，因而也对应一个十进制数,2.2 析取范式和合取范式,极小项的编码:对应成真赋值三个变元p、q、r可构造8个极小项： pqr FFF 0 记作 m0 pqr FFT 1 记作 m1 pqr FTF 2 记作 m2 pqr FTT 3 记作 m3 pqr TFF 4 记作 m4 pqr TFT 5 记作 m5 pqr TTF 6 记作 m6 pqr TTT 7 记作 m7,2.2 析取范式和合取范式,极大项的编
12、码:对应成假赋值如三个变元 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 记作 M7,2.2 析取范式和合取范式,定理:设mi和Mi是命题变元p1, p2 pn形成的极小项和极大项，则：(1) mi mj F, (ij)(2) Mi Mj T, (ij)(3) mi Mi； Mi mi,2.2 析取范式和合取范式,主析取范式(主合取范式)：由n个命题变项构成的析取范式(合取范式)中所有的简单合取式(简单析取式)都是极小项(极大项)定理: 任何
13、命题公式都存在着与其等值的主析取范式和主合取范式，并且是唯一的。,2.2 析取范式和合取范式,证法一在真值表中，使命题公式的真值为T的指派所对应的极小项的析取，即为此公式的主析取范式证：给定一个命题公式A，使其为T的真值指派所对应的极小项为m1, m2, mk,这些极小项的析取记为B，为此要证AB，即要证A与B在相同的指派下具有相同的真值。,2.2 析取范式和合取范式,首先对于使A为T的指派显然使B为T对于使A为F的指派，它对应的极小项(设为mj )不包含在m1, m2, mk 中。所以 mj为使B为F的指派所以A B 得证,2.2 析取范式和合取范式,一个公式的主析取范式即为令此公式的真值为
14、T的指派所对应的极小项的析取。一个命题公式的真值表是唯一的，因此一个命题公式的主析取范式也是唯一的,2.2 析取范式和合取范式,p q r m1 m3 m5 m6 m7,pqr的真值表,2.2 析取范式和合取范式,证法二：构造法用等值演算方法求命题公式主析取范式的方法将命题公式化归为与其等值的析取范式添变元: 消去重复项,Ai (pj pj) (Ai pj) (Ai pj),2.2 析取范式和合取范式,例：求(p(pq)q的主析取范式解：原式(pp)(pq)q -(1)化为析取范式 (pq)q -(2)化简(pq)(q(pp)(pq)(pq)(pq) -(3)添项(pq)(pq) m1 m3
15、-(4)合并相同最小项,2.2 析取范式和合取范式,主合取范式任何一个命题公式都可求得它的主合取范式一个命题公式的主合取范式是唯一的在真值表中，令命题公式的真值为“F”的指派就对应其主合取范式的一个极大项构造法,2.2 析取范式和合取范式,例:求p(pq)q的主合取范式 解：原式 p(pq)q(pp)(pq)q(pq)q(pq) q(pq)(q(p p) (pq)(pq) M0 M2,2.2 析取范式和合取范式,主析（合）取范式的用途讨论：求公式的成真与成假赋值判断公式类型判断两个命题公式是否等值应用主析（合）取范式分析和解决实际问题,2.2 析取范式和合取范式,1. 求公式的成真与成假赋值
16、例：(pq)r m1m3m5 m6m7 成真赋值为001, 011, 101, 110, 111 成假赋值为000, 010, 100,2.2 析取范式和合取范式,2. 判断公式的类型 设A含n个命题变项 A为重言式 A的主析取范式含2n个极小项 A的主合取范式为1 A为矛盾式 A的主析取范式为0 A的主合析取范式含2n个极大项 A为非重言式的可满足式 A的主析取范式中至少含一个（但不是全部）极小项 A的主合取范式中至少含一个（但不是全部）极大项,2.2 析取范式和合取范式,2. 判断公式的类型 例： 用公式的主析取范式判断下述公式的类型： （1）( p q) q （2）p( p q) （3）
17、( p q) r,2.2 析取范式和合取范式,3. 判断两个命题公式是否等值 例： 用主析取范式判两个公式是否等值 p(qr) 与 (pq)r p(qr) 与 (pq)r 解： p(qr) m0m1m2m3 m4m5 m7 (pq)r m0m1m2m3 m4m5 m7 (pq)r m1m3 m4m5 m7 显见，中的两公式等值，而的不等值.,2.2 析取范式和合取范式,例：某研究所要从3名科研骨干A，B，C中挑选12名出国进修，由于工作需要，选派时要满足以下条件：若A去，则C同去。若B去，则C不能去。若C不去，则A或B可以去。解:设p：派A去；q：派B去；r：派C去。则(pr) (qr)(r
18、(pq),2.2 析取范式和合取范式,经演算可得：(pr) (qr)(r (pq) m1m2m5可知选派方案有三种：C去，A，B都不去。B去，A，C不去。A，C去，B不去。,2.2 析取范式和合取范式,主合取范式与主析取范式转换公式: A = mi1 mi2 mis A = mj1 mj2 mjt ，t=2n-s A A (mj1 mj2 mjt ) mj1 mj2 mjt Mj1 Mj2 Mjt,2.2 析取范式和合取范式,讨论：具有n个变项的命题公式有多少个不同的主析取范式？对于含有个变项的命题公式，必定可写出22n个主析取范式(包括0)。同理，含有个变项的命题公式，也可写出22n个主合取
19、范式(包括1)。,第三节：联结词的完备集,2.3 联结词的完备集,“与非”联结词：符号“”(pq)读作：“p与q的否定”(pq)(pq),2.3联结词的完备集,“或非”联结词： 符号：“” (pq)读作：“p或q的否定” (pq) (pq),2.3 联结词的完备集,真值函数F: 0,1n 0,1联结词完备集S: S是一个联结词集合每一个真值函数都可以由仅含S中的联结词构成的公式表示定理: S =，是联结词完备集 证明：任何一个n（n1）元真值函数都与唯一的一个主析取范式等值，而主析取范式仅含，,2.3 联结词的完备集,推论: S =，是联结词完备集 证明：p q (p q) ( p q),2.
20、3 联结词的完备集,定理: ， 是联结词完备集证明：首先， p (p p) pp其次，p q (p q) (pq) (pq) (pq) p q (pp) (qq),(pq) (pq),第二章 习题课,主要内容等值式与等值演算基本等值式（16组，24个公式）主析取范式与主合取范式联结词完备集,基本要求,深刻理解等值式的概念牢记基本等值式的名称及它们的内容熟练地应用基本等值式及置换规则进行等值演算理解文字、简单析取式、简单合取式、析取范式、合取范式的概念深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系熟练掌握求主范式的方法（等值演算、真值表等）会用主范式求公式的成真赋值、成假赋值、
21、判断公式的类型、判断两个公式是否等值会将公式等值地化成指定联结词完备集中的公式会用命题逻辑的概念及运算解决简单的应用问题,练习1:概念,1. 设A与B为含n个命题变项的公式，判断下列命题是否为真？(1) AB当且仅当A与B有相同的主析取范式(2) 若A为重言式，则A的主合取范式为0(3) 若A为矛盾式，则A的主析取范式为1(4) 任何公式都能等值地化成, 中的公式(5) 任何公式都能等值地化成, , 中的公式,说明:(2) 重言式的主合取范式不含任何极大项，为1. (3) 矛盾式的主析取范式不含任何极小项, 为0. (4) , 不是完备集，如矛盾式不能写成, 中的公式. (5) , 是完备集.
22、,真,假,假,假,真,练习2：联结词完备集,2将A = (pq)r改写成下述各联结词集中的公式: (1) , , (2) , (3) , (4) , (5) (6) ,解 (1) (pq)r (pq)r (2) (pq)r (pq)r (3) (pq)r (pq)r (pq)r),练习2 解答,(4) (pq)r (pq)r) (pq)r) (5) (pq)r (pq)r (pq)r (pq)r) (pq)r)(pq)r) (6) (pq)r (pq)r (pq)r) (pq)r (pp)(qq)(rr) 说明：答案不惟一,练习3：应用题,3. 某公司要从赵、钱、孙、李、周五名新毕业的大学生中
23、选派一些人出国学习. 选派必须满足以下条件：(1) 若赵去，钱也去(2) 李、周两人中至少有一人去(3) 钱、孙两人中去且仅去一人(4) 孙、李两人同去或同不去(5) 若周去，则赵、钱也去用等值演算法分析该公司如何选派他们出国？,练习3解答,解此类问题的步骤：1.设简单命题并符号化2. 用复合命题描述各条件3. 写出由复合命题组成的合取式4. 将合取式化成主范式5. 求成真赋值, 并做出解释和结论,练习3解答,解1. 设简单命题并符号化设 p: 派赵去，q: 派钱去，r: 派孙去，s: 派李去，u: 派周去2. 写出复合命题(1) 若赵去，钱也去 pq(2) 李、周两人中至少有一人去 su(3) 钱、孙两人中去且仅去一人 (qr)(qr)(4) 孙、李两人同去或同不去 (rs)(rs)(5) 若周去，则赵、钱也去 u(pq),3. 设(1)(5)构成的合取式为A A = (pq)(su)(qr)(qr) (rs)(rs)(u(pq)4. 化成析取式 A (pqrsu)(pqrsu)结论：由上述析取式可知，A的成真赋值为00110与11001， 派孙、李去（赵、钱、周不去） 派赵、钱、周去（孙、李不去）,练习3解答,作业,5（2）6（2）152729,
