第四章 二元关系二元关系是一个很重要的概念,它在很多数学领域中都有应用,在计算机科学的如下理论都离不开关系,
逻辑设计,数据结构,编译原理,软件工程数据库理论,计算理论,算法分析,操作系统 等本章主要介绍:
关系的概念及表示方法关系的性质关系的运算,关系的复合,求逆关系,关系的闭包,
三种关系,等价关系,相容关系,次序关系。
4-1 序偶与集合的笛卡尔积实际上“序偶”概念以前已经用过。例如,用序偶表示平面直角坐标系中一个点 (a,b)。设 x表示上衣,y表示裤子,(x,y)可以表示一个人的着装。
一,序偶与有序 n元组
1.定义,由两个对象 x,y组成的序列称为有序二元组,也称之为序偶,记作 <x,y>;称 x,y分别为序偶 <x,y>的第一,第二元素。
注意,序偶 <x,y>与集合 {x,y}不同:
序偶 <x,y>:元素 x和 y有 次序;
集合 {x,y}:元素 x和 y的次序是无关紧要的。
2.定义,设 <x,y>,<u,v>是两个序偶,如果
x=u和 y=v,则称 <x,y>和 <u,v>相等,
记作 <x,y>=<u,v>.
3,定义,有序 3元组是一个序偶,其第一个元素也是个序偶。
有序 3元组 << a,b>,c>可以简记成 <a,b,c>。
但 <a,<b,c>>不是 有序 3元组。
4.定义,有序 n元组是一个序偶,其第一个元素本身是个有序 n-1元组,记作 <<x1,x2,?,xn-1>,xn>。且可以简记成
<x1,x2,?,xn-1,xn>。
5,定义,<x1,x2,?,xn>=<y1,y2,·?,yn>
( x1= y1)? ( x2= y2)( xn= yn)
二,集合的 笛卡尔积例如“斗兽棋”的 16颗棋子,
可看成是由两种颜色的集合 A和 8种动物的集合 B组成的。
A={红,蓝 }
B={象,狮,虎,豹,狼,狗,猫,鼠 }
每个棋子可以看成一个序偶,斗兽棋可记成集合 A?B,
{ <红,象 >,<红,狮 >,<红,虎 >,<红,豹 >,<红,狼 >,<红,狗 >,<红,猫 >,<红,鼠 >,
<蓝,象 >,<蓝,狮 >,<蓝,虎 >,<蓝,豹 >,<蓝,狼 >,<蓝,狗 >,<蓝,猫 >,<蓝,鼠 > }
虎象 狮 豹 狼 鼠猫狗虎象 狮 豹 狼 鼠猫狗
1.定义,设 A,B是集合,由 A的元素为第一元素,
B的元素为第二元素组成序偶的集合,称为 A
和 B的笛卡尔积,记作 A× B,即
A?B={<x,y>|x?A∧ y?B}
例 1 设 A={0,1},B={a,b},求 A?B,B?A,
A?A 。
解,A?B={<0,a>,<0,b>,<1,a>,<1,b>}
B?A={<a,0 >,<b,0>,<a,1>,<b,1>}
A?A={<0,0>,<0,1>,<1,0>,<1,1>}
可见 A× B≠B× A
所以,集合的笛卡尔积运算不满足交换律。
另外
(A?B)?C={<<a,b>,c>|<a,b>?A?B?c?C}
A?(B?C)={<a,<b,c>>|a?A?<b,c>?B?C},
因 <a,<b,c>>不是有序三元组,
所以 (A?B)?C?A?(B?C)。
故?也不满足结合律。
2.性质
1) 如果 A,B都是有限集,且 |A|=m,|B|=n,则
|A?B |=mn,
证明:由笛卡尔积的定义及排列组合中的乘法原理,直接推得此定理。
2) A?Φ=Φ?B=Φ
3)?对 ∪ 和 ∩满足分配律。
设 A,B,C是任意集合,则
⑴ A?(B∪ C)= (A?B)∪ (A?C);
⑵ A?(B∩C)= (A?B)∩(A?C);
⑶ (A∪ B)?C= (A?C)∪ (B?C);
⑷ (A∩B)?C= (A?C)∩(B?C)
证明⑴,任取 <x,y>?A?(B∪ C)
x?A?y?B∪ C?x?A?(y?B∨ y?C)
( x?A?y?B)∨ (x?A?y?C)
<x,y>?A?B∨ <x,y>?A?C
<x,y>?(A?B)∪ (A?C) 所以⑴式成立。
其余可以类似证明。
4)若 C,则
A?B?(A?C?B?C)?(C?A?C?B).
证明,必要性,设 A?B,求证 A?C?B?C
任取 <x,y>?A?C?x?A?y?C
x?B?y?C (因 A?B)
<x,y>?B?C 所以,A?C?B?C,
充分性,若 C,由 A?C?B?C 求 证 A?B
取 C中元素 y,任取 x?A?x?A?y?C
<x,y>?A?C
<x,y>?B?C (由 A?C?B?C )
x?B?y?C?x?B 所以,A?B.
所以 A?B?(A?C?B?C)
类似可以证明 A?B?(C?A?C?B).
5) 设 A,B,C,D为非空集合,则
A?B?C?D?A?C∧ B?D.
证明,首先,由 A?B?C?D 证明 A?C∧ B?D.
任取 x?A,任取 y?B,所以
x?A?y?B
<x,y>?A× B
<x,y>?C× D (由 A?B?C?D )
x?C?y?D 所以,A?C∧ B?D.
其次,由 A?C,B?D,证明 A?B?C?D
任取 <x,y>?A× B
<x,y>?A× B? x?A?y?B
x?C?y?D (由 A?C,B?D)
<x,y>?C× D 所以,A?B?C?D 证毕,
6)约定
(…(A 1?A2)?…?An-1)?An)=A1?A2?…?An
特别 A?A?…?A = An
设 R是实数集合,则 R2表示 笛卡尔坐标平面,
R3表示 三维空间,Rn表示 n维空间。
3.应用
1)令 A1={x|x是 学号 } A2={x|x是 姓名 } A3={男,女 }
A4={x|x是 出生日期 } A5={x|x是 班级 } A6 ={x|x是 籍贯 }
则 A1?A2?A3?A4?A5?A6中一个元素:
<001,王强,男,1981:02:16,计 2001-1,辽宁 >
这就是学生档案数据库的一条信息,所以学生的档案就是 A1?A2?A3?A4?A5?A6的一个子集。
n 个
2) 令
A={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,
w,x,y,z} 是英文字母表一个 英文单词可以看成有序 n元组:如
at=<a,t>,boy=<b,o,y>,data=<d,a,t,a>,
computer=<c,o,m,p,u,t,e,r>
于是可以说:
at?A2,boy?A3,data?A4,computer?A8,…
于是英文词典中的 单词集合 可以看成是
A∪ A2∪ … ∪ An 的一个子集。
作业 第 105页 ⑵
4-2 关系及其表示法关系是一个非常普遍的概念,如数值的大于关系、整除关系,人类的父子关系、师生关系、同学关系等。下面讨论如何从中抽象出关系的定义和如何表示关系。
一,例子
1,大写英字母与五单位代码的对应关系 R1:
令 α={A,B,C,D,…Z}
β={30,23,16,22,…,21} 是 五单位代码集合
β={11000,10011,01110,10010,…,10001}
R1={<A,30>,<B,23>,<C,16>,...,<Z,21>}?α× β
2.令A ={1,2,3,4},A中元素间的 ≤关系 R2,
R2={ <1,1>,<1,2>,<1,3>,<1,4>,<2,2>,<2,3>,
<2,4>,<3,3>,<3,4>,<4,4>}?A× A
二,基本概念
1.关系的定义定义 1:设 A、B是集合,如果R?A× B,则称 R是一个 从 A到 B的二元关系。如果 R?A× A,则称 R是 A上 的二元 关系。 二元 关系简称为关系。
定义 2:任何序偶的集合,都称之为一个二元关系。
如,R={<1,a>,<书,车 >,<人,树 >}
<x,y>?R?xRy 也称之为 x与 y有R关系。
后缀表示 中缀表示
<x,y>?R?xRy 也称之为 x与 y没有R关系。
例 3,R是实数集合,R上的几个熟知的关系:
从例 3中可以看出 关系是序偶 (点 )的集合 (构成线、面 )。
x2+y2=4≤

=
x
y
2.关系的定义域与值域定义域 (domain),设 R?A× B,由所有 <x,y>?R
的第一个元素组成的集合,称为 R的定义域,
记作 dom R,即
dom R={x|?y(<x,y>?R)}
值域 (range),设 R?A× B,由所有 <x,y>?R的第二个元素组成的集合,称为 R的值域,
记作 ran R,即
ran R={y|?x(<x,y>?R)}
上述 R2={ <1,1>,<1,2>,<1,3>,<1,4>,<2,2>,<2,3>,
<2,4>,<3,3>,<3,4>,<4,4>}
dom R2 ={1,2,3,4}
ran R2 ={1,2,3,4}
三,关系的表示方法
1,枚举法,
即将关系中所有序偶一一列举出,写在大括号内。如前的 R2 ={ <1,1>,<1,2>,<1,3>,<1,4>,<2,2>,
<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} 。
2.谓词公式法,
即用谓词公式表示序偶的第一元素与第二元素间的关系。例如
R={<x,y>|x<y}
3.有向图法,
R?A× B,用两组小圆圈 (称为 结点 )分别表示 A
和 B的元素,当 <x,y>?R时,从 x到 y引一条有向弧 (边 )。这样得到的图形称为 R的关系图。
如 R?A× A,即 R是集合 A中关系时,可能有
<x,x>?R,则从 x到 x画一条有向环 (自回路 )。
例 设 A={1,2,3,4},B={a,b,c},R3?A× B,
R3={ <1,a>,<1,c>,<2,b>,<3,a>,<4,c>}
则 R3的关系图如下:
例 设 A={1,2,3,4},R4?A× A,
R4={ <1,1>,<1,4>,<2,3>,<3,1>,<3,4>,<4,1>,<4,2>}
则 R4的关系图如右上图。
1。
2。
3。
4。



A B
a
b
c
1。 。
4。 。
2
3
R4,R3,
4.矩阵表示法,
有限集合之间的关系也可以用矩阵来表示,这种表示法便于用计算机来处理关系。
设 A={a1,a2,?,am},B={b1,b2,?,bn}是个有限集,
R?A× B,定义 R的 m× n阶 矩阵
MR=(rij)m× n,其中
rij=
R3={ <1,a>,<1,c>,<2,b>,<3,a>,<4,c>}
R4={ <1,1>,<1,4>,<2,3>,<3,1>,<3,4>,<4,1>,<4,2>}
上例中 MR = MR4=
1 若 <ai,bj>∈ R
0 若 <ai,bj>∈ R (1≤i≤m,1≤j≤n)
3
1 0 1
0 1 0
1 0 0
0 0 1 4× 3
1
2
3
4
a b c
1 0 0 1
0 0 1 0
1 1 0 0
1 0 0 1
4× 4
1
2
3
4
1 2 3 4
四,三个特殊关系
1.空关系 Φ:
因为 Φ?A× B,(或 Φ?A× A),所以 Φ也是一个从 A到 B(或 A上 )的关系,称之为 空关系 。即无任何元素的关系,它的关系图中只有结点,无任何边;它的矩阵中全是 0。
2.完全关系 (全域关系 ):
A× B(或 A× A)本身也是一个从 A到 B(或
A上 ) 的关系,称之为完全关系。即含有全部序偶的关系。它的矩阵中全是 1。
3,A上的 恒等关系 IA:
IA?A× A,且 IA ={<x,x>|x∈ A}称之为 A
上的恒等关系。
例如 A={1,2,3},则 IA ={<1,1>,<2,2>,<3,3>}
A上的 Φ、完全关系及 IA的关系图及矩阵如下:
MIA =
1 0 0
0 1 0
0 0 1 3× 3
1。
2。 。 3
1。
2。 。 3
1 1 1
1 1 1
1 1 1 3× 3
1。
。2。 3
0 0 0
0 0 0
0 0 0 3× 3
MΦ= MA× A=
Φ A× A IA
五,关系的集合运算由于关系就是集合,所以集合的 ∩,∪,
-,?和 ~运算对关系也适用。
例如,A是学生集合,R是 A上的同乡关系,
S是 A上的同姓关系,则
R∪ S:或同乡或同姓关系
R∩S:既同乡又同姓关系
R-S,同乡而不同姓关系
R?S:同乡而不同姓,或同姓而不同乡关系
~R:不是同乡关系,这里 ~R=(A× A)-R
作业 第 109页 ⑵、⑸ c)d)
4-3 关系的性质本节将研究关系的一些性质,它们在关系的研究中起着重要的作用 。 这是本章最重要的一节 。
本节中所讨论的关系都是集合 A中的关系 。
关系的性质主要有:自反性,反自反性,对称性,反对称性和传递性 。
一,自反性定义,设 R是集合 A中的关系,如果对于任意 x∈ A都有 <x,x>∈ R (xRx),则称 R是 A中自反关系 。 即
R是 A中自反的x(x?A?xRx)
例如在实数集合中,“?”是自反关系,因为,对任意实数 x,有 x? x.
从关系有向图看自反性,每个结点都有环。
从关系矩阵看自反性:主对角线都为 1。
令 A={1,2,3}给定 A上八个关系如下:
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R2R1 R3 R4
R5 R6 R7 R8
可见这八个关系中 R1,R3,R4是自反的。
二,反自反性定义,设 R是集合 A中的关系,如果对于任意的 x∈ A都有 <x,x>?R,则称 R为 A中的反自反关系。即
R是 A中反自反的x(x?A?<x,x>?R)
从关系有向图看反自反性,每个结点都无环。
从关系矩阵看反自反性:主对角线都为 0。
如实数的大于关系 >,父子关系是反自反的。
注意,一个不是自反的关系,不一定就是反自反的,如前边 R6,R7非自反,也非反自反。
下面 R2,R5,R8、均是反自反关系 。
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R2R1 R3 R4
R5 R6 R7 R8
三,对称性定义,R是集合 A中关系,若对任何 x,y∈ A,如果有 xRy,必有 yRx,则称 R为 A中的对称关系。
R是 A上对称的
x?y((x?A?y?A?xRy)?yRx)
从关系有向图看对称性,在两个不同的结点之间,若有边的话,则有方向相反的两条边。
从关系矩阵看对称性:以主对角线为对称的矩阵。
邻居关系是对称关系,朋友关系是对称关系。
下边 R3,R4,R6,R8均是对称关系。
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R2R1 R3 R4
R5 R6 R7 R8
四,反对称性定义,设 R为集合 A中关系,若对任何 x,y∈ A,如果有
xRy,和 yRx,就 有 x=y,则称 R为 A中反对称关系 。
R是 A上反对称的
x?y((x?A?y?A?xRy?yRx)?x=y)
x?y((x?A?y?A?x?y?xRy)?y x) (P112)
由 R的关系图看反对称性,两个不同的结点之间最多有一条边。
从关系矩阵看反对称性,以主对角线为对称的两个元素中最多有一个 1。
另外对称与反对称不是完全对立的,有些关系它既是对称也是反对称的,如空关系和恒等关系。
R
下边 R1,R2,R4,R5,R8均是反对称关系。
R4,R8既是对称也是反对称的。
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R2R1 R3 R4
R5 R6 R7 R8
五,传递性定义,R是 A中关系,对任何 x,y,z∈ A,如果有 xRy,和 yRz,就有 xRz,则称 R为 A中传递关系。
即 R在 A上传递
x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz)
实数集中的 ≤、<,集合?,?是传递的。
从关系关系图和关系矩阵中不易看清是否有传递性。有时,必须直接根据传递的定义来检查。
检查时要特别注意使得传递定义表达式的前件为 F的时候此表达式为 T,即是传递的。
即若 <x,y>∈ R与 <y,z>∈ R有一个是 F时 (即定义的前件为假 ),R是传递的。
例如 A={1,2},下面 A中关系 R是传递的,
通过带量词的公式在论域展开式说明
R在 A上传递
x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz)
x?y?z((xRy?yRz)?xRz) (为了简单做些删改 )
y?z((1Ry?yRz)?1Rz)y?z((2Ry?yRz)?2Rz)
(?z((1R1?1Rz)?1Rz)z((1R2?2Rz)?1Rz)
(?z((2R1?1Rz)?2Rz)?(?z((2R2?2Rz)?2Rz))
(((1R1?1R1)?1R1)?((1R1?1R2)?1R2))?
(((1R2?2R1)?1R1)?((1R2?2R2)?1R2))?
(((2R1?1R1)?2R1)?((2R1?1R2)?2R2))?
(((2R2?2R1)?2R1))? ((2R2?2R2)?2R2))
(((F?F)?F)?((F?T)?T))?(((T?F)?F)?((T?F)?T))?
(((F?F)?F)?((F?T)?F))?(((F?F)?F))?((F?F)?F))?T
12
下边 R1,R3,R4,R5,R8均是传递的关系 。
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R2R1 R3 R4
R5 R6 R7 R8
本节要求,
1.准确掌握这五个性质的定义。
2.熟练掌握五个性质的判断和证明。
R是 A中 自反 的x(x?A?xRx)
R是 A中 反自反 的x(x?A?<x,x>?R)
R是 A上 对称 的x?y((x?A?y?A?xRy)?yRx)
R是 A上 反对称 的
x?y((x?A?y?A?xRy?yRx)?x=y)
x?y((x?A?y?A?x?y?xRy)?y x)
R在 A上 传递
x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz)
上述定义表达式都是 蕴涵式,所以判断关系 R性质时要特别注意使得性质定义表达式的前件为 F的时候此表达式为 T,即 R是满足此性质的。 (自反和反自反性除外 )
R
自反性反自反性对称性传递性反对称性每个结点都有环 主对角线全是 1
每个结点都无环 主对角线全是 0
不同结点间如果有边,
则有方向相反的两条边,
是以对角线为对称的矩阵不同结点间,最多有一条边,
以主对角线为对称的位置不会同时为 1
如果有边 <a,b>,<b,c>,
则也有边 <a,c>,
或者定义的前件为假,
如果 aij=1,且 ajk=1,
则 aik=1
从 关 系的矩 阵从 关 系的有向 图性 质 判定,
下面归纳这八个关系的性质,Y-有 N-无
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R2R1 R3 R4
自反性 反自反性 对称性 反对称性 传递性
R1 Y N N Y Y
R2 N Y N Y N
R3 Y N Y N Y
R4 Y N Y Y Y
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R5 R6 R7 R8
自反性 反自反性 对称性 反对称性 传递性
R5 N Y N Y Y
R6 N N Y N N
R7 N N N N N
R8 N Y Y Y Y
练习 1:令 I是整数集合,I上关系 R定义为:
R={<x,y>|x-y可被 3整除 },求证 R是自反、对称和传递的。
证明,⑴证自反性,任取 x∈ I,(要证出 <x,x>?R )
因 x-x=0,0可被 3整除,所以有 <x,x>∈ R,故 R自反。
⑵证对称性,任取 x,y∈ I,设 <x,y>∈ R,(要证出 <y,x>?R )
由 R定义得 x-y可被 3整除,即 x-y=3n(n∈ I),
y-x=-(x-y)=-3n=3(-n),因 -n∈ I,∴ <y,x>∈ R,
所以 R对称。
⑶ 证传递性,任取 x,y,z∈ I,设 xRy,yRz,(要证出 xRz)
由 R定义得 x-y=3m,y-z=3n (m.n∈ I)
x-z= (x-y)+(y-z)=3m+3n=3(m+n),因 m+n∈ I,
所以 xRz,所以 R传递。 证毕练习 2,设 R是集合 A上的一个自反关系,求证:
R是对称和传递的,当且仅当
<a,b>和 <a,c>在 R中,则有 <b,c>也在 R中。
证明,必要性,已知 R是对称和传递的。
设 <a,b>?R 又 <a,c>?R,(要证出 <b,c>?R )
因 R对称的故 <b,a>?R,又已知 <a,c>?R 由传递性得 <b,c>?R。所以有如果 <a,b>和 <a,c>在 R中,则有
<b,c>也在 R中。
充分性,已知任意 a,b,c?A,如 <a,b>和 <a,c>在 R
中,则有 <b,c>也在 R中。
先证 R对称,任取 a,b?A 设 <a,b>?R,(要证出
<b,a>?R ) 因 R是自反的,所以 <a,a>?R,由
<a,b>?R且 <a,a>?R,根据已知条件得 <b,a>?R,
所以 R是对称的。
再证 R传递,任取 a,b,c?A 设 <a,b>?R,
<b,c>?R。 (要证出 <a,c>?R )
由 R是对称的,得 <b,a>?R,由
<b,a>?R且 <b,c>?R,根据已知条件得
<a,c>?R,所以 R是传递的。
作业 第 113页
⑴、⑶、⑷
4-4 关系的复合二元关系除了可进行集合并、交、补等运算外,
还可以进行一些新的运算,先介绍由两个关系生成一种新的关系,即关系的复合运算。
例如,有 3个人 a,b,c,A={a,b,c},
R是 A上 兄妹 关系,
S是 A上 母子 关系,
<a,b>∈ R∧ <b,c>∈ S
即 a是 b的哥哥,b是 a的妹妹 ;
b是 c的母亲,c是 b的儿子。
则 a和 c间就是 舅舅和外甥 的关系,记作 R?S,
称它是 R和 S的复合关系 。
SR?
a b cR S
1.定义,设是 R从 X到 Y的关系,S是从 Y到 Z的关系,则 R和 S的复合关系记作 R?S 。定义为:
R?S ={<x,z>|x?X?z?Zy(y?Y
<x,y>?R?<y,z>?S)}
显然,R?S 是从 X到 Z的关系。
2.复合关系的计算方法 (俗称过河拆桥法 )
A={1,2,3} B={1,2,3.4} C={1,2,3,4,5}
R?A× B S?B× C
⑴ 枚举法
R={<1,2>,<2,3>,<2,4>,<3,1>}
S={<1,2>,<2,1>,<2,3>,<3,4>,<4,2>,<4,5>} 则
R?S={<1,1>,<1,3>,<2,4>,<2,2>,<2,5>,<3,2>}
⑵有向图法
⑶关系矩阵法令 A={a1,a2,…,a m} B={b1,b2,…,b n}
C={c1,c2,…,c t} R?A× B S?B× C




C
1
2
3
。 4
1。
2。
3。
A
1。
2。
3。
A



B
1
2
3
。 4
R S
5。



C
1
2
3
。 4
5
SR?
c11=(a11∧ b11)∨ (a12∧ b21)∨,..∨ (a1n∧ bn1)
= (a1k∧ bk1) (其中 ∧ 是逻辑乘,∨ 是逻辑加 )
cij=(ai1∧ b1j)∨ (ai2∧ b2j)∨,..∨ (ain∧ bnj)
= (aik∧ bkj) (1≤i≤m,1≤j≤t)
MS MR
<a1,b1><a1,b2>...<al,bn>
<a2,b1><a2,b2>...<a2,bn>...,..
<am,b1><am,b2>...<am,bn>
(aij)
<b1,c1><b1,c2>...<bl,ct>
<b2,c1><b2,c2>...<b2,ct>...,..
<bn,c1><bn,c2>...<bn,ct>
(bij)
<a1,c1>...<al,ct>
<a2,c1>...<a2,ct>...,..
<am,c1>...<am,ct>
M
SR?
(cij)
0 1 0 0
0 0 1 1
1 0 0 0 3× 4
。 1 0 0 0 01 0 1 0 0
0 0 0 1 0
0 1 0 0 1
=
4× 5
1 0 1 0 0
0 1 0 1 1
1 0 0 0 0 3 × 5
k=1
n∨
k=1
n∨
⑷ 谓词公式法设 I是实数集合,R和 S都是 I上的关系,定义如下:
R={<x,y>| y=x2+3x}
S={<x,y>| y=2x+3}
所以 R?S ={<x,y>| y=2x2+6x+3}
三,性质关系复合运算不满足交换律,但是
1.满足结合律,R?A× B S?B× C T?C× D 则
TS)(RT)S(R
x x2+3x 2(x2+3x)+3 = 2x2+6x+3R S
证明:任取 <a,d>∈ R (S T)
b(b∈ B∧ <a,b>∈ R∧ <b,d>∈ S T)
b(b∈ B∧ <a,b>∈ R∧?c(c∈ C∧ <b,c>∈ S∧ <c,d>∈ T))
b?c(b∈ B∧ <a,b>∈ R∧ (c∈ C∧ <b,c>∈ S∧ <c,d>∈ T))
c?b(c∈ C∧ (b∈ B∧ <a,b>∈ R∧ <b,c>∈ S∧ <c,d>∈ T))
c (c∈ C∧?b(b∈ B∧ <a,b>∈ R∧ <b,c>∈ S)∧ <c,d>∈ T)
c (c∈ C∧ <a,c>∈ R S)∧ <c,d>∈ T)
<a,d>∈ (R S) T
TS)(RT)S(R
A B
C D
R
T
所以可以用下图形象表示,
2,R?A× B S?B× C T?B× C
⑴ R (S∪ T)=(R S)∪ (R T)
⑵ R (S∩T)?(R S)∩(R T)
证明 ⑴ 任取 <a,c>∈ R (S∪ T)
b(b∈ B∧ <a,b>∈ R∧ <b,c>∈ S∪ T)
b(b∈ B∧ <a,b>∈ R∧ (<b,c>∈ S∨ <b,c>∈ T))
b((b∈ B∧ <a,b>∈ R∧ <b,c>∈ S)∨
(b∈ B∧ <a,b>∈ R∧ <b,c>∈ T))
b(b∈ B∧ <a,b>∈ R∧ <b,c>∈ S)∨
b(b∈ B∧ <a,b>∈ R∧ <b,c>∈ T)
<a,c>∈ R S∨ <a,c>∈ R T
<a,c>∈ (R S)∪ (R T)
所以 R (S∪ T)=(R S)∪ (R T)
证明⑵ 任取 <a,c>∈ R (S∩T)
b(b∈ B∧ <a,b>∈ R∧ <b,c>∈ S∩T)
b(b∈ B∧ <a,b>∈ R∧ (<b,c>∈ S∧ <b,c>∈ T))
b((b∈ B∧ <a,b>∈ R∧ <b,c>∈ S) ∧
(b∈ B∧ <a,b>∈ R∧ <b,c>∈ T))
b(b∈ B∧ <a,b>∈ R∧ <b,c>∈ S)∨
b(b∈ B∧ <a,b>∈ R∧ <b,c>∈ T)
<a,c>∈ R S ∧ <a,c>∈ R T
<a,c>∈ (R S)∩(R T)
所以 R (S∩T)?(R S)∩(R T)
x(A(x)∧ B(x))xA(x)∧?xB(x)
3,R是从 A到 B的关系,则
R IB=IA R=R
此式的证明很容易,从略。下面列举一例来验证。
令 A={1,2,3},B={a,b,c,d}
从这两个图看出它们的复合都等于 R。
1。
2。
3。
AIA



B
a
b
c
。 d
R
1。
2。
3。
AR
IB



a
b
c
。 d



B
a
b
c
。 d
1。
2。
3。
A B
4,关系的乘幂令 R是 A上关系,由于复合运算可结合,所以关系的复合可以写成乘幂形式。即
R R=R2,R2 R=R R2 =R3,…
一般地
R0 =IA,
Rm Rn = Rm+n
(Rm)n =Rmn (m,n为非负整数 )
例如 R是 A上关系,如上图所示,可见
<a,c>?R2,表明在 R图上有从 a到 c有两条边的路径,
a b c;<a,d>?R3,表明在 R图上有从 a到 d有三条边的路径,a b c d。,..如果 <x,y>?Rk,表明在
R图上有从 x到 y有 k条边 (长为 k)的路径 。 (x,y?A)
a
d
b
c
R:
4-5 逆关系逆关系 (反关系 )也是我们经常遇到的概念,例如 ≤与 ≥就是互为逆关系。
一,定义
R是从 A到 B的关系,如果将 R中的所有序偶的两个元素的位置互换,得到一个从 B到 A的关系,
称之为 R的逆关系,记作 RC,或 R-1。
RC={<y,x>|<x,y>?R}
<y,x>∈ RC?<x,y>?R
二,计算方法
1,R={<1,2>,<2,3>,<3,4>,<4,5>}
RC ={<2,1>,<3,2>,<4,3>,<5,4>}
2,RC的有向图:是将 R的有向图的所有边的方向颠倒一下即可。
3,RC的矩阵 M =(MR)T 即为 R矩阵的转置。如三,性质令 R,S都是从 X到 Y的关系,则
1,(RC)C = R
2,(R∪ S)C = RC∪ SC 。
3,(R∩S)C = RC∩SC 。
4,(R- S)C = RC- SC 。
RC
1 0 11 0 1 00 0 0 1
1 0 1 1
MR=
3× 4
0 0 0
1 0 1
0 1 1
MR =c
4× 3
证明 1.:任取 <y,x>?(R∪ S)C,则
<y,x>?(R∪ S)C? <x,y>?R∪ S
<x,y>?R∨ <x,y>?S
<y,x>?RC∨ <y,x>?SC
<y,x>? RC∪ SC
所以 (R∪ S)C = RC∪ SC,其它类似可证。
5,R?S? RC?SC 。
证明,充分性,已知 RC? SC,则任取 <x,y>∈ R
<y,x>?RC? <y,x>?SC? <x,y>?S ∴ R?S
必要性,已知 R? S,则任取 <y,x>∈ RC
<x,y>?R?<x,y>?S?<y,x>?SC ∴ RC?SC
6.(~R)C=~RC
证明,任取 <y,x>∈ (~R)C?<x,y>∈ ~R?<x,y>?R
<y,x>?RC?<y,x>∈ ~RC ∴,(~R)C=~RC
7.令 R是从 X到 Y的关系,S是 Y到 Z的关系,则
(R S)C= SC RC 。 (注意 ≠RC SC )
证明,任取 <z,x>∈ (R S)C
<x,z>?R S
y(y∈ Y∧ <x,y>∈ R∧ <y,z>∈ S)
y(y∈ Y∧ <z,y>∈ SC∧ <y,x>∈ RC)
<z,x>?SC RC 所以 (R S)C= SC RC
8,R是 A上关系,则
⑴ R是对称的,当且仅当 RC =R
⑵ R是反对称的,当且仅当 R∩RC?IA。
证明,⑴ 充分性,已知 RC =R (证出 R对称 )
任取 x,y?A 设 <x,y>?R,则 <y,x>?RC,而 RC =R
所以有 <y,x>?R,所以 R对称。
必要性,已知 R 对称,(证出 RC =R)
先证 RC?R,任取 <y,x>∈ RC,则 <x,y>?R,因 R对称所以有 <y,x>∈ R,所以 RC?R。
再证 R? RC,任取 <x,y>?R,因 R对称,所以有
<y,x>∈ R,则 <x,y>∈ RC,所以 R?RC。
最后得 RC =R 。
证明⑵ 充分性,已知 R∩RC?IA,(证出 R反对称 )
任取 x,y?A 设 <x,y>?R 且 <y,x>∈ R,
<x,y>?R∧ <y,x>∈ R?<x,y>?R∧ <x,y>∈ RC,
<x,y>?R∩RC? <x,y>? IA (因 R∩RC?IA )
x=y 所以 R反对称。
必要性,已知 R反 对称,(证出 R∩RC?IA)
任取 <x,y>?R∩RC
<x,y>?R∩RC?<x,y>?R∧ <x,y>?RC
<x,y>?R∧ <y,x>?R
x=y (因 R反对称 )
<x,y>?IA 所以 R∩RC?IA 。
第 4-3和 4-4节的 要求,
熟练掌握求复合关系和逆关系的计算方法及性质。
作业,第 118页⑴、⑵ a)b)、⑶、⑸
4-6 关系的闭包运算关系的闭包是个很有用的概念,特别是传递闭包。关系的闭包是通过关系的复合和求逆构成的一个新的关系。这里要介绍关系的自反闭包、对称闭包和传递闭包。
一,例子给定 A中关系 R,如图所示,
分别求 A上另一个关系 R’,使得它是包含 R的“最小的” (序偶尽量少 )分别具有自反 (对称、传递 )性的关系。 这个 R’就分别是 R的 自反 (对称、传递 )闭包。
1。
2。 。 3
这三个关系图分别是 R的 自反、对称、传递闭包。
二,定义,给定 A中关系 R,若 A上另一个关系 R’,
满足:⑴ R?R’;
⑵ R’是自反的 (对称的、传递的 );
⑶ R’是,最小的,,即对于任何 A上自反 (对称、
传递 )的关系 R”,如果 R?R”,就有 R’?R”。
则称 R’是 R的 自反 (对称、传递 )闭包。记作 r(R)、
(s(R),t(R)) (reflexive,symmetric,transitive)
1。
2。 。 3
1。
2。 。 3
1。
2。 。 3
实际上 r(R),(s(R),t(R)) 就是包含 R的“最小”
的 自反 (对称、传递 )关系。
三,计算方法定理 1.给定 A中关系 R,则 r(R)=R∪ IA。
证明:令 R’=R∪ IA,显然 R’是自反的和 R?R’,下面证明 R’是“最小的”:如果有 A上自反关系
R”且 R?R”,又 IA?R”,所以 R∪ IA?R”,即 R’?R”。
所以 R’就是 R的自反闭包。即 r(R)=R∪ IA 。
定理 2.给定 A中关系 R,则 s(R)=R∪ RC 。
证明方法与 1.类似。
定理 3.给定 A中关系 R,则 t(R)=R∪ R2∪ R3∪,.,。
证明:令 R’= R∪ R2∪ R3∪,..,
⑴ 显然有 R?R’ ;
⑵证 R’是传递的:任取 x,y,z?A,设有 <x,y>?R’
<y,z>?R’,由 R’定义得必存在整数 i,j使得
<x,y>?Ri,<y,z>?Rj,根据关系的复合得
<x,z>?Ri+j,又因 Ri+j?R’,所以 <x,z>?R’,∴ R’传递 。
⑶ 证 R’是“最小的”:如果有 A上传递关系 R”且
R?R”,( 证出 R’?R”)任取 <x,y>?R’,则由 R’定义得必存在整数 i,使得 <x,y>?Ri,根据关系的复合得
A中必存在 i-1个元素 e1,e2,...,ei-1,使得 (见 49页 )
<x,e1>?R∧ <e1,e2>?R∧,..∧ <ei-1,y>?R。因 R?R”,
∴ 有 <x,e1>?R”∧ <e1,e2>?R”∧,..∧ <ei-1,y>?R”。
由于 R”传递,所以有 <x,y>?R”。 ∴ R’?R”。
综上所述,R’就是 R的传递闭包,即
t(R)=R∪ R2∪ R3∪ …= ∪ Rii=1∞
用上述 公式计算 t(R),要计算 R的无穷大次幂,好象无法实现似的。其实则不然,请看下例,
A={1,2,3} A中关系 R1,R2,R3,如下:
R1={<1,2>,<1.3>,<3,2>}
R2 ={<1,2>,<2.3>,<3,1>}
R3 ={<1,2>,<2.3>,<3,3>}
={<1,2>} = =Φ 所以
t(R1)= ∪ ∪ = R1
={<1,3>,<2,1>,<3,2>} ={<1,1>,<2,2>,<3,3>}
=IA,= R2,..
t(R2)= R2∪ ∪
={<1,3>,<2,3>,<3,3>} =
t(R3)= R2∪
2R
1
3R
1
4R
1
1R
1
2R
1
3R
1
2R
2
3R
2
4R
2
3R
2
2R
2
3R
2
3R
3
2R
3
2R
3
2R
3
定理 4.给定 A中关系 R,如果 A是有限集合,|A|=n
则 t(R)=R∪ R2∪,..∪ Rn 。
证明:令 R’=R∪ R2∪ R3∪,..,R”=R∪ R2∪,..∪ Rn
下面证明 R’=R”,
显然有 R”?R’。下面证明 R’?R”:
任取 <x,y>?R’,由 R’定义得必存在 最小的 正整数 i 使得 <x,y>?Ri,(下面证明 i≤n)如果 i> n,
根据关系的复合得 A中必存在 i-1个元素 e1,e2,...,ei-1,
使得 <x,e1>?R∧ <e1,e2>?R∧,..∧ <ei-1,y>?R。
上述元素序列,x=e0,e1,e2,...,ei-1,y=ei中共有 i+1个元素,i+1>n,而 A 中只有 n个元素,所以上述元素中至少有两个相同,设 ej=ek (j<k),于是 R的关系图中会有下面这些边:
从此图中删去回路中 k-j(k-j≥1)条边后得
<x,y>∈ Ri-(k-j),i-(k-j)<i,与 i是 最小的 矛盾。
所以 i≤n,所以 <x,y>∈ R”,于是 R’?R”。
最后得 R’=R”,所以
t(R)=R∪ R2∪,..∪ Rn 定理证毕。

。 。 。 。 。 。 。x e
1 ej-1 ej =ek
ej+1。




ej+2
ek-1
ek-2
ek+1 ek+2…..,…..,ei-1 y
求 t(R)的矩阵 Warshall算法,|X|=n,R?X× X,
令 MR=A R2的矩阵为 A2,… R k的矩阵为 Ak,于是
t(R)的 矩阵记作 MR+=A+A2+…+A k +… (+是逻辑加 )
⑴ 置新矩阵 A,=MR ;
⑵ 置 i=1;
⑶ 对所有 j,如果 A[j,i] =1,则对 k=1,2,…,n
A[j,k]:=A[j,k]+A[i,k]; /*第 j行 +第 i行,送回第 j行 */
⑷ i加 1;
⑸ 如果 i≤n,则转到步骤 ⑶,否则停止。
下面举例,令 X={1,2,3,4},
X中关系 R图如右图所示。
运行该算法 求 t(R)的矩阵,
1。
2。


4
3
i=1 (i---列,j---行 )
A[4,1]=1
1行 +4行 →4 行
i=2 A[1,2]=1,1行 +2行 →1 行
A[2,2]=1,2行 +2行 →2 行 A不变
A[4,2]=1,4行 +2行 →4 行,4行全 1,A不变
i=3 A[1,3]=1,1行 +3行 →1 行,3行全 0,A不变
A[2,3]=1,2行 +3行 →2 行,3行全 0,A不变
A[4,3]=1,4行 +3行 →4 行,3行全 0,A不变
i=4 A[1,4]=1,1行 +4行 →1 行
A[4,4]=1,4行 +4行 →4 行 A不变,
最后 A=Mt(R)
1101
0000
0110
1010
A=MR= A=
1111
0000
0110
1010
A的初值,
A=
1111
0000
0110
1110
A=
1111
0000
0110
1111
四,性质定理 5,R是 A上关系,则
⑴ R是自反的,当且仅当 r(R)=R.
⑵ R是对称的,当且仅当 s(R)=R.
⑶ R是传递的,当且仅当 t(R)=R.
证明略,因为由闭包定义即可得。
定理 6,R是 A上关系,则
⑴ R是自反的,则 s(R)和 t(R)也自反。
⑵ R是对称的,则 r(R)和 t(R)也对称。
⑶ R是传递的,则 r(R)也传递。
证明,⑴ 因为 R自反,由定理 5得 r(R)=R,即
R∪ IA=R,r(s(R))=s(R)∪ IA=(R∪ RC)∪ IA
= (R∪ IA)∪ RC=r(R)∪ RC =R∪ RC =s(R)∴ s(R)自反类似可以证明 t(R)也自反。
证明 ⑵,证明 t(R)对称,
(t(R))C=(R∪ R2∪,..∪ Rn∪,..)C
= RC∪ (R2)C ∪,..∪ (Rn)C∪,..
= RC∪ (RC)2 ∪,..∪ (RC)n∪,.,
=R∪ R2∪,..∪ Rn∪,.,(∵ R对称,∴ RC =R)
=t(R) 所以 t(R)也对称。
类似可以证明 r(R)也对称。
证明 ⑶,证明 r(R)传递,先用归纳法证明下面结论,
(R∪ IA)i= IA∪ R∪ R2∪,..∪ Ri
① i=1时 R∪ IA= IA∪ R 结论成立。
②假设 i≤k 时结论成立,即
(R∪ IA)k= IA∪ R∪ R2∪,..∪ Rk
(R2)c=(R R)c
=Rc Rc
=(Rc)2
③ 当 i=k+1时
(R∪ IA)k+1=(R∪ IA)k (R∪ IA)
= (IA∪ R∪ R2∪,..∪ Rk) (IA∪ R)
= (IA∪ R∪ R2∪,..∪ Rk)∪ (R∪ R2∪,..∪ Rk+1)
= IA∪ R∪ R2∪,..∪ Rk∪ Rk+1
所以结论成立,
t(r(R))=t(R∪ IA)
= (R∪ IA)∪ (R∪ IA)2∪ (R∪ IA)3∪,..
=(IA∪ R)∪ (IA∪ R∪ R2)∪ (IA∪ R∪ R2∪ R3)∪,..
= IA∪ R∪ R2∪ R3∪,..= IA∪ t(R)
= IA∪ R (R传递 t(R)=R)
=r(R) 所以 r(R)也传递。


定理 7:设 R1,R2是 A上关系,如果 R1?R2,则
⑴ r(R1)? r(R2) ⑵ s(R1)? s(R2) ⑶ t(R1)?t(R2)
证明⑴ r(R1)=IA∪ R1?IA∪ R2= r(R2)
⑵,⑶类似可证。
定理 8:设 R是 A上关系,则
⑴ sr(R)=rs(R) ⑵ tr(R)=rt(R) ⑶ st(R)?ts(R)
证明,⑴ sr(R)=r(R)∪ (r(R)c=(R∪ IA)∪ (R∪ IA)c
= (R∪ IA)∪ (Rc∪ IAc) =R∪ IA∪ Rc∪ IA
= (R∪ Rc)∪ IA= s(R)∪ IA=rs(R)
⑵ 的证明用前边证明的结论:
(R∪ IA)k= IA∪ R∪ R2∪,..∪ Rk
很容易证明,这里从略。
⑶ 因 R?s(R) 由定理 7得 t(R)?ts(R) st(R)?sts(R)
因 s(R)对称,有定理 6得 ts(R) 也对称,由定理 5得
sts(R)=ts(R) 所以有 st(R)?ts(R) 。 证明完毕。
通常将 t(R) 记成 R+,tr(R)记成 R*,即
t(R)= R+=R∪ R2∪,..∪ Rn∪ …=
tr(R)=rt(R) =R*= R0∪ R∪ R2∪,..∪ Rn∪ …=
练习,给定 A中关系 R
如图所示:分别画出 r(R)、
s(R),t(R),sr(R),rs(R)、
tr(R),rt(R),st(R),ts(R)
的图。
1。
2。


4
3
∪ Rii=1∞
∪ Rii=0∞
1。
2。


4
3
1。
2。


4
3
1。
2。


4
3
1。
2。


4
3
1。
2。


4
3
1。
2。


4
3
1。
2。


4
3
1。
2。


4
3
1。
2。


4
3
r(R) s(R) t(R)
sr(R)
rs(R)
tr(R)
rt(R)
st(R)
ts(R)
本节重点掌握闭包的定义、计算方法和性质。
作业 第 127页 ⑴、⑸、⑺、⑻
4-7 集合的划分与覆盖图书馆的图书,要分成许多类存放,学校的学生要按照专业分成许多班,… 即对集合的元素划分一,定义 设 X是一个非空集合,A={A1,A2,...,An},
Ai?Φ Ai?X (i=1,2,...,n),如果满足
A1∪ A2∪,..∪ An =X (i=1,2,...,n)
则称 A为集合 X的 覆盖 。
设 A={A1,A2,...,An}是 X一个覆盖,且 Ai?Aj=Φ
(i?j,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}}
A1,A2,A3,A4 是覆盖。 A1,A2,A3也是划分。
划分,一定是覆盖;但覆盖,不一定是划分 。
二,最小划分与最大划分最小划分,划分块最少的划分。即只有一个划分块的划分,这个划分块就是 X本身。如 A1 。
最大划分,划分块最多的划分。即每个划分块里只有一个元素的划分。如 A2 。
A1,A2,A3是一种划分,其中 A1是最小划分,A2是最大划分。
三,交叉划分例 X是东大学生集合,A和 B都是 X的划分:
A={M,W},M?X,W?X,M={男生 },W={女生 }
B={L,N},L?X,N?X,L={辽宁人 },N={非 辽宁人 }
C={L∩M,L∩W,N∩M,N∩W }
称 C是 X的交叉划分。
M W
L
N
L∩M L∩W
N∩M N∩W
辽宁男生 辽宁女生 非辽宁男生 非辽宁女生定义,若 A={A1,A2,...,Am}与 B={B1,B2,...,Bn}都是集合 X
的划分,则其中所有的 Ai?Bj,组成的集合 C,称为 C是 A与
B两种划分的交叉划分,(此定理的证明不讲 )
证明,{ A1,A2,...,Am}与 {B1,B2,...,Bn}的交叉划分是
C={A1?B1,A1?B2,...,A1?Bn,
A2?B1,A2?B2,...,A2?Bn,...,
Am?B1,Am?B2,...,Am?Bn}
在 C中任取元素,Ai?Bh?X (∵ Ai?X,Bj?X)
(A1?B1)∪ (A1?B2)∪,..∪ (A1?Bs)∪ (A2?B1)∪ …
∪ (A2?Bs)∪,.,∪ (Ar?B1)∪ (Ar?B2)∪,..∪ (Ar?Bs)
=(A1?( B1∪ B2∪ B3∪,..Bs))∪
(A2?( B1∪ B2∪ B3∪,.,∪ Bs))∪,.,∪
(Ar?( B1∪ B2∪ B3∪,.,∪ Bs))
= (A1∪ A2∪ A3∪,..∪ Ar)?( B1∪ B2∪ B3∪,.,∪ Bs)
=X?X=X
再验证 C中任意两个元素不相交:
在 C中任取两个不同元素 Ai?Bh和 Aj?Bk,考察
(Ai?Bh)? (Aj?Bk) (i=j和 h=k不同时成立 )
= (Ai?Aj)?(Bh?Bk)
i= j,h≠k (Ai?Aj)?(Bh?Bk) =Ai=?
i≠j,h≠k (Ai?Aj)?(Bh?Bk)==?
i≠j,h=k (Ai?Aj)?(Bh?Bk)= Bh =?
综上所述,C是 X的划分。
作业,第 130页 (1)
4-8 等价关系与等价类等价关系是很重要的关系,它是我们遇到最多的关系,例如,数值相等关系 =、命题间的等价关系?、三角形相似 ∽ 和全等关系 ≌,…..
一,等价关系
1.定义,设 R是 A上关系,若 R是自反的、对称的和传递的,则称 R是 A中的等价关系。若
a,b?A,且 aRb,则称 a与 b等价。
例子,集合 A={1,2,3,4,5,6,7},R是 A上的模 3同余关系,即
R={<x,y>|x-y可被 3整除 (或 x/3与 y/3的 余数相同 )}
即 <x,y>∈ R? x(mod 3)=y(mod3)
例如 4(mod 3)=7(mod3) 3(mod 3)=6(mod3)
R={<1,1>,<1,4>,<1,7>,<2,2>,<2,5>,<3,3>,<3,6>,<4,1>,
<4,4>,<4,7>,<5,2>,<6,3>,<6,6>,<7,1>,<7,4>,<7,7>}
2.等价关系的有向图
1)完全关系 (全域关系 A× A)图,下面分别是当 A中只有
1,2,3个元素时的完全关系图。
1。
2。
1。
2。 3。1。
A={1} A={1,2} A={1,2,3}
2.等价关系的有向图,
上边 的模 3同余关系
R的图:
从关系图可看出,R是自反、
对称、传递的关系,所以 R是等价关系。
等价关系 R的有向图可能由若干个独立子图 (R图的一部分 )构成的,每个独立子图都是完全关系图 。
上述关系 R图就是由三个独立的完全图构成的。
下面给出八个关系如图所示,根据等价关系有向图的特点,判断哪些是等价关系,
2。
5。
1。
4。 7。
3。
6。
A={1,2,3}下面是 A中关系:
1。
2。 。
1。
2。 。 33
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R2R1
R5 R6
1。
2。 。
1。
2。 。 33
R3 R4
R7 R8
思考题,A={1,2,3},可构造多少个 A中不同的等价关系?可以根据等价关系有向图的特点来考虑。
如果等价关系 R中有
a)三个独立子图的情形,则 ( )个等价关系 。
b)二个独立子图的情形,则 ( )个等价关系 。
c)一个独立子图的情形,则 ( )个等价关系 。
一共有 ( )个 中不同的等价关系。
二,等价类我们经常用等价关系对集合进行划分,得到的划分块称之为等价类。
1.定义,R是 A上的等价关系,a∈A,由 a确定的集合 [a]R:
[a]R={x|x∈A∧<a,x>∈R}
称集合 [a]R为由 a形成的 R等价类。简称 a等价类。
可见 x∈[a] R?<a,x>∈ R
上例,A={1,2,3,4,5,6,7},R是 A上的模 3同余关系,
[1]R={1,4,7}= [4]R = [7]R ----余数为 1的等价类
[2]R={2,5}= [5]R ----余数为 2的等价类
[3]R={3,6}= [6]R ----余数为 0的等价类思考题,此例为什么只有三个等价类?
2,由等价关系图求等价类,R图中每个独立子图上的结点,
构成一个等价类。不同的等价类个数 =独立子图个数。
上述三个等价关系各有几个等价类?说出对应的各个等价类。
1。
2。 。 3
R2
1。
2。 。 3
R1

R3

。1
2 3
从上述模 3同余关系例子中,可以归纳出等价类的性质:任何两个等价类要么相等,要么不相交;那么在什么情况下相等?那么在什么情况下不相交?
3.等价类性质
R是 A上等价关系,任意 a,b,c∈ A
⑴ 同一个等价类中的元素,彼此有等价关系 R。
即任意 x,y∈ [a]R,必有 <x,y>∈ R
证明,任取 x,y∈ [a]R,由等价类定义得,<a,x>∈ R,
<a,y>∈ R,由 R对称得,<x,a>∈ R,又由 R传递得 <x,y>∈ R。
⑵ [a]R∩[b]R=Φ,当且 仅当 <a,b>?R。
证明,设 <a,b>?R,假设 [a]R∩[b]R≠Φ,则存在 x∈ [a]R∩[b]R,
∴ x∈ [a]R∧ x∈ [b]R,∴ <a,x>∈ R,<b,x>∈ R,由 R对称得
<x,b>∈ R又由 R传递得 <a,b>∈ R,产生矛盾。
若 [a]R∩[b]R=Φ,而 <a,b>∈ R,由等价类定义得 b∈ [a]R,
又因为 bRb,所以 b∈ [b]R,所以 b∈ [a]R∩[b]R,产生矛盾。
⑶ [a]R=[b]R 当且 仅当 <a,b>∈ R。
证明:若 <a,b>∈ R,则任何 x∈ [a]R,有 <a,x>∈R,由对称性得 <b,a>∈R,再由传递性得 <b,x>∈R,∴x∈ [b]R,
所以 [a]R?[b]R。 类似可证 [b]R?[a]R。 ∴ [a]R=[b]R。
如果 [a]R=[b]R,由于有 aRa,所以 a∈ [a]R,a∈ [b]R,
所以有 <b,a>∈ R,由对称性得 <a,b>∈R.
⑷,A中任何元素 a,a必属于且仅属于一个等价类。
证明,A中任何元素 a,由于有 aRa,所以 a∈ [a]R,如果
a∈ [b]R,所以有 <a,b>∈ R.由性质⑶得 [a]R=[b]R 。
⑸,任意两个等价类 [a]R,[b]R,
要么 [a]R=[b]R,要么 [a]R∩[b]R=Φ。
(因为要么 <a,b>∈ R,要么 <a,b>?R。 )
⑹ R的所有等价类构成的集合是 A的一个划分。
(由性质⑷⑸即得。 ) (这个划分称之为 商集 )
三,商集商”和除法有关,比如把 一块蛋糕 平均分成四份,从两种不同的角度看这件事:
从算术角度看,1用 4除,每份 1/4,这就是“商”,于是,
1=1/4+1/4+1/4+1/4
从集合角度看,
集合 A用模 3同余关系 R划分,得到三个等价类,所以
A {{1,4,7},{2,5},{3,6}}={[1]R,[2]R,[3]R}----商集定义,R是 A上等价关系,由 R的所有等价类构成的集合称之为 A关于 R的商集。记作 A/R。即
A/R={[a]R |a∈ A}
用刀分 }{
用 R分生 日 日快 快乐 乐 生例如 A={1,2,3,4,5,6,7},R上模 3同余关系,则
A/R= {[1]R,[2]R,[3]R} ={{1.4.7},{2,5},{3,6}}
练习 X={1,2,3},X上关系 R1,R2,R3,如上图所示。
X/R1={[1]R1,[2]R1,[3]R1}={{1},{2},{3}}
X/R2={[1]R2,[2]R2}={{1},{2,3}}
X/R1={[1]R3}={{1,2,3}}
1。
2。 。 3
R2
1。
2。 。 3
R1

R3

。1
2 3
定理,集合 A上的等价关系 R,决定了 A的一个划分,该划分就是商集 A/R.
证明:由等价类性质可得,
1) A/R中任意元素 [a]R,有 [a]R?A,
2) 设 [a]R,[b]R是 A/R的两个不同元素,有 [a]R?[b]R=Φ
3) 因为 A中每个元素都属于一个等价类,所以所有等价类的并集必等于 A。
所以商集 A/R是 A的一个划分。
定理,设 R1和 R2是非空集合 A上的等价关系,则
A/R1=A/R2 当且仅当 R1=R2 。
(这个定理显然成立。 )
四,由划分确定等价关系例如,X={1,2,3,4},
A={{1,2},{3},{4}},A是 X
的一个划分,求 X上一个等价关系 R,使得 X/R=A。
显然 R的图如右图所示:
R={1,2}2∪ {3}2∪ {4}2 。
一般地 A={A1,A2,…,A n}是 X的一个划分,则构造一个 X中的等价关系 R,使得 X/R=A。
R= A1∪ A2∪,…,∪ An 其中 Ai= Ai× Ai,
下面证明 R是 X中的等价关系。
等价关系 集合的划分
A/R

2。
1。 3。
4。
2 2 2 2
定理,集合 X的一个划分可以确定 X上 的一个等价关系。
证明:假设 A={A1,A2,...,An}是 X的一个划分,如下构造
X 上 的一个等价关系 R,
R= A1∪ A2∪,…,∪ An 其中 Ai = Ai× Ai,(i=1,2…n).
1) 证 R自反,任取 a∈ X,因为 A是 X的划分,必存在
Ai?A使 x?Ai,于是 <a,a>∈ Ai× Ai,又 Ai× Ai?R∴ 有 aRa。
2) 证 R对称,任取 a,b∈ X,设 aRb,必存在 Ai?A使得
<a,b>∈ Ai× Ai,于是 a,b?Ai,?bRa,R是对称的。
3) 证 R传递,任取 a,b,c∈ X,设 aRb,bRc,必存在 Ai?A使得 <a,b>∈ Ai× Ai,<b,c>∈ Ai× Ai,
(不可能有另一个划分块 Ak?A使得 <b,c>∈ Ak× Ak,因为如果这样,就使得,既 b∈ Ai又 b?Ak,与 A是划分矛盾。 )
于是 a,b,c?Ai,所以 <a,c>∈ Ai× Ai,又 Ai× Ai?R∴ 有 aRc
所以 R传递。 最后得 R是集合 X中的关系。
2 2 2 2
本节重点:
等价关系概念、证明。
等价类概念、性质。
求商集。
作业,第 134页
⑴、⑵、⑷、⑹、⑺
4-9 相容关系相容关系是另一种常见关系,如朋友关系、同学关系等。
这些关系的共性是自反的、对称的。
一,定义,给定集合 X上的关系 r,若 r是自反的、
对称的,则 r是 A上 相容关系。
例子,X 是由一些英文单词构成的集合。
X={fly,any,able,key,book,pump,fit},X上关系 r:
r={<α,β>|α∈ X,β∈ X且 α与 β含有相同字母 }
r的有向图:
看出有自反、
对称性。而不传递。
any。
。 ablefly。
key。
。 book
pump。
fit。
y
b
k
l
y
f y
二,简化图和简化矩阵图的简化,⑴不画环;
⑵两条对称边用一条无向直线代替。
令 x1=fly,x2= any,x3= able,x4=key,x5=book,x6= pump,
x7= fit,X={x1,x2,x3,x4,x5,x6,x7},r的简化图为:
矩阵的简化,因为 r的矩阵是对称阵且主对角线全是 1,
用下三角矩阵 (不含主对角线 )代替 r的矩阵。如上图所示。
x2。
x1。 。 x3
x4。
x5。
x6。
x7。
x1 x2 x3 x4 x5 x6
x7
x6
x5
x4
x3
x2 1
1
1
1
1
11
1 1
0
0 0
0 0 0 0
0 0 0
0
0
三,相容类及最大相容类在等价关系中讨论了等价类,这里要讨论相容类。
定义,设 r是集合 X上的相容关系,C?X,如果对于 C中任意两个元素 x,y有 <x,y>∈ r,称 C是 r的一个 相容类 。
上例中 {x1,x2},{x3,x4},{x1,x2,x3},{x2,x3,x4},{x1,x2,x4},
{x3,x4,x5},{x1,x3,x4},{x1,x2,x3,x4},{x1,x7},{x6} 都是相容类。
上述相容类中,有些相容类间有真包含关系。
下面定义最大相容类。
定义,设 r是集合 X上的相容关系,C是 r的一个相容类,
如果 C不能被其它 相容类所真包含,则称 C是一个 最大相容类。
也可以说,C是一个相容类,如果 C中加入任意一个新元素,就不再是相容类,C就是一个 最大相容类。
{x1,x2,x3,x4},{x3,x4,x5},{x1,x7},{x6}都是 最大相容类。
从简化图找最大相容类,------找最大完全多边形。
最大完全多边形,含有结点最多的多边形中,每个结点都与其它结点相联结。
一个孤立顶点 --------完全 0边形;
两个结点间有连线 (非三角形中的一边 ) ---完全 1边形;
三角形 ------完全 3边形;完全 4边形,… 如下图所示:
在相容关系简化图中,每个最大完全多边形的结点集合构成一个最大相容类。
上例中最大相容类 {x1,x2,x3,x4},{x3,x4,x5},{x1,x7},{x6}
分别对应最大完全四、三、一、零边形。
。 。 。x
1。 。 。
。 。 。 。
给定 X上相容关系 r’,如图所示,
r’的最大相容类,{x1,x2,x5},
{x2,x3,x5},{x3,x4,x5},
{x1,x4,x5},
四,完全覆盖,
定义,r是中的相容关系,由 r的所有 最大相容类为元素构成的集合,称之为 X的完全覆盖。记作 Cr(X)。
Cr(X)={{x1,x2,x3,x4},{x3,x4,x5},{x1,x7},{x6}}
Cr’(X)={{x1,x2,x5},{x2,x3,x5},{x3,x4,x5},{x1,x4,x5}}
本节要求,相容关系、相容类概念,画图,求完全覆盖。
作业 第 139页 (2)
x2。 x3 。
x1。 x4。
x5。
4-10 次序关系次序关系也是常遇到的重要关系,例如:
数值的 ≤、<,≥、>关系;
集合的?,?关系;
图书馆的图书按书名的字母次序排序;
词典中的字 (词 )的排序;
计算机中文件按文件名排序;
程序按语句次序执行; …….
本节讨论几种次序关系。
一,偏序关系 (partial order relation)
1,定义,R是 A上自反、反对称和传递的关系,则称 R
是 A上的偏序关系。并称 <A,R>是偏序集。
例如数值的 ≤,≥关系和集合的?都是偏序关系。
因为数值 ≤是熟知的偏序关系,所以用符号,≤”表示任意偏序关系,但要 注意 !!“≤”不一定是“小于或等于”的含义 。
例 1 A={1,2,4,6},≤是 A中的整除关系,其关系图如右图,显然
≤是自反、反对称和传递的,即它是个偏序。
2,x与 y是可比较的,<A,≤>是偏序集,x,y∈ A,如果要么 x≤y,要么 y≤x,则称 x与 y是可比较的。
上例中 1,2,4或 1,2,6间是可比较的。而 4与 6间是不可比较的
2。
1。

6
4
二,全序 (线序、链 )
定义,<A,≤>是偏序集,任何 x,y∈ A,如果 x与 y都是可比较的,则称 ≤是全序关系 (线序、链 )。
例 2 B={1,2,4,8},≤表示整除关系,
则 ≤是全序关系,如图:
全序关系一定是偏序关系,但是偏序不一定是全序。
偏序关系的有向图,不能直观地反映出元素之间的次序,
所以下面介绍另外一种图 ---Hasse图。通过这个图,就能够清晰地反映出元素间的层次。
下面介绍 Hasse图。
2。
1。

8
4
三,偏序集的哈斯图 (Hasse图 )
<A,≤>是偏序集,x,y∈ A
1.元素 y盖住元素 x:如果 x≤y,且 x≠y,且不存在 z∈ A,使得 z≠x∧ z≠y∧ x≤z∧ z≤y,则称 元素 y盖住元素 x。
元素 y盖住 x?x≤y∧ x≠y∧z(z∈ A∧ z≠x∧ z≠y∧ x≤z∧ z≤y)
即元素 y盖住元素 x?不存在 z∈ A,使得 z介于 x与 y之间。
上例中 4没有盖住 1,因为中间有个 2,1≤2≤4.
2.偏序集 Hasse图的画法,令 <A,≤>是偏序集,
1.用,”表示 A中元素。
2.如果 x≤y,且 x≠y,则结点 y要画在结点 x的上方。
3,如果 x≤y,且 y盖住 x,x与 y之间连一直线。
4,一般先从最下层结点 (全是射出的边与之相连 (不考虑环 )),逐层向上画,直到最上层结点 (全是射入的边与之相连 )。 (采用抓两头,带中间的方法 )

例如,前边两个例子:
它们的H asse图分别如下:
可见右图,是全序,它的H asse图是一条直线,所以全序 也叫 线序,或 链 。是从它的 Hasse图得名。
下面作 练习,教材第 146页 (7)
2。
1。

6
4 2。
1。

8
4
1 。
2 。
4 。6 。
1 。
2 。
4 。
8 。
4。
1。
3。2。
3。
4。
1。
2。
1 。 2 。
4 。3。
4。
2 。
1。
3。
全序练习:
C={1,2,3,6,12,24,36},D={1,2,3,5,6,10,15,30}
≤ 是 C,D上 整除关系,<C,≤>,<D,≤>的 Hasse图:
以及 A={a,b,c} <P(A),?>的 Hasse图:
练习:
C={1,2,3,6,12,24,36},D={1,2,3,5,6,10,15,30}
≤ 是 C,D上 整除关系,<C,≤>,<D,≤>的 Hasse图:
以及 A={a,b,c} <P(A),?>的 Hasse图:
6 。
1 。 3 。
12。
2 。
24。 36。 30。
3。
1 。
2。 5。
1 0。 1 5。6。
{a,b,c}。
{b}。
Φ。
{a}。 {c}。
{a,c}。 {b,c}。{a,b}。
<C,≤> <D,≤> <P(A),? >
四,偏序集中的重要元素在格和布尔代数中,要用到下面一些术语。
设 <A,≤>是偏序集,B是 A的非空子集。
一,极小元与极大元
y是 B的 极小元y(y∈ B∧x(x∈ B∧ x≠y∧ x≤y))
(在 B中没有比 y更小的元素了,y就是 极小元 )
y是 B的 极大元y(y∈ B∧x(x∈ B∧ x≠y∧ y≤x))
(在 B中没有比 y更大的元素了,y就是 极大元 )
举例,给定 <A,≤>的 Hasse图如图所示:
从 Hasse图找极小 (大 )元:子集中处在最下 (上 )层的元素是极小 (大 )
元。
6 。
1 。 3 。
12。
2 。
24。 36。
子集 B 极小元 极大元
{2,3}
{1,2,3}
{6,12,24}
C
2,3 2,3
1 2,3
6 24
1 24,36
二,最小元与最大元
y是 B的 最小元y(y∈ B∧?x(x∈ B?y≤x))
(最小元 y是 B中元素,该元素比 B中所有元素都小 )
y是 B的 最大元y(y∈ B∧?x(x∈ B?x≤y))
(最大元 y是 B中元素,该元素比 B中 所有元素都大 )
举例,给定 <A,≤>的 Hasse图如图所示:
从 Hasse图找 最小 (大 )元:子集中如果只有唯一的极小 (大 )元,则这个极小 (大 )元,就是最小 (大 )元。否则就没有最小 (大 )元。
下面介绍 最小 (大 )元的唯一定理。
6 。
1 。 3 。
12。
2 。
24。 36。子集 B 最小元 最大元
{2,3}
{1,2,3}
{6,12,24}
C
无 无
1 无
6 24
1 无定理,<A,≤>是偏序集,B是 A的非空子集,如果 B有最小元 (最大元 ),则最小元 (最大元 )是唯一的。
证明,假设 B有两个最小元 a,b,则因为 a是 最小元,b∈ B,根据 最小元定义,有 a≤b;
类似地,因为 b是 最小元,a∈ B,根据 最小元定义,有
b≤a。因为 ≤有反对称性,所以有 a=b。
同理可证 最大元的唯一性。
小结,<A,≤>是偏序集,B是 A的非空子集,则
⑴ B的 极小 (大 )元总是存在的,就是子集中处在最下 (上 )
层的元素是极小 (大 )元。
⑵ B的 最小元 (最大元 )有时可能不存在,只有有唯一的极小 (大 )元,则这个极小 (大 )元就是最小 (大 )元。否则就没有最小 (大 )元。
3.上界与下界 (Upper Bound and Lower Bound)
y是 B的 上界y(y∈ A∧?x(x∈ B?x≤y))
(上界 y是 A中元素,该元素比 B中所有元素都大 )
y是 B的 下界y(y∈ A∧?x(x∈ B?y≤x))
(下界 y是 A中元素,该元素比 B中 所有元素都小 )
举例,给定 <A,≤>的 Hasse图如图所示:
从 Hasse图找 上 (下 )界,注意 是在 A中找!
6 。
1 。 3 。
12。
2 。
24。 36。
子集 B 上界 下界
{2,3}
{1,2,3}
{6,12,24}
C
1
6,12,24,36 1
24 6,2,3,1
1无
6,12,24,36
4,最小上界 (上确界 )和最大下界 (下确界 )
(Least Upper Bound and Greatest Lower Bound)
定义,y是 B的上界,并且对 B的所有上界 x,都有 y≤x,则称 y是 B的 最小上界 (上确界 ),记作 LUB B=y 。
(即 y是上界中最小的。如果 B有上确界,则是唯一的 )
y是 B的下界,并且对 B的所有下界 x,都有 x≤y,则称 y是 B的 最大下界 (下确界 ),记作 GLB B=y 。
(即 y是下界中最大的。如果 B有上确界,则是唯一的 )
举例,给定 <A,≤>的 Hasse图如图所示:
6 。
1 。 3 。
12。
2 。
24。 36。
子集 B 上界 下界
{2,3}
{1,2,3}
{6,12,24}
C
1
6,12,24,36 1
24 1,2,3,6
1无
6,12,24,36
上确界 下确界
6
6
24

1
1
6
1
* 五,良序定义,<A,≤>是偏序集,如果对 A的任何非空子集 B,都有最小元,则称 ≤是 A上的良序,并称 <A,≤>为良序集。
例如 N是自然数集合,I是整数集合,≤是小于或等于关系,<N,≤>就是 良序集。而 <I,≤>不是良序集。
定理,所有 良序集,一定是全序集。
证明,设 <A,≤>为良序集,任取 x,y∈ A,构成子集 {x,y},它有最小元,该最小元或是 x,或是 y,于是有 x≤y或 y≤x,所以 <A,≤>是全序集。
定理,有限的 全序集,一定是良序集。
证明:设 A={a1,a2,…a n},<A,≤>是全序集,假设它不是良序,必存在非空子集 B?A,B中无最小元,因 B是有限集,
必存在 x,y∈ B,使得 x y,与 ≤是全序矛盾,∴ <A,≤>是良序集。

本节要求:
掌握偏序,全序的概念,
会画 Hasse图,
会求重要元素。
作业 第 145页 (1),(6),(7)
本章小结 枚举法有向图矩阵
*等价关系 有向图等价类商集划分偏序关系相容类最大相容类完全覆盖简化图全序哈斯图重要元素计算方法运算性质二元关系概念及表示方法性质*
自反对称传递反对称反自反相容关系运算复合求逆闭包谓词
*
*
第四章 习题课第 104页⑴ b) A={0,1} B={1,2} 求 A2× B。
A?B={<x,y>|x?A∧ y?B}
A2 =A× A={<0,0>,<0,1>,<1,0>,<1,1> }
A2× B={<<0,0>,1>,<<0,1>,1>,<<1,0>,1>,<<1,1>,1>,
<<0,0>,2>,<<0,1>,2>,<<1,0>,2>,<<1,1>,2> }
第 109页⑴ X={a,b,c} Y={s} X到 Y的所有关系:
X× Y={<a,s>,<b,s>,<c,s>}
X× Y的任何一个子集都是一个 从 X到 Y的关系。如果
|X|=m |Y|=n则有 2mn个从 X到 Y的关系,故,有 23=8个关系,
R0=Φ
R1={<a,s>} R2={<b,s>} R3={<c,s>}
R4={<a,s>,<b,s>} R5={<a,s>,<c,s>} R6={<b,s>,<c,s>}
R7={<a,s>,<b,s>,<c,s>}
⑵ 设 |A|=n,有多少个 A上的关系?
因为 R?A× A,所以 A× A有多少个子集就有多少个 A上关系,由集合的幂集就是该集合的子集构成的,所以 A上关系个数就是 A× A 的幂集 P(A× A)的元素个数 |P(A× A)|,
而 2|A× A|=2nn= 。所以有 个不同的 A上关系。
第 113页⑴ A={1,2,3},A上五个关系如下,(T略有改动 )
2n2
。。

1
32 。。

1
32 。。

1
32 。。

1
32 。。

1
32
R S T Φ A× A
R
A× A
Φ
T
S
自反 反自反 对称 反对称 传递
N N N Y Y
Y N Y N YY N N Y Y
N Y Y Y Y
Y N Y N Y
2n2
上述五个关系中,
哪些是等价关系?如果是等价关系,求其商集。
哪些是相容关系?如果是相容关系,求其完全覆盖。
哪些是偏序关系?如是偏序关系,画 Hasse图,并求A的极小 (大 )元、最小 (大 )元、上界与下界、上确界和下确界。
等价关系,S和 A× A,对应的商集分别是:
A/S={{1,2},{3}} A/A× A={{1,2,3}}
相容关系,S和 A× A,对应的完全覆盖分别是:
CS(A)={{1,2},{3}} CA× A(A)={{1,2,3}}
偏序关系,T
A的极小元、最小元、下界、下确界都是,1
A的极大元、最大元、上界、上确界都是,3 1。
2。
3。
第 118页⑴ R和 S都是 A上关系,
a) R和 S都自反,一定自反。
因为任取 a∈ A,由于 R和 S都自反,所以 <a,a>∈ R 及
<a,a>∈ S 故 <a,a>∈ ∴ 自反,
b) R和 S都反自反,不一定反自反。举反例:
c) R和 S都对称,不一定对称。
d) R和 S都传递,不一定传递。
R So
R So
R So
R So
R So
R So
。1 。 2 。1 。 2 。1 。 2R S R So
。 a
。 c
。 a
。 cb。
。 a
。 cb。
R S
。 a
。 cb。
。 a
。 cb。
。 a
。 cb。
R S R So
R So
⑵ S是X上关系。
a)证明S传递,当且仅当 (可用此定理判定传递 )
证明,充分性,已知任取 x,y,z∈ X,且有 <x,y>∈ S,<y,z>∈ S,根据关系的复合得
<x,z>∈,由已知得 <x,z>∈ S,所以S传递。
必要性,已知S传递,
任取 <x,y>∈,根据关系的复合得
z(z∈ X∧ <x,z>∈ S∧ <z,y>∈ S),由S传递得 <x,y>∈ S
所以
b)证明S自反,当且仅当 IX?S。 (可用此定理判定自反 )
证明,充分性,已知 IX?S,
任取 x∈ X,有 <x,x>∈ IX,由已知得 <x,x>∈ S,所以S自反。
必要性,已知S自反,
任取 <x,y>∈ IX,得 x=y,而 S自反,所以 <x,y>∈ S∴ IX?S
S S?So
S S?So
S So
S So
S S?So
⑶ S是X上关系,证明S是自反和传递,则 =S。 其逆为真吗?
证明,由⑵ a)得S传递,则,只证明 S?
任取 <x,y>∈ S,又已知S自反,所以 <x,x>∈ S,于是有
<x,x>∈ S∧ <x,y>∈ S,由关系的复合得 <x,y>∈
所以有 S?,最后得 =S。
其逆不一定为真。例如 S如图所示:
它满足 =S,但S不自反。
⑸ R是 A上关系,
a)R自反,Rc也自反。
因为任取 x∈ A,因 R自反,所以 <x,x>∈ R,∴ <x,x>∈ Rc
b) R对称,Rc也对称。
因为 R对称,所以 Rc =R ∴ Rc也对称。
S So
S S?So S So
S So
S So S So
S So
。 a
。 cb。

c) R传递,Rc也传递。
方法 1,任取 x,y,z∈ A,且有 <x,y>∈ Rc,<y,z>∈ Rc,于是
<y,x>∈ R,<z,y>∈ R,因 R传递,∴ <z,x>∈ R,于是有
<x,z>∈ Rc,∴ Rc传递。
方法 2,t(Rc)=Rc∪ (Rc)2∪ (Rc)3∪ …
= Rc∪ (R2)c∪ (R3)c∪ …
= (R∪ R2∪ R3∪ …) c
= (t(R))c=Rc (因为 R传递,所以 t(R)=R )
所以 Rc传递。
(R2)c= (R?R)c=(Rc?Rc)= (Rc)2
归纳:关系性质证明方法设 R是 A上关系,
一,证明 R的自反性:
方法 1 用自反定义证:任取 x∈ A,证出 <x,x>∈ R.
方法 2 用恒等关系 IA证,证出 IA?R,( P119 (2) b) )
方法 3 用自反闭包证,证出 r(R)=R,即 R∪ IA=R.
二,证明 R的反自反性:
方法 1 用反自反定义证:任取 x∈ A,证出 <x,x>?R.
三,证明 R的对称性:
方法 1 用对称定义证:
任取 x,y∈ A,设 <x,y>∈ R,证出 <y,x>∈ R.
方法 2 用求逆关系证,证出 Rc=R.
方法 3 用对称闭包证,证出 s(R)=R,即 R∪ Rc =R.
四,证明 R的反对称性:
方法 1 用定义 1证:
任取 x,y∈ A,设 <x,y>∈ R,<y,x>∈ R.证出 x=y。
方法 2用定义 2证:
任取 x,y∈ A,x≠y,设 <x,y>∈ R,证出 <y,x>?R.
方法 3 用定理证,证出 R∩Rc? IA,(见 教材 P118)
五,证明 R的传递性:
方法 1 用传递定义证:
任取 x,y,z∈ A,设 <x,y>∈ R,<y,z>∈ R,证出 <x,z>∈ R.
方法 2 用传递闭包证,证出 t(R)=R,
即 R∪ R2∪ R3∪,.,=R.
方法 3用定理证,证出 ( P119 (2) a) )
下面证明第 113页 (4)
R R?Ro
P113(4)R和 S都 A上是自反、对称、传递的,求证 R∩S也是自反、对称和传递的。
证明,一,证明 R∩S的自反性方法 1 用自反定义证:任取 x∈ A,(证出 <x,x>∈ R∩S)
因 R和 S都自反,所以有 <x,x>∈ R,<x,x>∈ S,于是有
<x,x>∈ R∩S,所以 R∩S也自反。
方法 2 用恒等关系 IA证,(证出 IA?R∩S)
因 R和 S都自反,所以 IA?R,IA?S,所以 IA?R∩S
所以 R∩S也自反。
方法 3 用自反闭包证:
(证出 r(R∩S)=R∩S,即 (R∩S)∪ IA= R∩S)
因 R和 S都自反,所以 r(R)=R,r(S)=S,
r(R∩S)=(R∩S)∪ IA= (R∪ IA)∩(S∪ IA)= r(R)∩r(S)=R∩S
所以 R∩S也自反。
二,证明 R∩S 的对称性:
方法 1 用对称定义证:
任取 x,y∈ A,设 <x,y>∈ R∩S,(证出 <y,x>∈ R∩S,)
则 <x,y>∈ R,<x,y>∈ S,因为 R和 S对称,所以有
<y,x>∈ R,<y,x>∈ S,于是 <y,x>∈ R∩S 。 ∴ R∩S 对称。
方法 2 用求逆关系证,(证出 (R∩S )c=R∩S,)
因为 R和 S对称,所以有 Rc=R,Sc=S,而
(R∩S )c=Rc∩S c= R∩S,∴ R∩S 对称。
方法 3 用对称闭包证:
(证出 s(R∩S )=R∩S,即 (R∩S )∪ (R∩S )c =R∩S,)
因为 R和 S对称,所以 s(R)=R,s(S)=S
s(R∩S )= (R∩S )∪ (R∩S )c =(R∩S )∪ (Rc∩S c)
=(R∪ Rc)∩ (R∪ Sc)∩ (S∪ Sc)∩ (S∪ Rc)
=(s(R)∩ (R∪ Sc))∩ (s(S)∩ (S∪ Rc))
=(R∩ (R∪ Sc))∩ (S∩ (S∪ Rc))=R∩ S (吸收律 )
∴ R∩S 对称。
五,证明 R的传递性:
方法 1 用传递定义证:任取 x,y,z∈ A,
设 <x,y>∈ R∩S,<y,z>∈ R∩S,(证出 <x,z>∈ R∩S )
<x,y>∈ R∩S ∧ <y,z>∈ R∩S
<x,y>∈ R∧ <x,y>∈ S∧ <y,z>∈ R∧ <y,z>∈ S
(<x,y>∈ R∧ <y,z>∈ R)∧ (<x,y>∈ S ∧ <y,z>∈ S)
<x,z>∈ R∧ <x,z>∈ S (因为 R,S传递)
<x,z>∈ R∩S 所以 R∩S 传递。
方法 2 用传递闭包证,证出 t(R∩S )=R∩S,
即 (R∩S )∪ (R∩S )2∪ (R∩S )3∪,.,=R∩S,
方法 3用定理证,证出用 方法 2,方法 3证明此题的传递性有很大难度。
R?(S∩T)?(R?S)∩(R?T)
希望同学们灵活掌握证明关系性质的方法 。
(R∩S ) (R∩S )?(R∩S )o
P127(1)R的有向图如图所示,求 r(R),s(R),t(R)。
(5)R1和 R2是 A上关系,且 R2?R1,求证
a) r(R2)?r(R1),b) s(R2)?s(R1),c) t(R2)?t(R1)。
证明,a) r(R2)=R2∪ IA?R1∪ IA=r(R1),
b) s(R2)= R2∪ (R2)c?R1∪ (R1)c =s(R1),
(因为 R2?R1,所以 (R2)c?(R1)c )
c) 先用归纳法证明 (R2)i?(R1)i,
⑴ i=1时,R2?R1 显然结论成立
⑵假设 i≤k时,结论成立,即 (R2)i?(R1)i;
⑶ i=k+1时,(R2)k+1= (R2)k R2?(R1)k R1=(R1)k+1,
t(R2) =R2∪ (R2)2∪,..∪ (R2)k∪,..
R1∪ (R1)2∪,..∪ (R1)k∪ …= t(R1)。 c)的另一证法,
R
。 a
。 cb。
。 a
。 cb。
。 a
。 cb。
。 a
。 cb。r(R) s(R) t(R)
。 。
c) 因为 R2?R1,又 R1?t(R1),所以 R2?t(R1)。 于是有
t(R2)和 t(R1)都是包含 R2的传递关系,而 t(R2)是包含 R2的最小的传递关系,所以 t(R2)?t(R1)。
(7),R1和 R2是 A上关系,求证
a) r(R1∪ R2)=r(R1)∪ r(R2),
b) s(R1∪ R2)= s(R1)∪ s(R2),
c) t(R1)∪ t(R2)? t(R1∪ R2),
证明,a) r(R1∪ R2)= (R1∪ R2)∪ IA= (R1∪ IA) ∪ (R2∪ IA)
=r(R1)∪ r(R2),
b) s(R1∪ R2)= (R1∪ R2)∪ (R1∪ R2)c
=(R1∪ R2)∪ (R1)c∪ (R2)c =(R1∪ (R1)c )∪ (R2∪ (R2)c)
=s(R1)∪ s(R2),
c)因 R1? (R1∪ R2)且 R2?(R1∪ R2),由题 (5)得
t(R1)?t(R1∪ R2),t(R2)?t(R1∪ R2),所以有
t(R1)∪ t(R2)? t(R1∪ R2)。
(8),R是 A上关系,R*=tr(R),求证,
a) (R+)+=R+ b) R R*=R+=R* R c) (R*)*=R*
R+ = t(R)=R∪ R2∪ R3∪ …=
R*=rt(R)= IA∪ R∪ R2∪ R3∪,.,=
证明,a) (R+)+=t(t(R)),因为 t(R)是传递的,所以
t(t(R))=t(R),即 (R+)+=R+ 。
b) R R*=R (IA∪ R∪ R2∪ R3∪,.,) ∵ 复合对并可分配,
=R∪ R2∪ R3∪ …= R +。
类似可证 R* R= R+
c) (R*)*=tr(tr(R))=trtr(R)=trrt(R) (∵ tr(R)=rt(R))
=trt(R) (∵ rt(R)是自反的,∴ rrt(R)=rt(R))
=ttr(R)
=tr(R) (∵ tr(R)是传递的,∴ ttr(R)=tr(R))
=R*
。 。
。 。

∪ Rii=1∞
∪ Rii=0∞
第 130页 (1).X是集合,且 |X|=4,X有多少个不同的划分?
解,
第 134页 (2),X是集合,且 |X|=4,X上有多少个不同的等价关系?
解,此题的答案与上题一样。因为每个划分对应一个等价关系。
划分块数 各块元素个数 相应划分个数 总数
1 4 C44 = 1
1 3 C41 = 4
2 2 1/2C42 = 32
3 1 1 2 C42 = 6
4 1 1 1 1 C44 =1
15
(4),R是 A上关系,设
S={<a,b>|?c∈ A∧ <a,c>∈ R∧ <c,b>∈ R}
求证若 R是等价关系,则 S也是等价关系。
证明,a)证 S自反,任取 a∈ A,∵ R是自反的,∴ 有
<a,a>∈ R,由 S定义得 <a,a>∈ S,(S定义中 c就是 a)∴ S自反,
b)证 S对称,任取 a,b∈ A,且有 <a,b>∈ S,由 S定义得
c∈ A∧ <a,c>∈ R∧ <c,b>∈ R,由 R对称得
c∈ A∧ <b,c>∈ R∧ <c,a>∈ R,由 S定义得 <b,a>∈ S,S对称,
c)证 S传递,任取 a,b,c∈ A,有 <a,b>∈ S,<b,c>∈ S,由 S定义得
(?d∈ A∧ <a,d>∈ R∧ <d,b>∈ R)∧ (?e∈ A∧ <b,e>∈ R∧ <e,c>∈ R),
由于 R传递,所以有 <a,b>∈ R,<b,c>∈ R,
由 S定义得 <a,c>∈ S,所以 S传递,所以 S是 A上等价关系,
(6),R是 A上对称和传递的关系,证明如果?a∈ A,?b∈ A,
使得 <a,b>∈ R,则 R是一个等价关系,
证明,任取 a∈ A,有已知得?b∈ A,使得 <a,b>∈ R,由 R对称得 <b,a>∈ R,又由 R传递得,<a,a>∈ R,R自反,∴ R是等价关系,
(1)(7).R和 S都是 A上等价关系,下面哪个是 A上等价关系?
证明或举反例说明,
a) R∪ S b) R∩S c) ~R (即 A× A-R)
d) R-S e)R2 f) r(R-S)
解,a) c) d) f)不是,请看反例,
R
。 a
。 cb。
。 a
。 cb。
。 a
。 cb。S R∪ S
。 a
。 cb。 ~R
。 a
。 cb。 R’
。 a
。 cb。 R’-S
。 a
。 cb。 r(R’-S)
b),R∩S是等价关系,前面已经证明过,(第 113页题 (4))
e).① 证 R2自反,任取 a∈ A,因为 R自反,所以 <a,a>∈ R,根据关系的复合得,<a,a>∈ R R,即 <a,a>∈ R2,所以 R2自反。
② 证 R2对称,(R2)c=(Rc)2=R2 (由 R对称得 Rc=R) ∴ R2对称
③ 证 R2传递,任取 a,b,c∈ A,设有 <a,b>∈ R2,<b,c>∈ R2,
根据关系的复合得,
(?d∈ A∧ <a,d>∈ R∧ <d,b>∈ R)∧ (?e∈ A∧ <b,e>∈ R∧ <e,c>∈ R),
由于 R传递,所以有 <a,b>∈ R,<b,c>∈ R,∴ <a,c>∈ R2
所以 R2传递。最后得 R2是等价关系。
第 139页 (2),X={x1,x2,x3,x4,x5,x6},R是 X上相容关系,
其简化关系矩阵如下:求 X的完全覆盖。
解,R的简化图为:
CR(X)={{x1,x2,x3,},{x1,x3,x6},{x3,x4,x5},{x3,x5,x6}}
o
x2 1
x3 1 1
x4 0 0 1
x5 0 0 1 1
x6 1 0 1 0 1
x1 x2 x3 x4 x5
x1 。 。 x2
x6 。
x5 。 。 x4
。 x3
第 145页 (1),给定集合 {3,5,15},{1,2,3,6,12},{3,9,27,54},
≤为整除关系,分别画出上述集合上的 ≤的关系图,
Hasse图,并指出哪些是全序关系。
全序

。 。

。 。。

1
2 36
1215
53

。 。

27
54
9
3

。 。

。 。


1
2 3
6
1215
53




27
54
9
3
(6),P={x1,x2,x3,x4,x5},P上偏序关系的
Hasse图如图所示,求子集 {x1,x2,x3},
{x2,x3,x4},{x3,x4,x5}和 P的极小 (大 )元、
最小 (大 )元、上界、下界、最小上界和最大下界 (上确界和下确界 )。

。 。
。。
x1
x2 x3
x4 x5
子 集 极小元 极大元 最小元 最大元 上界 下界 上确界 下确界
{x1,x2,x3} x2,x3 x1 无 x1 x1 x4 x1 x4
{x2,x3,x4} x4 x2,x3 x4 无 x1 x4 x1 x4
{x3,x4,x5} x4,x5 x3 无 x3 x1,x3 无 x3 无
P x4,x5 x1 无 x1 x1 无 x1 无第四章 二元关系到此结束