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$。

命题逻辑

命题

能判断对错指代清楚的叫命题。例如：

  • 今天会下雨
  • 根号三是无理数

逻辑符号

  1. 合取：记作 $q \land p$，只有两个都为真，结果才为真。
  2. 析取：记作 $q \lor p$，两个只要有一个真，结果就为真。
  3. 否定：记作 $\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

  1. 蕴含式：$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 (\forall x P(x))\equiv \exists x \lnot P(x)$

$\lnot (\exists x P(x))\equiv \forall x \lnot P(x)$

下面还有更复杂一些的：