前言

这是北京大学《离散数学基础》的课程笔记，本课程由张昕老师教授。

阅读入口

集合、关系与函数

• 集合
• 二元关系
• 函数
• 初等数论基础及其应用

图论

• 图的基本概念
• 欧拉图与哈密顿图
• 树
• 平面图
• 支配集、覆盖集、独立集、匹配与着色

组合计数与代数结构

• 基本的组合计数公式
• 递推方程与生成函数
• 代数系统
• 群与环
• 格与布尔代数

数理逻辑

• 命题逻辑的基本概念
• 命题逻辑等价运算
• 命题逻辑的推理理论
• 一阶逻辑基本概念
• 一阶逻辑等值演算与推理

形式语言与自动机

• 语言和文法
• 带输出的有限状态机
• 不带输出的有限状态机
• 语言的识别