离散数学二元关系

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