《离散数学基础洪帆关系》由会员分享，可在线阅读，更多相关《离散数学基础洪帆关系（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
2、=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、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,(
4、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的
5、一个关系，,则使得,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上的普遍关系, 记
6、作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),图(
7、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。,值域,关系矩阵为：,2.3 关系的复合,一、关系的一般运算：交、并、补、差,试求：,例1 设A=4,6,9,10,和,是A上的两个关系：,=(a,b)|(a-b)/2是正整数，,=(a
8、,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,
9、是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, 数字的
10、加法和乘法按照以下方式进行：0+0=0 0+1=1+0=1+1=111=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上的关系,的关
11、系矩阵是,则复合关系,四、 求复合关系的关系图的方法,由,的关系图构造,的关系图的方法：,对于,的图中的每个结点,ai,确定从,ai,经由长为 n 的路能够到达的结点，,这些结点在,的图中，边必须由,ai,指向它们。,2.5 关系的性质与闭包运算,一、 关系的性质,是反对称的。,1.定义,设,是集合A上的关系:,(1) 若对于所有的,都有,则称,是自反的。,(2) 若对于所有的,都有,则称,是反自反的。,(3) 若对于所有的,若每当有,就必有,则称,是对称的。,是可传递的。,(4) 若对于所有的,若每当有,就必有,则称,(5) 若对于所有的,若每当有,就必有,则称,a) 一个关系可以既不是自反
12、关系又不是反自反关系. 例如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),(
13、2,1); (4) = , 即空关系;(5) =AA, 即全域关系;,解:,(2) 自反的, 对称的, 传递的;,(3) 反自反的, 反对称的;,(4) 反自反的, 对称的，反对称的,可传递的;,(5) 自反的, 对称 的, 可传递的。,(1) 反对称的，传递的;,例2 指出下列五种二元关系的性质。 (1) 实数集合上的“小于等于”关系。自反的, 反对称的,可 传递的。 (2) 集合上的“包含”关系。自反的, 反对称的,可传递的。 (3) 正整数集合上的“整除|”关系。自反的, 反对称的, 可传递的。(4) 平面上直线集合上的“垂直”关系。反自反的,对称的。(5) 平面上直线集合上“平行/”关
14、系 。自反的,对称的,可传递的。,4.关系的性质在关系矩阵和关系图中的特点,二、二元关系的闭包设 是集合A上的关系, 我们希望 具有某些有用的性质, 比如说自反性。如果不具有自反性, 我们通过在其中添加一部分序偶来改造, 得到新的关系 , 使得其具有自反性。但又不希望它与 相差太多, 换句话说, 添加的序偶要尽可能的少。满足这些要求的就称为 的自反闭包。除自反闭包外还有对称闭包和传递闭包等。,1.定义 设 是集合A上的关系, 的自反闭包(对称闭包或传递闭包)是A上关系它满足下列条件:(1) 是自反的(对称的或可传递的);(2) ;(3) 对A上任何包含 的自反(对称或可传递)关系 , 有 。注: 将自反闭包记为 , 对称闭包记为 将传递闭包记为 。,定理 设 是集合A上的关系：则(1) ;(2) ;(3) 。推论: 设 是有限集合A上的关系, 若#(A)=n,则 。,2. 求闭包的方法,注：由,的关系图构造,的关系图的方法：,对于,的图中的每个结点,
