离散数学关系

第2章关系考察日常生活和科学技术中的“关系”：人与人之间有：父子关系兄弟关系师生关系两数之间有：大于关系等于关系　小于关系集合之间有：包含关系相等关系元素与集合之间有：属于关系 函数 excel方差函数excelsd函数已知函数     2 f x m x mx m      2 1 4 2拉格朗日函数pdf函数公式下载 之间有：　调用关系……关系－－联系:事物间的多值对应。本章讨论的是：用集合理论刻画这些“联系”所建立的最一般的数学模型－－关系，这也是计算机科学中数据描述和信息处理的最常用的数学模型。2.1关系的概念2.1.1n元关系定义2-1设A1,A2,…An是集合，则称A1×A2×…×An的任意一个子集R为A1,A2,…An间的n元关系。集合A1,A2,…,An叫做关系的域,n叫做它的阶。若RAn,则称R为A上的n元关系。可以利用n元关系 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示计算机的数据库:数据库由记录组成，这些记录是由字段构成的n元组。字段是n元组的数据项。例设R是A×N×S×D×T的子集，其中A是所有航空公司的集合，N是航班号的集合，S是出发地的集合，D是目的地的集合，T是起飞时间的集合。则R是由5元组(a,n,s,d,t)组成的表示飞机航班的关系。例如，设R表示由国内航空公司飞机航班构成的关系，如果南方航空公司在15:00有从广州到北京的2963航班，那么(南方航空，2963，广州，北京，15:00)属于R。定义若(a,b)∈R,则称a与b有关系R,记为aRb;若(a,b)R,则称a与b没有关系R,记为aRb。设有两个集合A和B，其笛卡儿积A×B的任意一个子集R称为从A到B的一个二元关系（relationfromAtoB）。即:RA×B特别地，当A＝B时，R称为A上的关系（relationonA）,这时RA22.1.2二元关系直观地看，二元关系就是反映“多值对应”的二维表，例如，学生－选课表：学生课程张三离散数学李四微积分张三高级语言......把学生选课表用集合来表示：R={（张三,离散数学）,　（李四,微积分）,　（张三,高级语言）,　…}序偶的集合R同样也刻画了学生集合A=｛张三，李四，…｝与课程集合B=｛离散数学，微积分，高级语言，…｝之间“多值对应”的联系。【例】设A＝｛1,2,3,4,5｝,B＝｛a,b,c｝,则R1＝{(1,a),(1,b),(2,b),(3,a)}是从A到B的关系,而R2＝{(a,2),(c,4),(c,5)}是从B到A的关系。【定义】设RA×A,1)当R＝时,称R为A上的空关系;2)当R＝A×A=A2时,称R为集合A上的全域关系,用EA表示。显然EA＝{(x,y)|x∈A且y∈A}3)若R＝｛(x,x)|x∈A｝,则称R是A上的恒等关系,用ＩA表示。【例】设A＝{1,2,3,4,5}，R是A上的二元关系，其定义为：当a，b∈A且a能整除b时，(a,b)∈R（R称为A上的整除关系），求R。【例】设A＝{1,2,3,4,5,6}，R是A上的二元关系，其定义为：当a，b∈A且a和b被3除后余数相同时，(a,b)∈R（R也称为A上的模3同余关系,记为3），求R。定义1.12设R是一个二元关系，(1)R中所有序偶的第一元素构成的集合称为R的定义域（domain），记做domR。(2)R中所有序偶的第二元素构成的集合称为R的值域（range），记做ranR。2.1.3关系的定义域、值域例如：A={a,b,c,d}，B={1,2,3}，R＝{(a,2),(b,2),(c,1)}，则：domR={a,b,c}，ranR={1,2}2.1.4关系表示1、关系图2、关系矩阵1.关系图情形1：R是从A到B的关系,采用如下的图示:　1）用大圆圈表示集合A和B，里面的小圆圈（或实心圆）表示集合中的元素;2）若a∈A，b∈B，且(a,b)∈R，则在图中将表示a和b的小圆圈用直线或弧线连接起来,并加上从结点a到结点b方向的箭头。例如：A={a1,a2,a3,a4}B={b1,b2,b3,b4,b5}R={(a1,b1),(a2,b3),(a3,b2),(a4,b4),(a4,b5)}情形2：R是A上的关系,其画法如下:1)集合A中的每一个元素a用带有元素符号的顶点(称作顶点a)表示。2)若a,b∈A,且(a,b)∈R,则将顶点a和顶点b用一条带有箭头的有向边连接起来,其方向由顶点a指向顶点b。【例】A={a1,a2,a3,a4,a5}，R={(a1,a1),(a1,a2),(a2,a3),(a3,a4),(a4,a1),(a4,a5),(a5,a3)}。求R的关系图。2.关系矩阵：由 表格 关于规范使用各类表格的通知入职表格免费下载关于主播时间做一个表格详细英语字母大小写表格下载简历表格模板下载 法抽象而来【定义】设集合A＝{x1,x2,…,xm},B＝{y1,y2,…yn},R是从A到B的关系,则m×n矩阵MR＝(mij)m×n叫R的关系矩阵,其中:【例】设A＝{1,2,3,4,5},B＝{a,b,c},求下面两个关系的关系矩阵。A到B的关系:R1＝{(1,a),(1,b),(2,b),(3,a)}B到A的关系:R2＝{(a,2),(c,4),(c,5)}设集合A＝{a1,a2,…,an},对于A上的关系R,其关系矩阵MR＝(mij)n×n是n×n的,其中:【例】求A＝{1,2,3,4}上的≤关系、EA和IA的关系矩阵。2.1.5函数的关系定义函数如何转换成关系?【例2-15】A={a,b,c},B={1,2,3},f:AB,f(a)=2,f(b)=3,f(c)=3.注意：一般来说,A到B的关系不是A到B的函数.定义2-4A到B的关系f满足:(1)domf=A;（像的存在性）(2)对任意x∈A，若(x,y1)∈f且(x,y2)∈f,则y1=y2；（像的唯一性）则称f为A到B的函数。关系如何转换成函数?作业：P44:1,3,7，13(1)(2)2.2关系的运算2.2.1.关系的集合运算设注意：可以用n元关系上的集合运算构造新的n元关系。例设A和B分别是学校的所有学生和所有课程的集合。假设:R1由所有有序对(a,b)组成，其中a是选修课程b的学生;R2由所有的有序对(a,b)构成，其中课程b是a的必修课。问关系R1∪R2，R1∩R2，R1－R2，R2－R1，R1⊕R2是什么?解关系R1∪R2由所有的有序对(a,b)组成，其中a是一个学生，他或者选修了课程b，或者课程b是他的必修课。R1∩R2是所有有序对(a,b)的集合，其中a是一个学生，他选修了课程b并且课程b也是a的必修课。R1－R2是所有有序对(a,b)的集合，其中a已经选修了课程b，但b不是a的必修课。R2－R1是所有有序对(a,b)的集合，其中b是a的必修课，但a没有选它。R1⊕R2由所有的有序对(a,b)组成，其中学生a已经选修了课程b，但课程b不是a的必修课，或者课程b是a的必修课，但是a没有选修它。如何用关系矩阵实现关系的集合运算?Questions记关系R的关系矩阵为MR=(uij)mn，关系S的关系矩阵为MS=(vij)mn，则1)R∪S的关系矩阵MR∪S是MR与MS的按位或(布尔和):MR∪S=MR+MS=(uij+vij)mn=(uijvij)mn布尔和逻辑或布尔和2)R∩S的关系矩阵MR∩S是MR与MS的按位与(按位布尔积):MR∩S=(uijvij)mn=(uijvij)mn3)的关系矩阵M是MR的按位取反:把每个1改为0，每个0改为14)利用A－B＝A∩,可计算MR-S及MRS布尔积逻辑与2.2.2关系的逆运算定义2-5设R是A到B的二元关系，如果把R中的每一个有序对中的元素顺序互换，所得到的B到A的二元关系称为R的逆关系，记作R-1。例:R表示“课程-学生”关系，则R-1是“学生-课程”关系。【例】A={a,b,c}，B={x,y,z}，R是A到B的二元关系，且有：R={(a,x),(b,y),(c,y)}，则R-1是B到A的二元关系，且有：R-1={(x,a),(y,b),(y,c)}【例】A={1,2,3}，R是A上的二元关系，且有：R={(1,2),(2,3),(3,1)}则其逆关系为：R-1={(2,1),(3,2),(1,3)}逆关系R-1的关系矩阵与关系R的关系矩阵有何联系？Questions如果二元关系R的关系矩阵为MR，则MR的转置矩阵MRT就是逆关系R-1的关系矩阵。【定理2-2】【定理2-3】(1)(2)(3)R是A上的关系,则定义2-6R是集合A到B的二元关系，S是集合B到C的二元关系，R和S的复合R◦S定义为R◦S={(x,z)|y∈B使得(x,y)∈R且(y,z)∈S}它是A到C的二元关系。2.2.3关系的复合运算1.关系R和S的复合例:R表示“教师-课程”关系，S表示“课程-学生”关系，则R◦S是“教师-学生”关系。例:R表示“父子”关系，则R◦R是“祖孙”关系。例:R表示“教师-课程”关系，S表示“课程-学生”关系，T表示“学生-家长”关系，则(R◦S)◦T是“教师-学生家长”关系。例:R表示“父子”关系，则(R◦R)◦R是什么关系?例:设A＝｛1,2,3,4｝,B＝｛2,3,4｝,C＝｛1,2,3｝,R＝｛(a,b)|(a,b)∈A×B且(a＋b＝4)｝S＝｛(b,c)|(a,b)∈B×C且(|b－c|＝1)｝求R◦S。解:R＝{(1,3),(2,2)}S＝{(2,1),(3,2),(4,3),(2,3)}R◦S＝{(1,2),(2,1),(2,3)}复合关系R◦S的图示如图所示。复合关系R◦S2.复合关系的矩阵表示设A={a1,a2,…,am}，B={b1,b2,…,bn}，C={c1,c2,…,cs}，R是A到B的二元关系，R的关系矩阵为：其中：1(ai,bj)∈R0(ai,bj)RS是B到C的二元关系，S的关系矩阵：其中：1(bi,cj)∈S0(bi,cj)S令：则有：当u11v11=1或u12v21=1或……或u1nvn1=1时w11=1；当u11v11=0且u12v21=0且……且u1nvn1=0时w11=0；一般地有：当ui1v1j=1或ui2v2j=1或……或uinvnj=1时wij=1；当ui1v1j=0且ui2v2j=0且……且uinvnj=0时wij=0；引入布尔加法(逻辑或)（即0+0=0，1+0=0+1=1，1+1=1），则：w11=1当且仅当u11v11+u12v21+……+u1nvn1=1；一般地wij=1当且仅当ui1v1j+ui2v2j+……+uinvnj=1；这说明：复合关系R◦S的关系矩阵MR◦S=MR◦MS其中◦是矩阵的布尔乘法（矩阵的逻辑乘法）。【例】A={1,2,3}，B={a,b,c,d}，C={x,y,z}，R是A到B的二元关系，R={(1,a),(1,b),(2,b),(3,c)}，S是B到C的二元关系，S={(a,x),(b,x),(b,y),(b,z)}。则有：【例】A={1,2,3,4}，R和S都是A上的二元关系R={(1,1),(1,2),(1,3),(2,3),(2,4),(4,3),(4,4)}S={(1,2),(1,3),(2,3),(2,4),(3,1),(4,3)}则有：定理2-4设R是A到B的二元关系，S是B到C的二元关系，T是C到D的二元关系，则：(R◦S)◦T=R◦(S◦T)二元关系与其关系矩阵是一一对应的，复合关系R◦S的关系矩阵等于R的关系矩阵与S的关系矩阵的乘积，而矩阵的乘法运算满足结合律，所以关系的复合也满足结合律，即：定理2-7设RA×B，则：(1)IA◦R=R(2)R◦IB=R定理2-6设R是A到B的二元关系，S是B到C的二元关系，则(R◦S)-1=S-1◦R-1。定义2-7设R是A上的关系，n为自然数，则R的n次幂定义为：(1)R0={(x,x)|x∈A}=IA(2)Rn+1=Rn◦R由于二元关系的复合满足结合律，所以二元关系的幂运算是有意义的。3.关系的幂运算【例】设R是世界上所有人的集合上的关系，如果a认识b，那么R包含(a,b)。问Rn是由怎样的序偶构成的?其中n是大于等于2的正整数。解如果存在人c，使得(a,c)R且(c,b)R，即存在人c使得a认识c，c认识b，那么关系R2包括(a,b)。类似地，如果存在人x1，x2，…，xn-1使得a认识x1，x1认识x2，…，xn-1认识b，那么Rn包含对(a,b)。【例】设R是广州市所有地铁站的集合上的关系。如果可以从站a不换车就旅行到站b，那么R包含对(a,b)。当n是正整数时，Rn是由怎样的序偶构成的?解如果经过至多n-1次换车就可以从站a旅行到站b，关系Rn就包含(a,b)。定理2-8设R是A上的关系，m,n∈N，则(1)Rm◦Rn=Rm+n(2)(Rm)n=Rmn(3)(Rm)-1=(R-1)m作业：P51:1,3,11定义2-9,10设R是A上的关系,(1)若对于所有的x∈A,都有(x,x)∈R,则称R是自反的(reflexive)。(2)若对于所有的x∈A,都有(x,x)R,则称R是反自反的(irreflexive)。2.3关系的性质【例】设A＝{1,2,3},R1,R2,R3是A上的关系，其中R1＝{(1,1),(2,2)}R2＝{(1,1),(2,2),(3,3),(1,2)}R3＝{(1,3)}说明它们是否为A上的自反关系或反自反关系。【例】全域关系EA,恒等关系ＩA是A上的自反关系;小于等于关系A,整除关系DA是A上的自反关系;小于关系