当前位置:首页 > 电子/通信 > 综合/其它 > 关系及其表示法-集合与关系-离散数学
关系及其表示法第1页关系是一个非常普遍的概念,如数值的大于关系、整除关系,人类的父子关系、师生关系、同学关系等。要求:1、理解定义关系定义域(前域)、值域2、掌握关系的表示方法3、熟记特殊的关系4、会计算关系的集合运算第2页1.关系的定义空集或任一序偶的集合,都称为一个二元关系。设A、B是集合,若RA×B,则称R是一个从A到B的二元关系。若RA×A,则称R是A上的二元关系。二元关系简称为关系。x,yR可记作xRy;一、基本概念设R1={1,2,a,b},R2={1,2,a,b}。则R1是二元关系,R2不是二元关系,只是一个集合。举例关系是以序偶为元素的集合。x,yR可记作xRy定义1:定义2:x,yR,xRy,表示x和y具有关系R。x,yR,表示x和y不具有关系R。第3页注意:关系集合满足以下条件之一:(1)集合非空,且它的元素都是序偶;(2)集合是空集,即空集也可称作关系。序偶是讲究次序的,关系也是有序的。即x,y∈R未必有y,x∈R,x与y有关系R,未必y与x有关系R。例:甲与乙有父子关系,则乙与甲肯定没有父子关系。由于任何A×B的子集都是一个二元关系,而A×B共有2|A|╳|B|个不同的子集。因此,从A到B不同的关系共有2|A|╳|B|个。1.2.3.第4页例3-5.1①A={0,1},B={x,y,z},则R1={0,x,1,z},R2=A×B,R3=等都是从A到B的二元关系;R4={0,0}和R3同时也是A上的二元关系。②A为整数集合,则R={x,y|x能整除y(即x|y),x,yA}为A上的整除关系。如:1,3,2,8,4,80,7,84等等。③父子关系:{x,y|x人类,y人类,且x是y的父亲(y是x的儿子)}第5页④有王、张、李、赵是某校的老师,该校有三门课程:程序设计、离散数学和英语,已知王可以教程序设计和离散数学,张可以教程序设计和英语,李可以教离散数学,赵可以教英语,若记A={王,张,李,赵},B={程序设计,离散数学,英语}。那么这些老师与课程之间的对应关系就可以用由A到B的一个关系R中的序偶来表示。R={王,程序设计,王,离散数学,张,程序设计,张,英语,李,离散数学,赵,英语}第6页2.三个特殊关系(1)空关系Φ:因为ΦA×B,(或ΦA×A),所以Φ也是一个从A到B(或A上)的关系,称为空关系。(2)完全关系(全域关系)E:即含有A×B(或A×A)全部序偶的关系,A×B(或A×A)本身也是一个从A到B(或A上)的关系,称为完全关系。(3)A上的恒等关系IA:IAA×A,且IA={x,x|x∈A}称为A上的恒等关系。A={1,2,3},则空关系=ΦEA={1,1,1,2,1,3,2,1,2,2,2,3,3,1,3,2,3,3}IA={1,1,2,2,3,3}。举例第7页其他常见的关系小于或等于关系:LA={x,y|x,y∈A∧x≤y},其中AR。整除关系:DA={x,y|x,y∈A∧x整除y},其中AZ*Z*是非零整数集包含关系:R={x,y|x,y∈A∧xy},其中A是集合族。设A={1,2,3},B={a,b},则(1)LA={1,1,1,2,1,3,2,2,2,3,3,3}DA={1,1,1,2,1,3,2,2,3,3}(2)令C=ρ(B)={,{a},{b},{a,b}},则C上的包含关系是R={,,,{a},,{b},,{a,b},{a},{a},{a},{a,b},{b},{b},{b},{a,b},{a,b},{a,b}}举例第8页二、关系的表示方法1.枚举法即将关系中所有序偶一一列举出,写在大括号内。如R={1,1,1,2,1,3,1,4,2,2,2,3,2,4,3,3,3,4,4,4}。2.谓词公式法即用谓词公式表示序偶的第一元素与第二元素间的关系。如“”={x,y|x∈N∧y∈N∧xy}3.有向图法4.关系矩阵法第9页3.有向图法表示二元关系R的图叫做R的关系图。⑴从A到B的二元关系R的关系图。⑵A上的二元关系R的关系图。第10页ABR:⑴A到B二元关系R的关系图设A={a1,a2,…,am},B={b1,b2,…,bn},R是A到B二元关系,R的关系图的绘制方法如下:4。3。2。1。。c。b。a①画出m个小圆圈(实心或空心)表示A的元素,再画出n个小圆圈表示B的元素。这些小圆圈叫做关系图的结点。②关系中的序偶ai,bj,画一条从ai到bj的有方向(带箭头)的线。这些有方向的线叫关系图的边。(注意ai是始点,bj是终点,次序不能颠倒)。例3-5.3:设A={1,2,3,4},B={a,b,c},RA×B,R={1,a,1,c,2,b,3,c},R的关系图如下:第11页⑵A上的二元关系R的关系图设A={a1,a2,…,am},R是A上的二元关系,其关系图的绘制方法如下:①画出m个小圆圈表示A的元素。②若ai,ajR,则从ai到aj画一根有方向(带箭头)的线。③若ai,aiR,则从ai到ai画一条有向环(自回路)。例:设函数集合P={P1,P2,P3,P4,P5},考虑它们之间的调用关系R:P1调用P2;P2调用P4;P2调用P2;P3调用P1;P4调用P5;P5调用P2;则R={P1,P2,P2,P4,P2,P2,P3,P1,P4,P5,P5,P2R的关系图为:P1P2P3P4P5第12页有限集合之间的关系也可以用矩阵来表示,这种表示法便于用计算机来处理关系。设A={a1,a2,,am},B={b1,b2,,bn}是个有限集,RA×B,定义R的关系矩阵是m×n阶矩阵MR=(rij)m×n,其中A={a1,a2,,am}是个有限集,RA×A,定义R的关系矩阵是m×m阶矩阵MR=(rij)m×m,其中1若ai,bj∈R0若ai,bj∈R(1≤i≤m,1≤j≤n)4.矩阵表示法rij=1若ai,bj∈R0若ai,bj∈R(1≤i,j≤m)rij=第13页A={a,b,c},B={1,2,3,4},R1A×BR1={a,1,a,3,b,2,c,1,c,4}A={1,2,3,4},R2A×AR2={1,1,1,4,2,3,3,1,3,4,4,1,4,2}1010010010013×41234注意MR1=MR2=abc1001001010014×4123412341100在写关系矩阵时,首先应对集合A和B中的元素进行排序,不同的排序会得到不同的关系矩阵。当集合以枚举法表示时,如果没有对集合的元素排序,则默认枚举的次序为元素的排序。第14页A={1,2,3}上的Φ、完全关系及IA的关系图及矩阵如下:MIA=1000100013×30000000003×3MΦ=1111111113×3MA×A=1。。2。3Φ。1。2。3A×A。1。2。3IA特殊关系的表示第15页例3-5.4(1)设A={1,2,3,4},B={2,4,6},R表示A与B的整除关系,写出关系R的四种表示法。解:由题意得枚举法:谓词公式法:对应的关系图为:关系矩阵为:12342461114×3246MR=1234111001010R={1,2,1,4,1,6,2,2,2,4,2,6,3,6,4,4};R={x,y|x能整除y,x∈A,y∈B}。第16页由于关系就是集合,所以集合的∩、∪、~和-运算对关系也适用。定理3-5.1设R和S是从集合X到集合Y的两个关系,则R∩S,R∪S,~R,R-S仍是从X到Y的关系。证明:因为RXY,SXY,所以R∩SXY,R∪SXY;~R=XY-RXY,同理:~SXYR-S=R∩~SXY。故R∩S,R∪S,~R,R-S是从X到Y的关系。三、关系的集合运算第17页A是学生集合,R是A上的同乡关系,S是A上的同姓关系,则R∪S:或同乡或同姓关系R∩S:既同乡又同姓关系R-S:同乡而不同姓关系~R:不是同乡关系,这里~R=(A×A)-R例3-5.2第18页作业第109页⑵、⑸c)d)第19页
本文标题:关系及其表示法-集合与关系-离散数学
链接地址:https://www.777doc.com/doc-3500990 .html