命题逻辑ppt课件.ppt

1,命题逻辑,2,第2章 命题逻辑,2.1 命题及其表示 2.2 命题公式 2.3 命题公式间的关系 2.4 主范式与判定定理 2.5 命题逻辑的推理理论,3,2.1 命题及其表示,命题与真值 原子命题 复合命题 命题常项 命题变项 联结词,4,命题与真值,命题: 能判断真假的陈述句。这种陈述句的判断只有两种可能：一种是 正确的判断，一种是错误的判断。称判断为正确的命题的真值（或 值）为真，称判断为错误的命题的真值（或值）为假。 因此又可称命题是具有唯一真值的陈述句或判断结果惟一的陈述句 命题的真值: 判断的结果 真值的取值: 真与假 二者取一 真命题: 真值为真的命题 假命题: 真值为假的命题 注意: 感叹句、祈使句、疑问句都不是命题 陈述句中的悖论以及判断结果不惟一确定的也不是命题,5,例 下列句子中那些是命题？ (1) 是无理数. (2) 2 + 5 8. (3) x + 5 3. (4) 你有铅笔吗？ (5) 这只兔子跑得真快呀！ (6) 请不要讲话！ (7) 我正在说谎话.,真命题,假命题,真值不确定,疑问句,感叹句,祈使句,悖论,(3)(7)都不是命题,6,理发师悖论,某乡村有一位理发师，一天他宣布：只给不自己理发的人理发。这里就产生了问题：理发师给不给自己理发？ 如果他给自己理发，他就是自己理发的人，按照他的原则，他不能给自己理发； 如果他不给自己理发，他就是不自己理发的人，按照他的原则，他就应该给自己理发。 这就产生了矛盾。,7,命题的分类,简单命题(原子命题)： 简单陈述句构成的命题 复合命题： 由简单命题用联结词联结而成的命题,8,简单命题符号化,在本书中用小写英文字母 p, q, r, ,pi,qi,ri (i1）表示简单命题，将表示命题的符号放在该命题的前面，称为命题符号化。 用“1”表示真，用“0”表示假 对简单命题而言，它的真值是确定的，因而又称为命题常项或命题常元。 例如，令 p： 是有理数，则 p 的真值为 0 q：2 + 5 = 7，则 q 的真值为 1 见课本例1.2,9,联结词与复合命题,1.否定式与否定联结词“” 定义2.1 设p为任一命题，复合命题 “非p”（或 “p的否定”）称为p的否定式，记作p，符号称作否定联结词，并规定p 为真当且仅当（即：等价）p为假 2.合取式与合取联结词“” 定义 2.2设p,q为两命题,复合命题“p并且q”(或“p与q”)称 为p与q的合取式，记作pq，称作合取联结词，并规 定 pq为真当且仅当p与q同时为真 注意：描述合取式的灵活性与多样性 分清简单命题与复合命题,10,例 将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. (4) 王晓不是不聪明，而是不用功. (5) 张辉与王丽都是三好学生. (6) 张辉与王丽是同学. 解 令 p：王晓用功，q：王晓聪明，则 (1) pq (2) pq (3) pq.,11,例 (续),(4) (p)q. 令 r : 张辉是三好学生，s :王丽是三好学生 (5) rs. (6) 令 t : 张辉与王丽是同学，t 是简单命题 .,说明: (1)(4)说明描述合取式的灵活性与多样性. (5) 中“与”联结的是句子的主语成分，因而(5) 中句子是简单命题.,12,联结词与复合命题(续),定义2.3 设 p,q为二命题，复合命题“p或q”称作p与q的析取式，记作pq，称作析取联结词，并规定 pq为假当且仅当p与q同时为假. 即:pq为真当且仅当p与q至少有一个为真。 此处定义的析取式pq表示的是一种相容性或，即允许p与q同时为真 注意区分自然言语中“或”的二义性。见课本描述。,例 将下列命题符号化 (1) 2或4是素数. (2) 2或3是素数. (3) 4或6是素数. (4) 小元元只能拿一个苹果或一个梨. (5) 王晓红生于1975年或1976年.,3.析取式与析取联结词“”,13,解 令 p:2是素数, q:3是素数, r:4是素数, s:6是素数, 则 (1), (2), (3) 均为相容或. 分别符号化为: pr , pq, rs, 它们的真值分别为 1, 1, 0. 而 (4), (5) 为排斥或. 令 t :小元元拿一个苹果，u:小元元拿一个梨， 则 (4) 符号化为 (tu) (tu). 令v :王晓红生于1975年,w:王晓红生于1976年,则 (5) 既可符号化为 (vw)(vw), 又可符号化为 vw , 为什么? （看vw 的值是多少？）,14,联结词与复合命题(续),定义2.4 设 p,q为二命题，复合命题 “如果p,则q” 称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件. 称作蕴涵联结词，并规定，pq为假当且仅当 p 为真 q 为假.,4.蕴涵式与蕴涵联结词“”,15,pq 的逻辑关系：q为p的必要条件 或p为q的充分条件 （找关系时，要分清蕴涵式的前件与后件， 即找准充分条件或必要条件） “如果 p，则 q ” 的不同表述法很多： 若 p，就 q（ p是q的充分条件 ） 只要 p，就 q （ p是q的充分条件 ） p 仅当 q （ q是p的必要条件 ） 只有 q 才 p （ q是p的必要条件 ） 除非 q, 才 p 或 除非 q, 否则非 p，(必须记住) 否则非 可以理解为 才 当 p 为假时，pq 为真 常出现的错误：不分充分与必要条件 见课本中注意的两点事项,联结词与复合命题(续),16,例 设 p:天冷，q:小王穿羽绒服， 将下列命题符号化 (1) 只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候.,注意： pq 与 q p 等值（真值相同）,pq,pq,pq,pq,qp,qp,qp,qp,17,联结词与复合命题(续),定义2.5 设p，q为二命题，复合命题 “p当且仅当q”称作p与q的等价式，记作pq，称作等价联结词. pq为真当且仅当p与q同时为真或同时为假. 说明: (1) pq 的逻辑关系:p与q互为充分必要条件 (2) pq为真当且仅当p与q同真或同假,5.等价式与等价联结词“”,18,例 求下列复合命题的真值 (1) 2 + 2 4 当且仅当 3 + 3 6. (2) 2 + 2 4 当且仅当 3 是偶数. (3) 2 + 2 4 当且仅当 太阳从东方升起. (4) 2 + 2 4 当且仅当 美国位于非洲. (5) 函数 f (x) 在x0 可导的充要条件是它在 x0 连续. 它们的真值分别为 1，0，1，0，0.,19,用联结词把各种各样的复合命题符号化,基本步骤： 1：分析出各简单命题，将它们符号化； 2：使用合适的联结词，把简单命题逐个联结起来，组成复合命题的符号化表示。 注意析取联结词的应用,20,联结词与复合命题(续),以上给出了5个联结词：, , , , ，组成 一个联结词集合, , , , ， 联结词的优先顺序为：, , , , ; 1:如果出现的联结词同级，又无括号时，则按从左到右的顺序运算; 2:若遇有括号时，应该先进行括号中的运算. 注意: 本书中使用的 括号全为圆括号（）.,21,2.2 命题公式,命题变项与合式公式 公式的赋值 真值表 命题的分类 重言式 矛盾式 可满足式,22,命题变项与合式公式,命题常项：简单命题 原子命题 命题变项：真值不确定的陈述句 定义2.6 合式公式 (命题公式, 公式) 递归定义如下： (1) 单个命题常项或变项 p,q,r,pi ,qi ,ri ,0,1 是合式公式； (2) 若A是合式公式，则 (A)也是合式公式； (3) 若A, B是合式公式，则(AB), (AB), (AB), (AB)也是合式公式； (4) 只有有限次地应用(1)(3)形成的符号串才是合式公式。 注: 外层括号可以省去 问：命题公式是命题吗？ 不是，原因为：命题公式中可能含有命题变项。,23,合式公式的层次,定义 2.7 (1) 若公式A是单个的命题(常项或变项）, 则称A为 0层公式. (2) 称A是n+1(n0)层公式是指下面情况之一： (a) A= B, B是n层公式； (b) A=BC, 其中B,C分别为i层和j层公式，且 n=max(i, j)； (c) A=BC, 其中B,C的层次及n同(b)； (d) A=BC, 其中B,C的层次及n同(b)； (e) A=BC, 其中B,C的层次及n同(b). (3)若A的最高层次为k.则A是k层公式。,24,合式公式的层次 (续),例如 公式 p 0层 p 1层 pq 2层 (pq)r 3层 (pq) r)(rs) 4层,25,公式的赋值,定义2.8 给命题公式A中的所有的命题变项 p1, p2, , pn指定一组真值称为对A的一个赋值或 解释 成真赋值: 使公式为真的赋值 成假赋值: 使公式为假的赋值 说明： 赋值=12n之间不加标点符号，i=0或1. A中仅出现 p1, p2, , pn，给A赋值12n是 指 p1=1, p2=2, , pn=n A中仅出现 p, q, r, , 给A赋值123是指 p=1,q=2 , r=3 含n个变项的公式有2n个赋值.,26,真值表,真值表: 将命题公式A在所有赋值之下取值的情况列成表，成为A的真值表 例 给出公式的真值表 A= (qp) qp 的真值表,27,例 B = (pq) q 的真值表,实例,28,例 C= (pq) r 的真值表,29,公式的类型,定义2.9 设A为一个命题公式 (1) 若A在它的各种赋值下取值均为真，则称A为重言式(也称永真式) (2) 若A在它的各种赋值下取值均为假，则称A为矛盾式(也称永假式) (3) 若A至少存在一组赋值是成真赋值，则称A为可满足式 注意：重言式是可满足式，但反之不真. 上例中A为重言式，B为矛盾式，C为可满足式 A= (qp)qp，B =(pq)q，C= (pq)r,30,小结：,本节主要内容： 要理解所学的定义，利用所给的定义进行简单的判断和分析。 1：命题 命题常项 命题变项 简单命题 复合命题的定义。 2：联结词：, , , , 定义 取值情况，对应的语言词汇表达。 3：命题公式 层次 成真赋值 成假赋值 真值表的定义 4：构造真值表的具体步骤，重言式 矛盾式 可满足式 定义,31,上节知识复习,1:定义：命题 真(假)命题 命题常(变)项 2:五个联结词定义及取值情况，对应的 语言表达 3:复合命题符号化的步骤 4:命题公式 命题公式的层次定义及判断 5:成真赋值 成假赋值 重言式 矛盾式 可满足式定义 6:真值表定义及构造步骤,32,随堂练习,1：写出命题、简单命题的定义。 2：用符号定义五个联结词及其各自取值情况。 3：写出蕴涵式的定义，分析前件与后件的关系， 列出对应的语言表达形式。 4：写出遇到析取联结词二义性时的判断方式及对应 符号表示。 5：列出下面公式的真值表，说明各公式的层次 (pq)(pq)(qp) (pq)(pq) 6：写出命题公式的定义,33,随堂练习,7：命题符号化： a:只有天冷,小王才穿羽绒服. b:除非天冷,小王才穿羽绒服. c:除非小王穿羽绒服,否则天不冷. d:如果天不冷,则小王不穿羽绒服. e:小王穿羽绒服仅当天冷的时候. f:只有4是偶数，3才能被2整除。 g:选小王或小李中的一人当三好学生。 h:小王现在在宿舍或在图书馆里。,34,2.3 命题公式间的关系,学习目标： 等值式 基本等值式 等值演算 置换规则,35,等值式,定义 设A、B为两命题，若等价式AB是重言式，则称A与B等值的，记作AB，并称AB是等值式 说明：定义中符号“”不是联结词符，它只是当A与B等值时的一种记法。注意区分“”、“=”和“” 可以用真值表验证两个公式是否等值 等价关系具有自反性、对称性、传递性。 请验证：p(qr) (pq) r p(qr) (pq) r,36,用真值表法的验证方式,设A、B为两命题，由定义判断A与B是否等值，应判断AB是否为重言式，若AB的真值表最后一列全为1，则AB为重言式，因而AB，但最后一列全为1当且仅当在各赋值之下，A与B的真值相同。因而判断A与B是否等值等价于判断A、B的真值表是否相同。,37,基本等值式,利用真值表法可以验证很多等值式： 下面24个重要的等值式，是学好数理逻辑的关键基础，应当牢记！ 在下面的公式中，A、B、C代表任意的 命题公式。,38,基本等值式,双重否定律 : 1.AA 等幂律： 2. AAA, 3. AAA 交换律: 4.ABBA, 5. ABBA 结合律: 6. (AB)CA(BC) 7.(AB)CA(BC) 分配律: 8.A(BC)(AB)(AC) 9.A(BC) (AB)(AC),39,基本等值式(续),德·摩根律 : 10. (AB)AB 11.(AB)AB 吸收律: 12.A(AB)A, 13. A(AB)A 零律: 14. A11, 15.A00 同一律: 16.A0A, 17. A1A 排中律: 18.AA1 矛盾律: 19.AA0,40,基本等值式(续),蕴涵等值式: 20. ABAB 等价等值式: 21.AB(AB)(BA) 假言易位: 22. ABBA 等价否定等值式:23.ABAB 归谬论: 24.(AB)(AB) A 注意: A,B,C代表任意的命题公式 牢记这些等值式是继续学习的基础,41,等值演算与置换规则,等值演算: 由已知的等值式推演出新的等值式的过程 置换定理：设(A)是含命题公式A的命题， 若AB, 则(B)(A) 等值演算的基础： (1) 等值关系的性质：自反、对称、传递 (2) 基本的等值式 (3) 置换规则,42,应用举例证明两个公式等值,例1证明 p(qr) (pq)r 证 p(qr) p(qr) （蕴涵等值式） (pq)r （结合律） (pq)r （德摩根律） (pq) r （蕴涵等值式）,说明:也可以从右边开始演算（请做一遍） 因为每一步都用置换规则，故省略不写 熟练后，基本等值式也可以不写出,43,应用举例证明两个公式不等值,例2 证明: p(qr) (pq) r 用等值演算不能直接证明两个公式不等值,证明两 个公式不等值的基本思想是找到一个赋值使一个成 真,另一个成假. 方法一 真值表法（自己证） 方法二 观察赋值法. 容易看出000, 010等是左边的 成真赋值，是右边的成假赋值. 方法三 用等值演算先化简两个公式，再观察.,44,应用举例判断公式类型,例3 用等值演算法判断下列公式的类型 (1) q(pq) 解 q(pq) q(pq) （蕴涵等值式） q(pq) （德摩根律） p(qq) （交换律，结合律） p0 （矛盾律） 0 （零律） 由最后一步可知，该式为矛盾式.,45,例3 (续),(2) (pq)(qp) 解 (pq)(qp) (pq)(qp) （蕴涵等值式） (pq)(pq) （交换律） 1 由最后一步可知，该式为重言式. 问：最后一步为什么等值于1？,46,例3 (续),(3) (pq)(pq)r) 解 (pq)(pq)r) (p(qq)r （分配律） p1r（排中律）pr （同一律） 这不是矛盾式，也不是重言式，而是非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.,总结：A为矛盾式当且仅当A0 A为重言式当且仅当A1 说明：演算步骤不惟一,应尽量使演算短些,47,本节小结,熟悉等值、等值演算的定义 会用真值表法判断等值 记熟会用24个重要的等值式,48,2.4 主范式与判定为题,学习目标： 析取范式与合取范式 主析取范式与主合取范式,49,析取范式与合取范式,简单析取式:仅由有限个命题变项或其否定构成的析取式称为简单析取式。 如 p, q, pq, pqr, 简单合取式:仅由有限个命题变项或其否定构成的合取式称为简单合取式。 如 p, q, pq, pqr, 由定义可知： 1:一个简单析取式是重言式，当且仅当它同时含一个命题变项及其否定。 2:一个简单合取式是矛盾式，当且仅当它同时含一个命题变项及其否定。,50,析取范式与合取范式(续),析取范式:仅由有限个简单合取式组成的析取式称为析取范式。 A=A1A2Ar, 其中A1,A2,Ar是简单合取式。A是析取范式。 合取范式:仅由有限个简单析取式组成的合取式称为合取范式。 A=A1A2Ar , 其中A1,A2,Ar是简单析取式。A是合取范式。 显然：任何析取范式的对偶式为合取范式， 任何合取范式的对偶式为析取范式，,51,析取范式与合取范式(续),析取范式与合取范式有下列性质： 1：一个析取范式是矛盾式，当且仅当它的每个简单合取式都是矛盾式。 2：一个合取范式是重言式，当且仅当它的每个简单析取式都是重言。,52,析取范式与合取范式(续),范式:析取范式与合取范式的总称 公式A的析取范式: 与A等值的析取范式 公式A的合取范式: 与A等值的合取范式 说明： 单个命题变项及其否定既是简单析取式，又是简单合取式 形如 pqr, pqr 的公式既是析取范式， 又是合取范式 (为什么?),53,命题公式的范式,定理 （范式存在定理）任何命题公式都存在着与之等值的析取范式和合取范式. 求公式A的范式的步骤： (1) 由于,是全功能集，因而若A中含联结词, ,等，可用基本的等值式及置换规则将这些联结词消去。 (2) 否定联结词的内移或消去 (3) 使用分配律 对分配（求析取范式） 对分配（求合取范式） 公式的范式存在，但不惟一，这是它的局限性,54,求公式的范式举例,例 求下列公式的析取范式与合取范式 (1) A=(pq)r 解 (pq)r (pq)r （消去） pqr （结合律） 这既是A的析取范式（由3个简单合取式组成的析 取式），又是A的合取范式（由一个简单析取式 组成的合取式）,55,求公式的范式举例(续),(2) B=(pq)r 解 (pq)r (pq)r （消去第一个） (pq)r （消去第二个） (pq)r （否定号内移德摩根律） 这一步已为析取范式（两个简单合取式构成） 继续： (pq)r (pr)(qr) （对分配律） 这一步得到合取范式（由两个简单析取式构成）,56,极小项,定义 在含n个命题变项的简单合取式中，若每个命题变项与其否定不同时存在，而两者之一必出现且仅出现一次，且第i（1in）个命题变项或其否定出现在从左起的第i位上（若命题变项无角标，则按字典顺序排序），称这样的简单合取式为极小项. 说明： n个命题变项产生2n个极小项。2n个极小项均互不等值 用mi表示第i个极小项，将mi里的命题变项看成1，命题变项的否定看成0，则每个极小项对应一个二进制数，也对应一个十进制数。二进制数正是该极小项的成真赋值，十进制数i是该极小项成真赋值的十进制表示也是该极小项抽象表示法的角码.,57,由p, q, r三个命题变项形成的极小项,58,知识回顾,1:定义：排斥或 与非式 或非式 全功能集 冗余的（独立的）联结词 2:对偶式 对偶原理 简单合取式 简单析取式 析取范式与合取范式 极小项 3:求公式A的范式的步骤,59,主析取范式,定义：主析取范式: 设命题公式A中含n个命题变项，如果A的析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式 例如，n=3, 命题变项为p, q, r时， (pqr)(pqr) m1m3 是主析取范式 A的主析取范式: 与A等值的主析取范式,60,主析取范式(续),定理 2.5 任何命题公式的主析取范式都是存在的, 并且是惟一的. 用等值演算法求给定命题公式的主析取范式的步骤： (1) 先求A的析取范式A。 (2)若A的某简单合取式B中不含命题变项pi, 也不含否定pi ，则将B展成如下形式 B B1 B (pi pi) ( B pi )(B pi) (3) 将重复出现的命题变项、矛盾式及重复出现的极小项都“消去”，如pp用p取代， pp用0取代， mi mi用mi 取代。 (4) 将极小项按由小到大的顺序排序.并用 表示，如m1 m2 m5用(1,2,5)表示。,61,主析取范式用途,1：判断两命题公式是否等值 由于任何命题公式的主析取范式都是唯一的，因而若AB，说明A与B有相同的主析取范式。 反之，若A与B有相同的主析取范式，必有AB。 2：判断命题公式的类型 设A是含n个命题变项的命题公式，A为重言式，当且仅当A 的主析取范式中含全部2n个极小项。A为矛盾式，当且仅 当A的主析取范式中不含任何极小项。若A的主析取范式中 至少含一个极小项，则A是可满足式。 3：求命题公式的成真和成假赋值。,62,极大项,定义 在含有n个命题变项的简单析取式中，若每个命题变项与其否定不同时存在，而两者之一必出现且仅出现一次，且第i（1in）个命题变项或其否定出现在从左起的第i位上，称这样的简单析取式为极大项. 说明： n个命题变项产生2n个极大项。2n个极大项均互不等值 用Mi表示第i个极大项，将Mi里的命题变项看成0，命题变项的否定看成1，则每个极大项对应一个二进制数，也对应一个十进制数。二进制数正是该极大项的成假赋值，十进制数i是该极大项成真赋值的十进制表示也是该极大项抽象表示法的角码.,63,由p, q, r三个命题变项形成的极大项,64,知识回顾,掌握对偶式定义 对偶原理 定理1.2 简单合取式、简单析取式、析取范式、合取范式、主析取范式、主合取范式定义 主析取范式、主合取范式的求法、表示意义、与真值表之间的转化方式 极小项、极大项定义、二进制的成真赋值（成假赋值）与对应的十进制角标关系,65,极小项与极大项,注意： mi(Mi)称为极小项(极大项)的名称. mi与Mi的关系: mi Mi , Mi mi （结合定理1.2理解） 记忆理解极小项与极大项的定义、取值、用法时，重点记忆一个，另一个利用上述关系式推导即可,66,极小项与极大项(续),由p, q两个命题变项形成的极小项与极大项,67,主合取范式,定义：主合取范式: 设命题公式A中含n个命题变项，如果A的合取范式中的简单析取式全是极大项，则称该合取范式为A的主合取范式 例如，n=3, 命题变项为p, q, r时， (pqr)(pqr) M1M5 是主合取范式 A的主合取范式: 与A等值的主合取范式,68,主合取范式（续）,任意命题公式的主合取范式一定存在，且是唯一的。 求一命题公式A的主合取范式与求主析取范式的步骤非常相似，也是先求出合取范式A。若A的某简单析取式B中不含命题变项pi,， 也不含否定pi ，则将B展成如下形式： B B0 B(pi pi) (B pi )(B pi),69,主合取范式(续),由A的主析取范式求主合取范式的步骤为： (1):求出A的主析取范式中没包含的极小项 (2):求出与(1)中极小项角码相同的极大项 (3):由以上极大项构成的合取式为A的主合取式。,70,求公式的主范式,例 求公式 A=(pq)r的主析取范式与主合 取范式. (1) 求主析取范式 (pq)r (pq)r , （析取范式） (pq) (pq)(rr) (pqr)(pqr) m6m7 , ,71,求公式的主范式(续),r (pp)(qq)r (pqr)(pqr)(pqr)(pqr) m1m3m5m7 , 代入并排序，得 (pq)r m1m3m5 m6m7（主析取范式）,72,求公式的主范式(续),(2) 求A的主合取范式 (pq)r (pr)(qr) , （合取范式） pr p(qq)r (pqr)(pqr) M0M2, ,73,求公式的主范式(续),qr (pp)qr (pqr)(pqr) M0M4 , 代入并排序，得 (pq)r M0M2M4 （主合取范式）,74,主范式的用途与真值表相同,(1) 求公式的成真赋值和成假赋值 例如 (pq)r m1m3m5 m6m7， 其成真赋值为001, 011, 101, 110, 111， 其余的赋值 000, 010, 100为成假赋值. 类似地，由主合取范式也可立即求出成 假赋值和成真赋值.,75,主范式的用途(续),(2) 判断公式的类型 设A含n个命题变项，则 A为重言式A的主析取范式含2n个极小项 A的主合取范式为1. A为矛盾式 A的主析取范式为0 A的主合析取范式含2n个极大项 A为非重言式的可满足式 A的主析取范式中至少含一个且不含全部极小项 A的主合取范式中至少含一个且不含全部极大项,76,主范式的用途(续),例 用主析取范式判断下述两个公式是否等值： p(qr) 与 (pq)r p(qr) 与 (pq)r 解 p(qr) = m0m1m2m3 m4m5 m7 (pq)r = m0m1m2m3 m4m5 m7 (pq)r = m1m3 m4m5 m7 显见，中的两公式等值，而的不等值.,(3) 判断两个公式是否等值,说明：由公式A的主析取范式确定它的主合取范式，反之亦然. 用公式A的真值表求A的主范式.,77,主范式的用途(续),例 某公司要从赵、钱、孙、李、周五名新毕 业的大学生中选派一些人出国学习. 选派必须 满足以下条件： (1)若赵去，钱也去； (2)李、周两人中至少有一人去； (3)钱、孙两人中有一人去且仅去一人； (4)孙、李两人同去或同不去； (5)若周去，则赵、钱也去. 试用主析取范式法分析该公司如何选派他们出 国？,78,例 (续),解此类问题的步骤为： 将简单命题符号化 写出各复合命题 写出由中复合命题组成的合取式 求中所得公式的主析取范式,79,例 (续),解 设p：派赵去，q：派钱去，r：派孙去， s：派李去，u：派周去. (1) (pq) (2) (su) (3) (qr)(qr) (4) (rs)(rs) (5) (u(pq) (1) (5)构成的合取式为 A=(pq)(su)(qr)(qr) (rs)(rs)(u(pq),80,例 (续), A (pqrsu)(pqrsu) 结论：由可知，A的成真赋值为00110与11001， 因而派孙、李去（赵、钱、周不去）或派赵、钱、 周去（孙、李不去）. A的演算过程如下: A (pq)(qr)(qr)(su)(u(pq) (rs)(rs) （交换律) B1= (pq)(qr)(qr) (pqr)(pqr)(qr) （分配律）,81,例 (续),B2= (su)(u(pq) (su)(pqs)(pqu) （分配律） B1B2 (pqrsu)(pqrsu) (qrsu)(pqrs)(pqru) 再令 B3 = (rs)(rs) 得 A B1B2B3 (pqrsu)(pqrsu) 注意：在以上演算中多次用矛盾律 要求：自己演算一遍,82,2.5 命题逻辑的推理理论,本节目标： 推理的形式结构 判断推理是否正确的方法 推理定律与推理规则 构造证明法,83,推理的形式结构问题的引入,推理举例: (1) 正项级数收敛当且仅当部分和上有界. (2) 若AÈCÍBÈD，则AÍB且CÍD. 推理: 从前提推出结论的思维过程 前提是指已知的命题公式， 结论是从前提出发应用推理规则推出的命题公式 上面(1)是正确的推理，而(2)是错误的推理. 证明: 描述推理正确或错误的过程.,84,推理的形式结构,定义：若(A1ÙA2ÙÙAk)®B为重言式, 则称A1,A2, Ak推出结论B的推理正确 ,B是A1, A2, , Ak的逻辑结论或有效结论。称(A1ÙA2ÙÙAk )®B为由前提A1,A2, Ak推出结论B的推理的形式结构。 用AÞB表示A®B是重言式。 若由前提A1,A2, Ak 推出结论B的推理正确，则记 作：A1ÙA2ÙÙAkÞB.,85,判断推理是否正确的方法,由定义可知：判断推理是否正确的方法就是判断重 言蕴涵式的方法： 真值表法 等值演算法 主析取范式法 构造证明法 说明：当命题变项比较少时，用前3个方法比较方 便, 此时采用形式结构“ A1ÙA2ÙÙAk®B” . 而在构 造证明时，采用“前提: A1, A2, , Ak, 结论: B”.,86,实例,例 判断下面推理是否正确 (1) 若今天是1号，则明天是5号. 今天是1号. 所 以明天是5号. 解 设 p：今天是1号，q：明天是5号. 证明的形式结构为: (p®q)Ùp®q 证明（用等值演算法） (p®q)Ùp®q Û Ø(ØpÚq)Ùp)Úq Û ØpÚØqÚq Û 1 得证推理正确,87,实例 (续),(2) 若今天是1号，则明天是5号. 明天是5号. 所以今天是1号. 解 设p：今天是1号，q：明天是5号. 证明的形式结构为: (p®q)Ùq®p 证明（用主析取范式法） (p®q)Ùq®p Û (ØpÚq)Ùq®p Û Ø (ØpÚq)Ùq)Úp Û ØqÚp Û (ØpÙØq)Ú(pÙØq)Ú (pÙØq)Ú(pÙq) Û m0Úm2Úm3 结果不含m1, 故01是成假赋值，所以推理不正确.,88,推理定律重言蕴涵式,重要的推理定律 A Þ (AÚB) 附加律 (AÙB) Þ A 化简律 (A®B)ÙA Þ B 假言推理 (A®B)ÙØB Þ ØA 拒取式 (AÚB)ÙØB Þ A 析取三段论 (A®B)Ù(B®C) Þ (A®C) 假言三段论 (A«B)Ù(B«C) Þ (A«C) 等价三段论 (A®B)Ù(C®D)Ù(AÚC) Þ (BÚD) 构造性二难,89,推理定律 (续),(A®B)Ù(ØA®B)Ù(AÚØA) Þ B 构造性二难（特殊形式） (A®B)Ù(C®D)Ù( ØBÚØD) Þ (ØAÚØC) 破坏性二难（可由构造性二难推导出）,说明： A, B, C为命题公式符号 若某推理符合某条推理定律，则它自然是正确的 AÛB产生两条推理定律: A Þ B, B Þ A,90,推理定律 (续),8条推理定律可以分为四组记忆： 第一组：第1、2条 第二组：第3、4、5条 第三组：第6、7条（传递性） 第四组：第8条（构造性二难） 说明：证明是一个描述推理过程的命题公式序列，其中的每个命题公式或者是已知的前提，或者是由某些前提应用推理规则得到的结论。,91,推理规则：,1：前提引入规则：在证明的任何步骤上，都可以引入前提。 2：结论引入规则：在证明的任何步骤上，所证明的结论都可作为后续证明的前提。 3：置换规则：在证明的任何步骤上，命题公式的任何子命题公式都可以用与之等值的命题公式置换。例：可用ØAÚB置换A®B等。 注：课本上P23中例1.20上面规则中，(4)-(10)其实就是8条推理定律，(11)其实是两个前提的记法。,92,构造证明直接证明法,例 构造下面推理的证明： 若明天是星期一或星期三，我就有课. 若有课，今天必备课. 我今天下午没备课. 所以， 明天不是星期一和星期三. 解 设 p：明天是星期一，q：明天是星期三， r：我有课，s：我备课 形式结构为 前提：(pÚq)®r, r®s, Øs 结论：ØpÙØq,93,直接证明法 (续),证明 r®s 前提引入 Øs 前提引入 Ør 拒取式 (pÚq)®r 前提引入 Ø(pÚq) 拒取式 ØpÙØq 置换,94,知识回顾,极大项与极小项之间关系，主析取范式与主合取范式之间的转化方法及步骤 定义：前提、推理、逻辑结论 八条推理定律及三条推理规则,95,构造证明附加前提证明法,欲证明 前提：A1, A2, , Ak 结论：C®B 等价地证明 前提：A1, A2, , Ak, C 结论：B 理由： (A1ÙA2ÙÙAk)®(C®B) Û Ø( A1ÙA2ÙÙAk)Ú(ØCÚB) Û Ø( A1ÙA2ÙÙAkÙC)ÚB Û (A1ÙA2ÙÙAkÙC)®B,96,附加前提证明法 (续),例 构造下面推理的证明: 2是素数或合数. 若2是素数，则 是无理数. 若 是无理数，则4不是素数. 所以，如果4是 素数，则2是合数. 用附加前提证明法构造证明 解 设 p：2是素数，q：2是合数， r： 是无理数，s：4是素数 形式结构 前提：pÚq, p®r, r®Øs 结论：s®q,97,附加前提证明法 (续),证明：