关系的运算

定义5.2.1: 设R，S是X到Y的二元关系，则R∪S，R∩S，R-S，~R，R ⨁ S也是X到Y的二元关系。 二元关系是以序偶为元素的集合，因此可以对它进行集合的运算，如∩、∪、-、 ~和⨁运算而产生新的集合。

基本运算

例子：

关系的复合运算

(实例引导) 设有家族成员集合A： R1是A上的姐弟关系，<x，y>R1，表示x是y的姐妹， R2是A上的父子关系，<y，z>R2，表示y是z的父亲。 由于y的中间作用，x与z之间产生了一种新的关系：姑侄关系。 关系复合运算性质：

关系的逆运算

逆运算的性质：

关系的性质

一. 自反性和反自反性

定义5.3.1: 从关系有向图看自反性:每个结点都有环。 从关系矩阵看自反性：主对角线都为1。 从关系有向图看反自反性:每个结点都无环。 从关系矩阵看反自反性：主对角线都为0。

集合A上自反、反自反关系的个数 例5.3.1:  设|A|=n，试计算A上所有具有自反和反自反性质关系R 的个数。

二.对称性和反对称性

从关系有向图看对称性:在两个不同的结点之间，若有边的话，则有方向相反的两条边。 从关系矩阵看对称性：以主对角线对称的矩阵。  由R的关系图看反对称性：两个不同的结点之间最 多有一条边。  从关系矩阵看反对称性：以主对角线对称的两个 元素中最多有一个1。  对称与反对称不是完全对立的，有些关系它既是对称也是反对称的，如空关系和恒等关系；亦存在既不对称也不是反对称的关系。

三. 传递性

从关系图和关系矩阵中不易看清是否有传递性。一般直接根据传递的定义来检查。 检查时要特别注意使得传递定义表达式的前件为F的时候此表达式为T，即是传递的。 即：对任意的x,y,z∈A，如果<x,y>R或者<y,z>R，则R在A上是传递的。

空关系是一种特殊关系，指关系集A×B中的子集∅。非空集合中的空关系是反自反的、对称的、反对称的和传递的，但不是自反的；

关系性质的判定定理

关系的性质闭包

闭包定义： 自反闭包对称闭包传递闭包计算方法： 传递闭包：

整数集上的自反闭包

关系的幂运算

单位元（幺元） 鸽巢原理一般指抽屉原理，是组合数学中一个重要的原理。抽屉原理的含义：如果每个抽屉代表一个集合，每一个苹果代表一个元素，假如有n+1个元素放到n个集合中，其中必定有一个集合里至少有两个元素

传递闭包的关系矩阵

Warshall算法

闭包关系的性质

1. R是A上关系，则 ⑴ R是自反的，当且仅当 r(R )=R。 ⑵ R是对称的，当且仅当 s(R )=R。 ⑶ R是传递的，当且仅当 t(R )=R。

多重闭包

二元关系的闭包仍然是二元关系，还可以继续对求得的关系求闭包。  例如，R是A上的二元关系, r®是它的自反闭包，还可以求r®的对称闭包。r®的对称闭包记为s(r®)，简记为sr®，读作R的自反闭包的对称闭包。  类似的，R的对称闭包的自反闭包r(s®)简记为rs®，R的对称闭包的传递闭包t(s®)，简记为ts®，……