四章节二元关系.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=, ,仅是对称的和反自反的; 则是传递的和对称
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 章节 二元关系
链接地址:https://www.31doc.com/p-3195530.html