四章节二元关系.ppt

《四章节二元关系.ppt》由会员分享，可在线阅读，更多相关《四章节二元关系.ppt（56页珍藏版）》请在三一文库上搜索。

1、第四章 二元关系,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、)； (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 二元关

3、系 定义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). 全域

4、关系： ； (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)

5、 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：设

6、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的关系矩阵，则 . 例：

7、 ； 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 关系

8、的运算,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上的

9、二元关系，则 证明：显然 ，下面证： 。 而 ，为此，只要证明对任意的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=

10、; 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具有完

11、全相同的序偶，对它的讨论代替对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是自反的，当且仅当其关系图中的每

12、个节点都有环，关系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

13、是传递的当且仅当其关系图中，任何三个节点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=, ,仅是对称的和反自反的； 则是传递的和对称

14、的。,4.4 关系的闭包,关系的限制于扩充：对于任何一个具备某种性质(如自反、对称、传递)的关系来说，在理论研究与应用上都十分重要，但遗憾的是，许多我们要研究的关系并不具有我们所希望的良好性质。因此，我们往往要在给定的关系中删去一些或添加一些元素，以改变原有关系的性质，即所谓的关系的限制与扩充。 关系的闭包则是关系的扩充。 定义4.16：设R是定义在A上的二元关系，若存在满足：(1) 是自反的(对称的或传递的)；(2). ；(3)对R的任何扩充 是自反的(对称的或传递的)，则 。一般将R的自反、对称、传递闭包记作r(R)，s(R)，t(R)。,4.4 关系的闭包,例：定义在N上的“，是定义在A

15、上的二元关系，求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

16、.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.5.1：集合和划分 定义4.18：设A是一个非空集合， 是A的任意n个非空子集，如果 满足： 则称集合

17、 为集合A的一个划分(Partition)，而 叫做这个划分的块或类。 例如：(1) 构成集合U的一个划分； (2) 构成了U上的一个划分。,4.5 等价关系与划分,4.5.2：等价关系 定义4.19：设R为非空集合A上的关系，如果R是自反的，对称的，传递的，则称R为A上的等价关系(Equivalent Relation)。若 ，称x等价于y,记作xy。 例：(1)一群人，同姓，同年龄，同性别都是等价关系，朋友，同学关系不是等价关系：不传递； (2) 都是A上的等价关系； (3)三角形“相似”，“全等”都是等价关系； (4)幂集上定义的 关系，整数集上定义的不是等价关系，不对称。,4.5 等价

18、关系与划分,例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.5.3：等价类与商集 定义4.20：设R是非空集合A上的等价关系，对任意 ，称集合 为x关于R的等价类(Equivalence Clas

19、s)，其中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上的

20、等价关系，则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为等价关系。

21、若设 ，则,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是循环关系

22、和自反关系。 证明：必要性：若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)。记作“”,

23、读作“小于等于”； (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，且不存在 ，使得xyz，则称y覆盖(Overla

24、y)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 次序关系,4.6.2：偏序集的哈斯图 由于偏序关系本身具有自反，反对称，传递的性质，在用关系图来描述偏序关系且不引起混淆，可以对其进行简化，得到的图叫做偏序图或哈斯图(Hasse)。 哈斯图的作图方法如下： (1):用小

25、圆圈或点表示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.6.3：偏序集中的特殊元素 定义4.23：设为偏序集， 最小元与极小元不一样，最小元是B中最小的元素，它与B中其它

26、元素都是可比的，而极小元不一定与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的最大元，最小元，极大元 ，极小元，上下 界，上

27、下确界。 解：,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.6.4：全序与良序 定义4.25：设是一个偏序集，若对 x与y都是可比的，则称关系“”为全序关系(Total Order Relation)，或称线序关系，简称全序或线序，称为全序集或线序集或链。 例：(1)集合A=a，b，c，上定义的关系=，是一个全序关系； (2)实数集合R上定义的“”是全序关系， ,