离散数学第九章 关系（二）

离散数学 关系

part 1. n元关系

1. 设 $A_{1},A_{2},A_{3},A_{4},...A_{n}$ 是集合。定义在这些集合上的 $n$ 元关系是$A_{1} \times A_{2} \times ... \times A_{n}$的子集。这些集合$A_{1},A_{2},A_{3},A_{4},...A_{n}$成为关系的域( domains of the relations ), $n$ 称为关系的阶（degree ).
2. 数据库和关系： 关系数据模型（relational data model )
   
   • 数据库由记录组成，这些记录是由域构成的 $n$ 元组，这些域是$n$元组的数据项。用于表示数据库的关系也称为表（tables ), 表中的每一列表示数据库的一个属性（attribute )。
   • 当 $n$ 元组的某个域的值能够确定这个 $n$ 元组时，$n$元关系的这个域就叫做主键（primary key )
   • 外延（extension ): 一个关系当前含有的所有 $n$ 元组
   • 内涵（intension ): 数据库更持久的内容，包括名字和属性
   • 当一组域的值确定一个关系中的 $n$ 元组时，这些域的笛卡儿积就叫做复合主键（ composite key )。

3. $n$ 元关系的运算

   • 选择运算： 设 $R$ 是一个 $n$ 元关系，$C$ 是 $R$ 中元素可能满足的一个条件。那么 选择运算符 $S_{C}$ 将 $n$ 元关系 $R$ 映射到 $R$ 中满足条件 $C$ 的所有 $n$ 元组构成的 $n$ 元关系。

   • 投影运算： $P_{i_{1},i_{2},...i_{m}}$，其中 $i_{1} < i_{2} < ...< i_{m}$, 将 $n$ 元组 $(a_{1}, a_{2}, ..., a_{n})$ 映射到 $m$ 元组 $(a_{i_{1}},a_{i_{2}},...a_{i_{m}})$, 其中 $m \leqslant n$.

   • 连接运算： 略去不表，课本中文版$P492$,英文版$P588$.

part 2. 关系的闭包（Closure of the relation )

1. 自反闭包： $R \cup \Delta$, 其中$\begin{equation} \Delta = \left\{ (a,a)|a \in A \right\}\end{equation}$
2. 对称闭包： $R \cup R^{-1}$, 其中$R^{-1} = \begin{equation} \left\{ (b,a)|(a,b) \in R \right\}\end{equation}$
3. 传递闭包：
   
   • 定理1： 设 $R$是集合 $A$ 上的关系，从 $a$ 到 $b$ 存在一条长为 $n$ ($n$ 为正整数）的路径，当且仅当 $(a,b) \in R^{n}$.
   • 定义： 连通性关系$R^{*}$由形如$(a,b)$的有序对构成，使得在关系$R$中，从 $a$ 到 $b$ 之间存在一条长度至少为1的路径。
   • 根据定义，从 $a$ 到 $b$ 存在长度至少为1的路径(path )，若其长度为 $n$,则由定理1可知，$(a,b) \in R^{n}.$ $R^{*}$ 对关系中任何$a,b$ 都存在路径，则
     $R^{*} = \displaystyle{ \bigcup_{n= 1}^{\infty} R^{n}}$
   • 关系 $R$ 的传递闭包等于通性关系(connectivity relation ) $R^{*}$.
   • 引理1：设$A$ 是含有 $n$ 个元素的集合。 $R$ 是集合 $A$ 上的关系，如果 $R$ 中存在一条从 $a$ 到 $b$ 的长度至少为1的路径，那么其长度不超过 $n$。当$a \not = b$ 时， 长度不超过 $n - 1$.
   • 由引理1可知，$R$ 的传递闭包$R^{*} = R \cup R^2 \cup R^3 \cup...\cup R^n$. (因为$a,b$间的路径长度最大不会超过$n$, 而$a,b$路径长度为$i$, 当且仅当$(a,b) \in R^i$）
   • 用0-1矩阵表示， $M_{R^*} = M_{R} \vee M_{R}^{[2]} \vee M_{R}^{[3]}\vee...M_{R}^{[n]}$
   • 求传递闭包 的算法1（复杂度为$O(n^4)$)：

part 3. 沃舍尔算法（ Warshall's algorithm )

• $W_0 = M_R, W_n = M_{R^*}$
• 从 $W_{k-1}$ 直接计算 $W_{k}$:
  
    $w^{[k]}_{ij} = 1$ 当且仅当 $w^{[k-1]}_{ij} = 1$ 或 $w^[{k-1]}_{ik} = 1$ 且 $w^{[k-1]}_{kj} = 1$
  
  
• 算法2： 沃舍尔算法（复杂度为$O(n^3)$):

part 4. 等价关系与偏序

1. 等价关系：(Equivalence Relations )
   
   • 需满足自反的，对称的，传递的。
   • 如果两个元素 $a$ 和 $b$ 由于等价关系而相关联，则称他们是等价的。记作：$a\sim b$.
2. 等价类：设 $R$ 是定义在集合 $A$ 上的等价关系。与 $A$ 中的要给元素 $a$有关系的所有元素的集合叫做 $a$ 的等价类。 $A$ 的关于 $R$ 的等价类记作 $[a]_R$。当只考虑一个关系时可以省去下标。
   
   • $[a]_R = \begin{equation} \left\{s|(a,s) \in R\right\}\end{equation}$
     If $b \in [a]_R$, then $b$ is called a representative(代表元） of this equivalence class.
3. 等价类与划分：(Equivalence Classes and Partitions )
   
   • 以下命题等价：
     (1) $aRb\space\space\space\space\space$(2) $[a] = [b]\space\space\space\space$(3)$[a]\cap[b] \not = \emptyset$
   • 集合 $S$ 的划分是 $S$ 的不相交非空子集构成的集合，且它们的并集就是 $S$。即，一族子集$A_i$, $i\in I$ ($I$ 是下标的集合）构成 $S$ 的划分，当且仅当：
     $A_i \not= \emptyset \space\space\space i\in I$
     $A_i \cap A_j = \emptyset\space\space\space\space i \not = j$
   • 可以用等价关系的等价类构成集合的划分，也何以用集合的每个划分来构成等价关系。
     2.偏序：(Partial Orderings )
   • 需满足自反的，反对称的，传递的。
   • 在偏序集(partial ordered set, or poset )里，记号$a\preceq b$表示$(a,b)\in R$
   • 偏序集$(S,\preceq)$ 中的元素$a,b$，如果有$a \preceq b$ 或 $b \preceq a$，则称 $a,b$ 是可比(comparable )的。否则是不可比(incomparable )的。
   • 如果偏序集每对元素都是可比的，则称其为全序集（totally ordered set )或线序集（linear ordered set ). $\preceq$称为全序或线序。一个全序集也称为链（chain ).
   • 对于偏序集，如果 $\preceq$ 是全序，并且其每个非空子集都有一个最小元素，则称它为良序集(well ordered set ).
   • 良序归纳原理：$S$ 为良序集，如果对所有$y \in S$，$P(x)对所有x\in S且 x\prec y$ 为真，则$P(y)$ 为真，因此对所有$x \in S$ 都为真。（良序归纳法不需要基础步骤 ）
4. 字典顺序（Lexicographic Order）很好理解，略去。
5. 拟序(Quasiorder) transitive and reflexive。（example： ($P(S),\subset$))
6. 乘积偏序（product partial order）与字典顺序相比，每项都需要满足$\preceq$ 的条件。
7. 同构（isomorphism）两个偏序集一一对应，偏序关系也一一对应。
8. $(S,R)$ 是偏序集，则 $(S,R^{-1})$ 也是偏序集，且后者被称作前者的对偶(Dual )。

part 5. 哈塞图（Hasse Diagram )

1. Let $(S, \preceq)$ be a poset. We say that an element $y \in S$ covers an element $x \in S$ if $x \prec y$
   and there is no element $z \in S$ such that $x \prec z \prec y$ . The set of pairs $(x,y)$ such that y
   covers x is called the covering relation of $(S, \preceq)$.
   
   • a is maximal(极大元） in the poset $(S, \preceq)$ if there is no $b \in S$ such that $a \prec b$.
   • minimal 定义反之。
   • 区分： maximal（没有更“大”） /greatest element（比所有都“大”）
     minimal（没有更“小”）/least element（比所有都“小”）
   • 最小上界(least upper bound, LUB ),最大下界（greatest lower bound，GLB)：对 $S$ 的子集 $A$,若在 $S$ 中能找到 $u$，使得对所有 $A$ 中的元素 $a$，都有 $a \preceq u$, 则 $u$ 为 $A$ 的最小上界。Vice versa.
   • 定理：有限的偏序集有至少一个极大元和至少一个极小元，至多一个最大元和至多一个最小元，至多一个LUB，至多一个GLB。
   • 同构关系的极大极小元，最大最小元，LUB和GLB都一一对应。
   • 拓扑排序（Topological Sorting）：定义一个相容（compatible）的全序集，每次寻找极小元排序。
   • 格(lattice ): 每对元素都有最小上界和最大下界，就称该偏序集为格。
   • $LUB(\begin{equation}\left\{a,b\right\}\end{equation}) = a\wedge b \space\space\space(join)$
   • $GLB(\begin{equation}\left\{a,b\right\}\end{equation}) = a\vee b \space\space\space(meet)$