序偶和笛卡尔积

序偶

对于有序n元组，当n=2时，我们将其称作有序二元组，也称作有序对,或序偶。

序偶的特点：

若a≠b,则(a,b)≠(b,a)
两个有序对(a,b)和(c,d)相等当且仅当a=c，b=d。

特征：成对出现、具有一定的顺序。

用序偶表示下列语句中的次序关系

(1)平面上点A的横坐标是x，纵坐标是y，x,y∈R；

(2)成都是四川的省会；

(3)英语课本在书桌上；

(4)左，右关系。

(1)(x,y)

(2)(成都,四川)

(3)(英语课本,书桌)

(4)(左,右)

笛卡尔积

设A，B是两个集合，所有有序对(x, y)做成的集合(其中x∈A，y∈B)，称为A，B的笛卡儿积，记为A×B。A x B = {(x，y)|x∈A且y∈B}

性质

|A×B|=|A|× |B|；
对任意集合A，有A×Ø=Ø，Ø×A=Ø；
笛卡儿积运算不满足交换律，即A×B≠B×A；
笛卡儿积运算不满足结合律，即(A×B)×C≠A×(B×C)
笛卡儿积运算对并和交运算满足分配律，即:
- A×(B∪C)=(A×B)∪(A×C)，
- (B∪C)×A=(B×A)∪(C×A)，
- A×(B∩C)=(A×B)∩(A×C)，
- (B∩C)×A=(B×A)∩(C×A)；
设A，B，C，D是集合，若A⊆C且B⊆D，则 A×B ⊆ C×D。

二元关系

★关系是一个集合，是序偶的集合。

定义

给定任意集合A和B，若R⊆A×B，则称R为从A到B的二元关系，特别在A=B时，称R为A上的二元关系。

从集合A到集合B的一个关系R是A×B的一个子集

R是有序对的集合。若(x,y)∈R，则也表示为x R y，即**(x,y)∈ R ⇔ x R y。**
- 若R =Ø，则称 R 为A 到 B上空关系；
- 若R =A×B，称R为A 到 B上全域关系
- 当A =B 时，
  - 称Ø为A上空关系
  - 称R =A×A为A上的全域关系
  - 称R={（x,x）|x∈A}为A上的恒等关系，记为**IA**。

当集合A,B都是有限集时，A×B共有2^|A|•|B|^个不同的子集，即从A到B的不同关系共有2|^A|•|B|^个。

定义域、值域、域

例

设A={ a , b ,甲，乙}，B={0，1，丙}, 关系S={(a,0) ,(b,0), (甲,1) ,(甲,丙) }
- 则可知D(S)={a, b, 甲},
- R(S)={0, 1, 丙}
实数集R上的”<”关系可定义为：<={(x,y)|x∈R,y∈R且X小于y}
- D(<)=R R(<)=R

关系矩阵

例

例： A={1,2,3,4} ，R={( x , y)| x, y∈A且 x > y}，试求MR，R={( 4 ,1),(4,2),(4,3), (3,1),(3,2),(2,1)}

关系图

例

关系运算

1. 关系的交、并、补、差

前已述及，关系是序偶(有序对)的集合，因此可以对关系进行运算。

若R, S⊆A×B，则R∪S，R ∩S，~R，R-S⊆A×B.

2.复合关系

设R是从集合X到Y的关系，S是从Y到Z的关系，把X到Z的关系定义为RoS。称RoS是关系R和S的合成关系或复合关系.

分配律

结合律

复合的幂运算

3.逆关系

定义

定理一

定理二

定理三

注意点

任意两个关系R和S能进行复合运算当且仅当R的后域是S的前域。
- 注意RoS的前域是R的前域，后域是S的后域；如果对任意的x∈A和z∈C，不存在y∈B使得xRy和ySz同时成立，则RoS为空，从而有ΦoR = RoΦ = Φ。
复合运算有三种计算方式(集合表达式、关系矩阵和关系图), 其中利用关系矩阵的计算方式是难点，RoS的关系矩阵等于R的关系矩阵和S的关系矩阵的布尔积。

关系运算的应用

例设有关系R和S分别如表1和表2所示，在R中增加关系S中的所有元组，试求增加后的关系。

在关系R中增加S中的所有元组，在关系数据库中称为对关系表的插入操作(InsertOperation)，该操作可以通过关系的并运算完成，即求在R中增加关系S的所有元组等价于求R∪S。

A B C

1 2 5

2 1 3

5 6 2

4 6 2

6 1 5

A	B	C
1	2	5
2	1	3
5	6	2
4	6	2
6	1	5

设有关系R和S如表4和表5所示，现在在R中去掉关系S中所出现的元组，试求去掉S后的关系。

相当于 R - S

关系性质

结论

若A上关系R是自反的，则MR中主对角线上元素全为1，而GR中每个结点有有向环；反之亦然。
若A上关系R是反自反的，则MR中主对角线上元素全为0，而GR中每个结点无有向环；反之亦然。
若A上关系R是对称的，则MR是对称矩阵，而GR中任何两结点若有弧必成对出现；反之亦然。
若A上关系R是反对称的，则MR中以主对角线为对称元素不能同时为1，而GR中若两结点间有弧不能成对出现；反之亦然。
若A上关系R是传递的，则MR中若rij=rjk=1，则rik=1，而GR中若有弧（x, y）和（y, z）则必有弧（x, z）；反之亦然。但不易从MR和GR中判定关系R传递性。

注意点

任何集合上的相等关系是自反的、对称的，反对称的和传递的，但不是反自反的。
整数集合Z中，关系≤是自反的、反对称的和传递的，但不是反自反的和对称的。关系**<是反自反的，反对称的和传递的，但不是自反的和对称的**。
非空集合上的空关系是反自反的，对称的，反对称的和传递的，但不是自反的。
空集合上的空关系则是自反的，反自反的，对称的，反对称的和传递的。
非空集合上的全域关系是自反的，对称的和传递的，但不是反自反的和反对称的。