2、复合关系
复合关系 设A,B,C是三个集合,R是A到B的关 系,S是B到C的关系,则R与S的复合关系是一个A到C 的关系,记作R◦S,定义为R◦S={<x, z>xA, zC, yB, 使<x, y>R, <y, z>S} 求复合关系的方法： 关系图之过河拆桥法 关系矩阵相乘法
I A { x, x | x A}
关系的三种表示方法：
1、集合表达式； 2、关系矩阵； 3、关系图。
第2节 关系的运算
关系R的定义域 关系R中所有有序对的第一元素的 集合.记作dom R;
关系R的值域
第二元素的集合.记作ran R.
关系R的域 fldR=domR∪ranR
注： 如果R是A到B的关系，则dom（R）A， dan（R）B
1
。
。
。 4
。 3
2
1
。 。 。
r(R)
。 4 。 3 。 4
1
。 。
s(R)
。 4 。 3 。 4
1
。 。 。
t(R)
。 4 。 3 。 4
st(R)
2
2
2
1
1
。
1
2
。
sr(R)
。 3
。 4 。 3
2
。
。 。
Baidu Nhomakorabea
tr(R)
。 3
。 4 。 3
2
。
。 3
。 4
1
。 。
rs(R)
1
1
。 。
ts(R)
rt(R)
4 哈斯图
偏序集的关系图,可以简化为哈斯图,其简化规则为: (1)所有结点的自回路均省略;
(2)省略所有弧上的箭头, 如果a≤b,则a画在b 的下方。
(3) a到b有边,b到c有边,则a到c的边必须省略。
5 覆盖的概念
设〈A，≤〉为偏序集。x，y ∈A，如果x<y且不存 在z∈ A使得x<z<y，则称y覆盖x。 b是a的覆盖 b d c
定义 R是非空集合A上的关系,若A上关系R’满足: (1） R'是自反的(对称的，传递的） (2）RR' (3）若R''，均有R' R'' 则称关系R'为R的自反(对称,传递)闭包, 记作r(R),(s(R),t(R))。 注： 自反闭包是包含R的最小的自反关系； 对称闭包是包含R的最小的对称关系； 传递闭包是包含R的最小的传递关系.
R2
1
。 。 2。 。 3 3
R3
1
R4
1
。
2
。
2
。
。
2
。 。 3
R5
。 。 3
R6
。 。 2。 。 3 3
R7 R8
几种特殊关系的性质
•空关系 •恒等关系 •全关系EA 思考 |A|=n, A上自反关系共有 2n(n-1) |A|=n, A上自反且对称的关系共有 个。 个。
第 4节
关系的闭包
第4章 二元关系和函数
集合的笛卡尔积和二元关系 关系的有关概念. 函数的概念和性质
4.1 集合的笛卡尔积和二元关系
1 有序对 两个元素x和y组成的有序二元组<x,y> 注：1)也称为序偶 2) <x,y>=<u,v>当且仅当 x=u且y=v 3) 类似定义有序n元组；
2 笛卡尔积
设A，B是任意两个集合，用A中元素作第一元素，B 中元素作第二元素，构成有序对，所有这样的有序对 组成的集合称集合A，B的笛卡尔积，记作A×B. 即A×B={<x, y>xA ∧yB}。 说明:<1> 如A，B均是有限集，A=m,B=n， 则必有AB=mn <2> 一般说AB与BA不相等，即集合的笛卡 尔积运算，不成立交换律。
(1) R是对称的 R－1＝R (2) R是对称的 关系图中没有单向边(自环有无皆可)。
(3) R是对称的 关系矩阵是对称阵
4、反对称性
定义 如果R是A上的关系,a,b∈A如果<a,b>∈R 且 <b,a>∈R，则必有a＝b,称R是A上的反对称关系 等价定义 判定方法
(1) R是A上反对称的 RR－1A
定理: 设R和S是从A到B的两个关系,则RS, RS, R-S, R, RS仍是从A到B的关系。 例3 从集合A={1，2，3，4}到B={a,b,c,d,e}的 关系为 R={<1,a>,<2,b>,<2,c>,<1,d>} S={<1,a>,<1,b>,<2,c>}
求RS, RS, R-S, R, RS
问：常见的偏序关系有哪些？
2 可比的概念
定义 设R为非空集合A上的偏序关系，
x , y A, 定义 (1) x y x y x y ,
其中，x<y读作x”小于” y。
(2) x与y可比 x y y x .
3 全序关系的概念
1) 设R是A上的偏序关系,若a, b∈A,a与b都是可 比的, 则称R为A上的全序关系,或称线序关系。 2) 集合A和A的偏序关系≤一起称为偏序集,记作 <A,≤>。
逆关系的性质
1) |R|=| R-1| 2)（R-1）-1=R 3) 设R是A到B的关系，S是B到C的关系，则
（R ◦ S）-1=S-1 ◦ R-1。 4) 设R是A上的关系，则 R◦IA=IA ◦ R=R.
第4.3节 关系的性质
——本节研究A上的关系R
1、自反性 定义 若x(x∈AxRx)，则称R在A上是自反的，或 称R具有自反性。
(2) R是A上反对称的关系矩阵中对称位置不同时 为1,但允许均为0. (3) R是A上反对称的关系图中没有双向边.
a,b∈A(<a,b>∈R 且a≠b 则<b,a>R)
5、传递性
定义 设R是A上的关系,a,b,c∈A,如果<a,b>∈R, <b,c>∈R,则必有<a,c>∈R,则称R为A上的传递关系, 或称R具有传递性。
集合形式的观察法
复合关系的补充说明
1)这里采用右复合.类似可以定义左复合； 2) 关系的复合运算不成立交换律 ； 3) 复合运算成立结合律 。
关系的n次幂
定义 设R是A上的二元关系，n ∈N,则关系的n次幂 Rn定义为：(1)R0 =A, A是A上的恒等关系； （2）Rn+1=Rn ◦ R 性质 设R是集合A上的关系，m，n∈N，则
例1
指出下列关系的定义域、值域和域 R1={<1,a>,<2,b>,<2,c>,<1,d>}
R2={<1,2>,<2,1>,<2,3>,<1,3>} 例2 设R是自然数集上的小于关系，则 domR= {0,1,2,3,……}
ranR= fldR= {1,2,3,……} {0,1,2,3,……}
1、关系的集合类运算
称[x]R为x关于R的等价类，简称为x的等价类。记
作[x] 或
x
。
3 等价类的性质
设R为非空集合A上的等价关系， x，y∈A, 则
（1） [x] 非空； （2）如果xRy[x]=[y]；
[ x ] [ y] （3） xRy
（4）所有等价类的并集就是A.
4 商集
——设R为非空集合A上的等价关系，以R的所 有等价类作为元素的集合称为A关于R的商集， 记作A/R.即 A/R={[x]R|x∈A}.
例1
设集合A={a, b, c}, B={0,1},求A×B， B×A，A×A,（A×B） B×A.
解：A×B ={<a,0>,<a,1>,<b,0>,<b,1>,<c,0>,<c,1>}
B×A ={<0,a>,<1,a>,<0,b>,<1,b>,<0,c>,<1,c>} A×A={<a, a>, <a, b>, <a, c>, <b, a>, <b, b>, <b, c>, <c, a>, <c, b>, <c, c>} 显然（A×B） B×A=
A/R 等价关系 ？ 集合的划分
二 偏序关系的概念
1 设R是非空集A上的关系,如果R具有自反性,反对称 性和传递性,则称R是A上的偏序关系,或称半序关系, 把关系R记作≤,如果<a,b>∈≤,则记作a≤b,读作 “a小于等于b”
例1 设集合A＝{a,b,c},A上的关系R＝ {<a,a>,<a,b>,<a,c>,<b,b>,<b,c>,<c,c>},从关系 图来验证R是偏序关系。
3 二元关系
关系 任意一个有序对集合称为一个二元关系，简 称关系, 记作R. 如果<a, b>R,可记作aRb,称a与b 有关系R，如<a, b>R,记作aRb,称a与b没有关系R。 这种记法称为中缀记法。
从A到B的二元关系 AB的任何一个子集所定义 的一个二元关系R，称从A到B的二元关系， A上的二元关系 AA的任何一个子集。
笛卡尔积的性质(1)
性质1：对于任意集合A，A=，A= 性质2：笛卡尔积运算不满足交换律，当 A，B，AB时AB BA 性质3：笛卡儿运算不满足结合律，即当A， B，C均非空时（AB）CA（BC）
笛卡尔积的性质(2)
性质4：对任意三个集合A，B，C有 A（BC）=（AB）（AC） A（BC）=（AB）（AC）
特点 (1) 传递关系的关系图的特点：如R是传递关系,如果结 点a能通过有向弧组成的有向路通向结点x,(该有向路, 包含两条或两条以上的弧)则a必须有有向弧直接指向x, 否则R就不是传递的。 (2) R2R
下边R1、R3、R4、R5、R8均是传递的关系。
1
。
2
1
。
2
1
。
1
。
2
。 。 3
R1
1
。 。 3
（BC）A=（BA）（CA）
（BC）A=（BA）（CA）
笛卡尔积的性质(3)
性质5 对于任意集合A，B，C，若C，则 1) AB的充要条件是ACBC 2) A B的充要条件是CACB 性质6：对任意四个非空集合则ABCD的充分必要条 件是AC，BD
注：每个元素都与自己有关系.
判定方法
(1) R是自反的 IA R (2) R是自反的 关系矩阵的对角元素均为1 (3) R是自反的 关系图中每个顶点有自环
2、反自反性
定义 若 x( x A xRx )则称R在A上是反自反的， 或称R具有反自反性。
注：每个元素都与自己没关系.
判定方法
怎样求出给定集合的闭包
• 设R是非空集A的关系,则r(R)=RA • 设R是非空集A的关系,则s(R)=RR-1 • 设R是非空集合A上的关系, 则 t(R)=RR2…
1) 怎样利用关系图求出R的闭包？ 2) 怎样利用关系矩阵求出R的闭包？
练习
给定A中关系R如图所示：分别画出 r(R)、s(R) 、t(R)、sr(R)、rs(R)、 tr(R)、 rt(R)、st(R) 、ts(R) 的图。
（1）Rm ◦ Rn=Rm+n (称第一指数律）
（2）（Rm）n=Rmn (称第二指数律）
3 逆关系
定义 设R是集合A到B的二元关系，则定义一个B到 A的二元关系R-1={<b,a>| <a,b>∈R}，称为R的逆关 系，记作R-1. 求逆关系的方法： 关系图之箭头反向法 关系矩阵转置法
集合形式的元素对换法
2
2
2
。 3
4.5 等价关系和偏序关系
一 等价关系 1 设R是非空集合A上的关系，如果R是自反的、 对称的和传递的，则称R为A上的等价关系 若<x, y>∈R, 则记为x~y 问:常见的等价关系有哪些？
2 等价类的概念
• X的等价类 R为非空集合A上的等价关系， x∈A ，令
[x]R={y|y A且 xRy}，
(1) R是反自反的 IA ∩R= (2) R是反自反的 关系矩阵的对角元素均为0 (3) R是反自反的 关系图中每个顶点没自环
3、对称性
定义 设R是A上的关系，x, y∈A, 如果 <x, y> ∈ R,则必有<y, x> ∈R ，则称R为A 上的对称关系,或称R具有对称性。 判定方法
A到B的不同的关系共有多少？
如|A|=m, |B|=n, |AB|=mn, 而关系是AB 的子集,根据幂集个数的结论,AB的子集 共有2mn,所以,A到B的关系共有 m ? n 个。
2
如A=B,则A上的关系共有 2 ?
nn
个。
集合A上的三种特殊关系：
1、空关系
2、全域关系 3、恒等关系
EA A A
5
集合的划分
设A是一个非空集合,={A1, A2,... ,An}, AiA (i=1,2,...,n), 如果满足: AiΦ , A1∪A2∪...∪An =A (i=1,2,..., n), AiAj=Φ ,(ij,1≤i,j≤n) 则称A是X的划分。每个Ai均称为划分块。
例 X={1,2,3}, A1={{1,2,3}}, A2={{1},{2},{3}}, A3={{1,2},{3}}, A4={{1,2},{2,3}}, A5={{1},{3}} 是划分的是哪个？
