《离散数学》教学大纲

1、 离散数学教学大纲前言离散数学课程是信息与计算科学专业的专业基础课程，也是应用性很强的一门数学课。离散数学是现代数学的一个重要分支，它是以数理逻辑、集合论、关系与函数、代数结构与布尔代数为讲授对象。是理论性较强、应用性较广、集理论性与应用性为一体的学科。设置本课程的目的是：通过本课程的学习，使学生了解和掌握关于离散数学的基本概念及其相关理论，以现代数学的方法，初步掌握处理离散结构所必须的一些基本数学工具和方法，为后继课程的学习作必要的理论准备。同时也要培养学生抽象思维、逻辑推理，符号演算和慎密概括的能力，从而使学生具有良好的专业理论素质，提高学生分析和解决实际问题的能力。学习本课程的要求是：(

2、1)学习数理逻辑最基本的内容，掌握命题逻辑及谓词逻辑的基本概念，掌握命题演算的方法，掌握命题推理及谓词推理的基本理论，并会用推理理论进行逻辑论证。(2)学习集合论的基本概念及性质，掌握集合运算及证明的基本理论和方法；学习二元关系的概念与性质，掌握等价关系和偏序关系，并使学生从更高层次理解函数。(3)学习代数系统的基本知识，掌握二元运算的定义和性质，了解代数系统的子代数和积代数、同态与同构等概念，掌握半群、幺半群、群、环、域和格、布尔代数等代数系统的定义及其性质。先修课程要求：数学分析，高等代数本课程计划90学时，4学分选用教材：方世昌著，离散数学(第二版)，西安电子科技大学，1996教学手段：

3、多媒体讲授考核方法：考试教学进程安排表周次学时数教学主要内容教学环节备注12命题，命题连接词讲课13命题变元与命题公式，重言式，恒等式常用的逻辑恒等式讲课22永真蕴涵式，恒等式和永真蕴涵式的两个性质，代入规则与替换规则讲课23对偶原理，析取范式和合取范式，最小析取(合取)范式，主析取(合取)范式讲课32主析取范式的个数，联结词的归约，讲课33推理规则，常用的推理规则，证明方法讲课42谓词，量词，量化断言合命题关系讲课43谓词公式，自由变元与约束变元，谓词演算的基本定义，谓词演算的永真公式讲课52谓词演算的几条规则，谓词演算的推理规则，术语“A(x)对y是自由的”的意义讲课53谓词演算的推理规则

4、举例讲课与习题课相结合62集合的概念，外延公理，罗素悖论，集合之间的包含关系讲课63集合上的运算，并，交和差的运算，补运算，并和交的扩展讲课72环和与环积，幂集合讲课73集合的归纳的定义，自然数，归纳证明法与应用举例讲课82集合的笛卡儿乘积，有限与无限集合讲课83可数集合，基数c讲课92基数的比较，三岐性定理，无限集合的特性讲课93基数的无限性和连续统假设讲课与习题课相结合102关系的概念，二元关系，关系矩阵和关系图讲课103关系的特性，关系的合成，关系的R幂讲课112合成关系的矩阵表达，关系上的闭包运算讲课113逆关系，关系上的闭包运算讨论课122偏序集合，拟序集合，线序集合和良序集合讲课1

5、23词典序和标准序，等价关系，划分讲课132划分的积与和讲课与习题课相结合133函数的定义，合成函数，归纳定义的函数，偏函数，函数前域的扩大和缩小讲课142特殊函数类，逆函数与规范映射讲课与习题课相结合143代数的构成和分类方法，么元和零元，逆元，子代数讲课152同态与同构概念与基本结论讲课153同余关系，商代数，积代数讲课162半群，独异点和它们的子代数，半群同态和独异点同态讲课163群的定义和性质，置换群和循环群，子群和同态，陪集和拉格朗日定理，正规子群和商群，群的直接乘积和群的图示讲课172环和域的简介，格的定义与基本性质讲课与习题课相结合173子格，格同态和格的积代数，几种特殊的格讲课

6、182布尔代数，子布尔代数，布尔同态，有限布尔代数的原子表示，布尔函数讲课183复习习题课第一章数理逻辑一、学习目的通过本章的学习，掌握作为计算机科学一种重要知识表示工具的数理逻辑的理论与方法，能将所研究的对象及其相互关系形式化，并进行简单的逻辑推理，能明辩缪误的推理，区别似是而非的结论。本章计划25学时。二、课程内容1.1命题命题的概念，原子命题与复合命题，命题联结词，真值表，命题变元与命题公式。1.2重言式真值表与逻辑恒等式，永真蕴含式，常用重要逻辑恒等式与永真蕴含式，代入规则，替换规则，对偶原理。1.3范式析取范式与合取范式，最小析取范式，最小合取范式，主析取范式与主合取范式，主析、合取

7、范式的个数。1.4联结词的扩充与规约与非，或非，排斥或，全功能联结词集合。1.5推理规则和证明方法最常用推理规则，证明方法，P规则，T规则，CP规则，推理证明的表上作业法，推理的其他问题。1.6谓词和量词个体变元与谓词变元，谓词命名式，存在量词与全称量词，论述域，量化断言与命题的关系，量词的辖域，自由变元与约束变元。1.7谓词演算的永真公式基本定义，谓词公式的基本永真式，含有量词的永真公式概要表，代入规则，替换规则，CP规则，对偶原理。1.8谓词演算的推理规则全称指定规则US，存在指定规则ES,全称推广规则UG,存在推广规则EG，谓词推理证明的表上作业法。三、教学基本要求了解：联结词的扩充与归

8、约。理解：命题符号化的想法，谓词演算的基本想法，谓词与量词、约束变元与自由变元的概念。掌握：命题及五个联结词的概念，常见的逻辑恒等式。用真值表对命题公式的判定，命题公式的等值演算，主合取范式与主析取范式的表示，常用的推理规则，应用P规则、T规则、CP规则进行形式推理，谓词的等值演算，应用UG、US、EG、ES规则进行谓词演算的形式推理。三、重点、难点提示和教学手段（一）本章重点：命题及五个联结词的概念，命题符号化及利用真值表对命题公式的判定，常用的命题等价公式和蕴涵公式，三个扩充联结词和全功能联结词组，主合取范式与主析取范式的表示，应用P规则、T规则、CP规则进行形式推理，谓词与量词、约束变元

9、与自由变元的概念，常用的谓词等价公式和蕴涵公式，应用UG、US、EG、ES规则进行谓词演算的形式推理。（二）本章难点：命题符号化，命题公式的等值演算，主范式，谓词的等值演算。（三）教学手段课堂讲授与习题课相结合五、思考与练习每节均有适当的思考题，采取随堂布置方式。练习题每节10题左右，从教材的习题中挑选。可采用每章讲授之前一次性布置，或每节讲完后再布置。第二章集合一、学习目的通过本章的学习，掌握集合的概念及各种运算，理解有限集合与无限集合的区别，并能用集合的工具描述和解决问题。计划20学时。二、课程内容2.1集合论基本概念集合的概念，集合的表示，集合间的包含关系，外延公理。2.2集合上的运算集

10、合的并、交、差和补运算，上述四种运算的主要性质，并与交运算的扩张，集合的对称差运算，幂集合，有限集的计数。2.3自然数和归纳法集合归纳的定义，数学归纳法第一原理，数学归纳法第二原理，应用举例。2.4集合的叉积n重组，二集合的叉积，n重叉积及其运算性质。2.5可数和不可数集合有限与无限集合，集合基数的一般概念，枚举，可数集合的定义及性质，无限集合的特性，基数c(连续统)。三、教学基本要求了解：集合的概念，罗素悖论，有限集的计数，可数集合，连续统。掌握：集合的运算及相关定律，幂集，掌握n元组与笛卡儿积，集合的基数，可数集(包括无限可数集)。四、重点、难点提示和教学手段（一）本章重点：集合的运算及相

11、关定律，幂集，掌握n元组与笛卡儿积，集合的基数，可数集(包括无限可数集)。（二）本章难点：集合的运算及规律。笛卡儿积，无限可数集合。（三）教学手段课堂讲授与习题课相结合五、思考与练习每节均有适当的思考题，采取随堂布置方式。练习题每节10题左右，从教材的习题中挑选。可采用每章讲授之前一次性布置，或每节讲完后再布置。第三章关系与函数一、学习目的通过本章的学习，掌握关系与函数的一般理论及其表示方法，理解关系的各种运算及其性质，特别着重偏序关系和哈斯图的表示、等价关系与等价类的划分，函数作为特殊关系的定义，满、单、双射函数，复合函数和反函数。本章计划22学时。二、课程内容3.1二元关系基本概念关系的概

12、念，二元关系，关系的图示与关系矩阵，关系的特性。3.2关系的合成二元关系的合成，集合上关系的幂，合成关系的矩阵表达。3.3关系上的闭包运算逆关系，逆关系的性质，关系的三种闭包运算，自反传递闭包。3.4偏序关系偏序集合的概念，哈斯图，最大(小)元素，上(下)界，线序集合，良序集合。3.5等价关系与划分等价关系的概念，等价类与商集，集合的划分，划分诱导的等价关系与等价关系诱导的划分。3.6函数的基本概念函数的定义，函数的定义域与值域，合成函数。3.7特殊函数类与逆函数满射、单射与双射函数，常函数，恒等函数，置换函数，特征函数，逆函数，规范函数。三、教学基本要求理解：置换函数的计算。了解：逆关系，拟

13、序，线序，良序集合，词典序和标准序，特殊函数类。掌握：关系的各种运算及其性质，特别着重偏序关系和哈斯图的表示、等价关系与等价类的划分，函数作为特殊关系的定义，满、单、双射函数，复合函数和逆函数。关系的基本概念，关系与函数的一般理论及其表示方法，关系的合成，关系的闭包四、重点、难点提示和教学手段（一）本章重点：关系的概念及其表示方法，关系的合成与闭包，偏序关系与哈斯图表示，等价关系与等价类的划分，函数的最一般定义、置换函数，合成函数与逆函数。（二）本章难点：关系的闭包及置换函数计算,等价关系,等价类和划分。（三）教学手段课堂讲授与习题课相结合五、思考与练习每节均有适当的思考题，采取随堂布置方式。

14、练习题每节10题左右，从教材的习题中挑选。可采用每章讲授之前一次性布置，或每节讲完后再布置。第四章代数结构一、学习目的通过本章的学习，掌握作为近世代数基础的代数结构一般理论，包括：代数运算，二元运算，结合律，交换律，幺元，分配律。半群、子半群及相关结论，独异点，群的概念，有限群，无限群，子群，交换群，循环群，陪集，拉格朗日定理，同构与同态，同态定理等基本概念。计划14学时。二、课程内容4.1代数结构代数系统的构成，载体，运算，和代数常数，代数系统的分类方法，幺元与零元，逆元及其相关性质。4.2子代数结构子代数的定义与性质，代数运算的封闭性。4.3代数同态与代数同构代数同态的概念，代数同构的概念

15、，满同态、单一同态，自同态，自同构，代数同态基本定理。4.4同余关系同余关系的概念，同余类，同余的相关定理。4.5商代数与积代数商代数的概念，商代数的基本定理，自然同态，积代数的概念。4.5半群与独异点半群、独异点，子半群，子独异点，可交换半群，可交换独异点，循环独异点，生成子半群，生成元集，半群同态，独异点同态，商半群，商独异点，半群的积代数。4.6群与子群群的定义与性质，有限群，可交换群，置换群与循环群，生成元，子群与群同态，陪集与拉格朗日定理，正规子群与商群，群的直接积与群的图示。4.7环与域环与域的定义与举例，子环与理想。三、教学基本要求了解：环和域基本概念域相关定理。商环概念。掌握：

16、同余关系，代数运算，二元运算，结合律，交换律，幺元，分配律。半群、子半群及相关结论，独异点，群的概念，有限群，无限群，子群，交换群，循环群，陪集，拉格朗日定理，同构与同态，同态定理等基本概念。四、重点、难点提示和教学手段（一）本章重点：代数结构的基本概念，子代数，代数结构的同态与同构，半群与独异点，循环半群，群的基本性质、子群及其陪集（二）本章难点：理解各种抽象概念的实质含义及其基本性质与计算。特别是：代数结构的同态与同构；商结构等（三）教学手段课堂讲授与习题课相结合五、思考与练习每节均有适当的思考题，采取随堂布置方式。练习题每节10题左右，从教材的习题中挑选。可采用每章讲授之前一次性布置，或

17、每节讲完后再布置。第五章格与布尔代数一、学习目的通过本章的学习，掌握格的概念，包括：格的两种等价定义，格的基本定理，分配格，有限格，有补格；掌握布尔表达式与布尔代数的概念。计划6学时。二、课程内容4.1格的概念格的基本概念，格的对偶原理与基本性质。4.2格是代数结构格的另一种等价定义，子格，格同态与格代数，格的同态，积代数。4.3特殊的格分配格，有界格，有补格，有补分配格及其性质。4.4布尔代数布尔代数的定义，子布尔代数，布尔同态，布尔代数的积代数，布尔函数，布尔函数的重要应用。三、教学基本要求了解：格的对偶性原理与基本性质，布尔代数的应用。理解： 格的定义，布尔代数的概念及其相关理论。掌握：几种特殊的格，分配格，有界格，有补格，有补分配格及其性质。从代数角度理解格的定义与性质。四、重点、难点提示和教学手段（一）本章重点：格的定义与性质，有界格、有补格、分配格的含义，布尔代