标签:   离散数学   二元关系  
文档信息
上传用户 岁月静好     
文档格式 ppt
文档价格 8 元
文档大小 1 MB
文档页数 141 页
相关文档推荐
doc 2020年一级建造师《建筑工程管理与实务》真题(II卷) 附解析
doc 山东省重点小学三年级数学【上册】开学摸底考试试题 (附答案)
doc 实验小学二年级数学下学期开学考试试题外研版A卷 含答案
doc 云南省2020年实验小学一年级数学开学考试试题B卷 含答案
doc 2019-2020学年高二英语上学期第二次月考试题无答案 (I)
doc 云南省2020年实验小学一年级数学开学考试试卷(I卷) 含答案
doc 山东省实验小学三年级数学下学期期末考试试卷 附答案
doc 实验小学二年级数学下学期开学考试试题江西版A卷 含答案
doc 山东省重点小学三年级数学【上册】开学摸底考试试卷 (含答案)
doc 实验小学二年级数学下学期开学考试试题外研版C卷 附解析
doc 2019-2020年高三上学期期中试题(化学)
doc 2019-2020年高三上学期期中试题(数学文)
doc 山东省实验小学三年级数学下学期期末考试试题 含答案
ppt 《技术经济学练习》PPT课件
doc 山东省实验小学三年级数学下学期期末摸底考试试题 (含答案)
doc 广东省重点小学四年级数学下学期期中考试试题D卷 (含答案)
doc 云南省2020年一年级数学下学期期末考试试题新人教版 (附解析)
doc 2020年六年级数学【上册】期末考试试卷豫教版C卷 附解析
doc 2019-2020年高三上学期期中试题 文科综合 含答案
ppt 离散数学-合式公式和谓词推理
doc 2019-2020年高三上学期期中试题理综
doc 实验小学二年级数学下学期开学考试试题外研版B卷 附解析
doc 2020年一级建造师《建筑工程管理与实务》真题D卷 (附解析)
doc 实验小学二年级数学下学期开学考试试题外研版(II卷) 附解析
doc 2019-2020学年高二英语上学期第二次月考试题(无答案)
doc 山东省实验小学三年级数学下学期期中考试试卷 (附答案)
doc 2019-2020年高三上学期期中语文试卷含解析
doc 云南省2020年一年级数学下学期期末考试试卷人教版 (附答案)
doc 2020年六年级数学【上册】期末考试试卷豫教版 附答案
doc 2020年一级建造师《建筑工程管理与实务》练习题B卷 (附答案)
doc 云南省2020年一年级数学下学期期末考试试题北师大版 (附答案)
doc 实验小学二年级数学下学期开学考试试题新人教版B卷 含答案
doc 广东省重点小学四年级数学下学期期中考试试题(II卷) 含答案
doc 2020年一级建造师《建筑工程管理与实务》真题D卷 (含答案)
doc 实验小学二年级数学下学期开学考试试题新人教版 附解析
doc 2020年六年级数学【上册】期末考试试卷长春版 附答案
doc 山东省重点小学三年级数学【上册】开学摸底考试试卷 附解析
doc 2020年一级建造师《建筑工程管理与实务》真题(II卷) (含答案)
doc 实验小学二年级数学下学期开学考试试题外研版(I卷) 附答案
ppt 《技术经济学复习》PPT课件
doc 2020年六年级数学【上册】期末考试试卷赣南版(I卷) 附解析
doc 山东省实验小学三年级数学下学期期中考试试题 附答案
doc 2020年六年级数学【上册】期末考试试卷豫教版(I卷) 含答案
doc 实验小学二年级数学下学期开学考试试题北师大版(I卷) 附答案
doc 广东省重点小学四年级数学下学期期中考试试题B卷 (附答案)
doc 2020年六年级数学【上册】期末考试试卷赣南版(I卷) 含答案
doc 实验小学二年级数学下学期开学考试试题新人教版A卷 含答案
doc 实验小学二年级数学下学期开学考试试题江苏版C卷 附解析
doc 2020年一级建造师《建筑工程管理与实务》真题C卷 (附解析)
doc 云南省2020年实验小学一年级数学开学测试试卷(II卷) 含答案
doc 2020年一级建造师《建筑工程管理与实务》真题(II卷) 附答案
doc 山东省重点小学三年级数学【上册】开学摸底考试试卷 (附答案)
doc 2020年六年级数学【上册】期末考试试卷豫教版A卷 附答案
doc 2020年六年级数学【上册】期末考试试卷豫教版B卷 含答案
ppt 《技术的价值》PPT课件
doc 2020年六年级数学【上册】期末考试试卷豫教版A卷 附解析
ppt 离散数学关系的概念、性质及运算
ppt 离散数学二元运算及其性质
doc 山东省重点小学三年级数学【上册】开学摸底考试试卷 含答案
doc 2020年一级建造师《建筑工程管理与实务》真题D卷 含答案
doc 广东省重点小学四年级数学下学期期中考试试题C卷 含答案
doc 2019-2020年高三上学期期中试题(基本能力)
doc 实验小学二年级数学下学期开学考试试题新人教版B卷 附解析
ppt 《技术的含义及作用》PPT课件
doc 山东省实验小学三年级数学下学期期末摸底考试试题 附答案
doc 山东省实验小学三年级数学下学期期末摸底考试试题 附解析
ppt 离散数学习题评讲
doc 2020年六年级数学【上册】期末考试试卷赣南版(II卷) 附答案
doc 2019-2020年高三上学期期中试题数学(尖子班)缺答案
doc 2020年六年级数学【上册】期末考试试卷豫教版C卷 附答案
doc 2020年一级建造师《建筑工程管理与实务》练习题A卷 含答案
doc 实验小学二年级数学下学期开学考试试题外研版B卷 含答案
doc 2020年一级建造师《建筑工程管理与实务》真题D卷 附答案
doc 山东省实验小学三年级数学下学期期末考试试卷 含答案
doc 云南省2020年一年级数学下学期期末考试试卷新人教版 (附解析)
ppt 离散数学半群与群
doc 2020年一级建造师《建筑工程管理与实务》真题B卷 含答案
doc 山东省实验小学三年级数学下学期期末摸底考试试卷 (含答案)
doc 云南省2020年一年级数学下学期期末考试试题人教版 (附解析)
doc 实验小学二年级数学下学期开学考试试题江西版 附解析
doc 2019-2020年高三上学期期中语文试题 含解析(I)
doc 实验小学二年级数学下学期开学考试试题江苏版B卷 附答案
doc 广东省重点小学四年级数学下学期期中考试试题D卷 附解析
doc 2020年六年级数学【上册】期末考试试卷豫教版(I卷) 附解析
doc 广东省重点小学四年级数学下学期期中考试试题D卷 (附解析)
doc 实验小学二年级数学下学期开学考试试题北师大版C卷 附解析
doc 云南省2020年一年级数学下学期期末考试试卷部编版 (附答案)
ppt 《技术工程与创新》PPT课件
doc 山东省实验小学三年级数学下学期期末摸底考试试卷 (附解析)
doc 2020年一级建造师《建筑工程管理与实务》真题(II卷) (附答案)
doc 2019-2020年高三上学期期中试题(历史)
doc 广东省重点小学四年级数学下学期期中考试试题D卷 (附答案)
doc 广东省重点小学四年级数学下学期期中考试试题B卷 附解析
doc 2020年六年级数学【上册】期末考试试卷长春版 附解析
doc 实验小学二年级数学下学期开学考试试题江苏版(II卷) 附答案
doc 2020年六年级数学【上册】期末考试试卷豫教版B卷 附答案
doc 山东省实验小学三年级数学下学期期末摸底考试试卷 含答案
doc 2019-2020年高三上学期期中试题 语文 缺答案
doc 2019-2020年高三上学期期中试题语文
doc 2020年一级建造师《建筑工程管理与实务》练习题C卷 (附答案)
doc 山东省实验小学三年级数学下学期期中考试试卷 含答案
doc 2019-2020年高三上学期期中调研政治试卷含答案
doc 2019-2020学年高二英语上学期第二次月考试题无答案
doc 2020年六年级数学【上册】期末考试试卷豫教版(II卷) 附解析
doc 山东省实验小学三年级数学下学期期末摸底考试试卷 附解析
ppt 《技术性论文写作》PPT课件
doc 2019-2020学年高二英语上学期第二次月考试题(含解析) (II)
ppt 《技术有形化简介》PPT课件
doc 2020年一级建造师《建筑工程管理与实务》真题B卷 (含答案)
ppt 《技术经济学讲》PPT课件
doc 实验小学二年级数学下学期开学考试试题江西版C卷 附解析
doc 云南省2020年实验小学一年级数学开学检测试题A卷 含答案
doc 实验小学二年级数学下学期开学考试试题江西版 附答案
doc 山东省实验小学三年级数学下学期期末考试试题 附解析
doc 实验小学二年级数学下学期开学考试试题外研版(II卷) 含答案
doc 实验小学二年级数学下学期开学考试试题江苏版(II卷) 附解析
ppt 《技术经济基本方法》PPT课件
doc 云南省2020年一年级数学下学期期中考试试题新人教版 (附答案)
ppt 离散数学代数结构
doc 广东省重点小学四年级数学下学期期中考试试题(II卷) 附解析
ppt 《技术经济学new》PPT课件
doc 实验小学二年级数学下学期开学考试试题北师大版B卷 附解析
doc 2019-2020年高三上学期期中试题(英语)
doc 云南省2020年一年级数学下学期期末考试试题人教版 (附答案)
ppt 《技术的性质》PPT课件
doc 2020年六年级数学【上册】期末考试试卷长春版 (含答案)
doc 云南省2020年一年级数学下学期期中考试试题新人教版 (附解析)
doc 实验小学二年级数学下学期开学考试试题新人教版A卷 附答案
doc 实验小学二年级数学下学期开学考试试题江苏版 附解析
doc 实验小学二年级数学下学期开学考试试题北师大版B卷 附答案
doc 广东省重点小学四年级数学下学期期中考试试题C卷 附解析
ppt 《技术经济学基础》PPT课件
doc 实验小学二年级数学下学期开学考试试题江苏版B卷 附解析
doc 山东省实验小学三年级数学下学期期末考试试卷 (含答案)
doc 2020年六年级数学【上册】期末考试试卷赣南版 (附答案)
doc 云南省2020年实验小学一年级数学开学检测试卷(I卷) 含答案
doc 实验小学二年级数学下学期开学考试试题外研版C卷 附答案
doc 云南省2020年实验小学一年级数学开学检测试题B卷 含答案
doc 2019-2020年高三上学期期中试题历史缺答案
doc 云南省2020年一年级数学下学期期末考试试题人教版 (含答案)
doc 云南省2020年实验小学一年级数学开学检测试题(II卷) 含答案
ppt 《技术经济学》PPT课件
doc 云南省2020年一年级数学下学期期末考试试卷部编版 (附解析)
doc 实验小学二年级数学下学期开学考试试题江苏版C卷 含答案
doc 2020年一级建造师《建筑工程管理与实务》真题D卷 附解析
doc 云南省2020年实验小学一年级数学开学测试试卷B卷 含答案
doc 2020年六年级数学【上册】期末考试试卷赣南版B卷 附解析
doc 2019-2020学年高二英语上学期第二次月考试题(无答案) (II)
ppt 离散数学命题逻辑等值演算
ppt 《技术的巨大作用》PPT课件
doc 广东省重点小学四年级数学下学期期中考试试题B卷 附答案
doc 2020年一级建造师《建筑工程管理与实务》练习题C卷 (含答案)
doc 实验小学二年级数学下学期开学考试试题江苏版C卷 附答案
doc 广东省重点小学四年级数学下学期期中考试试题C卷 (附答案)
doc 2020年六年级数学【上册】期末考试试卷赣南版C卷 附解析
doc 广东省重点小学四年级数学下学期期中考试试题(I卷) 附解析
doc 实验小学二年级数学下学期开学考试试题新人教版(II卷) 附解析
doc 山东省重点小学三年级数学【上册】开学摸底考试试题 (附解析)
doc 山东省实验小学三年级数学下学期期中考试试题 含答案
doc 2019-2020年高三上学期期中试题(语文)
doc 实验小学二年级数学下学期开学考试试题江西版A卷 附解析
doc 实验小学二年级数学下学期开学考试试题江苏版 含答案
doc 实验小学二年级数学下学期开学考试试题外研版 含答案
ppt 《技术图形分析》PPT课件
doc 云南省2020年实验小学一年级数学开学测试试卷A卷 含答案
doc 2020年六年级数学【上册】期末考试试卷长春版B卷 含答案
doc 2020年一级建造师《建筑工程管理与实务》练习题B卷 附解析
doc 2019-2020年高三上学期期中语文试题
doc 2019-2020年高三上学期期中试题(物理)
doc 2020年一级建造师《建筑工程管理与实务》练习题B卷 附答案
doc 实验小学二年级数学下学期开学考试试题新人教版A卷 附解析
doc 2019-2020年高三上学期期中试题物理
doc 山东省实验小学三年级数学下学期期末摸底考试试题 (附答案)
doc 云南省2020年实验小学一年级数学开学考试试题(II卷) 含答案
doc 2019-2020年高三上学期期中试题数学理
doc 云南省2020年一年级数学下学期期末考试试卷人教版 (附解析)
ppt 《技术经济学概论》PPT课件
doc 2020年一级建造师《建筑工程管理与实务》真题(I卷) (附解析)
ppt 《技术应用的两面性》PPT课件
ppt 《技术的性质定稿》PPT课件
doc 实验小学二年级数学下学期开学考试试题外研版(II卷) 附答案
doc 2019-2020学年高二英语上学期第二次段考12月试题
doc 2020年六年级数学【上册】期末考试试卷长春版A卷 附解析
doc 2019-2020学年高二英语上学期第二次月考试题(职教班)
doc 2020年一级建造师《建筑工程管理与实务》真题C卷 含答案
doc 广东省重点小学四年级数学下学期期中考试试题(I卷) (附答案)
doc 2019-2020学年高二英语上学期第二次月考试题
doc 2020年一级建造师《建筑工程管理与实务》练习题A卷 (附解析)
doc 山东省实验小学三年级数学下学期期末摸底考试试卷 (附答案)
doc 实验小学二年级数学下学期开学考试试题江苏版(II卷) 含答案
doc 2019-2020年高三上学期期中语文试题 含解析
ppt 离散数学-64几种特殊的图
doc 山东省实验小学三年级数学下学期期中考试试题 (附答案)
doc 2019-2020年高三上学期期中试题化学缺答案
doc 云南省2020年实验小学一年级数学开学考试试卷(II卷) 含答案
doc 云南省2020年实验小学一年级数学开学考试试题(I卷) 含答案
doc 实验小学二年级数学下学期开学考试试题江西版C卷 附答案
doc 云南省2020年实验小学一年级数学开学检测试卷A卷 含答案
ppt 离散数学-近世代数-代数结构
doc 实验小学二年级数学下学期开学考试试题江苏版(I卷) 含答案

离散数学二元关系

 版权申诉  ppt " "2020/2/24" "1" "第四章 二元关系" "主要内容: 关系的概念及表示方法 关系的性质 关系的运算: -关系的复合,求逆关系,关系的闭包。 三种关系: -等价关系,相容关系, 次序关系。 " "2020/2/24" "2" "一、序偶与有序n元组 1.定义:由两个对象x、y组成的序列称为有序二元组,也称之为序偶,记作;称x、y分别为序偶的第一,第二元素。 注意,序偶与集合{x,y}不同: 序偶:元素x和y有次序; 集合{x,y}:元素x和y的次序无关紧要。" "4-1 序偶与集合的笛卡尔积" "2020/2/24" "3" "2.定义:设是两个序偶, 如果x=u和y=v则称相等, 记作=。 3 .定义:有序3元组是一个序偶,其第一个元素也是个序偶。 有序3元组<< a,b>, c>可以简记成, 但>不是有序3元组。 " "2020/2/24" "4" "4.定义:有序n元组是一个序偶,其第一个元素本身是个有序n-1元组, 记作<, xn>。且可以简记成。 5. 定义= ( x1= y1) ( x2= y2) ( xn= yn) " "2020/2/24" "5" " 例如“斗兽棋”的16颗棋子, " "设:A={红,蓝} B={象,狮,虎,豹,狼,狗,猫,鼠} 每个棋子可以看成一个序偶,斗兽棋可记成集合AB : {<红,象>,<红,狮>,<红,虎>,<红,豹>,<红,狼>,<红,狗>, <红,猫>,<红,鼠>,<蓝,象>,<蓝,狮>,<蓝,虎>,<蓝,豹>, <蓝,狼>,<蓝,狗>, <蓝,猫>,<蓝,鼠> }" "2020/2/24" "6" "1.定义:设A、B是集合,由A的元素为第一元素,B的元素为第二元素组成序偶的集合,称为A和B的笛卡尔积,记作A×B,即 AB={|xA∧yB} 例1 设A={0,1},B={a,b},求AB , BA, AA 。 解: AB={<0,a>,<0,b>,<1,a>,<1,b>} BA={,,,} AA={<0,0>,<0,1>,<1,0>,<1,1>} 可见 A×B≠B×A 所以,集合的笛卡尔积运算不满足交换律。" "2020/2/24" "7" "另外 (AB)C={<,c>|AB cC} A(BC)={>|aA BC}, 因 >不是有序三元组, 所以(AB)CA(BC)。故也不满足结合律。 " "2.性质 1) 如果A、B都是有限集,且|A|=m, |B|=n,则 |AB |=mn。 证明:由笛卡尔积的定义及排列组合中的乘法原理,直接推得此定理。 2) AΦ=ΦB=Φ " "2020/2/24" "8" "3) 对∪和∩满足分配律。 设A,B,C是任意集合,则 ⑴ A(B∪C)= (AB)∪(AC); ⑵ A(B∩C)= (AB)∩(AC); ⑶ (A∪B)C= (AC)∪(BC); ⑷ (A∩B)C= (AC)∩(BC); 证明⑴ :任取A(B∪C) xA yB∪C xA(yB∨yC) ( xA yB)∨(xAyC) AB∨AC (AB)∪(AC) 所以⑴式成立。(其余可以类似证明)" "2020/2/24" "9" "4) 若C, 则 AB(ACBC) (CACB) 证明:充分性: 设AB,求证 ACBC 任取AC xAyC xByC (因AB) BC 所以, ACBC。 必要性:若C, 由ACBC 求证 AB 取C中元素y, 任取 xA xAyC AC BC (由ACBC ) xByC xB 所以, AB。 所以 AB(ACBC) 类似可以证明 AB (CACB)。" "2020/2/24" "10" "5) 设A、B、C、D为非空集合,则 ABCDAC∧BD 证明:首先,由ABCD 证明AC∧BD 任取xA,任取yB,所以 xAyBA×B C×D (由ABCD ) xCyD 所以, AC∧BD。 其次, 由AC,BD 证明ABCD 任取A×B  xAyB  xCyD (由AC,BD) C×D 所以, ABCD 证毕。" "2020/2/24" "11" " 6)约定 (…(A1A2)…An-1)An)=A1A2…An 特别 AA…A = An 设R是实数集合,则R2表示笛卡尔坐标平面, R3表示三维空间,Rn表示n维空间。 3. 应用 1)令A1={x|x是学号} A2={x|x是姓名} A3={男,女} A4={x|x是出生日期} A5={x|x是班级} A6 ={x|x是籍贯} 则A1A2A3 A4A5 A6中一个元素: <001,王强,男,1981:02:16,计2001-1,辽宁> 这就是学生档案数据库的一条信息,所以学生的档案就是A1A2A3 A4A5 A6的一个子集。" "2020/2/24" "12" "2) 令A={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v, w,x,y,z} 是英文字母表 一个英文单词可以看成有序n元组:如 at=, boy=, data=, computer= 于是可以说: atA2 ,boyA3,dataA4,computerA8,… 所以英文词典中的单词集合可以看成是 A∪A2∪…∪An 的一个子集。 作业 P105 ⑵" "2020/2/24" "13" "4-2 关系及其表示法" " 相关 按照某种规则,确认了二个对象或多个对象之间有关系,称这二个对象或多个对象是相关的。" "例1: 大写英文字母与五单位代码的对应关系R1: 令α={A,B,C,D,…Z} β={30,23,16,22,…,21}是五单位代码集合 β={11000, 10011, 01110, 10010,…, 10001} R1={,,,...,}α×β" "2020/2/24" "14" "例2:令A={1,2,3,4}, A中元素间的≤关系R2 : R2={ <1,1>,<1,2>,<1,3>,<1,4>,<2,2>,<2,3>, <2,4>, <3,3>, <3,4>,<4,4>}A×A" " 关系的定义 定义1: 设A、B是集合,如果RA×B,则称R是一个从A到B的二元关系。如果 RA×A,则称R是A上的二元关系。二元关系简称为关系。 定义2: 任何序偶的集合,都称之为一个二元关系。如:R={<1,a>,<书,车>,<人, 树>}" "基本概念" "2020/2/24" "15" "R xRy 也称之为x与y有R关系。" "R xRy 也称之为x与y没有R关系。" "例3. R是实数集合,R上的几个熟知的关系" " 从例3中可以看出关系是序偶(点)的集合(构成线、面)。" "2020/2/24" "16" "关系的定义域与值域 定义域(domain):设RA×B,由所有R的第一个元素组成的集合,称为R的定义域。 记作dom R,即 dom R={x|y(R)} 值域(range):设RA×B,由所有R的第二个元素组成的集合,称为R的值域。 记作ran R,即 ran R={y|x(R)} 令: R1={ <1,1>,<1,2>,<1,3>,<1,4>, <2,2>, <2,3>, <2,4>, <3,3>, <3,4>, <4,4>} dom R1 ={1,2,3,4} ran R1 ={1,2,3,4} " "2020/2/24" "17" "枚举法: 即将关系中所有序偶一一列举出,写在大括号内。如R ={ <1,1>,<1,2>,<1,3>, <1,4>, <2,2>, <2,3>, <2,4>, <3,3>, <3,4>, <4,4>} 。 谓词公式法: 即用谓词公式表示序偶的第一元素与第二元素间的关系。例如 R={|xR时,从x到y引一条有向弧(边)。这样得到的图形称为R的关系图。" "关系的表示方法" "2020/2/24" "18" "例 设A={1,2,3,4},B={a,b,c}, R1 A×B,R2 A×A, R1 ={ <1,a>,<1,c>,<2,b>,<3,a>,<4,c>}, R2 ={ <1,1>,<1,4>,<2,3>,<3,1>,<3,4>, <4,1>,<4,2>}" "R1 、R2的关系图如下:" "2020/2/24" "19" "矩阵表示法: 设A={a1, a2, , am},B={b1, b2, , bn}是个有限集, RA×B,定义R的m×n阶矩阵 MR=(rij)m×n,其中" "例:R1={ <1,a>,<1,c>,<2,b>,<3,a>,<4,c>} R2={ <1,1>,<1,4>,<2,3>,<3,1>,<3,4>, <4,1>,<4,2>}" "2020/2/24" "20" "空关系Φ: 因为ΦA×B,(或ΦA×A),所以Φ也是一个从A到B(或A上)的关系,称之为空关系。 即无任何元素的关系,它的关系图中只有结点,无任何边;它的矩阵中全是0。 完全关系(全域关系) : A×B(或A×A)本身也是一个从A到B(或A上) 的关系,称之为完全关系。 即含有全部序偶的关系。它的矩阵中全是1。 " "三个特殊关系" "2020/2/24" "21" "A上的恒等关系IA: IAA×A,且IA ={|x∈A}为A上的恒等关系。 例如 A={1,2,3}, 则IA ={<1,1>,<2,2>,<3,3>} A上的Φ、完全关系及IA的关系图及矩阵如下: " "2020/2/24" "22" " 由于关系就是集合,所以集合的∩、∪、-、 和~运算对关系也适用。 例如 A是学生集合,R是A上的同乡关系,S是A上的同姓关系,则 R∪S:或同乡或同姓关系 R∩S:既同乡又同姓关系 R-S :同乡而不同姓关系 RS:同乡而不同姓,或同姓而不同乡关系 ~R:不是同乡关系, 这里~R=(A×A)-R 作业 P109 ⑵、⑸c)d) " "关系的集合运算" "2020/2/24" "23" "本节中所讨论的关系都是集合A中的关系。 关系的性质主要有:自反性、反自反性、对称性、反对称性和传递性。 一. 自反性 定义:设R是集合A中的关系,如果对于任意x∈A都有∈R (xRx),则称R是A中自反关系。 即 R是A中自反的关系x(xAxRx) 例如:在实数集合中,“”是自反关系,因为,对任意实数x,有x  x. " "4-3 关系的性质" "2020/2/24" "24" "从关系有向图看自反性:每个结点都有环。 从关系矩阵看自反性:主对角线都为1。" " 令A={1,2,3},确定以下八个关系中哪些是自反的?" "2020/2/24" "25" "二.反自反性 定义:设R是集合A中的关系,如果对于任意的x∈A都有R ,则称R为A中的反自反关系。 即 R是A中反自反的x(xAR) 从关系有向图看反自反性:每个结点都无环。 从关系矩阵看反自反性:主对角线都为0。 如 实数的大于关系>,父子关系是反自反的。 注意:一个不是自反的关系,不一定就是反自反 的,如前边R6、R7非自反,也非反自反。 " "2020/2/24" "26" "R2、R5、 R8、均是反自反关系。" "观察下图:" "2020/2/24" "27" "三.对称性 定义:R是集合A中关系,若对任何x, y∈A,如果有xRy,必有yRx,则称R为A中的对称关系。 R是A上对称的 xy((xAyAxRy) yRx) 从关系有向图看对称性:在两个不同的结点之间,若有边的话,则有方向相反的两条边。 从关系矩阵看对称性:以主对角线为对称的矩阵。 例 邻居关系和朋友关系是对称关系。 " "2020/2/24" "28" "R3、R4、 R6 、 R8均是对称关系。" "2020/2/24" "29" "四.反对称性 定义:设R为集合A中关系,若对任何x, y∈A,如果有xRy,和yRx,就有x=y,则称R为A中反对称关系 。" " 由R的关系图看反对称性:两个不同的结点之间最多有一条边。 从关系矩阵看反对称性:以主对角线为对称的两个元素中最多有一个1。 另外对称与反对称不是完全对立的,有些关系它既是对称也是反对称的,如空关系和恒等关系。" "2020/2/24" "30" "上面R1、R2、R4、R5、R8均是反对称关系。 R4、R8既是对称也是反对称的。" "2020/2/24" "31" "五. 传递性 定义:R是A中关系,对任何x,y,z∈A,如果有xRy,和yRz,就有xRz,则称R为A中传递关系。 即R在A上传递 xyz((xAyAzAxRyyRz)xRz) 例 实数集中的≤、<,集合、是传递的。 从关系关系图和关系矩阵中不易看清是否有传递性。必须直接根据传递的定义来检查。 检查时要特别注意使得传递定义表达式的前件为F的时候此表达式为T,即是传递的。 即若∈R与∈R有一个是F时(即定义的前件为假),R是传递的。 " "例如 A={1,2},下面A中关系R是传递的。 通过带量词的公式在论域展开式说明R在A上传递" "xyz((xAyAzAxRyyRz)xRz) xyz((xRyyRz)xRz) (为了简单做些删改)  yz((1RyyRz)1Rz)yz((2RyyRz)2Rz) (z((1R11Rz)1Rz)z((1R22Rz)1Rz)  (z((2R11Rz)2Rz) (z((2R22Rz)2Rz)) (((1R11R1)1R1)((1R11R2)1R2))  (((1R22R1)1R1)((1R22R2)1R2))  (((2R11R1)2R1) ((2R11R2)2R2))  (((2R22R1)2R1))  ((2R22R2)2R2))  (((FF)F)((FT)T))(((TF)F)((TF)T)) (((FF)F) ((FT)F))(((FF)F))((FF)F))T" "2020/2/24" "33" "以上R1、R3、R4、R5、R8均是传递的关系。" "本节要求: 1.准确掌握这五个性质的定义。 2.熟练掌握五个性质的判断和证明。 R是A中自反的x(xAxRx) R是A中反自反的x(xAR) R是A上对称的xy((xAyAxRy) yRx) R是A上反对称的 xy((xAyAxRyyRx) x=y) xy((xAyAxyxRy)y x) R在A上传递 xyz((xAyAzAxRyyRz)xRz) 注意 性质表达式的前件为F时此表达式为T,即R是满足此性质的。 (自反和反自反性除外)" "2020/2/24" "35" "2020/2/24" "36" "下面归纳这八个关系的性质:Y-有 N-无 " "2020/2/24" "37" "2020/2/24" "38" "练习1:令I是整数集合,I上关系R定义为: R={|x-y可被3整除}, 求证R是自反、对称和传递的。 证明:⑴自反性:任取x∈I, 因 x-x=0, 0可被3整除,所以有∈R, 故R自反。 ⑵对称性:任取x,y∈I,设∈R, 由R定义得 x-y可被3整除, 即x-y=3n(n∈I), y-x=-(x-y)=-3n=3(-n), -n∈N ∴∈R, R是对称的。 ⑶传递性:任取x,y,z∈I,设xRy, yRz, 由R定义得 x-y=3m, y-z=3n (m.n∈I) x-z= (x-y)+(y-z)=3m+3n=3(m+n), m+n∈N 所以xRz, 所以R传递。 证毕 " "2020/2/24" "39" "练习2:设R是集合A上的一个自反关系,求证: R是对称和传递的,当且仅当在R中,则有也在R中。 证明:必要性 已知R是对称和传递的。 设R 又R,(要证出 R ) 因R对称的故R,又已知R 由传递 性得R。所以有如果在R 中,则有也在R中。 充分性 已知任意 a,b,cA,如在 R中,则有也在R中。 " "2020/2/24" "40" "先证R对称 任取 a,bA 设R,(要证出 R ) 因R是自反的,所以R,由 R且R,根据已知条件得 R ,所以R是对称的。 再证R传递 任取 a,b,cA 设R,R。 (要证出R ) 由R是对称的,得R ,由 R且R,根据已知条件得 R , 所以R是传递的。 作业 第113页 ⑴、⑶、⑷" "2020/2/24" "41" "4-4 关系的复合" "下面介绍由两个关系生成一种新的关系,即关系的复合运算。 例如,有3个人a,b,c,A={a,b,c}, R是A上兄妹关系, S是A上母子关系, ∈R∧∈S 即a是b的哥哥, b是a的妹妹; b是c的母亲,c是b的儿子。 则a和c间就是舅舅和外甥的关系,记作 RS, 称它是R和S的复合关系。 " "2020/2/24" "42" "1.定义:设R是从X到Y的关系,S是从Y到Z的关系,则R和S的复合关系记作RS 。定义为: RS ={|xXzZ y(yY RS)} 显然, RS 是从X到Z的关系。 2.复合关系的计算方法 (俗称过河拆桥法) A={1,2,3} B={1,2,3.4} C={1,2,3,4,5}  RA×B SB×C 枚举法  R={<1,2>,<2,3>,<2,4>,<3,1>} S={<1,2>,<2,1>,<2,3>,<3,4>,<4,2>,<4,5> 则 RS ={<1,1>,<1,3>,<2,4>,<2,2>,<2,5>,<3,2>} " "2020/2/24" "43" "有向图法" "⑶ 关系矩阵法 令A={a1, a2,…, am} B={b1, b2,…, bn} C={c1, c2,…, ct} RA×B SB×C" "" "2020/2/24" "44" "2020/2/24" "45" "⑷ 谓词公式法 设I是实数集合,R和S都是I上的关系,定义如下: R={| y=x2+3x} S={| y=2x+3} " "所以 RS ={| y=2x2+6x+3}" "三.性质 关系复合运算不满足交换律,但是 1.满足结合律: RA×B SB×C TC×D 则 " "2020/2/24" "46" "b(b∈B∧∈R∧∈ (S ○ T) b(b∈B∧∈R∧c(c∈C∧∈S∧∈T)) bc(b∈B∧∈R∧(c∈C∧∈S∧∈T)) cb(c∈C∧(b∈B∧∈R∧∈S∧∈T)) c (c∈C∧b(b∈B∧∈R∧∈S)∧∈T) c (c∈C∧∈(R ○ S)∧∈T) ∈ " "所以" "可以用下图形象表示:" "2020/2/24" "47" "2. RA×B SB×C TB×C " "证明⑴ 任取∈R ○ (S∪T)  b(b∈B∧∈R∧∈S∪T) b(b∈B∧∈R∧(∈S∨∈T)) b((b∈B∧∈R∧∈S)∨ (b∈B∧∈R∧∈T)) b(b∈B∧∈R∧∈S)∨ b(b∈B∧∈R∧∈T) ∈R ○ S∨∈R ○ T ∈(R ○ S)∪(R ○ T) 所以R ○ (S∪T)=(R ○ S)∪(R ○ T)" "2020/2/24" "48" "证明⑵ 任取∈R ○ (S∩T)  b(b∈B∧∈R∧∈S∩T) b(b∈B∧∈R∧(∈S∧∈T)) b((b∈B∧∈R∧∈S)∧ (b∈B∧∈R∧∈T)) b(b∈B∧∈R∧∈S)∧ b(b∈B∧∈R∧∈T) ∈R ○ S ∧∈R ○ T ∈(R ○ S)∩(R ○ T) 所以 R ○ (S∩T)(R ○ S)∩(R ○T) x(A(x)∧B(x)) xA(x)∧xB(x) " "2020/2/24" "49" "3. R是从A到B的关系,则 " "验证:" "令A={1,2,3}, B={a,b,c,d}" "从这两个图看出它们的复合都等于R。" "2020/2/24" "50" "4. 关系的乘幂 令R是A上关系,由于复合运算可结合,所以 关系的复合可以写成乘幂形式。即" "例如R是A上关系,如上图所示,可见 R2,表明在R图上有从a到c有两条边的路径: a→b→c;R3,表明在R图上有从a到d有三条 边的路径:a→b→c→d。...如果Rk,表明在 R图上有从x到y有k条边(长为k)的路径(x,yA)。" "有" "(m,n为非负整数)" "" "2020/2/24" "51" "4-5 逆关系" "一.定义 R是从A到B的关系,如果将R中的所有序偶的 两个元素的位置互换,得到一个从B到A的关系, 称之为R的逆关系,记作RC,或 R-1。 RC={|R} ∈RC R 二. 计算方法 1. R={<1,2>,<2,3>,<3,4>,<4,5>} RC ={<2,1>,<3,2>,<4,3>,<5,4>}" "2020/2/24" "52" "2. RC的有向图:是将R的有向图的所有边的方向颠倒一下即可。 3. RC的矩阵 M =(MR)T 即为R矩阵的转置。如" "三.性质 令R、S都是从X到Y的关系,则 1. (RC)C = R 2. (R∪S)C = RC∪SC 。 3. (R∩S)C = RC∩SC 。 4. (R-S)C = RC-SC 。" "2020/2/24" "53" "证明1:任取(R∪S)C,则 (R∪S)C  R∪S  R∨S  RC∨SC  RC∪SC 所以 (R∪S)C = RC∪SC ,其它类似可证。 5. RS  RC SC 。 证明:充分性,已知RC SC ,则任取∈R RC  SC  S ∴ RS 必要性,已知R S,则任取∈RC  R S SC ∴ RCSC " "2020/2/24" "54" "6.(~R)C=~RC 证明:任取∈(~R)C ∈~RR RC ∈~RC ∴ (~R)C=~RC" "7.令R是从X到Y的关系,S是Y到 Z的关系,则 (R ○ S)C= SC ○ RC 。 (注意≠RC ○ SC ) 证明:任取∈(R ○ S)C R ○ S y(y∈Y∧∈R∧∈S)  y(y∈Y∧∈SC∧∈RC) SC ○ RC 所以(R ○ S)C= SC ○ RC " "2020/2/24" "55" "8. R是A上关系,则 ⑴ R是对称的,当且仅当 RC =R ⑵ R是反对称的,当且仅当 R∩RC IA。 证明:⑴ 充分性,已知 RC =R (证出R对称) 任取x,yA 设R,则RC,而RC =R 所以有R ,所以R对称。 必要性,已知R 对称,(证出RC =R) 先证RCR,任取∈RC,则R,因R对称 所以有∈R,所以RCR。 再证R RC,任取R, 因R对称,所以有 ∈R,则∈RC, 所以RRC。 最后得RC =R 。" "2020/2/24" "56" "证明 ⑵ 充分性,已知R∩RC IA,(证出R反对称) 任取x,yA 设R 且∈R, R∧∈RR∧∈RC,  R∩RC   IA (因R∩RC IA ) x=y 所以R反对称。 必要性,已知R反对称,(证出R∩RC  IA) 任取R∩RC R∩RCR∧RC R∧R x=y (因R反对称) IA 所以R∩RC IA 。" "作业:第118页⑴ ⑵a)b)、⑶、⑸" "2020/2/24" "57" "4-6 关系的闭包运算" "关系的闭包是通过关系的复合和求逆构成的一个新的关系。 这里要介绍关系的自反闭包、对称闭包和传递闭包。" "一.例子 给定 A中关系R,如图所示, 求A上另一个关系R’,使 得它是包含R的“最小的”(序偶 尽量少)具有自反(对称、传递)性的关系。 这个R'就是R的自反(对称、传递)闭包。" "2020/2/24" "58" "这三个关系图分别是R的自反、对称、传递闭包。" "二.定义:给定 A中关系R,若A上另一个关系R′, 满足:⑴RR′; ⑵R′是自反的(对称的、传递的); ⑶R′是“最小的”,即对于任何A上自反(对称、传递)的关系R″,如果RR″,就有R′R″。则称R′是R的自反(对称、传递)闭包。记作r(R)、s(R)、t(R))(reflexive、symmetric、transitive)" "2020/2/24" "59" "三.计算方法 定理1.给定 A中关系R,则 r(R)=R∪IA。 证明:令R' =R∪IA,显然R'是自反的和R R' ,下面证明R'是“最小的”:如果有A上自反关系R"且R R",又IA R",所以 R∪IA R",即R'  R" 。所以R'就是R的自反闭包。即r(R)=R∪IA 。 定理2.给定 A中关系R,则 s(R)=R∪RC 。 证明方法与1.类似。 定理3.给定 A中关系R,则 t(R)=R∪R2∪R3∪... 。 证明:令R' = R∪R2∪R3∪..., ⑴显然有 R R' ;" "2020/2/24" "60" "⑵证R'是传递的:任取x,y,zA,设有 R'  R', 由R'定义得必存在整数i,j使得Ri , Rj ,根据关系的复合得Ri+j, 又因Ri+j  R',所以 R', ∴ R'传递。 ⑶证R'是“最小的”:如果有A上传递关系R"且RR",(证出R'  R" )任取 R' ,则由R'定义得必存在整数i,使得Ri ,根据关系的复合得A中必存在i-1个元素e1, e2,...,ei-1,使得 (见49页) R∧R∧...∧R。因RR", ∴有 R" ∧ R" ∧...∧R" 。 由于R"传递,所以有 R" 。∴ R'  R" 。 综上所述, R'就是R的传递闭包,即 t(R)=R∪R2∪R3∪…=∪Ri " "2020/2/24" "61" "用上述公式计算t(R),要计算R的无穷大次幂,好象无法实现似的。其实则不然,请看下例: A={1,2,3} A中关系R1,R2,R3,如下: R1={<1,2>,<1.3>,<3,2>} R2 ={<1,2>,<2.3>,<3,1>} R3 ={<1,2>,<2.3>,<3,3>} R12 ={<1,2>} ,R13 = R14 =Φ 所以 t(R1)= R1∪ R12 ∪ R13 = R1 R22 ={<1,3>,<2,1>,<3,2>} R23={<1,1>,<2,2>,<3,3>}, R23=IA, R24= R2 ... t(R2)= R2∪ R22∪ R23 R32 ={<1,3>,<2,3>,<3,3>} ,R33 = R32 t(R3)= R3∪R32" "2020/2/24" "62" "定理4.给定 A中关系R,如果A是有限集合,|A|=n 则 t(R)=R∪R2∪...∪Rn 。 证明:令R' =R∪R2∪R3∪..., R" =R∪R2∪...∪Rn 显然有R"  R' ,下面证明R'  R" : 任取 R',由R'定义得必存在最小的正整数i 使得Ri , (下面证明i≤n)如果i>n,根据关系的复合得A中必存在i-1个元素e1, e2,...,ei-1,使得 R∧R∧...∧R。上述元素序列: x=e0, e1, e2,...,ei-1,y=ei中共有i+1个元素,i+1>n , 而A 中只有n个元素,所以上述元素中至少有两个相同,设ej=ek (j∈Ri-(k-j),i-(k-j)∈R'', 于是 R'  R" 。 最后得 R' = R" ,所以 t(R)=R∪R2∪...∪Rn 定理证毕。 " "2020/2/24" "64" "求t(R)的矩阵Warshall算法: |X|=n, RX×X,令MR=A R2的矩阵为A2,… Rk的矩阵为Ak .于是t(R)的矩阵记作MR+=A+A2+…+Ak +… (+是逻辑加) ⑴置新矩阵 A :=MR ; ⑵置 i=1; ⑶对所有 j ,如果A[j,i] =1 ,则对k=1,2,…,n A[j,k]:=A[j,k]+A[i,k]; /*第j行+第i行,送回第j行*/ ⑷ i加1; ⑸ 如果i≤n, 则转到步骤⑶,否则停止。" "2020/2/24" "65" "举例,令X={1,2,3,4}, X中关系R图如右图所示。 运行该算法求t(R)的矩阵: " "i=1 (i---列, j---行) A[4,1]=1 L1+L4→L4" "最后 A=Mt(R)" "i=2 A[1,2]=1 A[2,2]=1 A[4,2]=1 L1+L2→L1 L2+L2→L2 L4+L2→L4" "i=3 A[1,3]=1, A[2,3]=1, A[4,3]=1 L1+L3→L1 L2+L3→L2 L4+L3→L4 " "i=4 A[1,4]=1 A[4,4]=1 L1+L4→L1 L4+L4→L4" "2020/2/24" "66" "四.性质 定理5. R是A上关系,则 ⑴ R是自反的,当且仅当 r(R)=R. ⑵ R是对称的,当且仅当 s(R)=R. ⑶ R是传递的,当且仅当 t(R)=R. 定理6. R是A上关系,则 ⑴ R是自反的,则s(R)和t(R)也自反。 ⑵ R是对称的,则r(R)和t(R)也对称。 ⑶ R是传递的,则r(R)也传递。 证明: ⑴因为R自反,由定理5得r(R)=R,即 R∪IA=R, r(s(R))=s(R)∪IA=(R∪RC)∪IA = (R∪IA)∪RC=r(R)∪RC =R∪RC =s(R)∴s(R)自反 " "2020/2/24" "67" " 类似可以证明t(R)也自反。 证明⑵. 证明t(R)对称: (t(R))C=(R∪R2∪...∪Rn∪...)C = RC∪(R2)C ∪...∪(Rn)C∪... = RC∪(RC)2 ∪...∪(RC)n∪... =R∪R2∪...∪Rn∪... (∵R对称,∴RC =R) =t(R) 所以t(R)也对称。 类似可以证明r(R)也对称。 证明⑶. 证明r(R)传递:先用归纳法证明下面结论: (R∪IA)i= IA∪R∪R2∪...∪Ri ①i=1时 R∪IA= IA∪R 结论成立。 ②假设i≤k 时结论成立,即 (R∪IA)k= IA∪R∪R2∪...∪Rk" "2020/2/24" "68" "③当i=k+1时 (R∪IA)k+1=(R∪IA)k ○ (R∪IA) = (IA∪R∪R2∪...∪Rk)○ (IA∪R) = (IA∪R∪R2∪...∪Rk)∪(R∪R2∪...∪Rk+1) = IA∪R∪R2∪...∪Rk∪Rk+1 所以结论(R∪IA)i= IA∪R∪R2∪...∪Ri成立. t(r(R))=t(R∪IA) = (R∪IA)∪(R∪IA)2∪(R∪IA)3∪... =(IA∪R)∪(IA∪R∪R2)∪(IA∪R∪R2∪R3)∪... = IA∪R∪R2∪R3∪...= IA∪t(R) = IA∪R (R传递t(R)=R) =r(R) 所以r(R)也传递。 " "2020/2/24" "69" "定理7:设R1、R2是A上关系,如果R1R2 ,则 ⑴r(R1) r(R2) ⑵s(R1) s(R2) ⑶t(R1)t(R2) 证明⑴ r(R1)=IA∪R1IA∪R2= r(R2) ⑵,⑶类似可证。 定理8:设R是A上关系,则 ⑴sr(R)=rs(R) ⑵tr(R)=rt(R) ⑶st(R)ts(R) 证明: ⑴ sr(R)=r(R)∪(r(R)c=(R∪IA)∪(R∪IA)c = (R∪IA)∪(Rc∪IAc) =R∪IA∪Rc∪IA = (R∪Rc)∪IA= s(R)∪IA=rs(R) ⑵的证明用前边证明的结论: (R∪IA)k= IA∪R∪R2∪...∪Rk可证,这里从略。" "2020/2/24" "70" "⑶ 因 Rs(R) 由定理7得 t(R)ts(R) st(R)sts(R) 因s(R)对称,有定理6得ts(R) 也对称,由定理5得 sts(R)=ts(R) 所以有st(R)ts(R) 。 证明完毕。" "练习:给定A中关系R如图所示:分别画出r(R)、s(R) 、t(R)、sr(R)、rs(R)、tr(R)、rt(R)、st(R) 、ts(R)的图。 " "2020/2/24" "72" "本节重点掌握闭包的定义、计算方法和性质。 作业:P127 ⑴、⑸、⑺、⑻ " "2020/2/24" "73" "4-7 集合的划分与覆盖" "一.定义 设X是一个非空集合,A={A1, A2,... ,An},AiΦ AiX (i=1,2,...,n),如果满足A1∪A2∪...∪An =X (i=1,2,..., n)则称A为集合X的覆盖。 设A={A1, A2,... ,An}是X一个覆盖, 且AiAj=Φ (ij,1≤i,j≤n)则称A是X的划分,每个Ai均称为这个划分的一个划分类。 例 X={1,2,3}, A1={{1,2,3}}, A2={{1},{2},{3}}, A3={{1,2},{3}}, A4={{1,2},{2,3}}, A5={{1},{3}} A1, A2 ,A3 ,A4 是覆盖。 A1, A2 ,A3也是划分。 划分一定是覆盖;但覆盖不一定是划分。" "2020/2/24" "74" "二.最小划分与最大划分 最小划分:划分块最少的划分。即只有一个划分块的划分,这个划分块就是X本身。如A1={{1,2,3}} 。 最大划分:划分块最多的划分。即每个划分块里只有一个元素的划分。如A2 ={{1},{2},{3}} 。 A1,A2,A3是一种划分,其中A1是最小划分,A2是最大划分。 " "2020/2/24" "75" "三.交叉划分 例 X是东大学生集合, A和B都是X的划分: A={M,W},MX, WX, M={男生},W={女生} B={L,N},LX, NX, L={辽宁人},N={非辽宁人}" "C={L∩M , L∩W , N∩M , N∩W }" "称C是X的交叉划分。" "2020/2/24" "76" "定义:若A={A1, A2,... ,Am}与B={B1,B2,...,Bn}都是集合X的划分,则其中所有的AiBj,组成的集合C,称为C是A与B两种划分的交叉划分。 证明:在C中任取元素, AiBjX (∵AiX,BjX) (A1B1)∪(A1B2)∪...∪(A1Bn)∪(A2B1)∪…∪ (A2Bn)∪... (AmB1)∪(AmB2)∪...∪(AmBn) =(A1( B1∪B2∪B3∪...Bn))∪(A2( B1∪B2∪B3∪... ∪Bn))∪... ∪(Am( B1∪B2∪B3∪... ∪Bn)) = (A1∪A2∪A3∪...∪Am) ( B1∪B2∪B3∪... ∪Bn) =XX=X" "2020/2/24" "77" "再验证C中任意两个元素不相交: 在C中任取两个不同元素AiBh和AjBk,考察 (AiBh)  (AjBk) (i=j和h=k不同时成立) = (AiAj)(BhBk) i=j ,h≠k (AiAj)(BhBk) =Ai= i≠j ,h≠k (AiAj)(BhBk)== i≠j, h=k (AiAj)(BhBk)= Bh = 综上所述,C是X的划分。 作业:第130页 (1)" "2020/2/24" "78" "一.等价关系 1.定义:设R是A上关系,若R是自反的、对称的和传递的,则称R是A中的等价关系。 若a,bA,且aRb,则称a与b等价。 例子,集合A={1,2,3,4,5,6,7}, R是A上的模3同余关系,即 R={|x-y可被3整除(或x/3与y/3的余数相同)} 即∈R x(mod 3)=y(mod3) " "4-8 等价关系与等价类" "2020/2/24" "79" "上例中的关系为: R={<1,1>,<1,4>,<1,7>,<2,2>,<2,5>,<3,3>,<3,6>,<4,1>,<4,4>,<4,7>,<5,2>,<6,3>,<6,6>,<7,1>, <7,4>,<7,7>}" "2.等价关系的有向图 1)完全关系(全域关系A×A)图,下面分别是当A中只有1、2、3个元素时的完全关系图。" "A={1}" "A={1,2}" "A={1,2,3}" "2020/2/24" "80" "2.等价关系的有向图 模3同余关系R的图: 从关系图可看出R是自反、对称、传递的关系,所以R是等价关系。 " "等价关系R的有向图可能由若干个独立子图(R图的一部分)构成的,每个独立子图都是完全关系图。 -上述关系R图就是由三个独立的完全图构成的。 下面给出八个关系如图所示,根据等价关系有向图的特点,判断哪些是等价关系。 " "2020/2/24" "81" "下面是A ={1,2,3}中关系:" "" "" "2020/2/24" "82" "思考题:A={1,2,3},可构造多少个A中不同的等价关系?可以根据等价关系有向图的特点来考虑。 如果等价关系R中有 a)三个独立子图的情形,则( )个等价关系 。 b)二个独立子图的情形,则( )个等价关系 。 c)一个独立子图的情形,则( )个等价关系 。 一共有( )个中不同的等价关系。 " "2020/2/24" "83" "二. 等价类" "1.定义:R是A上的等价关系,a∈A,由a确定的集合[a]R: [a]R={x|x∈A∧∈R} 称集合[a]R为由a形成的R等价类。简称a等价类。 可见 x∈[a]R ∈R 上例,A={1,2,3,4,5,6,7}, R是A上的模3同余关系, [1]R={1,4,7}= [4]R = [7]R ----余数为1的等价类 [2]R={2,5}= [5]R ----余数为2的等价类 [3]R={3,6}= [6]R ----余数为0的等价类 思考题:此例为什么只有三个等价类?" "2020/2/24" "84" "2. 由等价关系图求等价类:R图中每个独立子图上的结点,构成一个等价类。 不同的等价类个数=独立子图个数。" "上述三个等价关系各有几个等价类?说出对应的各个等价类。" "2020/2/24" "85" "3.等价类性质 R是A上等价关系,任意a,b,c∈A ⑴ 同一个等价类中的元素,彼此有等价关系R。 即任意x,y∈[a]R,必有∈R 证明:任取x,y∈[a]R,由等价类定义得∈R, ∈R ,由R对称得∈R,又由R传递得∈R。 " "2020/2/24" "86" "⑵ [a]R∩[b]R=Φ, 当且仅当 R。 证明:设R,假设[a]R∩[b]R≠Φ,则存在x∈[a]R∩[b]R,∴ x∈[a]R∧x∈[b]R, ∴∈R ,∈R,由R对称得∈R又由R传递得∈R,产生矛盾。 若[a]R∩[b]R=Φ,而∈R,由等价类定义得b∈[a]R, 又因为bRb,所以b∈[b]R,所以b∈[a]R∩[b]R,产生矛盾。 " "2020/2/24" "87" "⑶ [a]R=[b]R 当且仅当 ∈R。 证明:若∈R,则任何x∈[a]R,有∈R,由对称性得∈R,再由传递性得∈R,∴x∈[b]R,所以[a]R[b]R。 类似可证[b]R[a]R。∴ [a]R=[b]R。 如果[a]R=[b]R,由于有aRa,所以a∈[a]R ,a∈[b]R ,所以有∈R,由对称性得∈R。 ⑷.A中任何元素a,a必属于且仅属于一个等价类。 证明:A中任何元素a,由于有aRa,所以a∈[a]R ,如果 a∈[b]R ,所以有∈R. 由性质⑶得:[a]R=[b]R 。 " "2020/2/24" "88" "⑸.任意两个等价类 [a]R、[b]R, 要么[a]R=[b]R ,要么[a]R∩[b]R=Φ 。 (因为要么∈R,要么R。) ⑹. R的所有等价类构成的集合是A的一个划分。 (由性质⑷⑸即得。) (这个划分称之为商集) 性质(4)说明了覆盖性,性质(5)说明了不相交性" "2020/2/24" "89" "三. 商集" "定义:R是A上等价关系,由R的所有等价类构成的集合称之为A关于R的商集。记作A/R。即 A/R={[a]R |a∈A}" "例如A={1,2,3,4,5,6,7} , R上模3同余关系,则 A/R= {[1]R,[2]R,[3]R} ={{1.4.7},{2,5},{3,6}}" "2020/2/24" "90" "练习: X={1,2,3},X上关系R1、R2 、R3,如上图所示。 X/R1={[1]R1,[2]R1,[3]R1}={{1},{2},{3}} X/R2={[1]R2 ,[2]R2}={{1},{2,3}} X/R3={[1]R3}={{1,2,3}}" "2020/2/24" "91" "定理: 集合A上的等价关系R,决定了A的一个划分,该划分就是商集A/R。 证明:由等价类性质可得 : 1) A/R中任意元素[a]R,有[a]RA。 2) 设[a]R,[b]R是A/R的两个不同元素,有[a]R[b]R=Φ 3) 因为A中每个元素都属于一个等价类,所以所有等价类的并集必等于A。 所以商集A/R是A的一个划分。 定理: 设R1和R2是非空集合A上的等价关系,则 A/R1=A/R2 当且仅当 R1=R2 。 (这个定理显然成立。) " "2020/2/24" "92" "四. 由划分确定等价关系" "例如,X={1,2,3,4}," "A={{1,2},{3},{4}}, A是X的一个划分, 求X上一个等价关系R,使得X/R=A。 显然由图可得:R={1,2}2∪{3}2∪{4}2 。" "一般地A={A1,A2,…,An}是X的一个划分,则构造一个X中的等价关系R,使得X/R=A。R=A12∪A22∪,…,∪An2 其中Ai= Ai2×Ai2, 下面证明R是X中的等价关系。" "定理: 集合X的一个划分可以确定X上的一个等价关系。 证明:假设A={A1, A2,... ,An}是X的一个划分,如下构造X 上的一个等价关系R: R=A12∪A22∪…∪An2,其中Ai2=Ai2×Ai2, 1) 证R自反:任取a∈X,因为A是X的划分,必存在 AiA使aAi ,于是∈Ai×Ai , 又Ai×Ai R ∴有aRa。 2) 证R对称:任取a,b∈X, 设aRb,必存在AiA使得 ∈Ai×Ai ,于是a,bAi , bRa, R是对称的。 3) 证R传递:任取a,b,c∈X, 设aRb,bRc, 必存在AiA使得∈Ai×Ai ,∈Ai×Ai ,于是a,b,cAi , 所以∈Ai×Ai ,又Ai×Ai R ∴有aRc 所以R传递。最后得R是集合X中的等价关系。" "2020/2/24" "94" "本节重点: 等价关系概念、证明。 等价类概念、性质。 求商集。 作业:P134 ⑴、⑵、⑷、⑹、⑺" "2020/2/24" "95" "4-9 相容关系" "定义:给定集合X上的关系r, 若r是自反的、对称的,则r是A上相容关系。 例子:X 是由一些英文单词构成的集合。 X={fly, any, able, key, book, pump, fit}, X上关系r: r={<α,β>|α∈X,β∈X且α与β含有相同字母}" "2020/2/24" "96" "r的有向图: 看出有自反、 对称性。而 不传递。 " "相容关系的简化图和简化矩阵" "图的简化:⑴不画环; ⑵两条对称边用一条无向直线代替。 " "矩阵的简化:因为r的矩阵是对称阵且主对角线全是1,用下三角矩阵(不含主对角线)代替r的矩阵。" "令x1=fly, x2= any, x3= able, x4=key, x5=book, x6= pump, x7= fit, X={x1 ,x2, x3, x4, x5, x6 ,x7}, r的简化图为:" "2020/2/24" "98" "相容类及最大相容类" "定义:设r是集合X上的相容关系,CX,如果对于C中任意元素x,y有∈r ,称C是r的一个相容类。 上例中{x1,x2},{x3,x4},{x1,x2,x3},{x2,x3,x4},{x1,x2, x4}, {x3,x4,x5},{x1,x3,x4},{x1,x2,x3,x4},{x1,x7},{x6} 都是相容类。上述相容类中,有些相容类间有真包含关系。" "定义:设r是集合X上的相容关系,C是r的一个相容类,如果C不能被其它相容类所真包含,则称C是一个最大相容类。 也可以说,C是一个相容类,如果C中加入任意一个新元素,就不再是相容类,C就是一个最大相容类。 {x1,x2,x3,x4} , {x3, x4, x5}, {x1,x7} , {x6}都是最大相容类。" "2020/2/24" "99" "从简化图找最大相容类:----找最大完全多边形。 即:含有结点最多的多边形中,每个结点都与其它结点相联结。" "在相容关系简化图中,每个最大完全多边形的结点集合构成一个最大相容类。 上例中最大相容类{x1,x2,x3,x4}, {x3, x4,x5}, {x1,x7}, {x6}分别对应最大完全四、三、一、零边形。" "2020/2/24" "100" "给定X上相容关系r' ,如图所示, r'的最大相容类:{x1,x2,x5}, {x2, x3, x5}, {x3, x4,x5}, {x1,x4 ,x5}, " "完全覆盖: 定义:r是X中的相容关系,由r的所有最大相容类为元素构成的集合,称之为X的完全覆盖。记作Cr(X)。 Cr(X)={{x1,x2,x3,x4}, {x3, x4, x5},{x1,x7},{x6}} Cr’(X)={{x1,x2,x5},{x2, x3, x5}, {x3, x4, x5}, {x1,x4 ,x5}} " "作业 P139 (2) " "2020/2/24" "101" "4-10 次序关系" "一. 偏序(半序)关系(partial order relation)" "[定义]:R是A上自反、反对称和传递的关系,则称R是A上的偏序关系。并称是偏序集。 例如数值的≤、≥关系和集合的都是偏序关系。 用符号“≤”表示任意偏序关系,但要注意“≤”不一定是“小于或等于”的含义。" "例1 A={1,2,4,6}, ≤是A中的整除关系,其关系图如右图,显然≤是自反、反对称和传递的,即它是个偏序。" "2020/2/24" "102" "注: (1)用矩阵表示半序关系,不能明显看到二元关系的特征。 (2)用简化的关系图表示较适合。 " " 简化的关系图: (1)自反性:每个顶点都有自回路,省去。 (2)反对称性:两个顶点间只可能有一个箭头从左→右,或从下→上的方向从小到大安置顶点,可省略箭头。 (3)传递性:由于有(a,b),(b,c)∈R 则(a,c) ∈R 故只画(a,b),(b,c)对应的边,省略边(a,c)。 " "2020/2/24" "103" "[定义]:Hasse图 设≤是A上的一个半序关系,如果a≤b ,则将a画在b下面,且不c,使a≤c,c≤b,则a,b间用直线连接。并符合简化的关系图的绘制,称这样得到关系图为Hasse图。" "例: A={1,2,3,4,5,6,7,8,9} B={a,b,c} R1={(a,b)| a≤b,a,b∈A} R2={(a,b)| a|b,a,b∈A} R3={(s1,s2)|s1s2,s1,s2∈p(B)}" "2020/2/24" "104" "2020/2/24" "105" "[定义] 全序: A上半序关系R,如果a,b∈A,都有a≤b,或b≤a,则称R为A上的全序关系。" "二.全序(线序、链)" " 全序的含义:A中每两个元素均能比大小,即任何两个元素都相关。 半序则是部分有序。 R1是全序,R2,R3都是半序 如:R2中,{1,2,6},{1,2,4,8},{1,3,9}都排成了序,但2与3,5与7,7与9…,在整除的意义上来说无法排出大小来。" "2020/2/24" "106" "练习: C={1,2,3,6,12,24,36}, D={1,2,3,5,6,10,15,30} ≤ 是C、D上整除关系:<C,≤>, <D,≤>的Hasse图:" "2020/2/24" "107" "三. 偏序集中的重要元素" "y是B的极小元  y(y∈A∧x(x∈A∧x≠y∧x≤y)) y是B的极大元  y(y∈A∧x(x∈A∧x≠y∧y≤x)) " "[定义]极大元与极小元: 设(P,≤)是半序集,AP,若a∈A,且在A中找不到一个元素b(b≠a),使a≤b(b≤a),则称a为A中的极大元(极小元)。" "2020/2/24" "108" "例(N,|)是半序集,A={2,3,4,5,6,7,8,9}则 A中极大元:8,6,9,5,7 极小元:2,3,5,7 注: 极大元,极小元并不要求唯一,且同一元素,可以既是极大元,又是极小元,如5,7。 极大元,极小元必须是子集A中的元素。" "2020/2/24" "109" "[定义] 最大元与最小元: 设(P,≤)是半序集,AP,若a∈A,b∈A,b≤a(a≤b),则称a为A的最大元(最小元)。" "例:上例 其Hasse图如下图所示" "结论:子集A中是不存在最大元(最小元)的。" "2020/2/24" "110" "[定理]是偏序集,B是A的非空子集,如果B有最小元(最大元),则最小元(最大元)是唯一的。 证明:假设B有两个最小元a、b,则 因为a是最小元,b∈B,根据最小元定义,有a≤b; 类似地,因为b是最小元,a∈B,根据最小元定义,有b≤a。因为≤有反对称性,所以有a=b。 同理可证最大元的唯一性。 小结:是偏序集,B是A的非空子集,则 ⑴ B的极小(大)元总是存在的,就是子集中处在最下(上)层的元素是极小(大)元。 ⑵ B的最小元(最大元)有时可能不存在,只要有唯一的极小(大)元,则这个极小(大)元就是最小(大)元。否则就没有最小(大)元。" "2020/2/24" "111" "[定义]上界与下界: 设(P,≤)是半序集,AP,若a∈P,对 b∈A,b≤a(a≤b)称a为A的上界(下界)。" "例:B={a,b,c},R3={ (s1,s2) | s1 s2,s1∈P(B) }, (P(B), )是半序集。 设A={Ф,{a},{b},{c},{a,c},{a,b},{a,c}} 其Hasse图如右图所示:" "2020/2/24" "112" "注: (1)上例中,A无最大元,但存在A的上界{a,b,c}。 (2)Ф为A的最小元,也是A的下界 (3)最大(小)元是A的一个上(下)界 (4)上(下)界可以不唯一,也可以不存在" "[定义]上确界与下确界: 设(p,≤)是半序集,AP,若a是A的一个上界(下界),而A的上界(下界)b,都有a≤b(b≤a),则称a是A的上确界(下确界)。" "2020/2/24" "113" "注: 上确界:最小上界 下确界:最大下界 如果存在上(下)确界,则上(下)确界一定是唯一的" "举例,给定的Hasse图如图所示:" "2020/2/24" "114" "* 四.良序" "[定义]是偏序集,如果对A的任何非空子集B ,都有最小元,则称≤是A上的良序,并称为良序集。 例如N是自然数集合,I是整数集合,≤是小于等于关系,就是良序集。而不是良序集。 定理 所有良序集,一定是全序集。 证明 设为良序集,任取x,y∈A,则{x,y} A, 它有最小元,该最小元或是x,或是y, 于是有x≤y或y≤x,所以是全序集。 定理 有限的全序集,一定是良序集。 证明 设A={a1,a2,…an},是全序集,假设它不是良序,必存在非空子集BA,B中无最小元,因B是有限集,必存在x,y∈B,使得x y,与≤是全序矛盾,∴是良序集。" "2020/2/24" "115" "本节要求: 掌握偏序 、全序的概念, 会画Hasse图, 会求重要元素。 作业: P145 (1), (6),(7) " "本章小结" "归纳:关系性质证明方法(设R是A上关系)" "一.证明R的自反性: 方法1 用自反定义证:任取 x∈A,证出∈R. 方法2 用恒等关系IA证:证出IA R. ( P119 (2) b) ) 方法3 用自反闭包证:证出r(R)=R, 即R∪IA=R. 二.证明R的反自反性: 方法1 用反自反定义证:任取 x∈A,证出R. 三.证明R的对称性: 方法1 用对称定义证: 任取 x,y∈A,设∈R, 证出 ∈R. 方法2 用求逆关系证:证出 Rc=R. 方法3 用对称闭包证:证出 s(R)=R, 即R∪Rc =R." "四.证明R的反对称性: 方法1 用定义1证: 任取 x,y∈A, 设∈R, ∈R.证出 x=y。 方法2 用定义2证: 任取 x,y∈A,x≠y, 设∈R, 证出R. 方法3 用定理证:证出 R∩Rc  IA . (见教材P118)" "2020/2/24" "119" "五.证明R的传递性: 方法1 用传递定义证: 任取 x,y,z∈A,设∈R,∈R, 证出 ∈R 方法2 用传递闭包证:证出 t(R)=R, 即 R∪R2∪R3∪... =R. 方法3 用定理证:证出 R2  R ( P119 (2) a) ) " "第四章习题课" "P104 ⑴b) A={0,1} B={1,2} 求 A2×B。 AB={|xA∧yB} A2 =A×A ={<0,0>,<0,1>,<1,0>,<1,1> } A2×B = <<0,0>,1>,<<0,1>,1>, <<1,0>,1>, <<1,1>,1>, <<0,0>,2>, <<0,1>,2>, <<1,0>,2>,<<1,1>,2> }" "2020/2/24" "121" "P109 ⑴ X={a,b,c} Y={s} X到Y的所有关系: X×Y={,,} X×Y的任何一个子集都是一个 从X到Y的关系。如果 |X|=m |Y|=n则有2mn个从X到Y的关系, 故,有23=8个关系: R0=Φ R1={} R2={} R3={} R4={,} R5={,} R6={,} R7={,,} " "⑵ 设|A|=n ,有多少个A上的关系? 因为RA×A,所以A×A有多少个子集就有多少个A上关 系,由集合的幂集就是该集合的子集构成的,所以A上关系 个数就是A×A 的幂集P(A×A)的元素个数|P(A×A)|, 而 2|A×A|=2nn=2n2 。所以有2n2个不同的A上关系。 P113 ⑴ A={1,2,3},A上五个关系如下:(T略有改动)" "上述五个关系中, 哪些是等价关系?如果是等价关系,求其商集。 哪些是相容关系?如果是相容关系,求其完全覆盖。 哪些是偏序关系?如是偏序关系,画Hasse图,并求A的极 小(大)元、最小(大)元、上界与下界、上确界和下确界。 等价关系:S和A×A,对应的商集分别是: A/S={{1,2},{3}} A/A×A={{1,2,3}} 相容关系: S和A×A,对应的完全覆盖分别是: CS(A)={{1,2},{3}} CA×A(A)={{1,2,3}} 偏序关系: T A的极小元、最小元、下界、下确界都是:1 A的极大元、最大元、上界、上确界都是:3 " "c) R和S都对称,R◦S不一定对称。" "举反例:" "第118页 ⑴ R和S都是A上关系, a) R和S都自反,R◦S一定自反。 b) R和S都反自反,R◦S不一定反自反。" " 举反例:" "d) R和S都传递,R◦S不一定传递。" " 举反例:" "⑵ S是X上关系。 a)证明S传递,当且仅当 S 2  S (可用此定理判定传递) 证明:充分性,已知 S 2  S 任取x,y,z∈X, 且有∈S,∈S, 根据关系的复合得∈ S 2 ,由已知得∈S ,所以S传递。 必要性,已知S传递,任取∈ S 2 ,根据关系的复合得z(z∈X∧∈S∧∈S),由S传递得∈S 所以S 2  S " "2020/2/24" "126" "b)证明S自反,当且仅当 IXS。 (可用此定理判定自反) 证明:充分性,已知IXS, 任取x∈X, 有∈IX , 由已知得∈S, 所以S自反。 必要性,已知S自反, 任取∈IX , 得x=y, 而S自反,所以∈S∴ IXS " "⑶ S是X上关系,证明S是自反和传递,则 S 2 =S。其逆为真吗? 证明 由⑵a)得S传递,则 S 2  S ,只证明S S 2   任取∈S, 又已知S自反,所以∈S,于是有∈S∧∈S,由关系的复合得∈ S 2 所以有S S 2 ,最后得S 2 =S。  其逆不一定为真。例如S如图所示: 它满足  S 2 =S,但S不自反。" "2020/2/24" "128" "⑸ R是A上关系, a) R自反,Rc也自反。 因为任取x∈A,因R自反,所以∈R,∴ ∈ Rc b) R对称,Rc也对称。 因为R对称,所以Rc =R ∴ Rc也对称。 " "c) R传递,Rc也传递。 方法1 . 任取x,y,z∈A, 且有∈Rc ,∈Rc, 于是∈R ,∈R,因R传递,∴∈于是有∈Rc,∴ Rc传递。 方法2. t(Rc)=Rc∪(Rc)2∪(Rc)3∪… = Rc∪(R2)c∪(R3)c∪… = (R∪R2∪R3∪…)c = (t(R))c=Rc (因为R传递,所以t(R)=R ) 所以Rc传递。 (R2)c=(R◦R)c=(Rc ◦Rc)= (Rc)2" "P113(4) R和S都A上是自反、对称、传递的,求证R∩S也是自反、对称和传递的。 证明:一.证明R∩S的自反性 方法1 用自反定义证:任取 x∈A, (证出∈R∩S) 因R和S都自反,所以有∈R,∈S,于是有 ∈R∩S,所以R∩S也自反。 方法2 用恒等关系IA证:(证出IA R∩S) 方法3 用自反闭包证: (证出r(R∩S)=R∩S, 即 (R∩S)∪IA= R∩S) 因R和S都自反,所以r(R)=R, r(S)=S, r(R∩S)=(R∩S)∪IA= (R∪IA)∩(S∪IA)= r(R)∩r(S)=R∩S 所以R∩S也自反。" "二.证明R∩S的对称性: 方法1 用对称定义证: 任取 x,y∈A,设∈R∩S, (证出 ∈R∩S.) 方法2 用求逆关系证:(证出 (R∩S)c=R∩S.) 因为R和S对称,所以有Rc=R, Sc=S,而 (R∩S)c=Rc∩Sc= R∩S , ∴R∩S对称。 方法3 用对称闭包证: (证出 s(R∩S)=R∩S, 即(R∩S)∪(R∩S)c =R∩S.) 因为R和S对称,所以s(R)=R,s(S)=S s(R∩S)= (R∩S)∪(R∩S)c =(R∩S)∪(Rc∩Sc) =(R∪Rc)∩(R∪Sc)∩(S∪Sc)∩(S∪Rc) =(s(R)∩(R∪Sc))∩(s(S)∩(S∪Rc)) =(R∩(R∪Sc))∩(S∩(S∪Rc))=R∩S ∴R∩S对称。" "三.证明R的传递性: 方法1 用传递定义证:任取 x,y,z∈A, 设∈R∩S,∈R∩S, (证出∈R∩S) ∈R∩S∧∈R∩S  ∈R∧∈S∧∈R∧∈S  (∈R∧∈R)∧(∈S ∧∈S)  ∈R∧∈S (因为R、S传递)  ∈R∩S 所以R∩S传递。 方法2 用传递闭包证:证出 t(R∩S)=R∩S, 即 (R∩S)∪(R∩S)2∪(R∩S)3∪... =R∩S. 方法3用定理证:证出(R∩S)◦(R∩S) (R∩S) 用方法2、方法3证明此题的传递性有很大难度。R(S∩T)(RS)∩(RT)" "P127(1)R的有向图如图所示,求r(R)、s(R)、t(R)。 (5)R1和R2是A上关系,且R2 R1,求证 a) r(R2) r(R1), b) s(R2) s(R1), c) t(R2) t(R1)。 证明:a) r(R2)=R2∪IAR1∪IA=r(R1), b) s(R2)= R2∪(R2)cR1∪(R1)c =s(R1), (因为R2 R1 ,所以 (R2)c(R1)c ) c) 先用归纳法证明(R2)i(R1)i , ⑴i=1时, R2 R1 显然结论成立 ⑵假设i≤k时,结论成立,即(R2)i(R1)i ; ⑶i=k+1时, (R2)k+1= (R2)k R2(R1)k R1=(R1)k+1 , t(R2)=R2∪(R2)2∪...∪(R2)k∪...  R1∪(R1)2∪...∪(R1)k∪…= t(R1)。c)的另一证法:" "" "" "" "c) 因为R2R1,又 R1t(R1), 所以R2t(R1) 。于是有 t(R2)和 t(R1)都是包含R2的传递关系,而t(R2) 是包含R2的 最小的传递关系,所以t(R2) t(R1)。 (7). R1和R2是A上关系,求证 a) r(R1∪R2)= r(R1)∪r(R2) , b) s(R1∪R2)= s(R1)∪s(R2) , c) t(R1)∪t(R2)  t(R1∪R2) , 证明:a) r(R1∪R2)= (R1∪R2)∪IA = (R1∪IA) ∪(R2∪IA)=r(R1)∪r(R2) , b) s(R1∪R2)= (R1∪R2)∪(R1∪R2)c =(R1∪R2)∪(R1)c ∪(R2)c =(R1∪(R1)c )∪(R2∪(R2)c) =s(R1)∪s(R2) , c) 因 R1 (R1∪R2)且R2 (R1∪R2),由题(5)得 t(R1)t(R1∪R2), t(R2)t(R1∪R2),所以有 t(R1)∪t(R2)  t(R1∪R2)。" "(8). R是A上关系,R*=tr(R), 求证: a) (R+)+=R+ b) R◦R*=R+=R*◦R c)(R*)*=R* R+ = t(R)= R∪R2∪R3∪…= R*=rt(R)=IA∪R∪R2∪R3∪...= 证明:a) (R+)+=t(t(R)), 因为t(R)是传递的,所以t(t(R))=t(R) , 即(R+)+=R+ 。 b) R◦R*=R◦(IA∪R∪R2∪R3∪... ) ∵复合对并可分配, =R∪R2∪R3∪…= R+。 类似可证 R*◦R= R+ c)(R*)*=tr(tr(R))=trtr(R)=trrt(R) (∵tr(R)=rt(R)) =trt(R) (∵rt(R)是自反的,∴rrt(R)=rt(R)) =ttr(R) =tr(R)(∵tr(R)是传递的,∴ttr(R)=tr(R)) =R*" "第130页(1).X是集合,且|X|=4,X有多少个不同的划分? 解. 第134页(2). X是集合,且|X|=4,X上有多少个不同的等 价关系? 解. 此题的答案与上题一样。因为每个划分对应一个等价 关系。" "(4).R是A上关系, 设 S={|c∈A∧∈R∧∈R} 求证若R是等价关系,则S也是等价关系。 证明:a)证S自反:任取a∈A,∵R是自反的,∴有 ∈R,由S定义得∈S, (S定义中c就是a)∴ S自反. b)证S对称: 任取a,b∈A,且有∈S,由S定义得 c∈A∧∈R∧∈R, 由R对称得 c∈A∧∈R∧∈R,由S定义得∈S,S对称. c)证S传递:任取a,b,c∈A,有∈S,∈S,由S定义得 (d∈A∧∈R∧∈R)∧(e∈A∧∈R∧∈R) , 由于R传递,所以有∈R,∈R, 由S定义得∈S, 所以S传递. 所以S是A上等价关系. (6). R是A上对称和传递的关系,证明如果a∈A,b∈A, 使得∈R,则R是一个等价关系. 证明:任取a∈A,有已知得b∈A,使得∈R,由R对称 得∈R,又由R传递得, ∈R,R自反, ∴R是等价 关系." "(1)(7).R和S都是A上等价关系,下面哪个是A上等价关系? 证明或举反例说明. a) R∪S b) R∩S c) ~R (即A×A-R) d) R-S e)R2 f) r(R-S) 解.a) c) d) f)不是. 请看反例:" "" "" "" "" "b). R∩S是等价关系, 前面已经证明过.(第113页题(4)) e).①证R2自反,任取a∈A,因为R自反,所以∈R,根据关系的复合得,∈R R, 即∈R2,所以R2自反。 ②证R2对称, (R2)c=(Rc)2=R2 (由R对称得Rc=R) ∴R2对称 ③证R2传递,任取a,b,c∈A,设有∈R2,∈R2, 根据关系的复合得, (d∈A∧∈R∧∈R)∧(e∈A∧∈R∧∈R) , 由于R传递,所以有∈R,∈R, ∴∈R2 所以R2传递。最后得R2是等价关系。 第139页(2) . X={x1,x2, x3, x4, x5, x6}, R是X上相容关系, 其简化关系矩阵如下:求X的完全覆盖。 解. R的简化图为: CR(X)={{x1,x2,x3,},{x1,x3,x6},{x3,x4,x5},{x3,x5,x6}}" "o" "第145页(1).给定集合 {3,5,15},{1,2,3,6,12},{3,9,27,54}, ≤为整除关系,分别画出上述集合上的≤的关系图, Hasse图,并指出哪些是全序关系。 " "(6) P={x1,x2, x3, x4, x5}, P上偏序关系的 Hasse图如图所示,求子集 {x1,x2, x3}, {x2, x3, x4},{x3, x4, x5}和P的极小(大)元、 最小(大)元、上界、下界、最小上界和 最大下界(上确界和下确界)。








































 版权投诉/申诉   非法内容举报    本页不提供全部页面预览,未展示部分请购买并下载后观看使用