加入收藏  || English Version 
 
《离散数学》教学大纲

  发布日期:2015-03-11  浏览量:307


前言

《离散数学》课程是信息与计算科学专业的专业基础课程,也是应用性很强的一门数学课。离散数学是现代数学的一个重要分支,它是以数理逻辑、集合论、关系与函数、代数结构与布尔代数为讲授对象。是理论性较强、应用性较广、集理论性与应用性为一体的学科。

设置本课程的目的是:通过本课程的学习,使学生了解和掌握关于离散数学的基本概念及其相关理论,以现代数学的方法,初步掌握处理离散结构所必须的一些基本数学工具和方法,为后继课程的学习作必要的理论准备。同时也要培养学生抽象思维、逻辑推理,符号演算和慎密概括的能力,从而使学生具有良好的专业理论素质,提高学生分析和解决实际问题的能力。

学习本课程的要求是:(1) 学习数理逻辑最基本的内容,掌握命题逻辑及谓词逻辑的基本概念,掌握命题演算的方法,掌握命题推理及谓词推理的基本理论,并会用推理理论进行逻辑论证。(2) 学习集合论的基本概念及性质,掌握集合运算及证明的基本理论和方法;学习二元关系的概念与性质,掌握等价关系和偏序关系,并使学生从更高层次理解函数。(3) 学习代数系统的基本常识,掌握二元运算的定义和性质,了解代数系统的子代数和积代数、同态与同构等概念,掌握半群、幺半群、群、环、域和格、布尔代数等代数系统的定义及其性质。

先修课程要求数学分析,高等代数

本课程计划90学时,4学分

选用教材方世昌著,离散数学(第二版),西安电子科技大学,1996

教学手段多媒体讲授

考核方法考试

 

 

教学进程安排表

 

周次

 

学时数

 

 

 

 

教学环节

 

备注

1

2

命题, 命题连接词

讲课

 

1

3

命题变元与命题公式,重言式,恒等式

常用的逻辑恒等式

讲课

 

2

2

永真蕴涵式,恒等式和永真蕴涵式的两个性质,代入规则与替换规则

讲课

 

2

3

对偶原理,析取范式和合取范式,最小析取(合取)范式,主析取(合取)范式

讲课

 

3

2

主析取范式的个数,联结词的归约,

讲课

 

3

3

推理规则,常用的推理规则,证明方法

讲课

 

4

2

谓词,量词,量化断言合命题关系

 

讲课

 

4

3

谓词公式,自由变元与约束变元,谓词演算的基本定义,谓词演算的永真公式

讲课

 

5

2

谓词演算的几条规则,谓词演算的推理规则,术语“A(x)y是自由的”的意义

讲课

 

5

3

谓词演算的推理规则举例

讲课与习题课相结合

 

6

2

集合的概念,外延公理,罗素悖论,集合之间的包含关系

讲课

 

6

3

集合上的运算,并,交和差的运算,补运算,并和交的扩展

讲课

 

7

2

环和与环积,幂集合

讲课

 

7

3

集合的归纳的定义,自然数,归纳证明法与应用举例

讲课

 

8

2

集合的笛卡儿乘积,有限与无限集合

讲课

 

8

3

可数集合,基数c

讲课

 

9

2

基数的比较,三岐性定理,无限集合的特性

讲课

 

9

3

基数的无限性和连续统假设

讲课与习题课相结合

 

10

2

关系的概念,二元关系,关系矩阵和关系图

讲课

 

10

3

关系的特性,关系的合成,关系的R

讲课

 

11

2

合成关系的矩阵表达,关系上的闭包运算

讲课

 

11

3

逆关系,关系上的闭包运算

讨论课

 

12

2

偏序集合,拟序集合,线序集合和良序集合

讲课

 

12

3

词典序和标准序,等价关系,划分

讲课

 

13

2

划分的积与和

讲课与习题课相结合

 

13

3

函数的定义,合成函数,归纳定义的函数,偏函数,函数前域的扩大和缩小

讲课

 

14

2

特殊函数类,逆函数与规范映射

讲课与习题课相结合

 

14

3

代数的构成和分类方法,么元和零元,逆元,子代数

讲课

 

15

2

同态与同构概念与基本结论

讲课

 

15

3

同余关系,商代数,积代数

讲课

 

16

2

半群,独异点和它们的子代数,半群同态和独异点同态

讲课

 

16

3

群的定义和性质,置换群和循环群,子群和同态,陪集和拉格朗日定理,正规子群和商群,群的直接乘积和群的图示

讲课

 

17

2

环和域的概况,格的定义与基本性质

讲课与习题课相结合

 

17

3

子格,格同态和格的积代数,几种特殊的格

讲课

 

18

2

布尔代数,子布尔代数,布尔同态,,有限布尔代数的原子表示,布尔函数

讲课

 

18

3

复习

习题课

 

 

 

 

 

 

 

 

 

 

 

第一章  数理逻辑

一、学习目的

通过本章的学习,掌握作为计算机科学一种重要常识表示工具的数理逻辑的理论与方法,能将所研究的对象及其相互关系形式化,并进行简单的逻辑推理,能明辩缪误的推理,区别似是而非的结论。本章计划25学时。

二、课程内容

§1.1  命题

命题的概念,原子命题与复合命题,命题联结词,真值表,命题变元与命题公式。

§1.2  重言式

真值表与逻辑恒等式,永真蕴含式,常用重要逻辑恒等式与永真蕴含式,代入规则,替换规则,对偶原理。

§1.3  范式

析取范式与合取范式,最小析取范式,最小合取范式,主析取范式与主合取范式,主析、合取范式的个数。

§1.4  联结词的扩充与规约

与非,或非,排斥或,全功能联结词集合。

§1.5  推理规则和证明方法

    最常用推理规则,证明方法,P规则,T规则,CP规则,推理证明的表上作业法,推理的其他问题

§1.6  谓词和量词

个体变元与谓词变元,谓词命名式,存在量词与全称量词,论述域,量化断言与命题的关系,量词的辖域,自由变元与约束变元。

§1.7  谓词演算的永真公式

基本定义,谓词公式的基本永真式,含有量词的永真公式概要表,代入规则,替换规则,CP规则,对偶原理。

§1.8  谓词演算的推理规则

全称指定规则US,存在指定规则ES, 全称推广规则UG, 存在推广规则EG,谓词推理证明的表上作业法。

三、教学基本要求

了解:联结词的扩充与归约。

理解:命题符号化的想法,谓词演算的基本想法,谓词与量词、约束变元与自由变元的概念。

掌握:命题及五个联结词的概念,常见的逻辑恒等式。用真值表对命题公式的判定,命题公式的等值演算,主合取范式与主析取范式的表示,常用的推理规则,应用P规则、T规则、CP规则进行形式推理,谓词的等值演算,应用UGUSEGES规则进行谓词演算的形式推理。

三、重点、难点提示和教学手段

(一)本章重点:命题及五个联结词的概念,命题符号化及利用真值表对命题公式的判定,常用的命题等价公式和蕴涵公式,三个扩充联结词和全功能联结词组,主合取范式与主析取范式的表示,应用P规则、T规则、CP规则进行形式推理,谓词与量词、约束变元与自由变元的概念,常用的谓词等价公式和蕴涵公式,应用UGUSEGES规则进行谓词演算的形式推理。

(二)本章难点:命题符号化,命题公式的等值演算,主范式,谓词的等值演算。

(三)教学手段

课堂讲授与习题课相结合

五、思考与练习

每节均有适当的思考题,采取随堂布置方式。

练习题每节10题左右,从教材的习题中挑选。可采用每章讲授之前一次性布置,或每节讲完后再布置。

 

第二章  集合

一、学习目的

通过本章的学习,掌握集合的概念及各种运算,理解有限集合与无限集合的区别,并能用集合的工具描述和解决问题。计划20学时。

二、课程内容

§2.1  集合论基本概念

集合的概念,集合的表示,集合间的包含关系,外延公理。

§2.2  集合上的运算

集合的并、交、差和补运算,上述四种运算的主要性质,并与交运算的扩张,集合的对称差运算,幂集合,有限集的计数。

§2.3  自然数和归纳法

集合归纳的定义,数学归纳法第一原理,数学归纳法第二原理,应用举例。

§2.4  集合的叉积

n重组,二集合的叉积,n重叉积及其运算性质。

§2.5  可数和不可数集合

有限与无限集合,集合基数的一般概念,枚举,可数集合的定义及性质,无限集合的特性,基数c(连续统)

三、教学基本要求

了解:集合的概念,罗素悖论,有限集的计数,可数集合,连续统。

掌握:集合的运算及相关定律,幂集,掌握n元组与笛卡儿积,集合的基数,可数集(包括无限可数集)

四、重点、难点提示和教学手段

(一)本章重点:集合的运算及相关定律,幂集,掌握n元组与笛卡儿积,集合的基数,可数集(包括无限可数集)

(二)本章难点:集合的运算及规律。笛卡儿积,无限可数集合。

(三)教学手段

课堂讲授与习题课相结合

五、思考与练习

每节均有适当的思考题,采取随堂布置方式。

练习题每节10题左右,从教材的习题中挑选。可采用每章讲授之前一次性布置,或每节讲完后再布置。

 

第三章  关系与函数

一、学习目的

通过本章的学习,掌握关系与函数的一般理论及其表示方法,理解关系的各种运算及其性质,特别着重偏序关系和哈斯图的表示、等价关系与等价类的划分,函数作为特殊关系的定义,满、单、双射函数,复合函数和反函数。本章计划22学时。

二、课程内容

§3.1  二元关系基本概念

关系的概念,二元关系,关系的图示与关系矩阵,关系的特性。

§3.2  关系的合成

二元关系的合成,集合上关系的幂,合成关系的矩阵表达。

§3.3  关系上的闭包运算

逆关系,逆关系的性质,关系的三种闭包运算,自反传递闭包。

§3.4  偏序关系

偏序集合的概念,哈斯图,最大()元素,上()界,线序集合,良序集合。

§3.5  等价关系与划分

等价关系的概念,等价类与商集,集合的划分,划分诱导的等价关系与等价关系诱导的划分。

§3.6  函数的基本概念

函数的定义,函数的定义域与值域,合成函数。

§3.7  特殊函数类与逆函数

满射、单射与双射函数,常函数,恒等函数,置换函数,特征函数,逆函数,规范函数。

三、教学基本要求

理解:置换函数的计算。

了解:逆关系,拟序,线序,良序集合,词典序和标准序,特殊函数类。

掌握:关系的各种运算及其性质,特别着重偏序关系和哈斯图的表示、等价关系与等价类的划分,函数作为特殊关系的定义,满、单、双射函数,复合函数和逆函数。关系的基本概念,关系与函数的一般理论及其表示方法,关系的合成,关系的闭包

四、重点、难点提示和教学手段

(一)本章重点:关系的概念及其表示方法,关系的合成与闭包,偏序关系与哈斯图表示,等价关系与等价类的划分,函数的最一般定义、置换函数,合成函数与逆函数。

(二)本章难点:关系的闭包及置换函数计算, 等价关系, 等价类和划分。

(三)教学手段

课堂讲授与习题课相结合

五、思考与练习

每节均有适当的思考题,采取随堂布置方式。

练习题每节10题左右,从教材的习题中挑选。可采用每章讲授之前一次性布置,或每节讲完后再布置。

 

第四章  代数结构

一、学习目的

通过本章的学习,掌握作为近世代数基础的代数结构一般理论,包括:代数运算,二元运算,结合律,交换律,幺元,分配律。半群、子半群及相关结论,独异点,群的概念,有限群,无限群,子群,交换群,循环群,陪集,拉格朗日定理,同构与同态,同态定理等基本概念。计划14学时。

二、课程内容

§4.1  代数结构

代数系统的构成,载体,运算,和代数常数,代数系统的分类方法,幺元与零元,逆元及其相关性质。

§4.2  代数结构

子代数的定义与性质,代数运算的封闭性。

§4.3   代数同态与代数同构

代数同态的概念,代数同构的概念,满同态、单一同态,自同态,自同构,代数同态基本定理。

§4.4 同余关系

同余关系的概念,同余类,同余的相关定理。

§4.5  代数与积代数

商代数的概念,商代数的基本定理,自然同态,积代数的概念。

§4.5  半群与独异点

半群、独异点,子半群,子独异点,可交换半群,可交换独异点,循环独异点,生成子半群,生成元集,半群同态,独异点同态,商半群,商独异点,半群的积代数。

§4.6  群与子群

群的定义与性质,有限群,可交换群,置换群与循环群,生成元,子群与群同态,陪集与拉格朗日定理,正规子群与商群,群的直接积与群的图示。

§4.7  环与域

环与域的定义与举例,子环与理想。

三、教学基本要求

了解:环和域基本概念域相关定理。商环概念。

掌握:同余关系,代数运算,二元运算,结合律,交换律,幺元,分配律。半群、子半群及相关结论,独异点,群的概念,有限群,无限群,子群,交换群,循环群,陪集,拉格朗日定理,同构与同态,同态定理等基本概念。

 

四、重点、难点提示和教学手段

(一)本章重点:代数结构的基本概念,子代数,代数结构的同态与同构,半群与独异点,循环半群,群的基本性质、子群及其陪集

(二)本章难点:理解各种抽象概念的实质含义及其基本性质与计算。特别是:代数结构的同态与同构;商结构等

(三)教学手段

课堂讲授与习题课相结合

五、思考与练习

每节均有适当的思考题,采取随堂布置方式。

练习题每节10题左右,从教材的习题中挑选。可采用每章讲授之前一次性布置,或每节讲完后再布置。

 

第五章  格与布尔代数

一、学习目的

通过本章的学习,掌握格的概念,包括:格的两种等价定义,格的基本定理,分配格,有限格,有补格;掌握布尔表达式与布尔代数的概念。计划6学时。

二、课程内容

§4.1  格的概念

格的基本概念,格的对偶原理与基本性质。

§4.2  格是代数结构

格的另一种等价定义,子格,格同态与格代数,格的同态,积代数。

§4.3  特殊的格

分配格,有界格,有补格,有补分配格及其性质。

§4.4  布尔代数

布尔代数的定义,子布尔代数,布尔同态,布尔代数的积代数,布尔函数,布尔函数的重要应用。

三、教学基本要求

了解:格的对偶性原理与基本性质,布尔代数的应用。

理解: 格的定义,布尔代数的概念及其相关理论。

掌握:几种特殊的格,分配格,有界格,有补格,有补分配格及其性质。从代数角度理解格的定义与性质。

四、重点、难点提示和教学手段

(一)本章重点:格的定义与性质,有界格、有补格、分配格的含义,布尔代数的概念及其相关理论。

(二)本章难点:从偏序集和从代数的角度来理解格的定义与性质;从有补分配格的的角度来理解布尔代数的定义与性质。

(三)教学手段

课堂讲授与习题课相结合

五、思考与练习

每节均有适当的思考题,采取随堂布置方式。

练习题每节10题左右,从教材的习题中挑选。可采用每章讲授之前一次性布置,或每节讲完后布置。

 

阅读书目(或参考文献)

[1] 《离散数学》,李盘林等编著,高等教育出版社。

[2] 《离散数学及其应用》,Kenneth H. Rosen 原著,袁崇义等译,机械工业出版社。

[3] 《离散数学》,耿素云等编著,高等教育出版社。

[4] 《离散数学》,左孝凌等著,上海科技文献出版社。

 

打印此页】【顶部】【关闭
   
版权所有 2019 澳门赌搏网站大全 All rights reserved 皖ICP备05018241号
地址:安徽省合肥市九龙路111号澳门新莆京娱乐网站磬苑校区理工楼H楼 邮编:230601 E-mail:math@ahu.edu.cn
访问统计:自2013年9月1日以来总访问:1000  后台管理


XML 地图 | Sitemap 地图