离散数学 二元关系与运算共62页

离散数学ቤተ መጻሕፍቲ ባይዱ二元关系与运算
21、静念园林好，人间良可辞。 22、步步寻往迹，有处特依依。 23、望云惭高鸟，临木愧游鱼。 24、结庐在人境，而无车马喧；问君 何能尔 ？心远 地自偏 。 25、人生归有道，衣食固其端。
41、学问是异常珍贵的东西，从任何源泉吸 收都不可耻。——阿卜·日·法拉兹
42、只有在人群中间，才能认识自 己。——德国
43、重复别人所说的话，只需要教育； 而要挑战别人所说的话，则需要头脑。—— 玛丽·佩蒂博恩·普尔
44、卓越的人一大优点是：在不利与艰 难的遭遇里百折不饶。——贝多芬
45、自己的饭量自己知道。——苏联

则关系R的各次幂为： R0 =A ={<1,1> ， <2,2> ， <3,3> ， <4,4> ， <5,5>} R1=R
R2= R • R={<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>，
从关系图来看关系的n次幂
R：
1
2
3
4
5
R2：
1
2
3
4
5
R2就是从R的关系图中的任何一个结点x出发，长 为2的路径，如果路径的终点是y，则在R2 的关系 图中有一条从x到y的有向边。其他以次类推：
R3：
1
2
3
4
5
R4：
1
2
3
4
5
定理 设|A|=n，R A×A，则必有i，j∈N， 0≤i＜j≤2n2，使得Ri=Rj。
＝R5，R7＝R6•R＝R5，…，Rn＝R5 (n＞5) 故Rn{R0,R1,R2,R3,R4,R5}。
S0=IA,S1＝S,
S2＝S•S＝{<a,c>,<b,d>,<c,e>,<d,f>}， S3＝S•S•S＝S2•S＝{<a,d>,<b,e>,<c,f>}， S4＝S3•S＝{<a,e>,<b,f>}， S5＝S4•S＝{<a,f>}， S6＝S5•S＝Φ， S7＝Φ， …， 故，Sn{S0,S1,S2,S3,S4,S5,S6}

举例
A表示某大学所有学生的集合，B表示大学开设的 表示某大学所有学生的集合， 表示大学开设的 表示某大学所有学生的集合 所有课程的集合， 所有课程的集合， 则A×B可以用来表示该校学生选课的所有可能情 × 可以用来表示该校学生选课的所有可能情 况。 是直角坐标系中x轴上的点集 令A是直角坐标系中 轴上的点集，B是直角坐标 是直角坐标系中 轴上的点集， 是直角坐标 系中y轴上的点集 轴上的点集， 系中 轴上的点集， 于是A× 就和平面点集一一对应 就和平面点集一一对应。 于是 ×B就和平面点集一一对应。
17
其它常用的关系
小于或等于关系： 小于或等于关系：LA={<x,y>|x,y∈A∧x≤y}，其中 A⊆R。 ∈ ∧ ， ⊆ 。 整除关系： 整除y}， 整除关系：DB={<x,y>|x,y∈B∧x整除 ，其中 B⊆Z* ∈ ∧ 整除 ⊆ Z*是非零整数集 包含关系： ⊆ 包含关系：R⊆＝{<x,y>|x,y∈A∧x⊆y}，其中 是集合族 ∈ ∧ ⊆ ，其中A是集合族
6
笛卡尔积举例
举例
设A={a,b}, B={0,1,2}，则 ， A×B={<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>} × B×A={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>} ×
举例
设 A={ x | 0<x<2 } ,B={ y |0<y<1 },则 则 A × B={ <x,y>| 0<x<2且0<y<1 } 且 1 y

19
证明
(2) 任取<x,y>, <x,y>∈(FG)1 <y,x>∈FG t (<y,t>∈F∧<t,x>∈G) t (<x,t>∈G1∧<t,y>∈F1) <x,y>∈G1 F1 所以 (F G)1 = G1 F1
20
关系运算的性质
定理7.3 设R为A上的关系, 则 RIA= IAR=R <x,y> <x,y>∈RIA t (<x,t>∈R∧<t,y>∈IA) t (<x,t>∈R∧t=y∧y∈A) <x,y>∈R
例如 A = P(B) = {,{a},{b},{a,b}}, 则 A上的包含关系是 R = {<,>,<,{a}>,<,{b}>,<,{a,b}>,<{a},{a}>, <{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>} 类似的还可以定义： 大于等于关系, 小于关系, 大于关系, 真包含关系等.
注意： 关系矩阵适合表示从A到B的关系或A上的关系（A,B为有 穷集） 关系图适合表示有穷集A上的关系
11
实例
例4 A={1,2,3,4}, R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}, R的关系矩阵MR和关系图GR如下：
1 1 0 0 0 0 1 1 MR 0 0 0 0 0 1 0 0
10
关系的表示

运算“ ”称为合成运算。
XDC
12
C
S
|
S
W
注意，在合成关系中，R的后域B一定是S的 前域B，否则R和S是不可合成的。合成的结果R S 的前域就是R的前域A，后域就是S的后域C。如果 对任意的x∈A和z∈C，不存在y∈B，使得xRy和 ySz同时成立，则R S为空，否则为非空。并且， R=R =。
S
W
U
S T
=R-1∩S-1=R-1-S-1
XDC
9
C
S
|
设R是A上的二元关系，那么R是对称的当且仅 当R＝R-1 证明：充分性
a,b∈A，如<a,b>∈R，则<b,a>∈R－1， 由于R－1＝R，故<b,a>∈R，∴R是对称的。 必要性 <a,b>∈R－1，则<b,a>∈R， 又因为R是对称的，故<a,b>∈R，∴R－1R， <a,b>∈R，因R是对称的，
S
W
U
S T
∴<b,a>∈R，∴<a,b>∈R－1，∴RR－1，
从而有 R＝R－1。
XDC
10
C
S
|
结论
R是A上反对称关系的充要条件是RR－1A。
S
W
U
S T
设R和S是A上的反对称关系，则R－1、 RS、也是A的反对称关系。 R、S均是 反对称的，未必能得出RS也是反对称 的。
XDC
40--11
C
S
|
三、关系的合成运算
设R是一个从集合A到集合B的二元关
S
W
系，S是从集合B到集合C的二元关系(也可

4.6 等价关系与划分
• 三 性质 • 定理4.13 设R是A上的等价关系，则 （1）对任一a∈A，有a∈[a]； （2）对a, b∈A，如果aRb，则[a]=[b]; （3）对a, b∈A，如果(a, b)∉R，则[a]∩[b]=∅; （4）∪a∈A[a]=A。
4.6 等价关系与划分
• 定理4.14 集合A上的任一划分可以确定A上 的一个等价关系R。 • 定理4.15 设R1和R2是A上的等价关系， R1=R2⇔ A/R1=A/R2 。 • 定理4.16 设R1和R2是A上的等价关系，则 R1∩R2是A上的等价关系。
4 .3 关系的运算
• 一 逆运算 • 定义4.7（逆关系） 设R是从A到B的二元关系， 则从B到A的二元关系记为R-1，定义为R-1 ={(b,a)|(a,b)∈R}，称为R的逆关系。 • 定理2.1 （1）(R-1)-1=R; （2）(R1∪R2)-1= R1-1∪ R2-1; （3）(R1∩R2)-1= R1-1 ∩R2-1; （4） (A×B)-1= B×A；
4 .5 关系的闭包
•
• (1) (2) (3) • (1) (2) (3)
二 基本性质
定理4.5 设R是A上的二元关系，则 R是自反的 ⇔ r( R )=R； R是对称的 ⇔ s( R )=R； R是传递的 ⇔ t( R )=R； 定理4.6 设R1和R2是A上的二元关系，若R1⊆R2则 r(R1)⊆ r(R2)； s(R1)⊆ s(R2)； t(R1)⊆ t(R2)。
第四章 关系
4.1 二元关系 4.2 关系的性质 4 .3 关系的运算 4 .5 关系的闭包 4.6 等价关系与划分
4.1 二元关系
• 一 定义4.1（二元关系）
设A和B是任意两个集合，A×B的子集R称为从A到 B的二元关系。当A=B时，称R为A上的二元关系。若 (a, b)∈R，则称a与b有关系R，记为aRb。 (a, b)∉R：a与b没有关系R R=∅：空关系 R=A×B：全关系

三、二元关系的定义
如果一个集合满足以下条件之一： 定义 如果一个集合满足以下条件之一： （1）集合非空 且它的元素都是有序对 ）集合非空, （2）集合是空集 ） 则称该集合为一个二元关系 简称为关系 记作R. 二元关系, 关系， 则称该集合为一个二元关系 简称为关系，记作 如<x,y>∈R, 可记作 xRy；如果 ∈ ；如果<x,y>∉R, 则记作 y ∉ 则记作x 实例： 实例：R={<1,2>,<a,b>}, S={<1,2>,a,b}. R是二元关系 当a, b不是有序对时，S不是二元关系 是二元关系, 不是有序对时， 不是二元关系 是二元关系 不是有序对时 根据上面的记法， 根据上面的记法，可以写 1R2, aRb, a c 等.
12
1、从A到B的二元关系与 上的二元关系 、 的二元关系与A上 到 的二元关系与
是两个集合， 是笛卡尔乘积 × 的子集，则称R 定义 A和B是两个集合，R是笛卡尔乘积 A×B 的子集，则称 和 是两个集合 为从A到 的一个二元关系 的一个二元关系。 为从 到B的一个二元关系。 例如： 例如：A={a1,a2,a3,a4,a5} ， B={b1,b2,b3} 的二元关系。 若 R={(a1,b1),(a2,b1),(a4,b3)}，那么R就是一个从A到B的二元关系。 ，那么R就是一个从A 也可写作a 并称a 相关。 对于R中的元素（ 相关 对于 中的元素（a1,b1） R ，也可写作 1Rb1 ，并称 1 , b1 以R相关。 中的元素 ∈ 对于不属于R的有序对，如（a5,b2） R，也可写作 5 对于不属于 的有序对， 的有序对 ∉ 也可写作a 并称a 不以R相关 相关。 并称a5 ,b2 不以 相关。 A上二元关系的一般定义： 上二元关系的一般定义： 上二元关系的一般定义 是集合， 定义 A是集合，R1是笛卡尔乘积 A×A 的子集，则称R1为A上的二元关系 × 的子集，则称R 上的二元关系 上的一个二元关系。 例如： ，那么R 上的一个二元关系 例如：A={a,b,c,d,e}，R1 ={(a,b), (c,a), (b,b)}，那么 1是A上的一个二元关系。 ， 由此可知， 的二元关系R就是笛卡尔乘积 × 的一个子集， 由此可知，从A到B的二元关系 就是笛卡尔乘积 A×B 的一个子集， 到 的二元关系 上的二元关系R 而A上的二元关系 1就是笛卡尔乘积 ×A 的一个子集 上的二元关系 就是笛卡尔乘积A× 的一个子集.

7.2.1 二元关系的基本定义
▪ 常见的几种特殊的二元关系
▪≤ ≥ ＜ ＞ ＝ ▪| ▪ 集合之间的关系 ： ＝ ≠
2020/7/15
20
计算机科学学院 刘芳
7.2.2 二元关系的表示
1.集合表示法
2.关系矩阵(matrix of relation)
▪ 设A＝{a1,a2,…,am} ，B＝{b1,b2,…,bn}，R是A到B的一个二
所以， （A∩B）×C＝（A×C）∩（B×C）成立。
2020/7/15
11
计算机科学学院 刘芳
7.1.3 有序 n 元组和 n 阶笛卡尔积
定义：
▪ n个元素x1，x2，…，xn组成的有序序列,记做：
＜x1,x2,…,xn＞
▪ 称为n重组（n元序偶、n元组）。
约定:
▪ ＜x1，x2，…, xn-1, xn＞= ＜<x1，x2，… ,xn-1 >,xn＞
1 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0
2020/7/15
28
计算机科学学院 刘芳
7.2.2 二元关系的表示
关系的表示方法
▪ 关系R的集合表达式 ▪ 关系矩阵MR ▪ 关系图GR
三者均可以唯一相互确定。
2020/7/15
29
计算机科学学院 刘芳
7.3 关系的运算
7.3.1 关系的定义域、值域 和 域
例:
▪ (1) R＝{<x,y> | x,yN, x＋y＜3}
＝{<0,0>, <0,1>, <0,2>, <1,0>, <1,1>, <2,0>}
▪ (2) C＝{<x,y> | x,yR, x2＋y2＝1}

rn2 ... rnn
ri,j =是关系矩阵
第十三页，共66页
例题
• 设A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>} 的关系图和关系矩阵为:
1 100 0 01 1 0 00 0
01 00
第十四页，共66页
关系图
• 设V是顶点的集合,E是有向边的集合,令V={x1, x2,..., xn},如果xiRxj, 则有< xi,xj >E,那么 G=<V,E>就是R的关系图.
• 判断下列命题的真假
• 若AC且BD,则有AxBCxD;(真) • 若AxBCxD,则有AC且BD.(假)
第八页，共66页
n阶笛卡儿积
• 定义4.4 设A1, A2,…, An,是集合(n2),它们的n阶 笛卡儿积记作A1x A2x… xAn,其中 A1x A2x… xAn＝{<x1, x2,…, xn>| x1 A1, x2 A2,..., xn An }
• 例如平面直角的坐标:<1,-1>,<2,0>,<1,1>,他的特性是 : 当x≠y时,<x,y>≠<y,x> <x,y>=<u,v>等充分必要条件是x=u,y=v.
• 序偶与集合的关系, <x,y>≠<y,x>,但{x,y}={y,x}
第三页，共66页
有序n元组
• 定义4.2 :一个有序n元组(3≤n)是一个有序对,其中 第一个元素是一个有序n-1元组，一个有序n元组 记作＜x1, x2,…, xn,>,即 ＜x1, x2,…, xn,>=<< x1, x2,…, xn-1,>, xn >

(4)笛卡儿积运算对并和交运算满足分配律，即
A×(B∪C)=(A×B)∪(A×C) (B∪C)×A=(B×A)∪(C×A) A×(B∩C)=(A×B)∩(A×C) (B∩C)×A=(B×A)∩(C×A)
(5)AC ∧ BD A×B C×D
A×(B∪C)=(A×B)∪(A×C)的证明
任取 <x,y> <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) 所以 A×(B∪C)=(A×B)∪(A×C)
关于AC∧BD A×BC×D的讨论
该性质的逆命题不成立，可分以下情况讨论。 （1）当A=B=时，显然有AC 和 BD 成立。 （2）当A≠且B≠时，也有AC和BD成立，证明如下：
任取x∈A，由于B≠,必存在y∈B,因此有 x∈A∧y∈B
<x,y>∈A×B <x,y>∈C×D x∈C∧y∈D x∈C 从而证明了 AC。 同理可证 BD。
关于AC∧BD A×BC×D的讨论
该性质的逆命题不成立，可分以下情况讨论。 （3）当A＝而B≠时，有AC成立，但不一定有BD成立。
反例：令A＝,B＝{1},C＝{3},D＝{4}。 （4）当A≠而B＝时，有BD成立，但不一定有AC成立。
反例略。
例7.2
例7.2 设A={1,2},求P(A)×A。
解答 P(A)×A ＝ {,{1},{2},{1,2}}×{1,2} ＝ {<,1>,<,2>, <{1},1>,<{1},2>, <{2},1>,<{2},2>, <{1,2},1>,<{1,2},2>}

第一节
二元运算及其性质
一、二元运算的定义与实例
1．二元运算的定义 定义10.1 设S为集合,函数f：S×S→S称为S上的二元运 算, 简称为二元运算. 复习函数的定义： 例如，f：N×N→N, f(<x,y>)=x+y就是N上的二元运算， 即普通的加法运算， 但普通减法运算不是N上的二元运算。 注：验证一个运算是否为集合S上的二元运算主要考虑 两点：(1)S中任何两个元素都可以进行这种运算，且运算 的结果是唯一的。(2)S中任何两个元素的运算结果都属于 S，即S对该运算是封闭的。
20
17
2．代数系统的表示 (a)列出所有的成分：集合、运算、代数常数（如果存 在） 如<Z,+,0>, <P(S),∪,∩> (b)列出集合和运算，在规定系统性质时不涉及具有单 位元的性质（无代数常数） 如<Z,+>, <P(S),∪,∩> (c)用集合名称简单标记代数系统 在前面已经对代数系统作了说明的前提下使用如代数 系统Z, P(B)
（2）一元运算的表示 （a）公式表示 例5 设A={1/2,1,2},定义A上的一元运算◦： ∀ x,y∈R, ◦x=1/x. （b）运算表 设S＝{a1,a2,…,an}， 则S上一元运算可以用如下运算表 表示：
6
例6 设A=P({a,b}),∼ 为绝对补运算（{a,b}为全集）. 则∼ 的运算表为：
14
定理10.2 设◦为S上可结合的二元运算, e为该运算的 单位元, 对于x∈S，如果存在左逆元yl 和右逆元yr, 则有 yl = yr= y, 且y是x的惟一的逆元. 证：由 yl◦x = e 和 x◦yr = e 得 yl = yl◦e = yl◦ (x◦yr) = (yl◦x) ◦yr = e◦yr = yr 令yl = yr = y,则y 是x 的逆元. 假若y′∈S 也是x 的逆元,则 y′= y′◦e = y′◦ (x◦y) = (y′◦x) ◦y = e◦y = y 所以y 是x 惟一的逆元. 注： 对于可结合的二元运算， 可逆元素 x 只有惟一的逆元， −1 记作 x .

闭包的定义基于关系的传递 性，即如果关系R满足传递性， 那么对于任何元素x，如果存 在元素y和z，使得xRy和yRz， 那么一定存在一个元素z'，使 得xRz'。闭包就是由给定关系 和所有满足闭包定义的新元 素构成的关系集合。
闭包具有一些重要的性质， 这些性质决定了闭包在数学 和计算机科学中的广泛应用 。
同余关系的应用
应用1
在密码学中，同余关系可用于生成加 密密钥。例如，通过选择两个同余的 数作为密钥，可以确保加密和解密操 作的一致性。
应用2
在计算机科学中，同余关系可用于实 现数据校验。例如，通过将数据与一 个已知的校验值进行同余运算，可以 检测数据是否在传输过程中被篡改。
THANKS
感谢观看
反对称性
如果对于关系中的每一对 元素，如果元素x与元素y 有关系，且元素y与元素x 也有关系，但元素x与元 素y的关系不等于元素y与 元素x的关系，则称该关 系具有反对称性。
习题解析
习题1
判断给定的关系是否具有自反性、反自反性、对称性和反对称性。通过举例和推理，分析 给定的关系是否满足这些性质。
习题2
表示方法
总结词
掌握二元关系的表示方法是解题的关键。
详细描述
在数学中，我们通常使用笛卡尔积来表示二元关系。例如，如果A和B是两个集合， 那么A和B的笛卡尔积可以表示为A×B，它包含了所有形如(a, b)的元素，其中a属于 A，b属于B。
习题解析
总结词
通过解析具体习题，可以加深对二元关系定义和表示方法的理解。
有着广泛的应用。
05
习题五：关系的同余
同余关系的定义与性质
定义
反身性
对称性
传递性
如果对于任意元素$x$， 都有$f(x) = g(x)$，则 称$f$和$g$是同余的。

复
合 推论1 设F, G, H为函数, 则 (F∘G)∘H 和 F∘(G∘H)
和
都是函数, 且 (F∘G)∘H = F∘(G∘H)
反 推论2 设 f： B→C, g： A→B, 则 f∘g：A→C, 且
函
x∈A 都有 f∘g(x) = f (g(x)).
数
《离散数学》二元关系和函数
函数复合运算的性质
开始时刻0最后停止加工机器的停机时刻2728?集合任务集?函数和关系加工时间函数可以开始加工29?可行调度?分配到机器
《离散数学》二元关系和函数
在高等数学中，函数是在实数集合上进行讨论的， 其定义域是连续的。
本章把函数概念予以推广
4.6
⑴定义域为一般的集合，支持离散应用。
函
⑵把函数看作是一种特殊的关系：单值二元关系。
f4={<1,b>,<2,a>,<3,a>}，
性 f5={<1,b>,<2,a>,<3,b>}
质
f6={<1,b>,<2,b>,<3,a>},
f7={<1,b>,<2,b>,<3,b>}
《离散数学》二元关系和函数
函数的像
定义 设函数 f：A→B, A1A.
4.6
A1 在 f 下的像： f(A1) = { f(x) | x∈A1 }
《离散数学》二元关系和函数
函数复合运算的性质
(2) 假设存在 x1, x2∈A使得 fg(x1) = f g(x2)
由合成定理有 f (g(x1))= f (g(x2)). 因为 f：B→C是单射的, 故 g(x1)=g(x2). 又由 于 g：A→B也是单射的, 所以 x1=x2. 从而证 明 f∘g：A→C是单射的. (3) 由 (1) 和 (2) 得证.

6
二、从A到B的关系与A上的关系 定义7.4 设A,B 为集合,A×B 的任何子集所定义的二 元关系叫做从A 到B 的二元关系,当A=B 时则叫做A 上 的二元关系. 例 A={0,1}, B={1,2,3}, 那么R1={<0,2>}, R2=A×B, R3=∅, R4={<0,1>} R1, R2, R3, R4 是从A 到B 的二元关系, R3和R4同时 也是A 上的二元关系.
{<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>
,<3,c>} B×A =
{<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>,<a,3>,<b,3>
,<c,3>}
2
注:笛卡儿积的性质 （1）不适合交换律 A×B ≠ B×A (A≠B, A≠∅, B≠∅) （2）不适合结合律 (A×B)×C ≠ A×(B×C) (A≠∅, B≠∅, C≠∅) （3）对于并或交运算满足分配律 A×(B∪C) = (A×B)∪(A×C) (B∪C)×A = (B×A)∪(C×A) A×(B∩C) = (A×B)∩(A×C) (B∩C)×A = (B×A)∩(C×A) （4）若A 或B 中有一个为空集，则A×B 就是空集. A×∅ = ∅×B = ∅ （5）若 |A| = m, |B| = n, 则 |A×B| = mn
这些性质是二元集{x,y}所不具备的.例如当x≠y 时 有{x,y}={y,x}.
1
二、笛卡儿积 定义7.2 设A,B 为集合，用A中元素为第一元素,B中 的元素为第二元素构成有序对.所有这样的有序对组 成的集合叫做A 与B 的笛卡儿积,记作A×B. 笛卡儿积的符号化表示为