中央广播电视大学《离散数学》课程教学大纲

第一部分 大纲说明

  1. 课程的性质与任务

    2. 《离散数学》是中央电大计算机应用专业计算机信息管理方向必修的专业基础课程。它是学习后续专业课程不可缺少的数学工具。该课程结合计算机学科的特点，主要研究离散量结构及相互关系，是一门理论性较强，应用性较广的课程。

    掌握集合论、数理逻辑和图论等离散数学的基本概念和基本原理，为学习计算机专业各后续课程做好必要的知识准备。进一步提高学生的抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。

  2. 与其他相关课程的关系

    3. 先修课程：线性代数。

    后续课程：数据结构、数据库等。

  3. 课程的主要内容与基本要求

本课程分为三部分：集合论、数理逻辑和图论。

  1. 集合论：主要讲述集合与关系。集合部分介绍最基本概念和集合的运算，重点是使学生会用集合描述和解决问题；关系部分要求掌握关系的性质，等价关系与偏序关系。

  2. 数理逻辑：作为计算机科学的一种重要知识表示工具，能将所研究的对象及其相互关系形式化，并进行简单的逻辑推理。

  3. 图论：主要介绍图的基本概念及其应用。

  1. 教学建议

    2. 离散数学是理论性较强的学科，学习离散数学的关键是准确掌握概念，多作练习。

  2. 教学要求的层次

各章教学的具体要求在后面列出的课程教学内容中给出，教学要求的层次为了解、理解和掌握。了解即能正确判别有关概念和方法；理解是能正确表达有关概念和方法的含义；掌握是在理解的基础上加以灵活应用。

第二部分 教学媒体与教学过程建议

一、课程教学总学时数、学分数

课程教学总学时数为45学时，其中授课45学时（含面授、录像学时），开设一学期。学分数为2.5学分。

二、文字教材与音像教材的配合

  1. 课程以文字教材为主，文字教材担负起形成整个课程体系系统性和完整性的任务，是学生学习的主要媒体形式。因此教材要概念准确，条理清晰，深入浅出，便于自学。

  2. 录像教材作为文字教材的强化媒体，配合文字教材讲授课程的重点、难点以及解题的分析方法与思路。

  3. 两者互相补充，互相配合。

三、学时的具体分配

教学内容 授课学时（含录像学时 ）

第一部分 集合论

【一】集合 3

【二】二元关系 14

第二部分 数理逻辑

【三】命题逻辑 12

【四】谓词逻辑 6

第三部分 图论

【五】图论 10

合计 45

四. 考核

本课程采用笔试考核方式。由中央电大根据教学大纲统一命题。

第三部分 教学内容与教学要求

【一】 集合

教学内容

3.1 集合的概念和表示 (.5)

一、集合、元素、子集、空集、全集、相等、幂集等概念

二、集合的表示方法

3.2 集合的运算 (1)

一、集合的交、并、差、补的概念

二、文氏（Venn）图

3.3 集合的运算性质 (1.5)

交换律、结合律、分配律、吸收律、 De Morgan律

3.4 典型例题解析与本章小结

教学要求

1. 掌握：子集、空集、全集、相等、幂集等基本概念；集合的表示法；集合的交、并、差、补等概念；交换律、结合律、分配律、De Morgan律等运算律，证明集合等式；

2. 理解：文氏图。

【二】 二元关系

教学内容

4.1 序偶与迪卡尔积 (1)

一、序偶与迪卡尔积

4.2 关系的概念和表示 (1.5)

一、二元关系

二、关系矩阵与关系图

4.3 关系的性质 (1.5)

    1. 自反性

    2. 对称性与反对称性

    3. 传递性

4.4 复合关系与逆关系 (1)

一、复合关系

二、逆关系

4.5 关系的闭包 (1.5)

一、自反闭包

二、对称闭包

三、传递闭包

4.6 等价关系 (2)

    1. 等价关系与等价类

    2. 划分

4.7 偏序关系 (2)

    1. 偏序关系、偏序集

    2. 哈斯（Hasse）图

    3. 序关系、序集

4.8 函数及其性质 (2)

一、函数

二、单射、满射、双射

4.9 复合函数与反函数 (1.5)

    1. 复合函数

    2. 反函数

4.10 典型例题解析与本章小结

教学要求

    1. 掌握：序偶与迪卡尔积的概念和应用；关系的概念；关系的性质；自反闭包、对称闭包、传递闭包的概念；等价关系与等价类的概念，划分的有关概念；偏序关系、偏序集的概念及用哈斯图表示；函数的概念。

    2. 理解：关系矩阵与关系图；复合关系与逆关系的概念及求法；单射、满射、双射的概念；复合函数与反函数的概念。

3. 了解：序关系与序集的概念。

【三】命题逻辑

教学内容

1.1 命题与联结词 （2）

一、命题与命题真值

二、五种逻辑联结词

三、复合命题

1.2 公式与解释 （3）

一、原子及其公式

二、公式的解释

三、真值表

四、公式的类型

五、公式的等价

1.3 范式 （2）

一、范式

二、主析取范式及其唯一性

1.4 公式类别的判别方法 （2）

    1. 真值表法

    2. 主析取范式

1.5 公式的蕴涵 （1.5）

    1. 公式蕴涵的三个等价定义及其逻辑结果

    2. 公式的逻辑结果与演绎的逻辑结果的等价性

    3. 基本蕴涵公式

1.6 形式演绎 (1.5)

    1. 规则P

    2. 规则Q

    3. 规则D

1.7 典型例题解析与本章小结

教学要求

1. 掌握： 命题、逻辑联结词的概念；公式与解释的概念，公式的递归定义，用基本等价式化简其他公式；主析取范式及其唯一性，用真值表法判断公式的类型；公式蕴涵与逻辑结果的概念；形式演绎方法。

2. 理解：用联结词产生复合命题的方法；公式在解释下的真值；公式范式的概念；形式演绎和蕴涵的关系。

【四】谓词逻辑

教学内容

    1. 个体词、谓词与量词 （1.5）

    1. 个体常元、变元和个体域

    2. 谓词与量词

    3. 谓词的约束变元与自由变元

    1. 公式与解释 (2)

    1. 原子公式

    2. 公式的递归定义

    3. 解释

    4. 谓词公式的类型

    1. 等价与蕴涵 (1)

    1. 等价

    2. 蕴涵

    1. 谓词逻辑命题符号化 (1.5)

4.6 例题解析与本章小结

教学要求

1. 掌握：个体词、个体域、谓词、量词的概念和使用；原子、公式、解释的概念；公式在解释下的真值；求公式的前束范式。

2. 理解：用谓词、量词、逻辑联结词描述一个简单命题；公式的递归定义；用解释的方法证明等价式和蕴涵式。

3 了解：以谓词逻辑为工具，将命题符号化。

【五】 图论

教学内容

4.1 图的概念 (2)

    1. 图的基本概念

    2. 无向图

    3. 图的连通性、同构

4.2 图的矩阵表示 (1)

一、关联矩阵

二、相邻矩阵

4.3 权图中的最短路问题 (2)

    1. 权图

    2. 最短路径

三、迪克斯特拉（Dijkstra） 算法

    1. 树 (3)

    1. 树

    2. 二叉树

    3. 支撑树

    4. 树的等价性定理

4.5 权图中的最小树 (1)

    1. 权图中的最小树

    2. 克鲁斯卡尔（Kruskal）算法

4.6 有向图与有向树 (1)

4.7 典型例题解析与本章小结

教学要求

1. 掌握：图的有关概念；用关联矩阵和相邻矩阵表示图；路的基本概念，权图的概念，用Dijkstra算法求权图中最短路；树、二叉树与支撑树的有关概念；用Kruskal算法求权图中最小树。

2. 理解：图的连通、同构的概念；树的等价定理；有向图与有向树的概念。

　

　

　

　

　

　

　

　

　

审定人：耿素云教授 北京大学

高维东教授 石油大学

张健清副教授 人民大学

99．4