第2章二元关系.

1第二章二元关系§1二元关系及其表示形式§2二元关系的基本类型与判定方法§3等价关系、相容关系和偏序关系§4复合关系、逆关系和关系的闭包运算2§2.1二元关系及其表示形式本节要求掌握的知识点：1、序言：何谓关系？多样性？2、笛卡尔乘积：概念、求法。3、二元关系的定义4、二元关系的3（+1）种表示方法3[相关]:按照某种规则，确定二个对象或多个对象之间有关系，称这二个对象或多个对象是相关的。注意:相关性与指定的规则有关。(1)扑克牌中的方块ｋ与梅花ｋ同花关系：不相关；同点关系：相关(2)父子二人同辈关系：不相关；2.1.1、序言：关系（相关）4注：二元关系：二个对象之间的关系多元关系：多个对象之间的关系多元关系常化成二元关系来研究无序的二元关系：方块ｋ与梅花ｋ，谁在前，谁在后都还是同点的。有序的二元关系：父子关系，不能交换父与子的次序又如:（1）ａ＋ｂ＝偶数，ａ与ｂ是无序的用［ａ，ｂ］表示无序对（2）ａ≤ｂ，ａ与ｂ是有序的二元关系，叫作ａ相关于ｂ，记成ａｒｂ，用（ａ，ｂ）表示有序对（3）无序的二元关系可用有序的二元关系表示即（ａ，ｂ）与（ｂ，ａ）都属于这种二元关系52.1.2、集合的笛卡儿乘积•[有序对]：设有二个集合Ａ与Ｂ，Ａ中任取元素ａ，Ｂ中任取元素ｂ，ａ与ｂ建立一种对应关系，记为（ａ，ｂ），总是把Ａ中元素写在前面，Ｂ中元素写在后面，称（ａ，ｂ）为有序对。6有序对的集合｛（ａ，ｂ）｜ａ∈Ａ，b∈Ｂ｝称为Ａ对Ｂ的直交积，记为Ａ×Ｂ，又称叉积，笛卡儿（Descartes）乘积。注：Ａ×Ｂ≠Ｂ×Ａ，不满足交换律，也不存在结合律！笛卡儿积满足分配律：（对∪，∩，－，⊕）（１）Ａ×（Ｂ∪Ｃ）＝（Ａ×Ｂ）∪（Ａ×Ｃ）（２）（Ｂ∩Ｃ）×Ａ＝（Ｂ×Ａ）∩（Ｃ×Ａ）（３）（Ｂ⊕Ｃ）×Ａ＝（Ｂ×Ａ）⊕（Ｃ×Ａ）（４）（Ａ－Ｂ）×Ｃ＝（Ａ×Ｃ）－（Ｂ×Ｃ）7（４）的证明：对（ｘ，ｙ）∈（Ａ－Ｂ）×Ｃｘ∈Ａ－Ｂ且ｙ∈Ｃｘ∈Ａ，ｙ∈Ｃ，ｘＢ（ｘ，ｙ）∈Ａ×Ｃ，（ｘ，ｙ）Ｂ×Ｃ（ｘ，ｙ）∈（Ａ×Ｃ）－（Ｂ×Ｃ）即得（Ａ－Ｂ）×Ｃ（Ａ×Ｃ）－（Ｂ×Ｃ）其次，对（ｘ，ｙ）∈（Ａ×Ｃ）－（Ｂ×Ｃ）（ｘ，ｙ）∈Ａ×Ｃ而（ｘ，ｙ）（Ｂ×Ｃ）ｘ∈Ａ，ｙ∈Ｃ而ｘＢｘ∈Ａ－Ｂ，ｙ∈Ｃ（ｘ，ｙ）∈（Ａ－Ｂ）×Ｃ即得（Ａ×Ｃ）－（Ｂ×Ｃ）（Ａ－Ｂ）×Ｃ因此，（Ａ－Ｂ）×Ｃ＝（Ａ×Ｃ）－（Ｂ×Ｃ）8Ａ×Ｂ的几何意义：设Ａ＝［ａ，ｂ］，Ｂ＝［ｃ，ｄ］，均为实闭区间则有序对（ｅ，ｆ），ｅ∈Ａ，ｆ∈Ｂ，是平面上一个点（1）Ａ×Ｂ表示矩形区域［ａ≤ｘ≤ｂ，ｃ≤ｙ≤ｄ］（2）Ｂ×Ａ应为矩形区域［ｃ≤ｘ≤ｄ，ａ≤ｙ≤ｂ］注：（1）当且仅当Ａ＝Ｂ时Ａ×Ｂ＝Ｂ×Ａ，是正方形区域（2）由于Ａ×Ｂ也是集合，它应满足集合的一切性质9按照某种规定，定义了一个有序对（ａ，ｂ）的集合Ｒ，其中ａ∈Ａ，ｂ∈Ｂ，称Ｒ为Ａ到Ｂ的一个二元关系。(显然RA×B，即：A×B的任意一个子集合都是A到B的一个二元关系！)注意:二元关系是指满足某规律的有序对的全体。例：Ｒ＝{（ａ,ｂ）｜ａ∈Ａ,ｂ∈Ｂ,ａRｂ},其中ａRｂ读作ａ相关于ｂ。二元关系的定义10二元关系的前域和值域：若R是A到B的二元关系前域：domR={x|（x，y）∈R}值域：ranR={y|（x，y）∈R}空关系和全域关系：（其他一般的二元关系？？）空关系：Φ全域关系：A×B当Ａ＝Ｂ时，Ｒ是Ａ到Ａ的二元关系，称为Ａ上的二元关系。（A到A的二元关系）•例：Ｒ＝｛（ａ，ｂ）｜ａ|ｂ，ａ，ｂ∈Ｎ｝是自然数集Ｎ上的二元关系。（称为“整除关系”）112.1.3二元关系的几种表示方法[二元关系的表示]：因为，二元关系本身也是集合，也可用穷举法，描述法来表示，还可用表格、图示、矩阵法表示。例如：Ａ＝｛张三，李四，王五，赵六｝Ｂ＝｛１００米，跳高，铅球，足球，跨栏｝穷举法表示：Ｒ＝｛（张三，铅球），（张三，足球），（李四，１００米），（李四，跳高），（王五，跨栏），（赵六，１００米）｝是运动会的报名表。12**二元关系的表示：（1）集合法(穷举法、描述法)Ｒ＝｛（张三，铅球），（张三，足球），（李四，１００米），（李四，跳高），（王五，跨栏），（赵六，１００米）｝是运动会的报名表，13（2）表格法用表格表示一目了然14（3）图示法用字母数字来代替这些元素Ａ＝{a，b，c，d}，Ｂ＝{1，2，3，4，5}关系图，直观！Ｒ＝｛(a,3),(a,4),(b,１),(b,2),（c,5),（d,1）｝15（4）矩阵法：把Ａ，Ｂ集合内元素排好序:16若Ｒ＝｛（ａ，ａ）｜ａ∈Ａ｝，称Ｒ为恒等关系，常用IA表示。说明：对于一个给定的有限集合，其上的恒等关系IA是唯一确定的。而且，恒等关系一定是A上的。例：A={1，2，3，4}上的恒等关系为：IA={(1,1),(2,2),(3,3),(4,4)}17讨论与思考•1、什么叫二元关系？它与子集合、幂集合、笛卡儿乘积的关系？•[例]|A|=4，|B|=5，问：A×B有几个元素（即：有几个有序数对）？A到B可以定义多少种互不相同的二元关系？•2、二元关系各种表示方法的优缺点及其适应场合？18作业（p24)7、12、13、1419§2.2二元关系的基本类型与判定本节要求掌握的知识点:1、二元关系的5种基本类型：概念、特点2、可传递关系的判别方法20设Ｒ是Ａ上的二元关系，（1）若对任意a∈A，(a,a)∈Ｒ，则称Ｒ为A上的自反关系。自反的二元关系的关系矩阵对角元均为１，即ａii＝１（ｉ＝１，２，…，ｎ）。（2）若对任意a∈A,(a,a)Ｒ，则称Ｒ为A上的反自反关系。Ｒ的关系矩阵对角元素均为０，即ａii＝０（i=1，2，3，…，n）2.2.1二元关系的基本类型21自反关系任意(a,a)∈R反自反关系任意(a,a)R既不是自反的，也不是反自反的二元关系！注意：不是自反的不一定是反自反的，不是反自反的也不一定是自反的。自反性与反自及性是互斥的，但不互补。如下图：22对称关系与反对称关系若（ａ，ｂ）∈Ｒ，ａ≠ｂ则有（ｂ，ａ）∈Ｒ，则称这样的二元关系Ｒ为对称关系。此时Ｒ的相关矩阵是对称矩阵，即ａij＝ａji[若（a,b）∈Ｒ,ａ≠ｂ，则有（ｂ，ａ）Ｒ，则称这样的二元关系Ｒ为反对称关系。此时Ｒ的关系矩阵满足ａijａji＝0（ｉ≠ｊ）23对称关系若(a,b)∈R则(b,a)∈R（a≠b）反对称关系若(a,b)∈R则(b,a)R（a≠b）既不是对称的，也不是反对称的二元关系！注意：对称与反对称,既不互斥，又不互补。即:不是对称的，不一定是反对称的；反之依然。如下图：24（5）传递关系设R是A上的二元关系，若满足当(a，b)∈R且(b，c)∈Ｒ时，有(a，c)∈Ｒ，则称这样的Ｒ为A上传递关系。[例]:若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×A25二元关系的性质：对应于关系图，有：（1）自反关系：每个顶点都有自回路，（2）反自反关系：每个顶点都没有自回路；（3）对称关系：任意两个顶点间或没有边，或有两条相向边；（4）反对称关系：任二顶点至多只有一条有向边；（5）传递关系：若ｘ到ｙ有边，ｙ到ｚ有边，则ｘ到ｚ必有边。[思考]那么，它们的关系矩阵又有什么特点？26例１：Ｒ1＝｛（ａ，ｂ）｜ａ≤ｂ，ａ，ｂ∈Ｎ｝是自反的，rii=1;不是对称的，(1,2)∈R1,而(2,1)R1是反对称的，是传递的。注：将≤改为＜，则无自反性，且是反自反的。例２：Ｒ2＝｛（ａ，ｂ）｜ａ整除ｂ，ａ，ｂ∈Ｎ｝是自反的，不是对称的，是反对称的，是可传递的。例３：Ｒ3＝｛（Ｓ1，Ｓ2）｜Ｓ1Ｓ2，Ｓ1，Ｓ2∈Ｐ(Ｓ)｝.其中Ｐ(Ｓ)是Ｓ的幂集。Ｒ3是自反的，不是对称的，是反对称的，是传递的。注：若改为，则无自反性。27例４：Ｒ4＝{(a,b)|a+b=偶数，a,ｂ∈Ｎ｝Ｒ4是自反的，对称的，传递的，因ａ＋ｂ＝偶，ｂ＋ｃ＝偶，则０＜ａ＋ｃ＝（ａ＋ｂ）＋（ｂ＋ｃ）－２ｂ＝偶数。所以,Ｒ4是传递的!例５：Ｒ5＝｛(a,ｂ)｜ａ,b互素，ａ，b∈Ｎ｝Ｒ5是对称的，但不是自反的，也无传递性。282.2.2可传递关系的判定方法•1）定义法：验证：若（a，b）∈R且（b，c）∈Ｒ是否都有（a，c）∈Ｒ。有一个例外就不是！•2）矩阵法：•方法1：若AR=（aij），B=A2=（bij），则R可传递当且仅当bij=1时必有aij=1。其中•方法2：对于关系矩阵AR中的每一个aij=1作如下操作：将AR中的第j行元素对应加（布尔加）到第i行元素上，若操作后矩阵无变化，则R是可传递的；否则，R不是可传递的。）（kjiknkijaab1例见教材P30(例2.6，2.7，2.8）29作业(p32)1、3、5、630§2.3等价关系、相容关系和偏序关系本节要求掌握的知识点：1、等价关系的概念、等价类、集合划分的概念，商集，等价关系与集合划分的相互确定。2、相容关系的概念、相容类/最大相容类、覆盖/完全覆盖，相容关系与完全覆盖的相互确定。3、偏序关系的概念、盖住/盖住元素、哈斯图及其画法、极大/小元、最大/最小元、上/下界、上/下确界、链/反链、半/全序集。312.3.1等价关系Ａ上的二元关系Ｒ,如果Ｒ是(1)自反的；(2)对称的；(3)传递的，则称Ｒ为（A上的）等价关系,若(ａ,ｂ)∈Ｒ则称ａ与ｂ等价，记作aRb(或ａ～ｂ）。322.3.2等价关系的特征2、等价关系的矩阵表示按等价关系来调整有限集中元素的顺序可使等价关系的矩阵表示的对角线上有若干个小方阵，这些小方正的元素都为11000000010000000110000011000000011100001110000111例如1、等价关系的表格及图形表示（p34，p35)332.3.3等价类和商集1、等价类:若R是A上的等价关系，a∈A，由Ａ中的所有与a等价的元素构成的集合，称为a的等价类。a的等价类记为[a]R，即[a]R={x|x∈A且aRx}注：等价关系Ｒ把Ａ的元素分为若干类，各类之间没有公共元素。34把集合Ａ分为若干非空子集Ａ1,Ａ2,…An满足：（1）当ｉ≠ｊ时,Ａi∩Ａj＝（2）ａ∈A，ｉ，使ａ∈Ａi（ｉ=1，2，…，n）,即:niiAA1则集合Pr(Ａ)＝{Ａ1,Ａ2,…,Ａn}称为Ａ的一个划分。2.3.4集合的划分35定理1：Ａ上的等价关系Ｒ确定了A的一种划分;反之,给定了集合Ａ的任一种划分，也总可以找到Ａ上的一个等价关系。注：（１）Pr（Ａ）（２）当且仅当Ａ＝Pr(Ａ）＝，（３）Ａ非空时Pr（Ａ）P（Ａ）P（Ａ）（Ａ的幂集）时，｝P（Ａ）＝｛}36例１：Ａ＝｛５２张扑克｝Ｒ1＝｛（ａ，ｂ）｜扑克ａ与ｂ同花｝Ｒ2＝｛（ａ，ｂ）｜扑克ａ与ｂ同点｝则:Ｒ1把Ａ分为四类同花类，Ｒ2把Ａ分为１３类同点类。例２：设Ａ＝｛０，１，２，３，４，５｝Ｒ＝｛（０，０），（１，１），（２，２），（３，３），（１，２），（１，３），（２，１），（２，３），（３，１），（３，２），（４，４），（４，５），（５，４），（５，５）｝则Ｒ是等价关系37Ｒ是等价关系，但不直观，用关系图表示。三个不连通的图二元关系R是自反的，对称的，传递的，且把Ａ分成了三个等价类，A/R＝｛｛０｝，｛１，２，３｝，｛４，５｝｝38商集的元素个数（即Ａ在Ｒ下的等价类个数）称为Ｒ的秩.2、等价关系R将A分成若干等价类，每个类选个代表组成新的集合称为A关于R的商集，表示为A/R。即:以集合A上的等价关系R确定的所有互不相同的等价类作为元素而构成的集合,称为A关于等价关系R的商集.例：在上例中A/R＝｛[０]R，[１]R，[４]R｝39例:设A＝{a,b,c,d}，给定π1,π2,π3,π4,π5,π6,如下：π1={{a,b,c},{d}}π2={{a,b},{c},{d}}π3={{a},{a,b,c,