《离散数学》教学大纲（专科）
说 明
一． 课程的性质
本课程是为计算机科学与技术专业专科开设的专业基础课。
离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程，是学习专业理论不可少的数学工具。离散数学是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般地是有限个和可数个元素，充分描述了计算机科学离散性的特点。在计算机科学中，离散数学与数据结构、操作系统、逻辑设计、算法分析、编译原理、人工智能、系统结构等课程联系紧密。
学习离散数学不仅为后续课程作必要的理论准备，而且其课程内容中所提供的一些把科学理论应用于实践的范例，可以培养学生逐步增强如何实施“科学理论---技术---生产力”转化的观念和方法，提高学生在知识经济时代中的适应能力。同时本课程在培养学生的创新能力，提高学生的科研素质方面都有着重要作用。
二． 课程的教学目的和要求
在计算机科学教学中，离散数学主要是为专业服务的基础理论课，是一门概念较多、理论性较强，应用性较广的课程。本课程主要教授数理逻辑、集合论、代数系统、图论方面的基础知识，是计算机科学与技术教学中一些后续课程学习的基础和工具。通过本课程的学习，要使学生掌握离散数学的基本概念和基本原理，以现代数学的观点和方法，初步掌握处理离散结构所必须的描述工具和方法。同时，也要培养学生抽象思维、慎密概括、逻辑推理的能力，从而使学生具有良好的开拓专业理论的素质和使用所学知识，分析和解决实际问题的能力。
三． 课程的主要教学内容
1. 集 合 论：集合的基本概念，集合的运算，包含排斥原理。
2. 二元关系：集合的笛卡尔乘积，关系的定义，关系的表示法，特殊关系，复合关系和逆关系，关系的闭包运算。
3. 函数：函数的定义，特殊函数，复合函数和逆函数。
4. 代数结构：代数系统，特殊运算和特殊元素；同构概念，半群、群；子群，循环群，置换群；陪集和拉格朗日定理。环、域；格与布尔代数。
1第七章图论第八章
2习题：图的概念在前面的各章中已经引进过。在那里，图只是作为表达集合、关系、函数的一种工具。本章主要对无向图的基本概念、基本性质、各种特殊的图及其判别方法进行较为详细的讨论。最后将无向图的概念和性质推广到有向图。也只介绍最基本的内容。主要内容如下7.1图的基本概念7.5二部图7.2图的矩阵表示7.6平面图7.3欧拉图与哈密尔顿图7.7有向图7.4树7.8有向树本章教学要求及重点难点理解图及其相关基本概念；理解有向图和无向图的连通性；熟练掌握图的矩阵表示；理解Euler图和Hamilton图的基本概念和它们的区别；理解二部图，平面图，有向图的基本概念；理解树的基本概念，树的性质；熟练掌握求最小生成树的方法；熟练掌握对二叉树的前序、中序、后序遍历方法。重点：Euler图和Hamilton图的基本概念和它们的区别；判断一个图是二部图，平面图；最小生成树，二叉树的前序、中序、后序遍历。难点：判断一个图是平面图。
4习题：一，图的定义图：G 是一个有序二元组(V，E)，记作G ＝(V，E)，其中：⑴V 是一个有限非空的集合，V 的元素称为G 的结点(或顶点)，V 称为G 的结点集。⑵E 是由V 中不同元素的对偶({vi，v j}，v i≠v j)组成的集合。这些对偶称为G 的边（或弧），E 称为G 的边集。§7.1 基本概念§6.1 基本概念一，图的定义
5习题：例：图G =(V，E)中，v1v3v4v5v2v1v2v3v4v5v1v2v3v4v5其图解可以分别画成如下几种样子：V＝{v1, v2, v3, v4, v5}，E ＝{(v1 , v2), (v1, v3), (v2, v3), (v2, v4), (v3, v5), (v4, v5)}例
6有关习题：概念要点：①结点集不能为空，在图解中，结点用点或小圆圈表示；边集可以是空集，在图解中，边用直线或曲线表示；②一个图的图解表示可以是多样的，因为结点的位置和形状可以任意，边的长度和形状也可是任意的。③图是结点集与边集的集合，图解只是图的一种直观表示形式，概念上不要混淆。但图解是研究图的一种极其有用的工具。概念要点有向图、无向图与元素有关的概念：有向边：组成边的对偶{vi，vj}若是有序的，则称该边是有向边有向图：每一条边都是有向边的图称为有向图(下面的图b、d、e、h)无向边：组成边的对偶{vi，vj}若是无序的，则称该边是无向边无向图：每一条边都是无向边的图称为无向图(下面的图a、c、g )。本章主要讲无向图习题：v1v2v1v2(a)(b)v1v2(c)(d)(e)(f)(g)213123123(h)123x1x2x3123
内 容 简 介
本书共分五编。第一编为集合论，其中包括集合的基本概念、二元关系、函数、自然数、基
数、序数。第二编为图论，其中包括图的基本概念、图的连通性、欧拉图与哈密顿图、树、
平面图、图的着色、图的矩阵表示、覆盖集、独立集、匹配、带权图及其应用。第三编为代
数结构，其中包括代数系统的基本概念、几个重要的代数系统：半群、群、环、域、格与布
尔代数。第四编为组合数学，其中包括组合存在性、组合计数、组合设计与编码以及组合最
优化。第五编为数理逻辑，其中包括命题逻辑、一阶谓词逻辑、Herbrand定理和直觉逻辑。
本书体系严谨、内容丰富、配有大量的例题和习题，并与计算机科学的理论与实践密切结合。
本书不仅适用于计算机及相关专业的本科生或研究生，也可供计算机专业的科技人员使
用或参考。
目 录
第一编 集合论
第一章 集合(1)
1.1 预备知识(1)
1.2 集合的概念及集合之间的关系(7)
1.3 集合的运算(10)
1.4 基本的集合恒等式(13)
1.5 集合列的极限(17)
习题一(20)
第二章 二元关系(23)
2.1 有序对与卡氏积(23)
2.2 二元关系(26)
2.3 关系矩阵和关系图(32)
2.4 关系的性质(34)
2.5 二元关系的幂运算(37)
2.6 关系的闭包(39)
2.7 等价关系和划分(45)
2.8 序关系(49)
习题二(53)
第三章 函数(58)
3.1 函数的基本概念(58)
3.2 函数的性质(59)
3.3 函数的合成(62)
3.4 反函数(64)
习题三(68)
第四章 自然数(70)
4.1 自然数的定义(70)
4.2 传递集合(74)
4.3 自然数的运算(76) 4.4 N上的序关系(78)
习题四(80)
第五章 基数(势)(81)
5.1 集合的等势(81)
1
本学期离散课程我们共学习了命题逻辑，一阶逻辑，集合的基本概念，二元关系和函数，图的基本概念，树等六章内容。
第一章 命题逻辑
在读取蕴含式时，如果前件为假，命题逻辑就为真。
重要等值式：分配律，德.摩根律，吸收律，蕴含等值式，
由有限个简单合取式 构成的析取式称为析取范式；
由有限个简单析取式 构成的合取式称为合取范式。
N个命题变项，在简单合取式中每个命题变项与其否定有且仅有一个出现一次，称为极小项。
N个命题变项，在简单析取式中每个命题变项与其否定有且仅有一个出现一次，称为极大项。
若合取范式中的简单析取式全是极大项，则该合取范式称为主合取范式。
任一命题公式都有唯一的主合取范式。
最简展开式：包含最少运算。
推理定律：附加，化简，假言推理，拒取式，析取三段论，假言三段论，等价三段论，构造性二难
构造证明法的技巧：附加前提证明法，归缪法。
难点：构造推理的证明。
原因：需要有一定的解题技巧性。
解决方法：深刻理解推理定律并记住，多加练习。
第二章 一阶逻辑
自由出现和约束出现
无自由出现的个体变项简称闭式。
换名规则：将一个指导变项 及其所在辖域中所有约束出现替换成公式中没有出现的个体变项符号。
用谓词公式处处代换命题公式，即代换实例。
量词否定等值式，量词辖域收缩与扩张等值式，量词分配等值式。
A为一谓词公式，若A具有Q1x1Q2x2….B，则称A是前束范式。
难点：前束范式的求取。
原因：解题往往要用多个定理和换名规则，较繁琐。
解决方法：熟练掌握定理和规则，多做题。
第三章 集合的基本概念和运算
幂等律，结合律，交换律，分配律，同一律，零律，排中律，矛盾律，吸收律，德摩根律
双重否定律
难点：集合关系的证明，集合的化简 2
原因：运算较复杂
解决方法：掌握算律，特别是德摩根律。
第四章 二元关系和函数
A上二元关系：全域关系EA；恒等关系IA；小于等于关系LA；整除关系DA；
