离散数学-newchap03(精品·公开课件).ppt

第 3章 关系 关系 关系是比函数更一般化的概念。关系中用有序对(a, b)表示从a 到b的一个关系。 关系数据库模型就是基于关系的概念，它可以帮助用户访问数据库（由计算机控制的记录的汇集）中的信息。 。抽象地说，我们把关系定义为有序对的集合。在 抽象的概念中，可认为有序对中的第一个元素与第二个元素相关。 3.1关系 关系可以想成一张表，其中列出了一些元素和其他元素之间的关系 定义 3.1.1 X到Y的关系R，是笛卡儿积X?Y的一个子集。如果(x,y) R，我们写为xRy且说x和y有关。当X=Y，我们称R是X上的(二元)关系。 集合和函数 集合 {x ∈X | (x, y)∈ R，对某个y ∈ Y} 称为R 的定义域。 集合 {y ∈Y | (x, y)∈ R，对某个x ∈ X} 称为R 的值域。 函数是一种特殊的关系。从X 到Y 的函数f 是从X 到Y 的关系，并具有性质： (a) f 的定义域是X。 (b) 对每个x ∈ X，有惟一的y ∈ Y 使得(x, y)∈ f。 例3.1.2 令X = {Bill, Mary, Beth, Dave}和 Y = {计算机科学，数学，艺术，历史} 则表3.1.1 表示的关系可写为 R = {(Bill, 计算机科学)， (Mary, 数学)， (Bill, 艺术) (Beth, 历史)， (Beth, 计算机科学)， (Dave, 数学)} 因为（Beth, 历史）∈R，所以可记为Beth R 历史。R 的定义域（表的第一列）为集合X，R 的值域（表的第二列）为集合Y。 例 3.1.3 X={2,3,4} Y={3,4,5,6,7} 定义X到Y的关系: x整除y 例3.1.4 设R 是X = {1, 2, 3, 4}上的关系，x, y ∈ X，如果x ≤ y，则(x, y)∈ R。 R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4,4)} R 的定义域和值域都是X。 可以用画出关系有向图（digraph）的方法来表示一个集合上关系. 为了画出集合X 上一个关系的有向图，先画出一些点（或称为顶点）来表示X 的元素。 有向图，有向边，圈 如果元素(x,y)在关系中，则画一个从x 到y 的箭头（称为有向边） 关系中形如(x, x)的元素对应于一条从x 到x 的有向边，这样的边称圈。 定义 3.1.6 集合X上的关系R，如果对于每个x X 都有(x,x) R，则称R是自反的。 例 3.1.7 自反？ 例 3.1.8 自反？ 定义 3.1.9 集合X上的关系R，如果对于每个x,y X，如(x,y) R必有(y,x) R,则称R是对称的。 例 3.1.10 ？对称的 例 3.1.11 ？对称的 定义 3.1.12 ？反对称的 集合X上的关系R，如果对于每个 x,y X,如(x,y) R且x?y,必有 (y,x) ? R 则称R是反对称的。 定义 3.1.13 ？反对称的 例 3.1.10 ？反对称的 例 3.1.15 R={(a,a), (b,b),(c,c)} 定义 3.1.16 集合X上的关系R，如果对于每个 x,y,z X,如(x,y) R且(y,z) R ,必有(x,z) R，则称R是传递的。 例3.1.17 传递的? 设R 是X = {1, 2, 3, 4}上的关系，如果x ≤ y，x, y ∈ X，则(x, y)∈ R。R 是传递的，因为 对所有的x, y, z ∈X，若(x, y)∈R 且(y, z)∈ R，则(x, z)∈R。 为了形式化地验证关系满足定义3.1.16， 需要列出R 中所有形如(x, y)和(y, z)的对，并检验每一种情况下都有(x, z)∈ R. 传递? 传递的? 定义 3.1.19 集合X上的关系R，如是自反的，反对称的和传递的。这种关系称为偏序。 例 3.1.20 正整数集合上的关系R定义为 (x,y) R 如x整除y，它是自反的，反对称的和传递的，R是一个偏序。 如果R 是集合X 上的一个偏序，有时用符号x? y 来表示(x, y)∈ R。这个符号表示将这种关系看做X 中元素的序。 假设R是集合X上的一个偏序。 如果x, y∈X并且x ? y或y ? x，则称x和y是可比的（comparable）。 如果x, y ∈ X 并且x ? y 且y ? x，则称x 和y 是不可比的（incomparable）。 如果X 中的每对元素都是可比的，称R 为全序（total order）。 正整数集上的