离散数学基础(洪帆)第二章关系.ppt

《离散数学基础(洪帆)第二章关系.ppt》由会员分享，可在线阅读，更多相关《离散数学基础(洪帆)第二章关系.ppt（54页珍藏版）》请在三一办公上搜索。

1、第2章 关系,本章主要内容：有序n元组（序偶）和笛卡儿积、关系的概念；关系的表示方法；关系的复合运算、关系的性质；等价关系、偏序。,2.1 笛卡儿积,1.定义 由n个具有给定次序的个体 a1,a2,an 组成的序列，称为有序n元组，记作(a1,a2,an)。注：有序n元组不是由n个元素组成的集合。因为前者明确了元素的排列次序，而集合没有这个要求。例如:(a,b,c)(b,a,c)(c,a,b)，但 a,b,c=b,a,c=c,a,b。,一、有序n元组,定义 假设(a1,a2,an)和(b1,b2,bn)是两个有序n元组,则(a1,a2,an)=(b1,b2,bn)成立,当且仅当a1=b1,a2

2、=b2,an=bn。3.序偶 当n=2时，有序二元组(a,b)称为序偶。,2.两有序n元组相等,1.定义 设A1,A2,An是任意集合,所有的有序n元组(a1,a2,an)的集合 称为 A1,A2,An的笛卡儿积,用A1A2 An表示，其中a1A1,a2A2,anAn,即：A1A2 An=(a1,a2,an)|aiAi,i=1,2,n,二、笛卡尔积,2.集合A与集合B的笛卡尔积,AB=(a,b)|,aA,bB,则 A1A2 An可表示为,注：若所有Ai都相同，,例1 设A=1,3,B=1,2,4，求：AB，BA 解：AB=(1,1),(1,2),(1,4),(3,1),(3,2),(3,4)B

3、A=(1,1),(1,3),(2,1),(2,3),(4,1),(4,3)显然 AB BA,即笛卡儿积不满足交换律。例2 设A=0,1,B=2,3,C=3,4则：ABC=(0,2,3),(0,2,4),(0,3,3),(0,3,4)(1,2,3),(1,2,4),(1,3,3),(1,3,4)(AB)C=(0,2),3),(0,2),4),(0,3),3),(0,3),4),(1,2),3),(1,2),4),(1,3),3),(1,3),4)A(BC)=(0,(2,3),(0,(2,4),(0,(3,3),(0,(3,4),(1,(2,3),(1,(2,4),(1,(3,3),(1,(3,4

4、).(AB)C A(BC)，因此笛卡儿积不满足结合律。,2.2 关系,1.定义 笛卡儿积A1A2 An的任意一个子集 称为A1,A2,An上的一个n元关系。注:当n=2时,AB的任一子集 称为由A 到B的一个二元关系。,一、关系的定义,注：1)空集是任何集合的子集,称为 空关系。,2)若集合A、B的元素分别是n、m,则A到 B的关系共有,注：若 是A到B的一个关系，如果(a,b),则称a与b有 关系,记作a b,如果(a,b),则称a与b没有 关系，记作a b。,集合称为关系的值域，记作,2.关系的定义域和值域,定义,设,是由A到B的一个关系，,则使得,a,b(bB)成立的所有元素aA的,集合

5、称为关系的定义域，记作,则使得,a,b(aA)成立的所有元素bB的,例1 设集合A=1,2,4,7,8,B=2,3,5,7,定义由A到B的关系:=(a,b)|(a+b)/5是整数 试问 由哪些序偶组成？并求此关系的定义域和值域。,1）定义 由集合A到A自身的关系称为 集合A上的关系。,3.A上的关系,例2 设A=2,3,4,5,9,25,定义A上的关系R,对于任意的a,bA,当且仅当(a-b)2A 时,有a R b,试问 R由哪些序偶构成？并求关系R的定义域和值域。,a)普遍关系 若关系 R=A2,则称R为A上的普遍关系,记作UA,即UA=(ai,ak)|ai,akA。,2）A上的普遍关系与恒

6、等式关系,b)恒等关系 A上的恒等关系用IA表示，定义为:IA=(ai,ai)|aiA,令有向图G=(V,E),其中顶点集V=A,边集E按如下规定:有向边,二、关系的表示方法,1.列举法 2.描述法,3.关系图,定义,设A=a1,a2,an,是A上的关系,的关系图。,则称有向图G为关系,例3 设集合A=1,2,3,4,R=(1,1),(1,2),(1,3),(1,4),(2,3)S=(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)都是 A上的二元关系。画出关系R与S的关系图。,图(1),图(2),R和S的关系图分别如下图(1)和图(2)所示：,且关系矩阵的第i行、第j列的

7、元素,4.关系矩阵,定义,设集合A=a1,a2,an,B=b1,b2,bm,是由A到B的关系,则,的关系矩阵,记为,定义如下：,定义为一个n行、m列的矩阵，,例4 设集合A=20,1,B=20,1,2-20,=(a,b)|a-b=是一个由A到B的关系,试列出关系 的定义域和值域，构造出关系矩阵。,解：定义域,=A,=B。,值域,关系矩阵为：,2.3 关系的复合,一、关系的一般运算：交、并、补、差,试求：,例1 设A=4,6,9,10,和,是A上的两个关系：,=(a,b)|(a-b)/2是正整数，,=(a,b)|(a-b)/3是正整数,二、关系的逆关系（关系的逆运算）,=(b,a)|(a,b),

8、注：逆关系,的关系矩阵,定义,设A和B是两个集合,是A到B的关系,则由B到A的关系:,的逆关系。,称为关系,记为,，,例2 设A=2,3,4,5,9,25,定义A上的关系：,三、关系的复合运算 1.定义 设 是一个有A1和A2的关系,是一个由A2到A3的关系,则 和 的复合关系是一个 由A1到A3的关系,用 表示，定义为当且仅当存在某个 A2,使得,时,有。这种从 和 得到的运算,称为关系的复合运算。,例2 设有集合A=4,5,8,15,B=3,4,5,9,11,C=1,6,8,13,是A到B的关系,是B到 C的关系,且分别定义为：=(a,b)|b-a|=1=(b,c)|b-c|=2或|b-c

9、|=4 试求复合关系。,定理2 设 是由A1到A2的关系,是由A2到A3的 关系,是由A3到A4的关系,则有：注：1)复合关系的运算具有结合律。2)当 A1=A2=An=An+1=A，时，复合关系 可以用 表示。,定理1 设 是有集合A到B的关系，则有：,2.关系复合的性质,例3 设A=a,b,c,d，A上的关系:=(a,a),(a,b),(b,d),(c,a),(d,c)试求复合关系。,2.4 复合关系的关系矩阵和关系图,一、布尔运算 布尔运算只涉及数字0和1,数字的加法和乘法按照以下方式进行：0+0=0 0+1=1+0=1+1=1 11=1 10=01=00=0 如：(11)+(011)+

10、(100)+1+0=1,则M1与M2乘积记为M1M2是一个ln的矩阵，,二、两关系矩阵的乘积,注：这里的加法和乘法都是布尔型的,定义,设M1是一个(i,j)通路(即第i行、第j列的元素)为,的lm关系矩阵，,M2是一个(i,j)通路为,的mn关系矩阵，,其(i,j)通路为：,的关系矩阵为：,三、复合关系的关系矩阵,定理1,设集合A,B,C都是有限集,是由A到B的关系,是由B到C的关系,他们的关系矩阵分别为,则复合关系,的关系矩阵为：,定理2,设有限集A上的关系,的关系矩阵是,则复合关系,四、求复合关系的关系图的方法,由,的关系图构造,的关系图的方法：,对于,的图中的每个结点,ai,确定从,ai

11、,经由长为 n 的路能够到达的结点，,这些结点在,的图中，边必须由,ai,指向它们。,2.5 关系的性质与闭包运算,一、关系的性质,是反对称的。,1.定义,设,是集合A上的关系:,(1)若对于所有的,都有,则称,是自反的。,(2)若对于所有的,都有,则称,是反自反的。,(3)若对于所有的,若每当有,就必有,则称,是对称的。,是可传递的。,(4)若对于所有的,若每当有,就必有,则称,(5)若对于所有的,若每当有,就必有,则称,a)一个关系可以既不是自反关系 又不是反自反关系.例如A=1,2,3上关系:(1,1),(1,2),(2,3)。b)一个关系既可以是对称的 又可以是反对称的.例如A=1,2

12、,3上的关系:(1,1),(2,2),(3,3)。,2.说明,3.定理 设 是集合A上的关系,则(1)是自反的当且仅当。(2)是对称的当且仅当。(2)是反对称的当且仅当。(5)是传递的当且仅当，即,例1 设A=1,2,3,4，试判定下列A上的关系的性质。(1)=(1,1),(1,2),(2,3),(1,3),(1,4);(2)=(1,1),(1,2),(2,1),(2,2),(3,3),(4,4);(3)=(1,3),(2,1);(4)=,即空关系;(5)=AA,即全域关系;,解:,(2)自反的,对称的,传递的;,(3)反自反的,反对称的;,(4)反自反的,对称的，反对称的,可传递的;,(5)

13、自反的,对称 的,可传递的。,(1)反对称的，传递的;,例2 指出下列五种二元关系的性质。(1)实数集合上的“小于等于”关系。自反的,反对称的,可 传递的。(2)集合上的“包含”关系。自反的,反对称的,可传递的。(3)正整数集合上的“整除|”关系。自反的,反对称的,可传递的。(4)平面上直线集合上的“垂直”关系。反自反的,对称的。(5)平面上直线集合上“平行/”关系。自反的,对称的,可传递的。,4.关系的性质在关系矩阵和关系图中的特点,二、二元关系的闭包 设 是集合A上的关系,我们希望 具有某些有用的性质,比如说自反性。如果不具有自反性,我们通过在其中添加一部分序偶来改造,得到新的关系,使得其

14、具有自反性。但又不希望它与 相差太多,换句话说,添加的序偶要尽可能的少。满足这些要求的就称为 的自反闭包。除自反闭包外还有对称闭包和传递闭包等。,1.定义 设 是集合A上的关系,的自反闭包(对称闭包或传递闭包)是A上关系 它满足下列条件:(1)是自反的(对称的或可传递的);(2);(3)对A上任何包含 的自反(对称或 可传递)关系,有。注:将自反闭包记为,对称闭包记为 将传递闭包记为。,定理 设 是集合A上的关系：则(1);(2);(3)。推论:设 是有限集合A上的关系,若#(A)=n,则。,2.求闭包的方法,注：由,的关系图构造,的关系图的方法：,对于,的图中的每个结点,ai,找出从,ai,

15、经有限长的路能够到达（有路）的结点，,这些结点在,的图中，边必须由,ai,指向它们。,3.定理 设 是集合A上的关系,则：(1)是自反的当且仅当;(2)是对称的当且仅当;(3)是传递的当且仅当;,4.定理 设 是集合A上的关系:(1)若 是自反的,则 也是自反的。(2)若 是对称的,则 也是对称的。(3)若 是传递的,则 也是传递的。5.定理 设 是A上的关系,且,则有,。,由等价关系的对称性也称b等价于a。,一、等价关系的定义,2.6 等价关系,定义,设,是集合A上的一个关系,若它是自反的,对称的且可传递的,则称,为A上的一个等价关系。,设,是集合A上的一个等价关系,若a,b成立,注：,则说

16、a等价于b,例1 在中国人组成的集合上定义的“同姓”关系,它具备自反、对称、传递的性质,因此是一个等价关系。例2 平面上直线集合上的“平行”关系是等价关系,而其上的“垂直”关系不是等价关系,因为它既不是自反的，也不是传递的。例3 平面上三角形的“全等、相似”关系是等价关系。例4“朋友”关系不是等价关系，因为它不是传递的。例5 集合的“包含”关系不是等价关系，因为它不是对称的。,例6 设A=1,2,8,如下定义A上的关系 R:R=(a,b)|a,bA,ab(mod3).其中ab(mod3)叫做a与b模3相等,即a与b除以3的余数相等(即3整除|a-b|).判定R是否为A上的一个等价关系？解:因为

17、有任意aA,aa(mod3)对任意a,bA,若ab(mod3),则ab(mod3)对任意a,b,cA,若ab(mod3),bc(mod3)则有ac(mod3),所以R是A上的等价关系。该关系的关系图如下图所示：,从图中可以看出,关系图被分成三个互不连通的部分。每一个部分中的数两两都等价(有关系),不同部分中的数则不等价(没有关系)。通过等价关系给出的每一部分叫此等价关系的等价类。,=b|bA,a,二、等价关系的等价类,1.定义,设,是集合A上的一个等价关系,则由A中等价于a的全体元素所组成的集合,称为由元素a所生成的等价类。,用,表示,即：,b,2.等价类的性质(1)对于任意aA,有a a,因

18、此a,即A中每一个元素所生成的等价类非空。(2)若a b,则,即彼此等价的元素属于同一个等价类。(3)若a b,则,即彼此不等价的元素属于不同的等价类,且这些等价类没有公共元素。,注：集合A上的任意一个等价关系定义A的一个分划,每一个等价类就是一个分划块。,3.等价分划,定理,设,是集合A上的等价关系,则等价类,的集合,|aA,构成集合A的一个分划。,由等价关系,的等价类所,导出的等价分划，,组成的A的分划,称为A上由,记为,例8 设A=0,1,2,3,4,5上的关系=(0,0),(1,1),(2,2),(3,3),(1,2),(1,3),(2,1)(2,3),(3,1),(3,2),(4,4

19、),(4,5),(5,4),(5,5)求它在A上所导出的等价分划。,解：显然此关系 是自反的,对称的和可传递的,因此是一等价关系,它在A上所导出的等价分划为:,=0,1,4=0,1,2,3,4,5,导出等价分划。,注：由定理知分划的概念和 等价的概念在本质上是相同的。,4.定理,设,是集合A上的一个分划,则存在A上的等价关系,使得,是A上由,例9 求出A=a,b,c上所有的等价关系。解：先给出A上的所以划分:,=a,b,c,=a,b,c,=a,c,b,=a,b,c,=a,b,c。,再给出每个划分所对应的等价关系为：,=(a,a),(b,b),(c,c)，,=(a,a),(b,b),(c,c),

20、(b,c),(c,b)，,=(a,a),(c,c),(a,c),(c,a),(b,b)，,=(a,a),(b,b),(a,b),(b,a),(c,c)，,=(a,a),(b,b),(c,c),(a,b),(a,c),(b,a),(b,c)(c,b),(c,a)。,的秩。,三、等价关系的商集,1.定义,设,是集合A上的等价关系,则等价类的集合,|aA,称为A关于,的商集,用,表示。,的基数称为,商集,2.7 偏序,1.定义 集合A上的一个关系,如果它是 自反的,反对称的和可传递的,则称此关系是A上的一个偏序关系,或简称为偏序,用符号 去表示。,一、偏序的定义,2.说明 设是集合A上的偏序关系,对

21、于 任意的a,bA,如果有ab或者ba 则称a和b是可比的,否则称a和b不可比的。,2.定义 一个集合A上的偏序,若对于A上的 每一个非空子集S,在S中存在 一个元素as(称为S的最小元素),使得对于所有的sS,有ass,则称它为A上的一个良序。,1.定义 一个集合A上的偏序,如果对 所有的a,bA,有a b或b a,则称它为A上的一个全序。,二、全序和良序,例1 定义在实数集R上的小于或等于关系,显然是R上的偏序关系,它也是R上的一个全序，但是它不是R上的良序。如(0,1)是R的一个子集,但是(0,1)中无最小元素。例2 定义在正整数集N上的小于或等于关系 是N上的偏序关系,也是全序和良序。

22、例3 定义在正整数集N上的“整除|”关系 是一个偏序关系,但不是全序也不是良序。因为显然对于 3,5N,既没有3|5,也没有5|3,所以不是全序。而对于N的子集3,5没有最小元,则不是良序。,3.结论：(1)一个集合A上的全序或良序一定是偏序,但是偏序却不一定是全序和良序。(2)一个偏序若是良序,则一定也是全序(3)全序不一定是良序,设A上定义的偏序关系,1.用结点表示A中的每一个元素。省略自回环。2.若ab,则结点a出现在结点b的下面。省略方向，规定方向自下朝上。3.若ac，cb，则省略a到b的连线。,三、偏序的关系图次序图（Hasse图),例5(1)集合X=2,3,6,12,24,36上的整除关系 是一个偏序,画出其次序图。(2)集合S=a,b,c的幂集上的包含关系 是一个偏序,画出其次序图。,解：(1)的次序图见图(a),(2)的次序图见图(b)。,