Site Overlay

9.1 Relations and Their Properties

关系

书上用 Relations 和 Relation 区分关系构成的集合和关系。中文没有复数变形,我就用英文了。

Relation 用有序数对表示。比如要表示 $1,2$ 之间有关系 $1\to 2$,则记作:

$$
(1, 2)
$$

Relations 就是 Relation 的集合:

$$
R_1 = \{(1,1),(1,2), (1,3)\}
$$

Relations 的运算:就是集合的运算。

有如下:

$R_1 \cup R_2$$R_1 \cap R_2$$R_1 - R_2$$R_1 \bigoplus R_2$$R_1 \circ R_2$

大家不熟悉的应该是 $R_1 \bigoplus R_2$ 了。它叫做“对称差集

$A \bigoplus B = (A-B)\cup (B-A)$

对于 $R_1 \circ R_2$,表示的是复合。学习函数的时候我们知道 $(f_1 \circ f_2)(x) = f_1(f_2(x))$ 表示,对于集合也是一样的。把 $R_2$ 中的某个关系作为输入,经过 $R_1$ 处理后的结果就是 $R_1 \circ R_2$

如果对自身进行复合,即 $R_1 \circ R_1$,则可以记作 $R_1^2$,以此类推:

$$
R^{n+1} = R^n \circ R
$$

关系的类型

自指(Reflexive):

若有:

$R_{3}=\{(1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1),(4,4)\},$
$R_{4}=\{(2,1),(3,1),(3,2),(4,1),(4,2),(4,3)\}$

$R_3$ 是自指的,因为 $(1,1),(2,2),(3,3),(4,4)$ 都在场。

$R_4$ 不是。

a----
↑   |
-----

对称(Symmetric):

$\forall a \forall b((a, b) \in R \rightarrow(b, a) \in R) $ ,则此Relation $R$ 是对称的。

a<---->b

反对称(Antisymetric)

$\forall a \forall b(((a, b) \in R \wedge(b, a) \in R) \rightarrow(a=b))$(也即只和自己对称),则此 Relation $R$ 是反对称的。

Transitive :

若对任何正整数 $n$$R^{n} \subseteq R$,则 $R$ 是 Transitive。

a-->b-->c
|       ↑
---------

问题;对于 $n$ 元素集合,可构成多少个自指关系?

首先我们有前提:$n$ 个元素构成的任何集合都是 $n\times n $ 的子集。

![image-20200920212129839](D:\Sync\primary\Document\md\数学\离散数学\9.1 Relations and Their Properties.assets\image-20200920212129839.png)

构成自指 $R$ 必须包含对角线上的元素,然后剩下的部分可以任意抽取,而剩下的部分有 $n^2 - n$ 个元素,可以构成 $2^{n(n-1)}$ 个子集。 因此答案是 $1 \cdot 2^{n(n-1)}$

推荐阅读:https://www-inst.eecs.berkeley.edu//~cs70/sp15/

发表评论

电子邮件地址不会被公开。 必填项已用*标注