集合论1 3图论3 51第三章.pdf

第三章 关 系 1. 映射是关系的一种特例 映射反映的是事物之间的单值的依赖关系，而 事物之间不仅仅是单值依赖关系，大部分都是多值 的依赖关系。对于这种多值的依赖关系，可以用 “关系”这个概念来描述。因此映射是关系的一种 特殊情况。 2.在这里，所研究的关系主要是二元关系，即两个 对象之间的关系，以后就不在特殊说明了。 3. 内容 关系概念的数学定义及几种等价的定义； 关系的几种特殊性质 二元关系的运算：合成运算、闭包运算、逆关系 二元关系的表示：关系矩阵、关系图 具有几种特殊性质的关系：等价关系、偏序关系 4.关系的应用 域(集合)-属性的取值范围。(每一列就是一个属性) 每一行是一个记录，记录的集合是一个(二维)表， 也就是一个关系。 表与表之间的连接就是关系的合成。 文化程度 单位 婚否 工资 男 25 学士 理学院 否 4000 男 27 航天院 否 5000 男 31 博士 计算机 是 8000 男 32 博士 建筑院 是 9000 A B C D E F G §1 关系的概念 1.1 背景 提起关系，我们就会想到一些具体的关系。 父子、母子、兄弟、姐妹、同学、朋友关系等等。 国家之间的 、贸易关系等等。 整数之间的大于、小于、相等关系等等。 矩阵之间的相似、对称、合同关系等等。 这些都是一些具体的关系，它们都涉及到一些具 体的事物和某种性质。因此关系是事物之间的联系， 至少指两个事物并且有一定的顺序。例如：父子关系、 大小关系等。 前面那些具体关系都涉及两个事物，它们都是二 元关系。以后都是以研究二元关系为主。 1.2 关系的定义 例：同学关系 定义1 设X，Y是两个集合，一个从X ×Y到 ｛是,否｝ 的映射R (R:X ×Y→{是,否})，称为X到Y的一个二 元关系。 （或X与Y间的 二元关系） 若X＝Y，则称R为X上的二元关系。 对于(x,y)∈X×Y，在R下的象为 “是”，则称x与y 符合关系，记为xRy或(x,y)∈R。 对于(x,y)∈X×Y，在R下的象为 “否”，则称x与y 没有或不符合关系，记为(x,y)∉ R。 说明: 1.关系不是单值对应关系，而是多值对应关系。 2.X与Y中可能都有空闲点。 3.为了便于计算机处理，0→否，1→是。 R:X×Y→{0,1}，于是R是X ×Y子集的特征函数。 Ch(X×Y)~2X×Y 关系R就是X ×Y的子集。 定义2 设X，Y是两个集合，X ×Y的任意子集R称为从X 到Y的一个二元关系。(R X ×Y) 若X＝Y，则称R为X上的二元关系。(R X ×X) 说明： (1)由定义2可知,X×Y的任一子集R都称为X到Y的二 元关系;共有2|X||Y|个二元关系。 (2)φ、X ×Y X ×Y，称X ×Y为X到Y的全关系，空集 φ为X到Y的空关系。 恒等关系是一个重要关系。 定义3 集合{(x,x)|x∈X}称为X上的恒等关系，或相 等关系。记为I ，即I={(x,x)|x∈X}。 X X 例：X={1,2,3},Y＝{a,b,c}，则 R1=X×Y={(1,a),(1,b),(1,c),(2,a),(2,b),(2,c), (3,a),(3,b),(3,c)} 全关系 R2=φ