《离散数学》课程教学大纲

1、PAGE PAGE 5离散数学 教学大纲（71001405） 一、说明 （一）课程性质 专业必修课, （二）教学目的 培养学生的抽象思维和慎密概括的能力，同时教授学生离散对象处理的基本理论和技术。 （三）教学内容 主要教学内容包括：数理逻辑、集合论、代数结构(群、环、域)、图论 （四）教学时数 周4学时,共72学时 （五）教学方式 课堂讲授 二、本文 第一篇 数理逻辑命题逻辑教学要点：熟练掌握命题逻辑、联结词的基本定义，进而掌握命题公式的定义和翻译，学会相应计算，理解并掌握等价式、重言式与蕴含式，掌握命题公式的的推理理论。教学时数： 12学时教学内容： 命题及其表示法(1学时)命题的定义及基本

2、概念联结词(2学时)联结词的定义、基本概念命题公式与翻译（2学时）命题公式的定义，以及如何将自然语言翻译成命题公式。真值表与等价公式（1学时）真值的定义、等价公式的定义与计算。重言式与蕴含式（2学时）重言式与蕴含式的定义，以及证明。1-6 其他联结词（1学时）对偶与范式（1学时）对偶与范式的定义和计算。1-8 推理理论（2学时）1-9 应用谓词逻辑教学要点：熟练掌握命题逻辑、联结词的基本定义，进而掌握命题公式的定义和翻译，学会相应计算，理解并掌握等价式、重言式与蕴含式，掌握命题公式的的推理理论。教学时数： 11学时教学内容：2-1 谓词的概念与表示（1学时）谓词的基本概念2-2 命题函数与量词

3、（2学时）命题函数与量词的基本概念、定义2-3 谓词公式与翻译（2学时）谓词公式的定义与将自然语言翻译成谓词公式2-4 变元的约束（1学时）基本定义与应用2-5 谓词演算的等价式与蕴含式（2学时）谓词演算的等价式与蕴含式的定义与证明2-6 前束范式（1学时）前束范式的定义与计算2-7 谓词演算的推理理论（2学时）谓词演算的推理规则以及推理理论第二篇 集合论集合与关系教学要点：熟练掌握命题逻辑、联结词的基本定义，进而掌握命题公式的定义和翻译，学会相应计算，理解并掌握等价式、重言式与蕴含式，掌握命题公式的的推理理论。教学时数： 21学时教学内容： 3-1 集合的概念和表示法（1学时）3-2 集合的

4、运算（2学时）3-3 包含排斥原理（带星号的内容）3-4 序偶与笛卡尔积（1学时）3-5 关系及其表示（2学时）3-6 关系的性质（2学时）3-7 复合关系和逆关系（1学时）3-8 关系的闭包运算（4学时）3-9 集合的划分和覆盖（2学时）3-10 等价关系与等价类（2学时）3-11 相容关系（2学时）3-12 序关系（2学时）第四章 函数教学要点：熟练掌握函数基本定义，进而能够计算逆函数与复合函数；了解技术的概念。教学时数： 4学时教学内容：4-1 函数的概念（1学时） 函数的定义4-2 逆函数和复合函数（1学时）逆函数的定义与计算；复合函数的定义与计算4-3 特征函数与模糊子集（带星号的内

5、容）4-4 基数的概念（1学时）基数的概念4-5 可数集与不可数集（1学时）可数集与不可数集的定义4-6 基数的比较（选讲内容）第三篇 代数系统 代数结构教学要点：熟练掌握群的基本定义，进而能够计算判定一个代数系统是否是群。教学时数：8学时教学内容：5-1 代数系统的引入（0.5学时） 代数系统的基本概念5-2 运算及其性质（0.5学时） 运算及其性质5-3 半群（1学时）半群的概念5-4 群与子群（2学时） 群与子群的定义与相关定理5-5 阿贝尔群和循环群（1学时）阿贝尔群和循环群的定义5-6 置换群与伯恩赛德定理（0.5学时）置换群的概念与伯恩赛德定理5-7 陪集与拉格朗日定理（0.5学时

6、）陪集的概念与拉格朗日定理5-8 同态与同构（1学时）同态与同构的基本概念5-9 环与域（1学时）环与域的定义第六章 格和布尔定理（选讲）6-1格的概念6-2 分配格6-3 有补格6-4 布尔代数6-5 布尔表达式第四篇 图论 第七章 图论教学要点：熟练掌握图中的基本概念、图的各种表示方法；理解并掌握欧拉图与汉密尔顿图的定义以及理论，掌握树、生成树、根树的基本概念，能熟练应用计算方法，并能综合应用。教学时数：16学时教学内容：7-1 图的基本概念（2学时）图的基本概念7-2 路与回路（2学时）路与回路的基本概念7-3 图的矩阵表示（2学时）图的表示方法7-4 欧拉图与汉密尔顿图（2学时）欧拉图

7、与汉密尔顿图的概念与理论7-5 平面图（2学时）平面图的定义与判断7-6 对偶图与着色（2学时）对偶图与着色7-7 树与生成树（2学时）树与生成树的基本概念与计算方法7-8 根树及其应用（2学时）根树的定义及其应用第五篇 计算机科学中的应用（选讲 ）第八章 形式语言与自动机8-1 串和语言8-2 形式文法8-3 有限状态自动机8-4 两类自动机转换8-5 有限状态机的简化8-6 有限状态机与正则语言第九章 纠错码初步9-1 通讯模型和纠错的基本概念9-2 线性分组码的纠错能力9-3 海明码9-4 查表译码法 三、参考书目 1、左孝陵，李为 ，刘永才：离散数学，出版社：上海科学与技术出版社，出版时间与版次：1982年九月出