北京航空航天大学 离散数学由介跃建主讲

         教师简介：介跃建，男，1962年出生，学历：硕士，职称：副教授，1982年到1986年在中山大学学习，1986年到现在在中国农业大学任教，担任《高等数学》、《线性代数》、《概率论与数理统计》、《离散数学》等课程的教学工作，同时参加过《高等数学》、《概率论与数理统计》的教材编写，在教学效果评选中被评为优秀教师，在科研方面撰写十多篇论文。

离散数学大纲
        离散数学是现代数学的一个分支，是计算机专业的重要专业基础课，是计算机专业必修课程之一，通过本课程的学习，培养学生的抽象思维和严格的逻辑推理能力，并使他们掌握处理离散结构所必需的描述工具和方法，为进一步学习“数据结构”、“数据库原理与应用”、“操作系统”等专业课打好基础，同时也为学生今后从事计算机开发和应用工作提供必要的数学工具。

第一章 命题逻辑
一、考核知识点
1、 命题与联结词
2、 命题公式与赋值
3、 等值演算
4、 联结词的全功能集
5、 范式
6、 推理理论
二、考核目标与考核要求
1、 命题与联结词
（1）识记： A 命题与真值。B 简单命题、复合命题。C 命题常元与命题变元。
D 联结词。E 真值表。
（2）领会： A 命题p的否定式 。B 命题p和q的合取式 。C 命题p和q的析取式 。D 命题p和q的蕴涵式 。E 命题p和q的等价式 。
（3）运用： A 运用六个常用联结词将命题符号化。B 熟练地判断复合命题的真假。
2、命题公式与赋值
（1）识记：A 命题公式的定义。B 公式的赋值。C 永真式、永假式、可满足式。
（2）领会：A 求给定公式的成真赋值和成假赋值。B 判断给定公式的类型。
（3）运用：A 熟练地求给定公式的真值表。B 用真值表判断给定公式的类型。
3、等值演算
（1）识记：A 两个公式等值的概念。B 等值演算。
（2）领会：置换规则的内容。
（3）运用：A 牢记并灵活运用重要的等值式：双重否定律、幂等律、交换律、结合律、分配律、吸收律、德?摩根律、零律、同一律、排中律、矛盾律、蕴涵等值式、等价等值式、异或等值式、假言易位等。B 用真值表判断两个公式是否等值。C 用等值演算判断两个公式是否等值。D 用等值演算判断公式的类型。 E 用等值演算解决实际问题。
4、 联结词的全功能集
（1）识记：A 联结词的全功能集。B 联结词的极小全功能集。
（2）领会：掌握 是全功能集。
（3）运用：由已知 是全功能集，证明其它联结词集合是全功能集。

5、 范式
（1）识记：A 简单析取式、简单合取式。B 析取范式、合取范式。C 极小项、极大项。D主析取范式、主合取范式。
（2）领会：A 求析取范式、合取范式的步骤。B 求主析取范式、主合取范式的步骤。
C 每个公式都有唯一的主析取范式和主合取范式。
（3）运用：A 熟练地求给定公式的主析取范式和主合取范式。 B 用主析取范式或主合取范式判断两公式是否等值。C 用主析取范式或主合取范式求公式的成真赋值和成假赋值。D 用主析取范式或主合取范式判断公式的类型。
6、 推理理论
（1）识记：A 推理。B 前提。C 逻辑推论。D 证明。
（2）领会：A 推理正确的定义。B 证明中用到的十条推理规则。C 附加前提证明法。
D 归谬法。
（3）运用：A 熟练地掌握判断推理是否正确的方法：真值表法、等值演算法、主析取范式法（主合取范式法）。B 用十条推理规则构造推理的证明。C 会使用附加前提证明法和归谬法。

第二章 一阶逻辑
一、考核知识点
1、一阶逻辑的基本概念
2、一阶语言及其解释
3、等值演算
4、前束范式
5、推理理论
二、考核目标与考核要求
1、 一阶逻辑的基本概念
（1）识记：A 个体、个体域、个体词、个体常元、个体变元。B 谓词。C 量词、全称量词、存在量词。
（2）领会：A 指定个体域与全总个体域。B 特性谓词。C 量词的意义由个体域确定。
（3）运用：A 熟练地将不太复杂的命题符号化。B 在不同个体域中将命题符号化。
2、 一阶语言及其解释
（1）识记：A 一阶语言的符号。B 项。C 原子公式。D 一阶公式。E 辖域。
F 变元的约束出现和自由出现。G 闭式。H 解释。I 赋值。J 代换实例。K 永真式、永假式、可满足式、重言式。
（2）领会：A 构成解释的四个组成部分。B 项和公式在解释和赋值下的意义。
C 项t对于公式A ( x ) 中的变元x的可代入性。
(3) 运用：A 在有限个体域下求公式的真值。B 求某些公式在给定解释下的真值。
C判断一个公式是否是重言式。D判断某些简单公式的类型。
3、 等值演算
(1) 识记：A 两个公式等值的概念。B 十三个常用的等值式。C 约束变元换名规则。
(2) 领会：A 常用等值式成立的条件。B量词辖域收缩与扩张的等值式。C 全称量词 对 不可分配。D 存在量词对 不可分配。
4、 前束范式
(1) 识记：A 前束范式。B 公式的前束范式。
(2) 领会：A 将一个公式化为与其等值的前束范式的步骤。B 一个公式的前束范式不是唯一的。
(3) 运用：求给定公式的前束范式。
5、 推理理论
(1) 识记：A 推理。B 前提。C 逻辑推论。D 证明。
(2) 领会：A推理正确的定义。B全称量词消去规则、全称量词引入规则、存在量词消去规则、存在量词引入规则及使用它们的限制条件。
(3) 运用：A 给出某些简单推理的证明。 B 用构造证明的方法证明某些简单实际问题中的推理是正确的。

第三章 集合的基本概念和运算
一、考核知识点
1、集合的基本概念
2、集合的运算
3、有限集合的计数
二、 考核目标与考核要求
1、 集合的基本概念
（1）识记：A 元素和集合的属于关系。B 有限集和无限集。C 子集和真子集。
D 集合的相等。E 空集。F 幂集。
（2）领会：A 全集的相对性。B 集合A的幂集是由A的全体子集构成的集合。
（3）运用：A 用集合的两种表示法表示集合。 B 求给定集合的幂集。
2、 集合的运算
（1）识记：A 交集。B 并集。C 差集。D 补集。E 对称差集。F 常用的集合恒等式。
（2）领会：A 用文氏图直观地表示集合的运算和集合之间的关系。B 证明集合相等的两种方法。
（3）运用：A 由给定集合求它们运算后所得集合。B 证明集合恒等式。
3、有限集合的计数
运用：用文氏图进行有限集合的计数。

第四章 关系和函数
一、 考核知识点
1、 有序偶和笛卡儿积
2、 关系的表示法以及关系的性质
3、 关系的运算
4、 等价关系和划分
5、 偏序关系
6、 函数的基本概念及性质
7、 函数的复合
8、 反函数
二、 考核目标与考核要求
1、 有序偶和笛卡儿积
(1) 识记：A 有序偶。B 有序n元组。C 笛卡儿积。
(2) 领会：A 有序偶和无序偶的区别。B 笛卡儿积运算的性质。
2、 关系的表示法以及关系的性质
(1) 识记：A 关系。B 集合A到集合B的关系。C 集合A上的关系。D 空关系。
E 集合A上的恒等关系。F 集合A上的全域关系。G 关系的定义域。H 关系的值域。I 关系矩阵。J 关系图。K 集合A上关系的自反性、反自反性、对称性、反对称性、传递性。
(2) 领会：A 用关系矩阵确定关系的性质。B 用关系图确定关系的性质。
(3) 运用：A 求给定关系的定义域和值域。B 判断关系的性质。
3、 关系的运算
(1) 识记：A 关系的复合。B 关系的幂运算。C 逆关系。D 关系的自反闭包、对称闭包、传递闭包。
(2) 领会：关系的复合运算满足结合律，但不满足交换律。
(3) 运用：A 由给定关系求复合关系和逆关系。B 求给定关系的自反闭包、对称闭包、传递闭包。
4、 等价关系和划分
(1) 识记：A 等价关系。B 等价类和商集。C 划分。
(2) 领会：等价关系和划分之间的一 一对应关系。
(3) 运用：A 判断集合A上的关系是否为等价关系。B 判断集合A的子集构成的集合是否是A上的划分。C 求给定等价关系决定的划分，即商集。
5、 偏序关系
(1) 识记：A 偏序关系。B 偏序集。C 全序关系。D 严格偏序关系。E 哈斯图。F 最大元、最小元、极大元、极小元。G 上界、下界、最小上界、最大下界。
(2) 领会：A 偏序关系、全序关系、严格偏序关系这三个概念之间的关系。B最大元和极大元，最小元和极小元之间的区别。
(3) 运用：A 判断集合A上的关系是否为偏序关系、全序关系、严格偏序关系。 B 画出给定偏序集的哈斯图。 C 求最大元、最小元、极大元、极小元、上界、下界、最小上界、最大下界。
6、函数的基本概念及性质
(1) 识记：A 函数。B 从集合A到集合B的函数。C 单射、满射、双射。D 恒等函数。E 常函数。F集合的特征函数。G 自然映射。
(2) 领会：A 函数是满足单值性的关系。B 单射、满射、双射的性质。
(3) 运用：A 判断一个关系是否是函数。 B 判断一个关系是否是从集合A到集合B的函数。C 判断一个函数是否是单射、满射、双射。 D 构造两个集合之间的双射。
7、函数的复合
(1) 识记：A 函数的复合。B 函数的复合运算满足结合律。
(2) 领会：A 函数的复合和关系的复合在记法上的区别。B 单射（满射、双射）和单射（满射、双射）的复合仍然是单射（满射、双射）。
(3) 运用：求两个给定函数的复合函数。
8、反函数
(1) 识记：反函数
(2) 领会：A 只有双射才有反函数。B 双射的反函数仍然是双射。
(3) 运用：A 判断一个函数是否有反函数。 B 求双射的反函数。

第五章 代数系统概述
一、 考核知识点
1、 二元运算及其性质
2、 代数系统
3、 代数系统的同态和同构
二、 考核目标与考核要求
1、 二元运算及其性质
(1) 识记：A n元运算。B 二元运算的结合律、交换律、幂等律、分配律、吸收律、消去律。C 幺元、零元、逆元。D 一元运算和二元运算的运算表。
（2）领会：A n元运算应该满足的条件。B 至多有一个幺元或零元。C 对于可结合的二元运算，每个元素至多有一个逆元。
(3) 运用：A 判断给定二元运算是否满足交换律、结合律、幂等律、分配律、吸收律、消去律等。 B 求幺元、零元、逆元。C 列一元运算和二元运算的运算表。
2、 代数系统
(1) 识记：A代数系统。B 子代数系统。
(2) 领会：A代数系统的概念。B 构成子代数系统的条件。
(3) 运用：判断代数系统的子集能否构成子代数系统。
3、 代数系统的同态和同构
(1) 识记：A 同态、单同态、满同态、自同态、。B 同构、自同构。
(2) 领会：理解同态、单同态、满同态、自同态、同构、自同构这些概念的异同，以及它们之间的关系。
(3) 运用：判断一个函数是否是同态、单同态、满同态、同构。

第六章 几种典型的代数系统
一、考核知识点
半群、幺半群和群
二、考核目标与考核要求
半群、幺半群和群
（1）识记: A 半群、子半群、半群同态。B 幺半群、子幺半群、幺半群同态。
C 群。D 群的阶。E 有限群与无限群。F 群中元素的阶。G交换群。H 克莱因四元群。I 循环群。J 循环群的生成元。K 子群。L群同态。
（2）领会：A 群的性质。B 群的子集构成子群的充分必要条件。
（3）运用：A 判断一个代数系统是否是群、半群、幺半群。B 判断群（半群、幺半群）的一个子集是否构成子群（子半群、子幺半群）。 C 求一个群的所有子群。 D 判断一个函数是否是群同态（半群同态、幺半群同态）。

第七章 图的基本概念
一、 考核知识点
1、 无向图与有向图
2、 通路、回路、图的连通性
3、 带权图与最短通路
4、 图的矩阵表示
二、 考核目标与考核要求
1、 无向图与有向图
（1）识记：A 无向图与有向图的定义。B 无向图中顶点的邻接（相邻）。C 顶点与边的关联。D 边的相邻。E 有向图中顶点的邻接。F 悬挂顶点与悬挂边。
（2）领会：A 有限图。B 零图与平凡图。C 简单图与多重图。D 正则图。
E 完全图。F 子图、生成子图、导出子图。G 补图。H 图的同构。I无向图中顶点的度数。J 有向图中顶点的入度、出度、度数。
（3）运用：A 灵活运用握手定理及其推论。 B 判断两个图是否同构。 C 能画出无向图 的满足某种要求的所有非同构子图。
2、 通路、回路、图的连通性
（1）识记：A 通路的定义。B 回路的定义。C 无向图中顶点之间的可达关系。D有向图中顶点之间的可达关系。 E 无向图或有向图中两顶点之间的短程线和距离。
（2）领会：A 通路的分类：初级通路、简单通路、复杂通路。B 回路的分类：初级回路、简单回路、复杂回路。C 无向连通图、连通分支。D有向连通图的分类：强连通图、单向连通图、弱连通图。E 点割集、割点。F 边割集、割边（桥）。
（3）运用：判断有向图或无向图中通路或回路的类型。
3、 带权图与最短通路
（1）领会：A 带权图。B 通路的权。C 带权图中两顶点之间的最短通路和矩离。
（2）运用：用Dijkstra列表法求带权图中两顶点之间的最短通路和距离。
4、 图的矩阵表示
（1）领会：A 无向图的关联矩阵。B 有向图（无环）的关联矩阵。C 有向图的邻接矩阵。D 有向图的可达矩阵。
（2）运用：A 由有向图的邻接矩阵的k次幂求从一顶点到另一顶点的长度为k 的通路数。B 通过邻接矩阵求有向图的可达矩阵。

第八章 树
一、 考核知识点
1、 树与生成树
2、 根树及其应用
二、 考核目标与考核要求
1、 树与生成树
（1）识记：A 无向树。B 树叶、分支点。C 森林。D 平凡树。E 生成树。F生成树的树枝、弦。G 生成树对应的基本回路、基本回路系统。H 生成树对应的基本割集、基本割集系统。I 最小生成树。
（2）领会：A 无向树的几个等价定义。B 非平凡无向树至少有两片树叶。C 任何连通无向图至少含有一棵生成树。D 在有m条边的n阶连通图中，生成树有n - 1条树枝，m – n + 1条弦。
(3) 运用：A 画顶点数等于n的全体非同构的无向树，其中 。 B 利用握手定理及树的性质，由已知树中某些顶点的度数求树中其它顶点的度数。
C 求连通图的生成树、基本回路、基本割集、基本回路系统、基本割集系统。 D 用kruskal的避圈法求最小生成树。
2、 根树及其应用
(1) 识记：A 有向树。B根树。C 树根、树叶、分支点。D 根树中顶点的层数及
树高。E 家族树、父亲、儿子、兄弟、祖先、后代。F子树。G有序树。
H 二元有序正则树的左子树、右子树。I 位置树。J 二元前缀码。K 最优二元树。
(2) 运用：A 将给定的有序树转化为二元位置树。 B 由一棵给定的二元正则树产生唯一的前缀码。 C 用Huffman算法求最优二元树。

第九章 几类特殊图
一、考核知识点
1、欧拉图与哈密顿图
2、二部图
3、平面图
二、考核目标与考核要求
1、欧拉图与哈密顿图
（1）识记：A 欧拉通路。B 欧拉回路。C 欧拉图。D 哈密顿通路。E 哈密顿回路。F 哈密顿图。
（2）领会：A 无向图为欧拉图的充分必要条件。B 有向图为欧拉图的充分必要条件。C 教材中给出哈密顿图的必要条件。D教材中给出的哈密顿图的充分条件。
（3）运用：识别欧拉图
2、二部图
（1）识记：A 二部图。B 完全二部图。　
（2）领会：二部图的判别定理。
（3）运用：用二部图给出某些简单的人员与任务的分配方案。
3、 平面图
（1）识记：A 平面图。B 平面图的面及次数。C 极大平面图。D 平面图的对偶图。
（2）领会：A 各面次数之和为边数的两倍。B 欧拉公式。C 平面图。
（3）运用：利用定义判断某些图是否为平面图。
? 参考文献:
[1] 耿素云、屈婉玲,离散数学基础, 北京大学出版社,1994年。
[2] 马振华，离散数学导引，清华大学出版社，1993年。
[3] 尹宝林、何自强、许光汉、檀凤琴，离散数学，高等教育出版社，1998年。
? 离散数学考试方式：采用闭卷考试。