离散数学(四)

以往我们总是见到“一个点处在平面R\times R上”之类的表述，粗略地理解为一个由两个垂直的实数轴张成的平面。笛卡尔积实际是生成一个以有序对作为元素的集合，放到平面几何中来说，上述的粗略理解倒也正确。

所谓的有序对，由两个元素a,b构成，记成\langle a,b\rangle。既然它被称作“有序对”，那么就与集合的无序不同，尖括号内的元素按不同的顺序构成、那么生成的有序对亦不同。准确地说：

a\neq b\leftrightarrow\langle a,b\rangle\neq\langle b,a\rangle

而两个集合A,B间的笛卡尔积记成A\times B，定义为：

A\times B=\{\langle a,b\rangle|a\in A\land b\in B\}

显然在大多数情况下A\times B\neq B\times A。笛卡尔积既不满足交换律也不满足结合律。但是，笛卡尔积与集合并有分配律：

A\times(B\cup C)=(A\times B)\cup(A\times C)

(B\cup C)\times A=(B\times A)\cup(C\times A)

一个关系我们通常用大写字母R来表示，它亦是一种集合，取的是两个集合的笛卡尔积的子集，即R\subseteq A\times B。如果A=B，那么我们称R是集合A上的关系。

对于A\times B中的元素\langle a,b\rangle，如果它是R中的元素，那么就称a和b具有关系R，可以记为a\ R\ b。可以结合比较常见的关系——比如实数域上的相等=——来理解。而从“相等”这个概念出发，我们引申出恒等关系，这种关系只存在于一个集合A及其自身的笛卡尔积A\times A中，记作\Delta_A：

\Delta_A=\{\langle a,a\rangle|a\in A\}

关系除了可以用集合的表示方法来表示之外，在元素较少的情况下也可以用有向图来表示。例如，有序对\langle 3,4\rangle在图中表示为顶点3指向顶点4的一条有向边。当然我们也能用更加“数学化”的关系矩阵来描述。假设集合A=\{a_1,a_2,...,a_n\},B=\{b_1,b_2,...,b_k\}，而它们有一个关系R\subseteq A\times B，由此唯一确定一个n\times k的布尔矩阵\bm{M}_R。记这个矩阵第i行j列的元素为m_{ij}，那么若a_i与b_j具有关系R，则m_{ij}=1，否则m_{ij}=0。

例如，恒等关系只是一个集合上的关系，因此恒等关系的关系矩阵必然是一个方阵；而恒等关系中都是自己对自己的关系，因此恒等关系矩阵的对角线上都是1、其余都为0，也即是一个单位矩阵。

所谓的逆关系，就是将关系R中的每一个元素\langle a,b\rangle都替换为\langle b,a\rangle，记为R^{-1}，即：

R^{-1}=\{\langle b,a\rangle|\langle a,b\rangle\in R\}

显然，对一个关系逆运算两次可以回到自身，即(R^{-1})^{-1}=R。

并且，逆运算保持子集关系，即假设关系R,S\subseteq A\times B，若R\subseteq S，则R^{-1}\subseteq S^{-1}。

另外，逆运算与集合的交或并是可交换的：

(R\cup S)^{-1}=R^{-1}\cup S^{-1}

(R\cap S)^{-1}=R^{-1}\cap S^{-1}

假设两个关系R\subseteq A\times B,S\subseteq B\times C，显然我们能通过R,S得到一个新的关系使其是A到C的关系、剔除掉中间的集合B。称这种运算为复合，记为S\circ R：

S\circ R=\{\langle a,c\rangle\ |\ \exists b\in B(\langle a,b\rangle\in R\ \land\ \langle b,c\rangle\in S)\}

关系复合不满足交换律，但满足结合律，即T\circ(S\circ R)=(T\circ S)\circ R。

关系复合还保持子集关系。假设有四个关系R,S,U,W，且R\subseteq S,U\subseteq W，那么U\circ R\subseteq W\circ S。

同时，如果R\subseteq A\times B，那么\Delta_B\circ R=R=R\circ \Delta_A。另外：

(S\circ R)^{-1}=R^{-1}\circ S^{-1}

\begin{cases} T\circ(R\cup S)=(T\circ R)\cup(T\circ S)\\ (R\cup S)\circ T=(R\circ T)\cup(S\circ T)\\\end{cases}

\begin{cases} T\circ(R\cap S)\subseteq T\circ R\\ T\circ(R\cap S)\subseteq T\circ S\\ (R\cap S)\circ T\subseteq R\circ T\\ (R\cap S)\circ T\subseteq S\circ T\\\end{cases}\qquad\Longrightarrow

\Longrightarrow\begin{cases} T\circ(R\cap S)\subseteq(T\circ R)\cap(T\circ S)\\ (R\cap S)\circ T\subseteq(R\circ T)\cap(S\circ T)\\\end{cases}

假设有两个关系R,S，分别对应关系矩阵\bm{M}_R,\bm{M}_S，这两个矩阵中的元素分别记为r_{ij},s_{ij}。

(1)R\cup S

只需将两个关系矩阵做逻辑或运算即可，即\bm{M}_{R\cup S}=\bm{M}_R\lor\bm{M}_S=[r_{ij}\lor s_{ij}]，即将两个矩阵对应位置的元素作或运算即可。

(2)R\cap S

只需将两个关系矩阵做逻辑与运算即可，即\bm{M}_{R\cap S}=\bm{M}_R\land\bm{M}_S=[r_{ij}\land s_{ij}]，即将两个矩阵对应位置的元素作与运算即可。

(3)R-S

R-S的关系矩阵使用特殊的减法运算：\bm{M}_{R-S}=\bm{M}_R\ominus\bm{M}_S=[r_{ij}\ominus s_{ij}]，这个减法定义为只有1减去0才等于1。即：

0\ominus1=0\ominus1=1\ominus1=0\quad,\quad1\ominus0=1

(4)R^{-1}

逆关系的关系矩阵就是原关系矩阵的转置，即\bm{M}_{R^{-1}}=\bm{M}_R^T=[r_{ji}]。

(5)S\circ R

关系复合是将两个矩阵作逻辑积运算：\bm{M}_{S\circ R}=\bm{M}_R\odot\bm{M}_S。所谓矩阵逻辑积，实际就是普通的矩阵乘法，但是将数乘换做逻辑与、加和换做逻辑或。

接下来我们总假设关系R是一个集合A上的关系，即R\subseteq A\times A。

如果对于任意a\in A，都存在\langle a,a\rangle\in R，那么就说R是自反的。反之，如果都不存在\langle a,a\rangle\in R，则说是反自反的。

我们发现上述定义是针对A中的全体元素说的，因此自反性和反自反性都是非常严格的定义。一个关系是自反的那么必不反自反，如果反自反则必不自反，也就是自反性和反自反性是互斥的(除非A是空集！)。但是由于这两种性质非常严格，一个关系可以既不自反也不反自反。

实数域上常见的自反关系显然有相等，以及带有“相等”的大于等于、小于等于，这些符号两边的数字相等则式子为真；常见的反自反关系有大于和小于，符号两边的数字相等则式子不成立。

显然，自反与反自反与恒等关系间存在联系。若一个关系是自反的，那么恒等关系必是它的子集，即\Delta_A\subseteq R；如果一个关系是反自反的，那么恒等关系与这个关系没有交集，即\Delta_A\cap R=\varnothing。

当我们用关系矩阵来表示这个关系的时候，如果其对角线上都是1，那么这是一个自反关系；如果都是0，则是一个反自反关系。否则既不自反也不反自反。

现在讨论全体的\langle a,b\rangle\in R。如果\langle b,a\rangle也属于R，那么称R是对称的；而在a\neq b的情况下，如果\langle b,a\rangle都属于R，那么称R是反对称的。

当然从关系矩阵的角度来看对称性和反对称性更加直观。对于对称性，上述定义要求对称关系的关系矩阵是一个对称矩阵，即关于对角线对称，即转置矩阵与原矩阵相等\bm{M}_R=\bm{M}_R^T；而对于反对称性，则是要求非对角线上两个对称的元素r_{ij}和r_{ji}都不能同时为1。注意到a\neq b，这是让我们不用关心对角线元素，也就是说自反性不影响反对称性。

从集合的角度而言，如果R=R^{-1}则关系是对称的，这对应上述的转置矩阵与原矩阵相等；而如果关系与其逆关系的交集是恒等关系的子集，即R\cap R^{-1}\subseteq\Delta_A，即可判定它是反对称的。

对称性和反对称性也是非常严格的，两者互斥(除非A是空集！)，但是一个关系可以既不对称也不反对称。实数域上的典型对称关系是相等和不相等，而其他的大于、大于等于等都是反对称关系。

传递性比较类似于关系与其自身的复合。如果对于任意\langle a,b\rangle,\langle b,c\rangle\in R，都有\langle a,c\rangle\in R，那么称关系R是传递的。

关系矩阵不能直观反映关系是否具有传递性。为了更简单地判定关系的传递性，我们通常计算关系与其自身的复合R\circ R。如果R\circ R\subseteq R，那么关系就是传递的；否则不是传递的。

实数域上的大部分关系都是传递的，比如相等、大于(等于)等。

上述中，从集合角度来考察关系性质的，就是性质概括法，可以利用之来验证关系性质。现总结罗列如下：

(1)R具有自反性：\Delta_A\subseteq R

(1)R具有反自反性：\Delta_A\cap R=\varnothing

(1)R具有对称性：R=R^{-1}

(1)R具有反对称性：R\cap R^{-1}\subseteq\Delta_A

(1)R具有传递性：R\circ R\subseteq R

首先给出下表：

\begin{matrix} & 运算 & 自反性 & 反自反性 & 对称性 & 反对称性 & 传递性\\ & R^{-1} & \checkmark & \checkmark & \checkmark & \checkmark & \checkmark\\ & R\cap S & \checkmark & \checkmark & \checkmark & \checkmark & \checkmark\\ & R\cup S & \checkmark & \checkmark & \checkmark & \times & \times\\ & R-S & \times & \checkmark & \checkmark & \checkmark & \times\\ & R\circ S & \checkmark & \times & \times & \times & \times\\\end{matrix}

现在解释上表的含义。这张表描述的是，如果给出的两个(或一个)关系都具有某种性质的话，那么运算结果是否还有这种性质。比如，如果R,S都对称，那么R\cup S也对称；如果R,S都自反，那么R-S不一定自反。

还是假定关系R是一个集合A上的关系，即R\subseteq A\times A。这个关系可能不自反、或者不对称、或者不传递，但我们可以通过一些手段扩展这个关系(也就是添加一些有序对元素)、并且只添加最少量的元素，使之成为一个自反或对称或传递的关系。这个新生成的关系称为闭包。

正如上述，自反闭包是在原关系的基础上，以最小的扩展生成自反关系。R的自反闭包记为r(R)，这是取reflexive的首字母。由于只要恒等关系是关系的子集那么关系就是自反的，因此r(R)=R\cup\Delta_A。

自反闭包可以证明一个关系是自反的，只要一个关系的自反闭包等于它自己。也就是若r(R)=R则R自反，反之亦然。

自反闭包保持子集关系，即若R\subseteq S，那么r(R)\subseteq r(S)。

自反闭包与集合的交与并是可交换的，即：

r(R\cap S)=r(R)\cap r(S)

r(R\cup S)=r(R)\cup r(S)

R的对称闭包记为s(R)，这是取symmetric的首字母。为了以最小的扩展生成对称关系，只需要将关系遍历一遍，添加原本没有的对称有序对即可，即s(R)=R\cup R^{-1}。

对称闭包可以证明一个关系是对称的，只要一个关系的对称闭包等于它自己。也就是若s(R)=R则R对称，反之亦然。

对称闭包保持子集关系，即若R\subseteq S，那么s(R)\subseteq s(S)。

自反闭包与集合并是可交换的，但与集合交不是，即：

s(R\cap S)\subseteq s(R)\cap s(S)

s(R\cup S)=s(R)\cup s(S)

R的传递闭包记为t(R)，这是取transitive的首字母。

传递闭包可以证明一个关系是传递的，只要一个关系的传递闭包等于它自己。也就是若t(R)=R则R传递，反之亦然。

传递闭包保持子集关系，即若R\subseteq S，那么t(R)\subseteq t(S)。

传递闭包与集合的交并只有子集的关系：

t(R\cap S)\subseteq t(R)\cap t(S)

t(R)\cup t(S)\subseteq t(R\cup S)

注意到到这里为止我们还没讲如何从原关系生成传递闭包。为此，我们需要先引入关系的幂。关系的n次幂，记作R^n，是关系与自己的n次复合。例如，R^3=R\circ R\circ R。

从关系矩阵的角度来说，取R^n的关系矩阵中的某一个元素m_{ij}。若m_{ij}=1，那么这说明元素i到j之间具有一条长度为n的通路。例如，原关系的关系矩阵就是在描述哪些元素间具有直接通路，也就是长度为1的通路。

在一个传递的关系中，若两个元素间具有一条长度大于等于2的通路，那么这两个元素间就应当有一条直接通路。因此，我们每计算一次R^n，就是在寻找任意两个元素间的n通路，当我们从1遍历到正无穷的时候，就相当于找到了所有长度的通路。这样，只要在“有通路”的两个元素间建立一条直接通路，我们就生成了原关系的传递闭包：

t(R)=\displaystyle\bigcup_{n=1}^{+\infty}R^n=R^*

R^*是中间的关系广义并的简记。然而实际上我们不可能一直计算到无穷大。假设A中有n个元素。如果一条通路长度大于n、那么这条通路必然会经过重复的顶点(鸽笼原理)，因此这条通路已经是至少两条长度小于n的通路的相连了。也就是说，我们只需计算到R^n即可结束：

t(R)=\displaystyle\bigcup_{k=1}^{n}R^k

Warshall算法实际就是图论中的Floyd算法。这个算法是利用递推式，从\bm{W}_0=\bm{M}_R开始，计算到\bm{W}_n为止。\bm{W}_n本身就是传递闭包结果，这省略了求广义并的过程。

记w_{ij}^k为矩阵\bm{W}_k的第i行j列元素。第k个矩阵由上一个矩阵，也就是第k-1个矩阵完全确定。递推式是：

w_{ij}^k=w_{ij}^{k-1}\lor(w_{ik}^{k-1}\land w_{kj}^{k-1})

等价关系是一个非常严格的关系。如果一个关系同时是自反关系、对称关系、传递关系，那么称它为等价关系。实数域上的典型等价关系就是相等。

接下来假定等价关系R\subseteq A\times A。

等价类是一个集合，它的元素来源于集合A，也就是说它的元素不是有序对。等价类必须基于集合A中的某个元素，例如a，将所有与a等价的元素囊括进来，就形成了a(所在等价关系上)的等价类，记为[a]_R。也就是：

[a]_R=\{x\in A|\langle a,x\rangle\in R\}

由于自反性，等价类中必然至少有一个元素，因此等价类不可能是空集：

[a]_R\neq \varnothing

既然等价类内的任意一个元素都是等价的，那么取任一个元素它都能“代表”这个等价类。也就是说，只要b\in [a]_R，那么b就是这个等价类的一个代表。当然a本身也是这个等价类的代表。

任取集合A中的两个元素a,b，它们之间要么等价要么不等价，因此它们代表的等价类要么相等要么没有交集，也就是：

[a]_R=[b]_R\quad或\quad [a]_R\cap[b]_R=\varnothing

必居其中之一。

商集是一个集合族，它是以等价类作为划分依据的等价关系的划分。

也就是每一个等价类都是一个划分块。A中所有元素的等价类构成的集合族，称为集合A关于等价关系R的商集，记为A/R：

A/R=\{[a]_R\ |\ a\in A\}

商集作为集合A的划分，显然其广义并就是集合A：

\displaystyle\bigcup_{a\in A}[a]_R=\bigcup A/R=A

如果一个关系自反、反对称、传递，那么称它为偏序关系，也简称为偏序，此时我们可以用一个类似小于等于的符号\preceq来表示它。

在此基础上，如果它是反自反的，那么称之为严格序关系。事实上，如果一个关系既反自反又传递，那么它必是一个反对称关系。

如果一个关系自反且传递、但不反对称，那么称它为拟序关系。

接下来我们着重于偏序关系R\subseteq A\times A，或者写成\preceq\subseteq A\times A：

偏序集需要包含偏序关系、以及偏序关系所处在的集合，记为(A,\preceq)。注意到反对称性只要求两个元素a,b的有序对\langle a,b\rangle,\langle b,a\rangle不同时存在，也即允许两者都不存在，此时既不存在a\preceq b也不存在b\preceq a，则称a,b间不可比。反之，称为可比的。当A中任意两个元素都可比，那么称偏序集(A,\preceq)是全序的，或称为线序的。

当a,b间有a\preceq b，称a小于或等于b，当然也能记为b\succeq a，称b大于或等于a。在此基础上，若还有a\neq b，那么记为a\prec b，称a小于b。

假如a,b间有a\prec b，并且中间不存在一个元素c使得a\prec c且c\prec b，则称b覆盖a。

哈斯图是一种简化的关系图，用于表示一个偏序关系。

由于偏序关系是对称的，每个元素必有一条指回自己的环，这显然可以省略；

由于偏序关系是传递的，两元素间有长度大于等于2的通路则必有直接通路，因此略去所有长度大于等于2的通路。这意味着只有一个元素覆盖另一个元素时，两者间才有边；

规定偏序关系中较大者总画在较小者的上方，这样可以略去方向。

首先我们来讲讲极大元、极小元、最大元、最小元：

取A中的某一个元素a。如果在A中没有比a更大的元素，那么称a为极大元；反之，如果在A中没有比a更小的元素，那么称a为极小元。

如果a大于等于A中所有的元素，那么称a为最大元；反之，如果a小于等于A中所有的元素，那么称a为最小元。

因此，如果a是最大元，那么它亦必是极大元；如果a是最小元，那么它亦必是极小元。(只有)在偏序集是全序的情况下，如果a是极大元，那么它亦是最大元；如果a是极小元，那么它亦是最小元。

再者，偏序集可以既没有最大元、也没有最小元，但如果有最大元、则最大元必唯一，如果有最小元、则最小元必唯一。然而，极大元和极小元的数量可以不限，既可以没有，也可以有多个。

接下来我们讲讲上界、下界、上确界、下确界：

“界”是针对偏序集(A,\preceq)的子集来说的。从偏序集中取一子集S，如果A中存在一个元素a大于等于S中的所有元素(注意是所有！)，则称a是S的上界；反之，若元素a小于等于S中的所有元素，则称a是S的下界。注意，这里只要求a\in A，也就是S中的元素也可以是S的上界或下界。

而上界中的最小元称为S的上确界，下界中的最大元称为S的下确界。类似于最大元最小元，S可以既没有上确界也没有下确界，但如果有的话必唯一；上确界必是上界，下确界也必是下界。

并且，如果有上界属于S，那么它必是上确界；同理，如果有下界属于S，那么它必是下确界。