第四章二元关系..ppt

第四章 二元关系 第四章 二元关系 4.1关系的基本概念 4.2关系的性质 4.3关系的表示 4.4关系的运算 4.5特殊关系 4.1关系的基本概念 定义：设 且 为n个任意集合， 一、关系的定义 例：令 则称R1是N上的一元关系，R2是N上的二元关系，R3是N上的三元关系。 一、关系的定义 例：设集合A={a,b},B={2,5,8} 一、关系的定义 例：设集合A={2,3,5,9}，试给出集合A上的小于或等于关系，大于或等于关系。 解：令集合A上的小于或等于关系为R1，大于或等于关系为R2，根据定义有： 二、关系的相等 定义：设R1为A1,A2,…,An间的n元关系，R2为B1, B2,…,Bm间的m元关系，如果： （1）n=m （2）若 ，则 （3）把R1和R2作为集合看，R1=R2。 则称n元关系R1和m元关系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：考虑自然数集合上的普通相等关系“=”，大于关系“”和大于等于关系“ ”具有的性质。 集合的压缩和开拓 定义：设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为 ，画出其关系图。 一、关系图 二、关系矩阵 二、关系矩阵 例：设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是不可传递的； 第四章 二元关系 4.1关系的基本概念 4.2关系的性质 4.3关系的表示 4.4关系的运算 4.5特殊关系 4.4关系的运算 注意：由于关系也是特殊的集合，因此集合的运算也适用于关系中。 设R1和R2是从A到B的二元关系，那么 ， ， 也是从A到B的二元关系，它们分别被称为二元关系R1和R2的交、并、差分和对称差分。 4.4关系的运算 4.4关系的运算 4.4.1关系的合成 4.4.2合成关系的矩阵表达和图解 4.4.3关系的求逆运算 4.4.4关系的闭包运算 4.4.1关系的合成 定义：设R是从X到Y的关系，S是从Y到Z的关系，于是可用R?S表示从X到Z的关系，通常称它是R和S的合成关系，用式子表示即是： 关系的合成 解：找出所有这样的偶对 ——对于某一个y来说，能有x+y=6和y-z=1，由上述的偶对就可构成从X到Z的关系R?S 。 关系的合成 关系的合成 注意：设是R从集合X到集合Y的关系，S是从集合Y到集合Z的关系，于是有： 如果R关系的值域与S关系的定义域的交集是个空集，则合成关系R?S也是个空关系； 若至少有一个序偶 ，其中笫二个成员是S中的某一个序偶的笫一个成员，则合成关系就是个非空关系。 对于合成关系R?S来说，它的定义域是集合X的子集，而它的值域则是Z的子集，事实上，它