做命题P→Q的逆命题 , 反命题和逆反命题.
蕴涵联结词的实例
例4 设 P：天冷，Q：小王穿羽绒服，将下列命题符号化 • PQ (1) 只要天冷，小王就穿羽绒服. • PQ (2) 因为天冷，所以小王穿羽绒服. • PQ (3) 若小王不穿羽绒服，则天不冷. • QP (4) 只有天冷，小王才穿羽绒服. • QP (5) 除非天冷，小王才穿羽绒服. • PQ (6) 除非小王穿羽绒服，否则天不冷. • QP (7) 如果天不冷，则小王不穿羽绒服. • QP (8) 小王穿羽绒服仅当天冷的时候.
• 注意： PQ 与 QP 等值（真值相同）
等值联结词
定义1.5: 设 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) 2 或 4 是素数. (2) 小元元只能拿一个苹果或一个梨. (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．《数理逻辑》，北京大学出版社，王捍贫编著； 5．《集合论与图论》，北京大学出版社，耿素云编著； 6．《代数结构与组合数学》，北京大学出版社，屈婉玲编著。
否定、合取、析取联结词
定义1.1: 设 P为命题，复合命题“非P”(或“P的否定”) 称为P的否定式，记作P，符号称作否定联结词. 规定 P 为真当且仅当P为假. 定义1.2: 设P,Q为两个命题，复合命题“P并且Q”(或“P 与 Q”)称为P与Q的合取式，记作P∧Q，∧称作合取联结 词. 规定P∧Q为真当且仅当P与Q同时为真. 定义1.3: 设P, Q为两个命题，复合命题“P或Q”称作P与 Q的析取式，记作P∨Q，∨称作析取联结词. 规定P∨Q 为假当且仅当P与Q同时为假.
1 0 1 0 0
联结词的运算顺序
• 在没有括号的情况下： – 联结词的运算顺序：, , , , • 同级按先出现者先运算.
凡符合联结词运算顺序的, 括号均可省去。 相同的运算符, 按从左至右次序计算时, 括号可省去。 最外层的圆括号可以省去。
例: (((P∧Q)∨R)→((R∨P)∨Q))
可写成 ：
(P∧Q∨R)→R∨P∨Q 但有时为了醒目, 也可以保留某些原可省去的括号。
小
结
• 本小节中P, Q, R, … 均表示命题.
• 联结词集为{, , , , }，P, PQ, PQ, PQ, PQ为 基本复合命题. 其中要特别注意理解PQ的涵义.
• 反复使用{, , , , }中的联结词组成更为复杂的复合命 题.
离散数学
主讲：路永刚
Email: ylu@
兰州大学信息科学与工程学院
发展历史
• 18世纪以前, 数学基本上是研究离散对象的数量和空间关系的科学。 • 后来因天文学,物理学的发展,如行星轨道,牛顿三大力学定律等研究,极 大地推动了连续数学(以微积分,数学物理方程, 复变函数论为代表)的 发展。离散对象的研究则处于停滞状态。 • • • • 20世纪30年代, 图灵(Alan Turing) 提出计算机的 理论模型——图灵机（Turing machine）。 这种模型早于实际制造计算机十多年，而现实的 计算机的计算能力, 本质上和图灵机的计算能力一样。
例 1 中(a) , (b) , (d) , (e)都是原子命题,
但“(c) 2 是偶数而 3 是奇数”不是, 因为它可写成“2 是偶 数”和“3 是奇数”两个命题。 命题和原子命题常用大写字母 P , Q , R :表示。 如用P表示“4 是质数”, 则记为 ：“ P: 4 是质数。”
命题分类
命题分类：原子命题与复合命题 原子命题 表示符号： 常用大写字母 P , Q , R 等表示 复合命题：是指由原子命题组成的命题 表示：常由联结词和大写字母（原子命题）组成 下面我们介绍联结词
命题公式及其赋值
命题变项与合式公式 命题变项 命题公式 命题公式的层次
公式的赋值 公式赋值 公式类型 真值表
命题公式的层次
定义：
(1) 若公式A是单个命题变项，则称A为0层公式. (2) 称 A 是 n+1(n≥0) 层公式是指下面情况之一： (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层公式.
• 由于在计算机内，机器字长总是有限的, 它代表离散的数或其它离散 对象，因此随着计算机科学和技术的迅猛发展，离散数学就显得更加 重要。
离散数学
• 离散数学，是现代数学的一个重要分支，是整个 计算机学科的专业基础课。
• 离散数学是以研究离散量的结构和相互间的关系 为主要目标。其研究对象一般地是有限个或可数 个元素，因此它充分描述了计算机科学离散性的 特点。
成绩考核办法
本课程的考核分为平时成绩和期末考试成绩两大部 分，其中平时成绩由日常考查成绩和作业成绩 组成，期末考试以闭卷笔试为主。
总成绩评定按百分制计算，平时成绩占30％，期末 成绩占70％。 总成绩计算公式： 总成绩＝平时成绩×30％＋期末成绩×70％
怎样学好本课程
• 该课程概念比较抽象、理论性比较强，所以需要 上课前预习，课堂注意听讲，积极提问，课后要 常复习，并认真完成作业。
蕴涵联结词
定义1.4: 设P, Q为两个命题，复合命题“如果P, 则Q”称作P与 Q的蕴涵式，记作PQ，并称P是蕴涵式的前件，Q为蕴涵式 的后件，称作蕴涵联结词. 规定：PQ为假当且仅当P为真Q为假.
(1) PQ 的逻辑关系：Q为 P 的必要条件 (2) 当 P 为假时，PQ恒为真，称为空证明 (3) 常出现的错误：不分充分与必要条件
• 本课程的教学应将以各种基本概念、定理、定理 证明、正反例、计算方法列为教学的重点，附带 讲各种具体应用。
第一章 数理逻辑
逻辑是研究推理的科学。 数理逻辑就是用数学方法（符号体系）研究推理的 科学。
主要内容：
• • • • • 命题逻辑基本概念 命题逻辑等值演算 命题逻辑推理理论 谓词逻辑基本概念 谓词逻辑等值演算与推理
蕴含式P→Q可以用多种方式陈述: ; “若P, 则” “Q每当P” “P仅当Q” “除非Q, 才P” 或 “除非Q，否则非P”，„．等。
如上例(b)中的R→S可陈述为“G是正方形的必要条件是 它的四边相等”。
给定命题P→Q, 我们把Q→P,P→Q, Q→P分别叫
例 1： 下述都是命题: (a) 今天下雪; (b) 3+3=6; (c) 2 是偶数而 3 是奇数; (d) 陈涉起义那天, 杭州下雨;
(e) 较大的偶数都可表为两个质数之和。
例 2： 下述都不是命题:
(a) x+y＞4。
(b) x=3。 (c) 真好啊!
(d) 你去哪里?
讨论 ： 一个人说:“我正在说谎”。这是不是命题？
合取联结词的实例
例： 将下列命题符号化. (1) 吴颖既用功又聪明. (2) 吴颖虽然聪明，但不用功. (3) 张辉与王丽都是三好生. (4) 张辉与王丽是同学. 解： 令P:吴颖用功, Q:吴颖聪明 (1) PQ (2) PQ (3) 设 P:张辉是三好生, Q:王丽是三好生， PQ (4) P: 张辉与王丽是同学
例7：
(a) P: 天不下雨, Q: 草木枯黄。
P→Q: 如果天不下雨, 那么草木枯黄。 (b) R: G是正方形, S: G的四边相等。 R→S: 如果G是正方形, 那么G的四边相等。 (c) W: 桔子是紫色的, V: 大地是不平的。 W→V: 如果桔子是紫色的, 那么大地是不平的。
形式蕴含和实质蕴含
(1) 单个命题变项和命题常项是命题公式, 称作原子命题公式 (2) 若A是命题公式，则 (A)也是 (3) 若A, B是命题公式，则(AB), (AB), (AB), (AB)也是 (4) 只有有限次地应用(1)—(3) 形成的符号串才是命题公式。
这样定义的命题公式也叫合式公式（简称公式）。
1.1 命 题
什么是命题？ 一个陈述语句叫做断言。 定义：一个命题是一个或真或假而不能两者都是的断言。
如果命题是真, 我们说它的真值为真
如果命题是假, 我们说它的真值是假。
命题
例：下列句子中那些是命题？ (1) 2是有理数. (2) 2 + 5 = 7. (3) x + 5 > 3. (4) 你去教室吗？ (5) 这个苹果真大呀！ (6) 请不要讲话！ (7) 2050年元旦下大雪. 假命题 真命题 不是命题 不是命题 不是命题 不是命题 命题，但真值现在不知道