离散数学第2版PPT4 二元关系.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《离散数学第2版PPT4 二元关系.ppt》由用户(momomo)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学第2版PPT4 二元关系 离散数学 PPT4
- 资源描述:
-
1、8.1 8.1 二元关系及其表示法二元关系及其表示法一、序偶与笛卡儿积一、序偶与笛卡儿积 笛卡尔(15961650),法国数学家、物理学家、哲学家,出生于法国拉哈的律师家庭,他一出世母亲就病故,依靠保姆照料长大。笛卡尔在当时欧洲著名的拉夫雷士学校读书,他虽身体孱弱,但尊敬师长,勤奋刻苦。笛卡尔生活在资产阶级与封建领主、科学与神学进行激烈斗争的时代。从读书始便对僵化的说教有强烈的怀疑批判精神,坚定不移地寻找真理。笛卡尔在获得法学博士学位后,为了“读世界这本大书”,曾到荷兰服役。退伍以后,主要居住在荷兰,也曾回到法国,从事学术研究。1649年应邀去瑞典担任女王的教师,最后因肺炎病逝在异国。8.1
2、8.1 二元关系及其表示法二元关系及其表示法一、序偶与笛卡儿积一、序偶与笛卡儿积 定义 由两个元素 按照一定的次序组成的二元组称为有序偶对有序偶对,简称序偶序偶,记作 ,其中 称为 的第一元素,为 的第二元素。例如,平面上点的坐标 ,;性质:当且仅当 ;当且仅当 ;将上述概念进行推广,即得到任意个元素的有序序列。8.1 8.1 二元关系及其表示法二元关系及其表示法一、序偶与笛卡儿积一、序偶与笛卡儿积 定义 将 个元素 按照一定的次序组成的 元组称 为 重有序序组,记作 ,即性质:当且仅当 。定义 设 是两个集合,称集合为集合 与 的笛卡尔积笛卡尔积。8.1 8.1 二元关系及其表示法二元关系及
3、其表示法一、序偶与笛卡儿积一、序偶与笛卡儿积直观地,可以把笛卡儿积看成是平面上点的集合,如下图所示。BA1 12 23 34 4a ab bc cd dDC8.1 8.1 二元关系及其表示法二元关系及其表示法一、序偶与笛卡儿积一、序偶与笛卡儿积例 设 ,则结论对两个集合 ,有当 时,有当 时,有任两个集合 ,有8.1 8.1 二元关系及其表示法二元关系及其表示法一、序偶与笛卡儿积一、序偶与笛卡儿积将上述概念进行推广至 个集合之间的笛卡尔积。定义 设 是 个集合,称集合为集合 的笛卡儿积。同样,当 时,容易证明,当 都是有限集时,8.1 8.1 二元关系及其表示法二元关系及其表示法二、关系的引入
4、二、关系的引入 设分别用两个集合 来表示教室里所有椅子的集合和学生的集合,即 。此时,若将它们用坐标描述出来即为右图所示。s1s2smc1c2c3cn0s3 例 假设我们在上“离散数学”课时,教室里共有 把椅子,听课的学生共有 个(),每个学生坐一把椅子。此时,学生与椅子之间有一定的从属关系。8.1 8.1 二元关系及其表示法二元关系及其表示法三、关系的定义三、关系的定义 定义 设 为 个非空集合,称 的任意子集 为以 为基的 元关系关系。特别地,当 时,称 为空关系空关系;当 时,称 为全关系全关系;由于 的任何子集都是一个 元关系,按照子集的定义,共有 个不同的子集,因此,以 为基的不同关
5、系共有 个。8.1 8.1 二元关系及其表示法二元关系及其表示法三、关系的定义三、关系的定义学籍表学号姓名性别英语数学物理040301李晓明男869180040302040330张国庆王薇薇男女768883938590 此关系是以学号学号、姓名姓名、性别性别、英语英语、数学数学、物理物理等六个集合的笛卡儿积为基的。8.1 8.1 二元关系及其表示法二元关系及其表示法四、二元关系四、二元关系 通常情况下研究的关系是两个集之间元素与元素之间的关系或者是一个集合内部两个元素之间的关系,称为二元关系,定义如下:定义 设 为两个非空集合,的任何一个子集 所定义的二元关系称为 到 的二元关系,简称关系。如
6、 是从 到 的二元关系,称 为 上的二元关系。由于 的子集中的元素都是序偶,因此,任何序偶的集合均是一个二元关系。8.1 8.1 二元关系及其表示法二元关系及其表示法四、二元关系四、二元关系 设有一序偶 ,则把这一事实记为 ,读作 对 有关系 ,如果 ,则记为 ,读作 对 没有关系 。8.1 8.1 二元关系及其表示法二元关系及其表示法四、二元关系四、二元关系称 为 的前域,为 的后域,满足称 为 的定义域,为 的值域,记为称为 的域。8.1 8.1 二元关系及其表示法二元关系及其表示法四、二元关系四、二元关系例 设解:8.1 8.1 二元关系及其表示法二元关系及其表示法五、关系的表示法五、关
7、系的表示法1、集合表示法 由于关系是一种特殊的集合,所以集合的两种基本表示法也可以用到关系的表示中,即枚举法枚举法和叙述法叙述法。例 设 ,关系 。定义集合 上的“小于等于”关系为8.1 8.1 二元关系及其表示法二元关系及其表示法五、关系的表示法五、关系的表示法2、关系图法 由于关系是一些有序组的集合,因此可以用有向图来刻划关系,这种图称为关系 的关系图。设 ,是从 到 的一个关系,对应于关系 的关系图有如下规定:(1)设 和 分别为图中的结点,用 表示;(2)如 ,则从 到 可用一有向边 相连。对应图中的有向边;8.1 8.1 二元关系及其表示法二元关系及其表示法五、关系的表示法五、关系的
8、表示法2、关系图法 如果 是定义在 上的关系,则对应于关系 的关系图有如下规定:(1)设 为图中的结点,用 表示;(2)如 ,则从 到 可用一有向边 相连。对应图中的有向边;(3)如 ,则从 到 可用一带箭头的小圆圈表示;8.1 8.1 二元关系及其表示法二元关系及其表示法五、关系的表示法五、关系的表示法例 设 是六个人,是三套房间,考虑 到 之间的一种住宿关系 ,如 住房间 ,则有 ,现假设:则此关系 的关系图如下:8.1 8.1 二元关系及其表示法二元关系及其表示法五、关系的表示法五、关系的表示法 例 设 是六个程序,考虑它之间的一种调用关系 ,如 可调用 ,则有 ,现假设则关系 的关系图
9、如下图所示:8.1 8.1 二元关系及其表示法二元关系及其表示法五、关系的表示法五、关系的表示法3、关系矩阵法 设 ,是从 到 的一个二元关系,称矩阵 为关系 的关系矩阵,其中又称 为 的邻接矩阵邻接矩阵。注:在写关系矩阵时,首先应对两个集合中的元素进行排序,不同的排序会得到不同的关系矩阵。当集合以枚举法表示时,如果没有对集合的元素排序,则默认枚举的次序为元素的排序。8.1 8.1 二元关系及其表示法二元关系及其表示法五、关系的表示法五、关系的表示法3、关系矩阵法 例 设 。考虑从 到 的“大于等于”关系 和“小于”关系 。相应的关系矩阵为:8.2 8.2 关系的运算关系的运算一、关系的交、并
10、、补、差运算一、关系的交、并、补、差运算 由于关系是以序偶为元素的集合,因此有关集合的交、并、补、差运算等在关系中也是适合的。设 都是 到 的关系,则 是相对于 的全集,因此,。8.2 8.2 关系的运算关系的运算一、关系的交、并、补、差运算一、关系的交、并、补、差运算例 设则有8.2 8.2 关系的运算关系的运算二、关系的复合运算二、关系的复合运算 定义 设 是从集合 到集合 的二元关系,是从集合 到集合 的二元关系,则 与 的复合关系(合成关系)是从 到 的关系,且 称为复合运算。在复合关系中,的后域一定是 的前域,否则无法复合。规定:8.2 8.2 关系的运算关系的运算二、关系的复合运算
11、二、关系的复合运算例 设有如下关系分别是从 到 和从 到 的关系,其中(1)用集合方法求 ;(2)用关系图法求 ;(3)用关系矩阵求 ;8.2 8.2 关系的运算关系的运算二、关系的复合运算二、关系的复合运算 R RS SR R。S SA AB BC CA AC C1 1。1 1。1 11 1。1 12 2。2 2。2 22 2。2 23 3。3 3。3 33 3。3 34 4。4 4。4 44 4。4 4关系矩阵求法为:8.2 8.2 关系的运算关系的运算二、关系的复合运算二、关系的复合运算设 是整数集合,是 到 的两个关系:则有8.2 8.2 关系的运算关系的运算三、关系的逆运算三、关系的
12、逆运算 定义 设 是一个从集合 到集合 的二元关系,则从 到 的关系 称为 的逆关系逆关系,运算“-1”称为逆运算。注:关系是一种集合,逆关系也是一种集合,但要区别开两个不同的关系 和 。则例 设 ,是从 到 的一个关系,8.2 8.2 关系的运算关系的运算三、关系的逆运算三、关系的逆运算 如果用关系图表示关系,则仅将关系图中的有向边的方向改变成相反方向即得逆关系的关系图。8.2 8.2 关系的运算关系的运算三、关系的逆运算三、关系的逆运算 如果用关系矩阵表示关系,则关系矩阵求转置即得逆关系的关系矩阵,对其进行按位求反即得其补的关系矩阵。注:8.2 8.2 关系的运算关系的运算四、关系运算的性
展开阅读全文