(黄)第2章二元关系(2016-3-26).

1第2章二元关系2.1二元关系的基本概念2.2复合关系、逆关系和关系的闭包运算2.3等价关系与偏序关系2.4函数22.1二元关系的基本概念2.1.1笛卡尔乘积二元关系的定义2.1.2二元关系的3种表示方法2.1.3二元关系的基本类型2.1.4例题选解32.1.1笛卡儿乘积与二元关系的定义设二个集合A与B,A中任取元素a,B中任取元素b称(a,b)为有序对，并要求有序对具有如下性质:注：在集合论中，有序对(a,b)也是一种特殊的集合，通常被定义为（a，b）={{a},{a,b}}.a1=a2且b1=b2。(a1,b1)=(a2,b2)易证此定义即可满足上述有序对所要求的性质。有序对的集合{(a,b)|a∈A,b∈B}称为A与B的笛卡儿积(Descartesproduct),记为A×B,即A×B={(a,b)|a∈A﹠b∈B}.RenéDescartes（1596-1650）笛卡儿（RenéDescartes）法国著名的哲学家、数学家、物理学家。他是西方近代哲学奠基人之一。他对现代数学的发展做出了重要的贡献，因将几何坐标体系公式化而被认为是解析几何之父。他还是西方现代哲学思想的奠基人，是近代唯物论的开拓者且提出了“普遍怀疑”的主张。黑格尔称他为“现代哲学之父”。人们在他的墓碑上刻下了这样一句话：“笛卡儿，欧洲文艺复兴以来，第一个为人类争取并保证理性权利的人。”笛卡儿的名言：我思故我在(Ithink,thereforeIam)4注一般来说A×B≠B×A，(A×B)×C≠A×(B×C)即笛卡儿积不满足交换律，也不存在结合律。笛卡儿积满足对∪,∩,-,⊕的分配律：(1)A×(B∪C)=(A×B)∪(A×C)(2)(B∩C)×A=(B×A)∩(C×A)(3)(A-B)×C=(A×C)-(B×C)(4)(B⊕C)×A=(B×A)⊕(C×A)5现只证明（3）,其余留作练习。6（3）(A-B)×C=(A×C)-(B×C)(x,y)∈(A-B)×Cｘ∈A-B且y∈Cx∈A,y∈C,ｘB(x,y)∈A×C,(x,y)B×C(x,y)∈(A×C)-(B×C)故(A-B)×C=(A×C)-(B×C)证明7Ａ×Ｂ的几何意义：设Ａ＝［ａ，ｂ］，Ｂ＝［ｃ，ｄ］，均为实闭区间则有序对（ｅ，ｆ），ｅ∈Ａ，ｆ∈Ｂ，是平面上一个点（1）Ａ×Ｂ表示矩形区域［ａ≤ｘ≤ｂ，ｃ≤ｙ≤ｄ］（2）Ｂ×Ａ应为矩形区域［ｃ≤ｘ≤ｄ，ａ≤ｙ≤ｂ］注：（1）当且仅当Ａ＝Ｂ时Ａ×Ｂ＝Ｂ×Ａ，是正方形区域（2）由于Ａ×Ｂ也是集合，它应满足集合的一切性质8设RA×B，把(a,b)∈R也记为aRb,此时称为a和b以R相关；把(a,b)R，也记为ab，此时称为a和b不以R相关。二元关系的定义设集合RA×B，则称Ｒ为Ａ到Ｂ的一个二元关系。(注意:二元关系是有序对的一个集合）。∈R9二元关系的前域和值域:若R是A到B的二元关系前域：domR={x|（x，y）∈R}值域：ranR={y|（x，y）∈R}空关系：R=Φ全域关系：A×B设RA×B且Ａ＝Ｂ，则Ｒ是Ａ到Ａ的二元关系，简称为Ａ上的二元关系。例R={(a,b)|a|b,a,b∈N}是自然数集N={0，1,2，3，…}上的二元关系。其中a|b表示a能整除b,即存在c∈N,使ｂ=ac(此时的Ｒ也称为N上的“整除关系”)102.1.2二元关系的3种表示方法例Ａ={张三,李四,王五,赵六}Ｂ={100米,跳高,铅球,足球,跨栏}穷举法表示：Ｒ={(张三,铅球),(张三,足球),(李四,100米),(李四,跳高),(王五,跨栏),(赵六,100米)}是运动会的报名表。二元关系的表示：因为二元关系本身也是集合，除了穷举法、描述法外，还可用表格,矩阵,图示法来直观地表示。11（1）表格法用表格表示一目了然12（2）矩阵法表示A={a1,a2,a3,a4},B={b1,b2,b3,b4,b5}R={(a1,b3),(a1,b4),(a2,b１),(a2,b2),(a3,b5),(a4,b1)})(m00001100000001101100aaaaMbbbbbij4321R54321MR称为R的关系矩阵，其中R)b,(a,0R)b,(a,1mjijiij用带数字下标的字母来代替这些元素设有限集Ａ＝{a1，a2，…，an-1,an}。设R为A上的二元关系，即RA×A，则R的关系矩阵常记为AR，其中AR=（aij),R)a,(a,0R)a,(a,1ajijiij)(aaaaaaaaaaaaaaaaAaaaaijnn1)n(nn2n12n1)2(n22211n1)1(n1211n21Rn1n211314（3）图示法Ａ＝{a,b,c,d}，Ｂ＝{1,2,3,4,5}关系图，直观！Ｒ＝{(a,3),(a,4),(b,1),(b,2),(c,5),(d,1)}15例A={1，2，3，4}上的恒等关系为：IA={(1,1),(2,2),(3,3),(4,4)}IA＝{(a,a）|a∈A}称Ｒ为A上的恒等关系。说明对于一个给定的有限集合，其上的恒等关系IA是唯一确定的。而且,恒等关系一定是A上的。162.1.3二元关系的基本类型本节要求掌握的知识点:1、二元关系的5种基本类型：自反、反自反、对称、反对称、传递2、可传递关系的判别方法17设Ｒ是Ａ上的二元关系，（1）若对任意a∈A，(a,a)∈Ｒ，则称Ｒ为A上的自反关系。自反的二元关系的关系矩阵对角元均为１。（2）若对任意a∈A,(a,a)Ｒ，则称Ｒ为A上的反自反关系。Ｒ的关系矩阵对角元素均为０。1111AR0000AR18注意：不是自反的不一定是反自反的，不是反自反的也不一定是自反的。自反性与反自及性是互斥的，但不互补。如下Venn图：A上所自反的二元关系构成的集合A上所有反自反的二元关系构成的集合A上所有二元关系构成的集合19（3）若(ａ,ｂ)∈Ｒ，ａ≠ｂ则有(ｂ,ａ)∈Ｒ，则称这样的二元关系Ｒ为对称关系。此时Ｒ的相关矩阵AR=（ａij）是对称矩阵，即ａij＝ａji（4）若（a,b）∈Ｒ,ａ≠ｂ，则有(ｂ,ａ)Ｒ，则称这样的二元关系Ｒ为反对称关系。此时Ｒ的关系矩阵AR=(ａij)满足ａijａji＝0（ｉ≠ｊ）20注意：对称与反对称,既不互斥，又不互补。如下Venn图：A上所有对称的二元关系组成的集合A上所有反对称的二元关系组成的集合A上所二元关系构成的集合A上所有既对称又反对称的二元关系21例若A={1,2,3,4},下面哪个是A上的传递关系?R1={(1,2)};R2={(1,2),(2,3),(1,3)}R3={(1,1),(2,2)};R4={(1,2),(2,3),(3,4),(3,1)}R5=A×A（5）设R是A上的二元关系，若满足当(a，b)∈R且(b，c)∈Ｒ时，有(a，c)∈Ｒ，则称这样的Ｒ为A上传递关系。22（6）可传递关系的判定方法2)矩阵法：A上的二元关系Ｒ的关系矩阵记为AR.）a（a）a（a）a（a）a（abnjin2ji21ji1kjikn1kij此处为布尔加运算符1)11,101,110,00(01)定义法：验证若(a，b)∈R且（b，c）∈Ｒ是否都有（a，c）∈Ｒ。有一个例外就不是！方法1：若AR=（aij），B=AR2=ARAR=（bij），(bij=1则R可传递aij=1)(AR-AR2)中的元素无负数方法2：对于关系矩阵AR中的每一个aij=1作如下操作：将AR中的第j行元素对应布尔加到第i行元素上，若操作后矩阵无变化，则R是可传递的；否则，R不是可传递的。矩阵法23例1若集合A上二元关系Ｒ的关系矩阵为1111100111001000010000110RA问R是否是A上的传递关系？24例1解法一)(ijRRRbAAA1111100110001000010000100111110011100100001000011011111001110010000100001102此时满足条件(bijaij=1)，故R是传递的。25例1解法二1111100111001000010000110RAa12=1a13=1a23=1a33=1a41=1a42=1a43=1a51=1a52=1a53=1a54=1a55=1分别将aij=1作如下操作：把AR中的第j行元素对应布尔加到第i行元素上已知VVV依次作类似操作后矩阵AR均无变化。AR无变化故R是传递关系26010011100001000101010000001000001110RA例2若集合A上二元关系Ｒ的关系矩阵为问R是否是A上的传递关系集？27例2解法一用矩阵的布尔乘法，省略。例2解法二010011100001000101010000001000001110RA发现a13=1时，将AR中的第3行元素对应布尔加到第1行元素上，操作后矩阵发生变化，故R不是A上的传递关系V28矩阵法：可传递关系的判定方法的证明）a（a）a（a）a（a）a（abnjin2ji21ji1kjikn1kij此处为布尔加运算符1)11,101,110,00(0方法1：若AR=（aij），B=AR2=ARAR=（bij），(bij=1则R可传递aij=1)证明设R可传递，且bij=1，即部分的证明）（1）a（a）a（a）a（a）a（abnjin2ji21ji1kjikn1kij则存在k,使aikakj=1,故aik=akj=1故(ai,ak)∈R且(ak,aj)∈R,则(ai,aj)∈R故aij=129部分的证明）（假设R不可传递,则存在ai,ak,aj使得(ai,ak)∈R且(ak,aj)∈R,但(ai,aj)∈R1）a（a）a（a）a（a）a（abnjin2ji21ji1kjikn1kij则aik=1,akj=1,aij=0,故有但这与(bij=1aij=1)相矛盾！(bij=1aij=1)成立。已知条件故R是可传递的。30方法2：对于关系矩阵AR中的每一个aij=1作如下操作：将AR中的第j行元素对应布尔加到第i行元素上，若操作后矩阵均无变化，则R是可传递的；否则，R不是可传递的。证明：若所有操作后矩阵均无变化。RAaiaj且设(aj,ak)∈R且不妨设kiaj1ak1aik=1设(ai,aj)∈R且不妨设ijaij=ajk=主对角线若aik=0,aik=0第k列元素对应布尔加到第i行元素第k列元素,第i行元素第k列元素为1,操作后矩阵发生了变化,则将AR中的第j行故aik=1,即(ai,ak)∈R,1故R是可传递的.两数不等矛盾。31从面的证明易见，若存在某一操作，使矩阵发生了变化，只能出现在下面的情形：即存在aij=1和ajk=1,但aik=0故(ai,aj)∈R且(aj,ak)∈R，但(ai,ak)∈R故R不是可传递的。32二元关系的性质（对应于关系图）（1）自反关系：每个顶点都有自回路:（2）反自反关系：每个顶点都没有自回路:（3）对称关系：任意两个顶点间或没有边，或有两条相向边:aiai×▼aiaj▼或▼aiaj▼××33（5）传递关系：若ai到ak有边,ak到aj有边则ai到aj必有边。（4）反对称关系：任二顶点至多只有一条有向边；思考它们的关系矩阵又有什么特点？▼aiaj▼××或▼aiaj▼×▼▼aiakaj▼▼