第二单元 关系.pptVIP

第二章 关系 本章将研究集合内元素之间的关联以及集合之间元素的关联，这就是“关系” “关系”是很重要的基本数学概念，它在各数学领域中均有很大的作用，并且对研究计算机科学中许多问题都是很好的数学工具 2.1 关系的基本概念 定义2.1 从集合A到集合B的一个关系R是A与B的笛卡尔积A×B的一个子集 关系R中有序偶第一个客体所允许选取对象的集合称为关系R的定义域，记以D(R)，第二个客体所允许选取对象集合称为关系R的值域，记以C(R) 在特殊情况下，当D(R)=C(R)=M时，M为一集合，此时称为关系为M上的关系 例：实数集R上的“”关系可以定义为： = {(x,y) | x∈R, y∈R,且xy} 2.1 关系的基本概念 如果从X到Y不存在某种关系R，则称这种关系为空关系，如果从X的每个元素到Y的每个元素之间均具有某种关系，则称此关系为全关系. 从X到Y的全关系即X×Y. 定义2.2 由集合X1、X2、…、Xn所确定的的n元关系是X1×X2×…×Xn的一个子集 2.1 关系的基本概念 大型的计算机结构中或一个大型软件结构中所谓的内部逻辑关系复杂，所指的“逻辑关系”就是这里的“关系”，只要把这些结构内的关系搞清，则任何结构的“正确性”“可靠性”就迎刃而解了. 2.1 关系的基本概念 关系的图的表示法 一个集合X={x1,x2,…,xn}上的关系可用一关系图表示之.集合X中元素可用图中结点表示；关系R的有序偶(xi,xj)可用图中从结点xi到xj的有向边表示。 例： 2.2 关系的运算 关系的交、并、补、差 关系是特殊的集合 有关集合的交、并、补、差在关系中也适用，有关集合运算的一些公式在关系中也适用 2.2 关系的运算 复合运算 定义2.3 设R是一个从X到Y的关系，S是一个从Y到Z的关系，则R与S的复合关系： RoS={(x,z) | x∈X,z∈Z,至少存在一个y∈Y有(x,y)∈R且(y,z)∈S} 计算方法： 1）从定义入手 2）有向图法 3）布尔矩阵 2.2 关系的运算 定理（复合运算满足结合律）： 设R、S、T分别表示从X到Y、Y到Z、Z到U的关系，则有 (RoS) oT = Ro(SoT) = RoSoT 定义2.4 设有一个集合X上的关系R，则Rn可定义如下： 1）R1=R 2）Rn+1=RnoR 故，RmoRn=Rm+n (Rm)n=Rm×n 2.2 关系的运算 例： 设R和S是集合X={0,1,2,3}上的关系，有 R={(x,y) | j=i+1 或 j=i/2} S={(x,y) | i=j+2} 求 RoS，SoR 解： R={(0,1),(1,2),(2,3),(0,0),(2,1)} S={(2,0),(3,1)} RoS={(1,0),(2,1)} SoR={(2,1),(2,0),(3,2)} 2.2 关系的运算 例： 设有X上的关系R1,R2,R3，试证： 如R1?R2，则R1oR3?R2oR3 证明： 对任意(a,c)∈R1oR3，存在b∈X，使得(a,b)∈R1且(b,c)∈R3 由于R1?R2，所以存在b∈X，使得(a,b)∈R2且(b,c)∈R3，于是(a,c) ∈R2oR3 因而R1oR3?R2oR3 2.2 关系的运算 逆运算 是一种一元运算，其结果组成的关系，称关系的逆关系. 定义2.5 设R是一个从X到Y的关系，即R={(x,y) | x∈X,y∈Y}，则从Y到X的关系 称为R的逆关系. 例：R={(1,a),(2,b),(3,c)} 2.2 关系的运算 定理 设R，S分别是从X到Y及Y到Z的关系，则有 1) 2) 3) 4) 5) 2.3 关系的重要性质 自反性 反自反性 对称性 反对称性 传递性 2.3 关系的重要性质 定义2.6 在集合X上的关系R，如对任意x∈X，有(x,x)∈R,则R是自反的 定义2.7 在集合X上的关系R，如对任意x∈X，有 (x,x) R,则R是反自反的 例： 在整数集Z上的关系，“≤”是自反的，不是反自反的；“”是反自反的，不是自反的。 在集合X={1,2,3,4}上的关系R：R={(1,1),(2,1),(3,4),(4,2)}既不是自反的也不是反自反的 2.3 关系的重要性质 一个关系的自反性在图形表示法中相当于一个关系图中的每个结点均有环出现 而一个关系的反自反性相当于一个关系图中的每个结点均无环出现 2.3 关系的重要性质 定义2.8 在集合X上的关系R，如果有(x,y)∈R,必有(y,x)∈R，则称R是对称的 定义2.9 在集合X上的关系R，如果有(x,y) ∈R且x≠y,必有(y,x) R，则称R是反对称的 例：有一些人的集合中“同事”关系是对称的，“父子”关系则是反对称