大学离散数学-关系（课件）.ppt

An Introduction to Database Systenm 3.5 关系及表示 定义3.5.1 设A，B是任意两个集合，A×B的子集R称为从A到B的二元关系，当A=B 时，称R为A上的二元关系。 从上述定义可以看出A到B的二元关系，也是序偶的集合。 若a, b∈ R，则称a与b有关系R，记作a R b。 若 ，则称a与b没有关系R，记作 。 例如：设A={a, b, c, d}, B={0, 1}，则R={﹤a, 0﹥, ﹤b, 0﹥, ﹤c, 1﹥} 就是一个从A到B的二元关系。 定义3.5.2 设A，B是任意两个集合，R是A到B上的二元关系，若R=?，则称为空关系。若R = A×B，则称R为全关系。 称为A上的恒等关系。 全关系 例如：设A={0, 1, 2}，则 。 定义设A，B是两个集合，R是从A到B上的二元关系，则 (1)若存在b∈B，使得a, b∈R，则所有这样的a∈A组成的集合，称为二元关系R的前域。记作dom(R)即 (2)若存在a∈A，使得a, b∈ R，则所有这样的b∈B组成的集合，称为二元关系R的值域。记作ran(R)，即 R的定义域和值域一起称作R的域，记作FLDR，即 FLDR = dom(R)∪ran(R) 从X到Y的二元关系R，也可以用图解的方式表示，X和Y是两个集合。xi是集合X中的元素，yj是集合Y中的元素，当且仅当xiRyj时，才有一条从xi指向yj的有向边。 关系：笛卡尔乘积的子集。 把 的两个子集 和空集分别称为从X到Y的全域关系和空关系。 定理若R和S是从集合A到B上的两个二元关系，则R和S的并、交、补、差也是A到B上的二元关系。 证明：因为R和S是从集合A到B上的二元关系 所以有R? A×B，S? A×B。从而有 即A∩B和A∪B都是A到B上的二元关系。 又因为 所以~R和~S也是A到B上的二元关系。 由于 故R-S也是A到B上的二元关系。 2 关系的表示 （1）关系的矩阵表示 设 X={a, b, c}, Y={0, 1, 2, 3}，R={a, 1, b, 2, c, 0}。可得关系R的矩阵表示如下： 由上例看出，给定从有限集X到Y的二元关系R，就可以构造出它的关系矩阵。 给定两个有限集合 和 ，并且R是从X到Y的二元关系 。如果有 则称矩阵 是R的关系矩阵，并记作 。 （2）关系的图形表示 从X到Y的二元关系R，也可以用图解的方式表示，X和Y是两个集合。xi是集合X中的元素，yj是集合Y中的元素，当且仅当xiRyj时，才有一条从xi指向yj的有向边。 注意：关系图中表达的关系与结点的位置和线段的长度无关。 设 画出R的关系图。 解： R的关系图如图所示。 R的关系图 （3） 关系的性质 判别关系的性质，也可以从关系矩阵和关系图上给予验证。 （1）若关系是自反的，当且仅当在关系矩阵中，对角线上的所有元素都是1；在关系图上，每个节点都有一条自己到自己的边（或称圈）。 （2）若关系是反自反的