离散数学及其算法-曹晓东,可在华章网站免费下载
离散数学及算法
离散数学及其算法-曹晓东,可在华章网站免费下载
课程名称：离散数学及算法 课 时： 学 分： 主讲教师： 联系方式：
离散数学及其算法-曹晓东,可在华章网站免费下载
教材及参考书 教材:– 离散数学与算法. 曹晓东，原旭等编著 .机 械工业出版社. 2007.
参考书:– 离散数学及应用.(英文版.第4版)(美) KennethH.Rosen著 – 离散数学.陈莉编著.高等教育出版社,2000.
离散数学及其算法-曹晓东,可在华章网站免费下载
学习方式 听课 (启发式、讨论式) 读书 (预习、复习) 报告 (综合练习)
离散数学及其算法-曹晓东,可在华章网站免费下载
考试成绩 平时成绩 (书面作业、综合练习、大作业30%) 期末考试(70%)
离散数学及其算法-曹晓东,可在华章网站免费下载
内容安排 数理逻辑– 包括命题逻辑和谓词逻辑(教材第一、二章)
集合论– 包括集合、关系和函数(教材第三、四、五 章)
代数系统– 包括代数系统的基本概念，几类典型的代数 系统(第六章)
图论– 包括图的基本概念，几种特殊的图(第七章)
离散数学及其算法-曹晓东,可在华章网站免费下载
第一章 命题逻辑 1.1引言 1.2命题及命题逻辑联结词 1.3命题变元和合式的公式 1.4重言式(或永真式)和永真蕴含式 1.5对偶原理 1.6范式和判定问题 1.7命题演算的推理理论
离散数学及其算法-曹晓东,可在华章网站免费下载
1.1引言 目标– 探索出一套完整的逻辑规则，这些规则 给出数学语句的准确定义，按照这些规 则可以确定任何特定的论证是否有效。
应用– 计算机电路设计 – 计算机程序构造 – 程序正确性证明
离散数学及其算法-曹晓东,可在华章网站免费下载
第一章 命题逻辑 1.1引言 1.2命题及命题逻辑联结词 1.3命题变元和合式的公式 1.4重言式(或永真式)和永真蕴含式 1.5对偶原理 1.6范式和判定问题 1.7命题演算的推理理论
离散数学及其算法-曹晓东,可在华章网站免费下载
1.2命题与命题逻辑联结词
1.2.1命题 1.2.2逻辑联结词
离散数学及其算法-曹晓东,可在华章网站免费下载
1.2.1命题一.定义：一个具有真假意义的陈述句被称为 一个命题。或真或假，不能既真又假。 例1:判断下面语句是否是命题 华盛顿是美国的首都。 多伦多是加拿大的首都。 1+101=110 几点了？ x+1=3 西安的小吃真多呀！
离散数学及其算法-曹晓东,可在华章网站免费下载
1.2.1命题 理发师问题– 理发师给所有不给自己理发的人理发。
离散数学及其算法-曹晓东,可在华章网站免费下载
1.2.1命题二、命题的真值及表示 命题用大写的英文字母，如，,,…来表示。 P:今天是星期二。 PQR 如果一个命题的真值是真，则用1或(Ture)来 表示；如果一个命题的真值是假，则用0或 (False)来表示。 原子命题 一个命题不能再分解为更简单的命题，这 个命题称为原子命题。
离散数学及其算法-曹晓东,可在华章网站免费下载
1.2命题与命题逻辑联结词
1.2.1命题 1.2.2逻辑联结词
离散数学及其算法-曹晓东,可在华章网站免费下载
1.2.2逻辑联结词复合命题，分子命题如果下周日下雪，那么我就去滑雪。
如果下周日不下雨并且没有考试，那么我去海 边玩。 这次演讲比赛，我们班将由赵明或者张强参加。
离散数学及其算法-曹晓东,可在华章网站免费下载
5种逻辑联结词 否定词“并非” 合取词“并且”
析取词“或者” 蕴含词“如果……,那么……”(单向词) 双向蕴含词“当且仅当”(双向词)
离散数学及其算法-曹晓东,可在华章网站免费下载
否定——
定义： 设 P是一个命题，则 P的否定是一个新的命题， P 记作“ P ”,读作“非 ”。 例2:找出命题“所有的素数都是奇数”的否定。 “并非所有的素数都是奇数。” 真值表：利用运算对象真值的 “所有的素数都不是奇数。” 所有可能组合判断命题的真假。 否定词“┐”的意义如下表：P T F P F T P P 0 1
或
1 0
离散数学及其算法-曹晓东,可在华章网站免费下载
合取——∧ 定义：
设P和Q是命题，则用P Q表示命题“P并且Q”。
表征意义 (在命题P和Q均为真时为真，否则为假。) 两命题合取的真值表P F F T T Q F T F T P Q F F F T P 0 Q 0 1 0 1 P Q 0 0 0 1
或
0 1 1
离散数学及其算法-曹晓东,可在华章网站免费下载
合取——∧命题P: 今天是星期五。 命题Q: 今天下雨。 找出命题P和Q的合取解：P Q表示“今天是星期五并且下雨”。 这一命题在下雨的星期五成真，不下雨 的星期五和不是星期五的日子都为假。