离散数学二元关系

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

1定义7.1由两个元素x和y,按照一定的顺序组成的二元组称为有序对或序偶,记作x,y,其中x是它的第一元素,y是它的第二元素.注:有序对具有如下性质:(1)有序性x,y≠y,x(当x≠y时)(2)x,y与u,v相等的充分必要条件是x=u且y=v.这些性质是二元集{x,y}所不具备的.例如当x≠y时有{x,y}={y,x}.第一节有序对与笛卡儿一、有序对第七章二元关系2二、笛卡儿积定义7.2设A,B为集合,用A中元素为第一元素,B中的元素为第二元素构成有序对.所有这样的有序对组成的集合叫做A与B的笛卡儿积,记作A×B.笛卡儿积的符号化表示为A×B={x,y|x∈A∧y∈B}例A={1,2,3},B={a,b,c}A×B={1,a,1,b,1,c,2,a,2,b,2,c,3,a,3,b,3,c}B×A={a,1,b,1,c,1,a,2,b,2,c,2,a,3,b,3,c,3}3注:笛卡儿积的性质(1)不适合交换律A×B≠B×A(A≠B,A≠∅,B≠∅)(2)不适合结合律(A×B)×C≠A×(B×C)(A≠∅,B≠∅,C≠∅)(3)对于并或交运算满足分配律A×(B∪C)=(A×B)∪(A×C)(B∪C)×A=(B×A)∪(C×A)A×(B∩C)=(A×B)∩(A×C)(B∩C)×A=(B×A)∩(C×A)(4)若A或B中有一个为空集,则A×B就是空集.A×∅=∅×B=∅(5)若|A|=m,|B|=n,则|A×B|=mn4例7.2设}2,1{A,求AAP)(.解AAP)(}2},2,1{,1},2,1{,2},2{,1},2{,2},1{,1},1{,2,,1,{}2,1{}}2,1{},2{},1{,{5例7.3(1)证明A=B,C=D⇒A×C=B×D(2)A×C=B×D是否推出A=B,C=D?为什么?解(1)任取x,yx,y∈A×C⇔x∈A∧y∈C⇔x∈B∧y∈D⇔x,y∈B×D(2)不一定.反例如下:A={1},B={2},C=D=∅,则A×C=B×D但是A≠B.6第二节二元关系一、二元关系的定义定义7.3如果一个集合满足以下条件之一:(1)集合非空,且它的元素都是有序对(2)集合是空集则称该集合为一个二元关系,简称为关系,记作R.如果x,y∈R,可记作xRy;如果x,y∉R,则记作xy.例:R={1,2,a,b},S={1,2,a,b}.则R是二元关系,当a,b不是有序对时,S不是二元关系.根据上面的记法,可以写1R2,aRb,ac等.7二、从A到B的关系与A上的关系定义7.4设A,B为集合,A×B的任何子集所定义的二元关系叫做从A到B的二元关系,当A=B时则叫做A上的二元关系.例A={0,1},B={1,2,3},那么R1={0,2},R2=A×B,R3=∅,R4={0,1}R1,R2,R3,R4是从A到B的二元关系,R3和R4同时也是A上的二元关系.8三、A上重要关系的实例定义7.5设A为任意集合,∅是A上的关系,称为空关系,EA,IA分别称为全域关系与恒等关系,其中EA={x,y|x∈A∧y∈A}=A×A,IA={x,x|x∈A}.例如,A={1,2},则EA={1,1,1,2,2,1,2,2},IA={1,1,2,2}.9特定集合上的小于等于关系LA、整除关系DA、包含关系R⊆定义如下:LA={x,y|x,y∈A∧x≤y},这里A⊆R,R为实数集合,DA={x,y|x,y∈B∧x整除y},这里A⊆Z*,Z*为非0整数集合,R⊆={x,y|x,y∈A∧x⊆y},这里A是集合族.10四、关系的表示表示一个关系的方式有三种:关系的集合表达式、关系矩阵、关系图.关系矩阵和关系图的定义(1)关系矩阵若},,,{},,,,{2121nmyyyBxxxA,R是从A到B的关系,R的关系矩阵是布尔矩阵nmijRrM][,其中RyxrRyxrjiijjiij,0,,1.11(2)关系图},,,{21nxxxA,R是从A上的关系,R的关系图是RAGR,,其中A为结点集,R为边集.如果jiyx,属于关系R,在图中就有一条从ix到jx的有向边.注:(1)关系矩阵适合表示从A到B的关系或者A上的关系(A,B为有穷集)(2)关系图适合表示有穷集A上的关系12例A={1,2,3,4},R={1,1,1,2,2,3,2,4,4,2},R的关系矩阵RM和关系图RG如下:0010000011000011RM,13第三节关系的运算一、关系的基本运算定义1.定义域、值域与域定义7.6设R是二元关系.(1)R中所有的有序对的第一元素构成的集合称为R的定义域,记作domR,即domR={x|∃y(x,y∈R)}(2)R中所有的有序对的第二元素构成的集合称为R的值域,记作ranR,即ranR={y|∃x(x,y∈R)}(3)R的定义域和值域的并集称为R的域,记作fldR,即fldR=domR∪ranR14例R={1,2,1,3,2,4,4,3},则domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}2.逆与合成定义7.7设R是二元关系,R的逆关系,简称R的逆,记作R−1,其中R−1={y,x|x,y∈R}定义7.8设F,G为二元关系,G对F的右复合记作F◦G,其中F◦G={x,y|∃t(x,t∈F∧t,y∈G)}153.限制与像定义7.9设R为二元关系,A是集合(1)R在A上的限制记作R↑A,其中R↑A={x,y|xRy∧x∈A}(2)A在R下的像记作R[A],其中R[A]=ran(R↑A)注:R在A上的限制R↑A是R的子关系,即R↑A⊆R,而A在R下的像R[A]是ranR的子集,即R[A]⊆ranR.例设R={1,2,1,3,2,2,2,4,3,2},则R↑{1}={1,2,1,3},R↑∅=∅,R↑{2,3}={2,2,2,4,3,2},R[{1}]={2,3},R[∅]=∅,R[{3}]={2}.16二、关系运算的性质定理7.1设F是任意的关系,则(1)(F−1)−1=F(2)domF−1=ranF,ranF−1=domF证(1)任取x,y,由逆的定义有x,y∈(F−1)−1⇔y,x∈F−1⇔x,y∈F.所以有(F−1)−1=F.(2)任取x,x∈domF−1⇔∃y(x,y∈F−1)⇔∃y(y,x∈F)⇔x∈ranF所以有domF−1=ranF.同理可证ranF−1=domF.17定理7.2设F,G,H是任意的关系,则(1)(F◦G)◦H=F◦(G◦H)(2)(F◦G)−1=G−1◦F−1证(1)任取x,y,x,y∈(F◦G)◦H⇔∃t(x,t∈F◦G∧t,y∈H)⇔∃t(∃s(x,s∈F∧s,t∈G)∧t,y∈H)⇔∃t∃s(x,s∈F∧s,t∈G∧t,y∈H)⇔∃s(x,s∈F∧∃t(s,t∈G∧t,y∈H))⇔∃s(x,s∈F∧s,y∈G◦H)⇔x,y∈F◦(G◦H)所以(F◦G)◦H=F◦(G◦H).18(2)任取x,y,x,y∈(F◦G)−1⇔y,x∈F◦G⇔∃t(y,t∈F∧t,x∈G)⇔∃t(x,t∈G−1∧t,y∈F−1)⇔x,y∈G−1◦F−1所以(F◦G)−1=G−1◦F−1.定理7.3设R为A上的关系,则R◦IA=IA◦R=R.19定理7.4(1)F◦(G∪H)=F◦G∪F◦H(2)(G∪H)◦F=G◦F∪H◦F(3)F◦(G∩H)⊆F◦G∩F◦H(4)(G∩H)◦F⊆G◦F∩H◦F证(3)任取x,y,x,y∈F◦(G∩H)⇔∃t(x,t∈F∧t,y∈G∩H)⇔∃t(x,t∈F∧t,y∈G∧t,y∈H)⇔∃t((x,t∈F∧t,y∈G)∧(x,t∈F∧t,y∈H))⇒∃t(x,t∈F∧t,y∈G)∧∃t(x,t∈F∧t,y∈H)⇔x,y∈F◦G∧x,y∈F◦H⇔x,y∈F◦G∩F◦H所以有F◦(G∩H)=F◦G∩F◦H.20定理7.5设F为关系,A,B为集合,则(1)F↑(A∪B)=F↑A∪F↑B(2)F[A∪B]=F[A]∪F[B](3)F↑(A∩B)=F↑A∩F↑B(4)F[A∩B]⊆F[A]∩F[B]证(1)任取x,yx,y∈F↑(A∪B)⇔x,y∈F∧x∈A∪B⇔x,y∈F∧(x∈A∨x∈B)⇔(x,y∈F∧x∈A)∨(x,y∈F∧x∈B)⇔x,y∈F↑A∨x,y∈F↑B⇔x,y∈F↑A∪F↑B所以有F↑(A∪B)=F↑A∪F↑B.21三、A上关系的幂运算定义7.10设R为A上的关系,n为自然数,则R的n次幂定义为:(1)R0={x,x|x∈A}=IA(2)Rn+1=Rn◦R注:对于A上的任何关系R1和R2都有AIRR0201.关系的幂的计算:给定A上的关系R和自然数n,怎样计算nR呢?若n是0或1,结果是很简单的.下面考虑2n的情况.如果R是用集合表达式给出的,可以通过1n次合成计算得到nR.22如果R是用关系矩阵M给出的,则nR的关系矩阵是nM,即n个矩阵M之积.与普通矩阵乘法不同的是,其中的相加是逻辑加,即111,10011,000.如果R是用关系图G给出的,可以直接由图G得到nR的关系图G.G的顶点集与G相同.考察G的每个顶点ix,如果在G中从ix出发经过n步长的路径到达顶点jx,则在G中加一条从ix到jx的边.当把所有这样的边都找到以后,就得到图G.23例7.2.3设{,,,}Aabcd,{,,,,,,,}Rabbabccd,求R的各次幂,分别用矩阵和关系图表示.解R的关系矩阵为0100101000010000M,则234,,RRR的关系矩阵分别是21010010100000000MMM,320101101000000000MMM,431010010100000000MMM.24因此42MM,53RR,.所以可以得到246RRR,357RRR,而0R,即为AI的关系矩阵.至此,R各次幂的关系矩阵都得到了.用关系图的方法得到0123,,,,RRRR的关系图如下图所示.25第四节关系的性质一、五种性质的定义1.自反性与反自反性定义7.11设R为A上的关系,(1)若∀x(x∈A→x,x∈R),则称R在A上是自反的.(2)若∀x(x∈A→x,x∉R),则称R在A上是反自反的.例如:自反关系:全域关系EA,恒等关系IA,小于等于关系LA,整除关系DA;反自反关系:实数集上的小于关系、幂集上的真包含关系.例设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}则R2是自反的,R3是反自反的,R1既不是自反的也不是反自反的.262.对称性与反对称性定义7.12设R为A上的关系,(1)若∀x∀y(x,y∈A∧x,y∈R→y,x∈R),则称R为A上对称的关系.(2)若∀x∀y(x,y∈A∧x,y∈R∧y,x∈R→x=y),则称R为A上的反对称关系.例如:对称关系:A上的全域关系EA,恒等关系IA和空关系∅反对称关系:恒等关系IA和空关系也是A上的反对称关系.例设A={1,2,3},R1,R2,R3和R4都是A上的关系,其中R1={1,1,2,2},R

1 / 48
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功