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

第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=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) BA=(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). (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的,集合称为关系的定义域，记作,则使得,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上的普遍关系与恒等式关系,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列的元素,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。,值域,关系矩阵为：,一、关系的一般运算：交、并、补、差,试求：,例1 设A=4,6,9,10,和,是A上的两个关系：,=(a,b)|(a-b)/2是正整数，,=(a,b)|(a-b)/3是正整数,二、关系的逆关系（关系的逆运算）,=(b,a)|(a,b),注：逆关系,的关系矩阵,定义,设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|=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)+(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,经由长为 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,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) 自反的, 对称 的, 可传递的。,(1) 反对称的，传递的;,例2 指出下列五种二元关系的性质。 (1) 实数集合上的“小于等于”关系。 自反的, 反对称的,可 传递的。 (2) 集合上的“包含”关系。 自反的, 反对称的,可传递的。 (3) 正整数集合上的“整除|”关系。 自反的, 反对称的, 可传递的。 (4) 平面上直线集合上的“垂直”关系。 反自反的,对称的。 (5) 平面上直线集合上“平行/”关系 。 自反的,对称的,可传递的。,4.关系的性质在关系矩阵和关系图中的特点,二、二元关系的闭包 设 是集合A上的关系, 我们希望 具有某些有用的性质, 比如说自反性。如果不具有自反性, 我们通过在其中添加一部分序偶来改造, 得到新的关系 , 使得其具有自反性。但又不希望它与 相差太多, 换句话说, 添加的序偶要尽可能的少。满足这些要求的就称为 的自反闭包。除自反闭包外还有对称闭包和传递闭包等。,1.定义 设 是集合A上的关系, 的自反闭包 (对称闭包或传递闭包)是A上关系 它满足下列条件: (1) 是自反的(对称的或可传递的); (2) ; (3) 对A上任何包含 的自反(对称或 可传递)关系 , 有 。 注: 将自反闭包记为 , 对称闭包记为 将传递闭包记为 。,定理 设 是集合A上的关系：则 (1) ; (2) ; (3) 。 推论: 设 是有限集合A上的关系, 若#(A)=n, 则 。,2. 求闭包的方法,注：由,的关系图构造,的关系图的方法：,对于,的图中的每个结点,ai,找出从,ai,经有限长的路能够到达（有路）的结点，,这些结点在,的图中，边必须由,ai,指向它们。,3.定理 设 是集合A上的关系, 则： (1) 是自反的当且仅当 ; (2) 是对称的当且仅当 ; (3) 是传递的当且仅当 ;,4.定理 设 是集合A上的关系: (1)若 是自反的, 则 也是自反的。 (2)若 是对称的, 则 也是对称的。 (3)若 是传递的, 则 也是传递的。 5.定理 设 是A上的关系, 且 , 则有 , , 。,由等价关系的对称性也称b等价于a。,一、 等价关系的定义,2.6 等价关系,定义,设,是集合A上的一个关系,若它是自反的, 对称的且可传递的,则称,为A上的一个等价关系。,设,是集合A上的一个等价关系,若a,b成立,注：,则说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上的一个等价关系？ 解: 因为有任意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, 因此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),(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),(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上的偏序关系, 对于 任意的a,bA, 如果有ab或者ba 则称a和b