Share Description
In this course, you will learn :
离散数学是计算机科学的基础理论，离散结构的基础知识和逻辑思维的形式化是信息技术类学生的基本功，离散数学的基本概念是理科专业学生进行信息类课程学习的重要基础。本课程介绍计算机科学和信息技术理论基础的概念和思想方法，介绍数理逻辑、集合论、图论、抽象代数和形式语言与自动机等各部分的基本概念，介绍离散数学基本概念和空间信息技术之间的联系与结合，培养学生理解和掌握离散数学基本概念，采用形式化方法分析问题，并能自觉运用逻辑分析、结构层次分析和同构类比等思想方法解决问题的能力。
Syllabus :
1. 数理逻辑：基本概念
- 课程介绍
- 正式内容之前：形式化及其极限
- 正式内容之前：悖论、版画、卡农
- 数理逻辑介绍
- 什么是命题
- 排中律
- 命题符号化
- 逻辑联结词
- 命题公式
- 真值函数
- 命题形式化
2. 数理逻辑：命题逻辑及形式系统
- 重言式
- 逻辑等价式和逻辑蕴涵式
- 代入原理和替换原理
- 证明逻辑等价式和逻辑蕴涵式
- 范式及基本术语
- 求范式的一般步骤
- 主范式
- 联结词集完备性
- 形式系统和证明、演绎
- 命题演算形式系统PC
- PC中的定理证明
- 三个元定理
- 定理判定问题
3. 数理逻辑：谓词逻辑及形式系统
- 数理逻辑-个体、谓词和量词
- 数理逻辑-谓词公式
- 数理逻辑-谓词公式永真式
- 数理逻辑-谓词演算形式系统FC
- 数理逻辑-全称引入规则及存在消除规则
- 数理逻辑-自然推理系统
- 数理逻辑-ND中的定理证明
4. 集合论：集合代数
- 集合论与无限1
- 集合基本概念1
- 子集合
- 集合基本运算
- 集合族及运算
- 归纳定义
- 自然数的定义
- 归纳原理
- 数学归纳法
5. 集合论：集合代数
- 有序组
- 笛卡尔积
- 关系定义
- 关系运算
- 关系合成运算
- 关系基本特性
- 关系特性定理
6. 集合论：特殊关系及函数
- 等价关系
- 等价关系与划分
- 划分之间的关系
- 划分运算
- 序关系
- 序关系中的特殊元素
- 函数
- 函数合成
- 特殊函数类
7. 图论：图的基本概念
- 图的定义
- 图的基本概念
- 度和正则图
- 子图与同构图
- 路径与连通性
- 连通性
- 欧拉图与哈密顿图
8. 图论：特殊图
- 图的矩阵表示
- 二分图
- 二分图的匹配
- 平面图
- 树
- 树的应用
9. 抽象代数
- 引言
- 代数结构
- 幺元
- 零元
- 逆元
- 可约元素
- 同构与同态
- 同余关系
- 群环域
10. 形式语言与自动机：基本概念
- 语言及研究方向
- 形式语言
- 短语结构语法
- 语言及语法表示
- 形式语法分类
- 语法分析
- BNF范式
- 语法图
- 正则语法
11. 形式语言与自动机：有限状态机
- 有限状态机
- 状态图
- 泵引理
- 机器同余
- 商机器
- 商机器的性质
- 机器化简
- 带输出的机器
- 程序实现状态机
12. 形式语言与自动机：图灵机与计算理论
- 图灵机
- 图灵机例子
- 图灵机变种
- 识别与判定
- 哥德尔编码
- 通用图灵机
- 停机问题
- 哥德尔不完备定理
- 不可判定问题
