当前位置：文档之家 › 离散数学——二元关系习题讲解

离散数学——二元关系习题讲解

  • 格式：ppt
  • 大小：380.50 KB
  • 文档页数：5

下载文档原格式

  / 5

合集下载

离散数学(第14讲)二元关系

离散数学(第14讲)二元关系


13
Discrete Mathematics 2）反之，在非空集合A上给定一个划分π，则可将A 分割成若干个划分块。 根据以下条件定义A上的二元关系R，即对任何元 素x,y∈A，如果x和y在同一划分块中，则xRy。显 然，R是A上的等价关系，称为由划分π所诱导的 等价关系，并且该等价关系的商集就等于π 。 结论 的划分是一一对应的。 集合A上的等价关系与集合crete Mathematics 在非空集合A上给定一个划分 在非空集合 上给定一个划分π={A1,A2,…,Am}， 上给定一个划分 ， 找出由π所唯一确定的 所唯一确定的A上的等价关系的方法如 找出由 所唯一确定的 上的等价关系的方法如 下： 把划分π的每一块 都拿出来， 把划分 的每一块Ai都拿出来，并且作其笛卡 的每一块 尔积A 尔积 i× Ai(i=1,2,..,m) ，然后求这些笛卡尔积的 并集，即为所求， 并集，即为所求，即
1
Discrete Mathematics 例 设A={1,2,3,4,5,6,7,8}， ， R={<x,y>|x,y∈A∧x =y(mod3)}，其中 =y(mod3) ∈ ∧ ，其中x 的含义是x和 分别除以 后的余数相等， 分别除以3后的余数相等 的含义是 和y分别除以 后的余数相等，即x-y可以 整除。 上的等价关系， 被3整除。不难验证 为A上的等价关系，它的关系 整除 不难验证R为 上的等价关系 图如下图所示： 下图所示 图如下图所示：
Discrete Mathematics
Discrete Mathematics 3、商集 、 为非空集合A上的等价关系， 定义 设R为非空集合 上的等价关系，以R的不相 为非空集合 上的等价关系 的不相 交的等价类为元素的集合叫做A在 下的商集， 下的商集 交的等价类为元素的集合叫做 在R下的商集，记 作A/R，即 ， A/R={[a]R |a∈A} ∈ 显然， 显然，在例1中，A在R下的商集是 中 在 下的商集是 A/R ={{1,4,7},{2,5,8},{3,6}}。 。
离散数学 第3章 二元关系

离散数学 第3章 二元关系


则R∪S,R∩S,R-S, R 等可分别定义如下:
x(R∪S)y xRy∨xSy x(R∩S)y xRy∧xSy x(R-S)y xRy∧x$y x R y xRy
第3章 二元关系
例3.1-3平面上的几何图形是平面R2 的子集,也是一
种关系.设(参看图3.1―2) R1={〈x,y〉｜〈x,y〉∈R2∧x2+y2≤9} R2={〈x,y〉｜〈x,y〉∈R2∧1≤x≤3) ∧(0≤y≤3)}
n
上 的 m 元 关 系 . 那 么 R1=R2, 当 且 仅 当 n=m, 且 对 一 切 i,1≤i≤n,Ai=Bi,并且R1和R2是相等的有序n重组集合
第3章 二元关系
3.1.2 二元关系
最重要的关系是二元关系.本章或
第3章 二元关系
第3章
二元关系
3.1 基本概念 3.2 关系的复合
3.3 关系上的闭包运算
3.4 偏序关系
3.5 等价关系和划分
第3章 二元关系
3.1
3.1.1 关系
基本概念
关系的数学概念是建立在日常生活中关系的概念 之上的.让我们先看两个例子 例3.1-1 设A={a,b,c,d}是某乒乓球队的男队员集合, B={e,f,g}是女队员集合.如果A和B元素之间有混双配对
第3章 二元关系
图 3.1―1
第3章 二元关系
A叫做关系R的前域,B叫做关系R的陪域
D(R)={x｜y(〈x,y〉∈R)}叫做关系R的定义域 R(R)={y｜x(〈x,y〉∈R)}叫做关系R的值域 关系是序偶的集合,对它可进行集合运算,运算结果 定义一个新关系.设R和S是给定集合上的两个二元关系,
关系的是a和g,d和e.我们可表达为:
离散数学(二元关系)课后总结

离散数学(二元关系)课后总结

第四章二元关系例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例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 证毕.例3、令A={1,2,3}给定A上八个关系如下：可见这八个关系中R1、R3、R4是自反的。

离散数学 二元关系(2)

离散数学 二元关系(2)

西南科技大学
17
计算机科学与技术学院
Discrete Mathematics
② 合成运算成立结合律
定理 设 R，S，T分别是A到B，B到C，C到D的关 系， 则有(R S) T = R (S T)。 证明：略
西南科技大学
18
计算机科学与技术学院
Discrete Mathematics (4)关系的幂 定义 设R是A上的二元关系，n∈N，则关系R的n次 幂Rn定义为： (1). R0 =A是A上的恒等关系，即R0={<x,x>|xA}； (2). R1=R (3). Rn+1=Rn R
西南科技大学
5
计算机科学与技术学院
Discrete Mathematics
定义的有关说明:
1. R与S能进行合成的必要条件是R的后域B一定是 S的前域B，否则就不能合成。 2. <x,z>有合成关系的定义为：至少有一个做中间 桥梁的元素y属于B，使x,y有关系R，y,z有关系S。 例1 设A={1,2,3,4,5}，B={3,4,5}，C={1,2,3}
R是A到B的关系，且R={<x,y>|x+y=6}，
S是B到C的关系，且S={<y,z>y-z=2} 。
求RS
西南科技大学
6
计算机科学与技术学院
Discrete Mathematics 只需从两个关系的二重组中搜索： ∵<1,5>∈R,<5,3>∈S,∴<1,3>∈RS
∵<2,4>R,<4,2>S,∴<2,2>RS
S R= {<d,b> ,<c,b>}
离散数学---二元关系和函数

离散数学---二元关系和函数

f 1 : ranf →N, f 1 (x) = x/2
编辑ppt
22
反函数
定理 设 f：A→B是双射的, 则f 1：B→A也是双射的.
证 因为 f 是函数, 所以 f 1 是关系, 且
dom f 1 = ranf = B , ran f 1 = domf = A, 对于任意的 y∈B = dom f 1, 假设有x1, x2∈A使得
<x,y1>∈f∧<x,y2>∈f y1 = y2
编辑ppt
23
反函数的定义及性质
对于双射函数f：A→B, 称 f 1：B→A是它的反 函数.
反函数的性质 定理 设 f：A→B是双射的, 则
f 1∘f = IB, f∘f 1 = IA
对于双射函数 f：A→A, 有 f 1∘f = f∘f 1 = IA
T(x) 1 0 1 0 0 1 1 1
编辑ppt
15
自然映射
5. 设 R 是 A 上的等价关系, 令 g：A→A/R g(a) = [a], a∈A
称 g 是从 A 到商集 A/R 的自然映射.
编辑ppt
16
实例
例8 (1) A的每一个子集A’都对应于一个特征函 数, 不同的子集对应于不同的特征函数. 例如 A={a, b, c}, 则有
解 BA = {f0, f1, … , f7}, 其中 f0={<1,a>,<2,a>,<3,a>}, f1={<1,a>,<2,a>,<3,b>} f2={<1,a>,<2,b>,<3,a>}，f3={<1,a>,<2,b>,<3,b>} 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>}
离散数学第四章 二元关系

离散数学第四章 二元关系


| A | m | B | n
| A B | mn
4．笛卡儿乘积运算对并和交运算满足分配率，即
2016/1/12
4.1 多重序元与笛卡尔乘积
笛卡尔乘积
设 A { Ai }1≤i≤n 是加标集合，与 A 对应的指标集合是集合 A1 , A2 ,, An
的笛卡儿乘积可以表示成
例如：
例4.4 设集合 A={2,3,5,9} ，试给出集合 A 上的小于或等于关系，大于或等于关 系。 解：令集合 A 上的小于或等于关系为 R1，大于或等于关系为 R2，根据定义4.1应有：
R1 { 2, 2 , 3,3 , 5,5 , 9,9 , 2,3 , 2,5 , 2,9 , 3,5 , 3,9 , 5,9} R2 { 2, 2 , 3,3 , 5,5 , 9,9 , 3, 2 , 5, 2 , 9, 2 , 5,3 , 9,3 , 9,5}
笛卡尔乘积
笛卡儿乘积运算具有以下性质。
• （ 1） A ( B C ) ( A B ) ( A C ) • （ 2） A ( B C ) ( A B ) ( A C ) • （ 3） ( A B ) C ( A C ) ( B C ) • （ 4） ( A B ) C ( A C ) ( B C ) 5 . A C B D A B C D
2016/1/12
2
主要内容
PART 01 PART 02 01 PART 03 01 PART 04 01 PART 05 01 PART 06 01 PART 07 01 PART 08 01
多重序元与笛卡尔乘积 关系的基本概念
关系的运算
二元关系(离散数学)

二元关系(离散数学)

第二章二元关系习题2.11.a)R = {<0, 0>, <0, 2>, <2, 0>, <2, 2>}b)R = {<1, 1>, <4, 2>}2.R1⋃ R2 = {<1, 2>, <2, 4>, <3, 3>, <1, 3>, <4, 2>}R1⋂ R2 = {<2, 4>}dom R1= {1, 2, 3}dom R2= {1, 2, 4}ran R1= {2, 3, 4}ran R2= {2, 3, 4}dom (R1⋃ R2) = {1, 2, 3, 4}ran (R1⋂ R2) = {4}3.证明：（根据定义域和值域的定义进行证明）因为x ∈ dom (R1⋃ R2) 当且仅当有y ∈ B使得<x, y> ∈ (R1⋃ R2)当且仅当有y ∈ B使得<x, y> ∈ R1或<x, y> ∈ R2当且仅当有y ∈ B使得<x, y> ∈ R1或有y ∈ B使得<x, y> ∈ R2当且仅当x ∈ dom (R1) 或x ∈ dom (R2)当且仅当x ∈ dom (R1) ⋃ dom (R2)所以，dom (R1⋃ R2) = dom (R1) ⋃ dom (R2) 。

因为若x ∈ ran (R1⋂ R2)，则有x ∈ A使得<x, y> ∈ (R1⋂ R2) ；有x ∈ A使得<x, y> ∈ R1且<x, y> ∈ R2 ；有x ∈ A使得<x, y> ∈ R1且有x ∈ A使得<x, y> ∈ R2 ；x ∈ ran (R1) 且x ∈ ran (R2)；x ∈ ran (R1) ⋂ ran (R2)。

所以，ran (R1⋂ R2) ⊆ ran (R1) ⋂ ran (R2)。

离散数学第七章二元关系

离散数学第七章二元关系


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
关系的表示
离散数学(第11讲)二元关系

离散数学(第11讲)二元关系


运算“ ”称为合成运算。
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 二元关系

4 二元关系


4.2 关系图与关系矩阵
（1）关系图 ）
定义4.2.1 设A,B为任意非空有限集，R⊆A×B。以A到 定义 为任意非空有限集 到 B上的每个元素为一个结点（小圆圈“ο”表示 上的每个元素为一个结点（ 表示），对 上的每个元素为一个结点 小圆圈“ 对 每个<x,y>∈R,画一条从 到 y的有向边 带箭头的直线 画一条从x到 的有向边 的有向边(带箭头的直线 每个 ∈R, 画一条从 或弧线)，这样得到的有向图称为关系R的关系图GR。 或弧线 ，这样得到的有向图称为关系 的关系图 P92 例1 画出R={﹤1,a﹥,﹤1,b﹥,﹤2,a﹥,﹤3,b﹥}的关系图 画出 ﹤ ﹥ ﹤ ﹥ ﹤ ﹥ ﹤ ﹥ 的关系图 有多少个序偶，就有多少条有向边， 有多少个序偶，就有多少条有向边， 关系R与关系图 之间是一一对应的关系。 与关系图G 关系 与关系图 R之间是一一对应的关系。
对于A中每个a 对于A中每个a, b, c，若aRb且bRc，则aRc，称R是传递 aRb且bRc， aRc， 的，即 关系R是传递的⇔ 关系R是传递的⇔(∀a)(∀b)(∀c)(a,b,c∈A∧aRb∧bRc→aRc) )(∀ )(∀ )(a aRb∧bRc→aRc)
注：必须严格按照→真值的定义来判断. 必须严格按照→真值的定义来判断.
4.2 关系图与关系矩阵
P93 例2
(1) 若关系 是自反的 当且仅当在关系图上每个结点都 若关系R是自反的 当且仅当在关系图上每个结点都 是自反的,当且仅当在关系图上 有自环. 有自环 (2) 若关系是反自反的 当且仅当关系图上每个结点都没 若关系是反自反的, 当且仅当关系图上每个结点都没 有自环. 有自环 (3) 若关系 对称 当且仅当在关系图上 任两个结点间若 若关系R对称 当且仅当在关系图上,任两个结点间若 对称,当且仅当在关系图上 有有向边,必是成对出现 必是成对出现. 有有向边 必是成对出现 (4)若关系是反对称的 当且仅当关系图上，任两个结点 若关系是反对称的, 当且仅当关系图上， 若关系是反对称的 间若有有向边,必是一条单方向的边 必是一条单方向的边. 间若有有向边 必是一条单方向的边 (5)传递关系较复杂 不易从关系图中直接判断 传递关系较复杂,不易从关系图中直接判断 传递关系较复杂 不易从关系图中直接判断.
离散数学 二元关系

离散数学 二元关系

2019/3/20 14
<x,y>R xRy 也称之为x与y有Ｒ关系。 后缀表示 中缀表示
<x,y>R xRy 也称之为x与y没有Ｒ关系。
例3. R是实数集合，R上的几个熟知的关系
≤ ≥ =
y x2+y2=4
x
从例3中可以看出关系是序偶(点)的集合 (构成线、面)。
2019/3/20 15
作业 P105 ⑵
2019/3/20 12
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>}α×β
2019/3/20
AB (CACB)。
9
5) 设A、B、C、D为非空集合，则 ABCDAC∧BD 证明：首先,由ABCD 证明AC∧BD 任取xA，任取yB，所以 xAyB<x,y>A×B <x,y>C×D (由ABCD ) xCyD 所以, AC∧BD。 其次, 由AC，BD 证明ABCD 任取<x,y>A×B xAyB xCyD (由AC，BD) <x,y>C×D 所以, ABCD 证毕。
2019/3/20ቤተ መጻሕፍቲ ባይዱ16
关系的表示方法 枚举法： 即将关系中所有序偶一一列举出，写在大括号内。 如R ={ <1,1>,<1,2>,<1,3>, <1,4>, <2,2>, <2,3>, <2,4>, <3,3>, <3,4>, <4,4>} 。 谓词公式法： 即用谓词公式表示序偶的第一元素与第二元素间 的关系。例如 R={<x,y>|x<y} 有向图法： RA×B,用两组小圆圈(称为 结点)分别表示A和B 的元素，当<x,y>R时，从x到y引一条有向弧 (边)。这样得到的图形称为R的关系图。

离散数学 二元关系(3)


则a,b∈A，a≠b，且<a,b>∈R，<b,a>∈R，
因R是传递的，∴<a,a>∈R，<b,b>∈R。
与R是反自反的矛盾。
∴R具有反对称性。
西南科技大学
23
计算机科学与技术学院
Discrete Mathematics 有关说明: (1). 由反自反性和传递性可以推出反对称性。
(2). 拟序关系具有反自反性，反对称性和传递性。
最大元不存在，极大元是4、6、15。
(3).B3={2,3,4,6,12,30}，则B3 的最大元、最小元均 不存在；极大元是12、30，极小元是2、3。
西南科技大学
18
计算机科学与技术学院
Discrete Mathematics 3、上界、下界、上确界、下确界 定义 设<A,≤>是偏序集，集合BA
系用哈斯图表示。
哈斯图是关系图的简化，其省略方法如下:
西南科技大学
5
计算机科学与技术学院
Discrete Mathematics (1). 把所有结点的自回路均省略，只用一个结点
表示A的元素。
(2). 省略所有有向边的方向，通过适当排列A中
元素的位置来确定它们的关系，如a≤b，则a画
在b的下方(向上画)。 (3).如a≤b，b≤c，则必有a≤c。所以，如a到b有 边，b到c有边，则把a到c的有向边省略掉。
④4≤5，5≤4两者均不成立，4、5的位置的高低不 决定两者的序关系。 ⑤该关系图共有14条有向弧，而哈斯图共有6条边， 省略了8条边。 4 6
5 2 1 8 3
西南科技athematics (2).哈斯图为：
(3).A={ａ,ｂ,ｃ}，则包含关系R是ρ(A)上的偏 序关系。则<ρ(A)，R>是偏序集,其哈斯图如下:

离散数学二元关系习题讲解


极 大 元
极 小 元
作业
2.设集合X={x1,x2,x3,x4,x5}上的偏序关系如下图所示 最 最 极 极 上 下 ，求X的最大元、最小元、极大元、极小元。求子 集 上 下 大 小 大 小 确 确 集X1={x2,x3,x4}，X合 ={x ,x ,x } ， X ={x ,x ,x } 的上 界 界 2 3 4 5 3 1 3 5 元 元 元 元 界 界 界、下界、上确界、下确界、最大元、最小元、极 大元和极小元。 X1 无 x4 x2， x4 x1 x x1 x4
3
偏序关系
1.设集合A={a,b,c,d,e,f,g,h}，对应的哈斯图见下图令 B1={a,b}，B2={c,d,e}。求出B1，B2的最大元、最小 元、极大元、极小元、上界、下界、上确界、下确 界。 h
f d
c a
4
g e
集 合 B1
最 大 元 无
最 小 元 无
b
B2
无
c
上 下 下 上界 确 确 界 界 界 c,d,e,f a,b a,b ,g,h 无 c 无 a, b, h c d,e c h c
x1
x3 x3 x1 x1
4ቤተ መጻሕፍቲ ባይዱ
X2
x2 x3
x3 x1 x1
无 x5 无
X3
x5 X
x4， x3， 无 x3 x5 x1 x x5 x1 x1
5
无 x5
x4
5
x4， x5
二元关系
二元关系基本概念(重点) 关系的运算 关系的性质(重点) 关系的闭包运算 等价关系与偏序关系(难点)
关系的性质
例5 判断下述关系所具备的性质。
(1)集合A上的恒等关系，全域关系。 (2)R1={<x,y>｜x≤y， x,y∈N}注：将≤改为＜? (3)R2={<x,y>｜x|y，x,y∈N-{0}} (4)R3={<S1,S2>｜S1S2，S1,S2∈P(S)}其中P(S)是 S的幂集。注：若改为? (5)R4={<x,y>｜x+y=偶数，x,y∈N}

离散数学 ch2.二元关系(3,4节)


下边R3、R4、 R6 、 R8均是对称关系。
1
。

1
。
2
。 。 3
R1
1
。 。 3
R2
1
。 。 2。 。 3 3
R3
1
R4
1
。
2
。
2
。
。
2
。 。 3
R5
。 。 3
R6
。 。 2。 。 3 3
R7 R8
四.反对称性
定义:设R为集合X中关系,若对任何x, y∈X,如果有 （x,y)∈ R,和(y ,x)∈ R,就有x=y,则称R为A中反对称关系 。 如实数的小于关系<，≤ ，均是反对称的。父子关系是反 对称的。
R 3 {(1,2), (3,0), (3,2)}
性质 判定 自反性
从关系的有向图 每个结点都有环
从关系的矩阵 主对角线全是1
反自反性
对称性 反对称性
每个结点都无环
主对角线全是0
不同结点间如果有边, 是以对角线为对称 则有方向相反的两条 的矩阵 边. 不同结点间,最多有一 以主对角线为对称 条边. 的位置不会同时为1
实际上r(R)、(s(R) 、t(R)) 就是包含R的“最小” 的自反(对称、传递)关系。 三.计算方法 定理1.给定 A中关系R,则 r(R)=R∪IA。 证明：令R’=R∪IA,显然R’是自反的和RR’，下 面证明R’是“最小的”：如果有A上自反关系 R”且RR”,又IAR”,所以 R∪IAR”,即R’R”。 所以R’就是R的自反闭包。即r(R)=R∪IA 。 ~ R 定理2.给定 A中关系R,则 s(R)=R∪ 。 证明方法与1.类似。（集合法） 定理3.给定 A中关系R,则 t(R)=R∪R2∪R3∪... 。 证明：令R’= R∪R2∪R3∪..., ⑴显然有 RR’ ；

离散数学第四章二元关系和函数

③ F在A上的限制记作FA= {<x,y>|xFyxA}; ④ A在F下的象F[A]=ran(FA).
例题
1. 设F,G是N上的关系,其定义为 F={<x,y>|x,yNy=x2}; G={<x,y>| x,yNy=x+1}, 求G-1,FoG,F{1,2},F[{1,2}]
2. 解:
① G-1={<1,0>,<2,1>,<3,2>,...,<x+1,x>,...}; ② z((z=x+1)y=z2)
① <<x,y>,z>(AxB)xC, <x,<y,z>> Ax(BxC), <x,<y,z>> (AxB)xC.
笛卡儿积运算具有的性质(2)
1. 笛卡儿积运算对或运算满足分配律, Ax(BC)=(AxB)(AxC) (BC)xA=(BxA)(CxA) Ax(BC)=(AxB)(AxC) (BC)xA=(BxA)(CxA)
2. domR1=ranR1=Z. R={<0,1>,<0,-1>,<1,0>,<-1,0>} domR2=ramR2={0,1,-1}
3. 图解方法
1
0
-1
R2
domR2
1 0 -1
ranR2
逆、合成、限制和象
1. 定义4.9: 设F,G为任意的关系,A为集合,则
① F的逆记作F-1, F-1={<x,y>|yFx}; ② F与G的合成记作FoG={<x,y>|z（xGzzFy）};
0100 1010 . 0001 0000

离散数学课件第四章二元关系习题


闭包的定义基于关系的传递 性，即如果关系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. 合计100分2. 给出每小题得分(注意: 写出扣分理由).3. 总得分在采分点1处正确设置.1 设R={<x,y>|x,y∈N且x+3y=12}.【本题合计10分】(1) 求R的集合表达式(列元素法);(2) 求domR, ranR;(3) 求RR;(4) 求R{2,3,4,6};(5) 求R[{3}];解(1) R={<0,4>,<3,3>,<6,2>,<9,1>,<12,0>}【2分】(2) domR={0,3,6,9,12}, ranR={0,1,2,3,4}【2分】(3) RR={<3,3>, <0,4>}【2分】(4) R{2,3,4,6}={<3,3>, <6,2>}【2分】(5) R[{3}]={3}【2分】2 设R,F,G为A上的二元关系. 证明:(1)R(F∪G)=RF∪RG(2)R(F∩G)RF∩RG(3)R(FG)=(RF)G.【本题合计18分：每小题6分，证明格式正确得3分，错一步扣1分】证明(1)<x,y>,<x,y>∈R(F∪G)t (xRt∧t(F∪G)y) 复合定义t(xRt∧(tFy∨tGy) ∪定义t((xRt∧tFy)∨(xRt∧tGy)) ∧对∨分配律t(xRt∧tFy)∨t(xRt∧tGy) 对∨分配律x(RF)y∨x(RG)y 复合定义x(RF∪RG)y ∪定义得证(2)<x,y>,x(R(F∩G))yt(xRt∧t(F∩G)y) 复合定义t(xRt∧(tFy∧tGy)) ∩定义t((xRt∧tFy)∧(xRt∧tGy)) ∧幂等律, ∧交换律, ∧结合律t(xRt∧tFy)∧t(xRt∧tGy) 补充的量词推理定律x(RF)y∧x(RG)y 复合定义x(RF∪RG)y ∪定义得证(3)<x,y>,<x,y>∈R(FG)s (<x,s>∈R∧<s,y>∈(FG)) 定义s (<x,s>∈R∧t (<s,t>∈F∧<t,y>∈G))) 定义st(<x,s>∈R∧<s,t>∈F∧<t,y>∈G) 辖域扩张公式ts((<x,s>∈R∧<s,t>∈F)∧<t,y>∈G) 存在量词交换t(s(<x,s>∈R∧<s,t>∈F)∧<t,y>∈G) 辖域收缩公式t(<x,t>∈(RF)∧<t,y>∈G) 复合定义<x,y>∈(RF)G 复合定义得证3 设F={<x,y>|x－y+2>0∧x－y－2<0}是实数集R上的二元关系, 问F具有什么性质并说明理由.【本题合计10分：每种性质2分----答对得1分，正确说明理由得1分】解F={<x,y>|x－y+2>0∧x－y－2<0}={<x,y>|－2<x－y<2}自反性: x∈R, <x,x>∈F显然.对称性: <x,y>,<x,y>∈F－2<x－y<2－2<y－x<2<y,x>∈F.不具有反自反性: 反例<2,2>∈F不具有反对称性: 反例<2,3>,<3,2>∈F, 显然2≠3不具有传递性: 反例<2,>,<,5>∈F, 但<2,5>不属于F.4 设A={a,b,c}, R={<a,b>,<a,c>},(1) 给出R的关系矩阵;(2) 说明R具有的性质(用关系矩阵的判定方法说明理由)【本题合计12分：第（1）小题2分；第（2）小题10分----答对性质得1分，说明理由得1分】解(1)R的关系矩阵M(R)为0 1 10 0 00 0 0(2)不具有自反性: M(R)的主对角线不是全为1是反自反的: M(R)的主对角线全为0不具有对称性: M(R)不是对称的是反对称的: M(R)对称的位置至多有一个1是传递的: M(R2)如下0 0 00 0 00 0 0显然满足: 如果M(R2)任意位置为1, 则M(R)对应位置也为15 设A≠, RA×A, 证明(1) r(R)=R∪I A(2) s(R)=R∪R-1【本题合计12分，每小题6分----证明格式正确得2分，过程错误一步扣1分】证明(1) 只要证明r(R)R∪I A和R∪I A r(R)即可先证r(R)R∪I A:I A R∪I AR∪I A自反(自反性的充要条件)r(R)R∪I A (自反闭包的最小性)再证R∪I A r(R):Rr(R)∧I A r(R) (自反闭包的性质及自反性的充要条件)R∪I A r(R)得证(2) 只要证明s(R)R∪R-1及R∪R-1s(R)即可先证s(R)R∪R-1:(R∪R-1)-1=R∪R-1 (理由如下: <x,y>,<x,y>∈(R∪R-1)-1<y,x>∈R∪R-1 (逆运算定义)<y,x>∈R∨<y,x>∈R-1 (∪定义)<x,y>∈R-1∨<x,y>∈R (逆运算定义)<x,y>∈R∪R-1 (∪定义, ∪交换律)所以(R∪R-1)-1=R∪R-1 )R∪R-1是对称的(对称性的充要条件)s(R)R∪R-1 (对称闭包的最小性)再证R∪R-1s(R):Rs(R) (闭包定义) ∧R-1s(R) (后者理由如下:<x,y>,<x,y>∈R-1<y,x>∈R (逆运算定义)<y,x>∈s(R)<x,y>∈s(R) (s(R)是对称的)所以R-1s(R) )R∪R-1s(R)得证6 设A={a,b,c,d}, R={<a,d>,<b,a>,<b,c>,<c,a>,<c,d>,<d,c>}, 用Warshall算法求t(R).【本题合计8分】解依次求出W0,W1,W2,W3,W4=t(R)【2分】W0=M(R)= 0 0 0 11 0 1 01 0 0 10 0 1 0【1分】W1= 0 0 0 11 0 1 11 0 0 10 0 1 0【1分】W2= 0 0 0 11 0 1 11 0 0 10 0 1 0【1分】W3= 0 0 0 11 0 1 11 0 0 11 0 1 1【1分】W4= 1 0 1 11 0 1 11 0 1 11 0 1 1【1分】即t(R)={<a,a>,<a,c>,<a,d>,<b,a>,<b,c>,<b,d>,<c,a>,<c,c>,<c,d>,<d,a>,<d,c>,<d,d>}.【1分】7 设R为A上的自反和传递的关系, 证明R∩R-1是A上的等价关系.【本题合计10分】证明自反性: x∈A,xRx∧xR-1x x(R∩R-1)x【3分】对称性: x,y∈A,x(R∩R-1)y xRy∧xR-1y yR-1x∧yRx y(R∩R-1)x【3分】传递性: x,y,z∈A,x(R∩R-1)y∧y(R∩R-1)z xRy∧xR-1y∧yRz∧yR-1z(xRy∧yRz)∧(xR-1y∧yR-1z) xRz∧xR-1z x(R∩R-1)z【4分】得证.8 设A={1,2,3,4}, 在A×A上定义二元关系R,<u,v>,<x,y>∈A×A, <u,v>R<x,y>u+y=v+x(1)证明R是A×A上的等价关系;(2)确定由R引起的对A×A的划分.【本题合计10分】解(1)自反性: <x,y>∈A×A, <x,y>R<x,y>显然成立.【2分】对称性: <x,y>,<u,v>∈A×A,<x,y>R<u,v>x+v=y+uu+y=v+x<u,v>R<x,y>【2分】传递性: <x,y>,<u,v>,<s,t>∈A×A,<x,y>R<u,v>∧<u,v>R<s,t>x+v=y+u ∧u+t=v+sx+t=y+s<x,y>R<s,t>【2分】因此R 是A×A 上的等价关系.(2)根据R 的定义, <x,y>R<u,v>x+v=y+ux －y=u －v, 因此[<x,y>]R={<u,v>|<u,v>∈A×A ∧u －v=x －y},【2分】 所以R 引起的划分如下:{ { <1,1>,<2,2>,<3,3>,<4,4>},{<1,2>,<2,3>,<3,4>},{<2,1>,<3,2>,<4,3>},{<1,3>,<2,4>},{<3,1>,<4,2>},{<1, 4>},{<4,1>} }【2分】9 设R, S 是A={1,2,3,4}上的等价关系, 其关系矩阵分别为 【本题合计5分】1100110000100001R M ⎛⎫ ⎪ ⎪= ⎪ ⎪⎝⎭, 1000011001100001S M ⎛⎫ ⎪ ⎪= ⎪ ⎪⎝⎭.求包含R 与S 的最小的等价关系.分析: 设包含R 与S 的最小等价关系为T ，则RT, ST, 所以RS T. 而T 是等价关系，根据等价关系的定义，T 应该具有自反性、对称性和传递性。

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

3
偏序关系
1.设集合 设集合A={a,b,c,d,e,f,g,h}，对应的哈斯图见下图令 设集合 ， B1={a,b}，B2={c,d,e}。求出 1，B2的最大元、最小元、 的最大元、最小元、 ， 。求出B 极大元、极小元、上界、下界、上确界、下确界。 极大元、极小元、上界、下界、上确界、下确界。
x1
x3 x3 x1 x1
无 x5 无
X3
x5 X
x4， x3， 无 x3 x5 x1 x x5 x1 x1
5
无 x5
x4
5
x4， x5
二元关系
二元关系基本概念(重点) 二元关系基本概念(重点) 关系的运算 关系的性质(重点) 关系的性质(重点) 关系的闭包运算 等价关系与偏序关系(难点) 等价关系与偏序关系(难点)
关系的性质
判断下述关系所具备的性质。 例5 判断下述关系所具备的性质。 (1)集合 上的恒等关系，全域关系。 集合A上的恒等关系 全域关系。 集合 上的恒等关系， (2)R1={<x,y>｜x≤y， x,y∈N}注：将≤改为＜? 改为＜ ｜ ， ∈ 注 改为 (3)R2={<x,y>｜x|y，x,y∈N-{0}} ｜ ， ∈ (4)R3={<S1,S2>｜S1⊆S2，S1,S2∈P(S)}其中 ｜ ⊆ ， 其中P(S)是 ∈ 其中 是 S的幂集。注：若⊆改为⊂? 的幂集。 改为⊂ 的幂集 (5)R4={<x,y>｜x+y=偶数，x,y∈N} 偶数， ∈ ｜ 偶数 (6)R5={<x，y>｜ x ≡ y(mod3), x,y∈Z} ， ｜ ∈
h f d c a
4
g e
集 合 B1 B2
最 大 元 无 无
最 小 元 无 c
上 下 下 上界 确 确 界 界 界 c,d,e,f a,b a,b ,g,h 无 c 无 a, d,e c h b,c h c
极 大 元
极 小 元
b
作业
2.设集合 设集合X={x1,x2,x3,x4,x5}上的偏序关系如下图所示 设集合 上的偏序关系如下图所示 的最大元、 集 最 极大元、极小元。 ，求X的最大元、最小元、最 极 、极小元。求子 下 的最大元 最小元、极大元 极 上 下 上 大 小 ,x 界 确 集X1={x2,x3,x4}，X合 大 4,x5}，X3={x1,x界 5}的上 确 ， 2={x3,x 小 ， 的上 3 元 元 元 元 界 界 下界、上确界、下确界、最大元、最小元、 界、下界、上确界、下确界、最大元、最小元、极 2， 大元和极小元。 大元和极小元。 X1 无 x4 x2 x4 x1 x x1 x4
2
等价关系
1．设A={1,2,3,4}，在A×A上定义二元关系 ： ． 上定义二元关系R： ， × 上定义二元关系 <<x,y>,<u,v>>∈R ⇔ x+y = u+v， ∈ ， 导出的划分. 求R导出的划分 导出的划分 2．设R是Z上的模 n 等价关系 即 ． 是 上的模 等价关系, x∼y ⇔ x ≡ y(modn), ∼ 试给出由R确定的 的划分π 确定的Z的划分 试给出由 确定的 的划分π.