当前位置：文档之家 › 离散数学-关系-1

离散数学-关系-1

  • 格式：pdf
  • 大小：190.72 KB
  • 文档页数：31

下载文档原格式

  / 31

合集下载

离散数学关系-PPT

离散数学关系-PPT
离散数学关系
基本要求和重难点:
• 基本要求
了解序偶与笛卡尔积,掌握关系得性质和运算,重 点掌握关系闭包运算得求法和偏序关系及哈斯图 得正确画法。
• 重难点
关系5种性质得判断,关系得闭包运算和偏序关系 得性质及特殊元素得判断。
引言
日常生活中,大家熟知一些常见关系, 例:家庭集合,有父子关系、夫妻关系等。 全校同学作为一个集合,有同班关系,同组关系。 在计算机科学中,在计算机逻辑设计中,应用了等 价关系,相容关系。 在编译原理、关系数据库、数据结构、数学中也有 关系。
例题
返回第5、3节目录
五、传递性例题
例: A={1,2,3,4} R={<1,4>,<4,3>,<1,3>,<3,1>,<1,2>,<3,2>,<2,3>, <4,2>,<1,1>,<3,3>} R不就是传递得
返回传递性
返回第5、3节目录
六、举 例
自反性 反自反性 对称性 反对称性 传递性
任何集合上得
返回总目录
一、自反性
自反性
定义: 若xA,均有xRx,那么称R就是自反得。
A上关系R就是自反得x(xA xRx)
在关系矩阵中,反映为主对角线元素均为1 在关系图中,反映为每结点都有自回路 例1: A＝{1,2,3},R={<1,1>,<2,2>,<3,3>,<1,2>}
1 23
例2:“＝”关系和“≤”关系就是自反得吗？
S={<4,2>,<2,5>,<3,1>,<1,3>}

离散数学第二章关系

离散数学第二章关系

例9 .设A={1,2,3,4} ，B={2,4,6,8,10} 。 R={(1,2),(2,4),(3,6)}。
则 (R) = {1,2,3}A ， (R) = {2,4,6}B 。
二.关系的一些关联性质 17
离散数学
定理1. 设R1,R2 A×B是两个关系。若 R1 R2 ，则
(1)保序性： (R1) (R2) ； (2)保序性： (R1) (R2) ；
注：笛卡尔(1596-1650 )，法国数学家， 1637年发表《方法论》之 一《几何学》，首次提出坐标及变量概念。这里是其概念的推广。
定义2. • 二个集合A，B的(二维或二重)叉积定义为 A×B ={(a, b): a A bB} ； •其元素——二元组(a, b)通常称为序偶或偶对(ordered
故 (R1)∩ (R2) = {1,2 }
21
离散数学
所以 (R1)∩ (R2) (R1 ∩ R2) 。
元素aA和集合A1A在关系R A×B下的关联集 (1)a的R-关联集(R-relative set of a)：
R(a)={b : bBaRb }B ；
(2) A1的R-关联集(R-relative set of A1)： R(A1)={b : bB (aA1)(aRb) }B 。
•当A=B时，即RA×A，则称R是A上的一个二元关 系。
例1 . 设A是西安交通大学全体同学组成的集合。 11
离散数学
R={(a,b) : aAbAa与b是同乡}A×A 于是，R是西安交通大学同学之间的同乡关系。
例2 . 设A是某一大家庭。
R1 = {(a,b) : aAbAa是b的父亲或母亲}A×A R2 = {(a,b) : aAbAa是b的哥哥或姐姐}A×A R3 = {(a,b) : aAbAa是b的丈夫或妻子}A×A 于是，

离散数学中的关系

离散数学中的关系

离散数学中的关系
离散数学中的关系指的是集合之间元素的联系或对应关系。

这种关系可以描述为有序对的集合，其中每个有序对都由一对元素组成。

在离散数学中常见的关系包括等价关系、偏序关系、全序关系等。

等价关系是一种自反、对称和传递的关系，即元素之间具有相等的性质。

例如，集合中两个元素的相等关系就是一种等价关系。

偏序关系是一种自反、反对称和传递的关系，即对元素之间存在一种偏序或排序关系。

例如，在集合中，可以通过元素之间的比较来确定它们的顺序关系。

全序关系是一种偏序关系，它不仅是自反、反对称和传递的，还具有完备性，即对于集合中任意两个元素，它们之间必定存在一种顺序关系。

离散数学中还有其他类型的关系，如函数关系、包含关系等。

函数关系是一种特殊的关系，它对于集合中的每个元素，都存在唯一的映射元素。

包含关系则描述了两个集合之间的包含或包含于关系。

通过对这些关系的研究和分析，可以帮助理解和解决离散数学中的问题。

同时，关系的性质和特征也为其他学科如计算机科学、逻辑学等提供了基础。

离散数学28.关系的性质1

离散数学28.关系的性质1
例如，集合X上的全域关系EX、 恒等关系IX都不是X上的反 自反关系.
2）若关系R不是反自反的，关系R也不一定是自反的，反之也 成立.
XZ-{0}时，整除关系 R2={<x,y>x,yX∧x整除y}. 都是自反关系.
(3) 数集X上的小于关系 R3= {<x,y>x,yX∧xy}. 不是自反的.
若集合X上的二元关系R是自反的充要条件： • 1） R是自反的恒等关系IX R. • 2） R是自反的关系R的关系矩阵MR的主对角线全是1. • 3） R是自反的关系R的关系图中每个结点都有上的二元关系,如果对于每 个x∈X，有<x,x>R，则称二元关系R是反自反的.
R在X上反自反 (x)(xX <x,x>R ). 例如，数集X上的小于关系 R3={<x,y>x,yX∧xy} 空关系 ，均为反自反关系.
若集合X上的二元关系R是反自反的充要条件： • 1） R是反自反的恒等关系IX R= . • 2） R是反自反的关系R的关系矩阵MR的主对角线全是0. • 3） R是反自反的关系R的关系图中每个结点都没有自回路.
设 X={1,2,3}, R1={<1,1>,<2,2>,<3,3>,<1,2>} 是X上的自反关系; R2={<1,3>} 是X上的反自反关系; R3 ={<1,1>,<1,2>,<2,2>,<2,3>} 既不是自反的，也不是反自反的.
注意：
1）一个关系R如果是自反的，一定不是反自反的；如果是反自 反 的，则一定不是自反的.
关系的性质
一、关系的性质
关系的性质主要有5种：自反性、反自反性、对称性、反对 称性、传递性.

离散数学 关系的性质

离散数学 关系的性质
关系矩阵中以主对角线对称的元素不能同时为1。
(3). 关系图的特点：
关系图中如果两个顶点之间有边一定是一条有向边。
实例：
恒等关系IA，空关系都是A上的反对称关系。
2021/5/27
12
例2 设A＝{1,2,3}, R1, R2, R3和R4都是A上的关系, 其中 R1＝{<1,1>,<2,2>}， R2＝{<1,1>,<1,2>,<2,1>} R3＝{<1,2>,<1,3>}， R4＝{<1,2>,<2,1>,<1,3>}
2021/5/27
3
(2). 关系矩阵的特点：
关系矩阵中主对角线上的元素全为1。
(3). 关系图的特点：
关系图中每个顶点都有环。
实例： A上的全域关系EA, 恒等关系IA，小于等于关系 LA, 整除关系DA都是自反关系：
2021/5/27
4
2．反自反的二元关系
(1). 定义： R是Ａ上的二元关系，若x(x∈A→<x,x>R),
例如 Ａ＝｛a,b,c｝, R={ (a,a),(b,b),(c,c),(a,b)}，
则Ｒ是自反的。
又如Ａ＝｛1,2,3｝, R是Ａ上的整除关系，
显然，Ｒ是自反的，因为（1, 1）,（2, 2）,（3, 3）
都属于R。 2021/5/27
2
注意，在关系的自反性定义中，要求对于A中 的每一个元素a都有(a,a) ∈R。所以当A={a,b,c}，而 R={(a,a),(b,b)}时，R并不是自反的，因为(c,c) R。 又如A={1,2,3}，R是A上的二元关系，当a,b∈A， 且a和b都是素数时，(a,b) ∈R。 可见Ｒ＝{(2,2),(3,3),(2,3),(3,2)}，Ｒ也不是自反关 系，因为(1,1) R。

离散数学-第1章

离散数学-第1章
27
练习1解答
提示： 分清复合命题与简单命题 分清相容或与排斥或 分清必要与充分条件及充分必要条件
答案: (1) 是简单命题
(2) 是合取式
(3) 是析取式（相容或）(4) 是析取式（排斥或）
设 p: 交通阻塞，q: 他迟到
(5) pq,
(6) pq或qp
(7) qp 或pq, (8) qp或pq
假命题 真命题 不是命题 不是命题
不是命题 不是命题
命题，但真值现在不知道
5
命题分类
命题分类：简单命题（也称原子命题）与复合命题 简单命题符号化
用小写英文字母 p, q, r, …, pi, qi, ri (i1)表示简单命题
用“1”表示真，用“0”表示假 例如，令
p： 2是有理数，则 p 的真值为0，
p q p pq (pq) (pq)q
00 1 1
0
0
01 1 1
0
0
10 0 0
1
0
11 0 1
0
0
成假赋值:00,01,10,11; 无成真赋值
24
公式的类型
定义1.10 (1) 若A在它的任何赋值下均为真, 则称A为重言式或永真式; (2) 若A在它的任何赋值下均为假, 则称A为矛盾式或永假式; (3) 若A不是矛盾式, 则称A是可满足式.
30
练习3解答
(1) pr(qp)
pqr
qp (qp) pr(qp)
000
1
0
0
001
1
0
0
010
0
1
0
011
0
1
0
100
1
0
0
101

离散数学讲解第一章

B7=B000111={a4,a5,a6} B12=B001100={a3,a4}
2018/12/20 21
集合族: 由集合构成的集合.
{{6}, {1,5} , {2,4}, {1,2,3}} 幂集都是集族.
2018/12/20
22
指标集(index set): 设A是集合族, 若 A = { Ai | iK }, 则K称为A的指标集.
全集是相对的, 视情况而定, 因此不唯一.
2018/12/20
24
1.4集合之间的运算
1. 并集: 设有集合A、B，属于A或属于B的所有元素 组成的集合，称为A与B的并集，记作AB AB = { u | uA 或 uB}
AB
2018/12/20
25
2. 交集：设有集合A、B，属于A同时又属于B的所有 元素组成的集合，称为A与B的交集，记作A B AB = { u | u A 且 u B }
2018/12/20 15
对任意集合A, A 证明: 反证法（设结论不成立，推出矛盾）
假设空集不是集合A的子集，即 A 根据定义1-2，存在x ， x A， 这与空集的定义矛盾 假设不成立，应有A，原结论成立。
2018/12/20
16
定理: 空集是唯一的.
证明: 设1与2都是空集, 则 12 且 21 1=2 .
2018/12/20
5
2. 集合的表示
列举法:
列出集合中的全体元素，元素之间用逗号分 开，然后用花括号括起来，例如: A={a,b,c,d,…,x,y,z} B={0,1,2,3,4,5,6,7,8,9} C={2,4,6,…}
2018/12/20
6
描述法
给定一个条件P(x) ，当且仅当a使条件P(a)成立 时，a∈A。

离散数学-第四章 关系-内容提要


{}
传递。
(5)如 果 VJ
:IT{∶ ∶ ∶ ∶ 蚕 ⒈11∶⒈ ∶ Ll ;, 翕 罐 ∶ ∶ ∶ 置 R在 A上
:I∶
:: 1∷
Vj V石
(Π
、 、 y,z)∈ R→ 〈 R∧ 〈 J,z〉 ∈ R),则 称 Π ,y,z∈ A∧ 〈 ,j〉 ∈
1亠
判别法
:
利用关系表达式判别 (1)R在 A上 白反 ㈡rA∈ R。
,
系:简 称全胛 蜮 线序 曳
柙
\宀
:'艹
° Γ ˉ叽
抖 ¨ ‰ 艹 渺 冖妒 ”
^讷
p¨ ¨
¨
i
∶
^¨
Ⅱ… ¨
=艹
)。
`呻
/
‘ :° f耷
一
^A’
工 < ′
工 < ′
Ι ⒕
,
、
\′
I纟
:
轱
/廴
跃
:
h,如 果 J≤ y∨ y※ J,贝 刂 ∈ 称
J与 j可 比。
称 y覆 盖 J。
偏序集中的特殊元素
得 ⒎ 则
:
y,z〉 ∈ S))。 ∈ R∧ 〈
有关基本运算的定理 ・ 定理 4.1 设 F是 任意的关系 ,则
(1)(Fˉ l)ˉ ^l=F。
・
(2)domFˉ ˉ ∴ =ranF,ranF~l=domF。
定理 4.2 设 F,G,Ⅳ 是任意的关系 ,则 (1)(F° G)° H=Fo(G° H), (2)(FoG)ˉ l=G^loF_ˉ
:
(2)R在 (3)R在 (4)R在 (5)R在 (1)R在 (2)R在 (3)R在 (4)R在
A上 反 自反 ⑶R∩ rA=¤ 。 A上 对称 山R=Rl。 ; A上 反对称 ㈡R∩ R~l∈ A上 传递 ㈡R。 R∈ R。

离散数学 关系的运算

R2 { a,c , b, a , c,b }
R3 R2 R { a, a , b,b , c,c } Ix
8
四、幂运算的性质
定理 设 R 是 A 上的关系, m, n∈N, 则 (1) Rm∘Rn=Rm+n (2) (Rm)n=Rmn
9
关系运算的矩阵表示
10
某关系R的关系图为：
1 2 3
4 5
6
a
b d
c
则R的关系矩阵为：
0 0 0 0
1 1 0 0
0 1 0 0 M R 0 0 1 0
0 0 0 0


0 0 1 0 11
思考：
写出集合A=｛1 , 2 , 3 , 4 ｝上的恒等关系、 空关 系、 全域关系和小于关系的关系矩阵。
关系矩阵（matrix of relation）。
设R A×B， A=｛a1, a2, …, am｝,
B=｛b1, b2, …, bn｝， 那么R的关系矩阵 MR为一m×n矩阵，它的第i , j分量rij 只
取值0或1， 而
1 rij 0
当且仅当iRbj 当且仅当 ai Rbj
求R1， R∘S ， S∘R 。 利用图示（不是关系图）方法求合成
R∘S ={<1,3>, <2,2>, <2,3>} S∘R ={<1,2>, <1,4>, <3,2>, <3,3>}
3
3、限制与像
定义 F 在A上的限制 F↾A = {<x,y> | xFy xA} A 在F下的像 F[A] = ran(F↾A)
定理2 设F, G, H是任意的关系, 则 (1) (F∘G)∘H=F∘(G∘H) (2) (F∘G)1= G1∘F1

离散数学题型梳理-第1章

离散数学常考题型梳理第1章 集合及其运算一、题型分析本章主要介绍集合论的基本概念和结论，集合的运算及其性质，以及利用运算性质进行集合表达式的化简和集合恒等式的证明等内容．经常涉及到的题型有：1-1集合与集合之间的包含、元素与集合之间的属于关系1-2幂集的计算1-3集合之间的运算1-4利用集合运算性质证明集合恒等式因此，在本章学习过程中希望大家要清楚地知道：1．集合与集合之间存在一种包含关系，当两个集合A 和B 存在关系A 包含B ，用A ⊇B 表示，或存在关系B 被A 包含，用B ⊆A 表示，这时称B 为A 的子集．注意空集∅是任意一个集合的子集，集合A 也是自己的子集．当B ⊆A 且B ≠A ，也就是说，只有B ⊂A 或A ⊃B 成立，则称B 为A 的真子集．若B 不是A 的子集，即B ⊆A 不成立时，则称A 不包含B ，记作B ⊆A ．然而，元素与集合之间存在一种从属关系，当a 是集合A 中的元素，则称a 属于A ，记作a∈A ；若a 不是集合A 中的元素，则称a 不属于A ，记作a ∉A ．因此，这两种关系一定不要混淆．2．由集合A 的所有子集组成的集合，称为A 的幂集，记作P (A )或2A ．若集合A 是由n 个元素所组成的集合，则A 的幂集由2n 元素组成．当n =3时，A 的幂集由23=8个元素组成．例如，设集合A = {0, 1, 2 }，则A 的全部子集由以下子集组成：0元子集（即空集）：∅；1元子集：{0}，{1}，{2}；2元子集：{0, 1}，{0, 2}，{1, 2}；3元子集（即集合A ）：{0, 1, 2}．因此，计算集合A 的幂集时，首先要按照上述方法写出集合A 的全部子集，然后检验写出的子集个数是否等于2n 个，其中n 是集合A 的元素个数．3．集合之间的运算有并（⋃）、交（⋂）、差（-）、补（~）和对称差（⊕）等五种运算，在做集合运算的题目时，一定要按照它们的定义进行计算．(1) 集合A 和B 的并集A B x x A ⋃=∈{或 x B ∈} 特点：由集合A 和B 的所有元素组成的集合．见图1 图1 图2(2) 集合A 和B 的交集A B x x A ⋂=∈{ 且 x B ∈}特点：由集合A 和B 的公共元素组成的集合．见图2(3) 集合A 与B 的差集A B -=∈∉{}x x A x B 且 特点：由属于A ，而不属于B 的所有元素组成的集合．见图3(4) 集合A 的补集~A ={}x x E x A ∈∉且特点：由属于全集E 但不属于集合A 的元素组成的集合．见图4补集总相对于一个全集而言，可以看作是全集E 与集合A 的差集．(5) 集合A 与B 的对称差A ⊕B ＝(A －B )⋃(B －A )或 A ⊕B ＝(A ⋃B )－(A ⋂B )特点：由分别属于集合A 与B 的元素但不属于它们公共元素组成的集合．见图5(6) 把集合A ，B 合成集合A ×B 叫做笛卡儿积，规定A ×B ＝{<x , y >∣x ∈A 且y ∈B }注意：由于有序对<x , y >中x ，y 的位置是确定的，因此A ×B 的记法也是确定的，不能写成B ×A.．笛卡儿积的运算一般不能交换.．虽然，笛卡儿积的内容是第2章2.1.1目的内容，是二元关系的预备知识，但我们认为把它作为集合的一种运算考虑更好些。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

二元关系的复合运算
定理3-6.2 设X，Y，Z，W是集合，RX×Y，SY×Z，T Z×W，则 (RS)T= R(ST) 证明：<x,w>∈(RS)T(z)(<x,z>∈RS∧<z,w>∈T) (z)((y)(<x,y>∈R∧<y,z>∈S)∧<z,w>∈T) (z)(y)((<x,y>∈R∧<y,z>∈S)∧<z,w>∈T) (y)(z)(<x,y>∈R∧(<y,z>∈S∧<z,w>∈T)) (y)(<x,y>∈R∧(z)(<y,z>∈S∧<z,w>∈T)) (y)(<x,y>∈R∧<y,w>∈ST)<x,w>∈R(ST) 所以 (RS)T=R(ST)
二元关系的复合运算
定义3-6.2 设R是A上的二元关系，n为自然数，R的n次幂记为Rn，定义 为： ⑴ R0=IA ⑵ Rn+1= RnR 由定义3-6.2可以看出，A上的任何二元关系的0次幂都相等，等于 A上的恒等关系IA。由定义3-6.2还可以看出： R1= R0 R=IAR=R R2= R1R= RR R3= R2R=(RR)R …… 因为复合运算满足结合律，所以R3又可以写成： n个R的复合 R3= RRR R 同样的道理Rn也可以写成： Rn= R R
MR=
例中的二元关系R是A上的二元关系， 只需看成A到A的二元关系，利用上述 定义，就可以方便地写出它的关系矩 阵。A上的二元关系和A到B的二元关 系的关系矩阵的定义是相同的。
二元关系的表示
4.用图表示二元关系 如果A和B是有限集，R是A到B二元关系，还可 以用图表示二元关系R。表示二元关系R的图叫 做R的关系图。A到B二元关系的关系图和A上的 二元关系的关系图的定义是不一样的。分别描 述如下：
二元关系的表示
例6 设A=a1,a2,a3,a4，B=b1,b2,b3，R是A到B的二元关 系，定义为： R=<a1,b1>,<a1,b3>,<a2,b2>,<a2,b3>, <a3,b1>,<a4,b1>,<a4,b2> 写出R的关系矩阵。 解: R的关系矩阵为：
MR= 1 0 1 1 0 1 0 1 1 1 0 0
二元关系的复合运算
例如,在例4.6中 R2=RR=<1,2>,<2,2> S2 =SS=<4,5>,<3,3>,<1,1> R3=RRR=<1,2>,<2,2> 定理3-6.5 设A是具有n个元素的有限集，R是A上的二元关系，则必存在 n2 自然数s和t，使得Rs=Rt，0≤s＜t≤2 。
… 证明：R是A上的二元关系，对任何自然数k，由复合关系的定义知，Rk 仍然是A上的二元关系，即RkA×A。另一方面，根据定理4.1.1， n2 A上的二元关系仅有2 种。列出R的各次幂R0，R1， 2 2 2 n，共有2 n＋1个，必存在自然数s和t，使得Rs=Rt， 2 ，…， R R2 0≤s＜t≤2 n 。
二元关系的复合运算
定理3-6.3 设R是A上的二元关系，RIA=IAR=R 证明：先证RIA=R <x,y>∈RIA(z)(<x,z>∈R∧<z,y>∈IA) (z)(<x,z>∈R∧z=y)<x,y>∈R 所以 RIAR <x,y>∈R<x,y>∈R∧<y,y>∈IA<x,y>∈RIA 所以 RRIA 故 RIA=R 类似的，可以证明IAR= R
二元关系的表示
1.用列举法表示二元关系 例4 设A=a,b，B=1,2， A到B的全域关系：E=A×B=<a,1>,<a,2>,<b,1>,<b,2> A上的恒等关系： IA=<a,a>,<b,b> 都是用列举法表示的。 2.用描述法表示二元关系 例5 设R是实数集， LR = <x,y>|x∈R∧y∈R∧x≤y， LR是实数集R上的二元关系。
3
H=<1,1>,<1,3>,<2,2>,<2,4>,<3,3>,<3,1>,<4,4>,<4,2>
二元关系的复合运算
定义3-6.1 设X，Y，Z是集合，RX×Y，SY×Z，集合 <x,z>x∈X∧z∈Z∧(y)(y∈Y∧<x,y>∈R∧<y,z>∈S) 叫做R和S的复合关系。记为RS,RSX×Z, RS是X到Z的二元关系。 例2 X=1,2,3,4,5，X上的二元关系R和S定义如下： R=<1,2>,<3,4>,<2,2> S=<4,2>,<2,5>,<3,1>,<1,3> 试求RS，SR，R(SR)，(RS)R，RR，SS，RRR 解: RS=<1,5>,<3,2>,<2,5>； SR=<4,2>,<3,2>,<1,4> (RS)R=<3,2>； R(SR)=<3,2> RR=<1,2>,<2,2>； SS=<4,5>,<3,3>,<1,1> RRR =<1,2>,<2,2> 可以看出,RS≠SR,这说明,二元关系的复合运算不满足交换律。
二元关系的复合运算
例 A= 1,2,3,4，A上的二元关系R定义如下： R=<1,2>,<2,1>,<2,3>,<3,4> 求二元关系R的各次幂，验证定理4.2.5。 解：|A|=4 R0=IA=<1,1>,<2,2>,<3,3>,<4,4> R1=R=<1,2>,<2,1>,<2,3>,<3,4> R2=R1 R= RR=<1,1>,<1,3>,<2,2>,<2,4> R3= R2R =<1,2>,<2,1>,<2,3>,<1,4> R4=R3 R=<1,1>,<1,3>,<2,2>,<2,4>=R2， 2 0≤2＜4≤216=2 4 R5=R4R=R2R=R3 R6=R5R=R3R=R4= R2 …… R2n=R2 R2n+1=R3, n =1,2,3,…
二元关系的复合运算
定理3-6.6设R是A上的二元关系，m，n为自然数，则 ⑴ RmRn =Rm+n ⑵ (Rm)n=Rmn 证明: ⑴ 对任意给定的m∈N，关于n进行归纳证明： 当n=0时，Rm R0=Rm IA=Rm=Rm+0 设n=k时，RmRk=Rm+k。下证n=k+1时，结果也对。 RmRk+1=Rm(RkR)=(RmRk)R=Rm+kR= Rm+k+1 ⑵ 对任意给定的m∈N，关于n进行归纳证明： 当n=0时，(Rm)0=IA=R0=Rm×0 设n=k时，(Rm)k=Rmk。下证n=k+1时，结果也对。 (Rm)k+1=(Rm)k Rm=RmkRm=Rmk+m=Rm(k+1)
关系的运算
例1 设X=1,2,3,4，X上的二元关系H和S定义如下，试求 H∪S，H∩S， ~H，S-H。 H=<x,y> | x y 是整数
2
S=<x,y> | x y 是正整数 解: 将H和S用列举法表示： S=<4,1> H∪S=<1,1>,<1,3>,<2,2>,<2,4>,<3,3>,<3,1>,<4,4>,<4,2>,<4,1> H∩S = φ ~H=X2-H=<1,2>,<1,4>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>,<4,1> S－H=<4,1>
二元关系的复合运算
定理3-6.4 设R，S，T是A上的二Байду номын сангаас关系, 则 ⑵ (R∪S)T=RT∪ST ⑷ (R∩S)TRT∩ST ⑴ R(S∪T)=RS∪RT; ⑶ R(S∩T)RS∩RT;
证明：仅证明⑶，类似地可证明⑴、⑵和⑷。 <x,y>∈R(S∩T)(z)(<x,z>∈R∧<z,y>∈S∩T) (z)(<x,z>∈R∧(<z,y>∈S∧<z,y>∈T)) (z)((<x,z>∈R∧<z,y>∈S)∧(<x,z>∈R∧<z,y>∈T)) (z)(<x,z>∈R∧<z,y>∈S)∧(z)(<x,z>∈R∧<z,y>∈T) <x,y>∈RS∧<x,y>∈RT <x,y>∈RS∩RT 故 R(S∩T)RS∩RT
A到B二元关系的关系图
⑴ A到B二元关系R的关系图 设A=a1,a2,…,am，B=b1,b2,…,bn，R是A到B二元 关系，R的关系图的绘制方法如下： ① 画出m个小圆圈表示A的元素，再画出n个小圆圈表示 B的元素。这些小圆圈叫做关系图的结点(下同)。 ② 如果<ai,bj >∈R，则从ai到bj 画一根有方向(带箭头)的线。这些 有方向(带箭头)的线叫做关系图的 边(下同)。