《离散数学及其应用》第二章·基本结构 学习笔记
一、集合
- 关于集合的常见符号:
符号 | 含义 |
---|---|
N | 自然数集 |
Z | 整数集 |
$Z^+$ | 正整数集 |
Q | 有理数集 |
R | 实数集 |
$R^+$ | 正实数集 |
C | 复数集 |
子集:
证明 A 是 B 子集的方法:如果 x 属于 A,则 x 也属于 B。
证明 A 不是 B 子集的方法:找到一个 x 属于 A,使得 x 不属于 B。
幂集:
集合 S 的幂集是集合 S 所有子集的集合。
集合 {$\emptyset$} 有两个子集:$\emptyset$ 和 {$\emptyset$} 本身。
有序 n 元组:
有序 n 元组 ($a_1$,$a_2$,…,$a_n$) 是以 $a_1$ 为第一个元素,$a_2$ 为第二个元素,…,$a_n$ 为第 n 个元素的有序聚集。
特别地,有序二元组称为序偶。
笛卡尔积:
集合 A 和集合 B 的笛卡尔积,记作 A $\times$ B ,是所有序偶 (a,b) 的集合
例如:集合 A = {1,2},集合 B = {a,b,c}。则 A $\times$ B = {(1,a), (1,b),(1,c),(2,a),(2,b),(2,c)}
笛卡尔积 A $\times$ B 的一个子集 R,称为从集合 A 到 集合 B 的一个关系。其中 R 是序偶,第一个元素属于集合 A,第二个元素属于 B。
集合运算:
符号 | 含义 | 举例 |
---|---|---|
$\bigcup$ | 并集 | A = {1,2,3} B = {2,3,4} A $\bigcup$ B = {1,2,3,4} |
$\bigcap$ | 交集 | A = {1,2,3} B = {2,3,4} A $\bigcap$ B = {2,3} |
\ 或 — | 差集 | A = {1,2,3} B = {2,3,4} A - B = A \ B = {1} |
$\overline A$ | 补集 | 令全集 U = {1,2,3,4} A = {1,2,3} $\overline A$ = {4} |
- 集合恒等式
名称 | 恒等式 | 理解 |
---|---|---|
恒等律 | $A \bigcap U = A$ $A \bigcup \emptyset = A$ |
集合和全集的交集仍是集合本身 集合和空集的并集仍是集合本身 |
支配律 | $A \bigcup U = U$ $A \bigcap \emptyset = \emptyset$ |
集合和全集的并集是全集 集合和空集的交集是空集 |
幂等律 | $A \bigcup A = A$ $A \bigcap A = A$ |
集合做交集或并集的幂运算仍为集合本身 |
补律 | $\overline {(\overline A)} = A$ | 对集合做两次求补运算仍为集合本身 |
交换律 | $A \bigcup B = B \bigcup A$ $A \bigcap B = B \bigcap A$ |
交集并集运算满足交换律 |
结合律 | $A \bigcup (B \bigcup C) = (A \bigcup B) \bigcup C$ $A \bigcap (B \bigcap C) = (A \bigcap B) \bigcap C$ |
交集并集运算满足结合律 |
分配律 | $A \bigcup (B \bigcap C) = (A \bigcup B) \bigcap (A \bigcup C)$ $A \bigcap (B \bigcup C) = (A \bigcap B) \bigcup (A \bigcap C)$ |
交集并集运算满足分配律 |
德·摩根定律 | $\overline{A \bigcap B} = \overline A \bigcup \overline B$ $\overline{A \bigcup B} = \overline A \bigcap \overline B$ |
可将求补运算分散到每个论元,并交换交集并集运算 |
吸收律 | $A \bigcup (A \bigcap B) = A$ $A \bigcap (A \bigcup B) = A$ |
A 并 (A 和 B 的交集) 为 A A 交 (A 和 B 的并集) 为 A |
互补律 | $A \bigcup \overline A = U$ $A \bigcap \overline A = \emptyset$ |
A 并 A 的补集为全集 A 交 A 的补集为空集 |
无限集:
可数集合:一个集合 或者 有限集 或者 与自然数具有相同的基数
如何证明一个集合是可数的:给出这个集合和正整数集合之间一一对应的函数。
不可数集合:与可数集合相反(例如,实数集是不可数的)
定理1:如果 A 和 B 是可数集合,则 $A \bigcup B$ 也是可数的。
定理2:如果存在一对一函数 f 从 A 到 B,和 g 从 B到 A,则存在 A 和 B 之间的一一对应函数。
定理3(康托定理):一个集合的基数总是小于其幂集的基数。
二、函数
在离散数学中,函数用于定义像序列和字符串这样的离散结构,写作:$f:A \rightarrow B$。
我们定义 A 为它的定义域(domain),B 为它的陪域(codomain)。我们也可称 函数f 把 A 映射到 B。
一对一函数(单射函数):当且仅当对于 f 的定义域中所有 a 和 b 有 f(a) = f(b)。
量词表达:$\forall a \forall b (f(a) = f(b) \rightarrow a = b)$
严格递增和严格递减函数必然是一对一函数。
映上函数(满射函数):当且仅当对每个 b $\in$ B 有元素 a $\in$ A 使得 f(a) = b。
双射函数:函数既是一对一函数也是映上函数,则称为双射函数。
反函数:如定义函数 f 为从集合 A 到 集合 B 的映射,则 f 的反函数(记作 $f^{-1}$)为集合 B 到集合 A 的映射。
如果函数不是一一对应关系函数(既是一对一函数又是映上函数),则无法定义反函数 。
我们也将一一对应关系称为可逆关系。
函数的合成:令 g 为从集合 A 到集合 B 的函数。 f 是从集合 B 到集合 C 的函数,函数 f 和 g 的合成,记作 f $\circ$ g。
定义对 $\forall a \in A,(f \circ g)(a) = f(g(a))$
注意:$f \circ g$ 除非特殊定义,则 g 的值域是 f 的定义域。
函数的图:A $\times$ B 的序偶集合
函数 f 的图像是序偶集合 ${(a,b) | a \in A 且 f(a) = b}$
部分函数 和 全函数:
部分函数:如定义从一个集合 A 到 集合 B 的部分函数 f ,是将 A 的一个子集映射到 B。
全函数:如定义从一个集合 A 到 集合 B 的全函数 f ,是将 **A **映射到 B。
三、序列
序列是一种用来表示序列表的离散结构。
- 迭代
- 正向替换:从初始条件出发,直到 $a_n$
- 反向替换:从 $a_n$ 出发,到所有项可以用 $a_1$ 表示
四、求和
求和记号:$\sum $,其中 $\sum_{j = m}^n {a_j}$ 表示序列 a 从 j = m 到 j = n 的和
五 、矩阵
(和线性代数学科相同的部分,此处不再赘述)
0 - 1 矩阵:所有元素非 0 即 1 的矩阵
0 - 1 矩阵的布尔运算:
- $b_1\bigwedge b_2$:如果 $b_1 = b_2 = 1$ 得 1,否则得 0;
- $b_1\bigvee b_2$:如果 $b_1 = 1 或 b_2 = 1$ 得 1,否则得 0;
0 - 1 矩阵的布尔积:
令 A = $[a_{ij}]$ 为 m$\times$k 阶 0 - 1 矩阵,B = $[b_{ij}]$ 为 k$\times$n 阶 0 - 1 矩阵,A 和 B 得布尔积,记作 $A \bigodot B$。
$c_{ij} = (a_{i1} \bigwedge b_{1j}) \bigvee (a_{i2} \bigwedge b_{2j}) \bigvee … \bigvee (a_{ik} \bigwedge b_{kj}) $
以上可以理解为:矩阵乘法,只不过对每个元素不是做乘法而是布尔运算
0 - 1 矩阵的布尔幂:
令 A 为 0 - 1 方阵,r 为正整数。A 的 r 次布尔幂是 r 个 A 的布尔积。
$A^{[r]} = A \bigodot A \bigodot A \bigodot A \bigodot … \bigodot A$ (r 个 A)
参考书籍:《离散数学及其应用》Kenneth H. Rosen 著