离散数学2010串讲

《离散数学教案》课件第一章：离散数学简介1.1 离散数学的定义与意义离散数学的定义离散数学在计算机科学中的应用1.2 离散数学的基本概念集合逻辑函数图论1.3 离散数学的研究方法形式化方法归纳法构造法第二章：集合与逻辑2.1 集合的基本概念与运算集合的定义与表示方法集合的运算（并、交、差、补）2.2 逻辑基本概念命题与联结词逻辑推理规则（蕴涵、逆否、德摩根定律）2.3 命题逻辑与谓词逻辑命题逻辑的形式化表示与推理谓词逻辑的形式化表示与推理第三章：函数与图论3.1 函数的基本概念与性质函数的定义与表示方法函数的单调性、连续性、奇偶性3.2 图的基本概念与运算图的定义与表示方法图的运算（节点、边、路径、连通性）3.3 树的基本概念与应用树与图的关系树的结构性质与应用（二叉树、堆、平衡树）第四章：组合数学4.1 组合数学的基本概念排列组合的定义与公式组合数学的应用（计数原理、图论）4.2 组合数学的计算方法直接法、间接法、递推法、函数法4.3 组合数学在计算机科学中的应用算法设计与分析（动态规划、贪心算法）程序语言中的组合类型（类型系统、类型检查）第五章：数理逻辑与计算复杂性5.1 数理逻辑的基本概念命题逻辑的数学模型（布尔代数、逻辑函数）谓词逻辑的数学模型（一阶逻辑、描述逻辑）5.2 计算复杂性的基本概念与分类计算复杂性的定义与度量（时间复杂性、空间复杂性）计算复杂性的分类（P与NP问题、整数分解问题）5.3 离散数学在算法设计与分析中的应用算法设计与分析的基本原则离散数学在算法优化与分析中的作用第六章：关系与映射6.1 关系的基本概念关系的定义与性质关系的类型（对称性、传递性、反身性）6.2 关系的闭包与简化关系的闭包概念关系的简化与规范化6.3 函数与二元关系函数与关系的联系与区别二元组与二元关系的应用第七章：代数结构7.1 代数结构的基本概念群、环、域的定义与性质代数结构在计算机科学中的应用7.2 群与群作用群的定义与运算群作用与群同态7.3 环与域环的定义与性质域的特殊性质与应用第八章：数理逻辑与计算理论8.1 数理逻辑的进一步应用命题逻辑与谓词逻辑的推理规则数理逻辑在计算机科学中的应用8.2 计算理论的基本概念计算模型的定义与分类计算复杂性的理论基础8.3 离散数学在计算理论中的应用计算理论中的逻辑与证明离散数学在算法设计与分析中的作用第九章：组合设计与计数原理9.1 组合设计的基本概念组合设计的定义与类型组合设计在编码理论中的应用9.2 计数原理的基本概念鸽巢原理、包含-排除原理函数的方法与应用9.3 图论与网络流图的遍历与路径问题网络流与最优化问题第十章：离散数学的综合应用10.1 离散数学在计算机科学中的应用算法设计与分析数据结构与程序语言设计10.2 离散数学在数学与应用数学中的作用组合数学在概率论与数论中的应用图论在网络科学与社会网络分析中的应用10.3 离散数学在未来科技发展中的展望量子计算与离散数学与逻辑推理重点和难点解析重点环节一：集合的基本概念与运算集合的表示方法（列举法、描述法）集合的运算（并、交、差、补）重点环节二：逻辑基本概念与推理命题与联结词（且、或、非）逻辑推理规则（蕴涵、逆否、德摩根定律）重点环节三：函数的基本概念与性质函数的定义与表示方法函数的单调性、连续性、奇偶性重点环节四：图的基本概念与运算图的定义与表示方法图的运算（节点、边、路径、连通性）重点环节五：组合数学的基本概念与计数原理排列组合的定义与公式组合数学的应用（计数原理、图论）重点环节六：关系与映射关系的定义与性质关系的类型（对称性、传递性、反身性）重点环节七：代数结构的基本概念群、环、域的定义与性质代数结构在计算机科学中的应用重点环节八：数理逻辑与计算理论数理逻辑的推理规则计算理论的基本概念（计算模型、计算复杂性）重点环节九：组合设计与计数原理组合设计的定义与类型计数原理的应用（鸽巢原理、包含-排除原理）重点环节十：离散数学的综合应用离散数学在计算机科学中的应用（算法设计与分析、数据结构与程序语言设计）离散数学在数学与应用数学中的作用（组合数学在概率论与数论中的应用、图论在网络科学与社会网络分析中的应用）全文总结和概括：本《离散数学教案》课件涵盖了离散数学的基本概念、逻辑推理、函数与图论、组合数学、数理逻辑与计算理论、组合设计与计数原理等多个重要环节。

16
1-2 联结词（续）
例：P：上海是一个大城市。 P：上海并不是一个大城市。 或 P：上海是一个不大的城市。
这两个命题具有相同的含义，因此用 同一个符号表示。
17
1-2 联结词（续）
P与 P的真值关系：
P
T F
PHale Waihona Puke F T否定是一个一元运算。
18
1-2 联结词（续）
（2）合取 设P，Q是两个命题，新命题“P并且Q”是 一个复合命题，称为命题P，Q的合取。记作： P∧Q 如：P：北京是中国的首都。 Q：北京是一个故都。 P∧Q：北京是中国的首都并且是一个 故都。
5

趣味逻辑数学题－巧猜围棋子

用数理逻辑学方法解题
P表示：“棋子为白色” Q表示：“甲说的是真话” 数理逻辑运算符： （非），（与），（或）
问题答案：S=(PQ)(PQ)
6
第一篇
数理逻辑
7
数理逻辑

数理逻辑是用数学方法来研究推理 过程的科学。主要是指引进一套符 号体系的方法，因此数理逻辑一般 又叫符号逻辑。 基本内容是：命题逻辑（演算）和 谓词逻辑（演算）。
22
1-2 联结词（续）
P∨Q的真值关系：
P T T F F Q T F T F P∨Q T T T F
析取是一个二元运算。
23
1-2 联结词（续）
注意：析取联结词∨与汉语中的“或”的意义不 完全相同。汉语中的“或”既可以表示“排斥 或”，也可以表示“可兼或”。
例如： P：今天晚上我在家看电视或去剧场看戏。 Q：他可能是100米或400米赛跑的冠军。
28
1-2 联结词（续）
在命题演算中，五个联结词的含义由真值表唯一确定。

1/1
Undirected graphs (Õã)
Definition: A graph G = (V, E) consists of V , a nonempty set of vertices (º:) or nodes and E, a set of edges (>). Each edge has either one or two vertices associated with it, called its endpoints. An edge is said to connect its endpoints. A graph with an infinite vertex set is called an infinite graph; a graph with a finite vertex set is called a finite graph. Example: A computer network is made up of data centers and communication links between computers.
Each phone call is represented by a directed edge There are multiple edges
9 / 41
Terminology for undirected graphs
Definition: Two vertices u and v in an undirected graph G are called adjacent (ƒ ) or neighbors in G if u and v are endpoints of an edge of G. The edge is called incident ('é) with u and v. The degree (Ý) of a vertex v in an undirected graph, denoted by deg(v), is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex. A vertex of degree zero is called isolated ( á ) A vertex is pendant (]! ) if it has degree one

3
离散数学
掌握等价关系的概念，并掌握覆盖、划分、等价类、 掌握等价关系的概念，并掌握覆盖、划分、等价类、商集的定 义和基本性质，弄清楚等价关系与划分之间的关系。 义和基本性质，弄清楚等价关系与划分之间的关系。牢记等价关 系的分类作用。 分类作用 系的分类作用。 掌握半序、半序集、全序、良序等概念， 掌握半序、半序集、全序、良序等概念，以及半序集的可比较 极大元、极小元、最大元、最小元、上界、下界、最大下界、 性、极大元、极小元、最大元、最小元、上界、下界、最大下界、 最小上界、直接后继等概念。牢记半序关系的非线性特性。 非线性特性 最小上界、直接后继等概念。牢记半序关系的非线性特性。 能画出有限半序集的哈斯图,并根据图讨论半序集的某些性质。 能画出有限半序集的哈斯图,并根据图讨论半序集的某些性质。
4
离散数学
第三章 函 数 重点要求
要求掌握函数的基本概念,弄清单射、满射、双射之间的区别。 要求掌握函数的基本概念 弄清单射、满射、双射之间的区别。 弄清单射 给定一个函数,要能够确定它是否是单射 满射、双射等。 要能够确定它是否是单射、 给定一个函数 要能够确定它是否是单射、满射、双射等。 掌握反函数和复合函数的定义和性质,并弄清楚它们存在的条件 并弄清楚它们存在的条件。 掌握反函数和复合函数的定义和性质 并弄清楚它们存在的条件。 理解元素及集合的象及原象的定义及相关的性质。 理解元素及集合的象及原象的定义及相关的性质。给定一个函 能够确定一个点的象,一个集合的象 能够确定一个点的原象,一 数,能够确定一个点的象 一个集合的象 能够确定一个点的原象 一 能够确定一个点的象 一个集合的象,能够确定一个点的原象 个集合的原象,能够确定两个函数的复合函数等 能够确定两个函数的复合函数等。 个集合的原象 能够确定两个函数的复合函数等。 掌握集合的势、可数集、不可数集等概念。 掌握集合的势、可数集、不可数集等概念。