离散数学基础 第四章 关系.ppt

第四章 关系 《离散数学基础》——谢胜利 本章主要内容 关系定义及其表示 关系的运算 N元关系及其应用 等价关系 偏序关系 第一节 关系定义及其表示 引言 日常生活和科学技术中的“关系”： 人与人之间有：父子关系、兄弟关系、师生关系 两数之间有：大于关系、等于关系、小于关系 集合之间有：包含关系 元素与集合之间有：属于关系 程序之间有：　调用关系 关系－－联系:事物间的多值依赖。 §1 二元关系的基本概念 一、关系的概念 直观地讲，关系就是反映“多值依赖”的二维表，例如， 学生－选课表： 把学生选课表用集合来表示： R={ 张三,离散数学, 　 李四,微积分,　 张三,高级语言,　 … } 有序对的集合R同样也刻画了学生集合｛张三，李四，…｝与课程集合｛离散数学，微积分，高级语言，…｝之间“多值依赖”的联系，称为二元关系。 §1 二元关系的基本概念 【示例】 设A＝｛1,2,3,4,5｝,B＝｛a,b,c｝, 则 R1＝{1,a,1,b,2,b,3,a}是从A到B的关系 R2＝{a,2,c,4,c,5}是从B到A的关系。 【例】设A={鸡蛋，奶，玉米}，B={奶牛，山羊，母鸡}。我们可以定义由A到B的关系 R ={a，b |a∈A,b∈ B，a由b产生}, 即 R={鸡蛋，母鸡， 奶，奶牛， 奶，山羊}。 补充：关系的应用: 关系数据模型 【定义】设有n个集合A1, A2, …, An, 则笛卡儿积A1×A2×…×An的任意一个子集R称为A1, A2, …, An上的一个n元关系。这些集合A1, A2, …, An叫做关系的域, n叫做它的阶。 若R? An, 则称R为A上的n元关系。 例 设R是A×N×S×D×T 的子集，其中A是所有航空公司的集合，N是航班号的集合，S是出发地的集合，D是目的地的集合，T是起飞时间的集合。则R是由5元组a, n, s, d, t组成的表示飞机航班的关系。 例如，设R表示由国内航空公司飞机航班构成的关系，如果南方航空公司在15:00有从广州到北京的2963航班，那么 南方航空，2963，广州，北京，15:00 属于R。 可以利用n元关系表示计算机的数据库。 数据库由记录组成，这些记录是由字段构成的n元组。字段是n元组的数据项。 用于表示数据库的关系叫做表，因为这些关系常常用表来给出。 例如，学生记录的数据库可以由包含学生的姓名、学号、专业、平均成绩GPA的字段构成。关系数据模型把一个记录表示成一个n元组。于是，学生记录可以被表示成形如 学生姓名、学号、专业、GPA 的4元组。4个记录的一个数据库样本是： 王明，231455，计算机科学，85.8 张强，888323，物理学，73.4 周祥，102147，计算机科学，83.7 刘海，453876，经济学，69.4 【定义】 设R?A×A, 1）当R＝Φ 时, 称R为A上的空关系; 2） 当R＝A×A=A2时, 称R为集合A上的全域关系, 用EA表示。显然EA ＝{x,y|x∈A且y∈A} 3） 若R＝｛x, x|x∈A｝, 则称R是A上的恒等关系, 用ＩA表示。 【定义】 设R是二元关系，由x，y∈R的所有x组成的集合称为R的前域，记作dom R；由 x，y∈R的所有y组成的集合称为R的值域，记作ran R。 例如：A＝{a, b, c, d, e }, B={x, y, z} R={a,x, b,y, e,x, e,y} 则dom R ran R 其它常用关系: 1) 小于等于关系LA LA ＝{x,y|x,y∈A且x≤y}, A?R 2) 整除关系DA DA ＝{x,y|x,y∈A且x|y}, A?Z+ 3) 包含关系R ? R ? ＝{x,y|x,y∈A且x?y}, A为集合族 【例】设A＝{1, 2, 3, 4, 5},R是A上的二元关系，其定义为：当a,b ∈A且a能整除b时，a，b∈R,求R。 解：R＝{1,1, 1,2, 1,3, 1,4, 1,5, 2,2, 2,4, 3,3, 4,4, 5,5} 【例】设A＝{1, 2, 3, 4, 5,6},R是A上的二元关系，其定义为：当a,b ∈A且a和b被3除后余数相同时，a，b∈R,求R。 解：R＝{1,1, 1,4, 2,2, 2,5, 3,3, 3,6, 4,4, 4,1, 5,5 ,5,2, 6,6, 6,3