大学理工
离散数学概论mooc（北京大学）
课程目录
- 0.1.1 1 课程简介
- 0.2.1 2 形式化及其极限
- 0.2.2 3 悖论、版画、卡农
- 1.1.1 4 数理逻辑介绍
- 1.1.2 5 什么是命题
- 1.1.3 6 排中律
- 1.1.4 7 命题符号化
- 1.1.5 8 逻辑联结词（上）
- 1.1.6 9 逻辑联结词（下）
- 1.2.1 10 命题公式
- 1.2.2 11 真值函数
- 1.2.3 12 命题形式化
- 3.1.1 13 重言式
- 3.1.2 14 逻辑等价式和逻辑蕴涵式
- 3.1.3 15 代入原理和替换原理
- 3.1.4 16 证明逻辑等价式和逻辑蕴涵式
- 3.2.1 17 范式及基本术语
- 3.2.2 18 求范式的一般步骤
- 3.2.3 19 主范式
- 3.2.4 20 联结词集完备性
- 3.3.1 21 形式系统和证明、演绎
- 3.3.2 22 命题演算形式系统PC
- 3.3.3 23 PC中的定理证明
- 3.3.4 24 三个元定理
- 3.3.5 25 定理判定问题
- 4.1.1 26 数理逻辑-个体、谓词和量词
- 4.1.2 27 数理逻辑-谓词公式
- 4.1.3 28 数理逻辑-谓词公式永真式
- 4.2.1 29 数理逻辑-谓词演算形式系统FC
- 4.2.2 30-数理逻辑-全称引入规则及存在消除规则
- 4.3.1 31-数理逻辑-自然推理系统
- 4.3.2 32-数理逻辑-ND中的定理证明
- 5.1.1 33 集合论与无限
- 5.1.2 34-集合基本概念
- 5.1.3 35-子集合
- 5.1.4 36-集合基本运算
- 5.1.5 37-集合族及运算
- 5.2.1 38-归纳定义
- 5.2.2 39-自然数的定义
- 5.2.3 40-归纳原理
- 5.2.4 41-数学归纳法
- 6.1.1 42 有序组
- 6.1.2 43 笛卡尔积
- 6.1.3 44 关系定义
- 6.2.1 45 关系运算
- 6.2.2 46 关系合成运算
- 6.3.1 47 关系基本特性
- 6.3.2 48 关系特性定理
- 7.1.1 49-等价关系
- 7.1.2 50-等价关系与划分
- 7.1.3 51-划分之间的关系
- 7.1.4 52-划分运算
- 7.1.5 53-序关系
- 7.1.6 54-序关系中的特殊元素
- 7.2.1 55-函数
- 7.2.2 56-函数合成
- 7.2.3 57-特殊函数类
- 8.1.1 58-图的定义
- 8.1.2 59-图的基本概念
- 8.1.3 60-度和正则图
- 8.1.4 61-子图与同构图
- 8.2.1 62-路径与连通性
- 8.2.2 63-连通性
- 8.2.3 64-欧拉图与哈密顿图
- 9.1.1 65-图的矩阵表示
- 9.1.2 66-二分图
- 9.1.3 67-二分图的匹配
- 9.2.1 68-平面图
- 9.2.2 69-树
- 9.2.3 70-树的应用
- 10.1.1 71-引言
- 10.1.2 72-代数结构
- 10.2.1 73-幺元
- 10.2.2 74-零元
- 10.2.3 75-逆元
- 10.2.4 76-可约元素
- 10.3.1 77-同构与同态
- 10.3.2 78-同余关系
- 10.3.3 79-群环域
- 11.1.1 80-语言及研究方向
- 11.1.2 81-形式语言
- 11.1.3 82-短语结构语法
- 11.1.4 83-语言及语法表示
- 11.2.1 84-形式语法分类
- 11.2.2 85-语法分析
- 11.2.3 86-BNF范式
- 11.2.4 87-语法图
- 11.2.5 88-正则语法
- 12.1.1 89-有限状态机
- 12.1.2 90-状态图
- 12.1.3 91-泵引理
- 12.2.1 92-机器同余
- 12.2.2 93-商机器
- 12.2.3 94-商机器的性质
- 12.2.4 95-机器化简
- 12.3.1 96-带输出的机器
- 12.3.2 97-程序实现状态机
- 13.1.1 98-图灵机
- 13.1.2 99-图灵机例子
- 13.1.3 100-图灵机变种
- 13.2.1 101-识别与判定
- 13.2.2 102-哥德尔编码
- 13.2.3 103-通用图灵机
- 13.3.1 104-停机问题
- 13.3.2 105-哥德尔不完备定理
- 13.3.3 106-不可判定问题
课程介绍
课程目标
重点在于让学生理解和掌握基本概念，培养采用形式化方法来分析问题的能力。
使学生能够自觉运用逻辑分析、结构层次分析和同构类比等思想方法来解决问题。
课程内容
数理逻辑：包括基本概念、命题逻辑及形式系统、谓词逻辑及形式系统。
集合论：集合基本概念、集合代数、特殊关系及函数。
图论：图的基本概念、特殊图。
抽象代数：介绍代数结构等相关内容。
形式语言与自动机：基本概念、有限状态机、图灵机与计算理论。
教学特色
注重理论与实践结合：通过精心设计的教学环节，如编程实现算法等实践，加深学生对离散数学相关概念和算法的理解。
线上线下混合式教学：线上慕课学习为学生提供自主学习机会，不受时间和地点限制；线下个人展示环节，学生可向全班展示对知识的理解和应用，促进师生互动。
以实践为导向的 Python 编程：采用离散数学结合 Python 编程的教学思路，通过慕课视频、每周作业、图文作业、教学资料和互动讨论 5 个教学环节，帮助学生应用所学知识解决实际问题。
