文章目录
- 关系的运算
- 基本运算
- 关系的复合运算
- 关系的逆运算
- 关系的性质
- 一. 自反性和反自反性
- 二.对称性和反对称性
- 三. 传递性
- 关系性质的判定定理
- 关系的性质闭包
- 关系的幂运算
- 传递闭包的关系矩阵
- 闭包关系的性质
- 多重闭包
关系的运算
定义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算法
闭包关系的性质
- 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®，……
