离散数学 关系.ppt

《离散数学 关系.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章关系1考察日常生活和科学技术中的“关系”：人与人之间有：父子关系兄弟关系师生关系两数之间有：大于关系等于关系小于关系2集合之间有：包含关系相等关系元素与集合之间有：属于关系函数之间有：调用关系……3关系－－联系:事物间的多值对应。本章讨论的是：用集合理论刻画这些“联系”所建立的最一般的数学模型－－关系，这也是计算机科学中数据描述和信息处理的最常用的数学模型。42.1关系的概念2.1.1n元关系定义2-1设A1,A2,…An是集合，则称A1×A2×…×An的任意一个子集R为A1,A2,…An间的n元关系。集合A1,A2,…,An叫做关系的域,n叫做它的阶。

2、若RAn,则称R为A上的n元关系。5可以利用n元关系表示计算机的数据库:数据库由记录组成，这些记录是由字段构成的n元组。字段是n元组的数据项。6例设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。7定义若(a,b)∈R,则称a与b有关系R,记为aRb;若

3、(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二元关系8直观地看，二元关系就是反映“多值对应”的二维表，例如，学生－选课表：学生课程张三离散数学李四微积分张三高级语言......9把学生选课表用集合来表示：R={（张三,离散数学）,（李四,微积分）,（张三,高级语言）,…}序偶的集合R同样也刻画了学生集合A=｛张三，李四，…｝与课程集合B=｛离

4、散数学，微积分，高级语言，…｝之间“多值对应”的联系。10【例】设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的关系。11【定义】设RA×A,1)当R＝时,称R为A上的空关系;2)当R＝A×A=A2时,称R为集合A上的全域关系,用EA表示。显然EA＝{(x,y)

5、x∈A且y∈A}3)若R＝｛(x,x)

6、x∈A｝,则称R是A上的恒等关系,用ＩA表示。12【例】设A＝{1,2,3,4,5}，R是A上的二元关系，其定义为：当a

7、，b∈A且a能整除b时，(a,b)∈R（R称为A上的整除关系），求R。13【例】设A＝{1,2,3,4,5,6}，R是A上的二元关系，其定义为：当a，b∈A且a和b被3除后余数相同时，(a,b)∈R（R也称为A上的模3同余关系,记为3），求R。14定义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)}

8、，则：domR={a,b,c}，ranR={1,2}152.1.4关系表示1、关系图2、关系矩阵161.关系图情形1：R是从A到B的关系,采用如下的图示:1）用大圆圈表示集合A和B，里面的小圆圈（或实心圆）表示集合中的元素;2）若a∈A，b∈B，且(a,b)∈R，则在图中将表示a和b的小圆圈用直线或弧线连接起来,并加上从结点a到结点b方向的箭头。17例如：A={a1,a2,a3,a4}B={b1,b2,b3,b4,b5}R={(a1,b1),(a2,b3),(a3,b2),(a4,b4),(a4,b5)}18情形2：R是A上的关系,其画法如下:1)集

9、合A中的每一个元素a用带有元素符号的顶点(称作顶点a)表示。2)若a,b∈A,且(a,b)∈R,则将顶点a和顶点b用一条带有箭头的有向边连接起来,其方向由顶点a指向顶点b。19【例】A={a1,a2,a3,a4,a5}，R={(a1,a1),(a1,a2),(a2,a3),(a3,a4),(a4,a1),(a4,a5),(a5,a3)}。求R的关系图。202.关系矩阵：由表格法抽象而来【定义】设集合A＝{x1,x2,…,xm},B＝{y1,y2,…yn},R是从A到B的关系,则m×n矩阵MR＝(mij)m×n叫R的关系矩阵,其中:21【例】设A＝{1,2,3,

10、4,5},B＝{a,b,c},求下面