1、1离散数学离散数学云南大学软件学院云南大学软件学院任课教师：谢仲文任课教师：谢仲文2013年秋季学期年秋季学期2绪论绪论 课程介绍和要求课程介绍和要求主要内容主要内容l教材说明教材说明l什么是离散数学？什么是离散数学？l为什么要学习离散数学？为什么要学习离散数学？l怎样学习离散数学？怎样学习离散数学？l课程要求与考试课程要求与考试3教材教材主教材：主教材：1、郝林等编著、郝林等编著.离散数学离散数学.北京北京:科学出版社科学出版社,2012年年5月月参考书目：参考书目：2、屈婉玲等编著、屈婉玲等编著.离散数学离散数学.北京北京:高等教育出版高等教育出版社，社，2008年年3月月3、左孝凌等编著
2、、左孝凌等编著.离散数学离散数学.上海上海:上海科学技上海科学技术文献出版社术文献出版社,2004年年1月月4问题问题l 什么是数理逻辑？（什么是数理逻辑？（符号化符号化+推理规则推理规则）l 经典数理逻辑经典数理逻辑和现代数理逻辑和现代数理逻辑主要内容主要内容l 命题逻辑命题逻辑l 谓词逻辑谓词逻辑l 推理与证明技术推理与证明技术第一部分第一部分 数理逻辑数理逻辑5第一讲第一讲 命题逻辑的基本概念命题逻辑的基本概念主要内容主要内容l命题与联结词命题与联结词 命题及其分类命题及其分类 联结词与复合命题联结词与复合命题l命题公式及其赋值命题公式及其赋值6命题与真值命题与真值 命题：命题：判断结果
3、惟一的陈述句判断结果惟一的陈述句 命题的命题的真值真值：判断的结果：判断的结果 真值的真值的取值范围取值范围：真与假：真与假 真命题与假命题真命题与假命题注意：注意：感叹句、祈使句、疑问句都不是命题感叹句、祈使句、疑问句都不是命题陈述句中的陈述句中的悖论悖论，判断结果不惟一确定的不是命题，判断结果不惟一确定的不是命题 1.1 命题与联结词命题与联结词7悖论悖论如果有一个句子如果有一个句子B，如果，如果承认承认B，则可以推出，则可以推出非非B成立；成立；反之，如果承认反之，如果承认非非B，又可推出，又可推出B成立成立。例子：例子：1、我正在说假话。、我正在说假话。2、罗素的理发师悖论。、罗素的理
4、发师悖论。3、克里特人伊壁孟德、克里特人伊壁孟德：所有的克里特人都是撒谎者。所有的克里特人都是撒谎者。悖论不是命题！悖论不是命题！悖论的共同特征：悖论的共同特征：论断者属于论断主体集论断者属于论断主体集。8例例1 1 下列句子中那些是命题？下列句子中那些是命题？(1)是有理数是有理数.(2)2+5=7.(3)x+5 3.(4)你去教室吗？你去教室吗？(5)这个苹果真大呀！这个苹果真大呀！(6)请不要讲话！请不要讲话！(7)2050年元旦下大雪年元旦下大雪.2 假命题假命题命题概念命题概念 真命题真命题不是命题不是命题 不是命题不是命题 不是命题不是命题不是命题不是命题命题，但真值现在不知道命题
5、，但真值现在不知道判断给定句子是否为命题的方法和步骤：判断给定句子是否为命题的方法和步骤：1、判断它是否为陈述句；、判断它是否为陈述句；2、判断它是否有唯一的真值。、判断它是否有唯一的真值。9命题分类：命题分类：简单命题简单命题（也称原子命题）与（也称原子命题）与复合命题复合命题简单命题符号化简单命题符号化：命题常量：命题常量l 用小写英文字母用小写英文字母 p,q,r,pi,qi,ri(i 1)表示简单命表示简单命题题l 用用“1”或或“1”表示真，用表示真，用“0”或或“0”表示假表示假 例如，令例如，令 p：是有理数，（是有理数，（p 的真值为的真值为0）q：2+5=7，（，（q 的真值
6、为的真值为1）复合命题符号化复合命题符号化：由常量和：由常量和联结词联结词组成的公式组成的公式 2命题分类命题分类10否定、合取、析取联结词否定、合取、析取联结词定义定义1.3 设设p,q为两个命题，复合命题为两个命题，复合命题“p或或q”称作称作p与与q的的析取式析取式，记作，记作pq，称作称作析取联结词析取联结词.规定规定pq为假当为假当且仅当且仅当p与与q同时为假同时为假.定义定义1.1 设设 p为命题，复合命题为命题，复合命题“非非p”(或或“p的否定的否定”)称称为为p的的否定式否定式，记作，记作 p，符号，符号 称作称作否定联结词否定联结词.规定规定 p 为真当且仅当为真当且仅当p
7、为假为假.定义定义1.2 设设p,q为两个命题，复合命题为两个命题，复合命题“p并且并且q”(或或“p与与 q”)称为称为p与与q的的合取式合取式，记作，记作pq，称作称作合取联结词合取联结词.规定规定pq为真当且仅当为真当且仅当p与与q同时为真同时为真.11例例2 将下列命题符号化将下列命题符号化.(1)吴颖既用功又聪明吴颖既用功又聪明.(2)吴颖不仅用功而且聪明吴颖不仅用功而且聪明.(3)吴颖虽然聪明，但不用功吴颖虽然聪明，但不用功.(4)张辉与王丽都是三好生张辉与王丽都是三好生.(5)张辉与张辉与王丽是同学王丽是同学.合取联结词的实例合取联结词的实例12解解 令令p:吴颖用功吴颖用功,q
8、:吴颖聪明吴颖聪明(1)p q(2)p q(3)p q(4)设设p:张辉是三好生张辉是三好生,q:王丽是三好生王丽是三好生 p q(5)p:张辉与张辉与王丽是同学王丽是同学(1)(3)说明描述合取式的灵活性与多样性说明描述合取式的灵活性与多样性(4)(5)要求分清要求分清“与与”所联结的成分所联结的成分合取联结词的实例合取联结词的实例13例例3 将下列命题符号化将下列命题符号化(1)2 或或 4 是素数是素数.(2)2 或或 3 是素数是素数.(3)4 或或 6 是素数是素数.(4)小元元只能拿一个苹果或一个梨小元元只能拿一个苹果或一个梨.(5)王小红生于王小红生于 1975 年或年或 197
9、6 年年.析取联结词的实例析取联结词的实例14解解 (1)令令p:2是素数是素数,q:4是素数是素数,p q(2)令令p:2是素数是素数,q:3是素数是素数,p q(3)令令p:4是素数是素数,q:6是素数是素数,p q(4)令令p:小元元拿一个苹果小元元拿一个苹果,q:小元元拿一个梨小元元拿一个梨 (pq)(p q)(5)p:王小红生于王小红生于 1975 年年,q:王小红生于王小红生于1976 年年,(pq)(p q)(1)(3)为为相容或相容或(4)(5)为为排斥或排斥或合取和析取如何记忆？合取和析取如何记忆？析取联结词的实例析取联结词的实例15定义定义1.4 设设p,q为两个命题，复合
10、命题为两个命题，复合命题“如果如果p,则则q”称作称作p与与q的的条件式条件式，记作，记作pq，并称，并称p是是条件条件式的式的前件前件，q为为条件条件式的式的后后件件，称作称作条件联结词条件联结词.规定：规定：pq为假当且仅当为假当且仅当p为真为真q为假为假.蕴涵联结词蕴涵联结词(1)pq 的逻辑关系：的逻辑关系：q为为 p 的必要条件的必要条件(2)“如果如果 p,则则 q”有很多不同的表述方法：有很多不同的表述方法：若若p，就，就q 只要只要p，就，就q p仅当仅当q 只有只有q 才才p 除非除非q,才才p 或或 除非除非q，否则非，否则非p，(3)当当 p 为假时，为假时，pq恒为真恒
11、为真(4)常出现的错误：不分充分与必要条件常出现的错误：不分充分与必要条件16例例4 设设 p：天冷，：天冷，q：小王穿羽绒服，将下列命题符号化：小王穿羽绒服，将下列命题符号化(1)只要天冷，小王就穿羽绒服只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服如果天不冷，则小王不穿羽绒服.(8)小
12、王穿羽绒服仅当天冷的时候小王穿羽绒服仅当天冷的时候.蕴涵联结词的实例蕴涵联结词的实例pq注意：注意：pq 与与 qp、p q等值（真值相同）等值（真值相同）pqpqqpqppqqpqp17定义定义1.5 设设 p,q为两个命题，复合命题为两个命题，复合命题“p当且仅当当且仅当q”称作称作p与与q的的等价式等价式，记作，记作pq，称作称作等价（双条件）联结词等价（双条件）联结词.规规定定pq为真当且仅当为真当且仅当p与与q同时为真或同时为假同时为真或同时为假.pq 的逻辑关系：的逻辑关系：p与与q互为充分必要条件互为充分必要条件等价联结词等价联结词例例5 5 求下列复合命题的真值求下列复合命题的
13、真值(1)2+2 4 当且仅当当且仅当 3+3 6.(2)2+2 4 当且仅当当且仅当 3 是偶数是偶数.(3)2+2 4 当且仅当当且仅当 太阳从东方升起太阳从东方升起.(4)2+2 4 当且仅当当且仅当 美国位于非洲美国位于非洲.(5)函数函数 0(x)在在 x0 可导的充要条件是可导的充要条件是 它在它在 x0 连续连续.1001018自学内容自学内容课本课本P8P9：l 四种次重要联结词四种次重要联结词19l 本小节中本小节中p,q,r,均表示命题均表示命题.l 联结词集为联结词集为,，p,p q,p q,pq,pq为为基本复合命题基本复合命题.其中要特别注意理解其中要特别注意理解pq
14、的涵义的涵义.反复使用反复使用,中的联结词组成更为复杂的复合命题中的联结词组成更为复杂的复合命题.l 复合命题的各个原子命题之间可以无任何实际联系。复合命题的各个原子命题之间可以无任何实际联系。设设 p:是无理数，是无理数，q:3是奇数，是奇数，r:苹果是方的，苹果是方的，s:太阳绕地球转太阳绕地球转 则复合命题则复合命题(pq)(rs)p)是假命题是假命题.2小结小结l 联结词的运算顺序：联结词的运算顺序：,同级按先出现者先运算同级按先出现者先运算.l 联结词的对称性。联结词的对称性。201.2 命题公式及其赋值命题公式及其赋值命题变项与合式公式命题变项与合式公式l 命题变项命题变项l 合式
15、公式合式公式l 合式公式的层次合式公式的层次公式的赋值公式的赋值l 公式赋值公式赋值l 公式类型公式类型l 真值表真值表21命题变项与合式公式命题变项与合式公式 命题常项、命题变项（命题变元）：类比常量和变量。命题常项、命题变项（命题变元）：类比常量和变量。常项与变项均用常项与变项均用 p,q,r,pi,qi,ri,等表示等表示.定义定义1.6 合式公式合式公式（简称公式）的递归定义：（简称公式）的递归定义：(1)单个命题变项和命题常项是合式公式单个命题变项和命题常项是合式公式,称作称作原子命题公式原子命题公式 (2)若若A是合式公式，则是合式公式，则(A)也是也是 (3)若若A,B是合式公式
16、，则是合式公式，则(A B),(A B),(AB),(AB)也是也是 (4)只有只有有限次有限次地应用地应用(1)(3)形成的符号串才是合式公式形成的符号串才是合式公式几点说明：几点说明：1、命题公式可以是没有真假值的；、命题公式可以是没有真假值的；2、并不是由命题常（变）元、联结词和一些括号组成的字符、并不是由命题常（变）元、联结词和一些括号组成的字符串都能成为命题公式串都能成为命题公式；3、递归定义：由、递归定义：由基础基础、归纳归纳和和界限界限组成。组成。22合式公式的层次合式公式的层次定义定义1.7(1)若公式若公式A是单个命题变项，则称是单个命题变项，则称A为为0层公式层公式.(2)
17、称称 A 是是 n+1(n0)层公式是指下面情况之一：层公式是指下面情况之一：(a)A=B,B 是是 n 层公式；层公式；(b)A=B C,其中其中B,C 分别为分别为 i 层和层和 j 层公式，层公式，且且 n=max(i,j)；(c)A=B C,其中其中 B,C 的层次及的层次及 n 同同(b)；(d)A=BC,其中其中B,C 的层次及的层次及 n 同同(b)；(e)A=BC,其中其中B,C 的层次及的层次及 n 同同(b).(3)若公式若公式A的层次为的层次为k,则称则称A为为k层公式层公式.例如例如 公式公式 A=p,B=p,C=pq,D=(pq)r,E=(p q)r)(r s)分别为
18、分别为0层，层，1层，层，2层，层，3层，层，4层公式层公式.23第二讲第二讲 命题逻辑的等值演算命题逻辑的等值演算上一讲主要内容回顾：上一讲主要内容回顾：简单命题和复合命题、简单命题和复合命题、5个重要联结词；个重要联结词；命题常项和命题变项；命题常项和命题变项；公式的递归定义、公式的层次；公式的递归定义、公式的层次；第二讲主要内容第二讲主要内容1-4 真值表与等价公式真值表与等价公式1-5 重言式与蕴含式重言式与蕴含式24定义定义1.8 设设p1,p2,pn是出现在公式是出现在公式A中的全部中的全部命题变项命题变项,给给p1,p2,pn各指定一个真值各指定一个真值,称为对称为对A的一个的一
19、个赋值赋值或或解释解释.若使若使A为为1,则称这组值为则称这组值为A的的成真赋值成真赋值;若使若使A为为0,则称这组则称这组值为值为A的的成假赋值成假赋值.例：如例：如 000,010,101,110是是(pq)r的成真赋值的成真赋值 001,011,100,111是成假赋值是成假赋值.说明：说明：l A中仅出现中仅出现 p1,p2,pn，给，给A赋值赋值=1 2 n是指是指 p1=1,p2=2,pn=n,i=0或或1,i之间不加标点符号之间不加标点符号l A中仅出现中仅出现 p,q,r,给给A赋值赋值 1 2 3是指是指 p=1,q=2,r=3 思考：含思考：含n个命题变项的公式有多少个赋值
20、？个命题变项的公式有多少个赋值？公式赋值公式赋值25定义定义1-4.1 将命题公式将命题公式A在所有在所有赋值赋值下取值的情况列成表下取值的情况列成表,称称作作A的的真值表真值表.构造真值表的步骤构造真值表的步骤:(1)找出公式中所含的全部命题变项找出公式中所含的全部命题变项p1,p2,pn(若无下角标若无下角标 则按字母顺序排列则按字母顺序排列),列出列出2n个全部赋值个全部赋值,从从000开始开始,按按 二进制加法二进制加法,每次加每次加1,直至直至111为止为止.(2)按从低到高的顺序写出公式的各个按从低到高的顺序写出公式的各个层次层次.(3)对每个赋值依次计算各层次的真值对每个赋值依次
21、计算各层次的真值,直到直到最后计算出公式最后计算出公式 的真值为止的真值为止.真值表真值表26例例6 写出下列公式的真值表写出下列公式的真值表,并求它们的成真赋值和成假并求它们的成真赋值和成假 赋值赋值:(1)(p q)r (2)(qp)qp (3)(p q)q真值表真值表27(1)A=(p q)r成真赋值成真赋值:000,001,010,100,110;成假赋值成假赋值:011,101,111 p q rp q r(p q)r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 00111111 10101010 11101010 真值表真值表128(2)B(qp
22、)qp成真赋成真赋值值:00,01,10,11;无成假赋值无成假赋值p q qp(qp)q(qp)qp0 00 11 01 1101100011111真值表真值表229(3)C (p q)q的真值表的真值表成假赋值成假赋值:00,01,10,11;无成真赋值无成真赋值p q p p q (p q)(p q)q0 00 11 01 11100110100100000真值表真值表330问题思考问题思考1、回顾：含、回顾：含n个命题变元的公式共有多少个不同的个命题变元的公式共有多少个不同的赋值？赋值？2、含、含n个命题变元的个命题变元的真值表真值表共有多少种不同的真值共有多少种不同的真值情况？情况？
23、3、真值表与公式之间的关系？、真值表与公式之间的关系？31公式的类型公式的类型定义定义1.10 (1)若若A在它的任何赋值下均为真在它的任何赋值下均为真,则称则称A为为重言式重言式或或永永真式真式;(2)若若A在它的任何赋值下均为假在它的任何赋值下均为假,则称则称A为为矛盾式矛盾式或或永永假式假式;(3)若若A不是矛盾式不是矛盾式,则称则称A是是可满足式可满足式.由例由例1可知可知,(p q)r,(qp)qp,(p q)q 分别为非重言式的可满足式分别为非重言式的可满足式,重言式重言式,矛盾式矛盾式.思考：思考：重言式与可满足式、矛盾式之间的关系？重言式与可满足式、矛盾式之间的关系？32真值表
24、的用途真值表的用途 真值表可用于求出公式的真值表可用于求出公式的全部成真赋值与成假赋值全部成真赋值与成假赋值,判断公式的类型判断公式的类型注意：注意：1、如果两个公式的真值表对所有赋值最后一列都相、如果两个公式的真值表对所有赋值最后一列都相同，则称两个公式的同，则称两个公式的真值表相同真值表相同；2、真值表只考虑、真值表只考虑最后的结果最后的结果，而不考虑构造真值表，而不考虑构造真值表的中间过程。的中间过程。33等价公式概念等价公式概念两种定义：两种定义：1、给定两个命题公式、给定两个命题公式A和和B，设，设P1，P2，Pn为所为所有出现于有出现于A和和B中的原子变元，若给中的原子变元，若给P
25、1，P2，Pn任一组真值指派，任一组真值指派，A和和B的真值都相同，则称的真值都相同，则称A和和B是是等价公式等价公式或逻辑相等，记作或逻辑相等，记作AB。2、若等价式若等价式AB是重言式，则称是重言式，则称A与与B等值等值，记作，记作AB，并称，并称AB是是等值式，等值式，A和和B是是等价公式。等价公式。说明：说明：1、与与的区别；的区别；2、A或或B中可能有中可能有哑元哑元出现出现.例例 (pq)(p q)(r r)r为左边公式的哑元为左边公式的哑元.34等值式例题等值式例题例例1 判断下列各组公式是否等值判断下列各组公式是否等值:(1)p(qr)与与(p q)r 11111101 111
26、11101 11011101 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1(p q)rp(qr)qr p q rp q00000011 结论结论:p(qr)(p q)r 35等值式例题等值式例题(2)p(qr)与与(pq)r 01011101 11111101 11011101 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1(pq)rp(qr)qr p q rpq11110011 结论结论:p(qr)与与(pq)r 不等值不等值36基本等价公式基本等价公式(1/2)双重否定律双重否定律 AA幂等律幂等律 A AA,A AA交
27、换律交换律 A BB A,A BB A结合律结合律 (A B)CA(B C),(A B)CA(B C)分配律分配律 A(B C)(A B)(A C),A(B C)(A B)(A C)德摩根律德摩根律 (A B)AB (A B)AB吸收律吸收律 A(A B)A,A(A B)A37基本等价公式基本等价公式(2/2)零律零律 A 11,A 00同一律同一律 A 0A.A 1A排中律排中律 AA1矛盾律矛盾律 AA0蕴涵等值式蕴涵等值式 ABA B等价等值式等价等值式 AB(AB)(BA)假言易位假言易位 ABBA等价否定等值式等价否定等值式 ABAB归谬论归谬论 (AB)(AB)A特别提示：必须牢记
28、这特别提示：必须牢记这16组等值式，这是继续学习的基础组等值式，这是继续学习的基础38等价演算等价演算1.等值演算等值演算由已知的等值式推演出新的等值式由已知的等值式推演出新的等值式的过程的过程2.等值演算的基础：等值演算的基础：(1)等值关系的性质：自反性、对称性、传递性等值关系的性质：自反性、对称性、传递性 (2)基本的等值式基本的等值式 (3)置换规则（关于如何应用置换规则（关于如何应用16组基本等价公式）组基本等价公式）39置换规则置换规则定义定义1-4.3 如果如果A是合式公式是合式公式(A)的一部分，且的一部分，且A本本身也是一个合式公式，则称身也是一个合式公式，则称A为合式公式为
29、合式公式(A)的的子公式子公式。定理定理1-4.1（置换规则置换规则P17定理定理1.3.3）设）设 (A)是含公是含公式式 A 的命题公式（的命题公式（A为为(A)的子公式），的子公式），(B)是是用公式用公式 B 置换置换 (A)中所有的中所有的 A 后得到的命题公后得到的命题公式式；若；若 BA，则，则 (B)(A)。40等值演算的应用举例等值演算的应用举例(1/2)(1/2)证明两个公式等值证明两个公式等值例例2 证明证明 p(qr)(p q)r证证 p(qr)p(q r)（蕴涵等值式，置换规则）（蕴涵等值式，置换规则）(pq)r （结合律，置换规则）（结合律，置换规则）(p q)r
30、（德摩根律，置换规则）（德摩根律，置换规则）(p q)r （蕴涵等值式，置换规则）（蕴涵等值式，置换规则）注：可在注明中省去置换规则注：可在注明中省去置换规则思考：可否用等值演算直接证明两个公式不等值？思考：可否用等值演算直接证明两个公式不等值？41证明两个公式不等值证明两个公式不等值例例3 证明证明 p(qr)与与(pq)r 不等值不等值证证 方法一方法一 真值表法真值表法方法二方法二 观察法观察法.观察到观察到000,010是左边的成真赋值，是右是左边的成真赋值，是右边的成假赋值边的成假赋值 方法三方法三 先用等值演算化简公式，然后再观察先用等值演算化简公式，然后再观察 p(qr)pq r
31、 (pq)r(p q)r(pq)r 更容易看出前面的两个赋值分别是更容易看出前面的两个赋值分别是左边的成真赋左边的成真赋 值和右边的成假赋值值和右边的成假赋值等值演算的应用举例等值演算的应用举例(2/2)(2/2)42作业作业l 复习本次课的内容复习本次课的内容l 作业本：作业本：1.P45的的4,5；2.P45的的7；3.P46:8的的(4)(6)。l 预习下次课内容预习下次课内容:蕴含式蕴含式43第三讲第三讲 蕴含式蕴含式上一讲主要内容回顾：上一讲主要内容回顾：赋值（解释）、成真赋值、成假赋值；赋值（解释）、成真赋值、成假赋值；真值表、重言式、矛盾式、可满足式；真值表、重言式、矛盾式、可满
32、足式；等价公式（两种定义）、等价公式（两种定义）、16组基本等价关系；组基本等价关系；子公式、置换规则。子公式、置换规则。第三讲主要内容第三讲主要内容1-5 蕴含式蕴含式44判断公式类型判断公式类型:A为矛盾式当且仅当为矛盾式当且仅当A 0 A为重言式当且仅当为重言式当且仅当A 1例例4 用等值演算法判断下列公式的类型用等值演算法判断下列公式的类型 (1)q(pq)(2)(pq)(qp)(3)(p q)(pq)r)等值演算判断公式类型等值演算判断公式类型(1/2)解解 (1)q(pq)q(p q)（蕴涵等值式）（蕴涵等值式）q(pq)（德摩根律）（德摩根律）p(qq)（交换律，结合律）（交换律
33、，结合律）p 0 （矛盾律）（矛盾律）0 （零律）（零律）矛盾式矛盾式45判断公式类型判断公式类型(2/2)(2)(pq)(qp)(p q)(qp)（蕴涵等值式）（蕴涵等值式）(p q)(p q)（交换律）（交换律）1重言式重言式(3)(p q)(pq)r)(p(qq)r （分配律）（分配律）p 1 r （排中律）（排中律）p r （同一律）（同一律）可满足式，存在可满足式，存在哑元哑元，101和和111是成真赋值，其它都是成假是成真赋值，其它都是成假赋值赋值.46重言式的性质重言式的性质定理定理 1-5.11-5.1 任何任何两个重言式两个重言式的的合取合取或或析取析取，仍然是，仍然是一个一
34、个重言式重言式。定理定理1-5.21-5.2 一个一个重言式重言式，对，对同一分量（命题变量）同一分量（命题变量）都都用用任何的同一个合式公式置换任何的同一个合式公式置换，其结果仍为一，其结果仍为一重言式。（重言式。（代入规则，注意与置换规则的比较代入规则，注意与置换规则的比较）思考：思考：1、举出与定理对应的例子。、举出与定理对应的例子。2、矛盾式的情况？、矛盾式的情况？3、可满足式的情况？、可满足式的情况？47蕴含式蕴含式定义定义a 设设P，Q是两个公式。是两个公式。称称Q是是P的逻辑结果的逻辑结果(或称或称P蕴涵蕴涵Q)，当且仅当，当且仅当对对P，Q的任意解释的任意解释I，如果，如果I满
35、足满足P，则则I也满足也满足Q，记作，记作PQ。定义定义b 当且仅当当且仅当PQ是一个重言式是一个重言式时，我们称时，我们称“P蕴含蕴含Q”，并记作，并记作PQ。注意：注意：1、PQ不是对称式不是对称式 2、和和的区别的区别 逆换式：逆换式：Q P，反换式：反换式：P Q，逆反式：逆反式：Q P 由真值表可见：由真值表可见：P Q Q P Q P P Q 即：条件命题公式与其逆反式是等价的。即：条件命题公式与其逆反式是等价的。48蕴含式的证明方法蕴含式的证明方法根据真值表：要证根据真值表：要证P Q，只需证对于，只需证对于任意的任意的P的成真赋的成真赋值值I，I也是也是Q的成真赋值。的成真赋值
36、。根据蕴含式定义：要证根据蕴含式定义：要证P Q，只需证，只需证P Q是重言式是重言式。对于对于PQ来说，只有来说，只有P的真值取的真值取1，Q的真值取的真值取0这样一种这样一种指派时，指派时，P Q的真值为的真值为0。（。（破坏该条件破坏该条件）证明证明P Q是重言式是重言式方法：方法：证法一：假设前件证法一：假设前件P为为1时，导出后件时，导出后件Q为为1(前真看后前真看后真真)。证法二：假设后件证法二：假设后件Q为为0时，前件时，前件P为为0(后假看前假后假看前假)。49练习：练习：推证推证Q(PQ）P 证法证法2(后假看前假后假看前假)假定P为F，则P为T。(a）：若Q为F，则PQ为F
37、，Q(PQ）为F。(b）：若Q为T，则Q为F，Q(PQ）为F。所以Q(PQ)P成立。证法证法1(前真看后真前真看后真)假定Q(PQ）为T，则Q为T，且(PQ）为T。由Q为F，则必须P为F，故P为T。50多前提蕴含多前提蕴含l 设设G1,Gn，H是公式，是公式，称称H是是G1,Gn的逻辑结果的逻辑结果(或称或称G1,Gn共同蕴涵共同蕴涵H)，当且仅当公式，当且仅当公式G1 Gn蕴涵蕴涵H；G1,Gn共同蕴涵共同蕴涵H记为：记为：G1,Gn H。l 显然，公式显然，公式H是是G1,Gn的逻辑结果的充要条件是：公的逻辑结果的充要条件是：公式式(G1 Gn)H)是恒真的。是恒真的。l 例如，例如，P，
38、PQ共同蕴涵共同蕴涵Q。l 定理定理：如果：如果H1，Hm，P共同蕴涵公式共同蕴涵公式Q，则，则H1，Hm共同蕴涵公式共同蕴涵公式PQ。l 例如，因为公式例如，因为公式PQ，QR，P共同蕴涵共同蕴涵R，所以，所以PQ，QR共同蕴涵共同蕴涵PR。51证明：证明：(1)因为因为(H1 Hm P)Q，所以公式，所以公式(H1 Hm P)Q是恒真的。是恒真的。(2)利用下面的基本等价公式：利用下面的基本等价公式：P1(P2P3)(P1 P2)P3(3)于是，于是，(H1 Hm P)Q=(H1 Hm)(PQ)。故故(H1 Hm)(PQ)是恒真的。是恒真的。(4)结论：结论：H1，Hm共同蕴涵共同蕴涵PQ
39、。定理证明定理证明52基本蕴含式基本蕴含式1.P QP2.P QQ3.PP Q4.QP Q5.P(PQ)6.Q(PQ)7.(PQ)P8.(PQ)Q9.P，QP Q10.P，P QQ11.P，PQQ12.Q，PQP13.PQ，QRPR14.P Q，PR，QRR 53蕴含式性质蕴含式性质1定理定理1-5.4 设设P、Q为任意两个命题公式，为任意两个命题公式，P Q的的充分必要条件是充分必要条件是P Q且且Q P。思考和总结：两个命题公式等价的证明方法有哪些？思考和总结：两个命题公式等价的证明方法有哪些？1、真值表法；、真值表法；2、对基本等价公式使用、对基本等价公式使用置换规则置换规则；3、从重言
40、式出发使用、从重言式出发使用代入规则代入规则；4、分别证明、分别证明P Q且且Q P；5、54蕴含式性质蕴含式性质2蕴含的常用性质：蕴含的常用性质：（1）设）设A、B、C为合式公式，若为合式公式，若A B且且A是是重言式，则重言式，则B必是重言式。必是重言式。（2）若）若A B，B C，则，则A C，即蕴含关，即蕴含关系是传递的。系是传递的。（3）若）若A B，且，且A C，那末，那末A (B C)。（4）若）若A B，C B，则，则(A C)B。55多前提蕴含的证明方法多前提蕴含的证明方法l 若给出前提集合若给出前提集合S=G1，Gk，公式，公式G，证明证明SG的方法如下：的方法如下：l 原
41、理：根据一些原理：根据一些基本等价式基本等价式和和基本蕴涵式基本蕴涵式，从，从S出出发，发，演绎演绎出出G，在演绎过程中遵循以下三条规则：，在演绎过程中遵循以下三条规则：1.规则规则1.可随便使用可随便使用前提前提(P规则规则)。2.规则规则2.可随便使用前面演绎出的某些公式的可随便使用前面演绎出的某些公式的逻辑结逻辑结果果(T规则规则)。3.3.规则规则3.如果需要演绎出的公式是如果需要演绎出的公式是PQ的形式，则的形式，则我们可将我们可将P做为做为附加前提附加前提使用，而力图去演绎出使用，而力图去演绎出Q。(CP规则规则)56多前提蕴含的证明例子多前提蕴含的证明例子例：证明例：证明P(QS
42、)，R P，QRS1.R P 规则规则12.R 规则规则33.P 规则规则2，由，由1,2根据根据104.P(QS)规则规则15.QS 规则规则2，由，由3,4根据根据116.Q 规则规则17.S 规则规则2，由，由5,6根据根据118.RS 规则规则3，根据，根据2,757回顾回顾1-6 其他联结词其他联结词回顾回顾4种次重要联结词：种次重要联结词：、c58真值函数真值函数定义定义 0,1上的上的n元函数元函数0:0,1n 0,1称称为为n元真值函数元真值函数.4个个一元真值函数确定了一元真值函数确定了4个个不等价的命题公式不等价的命题公式；真值函数确定了所需的联结词的个数；真值函数确定了所
43、需的联结词的个数；一元真值函数确定了只需要一元真值函数确定了只需要一个一个一元算子。一元算子。一元真值函数一元真值函数 p 0 0 0 1 1 1 0 1 0 1)1(3)1(2)1(1)1(0FFFF59二元真值函数二元真值函数PQ联结联结词词1联结联结词词2联结联结词词3联结联结词词4联结联结词词5联结联结词词6联结联结词词7联结联结词词8联结联结词词9联结联结词词10联结联结词词11联结联结词词12联结联结词词13联结联结词词14联结联结词词15联结联结词词161110110010101010101010100101100101100110011001101001010010001101
44、0110101010PQPPQQPPQ QPPQ QPQPQQP10PQPPQQPPQ QPQPQPPQ QP QPQP QPQP QQPQPc c 由表可见只需要由表可见只需要九个联结词九个联结词。60二元真值函数二元真值函数p q0 00 11 01 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1p q0 00 11 01 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1)2(7)2(6)2(5)2(4)2(3)2(2)2(1
45、)2(0FFFFFFFF)2(15)2(14)2(13)2(12)2(11)2(10)2(9)2(8FFFFFFFF2元真值函数按序排列元真值函数按序排列61公式与真值函数公式与真值函数)2(13F任何一个含任何一个含n个命题变项的命题公式个命题变项的命题公式A都对应惟一的一个都对应惟一的一个n元元真值函数真值函数 F,F 恰好为恰好为A的真值表的真值表.等值的公式对应的真值函数相同等值的公式对应的真值函数相同.例如：例如：pq,p q 都对应都对应62联结词完备集联结词完备集定义定义 设设S是一个联结词集合，如果任何是一个联结词集合，如果任何n(n 1)元真元真值函数都可以由仅含值函数都可以
46、由仅含S中的联结词构成的公式表中的联结词构成的公式表示，则称示，则称S是是联结词完备集联结词完备集.若若S是联结词完备集是联结词完备集,则任何命题公式都可由则任何命题公式都可由S中的联中的联结词表示结词表示.63极小联结词完备集极小联结词完备集1.由由(P Q)(P Q)(Q P)，故可把包含，故可把包含的公式等价变换为包含的公式等价变换为包含 和和的公式。的公式。2.由由P Q P Q，说明包含，说明包含“”的公式可的公式可以变换为包含以变换为包含“”和和“”的公式。的公式。3.由由P Q (P Q)，P Q (P Q)。4.故由故由“”这五个联结词组成的命题这五个联结词组成的命题公式，必可
47、由公式，必可由，或或，组成的命题公式组成的命题公式等价置换。等价置换。n一个联结词完备集中，若不包含一个联结词完备集中，若不包含冗余冗余的联结词，的联结词，则称该集合为一个则称该集合为一个极小极小联结词完备集。联结词完备集。64其他联结词其他联结词对于其他联结词，有下列性质：对于其他联结词，有下列性质：P Q (P Q)P Q (P Q)P Q (P Q)P Q (P Q)结论：S=,是联结词完备集c65联结词完备集联结词完备集思考思考 判断判断以下是否是联结词完备集？以下是否是联结词完备集？(1)S1=,(2)S2=,(3)S3=,(4)S4=,(5)S5=,证明证明(1),(2)在联结词完
48、备集中加入新的联结词后仍为完备集在联结词完备集中加入新的联结词后仍为完备集(3)A B (AB)(4)A B (AB)(5)ABA B,不是联结词完备集不是联结词完备集,0不能用它表示不能用它表示它的子集它的子集,等都不是等都不是66极小完备集极小完备集定理定理2.7 与与 为联结词完备集为联结词完备集.证明证明 ,为完备集为完备集 p pp (p p)p p p q (pq)pq (p p)(q q)p q (p q)(p q)(p q)(p q)得证得证 为联结词完备集为联结词完备集.对对 类似可证类似可证结论：结论：1.任意命题公式都可由仅包含任意命题公式都可由仅包含，或或，的命的命题公
49、式等价代换。题公式等价代换。2.，或或，为极小完备集。为极小完备集。3.极小完备集亦可为极小完备集亦可为 或或。67第一章 数理逻辑1-7 对偶与范式671-7 对偶对偶l 命题公式中仅含有命题公式中仅含有、中的联结词中的联结词 l 观察教材观察教材p16，表，表1-22等价公式联结词符号的特征，等价公式联结词符号的特征，找出规律。找出规律。l 如：分配律如：分配律 P(QR)(PQ)(PR)P(QR)(PQ)(PR)68对偶式对偶式l 定义：定义：1-7.1 在给定的命题公式中（仅含有在给定的命题公式中（仅含有、三种联结词），将联结词三种联结词），将联结词 换成换成，将，将 换换成成，若有特
50、殊变元，若有特殊变元0和和1亦互相取代，所得公式亦互相取代，所得公式A*称为称为A的对偶公式。的对偶公式。l 显然，显然，A也是也是A*的对偶式。的对偶式。l 求对偶式的方法：求对偶式的方法：1.先化为仅含有先化为仅含有、三种联结词的公式；三种联结词的公式；2.按定义依次完全替换。按定义依次完全替换。69第一章 数理逻辑1-7 对偶与范式69对偶举例对偶举例例题例题:写出下列表达式的对偶式写出下列表达式的对偶式(PQ)(P (Q S)(P Q)R(P Q)1 P Q P Q P Q Q R(P Q)(P Q)70第一章 数理逻辑1-7 对偶与范式70对偶德摩根律的普遍形式对偶德摩根律的普遍形式
