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

离散数学 关系4

  • 格式：ppt
  • 大小：2.70 MB
  • 文档页数：63

下载文档原格式

  / 63

合集下载

离散数学关系的性质

离散数学关系的性质

任取<x, y>
<x, y>R<y, x>R ………..………. x=y
前提
推理过程
结论
例6 证明若 R∩R1IA , 则 R 在 A 上反对称. 证 任取<x, y>
<x, y>R <y, x>R <x, y>R <x, y>R 1
<x, y>R∩R 1 <x, y>IA x=y 因此 R 在 A 上是反对称的.
有 R)
例(18) 不判自断反下也图不中反关自系反的；性对质称, 并, 不说反明对理称由；不传递. 注任因注<和只注列任证M对因f于反<W(于W对例例考当 R证考对其o3xx1r)aat意取此意证意的取于此等对等于23察检明察于中,,[M<rrj自和iyyss,x： <有 ： ： 元 <k于 称 于 k设 G查模 GkE>>hht(任R设RRj,反==RRR=aa]xx1,R1y是31的的ll在在M在素关：关A完 式000,,)则在123ll取A>y3，＝ ＝tR算算y,,,RR和＝＝＝＝o>111和r＝ 每 每上上上记系恒系所>是M∪<,,,和A不{{=n证法法………，{{{{xR<<({一一述述述作,等,有MtAM<<<Rad3<<上[,<是aaa小小明∩：的,,,<,iaaao)上ynnnyy0,,,y+,条条等等等关的Mbbb,,,ayR,,同>是,,,,=abc反jE于于依,z>,,>]Rxx的MMM>>，ckI>边边式式式系顶>zc,A,阶反+>>}[,}<自<,关关据>}<在kkk<i传,<b,,中中中点I,a,M1[[[b的jb对ARy反,,如如系系iii]Rc,b,递,,,,RRA.Rbt1矩矩矩后c，jjj>>1单[称]]]z；>>果 果,,,i===},}上关>,R阵阵阵就整整}}空<，R111，位的k有有(2x当当当自系R]2的的的得除除1……关,,矩.,一一Ry且且且)R反,RR元元元到关关……系>M阵R32条条34仅仅仅和＝2素素素图系系……是是t＝,[不xxk当当当MIR{相相相,,G..AAA{ii,<是包包4<’jt在上在到到在上是a]加加加都a.,A含含,a的的b时时时是xx>上Mx>关关jj,反关=<,使使使A的的<的的ya系系上b对系,用用用单单b传,转a,,>的称,>逻逻逻真真向向递,其置<,关<关辑辑辑包包边 边b关中a矩,系,系ac加加加含含,,系>阵>ii,}≠≠}...关关.其jj.,, 系系则则中在在GG中中加加(2一一)条条

离散数学练习4高级计数与关系 - 答案

离散数学练习4高级计数与关系 - 答案

离散结构单元测试(高级计数和关系)1、某校有12个教师，已知教数学的有8位，教物理的有6位，教化学的5位；数理5位，数化4位，理、化3位；数理化3位。

问教其他课的有几位？只教一门的有几位？只教两门的有几位？2、 求解递推关系3、求解递推关系：4、数1，2，…，9的全排列中，求偶数在原来位置上，其余都不在原来位置的错排数目5、已知}3,2,1{=A ，)}3,1(),1,3(),2,2(),1,1{(1=R ，)}3,1{(2=R ，)}3,3(),2,2(),1,1{(3=R--,n n n a a a --=12120,.a a ==01326--,n n n a a a -+=12440,.a a ==0114指出1R ，2R 和3R 有哪些性质？解1R 有对称性；2R 有反自反性、反对称性和传递性；3R 有自反性、对称性、反对称性和传递性。

6、Z 是整数集。

下列关系中，哪些是自反的、反自反的、对称的、反对称的或传递的？（1）}10||,|),{(2121211≤-∈=i i Z i i i i R 且解1R 有自反性和对称性。

（2）}8,|),{(2121212≥∈=i i Z i i i i R 且解2R 有对称性。

（3）|}|||,|),{(2121213i i Z i i i i R ≤∈=且解3R 有自反性和传递性。

7、 已知)}3,1(),1,2(),2,1{(1=R ，)}3,2(),1,1{(2=R ，求21R ，21R R 。

解 )}3,2(),2,2(),1,1{(21=R)}1,2(),3,1{(21=R R8、 设}3,2,1,0{=A ，A 上两个二元关系分别为：}2/1|),{(1i j i j j i R =+==或}2|),{(2+==j i j i R试求（1）21R R （2）12R R （3）121)(R R R解)}3,2(),1,2(),2,1(),1,0(),0,0{(1=R)}1,3(),0,2{(2=R)}1,2(),0,1{(21=R R)}2,3(),1,2(),0,2{(12=R R)}2,2(),1,1(),0,1{()(121=R R R9、 设},,{c b a S =, 二元关系R 如下，试求它们的传递闭包)(R t 。

离散数学第四版课后答案(第4章)

离散数学第四版课后答案(第4章)

第4章 习题解答4．1 A ：⑤； B ：③； C ：①； D ：⑧； E ：⑩4．2 A ：②； B ：③； C ：⑤； D ：⑩； E ：⑦4．3 A ：②； B ：⑦； C ：⑤； D ：⑧； E ：④分析 题4.1-4.3 都涉及到关系的表示。

先根据题意将关系表示成集合表达式，然后再进行相应的计算或解答，例如，题4.1中的}2,2,1,2,2,1,1,1{},2,2,1,1{><><><><=><><=s s E I};2,2,2,1,1,1{><><><=s I而题4.2中的}.1,4,4,3,1,2,4,1,1,1{><><><><><=R为得到题4.3中的R 须求解方程123=+y x ，最终得到}.1,9,2,6,3,3{><><><=R求R R 有三种方法，即集合表达式、关系矩阵和关系图的主法。

下面由题4.2的关系分别加以说明。

1°集合表达式法将ranR ran domR domR,, 的元素列出来，如图4.3所示。

然后检查R 的每个有序对，若R y x >∈<,，则从domR 中的x 到ranR 中的y 画一个箭头。

若danR 中的x 经过2步有向路径到达ranR 中的y ，则R R y x >∈<,。

由图4.3可知}.1,3,4,2,1,2,4,4,1,44,1,1,1{><><><><>><<><=R R如果求G F ，则将对应于G 中的有序对的箭头画在左边，而将对应于F 中的有序对的箭头画在右边。

对应的三个集合分别为ranF domF ran domG ,, ，然后，同样地寻找domG 到ranF 的2步长的有向路径即可。

离散数学第四章(第1讲)

离散数学第四章(第1讲)
xy??a??bc?xy??xyx??a??y??bc?xy??xyx??a??y??b??y??c?xy??xyx??a??y??b??x??a??y??c?xy??a??ba??c即a??bca??ba??c例
第四章 二元关系
§1 序偶与笛卡尔积 §2 关系及其表示 §3 关系的性质 §4 关系的运算 §5 等价关系与划分 §6 相容关系与覆盖 §7 偏序关系
§1 序偶与笛卡尔乘积
1 序偶 《定义》由二个具有给定次序的客体所组成的序列
称为序偶。记作〈x，y〉 例：X—Y二维平面上的一个点的坐标〈x，y〉就
是一个序偶。
说明： (1)在序偶中二个元素要有确定的排列次序。 若ab时，则〈a，b〉〈b，a〉 若〈x，y〉=〈a，b〉（x=a y=b） (2) 多重序元： 三元组：〈〈x，y〉，z〉 =〈x，y，z〉 n元组： 〈〈〈〈x1，x2〉，x3〉…〉，xn〉= 〈x1,…,xn〉
ran R={a,b,c,d}
FLD R={1,2,3,4,a,b,c,d}
４．关系和笛卡尔乘积 笛卡尔乘积的任何子集都可以定义一种二元关系。 例：X={1,2,3,4}，Y={1,2}
X Y {1,1 ,1,2 , 2,1 , 2,2 , 3,1 , 3,2 , 4,1 , 4,2 }
S1={<x,y>|x X yYx ≤ y}={<1,1><1,2><2,2>}
2 笛卡尔乘积 《定义》设A，B为二个任意集合，若序偶的第 一个成员（左元素）是A的一个元素，序偶的 第二个成员（右元素）是B的一个元素，则所 有这样的序偶构成的集合称为A和B的笛卡尔乘 积。
记作：A B={〈x，y〉|（xA）（yB）}

离散数学第4章 关系

离散数学第4章 关系

例4-1.2 集合A={a，b}，B={c，d}，试写出从 A到B的所有不同关系。 解：A×B={<a，c>，<a，d>，<b，c>，<b， d>}。于是A×B上的所有16个不同的关系： 关系中包含0个元素：； 关系中包含1个元素：{<a，c>}，{<a，d>}， {<b，c>}，{<b，d>}； 关系中包含2个元素：{<a，c>，<a，d>}， {<a，c>，<b，c>}，{<a，c>，<b，d>}， {<a，d>，<b，c>}，{<a，d>，<b，d>}， {<b，c>，<b，d>}；
（5）R是传递的
(x)(y)(z)(x，y，zAxRyyRz→xRz) R的关系矩阵(rij)n×n中对任意的i,j,k有, 若 rik＝1且rkj＝1则rij＝1 （当X是有限集 合）。 R的关系图中任意一条长度为2的路径都有从 其起始顶点到终止顶点的边（当X是有限集合）。
(3)关系矩阵:X＝﹛x1,x2,…,xn﹜到
Y=﹛y1,y2,…,ym﹜的关系R的关系矩阵为 MR＝(aij)n×m 1, 若xiRyj 其中 aij ＝ 0, 若xiRyj
(4)关系图:
X＝﹛x1,x2,…,xn﹜到Y ＝ ﹛y1,y2,…,ym﹜的关 系R的关系图为：分别在左右两列用小圆圈列出的X中的n个元 素和Y中的m个元素，若xiRyj，则从xi到yj画一条有向边。如右 图所示 X＝﹛x1,x2,…,xn﹜上的关系图为：在平面上用小 圆圈列出的X中的n个元素（位置不限），若xiRXj,则从xi到xj 画一条有向边。如左图所示 X Yy 1 x 1 x3 x2 x2 y2 x1 xn xn

离散数学课件第四章 关系

离散数学课件第四章 关系
Discrete Mathematics
关系的性质
例 2 (1) A上的全域关系EA,恒等关系IA及空关系都是A 上的对称关系;IA和 同时也是A上的反对称关系. (2)设A={1,2,3},则 R1={<1,1>,<2,2>}既是A上的对称关系,也是A上 的反对称关系; R2= {<1,1>,<1,2>,<2,1>}是对称的,但不是反对 称的; R3 ={<1,2>,<1,3>}是反对称的,但不是对称的; R4= {<1,2>,<2,1>,<1,3>}既不是对称的也不是 反对称的.
❖ 二、关系的表达方式 1. 集合表达式：列出关系中的所有有序对。 例 1 设A={1,2,3,4},试列出下列关系R的元素。 (1) R={<x,y> | x是y的倍数} (2) R={<x,y> | (x-y)2 A } (3) R={<x,y> | x/y是素数}
Discrete Mathematics
关系
第四章 二元关系
第一节 有序对与笛卡尔积
❖ 定义 1 由两个元素x和y（允许x＝y）按顺序排列成 的二元组叫做一个有序对，记为<x, y>。
❖ 有序对的性质： 1.当 x ≠ y时，<x, y> ≠ <y, x>。 2.<x, y>＝<u, v>的充分必要条件是 x=u且y=v。
Discrete Mathematics
笛卡尔积
❖ 定义 2 设A, B是集合。由A中元素作为第一元素，B 中元素作为第二元素组成的所有有序对的集合，称 为集合A与B的笛卡尔积（或直积），记为A×B。 即 A×B={<x,y>|x A y B}

离散数学-关系-4.1-2

离散数学-关系-4.1-2

E=ranR∪domS={1, 2, 3, 4}
① 把R看作A到E的关系，即相当于关系矩阵上在多出来 的列上加 0
② 把S 看作E到 D的关系，即相当于关系矩阵上加几行 0
③ 矩阵相乘
21
4.2.1 关系的基本运算
求关系的合成（续）
R: A→E, S: E→D A={1, 2}; E={1, 2, 3, 4}; D=ranS={1, 2, 3}; ������ ������ ������ ������ MR = ������ ������ ������ ������ ������ MS= ������ ������ ������ ������ ������ ������ ������ ������ ������ ������ ������ ������ ������ ������ ������
5
4.1.1 有序对与笛卡尔集
笛卡儿积的性质
(1) 若A= 或 B=，则 AB=. 即 A=B= (2) 若|A|=m, |B|=n, 则 |AB|=mn (3) 不适合交换律 AB BA (AB, A, B) (4) 不适合结合律 (AB)C A(BC) (A, B, C) (5) 对于并或交运算满足分配律 A(BC)=(AB)(AC) (BC)A=(BA)(CA) A(BC)=(AB)(AC) (BC)A=(BA)(CA)
������ ������ ������ ������ ������ ������ ������ ������ ������ ������ ������ M R MS = = ������ ������ ������ ������ ������ ������ ������ ������ ������ ������ ������ 故：R∘S ={<1,3>, <2,2>, <2,3>} 求： S∘R？

离散数学4.4-等价和偏序关系

离散数学4.4-等价和偏序关系
11
4.4.3 集合的划分
集合的划分
定义4.21 设A为非空集合, 若A的子集族 ( P(A)) 满 足下面条件： (1) (2) xy (x,y∈∧x≠y→x∩y=) (3) ������∈������ ������=A 则称是A的一个划分, 称 中的元素为A的划分块. 例3 设A＝{a, b, c, d}, 给定 1, 2, 3, 4, 5, 6如下： 1={{a, b, c},{d}}， 2={{a, b},{c},{d}} 3={{a},{a, b, c, d}}， 4={{a, b},{c}} 5={,{a, b},{c, d}}， 6={{a,{a}},{b, c, d}} 则 1和 2 是A的划分, 其他都不是A的划分. 12
4.4.4 偏序关系
相关概念
定义4.23 x与 y可比 设R为非空集合A上的偏序关系, x, yA, x与 y 可比 x≼y ∨ y≼x. 对IA, A上的元素可比吗？ 不可比 定义4.24 非空集合A上的反自反和传递的关系，称为A 上的拟序关系，简称为拟序，记作≺. 求证：如果一个关系是拟序，那么它一定是反对称的。 证：如果不是反对称的，则 ∃x, y, 使 x≺y, 且 y≺x成立。 根据传递性，有 x≺x， 与反自反性矛盾。 19 得证
4.4.1 等价关系
模3等价关系的关系图
设 A={1, 2, …, 8}, R={ <x,y>| x,y∈A∧x≡y (mod 3) } R 的关系图如下：
4
4.4.1 等价关系
注: (1) 关系图的特点: ① 不连通 ② 在每个连通分支中是完全图 (2) 关系矩阵的特点: 修改排列顺序后为对角块矩阵,对角块为全”1”矩阵 1 4 7 2 5 8 3 6 1 1 1 1 0 0 0 0 0 4 1 1 1 0 0 0 0 0 7 1 1 1 0 0 0 0 0 2 0 0 0 1 1 1 0 0 5 0 0 0 1 1 1 0 0 8 0 0 0 1 1 1 0 0 3 0 0 0 0 0 0 1 1 6 0 0 0 0 0 0 1 1

离散数学第四章课件

离散数学第四章课件

无对称的偶对。
表示关系矩阵的主对角线两侧各有一个1且 对称，即有一个对称的偶对。
C1
n(n＋1) 2
n(n＋1) C 2 n(n＋1) 2
表示关系矩阵的主对角线两侧全为1，
C1 ＋ n(n＋ ＋…＋ 2
n(n＋1) C 2 n(n＋1) 2
于是
C0 n(n＋1) 2 ＝
2
n(n＋1) 2
四、反对称性 ⒈ 定义： 若xy(x∈A∧y∈A∧xRy∧yRx→x=y)， 称R是反对称的。 例：设A={ a , b , c , d } R={ < a , b > , < a , c > , < b , b > , <b,d>,<c,c>,<c,d>, < d , d >}
⒉自反关系的关系矩阵的特征
R的关系矩阵的主对角线上的元素均为
1 ，则该关系就不具有自反性；
主对角线上有一个元素不为1，则该关
系就不具有自反性。
⒊ 自反关系的图的特征 自反关系的关系图中，每个顶点都有 自回路，则该关系具有自反性。
二、反自反性 ⒈ 定义：若x（x∈A xRx）则该关系是 反自反的。 ⒉ 具有反自反性的关系的关系矩阵的主对角
2 t1× t2 × … ×tn
五、关系的表示法-----通常有三种表示方法
⒈ 集合表示法： 因为关系也是集合，所以也可以用集合 的表示方法
例：A={ 2, 3,4,6 ,9,12 }上的整除关系
用特征描述法表示为
R＝{ < x , y > | x∈A ∧ y∈A ∧ x|y }
用穷举法表示为
R={ < 2 , 2 > , < 2 , 4 > , < 2 , 6 > ,

离散数学(第二版)第4章二元关系和函数

离散数学(第二版)第4章二元关系和函数

第四章 二元关系和函数
定义4.2.3 设R是A到B的二元关系。 (1) 用xRy表示 <x，y>∈R，意为x，y有R关系(为使可读 性好，我们将分场合使用这两种表达方式中的某一种)。 xy 表示<x，y> R。 (2) 由<x,y>∈R的所有x组成的集合称为关系R的定义域 (domain),记作Dom R，即
显然A×B与 B×A所含元素的个数相同(A，B是有限集 合)，但A×B≠B×A。
定理4.1.1 若A，B是有穷集合，则有 |A×B|=|A|·|B|(·为数乘运算)
该定理由排列组合的知识不难证明。 定理4.1.2 对任意有限集合A1，A2，…，An，有 |A1×A2×…×An|＝|A1|·|A2|·… ·|An|(·为数乘运算)
第四章 二元关系和函数
本节主要介绍关系的基本概念以及关系的表示方法。 定义4.2.1 任何序偶的集合，确定了一个二元关系，并 称该集合为一个二元关系，记作R 。 二元关系也简称关系。 对于二元关系R，如果<x，y>∈R，也可记作xRy。 定义并不要求R中的元素<x，y> 中的x，y取自哪个个体 域。 因此，R={<2，a>，<u，狗>，<钱币，思想>}也是一 个二元关系。
若R={<x，y>|x∈A∧y∈B∧ x|y }，则称R为整除关系， 常记为|，其中x|y表示x整除y。
若A是任意集合，R是A上的二元关系，下面的关系也常 见：
若R={<x，y>|x∈P(A)∧y∈P(A)∧x y}，则称R为包含
若R={<x，y>|x∈P(A)∧y∈P(A)∧x y}，则称R为真包
第四章 二元关系和函数

离散数学第4章关系

离散数学第4章关系
第一个关系中的顺序排列。
关系的复合运算
总结词
复合运算是一种二元运算，它返回两个 关系中满足一定条件的元素组成的新关 系。
VS
详细描述
关系的复合运算是指将两个关系中的元素 按照一定的顺序组合在一起，形成一个新 的关系。这个新的关系只包含满足一定条 件的元素，这些元素按照它们在各自关系 中的顺序排列。
关系的表示
总结词
关系的表示方法有多种，包括表格、图形和符号等。
详细描述
关系的表示方法可以根据具体情况选择。表格表示法是一种常用的方法，通过二维表格的形式列出所 有可能的元素对及其关系状态。图形表示法则更加直观，通过节点和边的形式展示关系。符号表示法 则使用特定的符号或字母来表示关系，如集合论中的笛卡尔积等。
04
关系闭包
闭包的定义
闭包
对于给定的关系R，其闭包记作R+， 是指在R的基础上通过添加某些有序对 后得到的新的关系。
定义方式
如果存在一个集合A，对于A中的任意 元素x和y，如果(x,y)在R+中，那么(x,y) 在R中也一定存在。
闭包的性质
02
01
03
自反性
如果一个关系是自反的，那么其闭包也是自反的。
详细描述
如果集合中的任何一个元素x，都不满足关系 R，使得x与自己有R关系，则称关系R具有反 自反性。例如，在一个班级中，“是自己的 老师”这个关系不具有自反性，因为没有人
是自己的老师。
对称性
总结词
对称性是指如果元素x和元素y之间有关系R，并且元素y 和元素x之间也有关系R，则称关系R是对称的。
详细描述
02
关系的运算
关系的并运算
总结词
并运算是一种二元运算，它将两个关系合并成一个新的关系 。

离散数学第五版第四章(耿素云、屈婉玲、张立昂编著)

离散数学第五版第四章(耿素云、屈婉玲、张立昂编著)

4.1迪卡尔乘积与二元关系
5) 迪卡尔乘积运算对并和交运算满足分配律，即： (3)A×（BC）= (A×B)(A×C） 证明： 对于任意的<x,y> <x,y>A×（BC） xA yBC xA (yB y C) (xAyB) (xAyC) <x,y>A×B <x,y>A×C <x,y>(A×B)(A×C)
A1×A2×……×An ={<x1,x2,……,xn>|x1A1 x2A2 …… xnAn}
4.1迪卡尔乘积与二元关系
例2：设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>}
4.1迪卡尔乘积与二元关系
（2）(AB)×(CD)=(A×C)(B×D) 证明：设A=、B={1}、C={2}、D={3} (AB)×(CD)={<1,2>、<1,3>} (A×C)(B×D)={<2,1>、<2,3>} 所以：等式不成立
（3）(A-B)×(C-D)=(A×C)-(B×D) 证明：设A={1}、B={1}、C={2}、D={3} (A-B)×(C-D)= (A×C)-(B×D)={<1,2>}
4.1迪卡尔乘积与二元关系
三、二元关系 2. 集合上元素的关系（定义4.6）
设A，B为集合，A×B的任何子集所定义的二元关系叫做 从A到B的二元关系，特别当A=B是则叫做A上的二元关系。 例：A={0,1}、B={1,2,3}，

离散数学第四章 关系

离散数学第四章 关系
21
2010-11-3
定理4.3.1 若R⊆A×B，S⊆B×C，T⊆C×D， 则 (R*S)*T=R*(S*T) 这说明复合运算是可结合的。我们常删去括号 将它们写成R*S*T。 由归纳法易证, 任意n个关系的合成也是可结合 的。在R1*R2*…*Rn中, 只要不改变它们的次序, 不论在它们之间怎样加括号, 其结果是一样的.
4
2010-11-3
定义4.1.2 给定集合A和B，若有序对的第一分 量是A的元素，第二分量是B的元素，所有这些 有序对的集合，称为A和B的笛卡尔积，记为 A×B， A×B={‹x,y›|x∈A∧y∈B}
5
2010-11-3
例 设A = {a, b, c}, B = {0, 1}, 则 A × B = {‹a, 0›, ‹a, 1›, ‹b, 0›, ‹b, 1›, ‹c, 0›, ‹c, 1›} B × A = {‹0, a›, ‹0, b›, ‹0, c›, ‹1, a›, ‹1, b›, ‹1, c›} A × A = {‹a, a›, ‹a, b›, ‹a, c›, ‹b, a›, ‹b, b›, ‹b, c›, ‹c, a›, ‹c, b›, ‹c, c›} B × B = {‹0, 0›, ‹0, 1›, ‹1, 0›, ‹1, 1›} 可以看出：A × B ≠ B × A (除非A = ∅或 B = ∅或 A = B,见后面定理) 即笛卡尔积不满足交换律。
18
2010-11-3
例 设A和B分别是学校的所有学生和所有课程的集合。假 设R由所有有序对‹a,b›组成，其中a是选修课程b的学生。 S由所有有序对‹a,b›构成，其中课程b是a的必修课。什么 是关系R∪S，R∩S，R⊕S，R-S和S-R？ 解：关系R∪S由所有的有序对‹a,b›组成，其中a是一个学 生，他或者选修了课程b，或者课程b是他的必修课。 R∩S是所有有序对‹a,b›的集合，其中a是一个学生，他选 修了课程b并且课程b也是a的必修课。 R⊕S由所有有序 对‹a,b›组成，其中学生a已经选修了课程b，但课程b不是 a的必修课，或者课程b是a的必修课，但a没有选修它。 R-S是所有有序对‹a,b›的集合，其中a已经选修了课程b但 课程b不是a的必修课。S-R是所有有序对‹a,b›的集合，其 中课程b是a的必修课，但a没有选它。

离散数学4.1-2

离散数学4.1-2

离散数学
11
函数的概念
续： 证明：1) 证f是入射。任取S1,S2∈P(An)，S1≠S2， 则存在元素aj(1≤j≤n),使得aj∈S1,ajS2或相反 aj∈S2,ajS1。 从而f(S1)＝b1b2b3…bn中必有bj＝1，f(S2)＝c1c2c3…cn必有 cj＝0或相反f(S1)＝b1b2b3…bn 中必有bj＝0，f(S2)＝ c1c2c3…cn必有cj＝1。 所以f(S1)≠f(S2)，即f是单射。
R6＝{<a,1>,<b,2>}
R8＝{<a,2>,<b,2>}
R9＝{<a,1>,<a,2>}
R10＝{<b,1>,<b,2>}
R12＝{<a,1>,<a,2>,<b,2>} R14＝{<a,2>,<b,1>,<b,2>}；
R11＝{<a,1>,<a,2>,<b,1>} R13＝{<a,1>,<b,1>,<b,2>}
离散数学
16
逆函数和复合函数
二、复合函数 设函数f：X→Y，g：W→Z， 若f(X)W，则 h＝gf={<x,z>|xX z Z (y)(yY y=f(x) z=g(y))}, 称g在f的左边可复合。当函数gf作用于X中的 任意一个元素x时，可记为 h(x)＝gf(x)＝g(f(x))。
离散数学
9
函数的概念
2) 设A＝B＝R(实数集合)。
f1(x)＝x2；f2(x)＝x+1；f3(x)＝1/x；
f4(x)＝ex； f5(x)＝ x 。 f(x)＝lnx。

离散数学 关系

离散数学 关系

离散数学关系离散数学中，关系是一个重要的概念。

关系是指一个元素集合之间的对应关系。

这个对应关系可以用图形表示。

让我们来一步步地探讨什么是关系和关系图。

首先，我们要了解什么是元素和元素集合。

元素是一组有意义的数据，它可以是数字、字母、单词等。

元素集合是由多个元素组成的集合，比如所有自然数可以形成一个元素集合。

接着，我们可以定义关系。

关系就是两个元素集合之间的对应关系。

这个对应关系可以用有序对(x,y)表示。

如果(x,y)属于一个关系，那么我们可以说x和y之间存在这个关系。

例如，我们可以定义一个关系R为{(1,2),(2,4),(3,6)}。

这个关系表示1对2，2对4，3对6。

我们可以从这个关系中得到很多信息，比如1对应2，2对应4，3对应6。

这告诉我们一些元素之间的关系。

然而，我们很难从一个关系里面得到全部元素的对应关系，因此我们需要使用关系图来更好地理解关系的意义。

关系图是一种用点和箭头表示关系的图形。

在关系图中，每个点代表一个元素，每个射线代表一个关系。

我们可以通过观察图形来更好地理解两个元素之间的关系。

例如，我们可以用以下图形表示关系R：在这个关系图中，我们可以看到每个点代表了一个元素，每个射线表示了一个关系。

箭头的方向表示了关系的方向。

这个关系图清晰地表达出了每个元素之间的对应关系，让我们更容易地理解这个关系。

除了上述的基本关系之外，离散数学还有很多其他类型的关系，比如等价关系、偏序关系、偏序关系等等。

这些关系的定义和性质都有所不同。

总之，在离散数学中，关系是一个非常重要的概念，它帮助我们理解元素之间的联系和关系，是学习离散数学的基础。

通过理解和掌握关系，我们可以更好地解决许多离散数学中的难题。

离散数学等价关系

离散数学等价关系

离散数学：离散数学（Discrete mathematics）是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。

离散的含义是指不同的连接在一起的元素，主要是研究基于离散量的结构和相互间的关系，其对象一般是有限个或可数个元素。

离散数学在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。

通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。

等价类：在离散数学中，等价关系是指定义在集合A上的关系，满足自反的、对称的和传递的等性质。

设R是定义在集合A上的等价关系，与A中一个元素a有关系的所有元素的集合叫做a的等价类。

等价类应用十分广泛，如在编程语言中，我们使用等价类来判定标识符是不是表示同一个事物。

定义：在离散数学中，等价关系是指定义在集合A上的关系，满足自反的、对称的和传递的等性质。

设R是定义在集合A上的等价关系，与A中一个元素a有关系的所有元素的集合叫做a的等价类。

A的关于R的等价类记作。

当只考虑一个关系时，我们省去下表R并把这个等价类写作[a]。

在软件工程中，是把所有可能输入的数据，即程序的输入域划分成若干部分（子集），然后从每一个子集中选取少数具有代表性的数据作为测试用例，从而减少了数据输入量从而提高了效率，称之为等价类方法，该方法是一种重要的、常用的黑盒测试用例设计方法。

分类：在离散数学中，等价类的划分基于以下定理：设R是定义在集合A上的等价关系。

那么R的等价类构成S的划分。

反过来，给定集合S的划分{ |i∈I},则存在一个等价关系R，它以集合作为它的等价类。

因为等价关系的a 在a 中和任何两个等价类要么相等要么不交集不相交的性质。

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

2020/2/29
《集合论与图论》第8讲
20
Bell数(Bell number)
问题: 给n个对象分类, 共有多少种分法?
答案: Bell数 B =
n n n n
n
n
k 1
k


1

2


n.
(Eric Temple Bell, 1883~1960)
second
n
kind):
S(n,k)=
n
k

n
xn S(n, k)x(x 1)(x 2) (x k 1) S(n, k)xk .
k 0
k 0
2020/2/29
《集合论与图论》第8讲
23
Bell数表
n
Bn
1
1
2
2
3
5
4
15
5
52
6
203
7
877
n
Bn
8
《集合论与图论》第8讲
16
划分(举例)
设 A1,A2,…,AnE, 则以下都是划分: Ai = {Ai,~Ai}, ( i=1,2,…,n ) Aij = {AiAj,~AiAj, Ai~Aj, ~Ai~Aj}-{} ( i,j =1,2,…,n ij ) …… A12…n = {~A1~A2… ~An,…, ~A1~A2… ~An-1An,… A1A2… An}-{}. #

Stirling子集数(Stirling
subset
number)
: n
k

把n个对象分成k个非空子集的分法个数.
递推公式:
n 0

0,
n 1

1,
n 2

2 n1
1,
n
n 1

C
2 n
,
n n

1.

n
k
2020/2/29
《集合论与图论》第8讲
15
划分(partition)
划分: 设A, AP(A),若A满足 (1) A ; (2) x,y( x,yA xy xy= 为划分 块(block).
2020/2/29
4,140
9
21,147
10
115,975
11
678,570
12
4,213,597
13
27,644,437
14
190,899,322
2020/2/29
《集合论与图论》第8讲
24
第二类Stirling数表
n\k 0 1 2 3
4
5
6
7
89
01
1 01
2 01 1
3 01 3 1
4 01 7 6
1
5 0 1 15 25 10
的等价类, 画出R3的关系图. 解: [1]=[4]={1,4}, [2]=[5]=[8]={2,5,8},
[3]={3}. #
4
8
1
2020/2/29
2
5
3
《集合论与图论》第8讲
13
商集(quotient set)
商集: 设R是A上等价关系, A/R = { [x]R | xA }
划分的加细(refinement)
划分的加细: 设A和B都是集合A的划分, 若A的每个划分块都包含于B的某个划分 块中, 则称A为B的加细.
A为B的加细 RARB
2020/2/29
《集合论与图论》第8讲
27
例14
例14: 考虑A={a,b,c}上的划分之间的加细.
解:
a
加细
xy
2020/2/29
《集合论与图论》第8讲
11
同余(congruence)关系
同余关系: 设n{2,3,4,…}, x,yZ,则
x与y模n同余(be congruent modulo n)
xy(mod n) n|(x-y) x-y=kn (kZ)
同余关系是等价关系
[0] ={
《集合论与图论》第8讲
22
第一、二类Stirling数
第一类Stirling数(Stirling number of the
first kind): s(n,k)
n
s(n, k)xk x(x 1)(x 2) (x k 1) xk .
k 0
第二类Stirling数(Stirling number of the
偏序关系: 设 RAA 且 A, 若R是自 反的, 反对称的, 传递的, 则称R为偏序关 系
通常用≼表示偏序关系,读作“小于等于” <x,y>R xRy x≼y
“严格小于”: x≺y x≼y xy 偏序集(poset): <A,≼>, ≼是A上偏序关系 例子: <A,>, <A,|>, <A,>, <,≼加细>
b c 加细
a 加细 bc
a 加细 bc
a bc
加细
a
加细
bc #
2020/2/29
《集合论与图论》第8讲
28
序关系
偏序,线序,拟序,良序 哈斯图 特殊元素: 最?元, 极?元, ?界, ?确界 (反)链
2020/2/29
《集合论与图论》第8讲
29
偏序(partial order)关系
都是A上等价关系, 求对应的商集, 其中 ai,ajA, ij. 是A上等价关系吗?
解: A/IA={ {a1}, {a2},…, {an } }
A/EA={ {a1,a2,…,an } } A/Rij= A/IA{{ai,aj}} - {{ai},{aj}}. 不是A上等价关系(非自反). #
kn|kZ},
11 0 1
10
2
[1] ={ 1+kn|kZ}, 9
3
[2] ={ 2+kn|kZ},…, 8
4
[n-1]={(n-1)+kn|kZ}.
765
2020/2/29
《集合论与图论》第8讲
12
例11
例11: 设 A={1,2,3,4,5,8}, 求 R3 = { <x,y> | x,yA xy(mod 3) }
称[x]R为x关于R的等价类, 简称x的等价类, 简记为[x].
等价类性质: [x]R ; xRy [x]R=[y]R ;
xRy [x]R[y]R= ; U{ [x]R | xA } =A.
2020/2/29
《集合论与图论》第8讲
7
定理27
定理27:设R是A上等价关系,x,yA, (1) [x]R (2) xRy [x]R=[y]R ; (3) xRy [x]R[y]R= ; (4) U{ [x]R | xA } =A. 证明: (1) R自反xRxx[x]R[x]R.
2020/2/29
《集合论与图论》第8讲
3
例9(续)
定义 自反 对称 传递 等价关系
R1 x与y同年生

R2 x与y同姓


R3 x的年龄不比

y小
R4 x与y选修同

门课程
R5 x的体重比y

重
2020/2/29
《集合论与图论》第8讲
4
例10


k
n

1
k


n k

11.
2020/2/29
《集合论与图论》第8讲
21
Stirling子集数
递推公式: n n 1 n 1

k


k
k


k
1.
剔除一个
其余分k类
加入一类
其余分k-1类
2020/2/29
自成一类
称为A关于R的商集, 简称A的商集. 显然 U A/R = A. 例11(续): A/R3 ={ {1,4}, {2,5,8}, {3} }.
2020/2/29
《集合论与图论》第8讲
14
例12(1)
例12(1): 设A={a1,a2,…,an}, IA, EA, Rij=IA{<ai,aj>,<aj,ai>}
2020/2/29
《集合论与图论》第8讲
17
划分(举例,续)
~Ai Ai
2020/2/29
《集合论与图论》第8讲
18
等价关系与划分是一一对应的
定理28: 设A, 则 (1) R是A上等价关系 A/R是A的划分 (2) A是A的划分 RA是A上等价关系,其中
xRAy z(zA xz yz) RA称为由划分A 所定义的等价关系(同块关系). #
例10: 设 RAA 且 A, 对R依次求三 种闭包共有6种不同顺序, 其中哪些顺序 一定导致等价关系? rst( R ), rts( R ), str( R ), srt( R ), trs( R ), tsr( R )=t(s(r( R )))
解: st( R )ts( R ), sr( R )=rs( R ),… tsr( R )=trs( R )=rts( R ) str( R )=srt( R )=rst( R )
x
2020/2/29
《集合论与图论》第8讲
8
定理27(证明(2))
(2) xRy [x]R=[y]R ; 证明: (2) 只需证明[x]R[y]R和[x]R[y]R. () z, z[x]RxRy zRxxRy