前置知识

1 学习本课程前需要什么

本课程不要求先学过自动机，但需要能够使用基础离散数学语言。

1.1 1. 集合

需要熟悉：

• 元素与集合：\(x\in A\)；
• 子集：\(A\subseteq B\)；
• 并、交、差；
• 空集合 \(\varnothing\)；
• 集合构造式，例如 \(\{x:P(x)\}\)。

1.2 2. 基本逻辑

需要熟悉：

• “如果……那么……” \(P\Rightarrow Q\)；
• “当且仅当” \(P\iff Q\)；
• 否定 \(\neg P\)；
• 全称量词 \(\forall\) 与存在量词 \(\exists\)。

第 1 章会重新训练证明方式，因此不要求已经非常熟练。

1.3 3. 基本代数

需要能够完成：

• 多项式展开与因式分解；
• 简单不等式变形；
• 求和符号 \(\sum\) 的基础使用；
• 指数运算。

1.4 4. 推荐但不是硬前置

• 离散数学中的图、树、递归；
• 基础算法与数据结构；
• 一门程序设计语言。