第七章: 二元关系 主要内容 本章与后面各章的关系 有序对与笛卡儿积 二元关系的定义与表示法 关系的运算 关系的性质 关系的闭包

Presentation on theme: "第七章: 二元关系 主要内容 本章与后面各章的关系 有序对与笛卡儿积 二元关系的定义与表示法 关系的运算 关系的性质 关系的闭包"— Presentation transcript:

1 第七章: 二元关系 主要内容 本章与后面各章的关系 有序对与笛卡儿积 二元关系的定义与表示法 关系的运算 关系的性质 关系的闭包
等价关系与划分 偏序关系 本章与后面各章的关系 是函数的基础 是图论的基础

2 第七章: 二元关系 第一节：有序对与笛卡儿积

3 引言 关系是数学中最重要的概念之一 在计算机科学中有广泛应用 父子关系、师生关系 等于、大于、小于关系 直线的平行、垂直关系 人工智能
程序设计 数据库管理—关系数据库

4 7.1 有序对与笛卡儿积 有序对（序偶）：由两个元素x，y(允许x=y)按给定顺序排列组成的二元组合
例：平面直角坐标系中的一个点的坐标 ＜1,3＞和＜3,1＞是表示平面上两个不同的点 <x，y> = <u，v>当且仅当x=u ，y=v 如果xy，那么＜x，y＞＜y ，x＞

5 7.1 有序对与笛卡儿积 例：已知<x+2,4>=<5,2x+y>，求x,y 解：根据有序对等式定义，只需求解方程式

6 7.1 有序对与笛卡儿积 笛卡尔积A×B：集合A中元素为第一元素，集合B中元素为第二元素的有序对集
A×B={<x，y>xA  yB} 例：设集合A={a，b，c}，B ={0，1}，求A×B，B×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×B)∩(B×A)=

7 7.1 有序对与笛卡儿积 例：设集合A={1，2}，求P(A)A 解： P(A)={，{1}，{2}，{1，2}} P(A)×A
={<，1>，<，2>，<{1}，1>，<{1}，2>，<{2}，1>，<{2}，2>， <{1，2}，1>，<{1，2}，2>}

8 7.1 有序对与笛卡儿积 说明： 如A，B均是有限集，A=m,B=n， 则必有AB=mn

9 7.1 有序对与笛卡儿积 笛卡儿积的性质： 对于任意集合A，A=，A= 一般不满足交换律，当A，B，AB时，
AB  BA 一般不满足结合律，即当A，B，C均非空时，(AB)CA(BC)

10 7.1 有序对与笛卡儿积 笛卡儿积的性质（续）： （1）A(B∪C)=(AB) ∪(AC) 对任意三个集合A，B，C有
（5）A C  B D  A×BC×D

11 7.1 有序对与笛卡儿积 证明： A(B∪C)=(AB) ∪(AC)  xA  y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)

12 7.1 有序对与笛卡儿积 例：设A，B，C，D是任意集合，判断下列命题是否正确？ A-(BC)={1}-{<1,2>}={1}
ABAC  BC 不正确。取A，BC，AB=AC= A-(BC)=(A-B)  (A-C) 不正确。取A=B={1}，C={2}， A-(BC)={1}-{<1,2>}={1} 而(A-B)  (A-C)={1}=

13 7.1 有序对与笛卡儿积 例：设A，B，C，D是任意集合，判断下列命题是否正确？ A=B，C=D  ACBD
正确。 存在集合A使得A  AA 正确。取A=时，AAA

14 第七章: 二元关系 第二节：二元关系

15 7.2 二元关系 关系是指事物之间（个体之间）的相互联系 二元关系R：满足下列条件之一的集合
集合非空，且它的元素都是有序对 集合为空集 定义：A，B是集合，A×B的子集叫做从A到B的一个二元关系 例：A={0，1}，B={1，2，3} R1={<0,2>}，R2={<0,1>} R3=

16 7.2 二元关系 几类特殊关系： 全域关系EA＝A×A 恒等关系IA＝{<x，x>|x∈A} 空关系

17 7.2 二元关系 例： A={0,1,2} EA={<0,0>,<0,1>,<0,2>,<1,0>, <1,1>,<1,2>,<2,0>,<2,1>,<2,2>} 恒等关系IA ={<0,0>,<1,1>,<2,2>}

18 7.2 二元关系 包含关系 例： A={2，3，4，5，6} A是一个集合,定义P(A)上的一个关系
R ={<u，v>uP(A)，vP(A)，且uv} A={a，b}，P(A)={ ，{a}，{b}，A} R={<，{a}>，<，{b}>，<，>，<，A>，<{a}，{a}>，<{a}，A>，<{b}，{b}>，<{b}，A>，<A，A>} 例： A={2，3，4，5，6} R={<a，b>a是b的倍数} R={<2，2> ，<3，3>，<4，2>，<4，4>，<5，5>，<6，2>，<6，3>，<6，6>}

19 7.2 二元关系 关系表示方法 枚举法（直观法、列举法） 谓词公式表示法（暗含法） 关系矩阵表示法 关系图表示法
xRy表示特定的序偶〈x，y〉 R 谓词公式表示法（暗含法） 关系矩阵表示法 关系图表示法

20 7.2 二元关系 关系表示方法 枚举法（直观法、列举法） 谓词公式表示法（暗含法） 关系矩阵表示法 关系图表示法
xRy表示特定的序偶〈x，y〉 R 谓词公式表示法（暗含法） 关系矩阵表示法 关系图表示法

21 7.2 二元关系 关系矩阵表示法 设集合A={a1,…,am},B={b1,…,bn},R是A到B的关系,则R的关系矩阵是一个mn阶的矩阵
MR=(rij)mn 其中rij =1,当<ai,bj>R ri j =0,当<ai,bj>R 如果R是A上的关系时,则其关系矩阵是一个方阵

22 7.2 二元关系 1 0 1 0 0 1 0 1 0 例：A={a,b,c,d},B={x,y,z},A=4，B=3,
R={<a,x>,<a,z>,<b,y>,<c,z>,<d,y>} 则MR是43的矩阵 MR = 其中r13=1表示<a,z>R,而r23=0,表示<b,z>R

23 7.2 二元关系 关系表示方法 枚举法（直观法、列举法） 谓词公式表示法（暗含法） 关系矩阵表示法 关系图表示法
xRy表示特定的序偶〈x，y〉 R 谓词公式表示法（暗含法） 关系矩阵表示法 关系图表示法

24 7.2 二元关系 关系图：A={a1,…,am}，B={b1,…,bn} 结点：m+n个空心点分别表示a1,…,am和b1,…,bn
有向边：如果<ai,bj>R,则由结点ai向结点bj通一条有向弧,箭头指向bj 自回路：<ai,ai>R,则画一条以ai到自身的一条有向弧 这样形成的图称为关系R的关系图

25 7.2 二元关系 例：A={2,3,4,5,6} (1)R1={<a,b>a是b的倍数}
(2)R2={<a,b>(a-b)2A } 5 3 6 4 2 5 3 6 4 2

26 第七章: 二元关系 第三节：关系的运算

27 7.3 关系的运算 二元关系的定义域和值域 例 定义域： 值域： X={1,2,3,4,5,6},Y={a,b,c,d,e,f}
R={<1,a>,<2,b>,<3,c>,<4,d>} domR={1,2,3,4} ranR={a,b,c,d}

28 7.3 关系的运算 二元关系的逆关系 说明 R-1就是将R中的所有有序对的两个元素交换次序成为R-1 ，故|R|=| R-1 |
R-1 的关系矩阵是R的关系矩阵的转置，即 MR-1=(MR)T R-1的关系图就是将R的关系图中的弧改变方向即可以

29 7.3 关系的运算 例： R={<a,a>，<a,d>，<b,d>，<c,a>，<c,b>，<d,c>} R-1={<a,a>，<d,a>，<d,b>，<a,c>，<b,c>，<c,d>} MR= MR-1=MRT=

30 7.3 关系的运算 例： d b c a R的关系图 R-1的关系图
R={<a,a>，<a,d>，<b,d>，<c,a>，<c,b>，<d,c>} R-1={<a,a>，<d,a>，<d,b>，<a,c>，<b,c>，<c,d>} d b c a R的关系图 R-1的关系图

31 7.3 关系的运算 关系的右复合 例 A={1,2,3,4,5},B={3,4,5},C={1,2,3}
R={<x,y>|x+y=6} ={<1,5>,<2,4>,<3,3>} S={<y,z>y-z=2} ={<3,1>,<4,2>,<5,3>} RS={<1,3>,<2,2>,<3,1>}

32 7.3 关系的运算 例（续） 5 4 3 2 1 从而RS的关系图 5 4 3 2 1

33 7.3 关系的运算 例： A={a,b,c,d,e} 注意：RSSR
R={<a,b>,<c,d>,<b,b>} S={<d,b>,<b,e>,<c,a>} RS={<a,e>,<c,b>,<b,e>} SR={<d,b>,<c,b>} RR={<a,b>,<b,b>} SS={<d,e>} 注意：RSSR

34 7.3 关系的运算 定义：R是二元关系，A是集合 R在A上的限制 A在R下的像 A R[A]

35 7.3 关系的运算 例：R = {<1, 2>, <1, 3>, <2,2>, <2,4>, <3,2>}, 求：

36 7.3 关系的运算 优先顺序： 逆运算优先于其他运算 关系运算优先于集合运算 没有规定优先权的运算以括号决定运算顺序

37 7.3 关系的运算 定理：设F是任意的关系，则 (F-1)-1=F domF-1 =ranF, ranF-1 =domF

38 7.3 关系的运算 定理：设F，G，H是任意的关系 证明：<x，y> (FG)-1  <y，x>FG
(FG)H = F(GH) (FG)-1 =G-1F-1 证明：<x，y> (FG)-1  <y，x>FG  t(<y，t>F  <t，x>G)  t(<x，t>G-1  <t，y>F-1)  <x，y>G-1F-1

39 7.3 关系的运算 例 R={<a,a>,<a,c>,<b,b>,<c,b>,<c,c>} S={<a,1>,<a,4>,<b,2>,<c,4>,<c,5>} RS={<a,1>,<b,2>,<c,2>,<a,4>, <c,4>,<a,5>,<c,5>} (RS)-1={<1,a>,<2,b>,<2,c>,<4,a>, <4,c>,<5,a>,<5,c>} R-1={<a,a>, <c,a>,<b,b>,<b,c>,<c,c>} S-1={<1,a>,<4,a>,<2,b>,<4,c>, <5,c>} S-1R-1={<1,a>,<2,b>,<2,c>,<4,a>, <4,c>,<5,a>,<5,c>}

40 7.3 关系的运算 定理: 设R为A上关系，则 RIA＝IAR＝R 定理: R(S∪T)=RS∪RT
(S∪T)X=SX∪TX (S∩T)XSX∩TX

41 7.3 关系的运算 证明 R(S∪T)=RS∪RT <x,z>∈ R(S∪T)
 y(<x,y>∈R∧<y,z>∈S∪T)  y(<x,y>∈R∧(<y,z>∈S∨<y,z>∈T))  y((<x,y>∈R∧<y,z>∈S)∨ (<x,y>∈R∧<y,z>∈T))  y(<x,y>∈R∧<y,z>∈S)∨ y(<x,y>∈R∧<y,z>∈T)  <x,z>∈RS ∨<x,z>∈ RT  <x,z>∈RS∪RT

42 7.3 关系的运算 证明 R(S∩T)RS∩RT
 <x,y>∈R(S∩T)  t (<x,t>∈R∧<t,y>∈S∩T)  t (<x,t>∈R∧<t,y>∈S∧<t,y>∈T)  t ((<x,t>∈R∧<t,y>∈S) ∧(<x,t>∈R∧<t,y>∈T))  t (<x,t>∈R∧<t,y>∈S) ∧t (<x,t>∈R∧<t,y>∈T)  <x,y>∈RS∧<x,y>∈RT  <x,y>∈RS∩RT

43 7.3 关系的运算 定理: R↾(A∪B) = R↾A∪R↾B R[A∪B] = R[A]∪R[B] R↾(A∩B) = R↾A∩R↾B

44 7.3 关系的运算 定理: R[A∩B]  R[A]∩R[B] 证明：y∈R[A∩B]
 x(<x,y>∈R∧x∈A∩B)  x(<x,y>∈R∧x∈A∧x∈B)  x((<x,y>∈R∧x∈A)∧(<x,y>∈R∧ x∈B))  x(<x,y>∈R∧x∈A)∧ x(<x,y>∈R∧ x∈B) y∈R[A]∧y∈R[B] y∈R[A]∩R[B]

45 7.3 关系的运算 R的n次幂 定理: 设R是集合A上的关系，m,n∈N 证明思路：使用归纳法并利用复合关系的结合律 记为Rn R0 =A
Rn+1=RnR 定理: 设R是集合A上的关系，m,n∈N RmRn=Rm+n (Rm)n=Rmn 证明思路：使用归纳法并利用复合关系的结合律

46 7.3 关系的运算 例R={<1,2>,<2,1>,<2,3>,<3,4>,<4,5>} R0= {<1,1>,<2,2>,<3,3>,<4,4>,<5,5>} R1=R R2={<1,1>,<2,2>,<1,3>,<2,4>,<3,5>} R3=R2R ={<1,2>,<2,1>,<1,4>,<2,3>,<2,5>} R4=R3R ={<1,1>,<2,2>,<1,5>,<2,4>,<1,3>} R5=R4R ={<1,2>,<1,4>,<2,1>,<2,3>,<2,5>}

47 7.3 关系的运算 从关系图来看关系的n次幂 R： 1 2 3 4 5 R2就是所有在R中通过二条弧连接的点，则在R2这两点间直接有条弧。
R2就是所有在R中通过二条弧连接的点，则在R2这两点间直接有条弧。 R3,R4…

48 7.3 关系的运算 定理：R是A上的二元关系，若存在自然数s和t，且s<t，使Rs=Rt，则 对所有的k≥0，则Rs+k=Rt+k
对所有的k,i≥0 ，则有Rs+kp+i=Rs+i p=t-s 设S={R0,R1,R2,…,Rt-1}，则R的每一次幂都是S的元素，即对任意q∈N, Rq∈S

49 7.3 关系的运算 定理：R是A上的二元关系，若存在自然数s和t，且s<t，使Rs=Rt 对所有的k≥0，则Rs+k=Rt+k
对所有的k,i≥0 ，则有Rs+kp+i=Rs+i p=t-s 设S={R0,R1,R2,…,Rt-1}，则R的每一次幂是S的元素，即对任意q∈N, Rq∈S

50 7.3 关系的运算 证明：对k进行归纳。 k=0时Rs+kp+i=Rs+i显然成立 假设Rs+kp+i=Rs+i，这里p=t-s ，那么
Rs+(k+1)p+i=Rs+kp+i+p=Rs+kp+iRp =Rs+iRp =Rs+p+i =Rs+t-s+i =Rt+i=Rs+i

51 7.3 关系的运算 定理：R是A上的二元关系，若存在自然数s和t，且s<t，使Rs=Rt 对所有的k≥0，则Rs+k=Rt+k
对所有的k,i≥0 ，则有Rs+kp+i=Rs+i p=t-s 设S={R0,R1,R2,…,Rt-1}，则R的每一次幂是S的元素，即对任意q∈N, Rq∈S

52 7.3 关系的运算 证明：若q<t，则Rq∈S 。 若q≥t，则存在自然数k，i使得 q=s+kp+i 其中0≤ i≤p-1，所以
Rq= Rs+kp+i = Rs+i 由于0≤ i≤p-1 s+i ≤ s+p-1 = s+t-s-1=t-1

53 第七章: 二元关系 第四节：关系的性质

54 7.4 关系的性质 自反性 反自反性 例 A={a,b,c} a∈A，有<a,a>∈R，则R为A上的自反关系
R1={<a,a>,<b,b>,<c,c>,<a,b>,<c,a>} R2={<a,b>,<b,c>,<c,a>} R3={<a,a>,<b,c>}

55 7.4 关系的性质 例：R是I+上的整除关系，则R具有自反性 例：R是I上的同余关系，则R具有自反性 其它≤，≥关系，均是自反关系
证明：x∈I+，x能整除x， ∴<x,x>∈R，∴R具有自反性 例：R是I上的同余关系，则R具有自反性 证明：x∈I，(x-x)/k=0∈I, ∴x与x同余∴<x,x>∈R∴R具有自反性 其它≤，≥关系，均是自反关系

56 7.4 关系的性质 例：N上的互质关系是反自反关系 实数上的＜,＞关系,均是反自反关系 证明：x∈N，x与x是不互质的，
∴<x,x>  R，∴R具有反自反关系 实数上的＜,＞关系,均是反自反关系

57 7.4 关系的性质 关系矩阵的特点？ 关系图的特点？ 定理：R是A上的关系，则： 自反关系的关系矩阵的对角元素均为1
反自反关系的关系矩阵的对角元素均为0 关系图的特点？ 自反关系的关系图中每个顶点都有环 反自反关系的关系图中每个顶点都没有环 定理：R是A上的关系，则： R是自反关系的充要条件是IAR R是反自反关系的充要条件是R∩IA=Ф

58 7.4 关系的性质 对称关系R 例 a,b∈A,如果<a,b>∈R,则必有<b,a>∈R

59 7.4 关系的性质 关系矩阵特点？ 关系图特点？ 定理： R在A上对称当且仅当R=R-1 证明：必要性
对称关系的关系矩阵是对称矩阵 关系图特点？ 如果两个顶点之间有边，一定是一对方向相反的边（无单边） 定理： R在A上对称当且仅当R=R-1 证明：必要性 <x,y>R<y,x>R<y,x>R-1 充分性 <x,y>R<y,x>R-1<y,x>R

60 7.4 关系的性质 反对称关系R 例: A＝{a,b,c}
a,b∈A,如果<a,b>∈R且<b,a>∈R,则必有a＝b a,b∈A,如果a≠b,<a,b>∈R,则必有<b,a>R 例: A＝{a,b,c} R＝{<a,a>,<b,b>} S＝{<a,b>,<a,c>} T＝{<a,c>,<b,a>,<a,b>} R,S是反对称的,T不是反对称的

61 7.4 关系的性质 例: 实数集合上≤关系是反对称关系 例：≥,<,>关系,均是反对称关系 反对称关系矩阵和关系图特点？
x,y∈实数集,如x≠y,且x≤y,则y≤x不成立 例：≥,<,>关系,均是反对称关系 反对称关系矩阵和关系图特点？ 若rij=1，且i≠j， 则rji=0 如果两个顶点之间有边，一定是一条有向边（无双向边） 定理： R在A上反对称当且仅当R∩R-1  IA

62 7.4 关系的性质 传递关系 a,b,c∈A,如果<a,b>∈R,<b,c>∈R, 必有<a,c>∈R 例 R1＝{<x,y>,<z,x>,<z,y>} 是传递关系 R2＝{<a,b>,<c,d>} R3＝{<a,b>,<b,a>} 不是传递关系

63 7.4 关系的性质 例:整除关系DI＋是I＋上的传递关系 例:P(A)上的包含关系具有传递性 例:实数集上的≤关系具有传递性
x,y,z∈I＋,如<x,y>∈DI＋,<y,z>∈DI＋,即x能整除y,且y能整除z,则必有x能整除z, <x,z>∈DI＋ 例:P(A)上的包含关系具有传递性 若uv,vw,则必有uw 例:实数集上的≤关系具有传递性 若x≤y,y≤z必有x≤z

64 7.4 关系的性质 传递关系关系图特点？ 如果结点a能通过有向弧组成的有向路径通向结点x,则a必须有有向弧直接指向x,否则R就不是传递的 例：R={<a,b>,<b,c>,<c,d>,<a,c>} 定理：R在A上传递当且仅当RR  R d c b a

65 7.4 关系的性质 自 反： 反自反： 对 称： 反对称： 传 递：

66 7.4 关系的性质 设A是集合，R1和R2是A上的关系 若R1，R2是自反和对称的，则R1∪R2也是自反的和对称的

67 7.4 关系的性质 设A是集合，R1和R2是A上的关系 若R1，R2是自反的和对称的，则R1∪R2也是自反 的和对称的
证明：R1，R2是自反的 IA R1，IA R2 所以IA R1∪R2 R1，R2是对称的 R1=R1-1和R2=R2-1 所以(R1∪R2)-1=R1-1∪R2-1= R1∪R2

68 7.4 关系的性质 例： X={1,2,3}，判断关系的性质 反自反 反对称 可传递
R1={<1,2>,<2,3>,<1,3>} 反自反 反对称 可传递 R2={<1,1>,<1,2>,<2,3>} 反对称

69 7.4 关系的性质 R3={<1,1>,<2,2>,<3,3>} 自反，对称，反对称，可传递的
R4= Ex 自反，对称，可传递的 自反，对称，反对称，可传递的

70 7.4 关系的性质 X={1,2,3}, R5=  若X=  ，X上的空关系 反自反的，对称的，反对称的，可传递的
自反的，反自反的，对称的，反对称的，可传递的

71 第七章: 二元关系 第五节：关系的闭包

72 7.5 关系的闭包 定义：R是非空集合A上的关系,若A上另外有一个关系R’满足如下三条： R’是自反的(对称的，传递的） RR’
称关系R’为R的自反(对称,传递)闭包,记作r(R) (s(R),t(R))

73 7.5 关系的闭包 解释 R’是在R的基础上添加有序对 添加元素的目的是使R’具有自反性(对称性,传递性)

74 7.5 关系的闭包 例A={a,b,c}，R={<a,a>,<a,b>,<b,c>} a c b c b
自反闭包r(R) {<a,a>,<a,b>,<b,c>,<b,b>,<c,c>} 对称闭包s(R) {<a,a>,<a,b>,<b,a>,<b,c>,<c,b>} 传递闭包t(R) {<a,a>,<a,b>,<b,c>,<a,c>} a c b r(R) a b c c b a b a c c b a

75 7.5 关系的闭包 定理：R是非空集合A上的关系,则 r(R)=RA 证明: RRA，RA是自反的
设R”满足RR”,R”是自反的 <a,b>RA 则<a,b>R或<a,b>A 如<a,b>R,由RR”知<a,b>R” 如<a,b>A,由R”的自反性知<a,b>R” 均有<a,b>R” RAR”

76 7.5 关系的闭包 定理: 设R是非空集A的关系,则 s(R)=RR-1 证明: RRR-1满足定义第2条
<a,b>RR-1 <a,b>R<a,b>R-1 <b,a>R-1<b,a>R <b,a>RR-1 RR-1是对称的

77 7.5 关系的闭包 如RR”,且R”是对称的 <a,b>RR-1
<a,b>R或<a,b>R-1 如<a,b>R,由RR”,则<a,b>R” 如<a,b>R-1,则<b,a>R,则<b,a>R” 因R”对称 <a,b>R”,RR-1R” 满足定义第3条

78 7.5 关系的闭包 例:设A={1,2,3},A上的关系R如图,求r(R),s(R)
r(R)= RA ={<1,2>,<2,3>,<3,2>,<3,3>,<2,2>,<1,1>} s(R)= RR-1 ={<1,2>,<2,3>,<3,2>,<3,3>,<2,1>}

79 7.5 关系的闭包 定理: 设R是非空集合A上的关系, 则 t(R)= R1R2…
证明：首先证明R1R2…  t(R)，使用归纳法。 n=1，显然R1= R t(R) 假设Rk  t(R)，对任意<x,y>有 <x,y>Rk+1 =Rk  R1 t(<x,t>Rk  <t,y>R1) t(<x,t>t(R)  <t,y>t(R)) <x,y>t(R) 其次， t(R)  R1R2…即证R1R2…传递 推论: 设A是非空有限集，R是集合A上的二元关系，则存在正整数n，使得t(R)=RR2… Rn

80 7.5 关系的闭包 例 A={a,b,c,d} 解:R2={<a,c>,<a,d>},R3=
R={<a,b>,<a,c>,<b,c>,<b,d>} S={<a,b>,<b,c>,<c,d>},求t(R),t(S) 解:R2={<a,c>,<a,d>},R3= t(R)=R{<a,c>,<a,d>} S2={<a,c>,<b,d>},S3={<a,d>},S4= t(S)=S{<a,c>,<b,d>}{<a,d>} a b c d R a b c d S

81 7.5 关系的闭包 给定关系R，r(R)，s(R)，t(R)的关系矩阵分别为M，Mr，Ms，Mt，那么： Mr=M+E Ms=M+M’
Mt=M+M2+M3+…

82 7.5 关系的闭包 关系图分别为G，Gr，Gs，Gt，那么： 考察G的每个顶点，如果没有环就加上一个环，最终得到的是Gr
考察G的每一条边，如果有一条从xi到xj的单向边，则在G中加一条xj到xi的反方向边，最终得到Gs 考察G的每个顶点xi，找出从xi出发的所有2步，3步，…，n步长的路径。设路径的终点为xj1， xj2， …， xjk。如果没有从xi到xjl的边，就加上这条边，最终得到Gt

83 7.5 关系的闭包 定理：设A是一集合，R是A上的二元关系，则有： 证明：Rr(R)。由自反闭包定义，r(R)R。
R是对称的当且仅当s(R)＝R R是可传递的当且仅当t(R)＝R 证明：Rr(R)。由自反闭包定义，r(R)R。

84 7.5 关系的闭包 定理：设A是集合，R1和R2是A上的二元关系，R1R2，则有：
r(R1)r(R2) s(R1)s(R2) t(R1)t(R2) 证明： r(R1)=R1A ，r(R2)=R2A

85 7.5 关系的闭包 定理：设X是一集合，R是X上的二元关系，则有： 若R是自反的，则s(R),t(R)也自反
若R是对称的，则r(R),t(R)也对称 若R是可传递的，则r(R)也可传递

86 7.5 关系的闭包 定理：设X是一集合，R是X上的二元关系，则有： 证明：归纳法证明若R是对称，则Rn也对称 n=1，显然成立
若R是对称的，则t(R)也对称 证明：归纳法证明若R是对称，则Rn也对称 n=1，显然成立 假设Rn对称，对任意<x,y> <x,y>Rn+1 t(<x,t>Rn<t,y>R) t(<t,x>Rn<y,t>R) <y,x>RRn <y,x>Rn+1

87 7.5 关系的闭包 定理：设X是一集合，R是X上的二元关系，则有：
若R是对称的，则t(R)也对称 证明：…<y,x>RRn <y,x>Rn+1 任取<x,y>，有 <x,y>t(R) n(<x,y>Rn) n(<y,x>Rn) <y,x>t(R)

88 7.5 关系的闭包 若R是传递的，s(R)不一定是传递的
反例：R={<a,b>,<c,b>}， R是传递的 s(R)={<a,b>,<b,a>,<c,b>,<b,c>} s(R)不是传递的

89 第七章: 二元关系 第六节：等价关系与划分

90 7.6 等价关系与划分 等价关系：非空集合A上的关系，满足： 例 自反的 对称的 可传递的 实数(或I、N集上)集合上的“=”关系
全集上集合的相等关系 命题集合上的命题等价关系

91 7.6 等价关系与划分 例：设A={1,2,3,4,5,6,7} R={<x,y>|x,y∈A∧(x-y)可被3整除}

92 7.6 等价关系与划分 (2) R的关系矩阵 R满足自反、对称和可传递的

93 7.6 等价关系与划分 等价类：设R是非空A集合上的等价关系，对于任何x∈A，令： [x]R ={y|y∈A  xRy}
[x]R是由x∈A生成的R等价类 x为等价类[x]R的表示元素

94 7.6 等价关系与划分 讨论 等价类[x]R是一个集合，[x]R  A ([x]R是A的子集)
在等价关系中的关系图中，一个最大连通子图中的点就是一个等价类

95 7.6 等价关系与划分 例： A={a,b,c,d} R={<a,a>，<b,b>，<a,b>，<b,a>，<c,c>，<d,d>，<c,d>，<d,c>} [a]R ={a,b}= [b]R [c]R ={c,d}= [d]R

96 7.6 等价关系与划分 例：设A=N 等价类 R={<x,y>|x∈A∧y∈A∧(x-y)可被3整除}

97 7.6 等价关系与划分 定理 设A是一个集合，R是A上的等价关系，xRy当且仅当[x]=[y] 证明：
充分性，因为x∈[x]=[y],即x∈[y] ，所以xRy。 必要性，已知xRy，考虑[x]的任意元素z，有zRx。根据R的传递性，有zRy，因此z∈[y]。证明[x][y]。类似可证明[y][x] ，所以[x]=[y]

98 7.6 等价关系与划分 定理：设A是一个集合，R是A上的等价关系， 证明：只需证明如果xRy，则[x]∩[y]=Ø
对于所有x,y∈A，或者[x]=[y]，或者 [x] ∩[y]=Ø 证明：只需证明如果xRy，则[x]∩[y]=Ø 反证法：假设[x]∩[y]≠Ø，则z[x]∩[y] <x,z>R  <z,y>R  <x,y>R (矛盾!)

99 7.6 等价关系与划分 定理：设R是集合A上的等价关系，则 A=∪{[x] | xA} 证明：首先易证∪{[x] | xA}  A
其次，对任意yA yA  y[y]  yA  y∪{[x] | xA} 所以： A  ∪{[x] | xA}

100 7.6 等价关系与划分 商集：R是A上的等价关系， 例：A为全班同学的集合，|A|=n，(n∈N) R的所有等价类构成的集合
记为A/R：{[x]R | x A} 例：A为全班同学的集合，|A|=n，(n∈N) 按指纹的相同关系R1是一个等价关系 A/R1={[x1]R1,…[xn]R1} 同姓关系R2是一等价关系 A/ R2 ={[张]，[李]，…}

101 7.6 等价关系与划分 划分：给定一非空集合A，A的一个划分为非空子集族S={A1, A2,… Am}，满足： S
xy(x, ySx≠yx∩y=) A1∪A2 ∪… ∪Am= A

102 7.6 等价关系与划分 例：A={a,b,c},下列哪些Ai为A的一个划分？ A1={{a},{b,c}} A2={{a},{c},{b}}

103 7.6 等价关系与划分 等价关系与划分有一一对应关系 划分到等价关系转化：A是一非空集合，S是A的一个划分，下述关系必定是一个等价关系
R={<x,y> | x, y A  x,y在S的同一划分} 等价关系到划分的转化：设A是非空集合，R是A上的等价关系。R的商集是A的划分

104 7.6 等价关系与划分 例：A ={a,b,c,d,e} S={{a,b},{c},{d,e}} 对应划分S的等价关系为
R={a,b}×{a,b}∪{c}×{c}∪{d,e}×{d,e}={<a,a>,<b,b>,<a,b>,<b,a>,<c,c>,<d,d>,<e,e>,<d,e>,<e,d>}

105 第七章: 二元关系 第七节：偏序关系

106 7.7 偏序关系 次序在现实生活中常见： 研究序理论的动机： 小于，包含等 研究一般次序关系 推导出一般序关系的性质
这些关系可以应用于所有特定的序关系

107 7.7 偏序关系 偏序关系R (记作≼) 例:偏序关系 a b c 自反性: a∈A，有<a,a>∈R
反对称性: a,b∈R,如果<a,b>∈R且<b,a>∈R,则必有a＝b 传递性: a,b,c∈A,如果<a,b>∈R,<b,c>∈R, 必有<a,c>∈R 例:偏序关系 A＝{a,b,c} R＝{<a,a>,<a,b>,<a,c>,<b,b>, <b,c>,<c,c>} a b c

108 7.7 偏序关系 例：A是非零自然数集, ≼是A上的整除关系。 ≼是A上的偏序关系 a∈A, a能整除a ∴ ≼具有自反性
a,b∈A,如a能整除b,且b能整除a,则a＝b ∴ ≼具有反对称性 a,b,c∈A,如a能整除b,b能整除c,则a能整除c,<a,c>∈ ≼ ∴ ≼具有传递性 ≼是A上的偏序关系

109 7.7 偏序关系 小于≺：a≺ba≼ba≠b 可比：a与b可比  a≼bb≼a 例：A={1，2，3}，≼是A上的整除关系
可比不同于等于 例：A={1，2，3}，≼是A上的整除关系 1，3可比 全序关系R：R是A上的偏序关系, 满足： a,b∈A, a与b可比 例：实数上的≤,≥关系是全序关系

110 7.7 偏序关系 哈斯图 得名于德国数学家Helmut Hasse 用来表示有限偏序集的一种数学图表 偏序集：<A, ≼>

111 7.7 偏序关系 覆盖：<A,≼>，b覆盖a如果 哈斯图思路： 条件2，3等于说如果b覆盖a,则画一条从a到b的弧线，否则不画
a≺b，不存在cA，a≺c≺b 哈斯图思路： 所有结点的自回路均省略 省略所有弧上的箭头,适当排列A中元素的位置,如a≼b,则a画在b的下方 如a≼b,b≼c,则必有a≼c, a到b有边, b到c有边,则a到c的无向弧省略 条件2，3等于说如果b覆盖a,则画一条从a到b的弧线，否则不画

112 7.7 偏序关系 例：画出下列偏序集的哈斯图。 1 2 5 3 4 6 <{1,2,3,4,5,6},R整除>

113 7.7 偏序关系 例：A={a,b,c},包含关系R是P(A)上的偏序关系,哈斯图如下:
P(A)={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} {a} {a,b}  {b} {a,b,c} {b,c} {c} {a,c}

114 7.7 偏序关系 最小(大)元：设<A, ≼>是偏序集,集合BA 说明 最大元b∈B：a∈B,均有a≼b
最小元b∈B：a∈B,均有b≼a 说明 如果A的子集B存在最大(小)元素,则最大(小)元素是唯一的 最大(小)元可能不存在

115 7.7 偏序关系 例:A＝{1,2,3,4,5,6},R是整除关系,哈斯图为 1 2 5 3 4 6 A中不存在最大元

116 7.7 偏序关系 极大(小)元：设<A, ≼>是偏序集,BA 说明 1 2 5 3 4 6
极大元b∈B：a∈B,如b≼a,则a＝b 不存在a∈B，b≺a 极小元b∈B：a∈B,如a≼b,则a＝b 不存在a∈B，a≺b 说明 极大元未必是最大元 极大元未必是唯一的 如果B是有限集,则B必存在极大元 最大元就是极大元 1 2 5 3 4 6

117 7.7 偏序关系 例：下列哈斯图表示的偏序集是否有最大(小)元？是否有极大(小)元？ {a} {a,b} ф {b} {a,b,c}
{a,c}

118 7.7 偏序关系 上(下)界：设<A, ≼>是偏序集, BA, a∈A 说明 B的上界a：对每个b∈B,有b≼a
B的下界a：对每个b∈B,有a≼b 说明 上下界不一定唯一

119 7.7 偏序关系 例：<A，R整除>, A={2,3,6,12,24,36}
B:{2,3},{2,3,6},{6,12},{6,12,24,36} A 上界 下界 B {2,3} 6,12,24,36 {2,3,6} {6,12} 12,24,36 2,3,6 {6,12,24,36}

120 7.7 偏序关系 上(下)确界：设<A, ≼>是偏序集, BA 说明 最小上界：C={b|b为B的上界}的最小元
最大下界：D={b|b为B的下界}的最大元 说明 B的最小元一定是B的下界，同时也是B的最大下界；B的最大元一定是B的上界，同时也是B的最小上界 最小上界或最大下界可能不存在 若存在最小上界或最大下界，是唯一的

121 7.7 偏序关系 例:〈A，R整除〉, A={2,3,6,12,24,36} B:{2,3},{2,3,6},{6,12},{6,12,24,36} A 上确界 下确界 B {2,3 } 6 {2,3,6 } {6,12 } 12 {6,12,24,36 }

122 7.7 偏序关系 拓扑排序：给定一个非空有限的偏序集合<A,≼’>，构造出一个全序集合<A, ≼> ，使得每当a≼’b有a≼b，方法如下： 选取A的极小元a，使a是<A, ≼>列表表示中的第一个元素 对子集A-{a}重复这一过程，每次一个新的极小元素被找到，它在<A,≼>的列表表示中成为下一个元素 重复这一过程，直到A的元素被抽完

123 7.7 偏序关系 例：求下列偏序集对应的全序集 24 24 12 8 12 8 4 4 6 6 2 3 2 3 1 1

124 第七章 习题课 有序对： 由两个元素x，y按给定顺序排列组成的二元组合 笛卡儿积： 集合A中元素为第一元素，集合B中元素为第二元素的有序对集
第七章 习题课 有序对： 由两个元素x，y按给定顺序排列组成的二元组合 笛卡儿积： 集合A中元素为第一元素，集合B中元素为第二元素的有序对集 二元关系R： 满足下列条件之一的集合： 集合非空，且它的元素都是有序对 集合为空集 从A到B的关系： A，B是集合，A×B的任何子集所定义的二元关系 A上的关系： A=B 空关系，全域关系，恒等关系，包含关系 关系的表示法： 集合表达式、关系矩阵、关系图 124

125 第七章 习题课 关系的八种运算： 定义域： 值域： 域： 逆： 右复合： 限制： 像： 幂： R0 =A；Rn+1=RnR

126 第七章 习题课 关系运算的五种性质: 自 反： 反自反： 对 称： 反对称： 传 递：

127 第七章 习题课 关系的三种闭包： 自反闭包： r(R)=RA 对称闭包： s(R)=RR-1 传递闭包： t(R)= R1R2…

128 第七章 习题课 A上的等价关系： 等价类： 商集： 划分： A的非空子集族S={A1, A2,… Am}，满足： A上的偏序关系与偏序集
第七章 习题课 A上的等价关系： 自反的；对称的；可传递的 等价类： [x]R ={y|y∈A  xRy} 商集： R的所有等价类构成的集合， 记为A/R：{[x]R | x A} 划分： A的非空子集族S={A1, A2,… Am}，满足： S xy(x, ySx≠yx∩y=) A1∪A2 ∪… ∪Am= A A上的偏序关系与偏序集

129 基本要求 熟练掌握关系的三种表示法 能够判定关系的性质，以及等价关系、偏序关系 掌握含有关系运算的集合等式
掌握等价关系、等价类、商集、划分、哈斯图、偏序集等概念 计算AB, dom R, ranR, fldR, R1, RS , Rn , r(R), s(R), t(R) 求等价类和商集A/R 给定A的划分，求出 所对应的等价关系 求偏序集中的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界 掌握基本的证明方法 证明涉及关系运算的集合等式 证明关系的性质、证明关系是等价关系或偏序关系 129

130 练习1 1．设A = {1, 2, 3}, R = {<x,y> | x, yA且x+2y  6 }，
S = {<1,2>, <1,3>,<2,2>}, 求: (1) R的集合表达式 (2) R1 (3) dom R, ran R, fld R (4) RS, R3 (5) r(R), s(R), t(R) 130

131 解答 (1) R = {<1,1>, <1,2>, <2,1>, <2,2>, <3,1>} (2) R1 = {<1,1>, <2,1>, <1,2>, <2,2>, <1,3 >} (3) domR = {1, 2, 3}, ranR = {1,2}, fldR = {1, 2, 3} (4) RS = {<1,2>, <1,3>, <2,2>, <2,3>, <3,2>, <3,3>} R3 = {<1,1>, <1,2>, <2,1>, <2,2>, <3,1>, <3,2>} (5) r(R) = {<1,1>, <1,2>, <2,1>, <2,2>, <3,1>, <3,3>} s(R) = {<1,1>,<1,2>,<2,1>, <2,2>, <3,1>, <1,3>} t(R) = {<1,1>, <1,2>, <2,1>, <2,2>, <3,1>, <3,2>} 131

132 练习2 2．设A={1,2,3,4}，在AA上定义二元关系R：
<<x,y>,<u,v>>R  x+y = u+v， 求R导出的划分. AA={<1,1>, <1,2>, <1,3>, <1,4>, <2,1>, <2,2>, <2,3>, <2,4>,<3,1>, <3,2>, <3,3>, <3,4>, <4,1>, <4,2>, <4,3>, <4,4>} 根据 <x,y> 中的 x+y = 2, 3, 4, 5, 6, 7, 8 将A划分成等价类： A/R={{<1,1>}, {<1,2>,<2,1>}, {<1,3>, <2,2>, <3,1>}, {<1,4>, <2,3>, <3,2>, <4,1>}, {<2,4>, <3,3>, <4,2>}, {<3,4>, <4,3>}, {<4,4>}} 132

133 练习3 3．设R是Z上的模 n 等价关系, 即 xy  x  y(modn), 试给出由R确定的Z的划分.
解 设除以 n 余数为 r 的整数构成等价类 [r]，则 [r] ={ kn+r | kZ }, r = 0, 1, …, n1  = { [r] | r = 0, 1, …, n1} 133

134 练习4 4．设偏序集 <A, R> 的哈斯图如图所示. (1) 写出A和R的集合表达式
(2) 求该偏序集中的极大元、极小元、最大元、最小元 解： (1) A = {a, b, c, d, e} R = {<d,b>, <d,a>, <d,c>, <e,c>, <e,a>, <b,a>, <c,a>}IA (2) 极大元和最大元是a, 极小元是d, e； 没有最小元. a b c d e 图11 134

135 练习5 5．设R是A上的二元关系， 设 S = {<a,b> | c(<a,c>R<c,b>R)}. 证明如果R是等价关系，则S也是等价关系。 证： R是A上的等价关系. (1) 证自反 任取x, xA  <x,x>R  x (<x,x>R<x,x>R)  <x,x>S (2) 证对称 任取<x,y>, <x,y>S  c(<x,c>R<c,y>R)  c (<c,x>R<y,c>R) <y,x>S (3) 证传递 任取<x,y>, <y,z>, <x,y>S  <y,z>S  c (<x,c>R<c,y>R)  d (<y,d>R<d,z>R)  <x,y>R<y,z> R  <x,z>S 135

136 练习6 6．设偏序集<A,R>和<B,S>，定义AB上二元关系T:
<x,y>T<u,v>  xRu  ySv 证明T为偏序关系. 证：(1) 自反性 任取<x,y>, <x,y>AB  xAyB  xRxySy  <x,y>T<x,y> (2) 反对称性 任取<x,y>,<u,v> <x,y>T<u,v><u,v>T<x,y>  xRu  ySv  uRx  vSy  (xRu  uRx)  (ySv  vSy)  x=u  y=v  <x,y>=<u,v> (3) 传递性 任取<x,y>,<u,v>, <w,t> <x,y>T<u,v><u,v>T<w,t>  xRu  ySv  uRw  vSt  (xRu  uRw)  (ySv  vSt)  xRw  ySt  <x,y>T<w,t> 136

137 关系性质的证明方法 1. 证明R在A上自反 任取x, xA  ……………………..….…….  <x,x>R
前提 推理过程 结论 2. 证明R在A上对称 任取<x,y>， <x,y> R  ……………………………….  <y,x>R 前提 推理过程 结论 137

138 关系性质的证明方法 3. 证明R在A上反对称 任取<x,y>，
<x,y>R<y,x>R  ……………………..  x = y 前提 推理过程 结论 4. 证明R在A上传递 任取<x,y>,<y,z>， <x,y>R<y,z>R  ……………………..  <x,z>R 前提 推理过程 结论 138

139 练习7 7．R,S为A上的关系，证明 RS  t(R)  t(S) 证：只需证明对于任意正整数n, Rn  Sn. 对n归纳.
假设对于n，命题为真，任取<x,y> <x,y>Rn+1  <x,y>Rn  R  t (<x, t>Rn  <t, y>R)  t (<x, t>Sn  <t, y>S)  <x,y>Sn  S  <x,y>Sn+1 139

140 关系等式或包含式的证明方法 数学归纳法（主要用于幂运算） 证明中用到关系运算的定义和公式, 如：
xdomR  y(<x,y>R) yranR  x(<x,y>R) <x,y>R  <y,x>R1 <x,y>R  S  t (<x,t>R<t,y>S) <x,y>R↾A  xA  <x,y>R yRA]  x (xA  <x,y>R) r(R) = RIA s(R) = RR1 t(R) = RR2… 140

141 作业 4 13 15 20 25 26 36 46