目录

第1章绪论

1.1离散数学的研究对象

1.2连续量的数字化

1.2.1图像的数字化

1.2.2语音的数字化

1.3离散数学在信息技术中的应用

1.3.1离散数学与关系数据库

1.3.2形式语言与编译系统

1.3.3数理逻辑与程序设计语言

1.3.4代数系统与密码学

1.3.5代数系统与程序语义

1.3.6印刷电路板布线问题

1.4本课程的特点和学习方法

1.5本章小结

1.6习题

第2章集合理论

2.1集合理论的发展历史

2.2集合的定义和运算

2.2.1集合的基本概念

2.2.2集合上的基本运算

2.3关系及其性质

2.3.1序对和笛卡儿积

2.3.2二元关系

2.3.3关系的运算

2.3.4关系的性质

2.3.5关系的闭包运算

2.4等价关系与集合的划分

2.4.1等价关系与等价类

2.4.2集合的划分

2.5序关系

2.5.1偏序关系的定义

2.5.2偏序集的哈斯图

2.6函数

2.6.1函数的定义

2.6.2逆函数与复合函数

2.7集合理论在计算机科学中的应用

2.7.1集合理论在关系数据库理论中的应用：关系代数

2.7.2集合理论在机器学习中的应用：粗糙集理论

2.8实践内容：集合上的运算

2.8.1编程实现集合的交、并和差运算

2.8.2二元关系性质的验证

2.9本章小结

2.10习题

第3章数理逻辑

3.1数理逻辑的发展历史

3.2命题逻辑

3.2.1命题演算的基本概念

3.2.2命题逻辑的合式公式及范式

3.2.3命题逻辑的推理理论

3.3谓词逻辑

3.3.1谓词逻辑的基本概念

3.3.2谓词逻辑的合式公式

3.3.3谓词形式系统的语义

3.3.4谓词演算的等值式

3.3.5前束范式

3.4数理逻辑在人工智能中的应用

3.4.1定理自动证明

3.4.2逻辑式程序设计语言Prolog运行机理

3.5实践内容：命题公式可满足性验证

3.5.1SAT基础知识

3.5.2SAT的求解算法

3.5.3变量和子句的存储方法

3.6本章小结

3.7习题

第4章图论及其应用

4.1图论的发展历史

4.2图的基本概念

4.2.1无向图及有向图

4.2.2相邻和度

4.2.3子图

4.2.4通路与连通性

4.3图的矩阵表示

4.3.1关联矩阵

4.3.2邻接矩阵

4.3.3可达矩阵

4.4欧拉图与哈密顿图

4.4.1欧拉图

4.4.2哈密顿图

4.5平面图与平面化算法

4.5.1平面图

4.5.2平面化算法

4.6带权图与生成树

4.6.1带权图

4.6.2树与生成树

4.7根树及最优二叉树

4.7.1根树

4.7.2最优二叉树

4.7.3最优前缀编码

4.8实践内容：用最优前缀编码压缩文件

4.9本章小结

4.10习题

第5章代数系统

5.1代数学的发展历史

5.2代数系统的基本概念、运算与性质

5.2.1二元运算

5.2.2代数系统的基本概念及性质

5.3半群、群与子群

5.3.1半群与含幺半群

5.3.2群与子群

5.3.3阿贝尔群

5.3.4循环群

5.3.5置换群

5.4同态、同构

5.4.1同态与同构的概念及性质

5.4.2同余

5.5环、域、格和布尔代数

5.5.1环

5.5.2域

5.5.3格

5.5.4布尔代数

5.5.5一元多项式环

5.6数据类型的代数规格说明

5.6.1代数系统的规格说明

5.6.2数据类型的代数规格说明

5.6.3SPEC-代数

5.7代数系统与密码学

5.7.1AES方法的总体结构

5.7.2数学基础

5.7.3AES的基本变换

5.7.4圈密钥生成

5.7.5AES的加密算法

5.7.6AES的基本逆变换

5.8实践内容：代数系统的实现

5.8.1面向对象的程序设计与代数系统

5.8.2代数系统的面向对象实现

5.9本章小结

5.10习题

第6章形式语言与自动机理论

6.1形式语言发展的历史

6.2形式语言理论

6.2.1语言的表示

6.2.2文法：语言的有限描述

6.2.3文法的乔姆斯基体系

6.2.4正规表达式

6.3自动机理论

6.3.1有限自动机

6.3.2下推自动机

6.3.3图灵机

6.3.4通用图灵机

6.4实践内容：词法分析器的设计

6.4.1目标语言的定义

6.4.2程序实现

6.5本章小结

6.6习题

第7章递归理论及其应用

7.1递归与计算

7.1.1递归、归纳和迭代

7.1.2可计算的含义

7.1.3递归理论的发展历史

7.2递归函数理论

7.2.1构造函数的方法

7.2.2递归函数

7.3递归与程序设计

7.4递归式求解

7.4.1递归关系的建立

7.4.2常系数齐次线性递归方程

7.4.3常系数非齐次线性递归方程

7.4.4迭代法

7.4.5归纳法

7.4.6母函数法

7.5实践内容：用堆栈模拟递归

7.5.1斐波那契数列问题的递归和迭代的比较

7.5.2用堆栈模拟递归

7.6本章小结

7.7习题

第8章组合理论初步

8.1组合理论简介

8.2排列、组合与二项式定理

8.2.1基本计数原理

8.2.2排列与组合

8.2.3多重集的排列组合

8.2.4二项式定理

8.3排列组合生成算法

8.3.1生成排列

8.3.2生成组合

8.4鸽巢原理

8.4.1第一抽屉原理

8.4.2鸽巢原理的加强形式

8.4.3Ramsey数及其在信息技术中的应用

8.5组合设计

8.5.1区组设计

8.5.2拉丁方设计

8.6本章小结

8.7习题

参考文献