二元关系

序偶与集合的笛卡尔积

定义:由两个对象x、y组成的序列称为有序二元组，也称之为序偶，记作<x,y>；称x、y分别为序偶<x,y>的第一，第二元素。

注意，序偶<x,y>与集合{x,y}不同：

序偶<x,y>：元素x和y有次序；

集合{x,y}：元素x和y的次序是无关紧要的。

序偶与有序n元组

序偶<x, y>与集合{x, y}不同，序偶有次序，集合无次序

笛卡尔积

mn

关系及其表示法

关系的定义

$R\subseteq A\times B$，则称R是从A到B的二元关系

后缀表示

中缀表示

关系的定义域与值域

关系的表示方法

枚举法

谓词公式法

$R=\{<x,y>|x<y\}$

有向图法

矩阵表示法

特殊关系

1. 空关系$\empty$

   关系矩阵全是0

2. 完全关系(全域关系)

$A\times B$或$A\times A$

包含全部序偶，

关系矩阵全是1

3. 恒等关系$I_A$

   关系矩阵只有对角线是1

关系的集合运算

由于关系就是集合，所以集合的**∩、∪、-、和~**运算对关系也适用。

关系的性质

自反性

$\forall x(x\in A\rightarrow xRx)$

反自反性

$\forall x(x\in A\rightarrow <x,x>\notin R)$

（自反和反自反是对立的）

对称性

$\forall x((x\in A\cap y\in A\cap xRy)\rightarrow yRx)$

邻居关系是对称关系，朋友关系是对称关系。

反对称性

$$\forall x\forall y((x\in A\cap y\in A\cap xRy\cap yRx)\rightarrow x=y)\\ \forall x\forall y((x\in A\cap y\in A\cap xRy\cap y\ne x)\rightarrow x\cancel{R}y)$$

对称和反对称不是完全对立的

如恒等关系、空关系

由R的关系图看反对称性：两个不同的结点之间最多有一条边。

从关系矩阵看反对称性：以主对角线为对称的两个元素中最多有一个1。

传递性

warshall算法

重要关系

等价关系

设R是A上关系,若R是自反的、对称的和传递的，则称R是A中的等价关系。

最多的关系，例如，

数值相等关系**=**、命题间的等价关系 、三角形相似∽和全等关系≌，

相容关系

给定集合X上的关系r, 若r是自反的、对称的,则r是A上相容关系。

如朋友关系、同学关系。

次序关系

偏序

R是A上自反、反对称和传递的关系，则称R是A上的偏序关系。并称<A,R>是偏序集。

数值的≤、＜、≥、＞关系；集合的属于关系；