关系分类：
- n元关系
- 二元关系
- 空关系
- 全关系
几个定义
- 二元关系
AxB记为$xRy$ - 全域关系$A \times B$, 恒等关系$I_A = {<x,x> | x \in A}$
- 两个$R_1$, $R_2$关系相等要求：1. $R_1 = R_2$。2. $R_1$,$R_2$来自的集合相等。
- 定义域 dom R，值域 ran R
关系的表示
- 列举法
- 关系图
- 关系矩阵 $a_{ij} = (x_i==y_j)$ 矩阵先行后列
关系的性质
谓词逻辑
P -> Q 真值表
| P Q | P ->Q |
|---|---|
| F F | T |
| F T | T |
| T F | F |
| T T | T |
五种典型二元关系
- 自反，反自反
- 对称，反对称
- 传递
| R | 自反 | 反自反 | 对称 | 反对称 | 传递 |
|---|---|---|---|---|---|
| $M_R$ | 对角线元素全1 | 对角线元素全0 | 对称矩阵 | 非对称矩阵 | 字面意思 |
| $G_R$ | 每个节点有自圈 | 节点都无自圈 | 成对出现有向边 | 无成对有向边 | 处处有捷径 |
| 既对称又反对称则关系矩阵只包括对角线 |
关系的运算
- 关系的交 ，和， 差，对称差。
- 补关系，逆关系
- 复合关系
- 关系幂
补充定理
若二元关系$R \in A^2$，则
i) R是自反的 iff $R^{-1}$是自反的
ii) R是反自反的 iff $R^{-1}$是反自反的
iii) R是对称的 iff $R^{-1}$是对称的，且$R = R^{-1}$
iv) R是反对称的 iff $R^{-1}$是反对称的
v) R是传递的 iff $R^{-1}$是传递的
关系的闭包
- 自反闭包 r(R)
- 对称闭包 s(R)
- 传递闭包 t(R)
R为集合A上的二元关系，
i) r(R) = R∪$I_A$；
ii) s(R) = R∪$R^{-1}$；
iii) t(R) = $R^+$ 。$R^+ = R^1 \cup R^2 \cup R^3 .... \cup R^n$
设二元关系R1，R2 $\in A^2$，R1 $\in$ R2则
i) $r(R1) \in r(R2)$；
ii) $s(R1) \in s(R2)$；
iii) $s(R1) \in s(R2)$。
设二元关系R $\in A^2$，
i) 若R是自反的，则s(R)和t(R)也是自反的；
ii) 若R是对称的，则r(R)和t(R)也是对称的；
iii) 若R是传递的，则r(R)也是传递的；s(R)不一定传递
v) rs(R) = sr(R)；
vi) rt(R) = tr(R)；
vii) st(R) $\in$ ts(R);