【教学课件】第四章二元关系.ppt

第四章 二元关系,4.1 二元关系及其表示法4.1.1 序偶与笛卡尔积定义4.1：由两个元素x和y按一定的次序组成的二元组称为有序对或序偶(Ordered)，记作，其中x是它的第一元素，y是它的第二元素。性质4.1：(1)：=当且仅当x=y；(2)：=当且仅当x=u,y=v;例如：平面上的坐标，x,y R；等都是序偶。,4.1 二元关系及其表示法,定义4.2：设A，B是两个集合，称集合 为集合A与B的笛卡尔积(Descartes Product)。例：设A=1,2；B=a,b则A B=，；B A=，。性质4.2：(1).|A B|=|A|B|(A,B为有限集合)；(2).；(3).不适合交换律，即AB BA(除非A，B=或A=B)；(4).不适合结合律，(AB)C A(BC)(除非)；(5).对和运算满足分配律，,4.1 二元关系及其表示法,证明：(6).，且当 或 时，逆命题成立。,4.1 二元关系及其表示法,定义4.3：一个有序n(n2)元组是一个有序对，它的第一个元素为有序的n-1元组，第二个元素为，记为 即：；当且仅当n维空间中的点M的坐标 为有序的n元组。定义4.4：设 为n个集合(n 2)，称集合 为n维卡氏积或n阶笛卡尔积，记作，当 时简记为。,4.1 二元关系及其表示法,4.1.2 二元关系定义4.5：若集合F中的全体元素为有序的n(n2)元组，则称F为n元关系，特别地，当n=2时，称F为二元关系，简称关系。对于二元关系F，若，常记作，反之；规定 为n元空关系，也是二元空关系，简称空关系。定义4.6：设A，B为两集合，AB的集合子集R称为A到B的二元关系，特别地，当A=B时，称R为A上的二元关系。例：A=a,b，B=c，则AB的子集有，,，,4.1 二元关系及其表示法,A到B上的全部二元关系；而，为B上的二元关系。一般来说，若|A|=m，|B|=n，A到B上的二元关系共有 个，A上的共有 个二元关系；特殊的二元关系：(1).空关系；(2).全域关系：；(3).恒等关系：。,4.1 二元关系及其表示法,定义4.7：设R为二元关系，则(1).为R的定义域；(2).为R的值域；(3).为R的域。一般地，若R是A到B上的二元关系，则有。例4-1：设A=1,2,3,4,5,6，B=a,b,c,d，则R=，那么domR=2,3,4,6，ranR=a,b,c。,4.1 二元关系及其表示法,4.1.2 关系的表示1.集合表示法 由于关系也是一种特殊的集合，所以可以用集合的两种基本的表示方法(枚举法，描述法)来表示关系；如：设A=2，B=3，则A到B上的有关系R=；集合N上的“小于等于”关系：R=|(x,y)N(x y)。2.关系图法定义4.8：设集合A=到B=上的二元关系R，以集合A，B中的元素为顶点，在图中用“”表示顶点，若 则可自顶点 向顶点 引有向边，其箭头指向，用这种方法画出的图称为关系图(Graph of Relation)。,4.1 二元关系及其表示法,例4-2：求集合A=1,2,3,4的恒等关系，空关系，全关系和小于关系的关系图。3.关系矩阵定义4.9：设，那么R的关系矩阵 为一mn矩阵，它的第i，j分量 只取0或1，且,4.2 关系的运算,1.关系的交，并，补，差运算定义4.10：设R和S为A到B的二元关系，其并，交，补，差运算定义如下：例4-3：设A=1,2,3,4，若R=|(x-y)/2是整数，x,y A，S=|(x-y)/3是正整数，x,y A，求RS，RS，S-R，R，R S。解：R=，,4.2 关系的运算,S=，RS=，；RS=；S-R=S=；R=AA-R=，；R S=(RS)-(RS)=RS.关系的补运算是对全关系而言的；关系的并，交，差，补的矩阵可用如下方法求取：,4.2 关系的运算,2.关系的逆运算由于关系是序偶的集合，除了集合的一般运算外，还有一些特有的运算。定义4.11：设R是A到B的关系，R的逆关系或逆是B到A的关系，记为，定义为：显然对任意，有；为R的关系矩阵，则.例：；A=a,b,c,d，B=1,2,3，R=，=，。,4.2 关系的运算,定理4.1：设R和S都是A到B上的二元关系，那么,4.2 关系的运算,3.关系的复合运算定义4.12：设R，S为二元关系，则R与S的复合关系 定义为：，其中“”为复合运算，也记为。例：设R表示父子关系，则 表示祖孙关系。例4-4：设集合A=0,1,2,3,4，R，S均为A上的二元关系，且R=|x+y=4=，S=|y-x=1=，；求一般地，,4.2 关系的运算,定理4.2：设F，G，H为任意二元关系，则定理4.3：设R为A上的关系，则定理4.4：设F，G，H为任意二元关系，则,4.2 关系的运算,4.关系的幂运算定义4.13：设R是集合A上的二元关系，则R的n次幂 定义为：例4-5：设A=0,1,2,3,4，R=，。则=，；=，；=，=,4.2 关系的运算,定理4.5：设R为A上的二元关系，m，n为自然数，则证(4)：若n=0时，则有 假设n=k时，有，则n=k+1时，有 命题成立。定理4.6：设集合A的基数为n，R是A上的二元关系，那么存在自然数i，j使得证明：我们知道，当|A|=n时，A上的二元关系共计 个，令k=，因此在 这k+1个关,4.2 关系的运算,系中，至少有两个是相同的(鸽巢原理)，即有定理4.7：设A是有限集合，且|A|=n，R是A上的二元关系，则证明：显然，下面证：。而，为此，只要证明对任意的kn，有 即可。对任意的，则由“”的定义知：存在，使得：,4.2 关系的运算,由于|A|=n，所以由鸽巢原理；k+1个元素 中至少有两个元素相同，不妨设为，则可在 中删去 后仍有由关系的复合运算得：，其中，此时：若，则；若，则重复上述做法，最终总能找到，使得，即有，由此有，由k的任意性，,4.2 关系的运算,5：集合在关系下的像定义4.14：设R为二元关系，A是集合(1)：R在A上的限制 定义为：(2)：A在R下的像RA定义为RA=ran()。例：R=，则：Ra=，；Ra=;Ra,a=R；Ra=b,a；Ra,a=b,a,a,a；,4.2 关系的运算,定理4.8：设F为关系，A，B为集合，则例4-6：设，A=0,1,2，B=0,-1,-2。(1)求RAB和RARB；(2)求RA-RB和RA-B。解(1)：RAB=R0=0；RARB=0,1,20,1,2=0,1,2；(2)：RA-RB=0,1,2-0,1,2=；RA-B=R1,2=1,2,4.3 关系的性质,我们在研究关系的性质时，可以假定关系是某一非空集合上的二元关系，这一假设不失一般性。因此任一A到B上的关系R，即，而，所以关系R总可以看成是AB 上的关系，它与原关系R具有完全相同的序偶，对它的讨论代替对R的讨论无损于问题的本质1.关系的性质定义4.15：设R是A上的二元关系，即，则(1)若，则称R是自反的(Reflexive)；(2)若，则称R是反自反的(Irreflexive)；,4.3 关系的性质,(3)若，则称R是对称的(Symmetric)(4)若，则称R是反对称的(Antisymmetric)(5)若，则称R是传递的(Transitive)例4-7：设A=a,b,c,d(1):R=，是自反的；S=，是反自反的；T=,既不是自反的也不是反自反的；,4.3 关系的性质,在关系图上：关系R是自反的，当且仅当其关系图中的每个节点都有环，关系R是反自反的，当且仅当其关系图中的每个节点上都无环；在关系矩阵上：关系R是自反的，当且仅当其关系矩阵的主对角线上全为1，关系R是反自反的，当且仅当其关系矩阵的主对角线上全为0。例4-8：设A=a,b,c,4.3 关系的性质,关系图上：关系R是对称的当且仅当其关系图中，任何一对节点之间，要么有方向相反的两条边，要么无任何边；关系R是反对称的当且仅当其关系图中，任何一对节点之间，至多有一条边；关系矩阵上：关系R是对称的当且仅当其关系矩阵是对称矩阵；关系R是反对称的当且仅当其关系矩阵为反对称矩阵。例4-9：设A=a,b,c,d,4.3 关系的性质,关系图上：关系R是传递的当且仅当其关系图中，任何三个节点x,y,z(可相同)之间，若从x到y，y到z均有一条边，则从x到z一定有一条边存在；关系矩阵上：关系R是传递当且仅当其关系矩阵中，对任意2.利用集合运算来判断关系的性质定理4.9：设R是集合A上的二元关系，则,4.3 关系的性质,3.关系性质的保守性定理4.10：设R，S是A上的二元关系，则例4-10：设R=，S=，是定义在A=a,b,c上的两个二元关系。,4.3 关系的性质,显然R，S是反自反的，反对称的，传递的，则 也是反自反的，反对称的，传递的；也具备上述的一切性质；(3)RS=,仅是对称的和反自反的；则是传递的和对称的。,4.4 关系的闭包,关系的限制与扩充：对于任何一个具备某种性质(如自反、对称、传递)的关系来说，在理论研究与应用上都十分重要，但遗憾的是，许多我们要研究的关系并不具有我们所希望的良好性质。因此，我们往往要在给定的关系中删去一些或添加一些元素，以改变原有关系的性质，即所谓的关系的限制与扩充。关系的闭包则是关系的扩充。定义4.16：设R是定义在A上的二元关系，若存在满足：(1)是自反的(对称的或传递的)；(2).；(3)对R的任何扩充 是自反的(对称的或传递的)，则。一般将R的自反、对称、传递闭包记作r(R)，s(R)，t(R)。,4.4 关系的闭包,例：定义在N上的“，是定义在A上的二元关系，求r(R)，s(R)，t(R)并画出R，r(R)，s(R)，t(R)的关系图，关系矩阵。解：r(R)=,;s(R)=,;t(R)=,;,4.4 关系的闭包,利用关系图，关系矩阵求闭包的方法：(1).求一个关系的自反闭包，即将图中所有的无环节点加上环，矩阵中的对角线上的值全定义为1；(2).求一个关系的对称闭包，则在图中，任何一对节点之间，若仅存在一条边，则加一条反方向的边；矩阵中则为：若，则令，即；(3).求一个关系的传递闭包，则在图中，对任意节点a，b，c，若a到b有一条边，同时b到c也有一条边，则从a到c必增加一条边(当a到c无边时)，在矩阵中，若。,4.4 关系的闭包,定理4.11：设R是A上的二元关系，则定理4.12：设R是集合A上的关系，则定理4.14：设R是集合A上的关系，则,4.4 关系的闭包,定义4.17：(1)集合A上的关系R的自反对称闭包定义为rs(R)=r(s(R);(2)集合A上的关系R的自反传递闭包定义为rt(R)=r(t(R);(3)集合A上的关系R的对称传递闭包定义为st(R)=s(t(R);类似的，可有sr(R)，tr(R)，ts(R)。定理4.15：设R是集合A上的关系，则,4.5 等价关系与划分,：集合和划分定义4.18：设A是一个非空集合，是A的任意n个非空子集，如果 满足：则称集合 为集合A的一个划分(Partition)，而 叫做这个划分的块或类。例如：(1)构成集合U的一个划分；(2)构成了U上的一个划分。,4.5 等价关系与划分,：等价关系定义4.19：设R为非空集合A上的关系，如果R是自反的，对称的，传递的，则称R为A上的等价关系(Equivalent Relation)。若，称x等价于y,记作xy。例：(1)一群人，同姓，同年龄，同性别都是等价关系，朋友，同学关系不是等价关系：不传递；(2)都是A上的等价关系；(3)三角形“相似”，“全等”都是等价关系；(4)幂集上定义的 关系，整数集上定义的不是等价关系，不对称。,4.5 等价关系与划分,例4-12：设m为正整数，整数集合上的关系 证明关系R是等价关系。证：(1)对任意，有 R自反；(2)对任意，若,则，即R对称；(3)对任意，若，即，而，R传递R是Z上的等价关系。,4.5 等价关系与划分,考察关系R和集合Z；R将Z分成了如下m个子集：这m个子集特点是：同一个子集中的元素之间都有关系R，不同子集的元素之间无关系R，每两个子集无公共元素，而所有子集的并正好为Z，构成了Z的一个划分。,4.5 等价关系与划分,：等价类与商集定义4.20：设R是非空集合A上的等价关系，对任意，称集合 为x关于R的等价类(Equivalence Class)，其中x称为 的生成元，由于 中的任何两个元素a，b均相互等价，一般记作ab。例4-13：设A=1,2,3,4,5,8，考虑R是A上的以3为模的同余关系，求其等价类。解：从例4-12知，R是一个等价关系，则,4.5 等价关系与划分,定理4.11：设R为非空集合A上的等价关系，则证：(1)，R是等价关系，则R自反，因此即(2),4.5 等价关系与划分,同理：(3)若，则存在，即：定义4.21：设R是集合A上的等价关系，由R确定的一切等价类的集合，称为集合A上关于R的商集(Quotient Set)，记为A/R，即,4.5 等价关系与划分,定理4.12：设R是非空集合A上的等价关系，则A上的关于R的商集A/R是A的一个划分，称之为由R导出的等价划分。证：由定理4.11知，命题成立。定理4.13：设(A)是非空集合A的一个划分，则A上的关系 是A上的等价关系，称之为由(A)所导出的等价关系。证明：(1)为A的一个划分，使得，即x和x同属于(A)的一个划分块，R是自反的；,4.5 等价关系与划分,(2)，则x和y同属于(A)的一个划分块，即y和x同属于一个划分块，R是对称的；(3)，则x，y同属于(A)的一个划分块，y，z同属于(A)的一个划分块，而由于不同划分块的交集为空，即x和z属于同一划分块，R是传递的；R为等价关系。若设，则,4.5 等价关系与划分,有定理4.12,4.13知，集合A上的等价关系与集合A的划分是一一对应的，因此可以说：划分与等价关系这两个不同的概念本质上是相同的，即是同一个概念的两种不同的表达方式。例4-14：设A=1,2,3，求A上的所有等价关系。解：先求A的划分：只有一个划分块的划分为1,2,3；具有2个划分块的划分为 1，2,3，2，1,3，3，1,2，具有3个划分块的划分为 1，2，3；相应的等价关系为：,4.5 等价关系与划分,例4-15：设R是集合A上的一个关系，对任意a，b，c A，若 那么称R为A上的循环关系。试证明R是A上的一个等价关系的充要条件是R是循环关系和自反关系。证明：必要性：若R是等价关系；(1)R等价=R自反(2)，R等价R对称，即R是循环关系；充分性：若R自反且循环：(1)自反性显然；(2)，R是自反，得，因R是循环的，即R是对称的；,4.5 等价关系与划分,(3)，则由R对称得，由R循环，R是传递的；R等价。,4.6 次序关系,在一些研究中，需要把研究的对象排出次序，因此，集合的元素之间还有一种重要关系，称为“先后次序”关系，即偏序关系。定义4.21：(1)设R为非空集合A上的关系，如果R是自反的，反对称的，传递的，则称R为A上的偏序关系(Partial Order relation)。记作“”,读作“小于等于”；(2)设R为非空集合A上的关系，如果R是反自反的，反对称的，传递的，则称R为A上的拟序关系(Quasi Order relation)。记作“”表示，读作“大于”。,4.6 次序关系,例：(1)集合A上的幂集(A)上定义的“”和“”分别是偏序关系和拟序关系；(2)实数集合R上定义的数的“小于等于”关系，“小于”关系，分别是偏序关系和拟序关系；(3)自然数集合N上定义的“整除”关系，也是一个偏序集合。定义4.22：设是一个偏序集，对，x y或y x，则称x与y是可比的(Comparable),若x与y是可比的，xy，且不存在，使得xzy，则称y覆盖(Overlay)x。,4.6 次序关系,例：(1)集合A=a，b，c，则偏序集中，a与a，b是可比的；a与b，c是不可比的；a，b覆盖a；a，b，c不覆盖a。(2)偏序集R，对，x与y都是可比的，但x不覆盖y，y也不覆盖x。(3)偏序集Z，对，x与y都是可比的，x覆盖x-1。(4)偏序集中，2与3不是可比的，2与6是可比的，并且6覆盖2,2与8可比，但8不覆盖2。,4.6 次序关系,：偏序集的哈斯图由于偏序关系本身具有自反，反对称，传递的性质，在用关系图来描述偏序关系且不引起混淆，可以对其进行简化，得到的图叫做偏序图或哈斯图(Hasse)。哈斯图的作图方法如下：(1):用小圆圈或点表示A中的元素，省掉关系图中的所有环(因自反性)；(2):对，若xy则将x画在y的下方，可省掉关系图中所有边的箭头；(3):对，若y覆盖x，则在x与y之间连条线，否则无线相连。,4.6 次序关系,按(1)，(2)，(3)所作成的图称为哈斯图。例4-16：设A=2,3,6,12,24,36，“”是A上的整除关系，画出其一般关系图和哈斯图。例4-17：设集合A=a，B=a，b，C=a，b，c分别画出集合A，B，C之幂集上定义的“”的哈斯图。,4.6 次序关系,：偏序集中的特殊元素定义4.23：设为偏序集，最小元与极小元不一样，最小元是B中最小的元素，它与B中其它元素都是可比的，而极小元不一定与B中的元素都可比，只要没有比它小的元素，它就是极小元；对于有穷集，极小元一定存在，但最小元不一定存在；,4.6 次序关系,如果最小元存在，最小元唯一，但极小元可以有多个；b是B的最小元b是B中的唯一极小元；反之，极大元亦然。定义4.24：设为偏序集，,4.6 次序关系,例4-18：设集合A=a，b，c，求偏序集 的子集的子集 的最大元，最小元，极大元，极小元，上界，下界，上确界，下确界。解：画图,4.6 次序关系,例4-19：设A=a，b，c，d，A上定义偏序集的哈斯图如图所示，求B=a，b和 C=c，d的最大元，最小元，极大元，极小元，上下 界，上下确界。解：,a,d,b,c,4.6 次序关系,上(下)界存在，并不一定存在最小上(下)界；b是B的最大元=b是B的极大元，上界，上确界；b是B的最小元=b是B的极小元，下界，下确界；a是B的上确界=a是B的最大元；a是B的下确界=a是B的最小元；若B存在上确界，则其上确界唯一；若B存在下确界，则其下确界唯一。,4.6 次序关系,：全序与良序定义4.25：设是一个偏序集，若对 x与y都是可比的，则称关系“”为全序关系(Total Order Relation)，或称线序关系，简称全序或线序，称为全序集或线序集或链。例：(1)集合A=a，b，c，上定义的关系=，是一个全序关系；(2)实数集合R上定义的“”是全序关系，是全序集。全序集中，任何两个元素可比，存在一个次序，其哈斯图为一链。,4.6 次序关系,定义4.26：设是一个偏序集，若A的任何一个非空子集有最小元，则称“”为良序关系(Well Order Relation)，简称良序，此时称为良序集。a，b有最小元，则a b或b a，良序关系是一个全序关系。“”是良序关系=“”是全序关系=“”是偏序关系；一般地，任何有限的全序集的每一个非空子集一定有最小元，所以，有限全序集一定是良序集，对与无穷的全序集则不一定。,