关系的基本概念及其性质 |
您所在的位置:网站首页 › 全域关系的关系图是什么 › 关系的基本概念及其性质 |
一、关系的基本概念及其性质
1、关系的概念
二元关系:
定义:设A和B是两个集合,A×B的任一子集R称为从A到B的一个二元关系。 如果(a,b)∈R,则a与b符合关系R,记为aRb; 如果(a,b) R,则a与b不符合关系R,记为aRb。 如果A=B,则称R为A上的二元关系。 性质: 若|A|=m,|B|=n,则|A×B|=m×n,A×B共有2m×n个子集,所以从A到B的二元关系共有2m×n个。 A×B也是从A到B的二元关系(全域关系)。 A×A上的任意子集都是A上的一个关系 若|A|=n,则A上的关系有2n2个 空集Φ称为从A到B的空关系。 集合{(a,a)|a∈A}称为A上的恒等关系或相等关系,记为IA。 全域关系:EA=A×A RC=A×A-R 序对(a,b)=(c,d)的充要条件是a=c,b=d 定义:设二元关系R⊆A×B,集合{x|x∈A且∃y∈B使(x,y)∈R}称为R的定义域,并记为dom(R);集合{y|y∈B且 ∃x∈A使(x,y)∈R}称为R的值域,并记为ran(R)。 一般地,dom(R)⊆A,ran(R)⊆B。 n元关系:定义:设A1,A2,…,An是n个集合,A1×A2×…×An的一个子集R称为A1,A2,…,An间的一个n元关系,每个Ai称为R的一个域。 2、关系矩阵和关系图 关系矩阵定义:设有穷集合A={a1,a2,…,an}和B={b1,b2,…,bm},R是从A到B的一个二元关系,R的关系矩阵定义为一个矩阵M=(mij),其中 从有穷集合A到有穷集合B的二元关系R用图表示时,首先用点表示A和B的元素,并在旁边标注元素的名字,然后用从点x到点y的矢线表示R中的序对(x,y)。若(x,x)∈R,则画一条从点x指向自身的线,称为环。这样由点和线组成的有向图称为R的关系图。 集合的并、交、差、余运算的性质对关系运算也成立。 作为关系时,余运算是对全域关系而言的,即将A×B作为全集E 3、偏序的性质 自反定义:集合A上的二元关系R称为自反的,如果∀x∈A,有xRx。 说明: 在这个定义中要求A的每个元素x,都有xRx,即(x,x)∈R, 这并不排斥某个序对(x,y),当x≠y时,仍有(x,y)∈R。 显然,R是自反的,当且仅当IA⊆R。(R-1也是自反的) 反自反定义:集合A上的二元关系R称为反自反的,如果∀x∈A,有xRx都不成立。 R是反自反的,则IA∩R=∅ 说明:非空集合上的一个二元关系是自反的,必不是反自反的,反之亦然。 一个二元关系不是自反的,未必是反自反的,反之亦然。 即存在既不是自反的,也不是反自反的二元关系。 对称定义:集合A上的二元关系R,如果∀x,y∈A,只要xRy就有yRx,则称R是对称的。(R-1=R) 反对称定义:集合A上的二元关系R,对∀x,y∈A,如果xRy且yRx,则x=y,则称R是反对称的。(如果xRy,则yRz,除非x=y时有yRx成立)(R∩R-1⊆IA) 关于对称与反对称的说明: 二元关系的对称性和反对称性不是矛盾的 存在既是对称的,也是反对称的二元关系 传递定义:集合A上的二元关系R,对∀ x,y,z∈A,如果xRy且yRz,则xRz,那么称R是传递的。 具有某种性质的关系的关系矩阵、关系图的特点关系矩阵 (1)R是自反的,当且仅当M的对角线上的全部元素均为1。 (2)R是反自反的,当且仅当M的对角线上的全部元素为0。 (3)R是对称的,当且仅当M是对称矩阵。 (4)R是反对称的,当且仅当i≠j时M中元素mij与mji不同时为1。 (5)R是传递的,当且仅当M中的元素mij=1且mjk=1时必有mik=1。 关系图 (6)R是自反的,当且仅当G的每个顶点上均有一个环。 (7)R是反自反的,当且仅当G中没有环。 (8)R是对称的,当且仅当G中任两不同的顶点之间如果有矢线,则必有两条方向相反的矢线。 (9)R是反对称的,当且仅当G中任两顶点之间最多有一条矢线。 (10)R是传递的,当且仅当G从某顶点i沿矢线方向经两条矢线可到达另一顶点j,则必有从顶点i到顶点j的矢线。 4、复合关系和逆关系 复合关系:定义:设R是A到B的二元关系,S是B到C的二元关系,则R与S的复合关系为一个从A到C的二元关系,记为R◦S。 R◦S={(x,z)|x∈A,z∈C, ∃y∈B使xRy且yRz} 关系的复合运算不满足交换律,也不满足幂等律,但是关系的复合运算满足结合律。 设R,S,T分别是集合A到B,B到C,C到D的二元关系,则(R◦S)◦T=R◦(S◦T)。 幂的定义:设R是A上的一个二元关系,递归地定义R的非负整数次幂为: R0=IA,R1=R,Rn+1=Rn◦R 定理:设R是A上的一个二元关系,对任意的非负整数m,n,有 Rm◦Rn=Rm+n,(Rm)n=Rmn 设A是一个有限集且|A|=n,R是A上的一个二元关系,则存在非负整数s,t,使0≤s<t≤2n2 且Rs=Rt。 定理:设R是A到B的二元关系,则 IA◦R=R◦IB=R 定理:设R1是A到B的二元关系,R2和R3是B到C的二元关系,R4是C到D的二元关系,则 (1)R1◦(R2∪R3)=(R1◦R2)∪(R1◦R3) (2)R1◦(R2∩R3)=(R1◦R2)∩(R1◦R3) (3)(R2∪R3)◦R4=(R2◦R4)∪(R3◦R4) (4)(R2∩R3)◦R4=(R2◦R4)∩(R3◦R4) 复合运算的矩阵实现设R和S都是A到B的二元关系,其关系矩阵分别为MR和MS,R∪S与R∩S的关系矩阵分别记为MR∪S和MR∩S,易证明: MR∪S=MR∨MS,MR∩S=MR∧MS。 设R是A到B的二元关系,S是B到C的二元关系,其关系矩阵分别为MR和MS,R◦S的关系矩阵MR◦S,易证明: MR◦ S=MR◦MS。 集合A上的关系R具有传递性的充要条件是R○R⊆R 逆关系定义:设R是从A到B的二元关系,则从B到A的二元关系R-1={(y,x)|(x,y)∈R}称为R的逆关系。 定理:设R是A到B的二元关系,则(R-1)-1=R。 定理:设R和S分别是A到B、B到C的二元关系,则 (R◦S)-1= R-1◦S-1 逆运算的矩阵实现 关系R-1的关系矩阵 是关系R的关系矩阵MR的转置矩阵,即 =(MR)T。 关系的闭包 传递闭包定义:设R是A上的一个二元关系,A上一切包含R的传递关系的交称为R的传递闭包,记为R+。 说明:R+是包含R的那些传递关系中最小的那个关系。 定理:二元关系R的传递闭包R+是传递关系。 定理:设R是A上的一个二元关系,则 定理:设A是n元集,R是A上的一个二元关系,则 传递闭包的矩阵运算实现,即: 定义:设R是A上的一个二元关系,A上包含R的所有自反且传递的二元关系的交称为R的自反传递闭包,记为R*。 定理:设R是A上的一个二元关系,则 R*=R0∪R+ 自反闭包定义:A上包含R的所有自反关系的交,记为r(R),易知 r(R)=R0∪R 而且R是自反的,当且仅当r(R)=R。 对称闭包定义:A上包含R的所有对称关系的交,记为s(R),易知 s(R)=R∪R-1 而且R是对称的,当且仅当s(R)=R。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |