二元关系 4.1-4.2.ppt

二元关系的运算 例4 设A={1,2,3,4,5,6}，定义在A上的关系R={1,1,1,2,2,3,3,4,4,5,5,6}，计算： (1)Rn(n=1,2,3,4,…) (2) 和 可以看到： （1）对于有穷集A上的关系R，R的不同的幂只有有限个。 （2）当n≥|A|时，则Rn ? 二元关系的运算 定理 设A是有限集合，且|A|＝n，R是A上的二元关系，则： 二元关系的运算 举例： 上图若表示一个计算机网络，数据中心之间通过单向的电话线链接，如何确定两个中心之间是否有一条电话线(可能不直接)链接？或者更一般的，如何确定一个有向图中每对顶点是否“连通”？ 波士顿 芝加哥 丹佛 底特律 圣地亚哥 纽约 二元关系的运算 合成运算的主要性质： (1) (F ? G) ?H=F ? (G ?H)； (2) (F ?G)-1=G-1 ?F-1； (3)Rm ? Rn＝Rm+n, (Rm)n＝Rmn \ 小结 初步了解关系的并、交、补、差、限制、像等运算与数据库中对关系表的操作的关系。 掌握二元关系的合成（幂）运算，主要是集合法与矩阵法。 掌握合成（幂）运算的主要性质。 作业 1.（续4.1节）给定集合A={1, 2, 3, 4}，且A中的关系R： R ={1,1, 1,3, 2,2, 3,4, 4, 1, 4, 4} 计算R2（矩阵法）。 2.分别对下图中所给的两个关系，求Rn，n?N。 3.课本：习题4.13 b d c a a c b e d * * * 离散数学 Discrete Mathematics 主讲：陈哲云 青岛理工大学计算机工程学院 2013.09 第4章 二元关系 集合论及二元关系 二元关系 4.1二元关系基本概念 (重点) 4.2 关系的运算 4.3 关系的性质 (重点) 4.4 关系的闭包 4.5 等价关系和偏序关系 (重点及难点) 4.6 函数的基本概念 二元关系基本概念 世间万物都存在着联系。 集合中的元素有什么联系，用“关系”来表达。 二元关系基本概念 二元关系定义及举例 特殊的二元关系 二元关系表示方法 二元关系 引例 1.设集合A = {张红，李明，王强，程飞}， B = {离散数学，操作系统，计算机图形学}， C={优，良，中，及格，不及格} 请写出学生选修课程情况及课程的成绩。 R = {张红，离散数学，优，张红，操作系统，良， 李明，操作系统，良，李明，计算机图形学，中，王强，离散数学，中，王强，操作系统，及格， 王强, 计算机图形学，良， 程飞, 计算机图形学，优} “关系”都可以对应到一张关系表，反之亦然 学生 课程 成绩 张红 离散数学 优 张红 操作系统 良 李明 操作系统 良 李明 计算机图形学 中 王强 离散数学 中 王强 操作系统 及格 王强 计算机图形学 良 程飞 计算机图形学 优 二元关系 引例 2.令A1={x|x是学号} A2={x|x是姓名} A3={男,女} A4={x|x是出生日期} A5={x|x是班级} A6 ={x|x是籍贯} 则A1?A2?A3 ?A4?A5 ?A6中一个元素： 2011001，王强，男，1991.05.04，计111，四川 这就是学生档案数据库的一条信息，所以学生 的档案就是A1?A2?A3 ?A4?A5 ?A6的一个子集。 学号 姓名 性别 出生日期 班级 籍贯 2011001 张红 女 1992.02.13 计111 辽宁 2011002 王强 男 1991.05.04 计111 四川 2011003 程飞 男 1992.08.12 计111 山东 2011004 李明 男 1991.09.24 计112 江西 2011005 刘艳 女 1992.04.18 计112 海南 2011006 马明 男 1991.07.27 计112 宁夏 2011007 王芳 女 1990.11.15 计113 山西 2011008 于亮 男 1992.12.08 计113 山东 二元关系 二元关系——有序对的集合 A到B的二元关系——R?A×B A上的二元关系——R?A×A n元关系 称 S ? A1×A2×…×An为 A1 , A2 , … , An 上的 n 元关系 x,y∈R ? x R y x,y ?R ? x R y 二元关系 例1 几个二元关系的例子 1. 程序间的调用关系，其中软件系统