《离散数学及其应用》第二章·基本结构 学习笔记

一、集合

  • 关于集合的常见符号:
符号 含义
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 著