第二单元 关系与序关系.pptVIP

第二章 关系与序关系 关系的概念 关系的表示 关系的性质 等价关系 关系的运算 偏序关系 2.1 关系的概念 [例]设A={Alice,Bob,Tom}, B={Algebra,Graphs, Sets} Alice选修了Graphs, Bob选修了Algebra, Graph和Sets; Tom选修了Algebra,Graphs; R={Alice,Graphs,Bob,Algebra,Bob,Graphs,Bob,Sets,Tom,Algrbra,Tom,Graphs } ? A?B, 表示了学生集合A与课程集合B之间的选修关系。 2.1 关系的概念 [二元关系的一般性描述] 一对对象之间的关系称为二元关系。 [例] teachers={a,b,c}，students={x,y,z} 建立教学关系 T: aTx iff a TEACHING x 用序偶集合表示为： T = {a,x,a,z,b,y,c,y,c,z} T ? teachers ? students 图示为： 2.1 关系的概念 [例] Subroutines={a,b,c,d,e} 子程序间调用关系 图示为： Calling={a,a,a,b,a,d,b,a,b,c,c,c, c,e, d,d} Calling ? Subroutines ? Subroutines 2.1 关系的概念 [二元关系的集合定义] 设X,Y是两个集合， X ? Y的任何一个子集 R 都确定了一种二元关系，称为从X到Y的二元关系。 x,y?R可记为 xRy，显然 R ? X ? Y x,y?R可记为 x?Ry 当 X=Y 即 X 与 Y 同一时，称 R 为 X 上的一个二元关系。 2.1 关系的概念 [例] F={x,y| x是y的父亲} S={x,y| x,y为正整数且x可整除y} T={y2,y| y为实数} 对上述的：x，y，R，有x,y?R 或 x,y?R，二者必居其一。 2.1 关系的概念 [定义域] 设二元关系S。由 x,y?S的所有对象 x 组成的集合称为S的定义域，记为Dom(S) 。 [值域] 由x,y?S的所有对象 y 组成的集合称为S的值域，记为Ran(S) (Range(S))。记 F(S) = D(S) ? R(S) ，称为 S 的域。 描述：Dom(S) = {x| (?y)(x,y?S)} Ran(S) = {y| (?x)(x,y?S)} 2.1 关系的概念 若干特殊关系： ① X 到Y 的全域关系： Ex,y = X?Y 特别地： Ex,x = X?X ② 空关系：? ③ 恒等关系：Ix = {xi,xi|xi?X} [例] 设 X={1,2,3,4}，求 X 上的关系 “ ”(大于)及其定义域、值域。 2.2 关系的表示方法 (1) 集合表示法 借用集合的各种描述方法对表示关系的序偶集合进行描述 (2) 关系矩阵 设 X={x1,x2,…,xm}，Y={y1,y2,…,yn}，m,n +? R是X到Y的二元关系。构造矩阵 2.2 关系的表示方法 [例] 2.2 关系的表示方法 (3) 关系图表示法 用结点表示X、Y上的元素；若 x,y?R 则从结点x到结点y画一条弧。 [例] 上述Teaching关系的关系图： 2.2 关系的表示方法 [例] 设 X={1,2,3,4}，X 上的关系 “ ”： 2.3 关系的性质 [定义] 设R是X上的二元关系，则： ① R 是自反的? (?x)(x?X?xRx) ② R 是对称的? (?x)(?y)(x,y?X?xRy?yRx) ③ R 是传递的? (?x)(?y)(?z)(x,y,z?X?xRy?yRz ?xRz) ④ R 是反自反的? (?x)(x?X??(xRx)) ⑤ R 是反对称的? (?x)(?y)(x,y?X?xRy?yRx ?x = y) 2.2 关系的性质 [习题] 设 X={1,2,3,4}，画出X 上的关系 “ ”，“?”和 整除“|”的关