《《离散数学》课件第一章.ppt》由会员分享，可在线阅读，更多相关《《离散数学》课件第一章.ppt（32页珍藏版）》请在三一文库上搜索。
1、1主要内容主要内容l 命题逻辑基本概念命题逻辑基本概念l 命题逻辑等值演算命题逻辑等值演算l 命题逻辑推理理论命题逻辑推理理论l 一阶逻辑基本概念一阶逻辑基本概念l 一阶逻辑等值演算与推理一阶逻辑等值演算与推理第一部分第一部分 数理逻辑数理逻辑2第一章第一章 命题逻辑的基本概念命题逻辑的基本概念主要内容主要内容l 命题与联结词命题与联结词 命题及其分类命题及其分类 联结词与复合命题联结词与复合命题l 命题公式及其赋值命题公式及其赋值3命题与真值命题与真值 命题：判断结果惟一的陈述句命题：判断结果惟一的陈述句 命题的真值：判断的结果命题的真值：判断的结果 真值的取值：真与假真值的取值：真与假 真
2、命题与假命题真命题与假命题注意：注意：感叹句、祈使句、疑问句都不是命题感叹句、祈使句、疑问句都不是命题陈述句中的悖论，判断结果不惟一确定的不是命题陈述句中的悖论，判断结果不惟一确定的不是命题 1.1 命题与联结词命题与联结词4例例1 1 下列句子中那些是命题？下列句子中那些是命题？(1)是有理数是有理数.(2)2+5=7.(3)x+5 3.(4)你去教室吗？你去教室吗？(5)这个苹果真大呀！这个苹果真大呀！(6)请不要讲话！请不要讲话！(7)2050年元旦下大雪年元旦下大雪.2 假命题假命题命题概念命题概念 真命题真命题不是命题不是命题 不是命题不是命题 不是命题不是命题不是命题不是命题命题，
3、但真值现在不知道命题，但真值现在不知道5命题分类：简单命题（也称原子命题）与复合命题命题分类：简单命题（也称原子命题）与复合命题简单命题符号化简单命题符号化l 用小写英文字母用小写英文字母 p,q,r,pi,qi,ri(i 1)表示简单命题表示简单命题l 用用“1”表示真，用表示真，用“0”表示假表示假 例如，令例如，令 p：是有理数，则是有理数，则 p 的真值为的真值为0，q：2+5=7，则，则 q 的真值为的真值为1 2命题分类命题分类6否定、合取、析取联结词否定、合取、析取联结词定义定义1.3 设设p,q为两个命题，复合命题为两个命题，复合命题“p或或q”称作称作p与与q的的析取式析取式
4、，记作，记作pq，称作称作析取联结词析取联结词.规定规定pq为假当为假当且仅当且仅当p与与q同时为假同时为假.定义定义1.1 设设 p为命题，复合命题为命题，复合命题“非非p”(或或“p的否定的否定”)称称为为p的的否定式否定式，记作，记作 p，符号，符号 称作称作否定联结词否定联结词.规定规定 p 为真当且仅当为真当且仅当p为假为假.定义定义1.2 设设p,q为两个命题，复合命题为两个命题，复合命题“p并且并且q”(或或“p与与 q”)称为称为p与与q的的合取式合取式，记作，记作pq，称作称作合取联结词合取联结词.规定规定pq为真当且仅当为真当且仅当p与与q同时为真同时为真.7例例2 将下列
5、命题符号化将下列命题符号化.(1)吴颖既用功又聪明吴颖既用功又聪明.(2)吴颖不仅用功而且聪明吴颖不仅用功而且聪明.(3)吴颖虽然聪明，但不用功吴颖虽然聪明，但不用功.(4)张辉与王丽都是三好生张辉与王丽都是三好生.(5)张辉与张辉与王丽是同学王丽是同学.合取联结词的实例合取联结词的实例8解解 令令p:吴颖用功吴颖用功,q:吴颖聪明吴颖聪明(1)p q(2)p q(3)p q(4)设设p:张辉是三好生张辉是三好生,q:王丽是三好生王丽是三好生 p q(5)p:张辉与张辉与王丽是同学王丽是同学(1)(3)说明描述合取式的灵活性与多样性说明描述合取式的灵活性与多样性(4)(5)要求分清要求分清“与
6、与”所联结的成分所联结的成分合取联结词的实例合取联结词的实例9例例3 将下列命题符号化将下列命题符号化(1)2 或或 4 是素数是素数.(2)2 或或 3 是素数是素数.(3)4 或或 6 是素数是素数.(4)小元元只能拿一个苹果或一个梨小元元只能拿一个苹果或一个梨.(5)王小红生于王小红生于 1975 年或年或 1976 年年.析取联结词的实例析取联结词的实例10解解 (1)令令p:2是素数是素数,q:4是素数是素数,p q(2)令令p:2是素数是素数,q:3是素数是素数,p q(3)令令p:4是素数是素数,q:6是素数是素数,p q(4)令令p:小元元拿一个苹果小元元拿一个苹果,q:小元元
7、拿一个梨小元元拿一个梨 (pq)(p q)(5)p:王小红生于王小红生于 1975 年年,q:王小红生于王小红生于1976 年年,(pq)(p q)或或 p q(1)(3)为相容或为相容或(4)(5)为排斥或为排斥或,符号化时符号化时(5)可有两种形式，而可有两种形式，而(4)则不能则不能析取联结词的实例析取联结词的实例11定义定义1.4 设设p,q为两个命题，复合命题为两个命题，复合命题“如果如果p,则则q”称作称作p与与q的的蕴涵式蕴涵式，记作，记作pq，并称，并称p是蕴涵式的是蕴涵式的前件前件，q为蕴涵式的为蕴涵式的后后件件，称作称作蕴涵联结词蕴涵联结词.规定：规定：pq为假当且仅当为假
8、当且仅当p为真为真q为假为假.蕴涵联结词蕴涵联结词(1)pq 的逻辑关系：的逻辑关系：q为为 p 的必要条件的必要条件(2)“如果如果 p,则则 q”有很多不同的表述方法：有很多不同的表述方法：若若p，就，就q 只要只要p，就，就q p仅当仅当q 只有只有q 才才p 除非除非q,才才p 或或 除非除非q，否则非，否则非p，(3)当当 p 为假时，为假时，pq恒为真，称为空证明恒为真，称为空证明(4)常出现的错误：不分充分与必要条件常出现的错误：不分充分与必要条件12例例4 设设 p：天冷，：天冷，q：小王穿羽绒服，将下列命题符号化：小王穿羽绒服，将下列命题符号化(1)只要天冷，小王就穿羽绒服只
9、要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候小王穿羽绒服仅当天冷的时候.蕴涵联结词的实例蕴涵联结词的实例pq注意：注意：pq 与与 qp 等值（真值相同）等值（真值相同）pqpqqpqppqqpqp13定义定义1.5 设设 p,
10、q为两个命题，复合命题为两个命题，复合命题“p当且仅当当且仅当q”称作称作p与与q的的等价式等价式，记作，记作pq，称作称作等价联结词等价联结词.规定规定pq为真为真当且仅当当且仅当p与与q同时为真或同时为假同时为真或同时为假.pq 的逻辑关系：的逻辑关系：p与与q互为充分必要条件互为充分必要条件等价联结词等价联结词例例5 5 求下列复合命题的真值求下列复合命题的真值(1)2+2 4 当且仅当当且仅当 3+3 6.(2)2+2 4 当且仅当当且仅当 3 是偶数是偶数.(3)2+2 4 当且仅当当且仅当 太阳从东方升起太阳从东方升起.(4)2+2 4 当且仅当当且仅当 美国位于非洲美国位于非洲.
11、(5)函数函数 f(x)在在 x0 可导的充要条件是可导的充要条件是 它在它在 x0 连续连续.1001014l 本小节中本小节中p,q,r,均表示命题均表示命题.l 联结词集为联结词集为,，p,p q,p q,pq,pq为为基本复合命题基本复合命题.其中要特别注意理解其中要特别注意理解pq的涵义的涵义.反复使用反复使用,中的联结词组成更为复杂的复合命题中的联结词组成更为复杂的复合命题.设设 p:是无理数，是无理数，q:3是奇数，是奇数，r:苹果是方的，苹果是方的，s:太阳绕地球转太阳绕地球转 则复合命题则复合命题(pq)(rs)p)是假命题是假命题.2小结小结l 联结词的运算顺序：联结词的运
12、算顺序：,同级按先出现者先运算同级按先出现者先运算.151.2 命题公式及其赋值命题公式及其赋值命题变项与合式公式命题变项与合式公式l 命题变项命题变项l 合式公式合式公式l 合式公式的层次合式公式的层次公式的赋值公式的赋值l 公式赋值公式赋值l 公式类型公式类型l 真值表真值表16命题变项与合式公式命题变项与合式公式 命题常项命题常项 命题变项（命题变元）命题变项（命题变元）常项与变项均用常项与变项均用 p,q,r,pi,qi,ri,等表示等表示.定义定义1.6 合式公式合式公式（简称公式）的递归定义：（简称公式）的递归定义：(1)单个命题变项和命题常项是合式公式单个命题变项和命题常项是合式
13、公式,称作称作原子命题公式原子命题公式 (2)若若A是合式公式，则是合式公式，则(A)也是也是 (3)若若A,B是合式公式，则是合式公式，则(A B),(A B),(AB),(AB)也是也是 (4)只有有限次地应用只有有限次地应用(1)(3)形成的符号串才是合式公式形成的符号串才是合式公式几点说明：几点说明：归纳或递归定义归纳或递归定义,元语言与对象语言元语言与对象语言,外层括号可以省去外层括号可以省去17合式公式的层次合式公式的层次定义定义1.7(1)若公式若公式A是单个命题变项，则称是单个命题变项，则称A为为0层公式层公式.(2)称称 A 是是 n+1(n0)层公式是指下面情况之一：层公式
14、是指下面情况之一：(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)分别为分别为0层，层，1层，层，2层，层，3层，层，4层公式层公式
15、.18定义定义1.8 设设p1,p2,pn是出现在公式是出现在公式A中的全部命题变项中的全部命题变项,给给p1,p2,pn各指定一个真值各指定一个真值,称为对称为对A的一个的一个赋值赋值或或解释解释.若使若使A为为1,则称这组值为则称这组值为A的的成真赋值成真赋值;若使若使A为为0,则称这组则称这组值为值为A的的成假赋值成假赋值.几点说明：几点说明：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
16、=3 l 含含n个命题变项的公式有个命题变项的公式有2n个赋值个赋值.如如 000,010,101,110是是(pq)r的成真赋值的成真赋值 001,011,100,111是成假赋值是成假赋值.公式赋值公式赋值19定义定义1.9 将命题公式将命题公式A在所有赋值下取值的情况列成表在所有赋值下取值的情况列成表,称作称作A的的真值表真值表.构造真值表的步骤构造真值表的步骤:(1)找出公式中所含的全部命题变项找出公式中所含的全部命题变项p1,p2,pn(若无下角标若无下角标 则按字母顺序排列则按字母顺序排列),列出列出2n个全部赋值个全部赋值,从从000开始开始,按按 二进制加法二进制加法,每次加每
17、次加1,直至直至111为止为止.(2)按从低到高的顺序写出公式的各个层次按从低到高的顺序写出公式的各个层次.(3)对每个赋值依次计算各层次的真值对每个赋值依次计算各层次的真值,直到最后计算出公式直到最后计算出公式 的真值为止的真值为止.真值表真值表20例例6 写出下列公式的真值表写出下列公式的真值表,并求它们的成真赋值和成假并求它们的成真赋值和成假 赋值赋值:(1)(p q)r (2)(qp)qp (3)(p q)q真值表真值表21(1)A=(p q)r成真赋值成真赋值:000,001,010,100,110;成假赋值成假赋值:011,101,111 p q rp q r(p q)r0 0 0
18、0 0 10 1 00 1 11 0 01 0 11 1 01 1 1 00111111 10101010 11101010 真值表真值表122(2)B(qp)qp成真赋成真赋值值:00,01,10,11;无成假赋值无成假赋值p q qp(qp)q(qp)qp0 00 11 01 1101100011111真值表真值表223(3)C (p q)q的真值表的真值表成假赋值成假赋值:00,01,10,11;无成真赋值无成真赋值p q p p q (p q)(p q)q0 00 11 01 11100110100100000真值表真值表324公式的类型公式的类型定义定义1.10 (1)若若A在它的任
19、何赋值下均为真在它的任何赋值下均为真,则称则称A为为重言式重言式或或永真式永真式;(2)若若A在它的任何赋值下均为假在它的任何赋值下均为假,则称则称A为为矛盾式矛盾式或或永假式永假式;(3)若若A不是矛盾式不是矛盾式,则称则称A是是可满足式可满足式.由例由例1可知可知,(p q)r,(qp)qp,(p q)q 分别为非重言式的可满足式分别为非重言式的可满足式,重言式重言式,矛盾式矛盾式.注意：重言式是可满足式，但反之不真注意：重言式是可满足式，但反之不真.真值表的用途真值表的用途:求出公式的全部成真赋值与成假赋值求出公式的全部成真赋值与成假赋值,判断公式的类型判断公式的类型25第一章第一章 习
20、题课习题课主要内容主要内容l 命题、真值、简单命题与复合命题、命题符号化命题、真值、简单命题与复合命题、命题符号化l 联结词联结词,及复合命题符号化及复合命题符号化l 命题公式及层次命题公式及层次l 公式的类型公式的类型l 真值表及应用真值表及应用基本要求基本要求l 深刻理解各联结词的逻辑关系深刻理解各联结词的逻辑关系,熟练地将命题符号化熟练地将命题符号化l 会求复合命题的真值会求复合命题的真值l 深刻理解合式公式及重言式、矛盾式、可满足式等概念深刻理解合式公式及重言式、矛盾式、可满足式等概念l 熟练地求公式的真值表，并用它求公式的成真赋值与成假熟练地求公式的真值表，并用它求公式的成真赋值与成
21、假赋值及判断公式类型赋值及判断公式类型261.将下列命题符号化将下列命题符号化 (1)豆沙包是由面粉和红小豆做成的豆沙包是由面粉和红小豆做成的.(2)苹果树和梨树都是落叶乔木苹果树和梨树都是落叶乔木.(3)王小红或李大明是物理组成员王小红或李大明是物理组成员.(4)王小红或李大明中的一人是物理组成员王小红或李大明中的一人是物理组成员.(5)由于交通阻塞，他迟到了由于交通阻塞，他迟到了.(6)如果交通不阻塞，他就不会迟到如果交通不阻塞，他就不会迟到.(7)他没迟到，所以交通没阻塞他没迟到，所以交通没阻塞.(8)除非交通阻塞，否则他不会迟到除非交通阻塞，否则他不会迟到.(9)他迟到当且仅当交通阻塞
22、他迟到当且仅当交通阻塞.练习练习127提示：提示：分清复合命题与简单命题分清复合命题与简单命题分清相容或与排斥或分清相容或与排斥或分清必要与充分条件及充分必要条件分清必要与充分条件及充分必要条件答案答案:(1)是简单命题是简单命题 (2)是合取式是合取式 (3)是析取式（相容或）是析取式（相容或）(4)是析取式（排斥或）是析取式（排斥或）设设 p:交通阻塞，交通阻塞，q:他迟到他迟到 (5)pq,(6)pq或或qp (7)qp 或或pq,(8)qp或或 pq (9)pq 或或 pq可见可见(5)与与(7)，(6)与与(8)相同（等值）相同（等值）练习练习1解答解答282.设设 p:2是素数是素
23、数 q:北京比天津人口多北京比天津人口多 r:美国的首都是旧金山美国的首都是旧金山 求下面命题的真值求下面命题的真值 (1)(p q)r (2)(q r)(pr)(3)(qr)(pr)(4)(qp)(pr)(rq)0练习练习2100293.用真值表判断下面公式的类型用真值表判断下面公式的类型 (1)p r(qp)(2)(pq)(qp)r (3)(pq)(pr)练习练习330练习练习3解答解答(1)p r(qp)矛盾式矛盾式p q rqp (qp)p r(qp)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 11001111 00110000 00000000 31练习练习3解答解答(2)(pq)(qp)r 永真式永真式11111111 11110011 11110011 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1(pq)(qp)r qp pq p q r32练习练习3解答解答(3)(pq)(pr)非永真式的可满足式非永真式的可满足式p q rpq pr (pq)(pr)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 11110011 11110101 11111001