《离散数学3-5》由会员分享，可在线阅读，更多相关《离散数学3-5（18页珍藏版）》请在金锄头文库上搜索。
1、1,第三章 集合论,集合的概念和表示法,1,集合的运算,2,序偶与笛卡尔积,4,关系及其表示,5,关系的性质,6,复合关系和逆关系,7,2,3.5 关系及其表示,一、二元关系 二、n元关系 三、几个特殊的二元关系 四、二元关系的表示,3,一、二元关系,引例：考虑集合A=2,3,5,9上的“小于”关系。,1. 二元关系的定义1：任意一个序偶集合称为一个二元关系，简称关系,记作R。如果R,可记作aRb,称a与b有关系R；如果R,记作aRb,称a与b没有关系R。这种记法称为中缀记法。例：R=,则中缀记法为：aR1，bR1，bR2。,/,4,例1：R=x,yN且xy 这是自然数集合上的一个“大于”关系
2、， 显然R,即3R2。 如果我们把R读作“大于”，则3R2读作“3大于2”。 说明： 1）我们把关系R这种无形的联系同集合这种“有形”的实体来描述，在今后的描述和论证带来方便； 2）有序对是讲究次序的，如R未必有R,即a与b有关系R，未必b与a有关系R。 例：甲与乙有父与子的关系，则乙与甲肯定没有父与子的关系了。,一、二元关系,5,2.二元关系定义2：AB的任何一个子集，称为A到B的一个二元关系，当A=B时，我们称之为A上的二元关系。 例2：设A=a,b,c,d,e,f为学生集合，B=,为课程集合，有如下三个二元关系： R1=,可以是一个从A到B的选课关系； R2=,为一个A上的二元关系，可以
3、表示上下铺关系； R3=,为一个B上的二元关系，可以表示先行课关系 。,一、二元关系,6,3.前域和值域 定义：关系R中所有序偶的： 第一元素的集合称为关系R的前域，记作Dom(R)； 第二元素的集合称为关系R的值域，记作Ran(R)。 如果R是A到B的关系，则D(R)A，R(R)B R的前域和值域一起称作R的域，记作FLDR。 例3：A=a,b,c B=1,2,3 R1=,是A到B的一个关系 R2=,是B上的一个关系 写出这两个关系的前域和值域：D(R1)=a,bA, R(R1)=1,2,3BD(R2)=1,2B, R(R2)=1,3B,一、二元关系,7,二、n元关系,定义：设Ai是任意集合
4、，则A1A2An的任何一个子集，称为A1A2An上的一个n元关系。当A1=A2=An时，我们称之为A上的n元关系。当n=2时，即为二元关系。 说明：今后若没有特别说明，“关系”一词都是指二元关系。并且通常只限于讨论同一集合上的二元关系，即R AA这种关系。,8,1. 是AB的子集，由定义的A上的关系，称为A上的空关系； 2. AB本身也AB的子集，R= AB时，称为全关系，记作E，即E=aA,bB； 3. A=aA称为A上的恒等关系。 例如：设集合A=0,1,2EA=, ,，是A上的全关系；A=,是A上的恒等关系；EA=AA=9，A=A=3。,三、几个特殊的二元关系,9,4. 小于等于关系 L
5、：A=1,2,3，定义A上的关系LA=a,bA,ab，则LA=,5. 整除关系 D：设B=1,2,3,4,5,6定义B上二元关系，DB= a,bB,baI，则DB=, ,注：baI说成“a能整除b”,或 “b能被a整除”。,三、几个特殊的二元关系,10,6. 同余关系 R：A=1,2,3,4，A上的二元关系：R=( a-b)/2I,a,bA,则R=, 说明：此关系称为“模2同余关系”记作ab(mod 2)，类似有“模3同余”模4同余等”。7. 包含关系 R：A是一个集合,定义P(A)上的一个关系,R=uP(A),vP(A),且uv例如：A=a,b,P(A)= ,a,b,AR=,三、几个特殊的二
6、元关系,11,设|A|=m,|B|=n,|AB|=mn,而关系是AB的子集,根据幂集个数的理论,AB的子集共有2mn,所以,A到B的关系共有2mn个。,思考：设|A|=m,|B|=n,A到B的不同的关系共有多少？,12,例4：设A=2,3,4,5,6，用列举法分别写出下列关系。 1）R=a是b的倍数 2）R=(a-b)2 A 3）R=a/b是素数 4）R=ab 5）R=a,b互质,解：1) R=, ,2) R=,3) R=,4) R=EA-A,共有25-5个有序对。5) R=, ,13,四、二元关系的表示,1. 关系的矩阵表示法 定义：设集合A=a1, ,am,B=b1bn，R是A到B的关系,
7、则R的关系矩阵是一个mn阶的矩阵MR=(rij)mn (m行n列），其中： rij =1,当 R rij =0,当 R如果R是A上的关系时,则其关系矩阵是一个方阵。 例如A=a,b,c,d，B=x,y,z,R=, ，则MR是43的矩阵。,14,例5：A=2,3,4,5,6，A上关系R1=|a是b的倍数，写出R1的关系矩阵。,解：R1=, 关系矩阵如下：,说明：1) 空关系的关系矩阵M的所有元素为0；2) 全关系EA的关系矩阵ME的所有元素为1；3) 恒等关系A的关系矩阵MI的所有对角元素为1，非对角元素均为零，此矩阵在线性代数中称为单位矩阵，记作。,四、二元关系的表示,15,2. 关系的图形表
8、示法,画法：设A=a1,am,B=b1,bn,(AB) 1) R是A到B的关系，用m+n个空心点分别表示a1,am和b1,bn(一般分列两边)，这些空心点称为结点； 2) 如果R，则由结点ai向结点bj画一条有向弧，箭头指向bj；如果R，则不画相应的弧，这样形成的图称为关系R的关系图。 3) 如果R是A上的关系，则画m个空心点表示a1,am(不画2m个结点,而且不再分列两边)，有向弧的画法同上，如果R，则画一条以ai到自身的一条有向弧，这种弧称为自回路。,四、二元关系的表示,16,例6：A=a,b,c B=1,2,3 R1=,是A到B的一个关系 R2=,是B上的一个关系,关系图直观清晰，是分析关系性质的方便工具，但不便于进行关系运算。,四、二元关系的表示,17,小 结,关系定义 定义1 定义2 几个特殊的二元关系 空关系、全关系和恒等关系 整除关系、同余关系和包含关系 二元关系的表示 矩阵表示 关系图,18,作业,P110 (4) ，(5)d思考：(1)，(2),
