二元关系介绍.ppt

《二元关系介绍.ppt》由会员分享，可在线阅读，更多相关《二元关系介绍.ppt（26页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1,4.1.4 关系的性质,一、自反性和反自反性 定义 设A是一个集合， R是A上的二元关系， （1）若aA，都有R，则称R是自反的，或称R具有自反性。 （2）若aA，都有R，则称R是反自反的，或称R具有反自反性。,2,设A=a,b,c,d，,例,R=,。,因为A中每个元素x，都有R，所以R是自反的。,R的关系图,R的关系矩阵,3,S=,。,例 (续1),S的关系图,S的关系矩阵,因为A中每个元素x，都有 S，所以S是反自反的。,4,T=,。,例 (续2),因为A中有元素b，使 T，所以T不是自反的；因为A中有元素a，使T，所以T不是反自反的。,T的关系图,T的关系矩阵,5,有关说明： （1）

2、注意定义中“任意”，“都”这两个词。 （2）如果R不是自反的，则R未必一定是反自反的。一个关系可能既不是自反的，也不是反自反的。 （3）表现在关系图上：关系R是自反的，当且仅当其关系图中每个结点都有环；关系R是反自反的，当且仅当其关系图中每个结点都无环。 （4）表现在关系矩阵上：关系R是自反的，当且仅当其关系矩阵的主对角线上全为1；关系R是反自反的当且仅当其关系矩阵的主对角线上全为0。,6,例1 R是Z上的整除关系，则R具有自反性。 证明： xN，x能整除x，R， R具有自反性。 例2 R是Z上的同余关系，则R具有自反性。 证明： xZ，(x-x)/k=0Z, x与x同余， R，R具有自反性。

3、 其它，关系，倍数关系，人与人的同名关系、集合的关系，均是自反的。,7,例3 Z上的大于关系是反自反关系。 证明：xZ，x不大于x，R， N上的大于关系是反自反的。 其他的如实数上的，关系,人与人的父子关系,均是反自反关系。,8,二、对称性 定义 设R是A上的关系，a,bA，如果R，则必有R，则称R是对称的，或称R具有对称性。 例如，A=1，2，3，4 R1，则R1是对称的； R2，则R2也是对称的； R3， 则R3不是对称的，因R，而R。,9,有关说明: 由对称性的定义可知，如果R是对称的，则当R时， 必有R。 对于像，这种序偶是否属于R对R的对称性没有影响。,R1的关系图,R1的关系矩阵,

4、是对称的,例 设A=a,b,c，,R1=,例 R是Z上的模5同余关系,则R是对称关系 ； 证明：R|x,yZ，(x-y)/5Z x,yZ，如果R， 则(x-y)/5 Z 所以， (y-x)/5 - (x-y)/5 Z R，故R具有对称性。,10,11,R3=,例 (续1),R4=,既不是对称的，也不是反对称的,R3的关系图,R3的关系矩阵,既是对称的，也是反对称的,R3的关系图,R3的关系矩阵,12,对称关系的关系矩阵和关系图的特点 1. 对称关系的关系矩阵是对称矩阵，即rijrji； 因为 rij1 R R rji1 一切i,j，rijrji=1 2. 对称关系的关系图的特点是任何两个不同的

5、结点之间，或者是一来一回两条边（弧），或者是没有边（弧）。而是否有自回路，对对称性没有影响。 显然,全域关系UA，空关系，恒等关系A，都是对称的。,13,三、反对称性 定义 如果R是A上的关系，a,bR如果R且R，则必有ab，称R是反对称的。 有关说明: 该定义的等价说法是： a,bA，如ab，R，则必有R。即两个不同点结点间不允许有两条边（弧）。 该定义的否命题说法并不成立。即“ab，R，则R”并不成立，即反对称关系的关系图允许两个不同点间没有弧。,14,例2 R是N上的整除关系,即 R|x,yN,y/xN, 显然，如果x能整除y，且xy，则y不能整除x。所以R是反对称的。,例1 设A=a,

6、b,c，R2=,R2的关系图,R2的关系矩阵,是反对称的,15,例3 A是某集合，R是(A)上的包含关系。 因u、v(A)，如uv，且uv，则必有v u, 所以，包含关系R是反对称的。 换一种理解，如果u,v(A)，有uv，vu，则必有uv。 集合A上的包含关系R是反对称的。 其它例如、关系，人与人的父子关系，领导与被领导关系均是反对称的。,16,反对称关系的关系矩阵和关系图特点 关系矩阵：R是反对称的，则其关系矩阵如果在非对角元上rij1，则在其对称位置上rji0，即rij和rji(ij)这两个数至多一个是1，但允许两个均为0。 关系图：任何两个不同的结点之间，至多有一条边（弧），或者没有边

7、（弧）。,17,四、传递性 定义 设R是A上的关系，a,b,cA，如果R，R，则必有R。则称R是传递的，或称R具有传递性。,设A=a,b,c,d，,R1=,是传递的,R1的关系图,R1的关系矩阵,18,设A=a,b,c,d，,例（续）,R2=,是传递的,R2的关系图,R2的关系矩阵,19,R3=,例 (续),R4=,不是传递的,R3的关系图,R3的关系矩阵,不是传递的,R3的关系图,R3的关系矩阵,20,表现在关系图上：关系R是传递的当且仅当其关系图中，任何三个结点x,y,z（可以相同）之间，若从x到y有一条边存在，从y到z有一条边存在，则从x到z一定有一条边存在。 表现在关系矩阵上：关系R是

8、传递的当且仅当其关系矩阵中，对任意i,j,k1,2,3,n，若rij=1且rjk=1，必有rik=1。,结论,21,例 整除关系DN是N上的传递关系。 证明：x,y,zN，如DN，DN，即x能整除y，且y能整除z，则必有x能整除z，即DN，所以整除关系具有传递性。 例 (A)上的包含关系，具有传递性。 因为若uv，vw，则必有uw。 例 实数集上的关系也具有传递性。 因为若xy，yz，必有xz。 其它如全域关系UA，空关系，恒关系A均是传递的。,关系性质的逻辑表示,设R是集合A上的二元关系， R是自反的,是永真的,R不是自反的,是永真的,R是反自反的,是永真的,R不是反自反的,是永真的,R是对

9、称的,是永真的,R不是对称的,是永真的,23,关系性质的逻辑表示(续),R是反对称的,R是传递的,是永真的,R不是传递的,是永真的,是永真的,R不是反对称的,是永真的,24,设A1,2,3,试判断如下图所示A上关系的性质：,图a)的关系是自反的、对称的、反对称的、传递的关系； 图b)的关系是具备反自反的、对称的、反对称的、传递的关系；,图c)的关系是具备对称的、反对称的、传递的关系； 图d)的关系是不具备任何的性质关系；,25,图e)的关系是具备自反的、对称的、传递的关系； 图f)的关系是具备反自反的、反对称的、传递的关系； 图g)的关系是具备反自反的、反对称的关系； 图h)的关系是具备反自反的、反对称的、传递的关系。,例,26,设A是任意的集合， A上的全关系AA是自反的、对称的、传递的关系； A上的空关系是反自反的、反对称的、对称的、传递的关系； A上的恒等关系IA是自反的、对称的、反对称的、传递的关系。,例,例 朋友关系是自反的、对称的、而非传递的关系； 父子关系是反自反的、反对称的、而非传递的关系.,