《离散数学1_1》由会员分享，可在线阅读，更多相关《离散数学1_1（77页珍藏版）》请在金锄头文库上搜索。
1、离散数学 主讲：路永刚 Email: 兰州大学信息科学与工程学院,发展历史,18世纪以前, 数学基本上是研究离散对象的数量和空间关系的科学。后来因天文学,物理学的发展,如行星轨道,牛顿三大力学定律等研究,极大地推动了连续数学(以微积分,数学物理方程, 复变函数论为代表)的发展。离散对象的研究则处于停滞状态。20世纪30年代, 图灵(Alan Turing) 提出计算机的 理论模型图灵机（Turing machine）。 这种模型早于实际制造计算机十多年，而现实的 计算机的计算能力, 本质上和图灵机的计算能力一样。由于在计算机内，机器字长总是有限的, 它代表离散的数或其它离散对象，因此随着计算
2、机科学和技术的迅猛发展，离散数学就显得更加重要。,离散数学,离散数学，是现代数学的一个重要分支，是整个计算机学科的专业基础课。离散数学是以研究离散量的结构和相互间的关系为主要目标。其研究对象一般地是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。离散数学是随着计算机科学的发展而逐步建立的，它形成于七十年代初期，是一门新兴的工具性学科。,离散数学,计算机求解的基本模式是： 实际问题 数学建模 算法设计 编程实现 离散数学可以为数学建模打下知识基础、为算法设计提供具体指导离散数学的作用就在于训练运用离散结构作为问题的抽象模型、构造算法、解决问题的能力。,图论,离散数学,集合论,数理逻辑
3、,代数结构,教材及主要参考书,主要教材： 离散数学西安电子科技大学出版社，方世昌主编，第三版。主要参考书： 1离散数学，高等教育出版社，李盘林、李丽双、李洋、王春立等编著； 2离散数学，清华大学出版社，耿素云、屈婉玲、张立昂等编著； 3离散数学，西安交通大学出版社，祝颂和、陆诗娣、陈建明、曾 明等编著； 4数理逻辑，北京大学出版社，王捍贫编著； 5集合论与图论，北京大学出版社，耿素云编著； 6代数结构与组合数学，北京大学出版社，屈婉玲编著。,成绩考核办法,本课程的考核分为平时成绩和期末考试成绩两大部分，其中平时成绩由日常考查成绩和作业成绩组成，期末考试以闭卷笔试为主。总成绩评定按百分制计算，平
4、时成绩占30，期末成绩占70。总成绩计算公式：总成绩平时成绩30期末成绩70,怎样学好本课程,该课程概念比较抽象、理论性比较强，所以需要上课前预习，课堂注意听讲，积极提问，课后要常复习，并认真完成作业。本课程的教学应将以各种基本概念、定理、定理证明、正反例、计算方法列为教学的重点，附带讲各种具体应用。,逻辑是研究推理的科学。 数理逻辑就是用数学方法（符号体系）研究推理的科学。主要内容： 命题逻辑基本概念 命题逻辑等值演算 命题逻辑推理理论 谓词逻辑基本概念 谓词逻辑等值演算与推理,第一章 数理逻辑,1.1 命 题,什么是命题？一个陈述语句叫做断言。 定义：一个命题是一个或真或假而不能两者都是的
5、断言。如果命题是真, 我们说它的真值为真如果命题是假, 我们说它的真值是假。,例：下列句子中那些是命题？(1) 是有理数.(2) 2 + 5 = 7.(3) x + 5 3.(4) 你去教室吗？(5) 这个苹果真大呀！(6) 请不要讲话！(7) 2050年元旦下大雪.,假命题,命题,真命题,不是命题,不是命题,不是命题,不是命题,命题，但真值现在不知道,例 1： 下述都是命题: (a) 今天下雪; (b) 3+3=6; (c) 2 是偶数而 3 是奇数; (d) 陈涉起义那天, 杭州下雨; (e) 较大的偶数都可表为两个质数之和。,例 2： 下述都不是命题: (a) x+y4。 (b) x=3
6、。 (c) 真好啊! (d) 你去哪里?,讨论 ： 一个人说:“我正在说谎”。这是不是命题？他是在说谎还是在说真话呢? 如果他讲真话, 那么他所说的是真, 也就是他在说谎。 另一方面, 如果他是说谎, 那么他说的是假， 所以他实际上是在说真话。从以上分析, 我们得出他必须既不是说谎也不是讲真话。这就是说断言“我正在说谎”事实上不能指定它的真假, 所以不是命题！ 这种断言叫悖论。,命题的真值,如果命题是真, 我们说它的真值为真 用1或者T表示 如果命题是假, 我们说它的真值是假 用0或者F表示,小结 命题与真值命题：判断结果唯一的陈述句命题的真值：判断的结果真值的取值：真与假真命题与假命题 注意
7、： 感叹句、祈使句、疑问句都不是命题 陈述句中的悖论，判断结果不惟一确定的不是命题,1.1 命题,若一个命题已不能分解成更简单的命题, 则这个命题叫原子命题或本原命题。 例 1 中(a) , (b) , (d) , (e)都是原子命题, 但“(c) 2 是偶数而 3 是奇数”不是, 因为它可写成“2 是偶数”和“3 是奇数”两个命题。命题和原子命题常用大写字母 P , Q , R :表示。 如用P表示“4 是质数”, 则记为 ：“ P: 4 是质数。”,原子命题,命题分类：原子命题与复合命题原子命题表示符号： 常用大写字母 P , Q , R 等表示复合命题：是指由原子命题组成的命题表示：常由
8、联结词和大写字母（原子命题）组成下面我们介绍联结词,命题分类,否定、合取、析取联结词,定义1.3: 设P, Q为两个命题，复合命题“P或Q”称作P与Q的析取式，记作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同时为真.,例： 将下列命题符号化 (1) 2 或 4 是素数. (2) 小元元只能拿一个
9、苹果或一个梨. (3) 王小红生于 1975 年或 1976 年.,析取联结词的实例,解 ： (1) 令P:2是素数, Q:4是素数, PQ (2) 令P:小元元拿一个苹果, Q:小元元拿一个梨(PQ)(PQ) (3) P:王小红生于 1975 年, Q:王小红生于1976 年, (PQ)(PQ) 或 PQ,例： 将下列命题符号化.(1) 吴颖既用功又聪明.(2) 吴颖虽然聪明，但不用功.(3) 张辉与王丽都是三好生.(4) 张辉与王丽是同学.,合取联结词的实例,解： 令P:吴颖用功, Q:吴颖聪明(1) PQ(2) PQ(3) 设 P:张辉是三好生, Q:王丽是三好生，PQ(4) P: 张辉
10、与王丽是同学,定义1.4: 设P, Q为两个命题，复合命题“如果P, 则Q”称作P与Q的蕴涵式，记作PQ，并称P是蕴涵式的前件，Q为蕴涵式的后件，称作蕴涵联结词. 规定：PQ为假当且仅当P为真Q为假.,蕴涵联结词,(1) PQ 的逻辑关系：Q为 P 的必要条件(2) 当 P 为假时，PQ恒为真，称为空证明(3) 常出现的错误：不分充分与必要条件,例 7 ： (a) P: 天不下雨, Q: 草木枯黄。 PQ: 如果天不下雨, 那么草木枯黄。 (b) R: G是正方形, S: G的四边相等。 RS: 如果G是正方形, 那么G的四边相等。 (c) W: 桔子是紫色的, V: 大地是不平的。 WV:
11、如果桔子是紫色的, 那么大地是不平的。,在日常生活中用蕴含式来断言前提和结论之间的因果或实质关系, 如上例(a)和(b), 这样的蕴含式叫形式蕴含；然而, 在命题演算中, 一个蕴含式的前提和结论并不需要有因果和实质联系, 这样的蕴含式叫实质蕴含。如上例(c)中, 桔子的颜色和大地的外形之间没有因果和实质关系存在, 但蕴含式WV是真, 因为前提是假而结论是真。,形式蕴含和实质蕴含,蕴含式PQ可以用多种方式陈述: ; “若P, 则Q” “P是Q的充分条件” “Q是P的必要条件” “Q每当P” “P仅当Q”“除非Q, 才P” 或 “除非Q，否则非P”，等。如上例(b)中的RS可陈述为“G是正方形的必
12、要条件是它的四边相等”。 给定命题PQ, 我们把QP,PQ, QP分别叫做命题PQ的逆命题 , 反命题和逆反命题.,例4 设 P：天冷，Q：小王穿羽绒服，将下列命题符号化 (1) 只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候.,蕴涵联结词的实例,PQ,注意： PQ 与 QP 等值（真值相同）,PQ,PQ,QP,QP,PQ,QP,QP,定义1.5: 设
13、P, Q为两个命题，复合命题“P当且仅当Q”称作P与Q的等值式，记作PQ，称作等值联结词. 规定PQ为真当且仅当 P与Q同时为真或同时为假.PQ 的逻辑关系：P与Q互为充分必要条件,等值联结词,例5 求下列复合命题的真值 (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,0,1,0,联结词的运算顺序,在没有括号的情况下： 联结词的运算顺序：, , , , 同级按先
14、出现者先运算.,凡符合联结词运算顺序的, 括号均可省去。 相同的运算符, 按从左至右次序计算时, 括号可省去。 最外层的圆括号可以省去。 例: (PQ)R)(RP)Q) 可写成 ：(PQR)RPQ 但有时为了醒目, 也可以保留某些原可省去的括号。,本小节中P, Q, R, 均表示命题.,联结词集为, , , , ，P, PQ, PQ, PQ, PQ为基本复合命题. 其中要特别注意理解PQ的涵义. 反复使用, , , , 中的联结词组成更为复杂的复合命题.,小 结,命题公式及其赋值,命题变项与合式公式 命题变项 命题公式 命题公式的层次 公式的赋值 公式赋值 公式类型 真值表,命题公式的层次,定
15、义： (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层公式.例如 公式 A=P, B=P, C=PQ, D=(PQ)R, E=(PQ) R) (RS)分别为0层，1层，2层，3层，4层公式.,命题
16、公式,命题常项命题变项（命题变元）常项与变项均用 P, Q, R, , Pi, Qi, Ri, , 等表示.,定义: 命题公式的递归定义：(1) 单个命题变项和命题常项是命题公式, 称作原子命题公式(2) 若A是命题公式，则 (A)也是(3) 若A, B是命题公式，则(AB), (AB), (AB), (AB)也是(4) 只有有限次地应用(1)(3) 形成的符号串才是命题公式。这样定义的命题公式也叫合式公式（简称公式）。,定义： 设P1, P2, , Pn是出现在公式A中的全部命题变项, 给P1, P2, , Pn各指定一个真值, 称为对A的一个赋值或解释. 若使A为1, 则称这组值为A的成真赋值; 若使A为0, 则称这组值为A的成假赋值.几点说明： A中仅出现 P1, P2, , Pn，给A赋值=12n是指P1=1, P2=2, , Pn=n, i=0或1, i之间不加标点符号含n个命题变项的公式有2n个赋值.如 000, 010, 101, 110是(PQ)R的成真赋值001, 011, 100, 111是成假赋值.,
