离散数学关系及其表示.pptVIP

第三章 集合与关系 3-5 关系及其表示 授课人：李朔 Email:chn.nj.ls@ 日常生活中，大家熟知一些常见关系，例：家庭集合，有父子关系、夫妻关系等。全校同学作为一个集合，有同班关系，同组关系。 在计算机科学中，在计算机逻辑设计中，应用了等价关系，相容关系。 在编译原理、关系数据库、数据结构中也有关系。 一、关系的概念 关系是一个基本概念，即多个客体间的某种联系。序偶可以表达这个概念。 P105 定义3-5.1 任意的序偶的集合确定了一个二元关系R，R中任一序偶x,y 可记作x,y ∈R或xRy。不在R中的任一序偶x,y 可记 x,y ∈R或xRy。 定义3-5.2 令R为二元关系，由x,y ∈R 的所有x组成的集合domR称为R有前域，即 使的所有y组成的集合ranR称作R的值域，即 R的前域和值域一起称作R的域，记作FLD R即 FLD R=domR∪ranR 例题1 P106 一、关系的概念 定义3-5.3 令X和Y是任意两个集合，直积X╳Y的子集R称作X到Y的关系。 例如：X到Y的关系R可用下图表示： 显然： 约定：X╳Y的两个平凡子集X╳Y和? ，分别称为从X到Y的全域关系和空关系。 一、关系的概念 考虑集合{2，3，5，9}上的小于关系“”，为了形象起见，我们用一条从i到j的有向线段表示关系“ij”. 一、关系的概念 当X=Y，关系R是X╳X的子集，这时称R为X上的二元关系。 通常A上不同二元关系的数目依赖于A的基数，若?A?=n（?A?表示A的元素数），则?A?A?= n2 。 对幂集，则有|P (A×A) |=2|A×A|=2 ，即A×A的子集有 2 个。所以具有n个元素的有限集A上有2 种二元关系。 例如 A={0, 1, 2}，则在A上可定义 =512个不同的关系。 P107 例题2 例题3 一、关系的概念 P107 定义3-5.4 设Ix是X是的二关系且满足Ix= ，则称Ix是X上的恒等关系。 例如： A={1，2，3}，IA={1,1,2,2,3,3} *关系是序偶的集合，同一域上的关系可以进行集合的所有运算，结果是一个关系。P107 例题4 P107 定理3-5.1 若Z和S是从集合X到集合Y的两个关系，则Z、S的并、交、差仍是X到Y的关系。 证明：因Z? X ? Y, S? X ? Y 故 Z?S ? X ? Y, Z?S ? X ? Y ?S=(X?Y-S)? X? Y Z-S=Z??S? X ? Y X到Y的关系R是X╳Y的子集，如果令X和Y为有限集，则二元关系R还可以用矩阵或图形表示。 二、关系矩阵和关系图 设给定的两个有限集合X={x1,x2,…,xm}，Y={y1,y2,…,yn}，R为从X到Y的一个二元关系。则对应于关系R有一个关系矩阵MR=[rij]mn，其中 (i=1,2,…，m；j=1,2,…，n) 设给定的两个有限集合X={x1,x2,…,xm}，Y={y1,y2,…,yn}，R为从X到Y的一个二元关系。在平面上作m个结点分别记作x1,x2,…,xm，然后另作n个结点分别记作y1,y2,…,yn。如果xi Ryi，则可自结点xi至结点yj处作一有向弧，其箭头指向yj ，如果xi Ryi ，则xi至yj处没有线段联结。 例：设A={a1,a2},B={b1,b2,b3},R={〈a1,b1〉,〈a2,b1〉,〈a1,b3〉,〈a2,b2〉},则其关系矩阵为： 二、关系矩阵和关系图 例如：设R={1,2,1,1,2,3,3,1,3,4,4,4}是X={1,2,3,4}上的关系，则其关系矩阵是： 其关系图是： 二、关系矩阵和关系图 例 设A=?a1,a2,a3,a4?，B=?b1,b2,b3?，R是A到B的二元关系，定义为： R=??a1,b1?,?a1,b3?,?a2,b2?,?a2,b3?,?a3,b1?,?a4,b1?,?a4,b2?? 写出R的关系矩阵。 解：R的关系矩阵为： 其关系图是： 二、关系矩阵和关系图 例 设A=?1,2,3,4?，R是A的二元关系，定义为： R=??1,1?,?1,2?,?2,1?,?3,2?,?3,1?,?4,3?,?4,2?,?4,1?? 写出A上二元关系R的关系矩阵。 解：R的关系矩阵为： 其关系图为： 二、关系矩阵和关系图 关系图主要表达结点与结点之间的邻接关系，故关系图中对结点位置和线的长短无关。 本课小结 关系，前域，值域，关系的