《离散数学第2章关系》由会员分享，可在线阅读，更多相关《离散数学第2章关系（139页珍藏版）》请在金锄头文库上搜索。
1、1,离散数学,西安交通大学电子与信息工程学院计算机系,2,离散数学,第二章 关系 (relation) 1 . 集合的叉积n元组 2 .关系 3 .关系的表示关系的性质 4 .关系的运算 5. 等价关系 6. 半序关系,3,离散数学,1 . 集合的叉积n元组 定义1. 叉积，笛卡尔积 (cross product , Cartesian product(1637) n个集合A1， A2， ，An的 n 维叉积定义为 =A1 A2 An =(a1, a2, , an): ai Ai(1i n) ；,4,离散数学,n 维叉积A1 A2 An的每个元素(a1, a2, , an)都称为一个n元组（n
2、-tuple）；即，叉积是元组的集合； 每个n元组(a1, a2, , an)的第i个位置上的元素ai称为该n元组的第i个分量（坐标或投影）；元组各分量的顺序不能改变；n 称为该叉积及其元组的维数；两个元组相等它们的维数相同且对应的分量相等。即 (a1, a2, , an)= (b1, b2, , bm) n=m (iN)(1i n)(ai = bi)；注：笛卡尔(1596-1650 )，法国数学家， 1637年发表方法论之一几何学，首次提出坐标及变量概念。这里是其概念的推广。,5,离散数学,定义2. 二个集合A，B的(二维或二重)叉积定义为 AB =(a, b): a A bB ；其元素二元
3、组(a, b)通常称为序偶或偶对(ordered pair) ；二元组(a, b)的第一分量上的元素a称为前者；第二分量上的元素b称为后者；二重叉积的A B第一集合A称为前集；第二集合B称为后集。,6,离散数学,例1 . A= a,b,c , B=0,1 AB=(a,0), (a,1), (b,0), (b,1), (c,0), (c,1) BA=(0,a), (0,b), (0,c), (1,a), (1,b), (1,c) 例2 . A=张三,李四，B=白狗,黄狗 AB=(张三,白狗),(张三,黄狗),(李四,白狗),(李四,黄狗) BA=(白狗,张三),(白狗,李四),(黄狗,张三),(
4、黄狗,李四),7,离散数学,一般地说，关于叉积和元组我们有：(1) (a, b) (b, a)；(2) AB B A ；(3) 二元组不是集合，因为二元组中的分量计较顺序, 而集合中的元素是不讲顺序的。(4) 我们也可用二元组来递归的定义n元组如下：(a,b,c)=(a,b),c) (a1, a2, , an-1 , an)= (a1, a2, , an-1) , an),8,离散数学,(5) 这样，我们也就可用二重叉积来递归的定义n维叉积如下： ABC=(AB)C A1A2 An-1An= (A1A2 An-1)An,9,离散数学,(6) 利用(5)所给的定义，我们可以递归的定义集合的叉积幂
5、如下：A2= AA A3 = A2 A An = An-1 A(7)我们规定空集与任何集合A的叉积是空集 。 即 A = = A由于若偶对的第一分量或第二分量不存在就没有偶对存在，故规定它们的叉积集合为空集是合理的。,10,离散数学,定理1. 设A,B,C,D是四个非空的集合。那么AB = CD A = C B = D 。证. )：（采用逻辑法）对任何的元素a,b (a,b)AB (a,b)CD (条件： A = C B = D ）所以 AB = CD 。,11,离散数学,)：（采用逻辑法）对任何的元素a,b aAbB (a,b)AB (a,b)CD (条件：AB = CD ） aCbD 所以
6、A = C B = D 。,12,离散数学,定理2 . 设A,B,C是三个非空集合。则 (1)左分配律：A(BC) = (AB)(AC) (2)左分配律：A(BC) = (AB)(AC) (3)右分配律：(AB)C = (AC)(BC) (4)右分配律：(AB)C = (AC)(BC),13,离散数学,证. 只证(1)（采用逻辑法）对任何的元素a,b(a,b)A(BC)aAb BC aA(bBbC) (aAbB)(aAbC) (分配律：p(qr)(pq)(pr) (a,b)AB(a,b)AC (a,b)(AB)(AC) 所以 A(BC) = (AB)(AC) 。,14,离散数学,2 .关系一.
7、 关系的基本概念定义1 . 二元关系(binary relation) 设A, B是两个非空的集合。二重叉集AB 的任何一个子集R都称为是从集合A到集合B的一种二元关系。即 RAB ；当 (a,b)R 时，称a与b有关系R ，记为 aRb ；当 (a,b)R 时，称a与b没有关系R ，记为 或 ； 当A=B时，即RAA，则称R是A上的一个二元关系。,15,离散数学,例1 . 设A是西安交通大学全体同学组成的集合。 R=(a,b) : aAbAa与b是同乡AA 于是，R是西安交通大学同学之间的同乡关系。例2 . 设N是自然数集合。 R= (a,b) : aNbNa|b NN 则R就是自然数集合上
8、的整除关系。,16,离散数学,例3 . 设A是某一大家庭。 R1 = (a,b) : aAbAa是b的父亲或母亲AA R2 = (a,b) : aAbAa是b的哥哥或姐姐AA R3 = (a,b) : aAbAa是b的丈夫或妻子AA 于是， R1是父母与儿女之间的关系，即父母子女关系； R2是兄弟姐妹之间的关系，即兄弟姊妹关系； R3是夫妻之间的关系，即夫妻关系。,17,离散数学,例4 . 设是整数集合。 R= (a,b) : aIbI(kI)(a-b =km) II 则R就是整数集合上的(模m)同余关系。例5 . 设A是某一大型FORTRAN程序中诸程序块的集合。 R= (a,b) : aA
9、bAa调用(call)b AA 则R就是程序块集合上的调用关系。例6 . 设A = 风，马，牛， R = (风,马)，(马,牛) AA 则R是A上的一个二元关系。,18,离散数学,关于关系概念，我们还有如下的几个定义和说明： 1全关系(full relation)： 关系R=AB称为全关系； 2空关系(empty relation)： 关系R= 称为空关系；空关系和全关系都是平凡关系；,19,离散数学,3幺关系或单位关系(identical relation)： 关系R= (a, a): aA AA称为A上的幺关系；例7 . 设A=1,2,3,4，则 R1 = (1,1) , (2,2) ,
10、(3,3) , (4,4) 是幺关系； R2 = (1,1) , (2,3) , (3,4) , (4,4) 不是； R3 = (1,1) , (2,2) , (3,3) , (4,4) ,(1,2) 也不是；,20,离散数学,4关系的交，并，补运算： 叉积是一种（新型的）集合；关系是叉积的子集；因此，关系也是一种（新型的）集合； 从而，有关集合论的一切概念、论述、运算也都适合于关系； 尤其是集合的交，并，补，差运算也都适合于关系；因此，关系也有交，并，补，差运算；,21,离散数学,例8 . 设N是自然数集合。 R=小于关系=(m,n) : mNnNmnNN S=整除关系=(m,n) : mN
11、nNm|nN N 则 R =大于等于关系()； RS=小于等于关系() ； RS=不相等的整除关系()；RS=小于又不整除关系( )； SR=相等关系(=) 。,22,离散数学,5关系的扩充(expansion)：若R1 R2 ，则称关系R2 是关系R1的一个扩充； 6 n元关系：n元关系R是n 维叉积的一个子集；即 R A1A2 An,23,定义3. 前域(domain) 后域(codomain) 设A, B是两个非空集合，R AB是一关系。则关系R的 前域： (R) = a : a A(bB)(aRb)A ； 后域： (R) = b : bB(aA)(aRb) B 。,离散数学,24,例9
12、 . 设A=1,2,3,4 ，B=2,4,6,8,10 。 R=(1,2),(2,4),(3,6)。 则 (R) = 1,2,3A ， (R) = 2,4,6B 。,离散数学,25,离散数学,二. 关系的一些关联性质定理1. 设R1,R2 AB是两个关系。若 R1 R2 ，则 (1)保序性： (R1) (R2) ； (2)保序性： (R1) (R2) ；证. 只证(1) （采用逻辑法）对任何元素a A， a (R1 ) aA(bB)(a,b)R1) (前域的定义) aA(bB)(a,b)R2) (条件：R1 R2 ) aA(bB)(a R2 b) a (R2 ) 所以 (R1) (R2) 。,26,定理2 . 设R1, R2是AB上的两个二元关系。则 (1) (R1 R2) = (R1) (R2) (2) (R1 R2) = (R1) (R2) (3) (R1 R2) (R1) (R2) (4) (R1 R2) (R1) (R2),
