第四章-二元关系.ppt

第四章二元关系第四章二元关系4.1关系的基本概念4.2关系的性质4.3关系的表示4.4关系的运算4.5特殊关系4.1关系的基本概念定义：任一序偶的集合确定一个二元关系R，R中任一序偶x,y可记作x,y∈R或xRy，称为x与y有关系R。否则，记作或例R1={x,y|xy,x和y是实数}一、关系的定义一、关系的定义例：设集合A={a,b},B={2,5,8}一、关系的定义例：设集合A={2,3,5,9}，试给出集合A上的小于或等于关系，大于或等于关系。解：令集合A上的小于或等于关系为R1，大于或等于关系为R2，根据定义有：一、关系的定义定义：设且为n个任意集合，一、关系的定义例：令则称R1是N上的一元关系，R2是N上的二元关系，R3是N上的三元关系。二、关系的相等定义：设R1为X到Y上的二元关系，R2为A到B上的二元关系，如果：（1）X=A（2）Y=B（3）把R1和R2作为集合看，R1=R2。则称二元关系R1和R2相等，记作R1=R2二、关系的相等例：设R1为从Z到I+的二元关系，R2和R3都是I上的二元关系三、关系的定义域和值域关系R(从A到B的关系)的定义域(简称为域)定义为：关系R的值域定义为：三、关系的定义域和值域第四章二元关系4.1关系的基本概念4.2关系的性质4.3关系的表示4.4关系的运算4.5特殊关系4.2关系的性质定义：设R为A上的二元关系4.2关系的性质4.2关系的性质4.2关系的性质例1：考虑自然数集合上的普通相等关系“=”，大于关系“”和大于等于关系“”具有的性质。例:A={1,2,3},A上的关系:R1={1,11,22,1}R2={1,31,22,3}R3={1,13,3}R4={1,12,23,31,21,32,1}判断以上关系各有哪些性质。解：(1)既不是自反又不是反自反，是对称的，不是传递的。(2)反自反的，反对称的，传递的。(3)既不是自反又不是反自反的，既是对称又是反对称的，传递的。(4)是自反的，既不是对称又不是反对称的，不是传递的。自反与反自反不交，存在既不是自反又不是反自反的关系。对称与反对称相交，存在既是对称又是反对称的关系，也存在既不是对称也不是反对称的关系。4.2关系的性质集合的压缩和开拓定义：设R为集合A上的二元关系且，则称S上的二元关系为R在S上的压缩，记为，并称R为在A上的开拓。集合的压缩和开拓第四章二元关系4.1关系的基本概念4.2关系的性质4.3关系的表示4.4关系的运算4.5特殊关系4.3关系的表示定义：设A和B为任意的非空有限集，R为任意一个从A到B的二元关系。以中的每个元素为结点．对每个皆画一条从x到y的有向边，这样得到的一个图称为关系R的关系图。一、关系图例：设A={2,3,4,5,6},B={6,7,8,12}，从A到B的二元关系R为画出其关系图。一、关系图一、关系图如果关系图中每个结点上都有环，则R是自反的；如果关系图中每个结点上都没有环，则R是反自反的；如果关系图中两顶点间有边，必是一对方向相反的边，则R是对称的；如果关系图中两顶点间有边，必是一条有向边,则R是反对称的；如果关系图中顶点xi到xj有边，xj到xk有边，则xi到xk必有边，则R是可传递的。二、关系矩阵二、关系矩阵例：设A={1,2,3},B={a,b,c},R是A到B的二元关系，并且，试画出R的关系图，给出关系矩阵。二、关系矩阵二、关系矩阵如果关系矩阵主对角线上的记入值全为1，则R是自反的；如果主对角线上的记入值全为0，则R是反自反的；如果矩阵关于主对角线是对称的，则R是对称的；如果矩阵关于主对角线是反对称的，(亦即rij=1时则一定有rji=0),则R是反对称的；二、关系矩阵如果对于任意的i,j,k,rij=1并且rjk=1时一定有rik=1，则R是可传递的；如果存在i,j,k,rij=1并且rjk=1时，有rik不等于1，则R是不可传递的；第四章二元