UCB CS70: discrete Math and probability theory
集合的复习以及数学标记
集合
集合可以包含任何东西，包括集合，任何元素。如过元素 \(x\) 在集合 \(A\) 中，那么记作 \(x \in A\)。如果 \(y\) 不属于 \(A\) 中，那么记作 \(y \notin A\)。
集合的基本属性：
- 集合中不存在顺序
- 如果\(A,B\)两个集合相等，那么记作
\(A = B\)
基数(Cardinality)
集合中的元素的个数，记作基数，比如 \(A = \{1,2,2,4\}\)，基数为 4，记作 \(\mid A\mid=4\).
如果基数为0，那么被称为空集，记作 \(\emptyset\)。
集合的基本运算
并运算
设 \(A,B\) 为两个集合，则由集合 \(A\) 和集合 \(B\) 中的所有元素汇集而成的集合称为集合 \(A\) 和集合 \(B\) 的 并。记作 \(A \cup B\)。即：
\(A \cup B = \{x \mid x\in A \vee x \in B\}\)
基本推理：
- \(A \cup B = B \cup A\)
- \(A \cup \emptyset = A\)
交运算
设 \(A,B\) 为两个集合，则由集合 \(A\) 和集合 \(B\) 中的公共元素汇集而成的集合称为集合 \(A\) 和集合 \(B\) 的 并。记作 \(A \cap B\)。即：
\(A \cap B=\{x \mid x\in A \wedge x \in B\}\)
基本推论： * \(A \cap B = B \cap A\) * \(A \cap \emptyset = \emptyset\)
差运算
设 \(A,B\) 为两个集合，则由属于集合 \(A\) 但不属于集合 \(B\) 的所有元素汇集的集合称为集合 \(A\) 与集合 \(B\) 的差。记作 \(A\backslash B\) 或 \(A − B\)。即：
\(A\backslash B= \{x \in A \mid x \notin B\}\)
基本推论： * \(A \backslash B = \emptyset\) * \(A \backslash \emptyset = A\) * \(\emptyset \backslash A = \emptyset\)
基本集合标记
- \(\mathbb{N}\) 表示所有自然数的数集
- \(\mathbb{Z}\) 表示所有整数的数集
- \(\mathbb{Q}\) 表示所有有理数：\(\{\frac{a}{b} \mid a,b \in \mathbb{Z},b \neq 0\}\)
- \(\mathbb{R}\) 表示所有实数集
- \(\mathbb{C}\) 表示所有复数集
笛卡尔积（Cartesian product）
笛卡尔积，记作 \(A \times B\)，表示两个集合中的 元素的有序对，即：
\(A \times B = \{(a,b) \mid a \in A,b \in B\}\)
幂集
幂集，就是原集合中所有的子集（包括全集和空集）构成的集。
\(S: \{T | T \subseteq S\}\)
举个栗子，如果 \(S = \{1,2,3\}\), \(S\)的幂集: \(P(S) = \{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}\)。
如果 \(\mid S \mid = k\)，那么 \(\mid P(S) \mid = 2^k\)。
命题逻辑
命题
能判断对错指代清楚的叫命题。例如： * 今天会下雨 * 根号三是无理数
逻辑符号
- 合取：记作 \(q \land p\)，只有两个都为真，结果才为真。
- 析取：记作 \(q \lor p\)，两个只要有一个真，结果就为真。
- 否定：记作 \(\lnot p\)，p 的否定，非 p。
永真式：表示无论变量如何，永远为真的式子。例如：\(P \lor \lnot Q\)
矛盾式：表示无论变量如何，永远为假的式子。例如：\(P \land \lnot Q\)
| \(P\) | \(Q\) | \(P \land Q\) | \(P \lor Q\) | \(\lnot P\) |
|---|---|---|---|---|
| T | T | T | T | F |
| T | F | F | T | F |
| F | T | F | T | T |
| F | F | F | F | T |
蕴含式：\(P \implies Q\)（P 蕴含 Q），若 \(P\) 为真，则 \(Q\) 为真。
- 简单关系：\((P \implies Q) \equiv (\lnot P \lor Q)\)。
- 如果 \(P \implies Q\) 和 \(Q \implies P\) 都为真，记作 \(P \iff Q\)，等价号。
已知 \(P \implies Q\)，我们可以定义： * 逆否命题为真：\(\lnot Q \implies \lnot P\) * 逆命题：\(Q \implies P\)
| \(P\) | \(Q\) | \(\lnot P\) | \(\lnot Q\) | \(P \implies Q\) | \(Q \implies P\) | \(\lnot Q \implies \lnot P\) | \(P \iff Q\) |
|---|---|---|---|---|---|---|---|
| T | T | F | F | T | T | T | T |
| T | F | F | T | F | T | F | F |
| F | T | T | F | T | F | T | F |
| F | F | T | T | T | T | T | T |
量词
全称量词：全称量词表示命题对所有元素都成立，通常用符号 \(\forall\) 表示。
存在量词：存在量词表示命题对至少一个元素成立，通常用符号 \(\exists\) 表示。
我们从高中用到大学，不再赘述了。
处理否定的一些定律
德摩根定律
\[\lnot (P \land Q) \equiv (\lnot P \lor \lnot Q)\] \[\lnot (P \lor Q) \equiv (\lnot P \land \lnot Q)\]
有关量词的一些定律
\(\lnot (\forall x P(x))\equiv \exists x \lnot P(x)\)
\(\lnot (\exists x P(x))\equiv \forall x \lnot P(x)\)
下面还有更复杂一些的：
\[\lnot (\forall x \exists y P(x,y)) \equiv \exists x \lnot(\exists y P(x,y)) \equiv \exists x \forall y \lnot P(x,y)\]
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！