离散数学 第三篇 二元关系01

离散数学

---

序偶

$$<x,y>$$

笛卡尔积

$$A \times B = \left\{ <x,y> | x\in A \wedge y\in B \right\}$$

关系

$$R \subseteq A \times B$$
其中$A$为关系$R$的前域，$B$为后域
定义域
值域

关系表示法

枚举

关系图

关系矩阵

邻接矩阵

复合关系

关系的逆运算

关系的幂运算

关系的性质

自反性与反自反性

对于非空集合$A$上的关系$R$
关键在于：$R$是否含有$<a_i,a_i>$
特例：存在即不是自反，也不是反自反的关系

对称性

对称性：
序偶元素里两个元素调换顺序，仍能在集合找到对应的元素
反对称性：

*（两个元素不等的）序偶元素里两个元素调换顺序，不能在集合找到对应的元素
+ 所有序偶里的元素都是相等的

特例：

• 存在既对称又反对称的
• 存在既不是对称又不是反对称的

传递性

关系内的序偶要有传递，传递后的序偶要在关系内

特例：

• 存在既对称又反对称的
• 存在既不是对称又不是反对称的

关系性质的判别定理

关系闭包运算