标签:   离散   数学   基础   洪帆   第二章   关系  
文档信息
上传用户 ༈དཔལ་     
文档格式 ppt
文档价格 7.6 元
文档大小 1 MB
文档页数 54 页
相关文档推荐
doc 实验小学二年级数学下学期开学考试试题江西版B卷 含答案
doc 广东省重点小学四年级数学下学期期末摸底考试试卷A卷 (附答案)
doc 2019-2020学年高二英语上学期第二次阶段性考试试题
doc 实验小学二年级数学下学期开学考试试题浙教版 附答案
doc 实验小学二年级数学下学期开学考试试题沪教版(II卷) 含答案
doc 实验小学二年级数学下学期开学考试试题沪教版 附解析
doc 山东省重点小学三年级数学【上册】开学摸底考试试题 附答案
doc 2019-2020年高三上学期期中调研政治试卷含答案
doc 实验小学二年级数学下学期开学考试试题江西版(I卷) 含答案
doc 云南省2020年实验小学一年级数学开学考试试卷(II卷) 含答案
doc 实验小学二年级数学下学期开学考试试题沪教版(II卷) 附答案
doc 2020年一级建造师《建筑工程管理与实务》练习题C卷 (含答案)
ppt 《技术贸易理论》PPT课件
doc 2020年一级建造师《建筑工程管理与实务》练习题B卷 附答案
doc 云南省2020年实验小学一年级数学期中检测试题C卷 含答案
ppt 《技能给排水培训》PPT课件
doc 实验小学二年级数学下学期开学考试试题沪教版C卷 附答案
doc 实验小学二年级数学下学期开学考试试题江西版A卷 附答案
ppt 《技术经济学概述》PPT课件
doc 山东省重点小学三年级数学【上册】开学考试试卷 (含答案)
doc 云南省2020年实验小学一年级数学期中考试试卷B卷 含答案
doc 2020年一级建造师《建筑工程管理与实务》练习题(II卷) 含答案
doc 2020年六年级数学【上册】期末考试试卷长春版B卷 附答案
ppt 离散数学图论-图的基本概念
doc 云南省2020年实验小学一年级数学期中测试试卷C卷 含答案
doc 2020年一级建造师《建筑工程管理与实务》练习题D卷 (附答案)
ppt 《技术部岗位职责》PPT课件
doc 实验小学二年级数学下学期开学考试试题沪教版 附答案
doc 2020年一级建造师《建筑工程管理与实务》练习题C卷 附答案
doc 山东省重点小学三年级数学【上册】开学摸底考试试题 (含答案)
doc 实验小学二年级数学下学期开学考试试题沪教版(I卷) 附答案
doc 广东省重点小学四年级数学下学期期末摸底考试试卷B卷 (附解析)
doc 2020年六年级数学【上册】期末考试试题上海教育版 附解析
doc 实验小学二年级数学下学期开学考试试题浙教版A卷 附答案
doc 2020年一级建造师《建筑工程管理与实务》练习题(I卷) (含答案)
doc 广东省重点小学四年级数学下学期期末摸底考试试卷A卷 附答案
doc 广东省重点小学四年级数学下学期期中考试试题(I卷) (附答案)
doc 云南省2020年实验小学一年级数学期中测试试题C卷 含答案
doc 2019-2020年高三上学期期中调研测试数学试题
doc 云南省2020年实验小学一年级数学期中测试试卷(II卷) 含答案
doc 云南省2020年实验小学一年级数学期中检测试题A卷 含答案
doc 2019-2020学年高二英语上学期第二次段考试题
doc 实验小学二年级数学下学期开学考试试题江西版(II卷) 附解析
ppt 《把关人与传播控制》PPT课件
doc 2019-2020年高三上学期期中调研测试化学试题含答案
doc 山东省重点小学三年级数学【上册】开学考试试题 含答案
doc 2020年六年级数学【上册】期末考试试卷长春版B卷 含答案
doc 云南省2020年实验小学一年级数学期中测试试题(II卷) 含答案
ppt 离散数学期末试题seu
doc 2020年六年级数学【上册】期末考试试题上海教育版 (附解析)
doc 实验小学二年级数学下学期开学考试试题江西版(II卷) 含答案
ppt 《技术设计的种类》PPT课件
doc 2019-2020年高三上学期期中调研考试 语文
doc 山东省重点小学三年级数学【上册】开学考试试卷 (附解析)
doc 实验小学二年级数学下学期开学考试试题沪教版B卷 附解析
doc 2019-2020学年高二英语上学期第二次阶段性考试试题(含解析)
doc 广东省重点小学四年级数学下学期期中考试试题(I卷) 附答案
doc 2020年六年级数学【上册】期末考试试卷长春版(II卷) 含答案
doc 云南省2020年实验小学一年级数学开学考试试题(I卷) 含答案
doc 实验小学二年级数学下学期开学考试试题沪教版C卷 含答案
doc 2020年一级建造师《建筑工程管理与实务》练习题C卷 含答案
doc 2019-2020学年高二英语上学期第二次段考(12月)试题
doc 2020年六年级数学【上册】期末考试试卷长春版C卷 附解析
ppt 《技能大比武解读》PPT课件
doc 2019-2020年高三上学期期中调研测试语文试题 (I)
ppt 《把不可能变成可能》PPT课件
ppt 《技术试验及其方法》PPT课件
doc 2019-2020年高三上学期期中语文试题 含解析
doc 2019-2020年高三上学期期中调研测试数学理试题含答案
doc 2019-2020年高三上学期期中调研政治试题含答案
doc 实验小学二年级数学下学期开学考试试题沪教版A卷 附答案
doc 2020年六年级数学【上册】期末考试试题上海教育版 (附答案)
doc 2020年六年级数学【上册】期末考试试卷长春版 附解析
doc 2020年六年级数学【上册】期末考试试卷长春版A卷 含答案
ppt 离散数学电子教案
ppt 《抄税处理税控机》PPT课件
doc 云南省2020年实验小学一年级数学开学考试试卷(I卷) 含答案
doc 实验小学二年级数学下学期开学考试试题沪教版(I卷) 含答案
doc 广东省重点小学四年级数学下学期期中考试试题(I卷) (附解析)
doc 2019-2020年高三上学期期中调研测试化学试题含解析
doc 2020年一级建造师《建筑工程管理与实务》练习题D卷 附解析
doc 实验小学二年级数学下学期开学考试试题沪教版B卷 附答案
doc 2019-2020年高三上学期期中调研数学试题
doc 云南省2020年实验小学一年级数学期中检测试卷C卷 含答案
doc 山东省重点小学三年级数学【上册】开学考试试卷 含答案
doc 山东省重点小学三年级数学【上册】开学考试试卷 附解析
doc 山东省重点小学三年级数学【上册】开学摸底考试试题 附解析
ppt 离散数学命题逻辑等值演算
doc 云南省2020年实验小学一年级数学期中检测试卷B卷 含答案
doc 云南省2020年实验小学一年级数学期中测试试卷B卷 含答案
doc 实验小学二年级数学下学期开学考试试题沪教版C卷 附解析
doc 实验小学二年级数学下学期开学考试试题江西版(I卷) 附答案
doc 山东省重点小学三年级数学【上册】开学摸底考试试题 (附答案)
ppt 离散数学命题逻辑
doc 云南省2020年实验小学一年级数学期中测试试卷(I卷) 含答案
doc 山东省重点小学三年级数学【上册】期中摸底考试试卷 (附答案)
doc 2020年六年级数学【上册】期末考试试卷长春版C卷 附答案
doc 2020年六年级数学【上册】期末考试试卷长春版C卷 含答案
doc 2019-2020年高三上学期期中调研生物试题 含答案
doc 2020年六年级数学【上册】期末考试试卷长春版(I卷) 附解析
doc 实验小学二年级数学下学期开学考试试题浙教版B卷 含答案
doc 2019-2020年高三上学期期中调研生物试题含答案
ppt 《技术经济学讲》PPT课件
doc 2019-2020年高三上学期期中调研测试语文试题
doc 云南省2020年实验小学一年级数学开学考试试题B卷 含答案
doc 2020年六年级数学【上册】期末考试试卷长春版(II卷) 附答案
doc 云南省2020年实验小学一年级数学期中检测试卷A卷 含答案
doc 云南省2020年实验小学一年级数学期中测试试卷A卷 含答案
doc 云南省2020年实验小学一年级数学期中检测试卷(I卷) 含答案
ppt 《技能鉴定培训》PPT课件
doc 实验小学二年级数学下学期开学考试试题沪教版 含答案
doc 2020年一级建造师《建筑工程管理与实务》练习题(II卷) (含答案)
doc 广东省重点小学四年级数学下学期期末摸底考试试卷B卷 (含答案)
doc 2020年一级建造师《建筑工程管理与实务》练习题(II卷) (附答案)
doc 实验小学二年级数学下学期开学考试试题沪教版B卷 含答案
doc 2019-2020年高三上学期期中语文试题
doc 2019-2020学年高二英语上学期第二次段考12月试题
doc 山东省重点小学三年级数学【上册】开学考试试题 (附答案)
doc 2020年六年级数学【上册】期末考试试卷长春版(I卷) 附答案
doc 广东省重点小学四年级数学下学期期中考试试题(I卷) 附解析
doc 实验小学二年级数学下学期开学考试试题沪教版A卷 附解析
doc 山东省重点小学三年级数学【上册】开学考试试题 (附解析)
doc 山东省重点小学三年级数学【上册】开学考试试题 附解析
doc 实验小学二年级数学下学期开学考试试题浙教版A卷 含答案
doc 2020年一级建造师《建筑工程管理与实务》练习题D卷 附答案
ppt 离散数学图的基本概论
doc 2019-2020年高三上学期期中调研测试数学试题 含答案
doc 实验小学二年级数学下学期开学考试试题江西版B卷 附解析
doc 山东省重点小学三年级数学【上册】开学考试试卷 附答案
doc 云南省2020年实验小学一年级数学期中检测试卷(II卷) 含答案
doc 实验小学二年级数学下学期开学考试试题江西版C卷 附解析
doc 2020年六年级数学【上册】期末考试试卷长春版B卷 附解析
doc 2019-2020学年高二英语上学期第二次统考试题
doc 2019-2020年高三上学期期中调研测试数学试卷含答案
ppt 《技术进步与》PPT课件
doc 2019-2020年高三上学期期中调研政治试卷 含答案
doc 云南省2020年实验小学一年级数学期中检测试题(I卷) 含答案
doc 2020年六年级数学【上册】期末考试试题上海教育版 (含答案)
ppt 《技术问题总结》PPT课件
doc 2020年六年级数学【上册】期末考试试卷长春版A卷 附解析
doc 山东省重点小学三年级数学【上册】开学考试试卷 (附答案)
doc 云南省2020年实验小学一年级数学开学考试试题A卷 含答案
ppt 《技术进步与发展》PPT课件
ppt 离散数学是研究离散数量关系和离散结构数学模型的数学
doc 实验小学二年级数学下学期开学考试试题浙教版 含答案
doc 广东省重点小学四年级数学下学期期末摸底考试试卷A卷 (附解析)
doc 2020年六年级数学【上册】期末考试试卷长春版(II卷) 附解析
doc 实验小学二年级数学下学期开学考试试题江西版(I卷) 附解析
doc 山东省重点小学三年级数学【上册】开学摸底考试试题 含答案
doc 2019-2020学年高二英语上学期第二次质量检测试题
doc 云南省2020年实验小学一年级数学期中检测试题B卷 含答案
doc 实验小学二年级数学下学期开学考试试题沪教版(I卷) 附解析
ppt 《技术部岗位职责新》PPT课件
doc 2019-2020年高三上学期期中调研化学试题含答案
doc 2019-2020学年高二英语上学期第二次月考试题(无答案)
doc 2019-2020年高三上学期期中调研化学试题含解析
doc 实验小学二年级数学下学期开学考试试题江西版B卷 附答案
ppt 离散数学第11章格与布尔代数
doc 广东省重点小学四年级数学下学期期末摸底考试试卷A卷 (含答案)
ppt 《技法总论短文改错》PPT课件
ppt 《技能自我探索》PPT课件
doc 实验小学二年级数学下学期开学考试试题浙教版A卷 附解析
doc 2020年一级建造师《建筑工程管理与实务》练习题(II卷) (附解析)
doc 云南省2020年实验小学一年级数学期中检测试题(II卷) 含答案
doc 2020年六年级数学【上册】期末考试试卷长春版(I卷) 含答案
ppt 《把人往好处想》PPT课件
doc 2020年六年级数学【上册】期末考试试卷长春版A卷 附答案
doc 广东省重点小学四年级数学下学期期中考试试题(I卷) 含答案
doc 2019-2020年高三上学期期中调研测试物理试题
doc 云南省2020年实验小学一年级数学开学考试试题C卷 含答案
doc 云南省2020年实验小学一年级数学期中考试试卷(II卷) 含答案
doc 山东省重点小学三年级数学【上册】开学考试试题 (含答案)
doc 2019-2020年高三上学期期中调研物理试题含答案
doc 2020年一级建造师《建筑工程管理与实务》练习题(II卷) 附答案
doc 2020年一级建造师《建筑工程管理与实务》练习题B卷 附解析
doc 实验小学二年级数学下学期开学考试试题江西版C卷 附答案
doc 2020年一级建造师《建筑工程管理与实务》练习题D卷 (附解析)
doc 实验小学二年级数学下学期开学考试试题浙教版 附解析
doc 云南省2020年实验小学一年级数学开学考试试题(II卷) 含答案
doc 2019-2020年高三上学期期中调研测试地理试题
doc 云南省2020年实验小学一年级数学期中测试试题B卷 含答案
ppt 《技术经济学练习》PPT课件
doc 山东省重点小学三年级数学【上册】开学考试试题 附答案
doc 2020年六年级数学【上册】期末考试试题上海教育版 附答案
doc 2020年六年级数学【上册】期末考试试卷长春版 附答案
doc 广东省重点小学四年级数学下学期期末摸底考试试卷B卷 (附答案)
doc 云南省2020年实验小学一年级数学期中测试试题A卷 含答案
doc 实验小学二年级数学下学期开学考试试题沪教版A卷 含答案
doc 实验小学二年级数学下学期开学考试试题江西版A卷 附解析
doc 实验小学二年级数学下学期开学考试试题江西版(II卷) 附答案
doc 云南省2020年实验小学一年级数学期中考试试卷(I卷) 含答案
doc 2020年一级建造师《建筑工程管理与实务》练习题C卷 (附答案)
ppt 《技能考试题型总结》PPT课件
doc 2019-2020年高三上学期期中调研测试历史试题
doc 云南省2020年实验小学一年级数学期中考试试卷A卷 含答案
doc 云南省2020年实验小学一年级数学期中考试试卷C卷 含答案
doc 广东省重点小学四年级数学下学期期末摸底考试试卷A卷 附解析
doc 山东省重点小学三年级数学【上册】期中摸底考试试卷 含答案
ppt 《技术部终总结》PPT课件
doc 2020年一级建造师《建筑工程管理与实务》练习题C卷 附解析

离散数学基础(洪帆)第二章关系

 版权申诉  ppt " "第2章 关系" " 本章主要内容: 有序n元组(序偶)和笛卡儿积、关系的概念; 关系的表示方法; 关系的复合运算、关系的性质; 等价关系、偏序。 " "2.1 笛卡儿积" "1.定义 由n个具有给定次序的个体 a1,a2,…,an 组成的序列, 称为有序n元组,记作(a1,a2,…,an) 。 注:有序n元组不是由n个元素组成的集合。 因为前者明确了元素的排列次序, 而集合没有这个要求。 例如: (a,b,c) ≠(b,a,c) ≠(c,a,b), 但 {a,b,c}={b,a,c}={c,a,b}。" "一、有序n元组" " 定义 假设(a1,a2,…,an) 和(b1,b2,…,bn) 是两个有序n元组, 则 (a1,a2,…,an)= (b1,b2,…,bn)成立, 当且仅当a1=b1, a2=b2,…, an=bn。 3. 序偶 当n=2时,有序二元组(a,b)称为序偶。" "2. 两有序n元组相等" " 1.定义 设A1,A2,…,An是任意集合, 所有的有序n元组(a1,a2,…,an) 的集合 称为 A1,A2,…,An的笛卡儿积, 用A1×A2× …×An表示, 其中a1∈A1, a2∈A2,…,an∈An, 即: A1×A2× …×An={(a1,a2,…,an)| ai∈Ai,i=1,2,…,n}" "二、笛卡尔积" "2. 集合A与集合B的笛卡尔积" "A×B={(a,b)|" "a∈A," "b∈B}" "则 A1×A2× …×An可表示为" " 注:若所有Ai都相同," " 例1 设A={1,3}, B={1,2,4},求:A×B, B×A 解: A×B={(1,1),(1,2),(1,4),(3,1),(3,2),(3,4)} B×A={(1,1),(1,3),(2,1),(2,3),(4,1),(4,3)} 显然 A×B≠ B×A, 即笛卡儿积不满足交换律。 例2 设A={0,1}, B={2,3}, C={3,4}则: A×B×C={(0,2,3), (0,2,4),(0,3,3),(0,3,4) (1,2,3),(1,2,4),(1,3,3),(1,3,4)} (A×B)×C={((0,2),3),((0,2),4),((0,3),3),((0,3),4), ((1,2),3),((1,2),4),((1,3),3),((1,3),4)} A×(B×C)={(0,(2,3)),(0,(2,4)),(0,(3,3)),(0,(3,4)), (1,(2,3)),(1,(2,4)),(1,(3,3)),(1,(3,4))}. (A×B)×C≠ A×(B×C),因此笛卡儿积不满足结合律。 " "2.2 关系" "1.定义 笛卡儿积A1×A2× …×An的任意一个子集 称为A1,A2,…,An上的一个n元关系。 注: 当n=2时, A×B的任一子集 称为由A 到B的一个二元关系。 " "一、关系的定义" " 注:1) 空集是任何集合的子集, 称为 空关系。" "2) 若集合A、B的元素分别是n、m" "则A到 B的关系共有" "注: 若 是A到B的一个关系, 如果(a,b) ∈ , 则称a与b有 关系 , 记作a b, 如果(a,b) , 则称a与b没有 关系,记作a b。" "集合称为关系的值域,记作" "2.关系的定义域和值域" " 定义 " "设" "是由A到B的一个关系," "则使得" "a" "b(b∈B)成立的所有元素a∈A的" "集合称为关系的定义域,记作 " "则使得" "a" "b(a∈A)成立的所有元素b∈B的" " 例1 设集合A={1,2,4,7,8}, B={2,3,5,7}, 定义由A到B的关系: ={(a,b)|(a+b)/5是整数} 试问 由哪些序偶组成? 并求此关系的定义域和值域。 " " 1)定义 由集合A到A自身的关系称为 集合A上的关系。 " "3. A上的关系" " 例2 设A={2,3,4,5,9,25},定义A上的关系R , 对于任意的a,b∈A,当且仅当(a-b)2∈A 时,有a R b, 试问 R由哪些序偶构成? 并求关系R的定义域和值域。" "a) 普遍关系 若关系 R =A2, 则称R为A上的普遍关系, 记作UA, 即UA={(ai,ak)|ai,ak∈A}。 " "2)A上的普遍关系与恒等式关系" "b) 恒等关系 A上的恒等关系用IA表示 , 定义为: IA={(ai,ai)|ai∈A} " " 令有向图G=(V,E), 其中顶点集V=A,边集E按如下规定: 有向边 " "" "" "二、关系的表示方法" "1.列举法 2.描述法" "3. 关系图" "定义 " "设A={a1,a2,…,an}, " "是A上的关系," "的关系图。" "则称有向图G为关系 " " 例3 设集合A={1,2,3,4}, R={(1,1),(1,2),(1,3),(1,4),(2,3)} S={(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)} 都是 A上的二元关系。 画出关系R与S的关系图。 " "图(1)" "图(2)" " R和S的关系图分别如下图(1)和图(2)所示:" "且关系矩阵的第i行、第j列的元素 " "4. 关系矩阵" "定义" "设集合A={a1,a2,…,an},B={b1,b2,…,bm}" "是由A到B的关系, " "则" "的关系矩阵 " "记为" "定义如下:" "定义为一个n行、m列的矩阵," " 例4 设集合A=2{0,1}, B=2{0,1,2}-2{0}, ={(a,b)|a-b= } 是一个由A到B的关系, 试列出关系 的定义域和值域,构造出关系矩阵。" "解:定义域" "=A, " "=B。" "值域" " 关系矩阵为: " "2.3 关系的复合" " 一、关系的一般运算:交、并、补、差" "试求:" " 例1 设A={4,6,9,10}, " "和" "是A上的两个关系:" "={(a,b)|(a-b)/2是正整数}," "={(a,b)|(a-b)/3是正整数}" "二、关系的逆关系(关系的逆运算) " "={(b,a)|(a,b)∈ " "注:逆关系 " "的关系矩阵" "定义 " "设A和B是两个集合, " "是A到B的关系, " "则由B到A的关系:" "的逆关系。" "称为关系 " "记为" "}," " 例2 设A={2,3,4,5,9,25}, " "定义A上的关系:" " 三、关系的复合运算 1. 定义 设 是一个有A1和A2的关系, 是一个由A2到A3的关系, 则 和 的复合关系是一个 由A1到A3的关系, 用 表示, 定义为当且仅当存在某个 ∈A2, 使得 , 时, 有 。 这种从 和 得到的运算, 称为关系的复合运算。" " 例2 设有集合A={4,5,8,15}, B={3,4,5,9,11}, C={1,6,8,13}, 是A到B的关系, 是B到 C的关系, 且分别定义为: ={(a,b)||b-a|=1} ={(b,c)||b-c|=2或|b-c|=4} 试求复合关系 。 " " 定理2 设 是由A1到A2的关系, 是由A2到A3的 关系, 是由A3到A4的关系, 则有: 注:1)复合关系的运算具有结合律。 2) 当 A1=A2=…=An=An+1=A, 时, 复合关系 可以用 表示。 " "定理1 设 是有集合A到B的关系,则有: " "2. 关系复合的性质" " 例3 设A={a,b,c,d},A上的关系: ={(a,a),(a,b),(b,d),(c,a),(d,c)} 试求复合关系 。 " "2.4 复合关系的关系矩阵和关系图" " 一、布尔运算 布尔运算只涉及数字0和1, 数字的加法和乘法按照以下方式进行: 0+0=0 0+1=1+0=1+1=1 1·1=1 1·0=0·1=0·0=0 如:(1·1)+(0·1·1)+(1·0·0)+1+0=1" "则M1与M2乘积记为M1﹒M2是一个l×n的矩阵, " "二、 两关系矩阵的乘积" "注: 这里的加法和乘法都是布尔型的" " 定义 " "设M1是一个(i,j)通路(即第i行、第j列的元素)为" "的l×m关系矩阵," "M2是一个(i,j)通路为 " "的m×n关系矩阵," "其(i,j)通路为:" "的关系矩阵为 : " "三、 复合关系的关系矩阵" " 定理1 " "设集合A,B,C都是有限集" "是由A到B的关系, " "是由B到C的关系, " "他们的关系矩阵分别为 " "则复合关系 " "的关系矩阵为: " " 定理2 " "设有限集A上的关系" "的关系矩阵是 " "则复合关系 " "四、 求复合关系的关系图的方法" "由" "的关系图构造" "的关系图的方法:" "对于" "的图中的每个结点" "ai" ",确定从" "ai" "经由长为 n 的路能够到达的结点," "这些结点在" "的图中,边必须由" "ai" "指向它们。" "2.5 关系的性质与闭包运算" "一、 关系的性质" "是反对称的。" "1.定义 " "设" "是集合A上的关系:" "(1) 若对于所有的 " "都有" "则称 " "是自反的。" "(2) 若对于所有的 " "都有" "则称 " "是反自反的。" "(3) 若对于所有的 " "若每当有 " "就必有" "则称 " "是对称的。" "是可传递的。" "(4) 若对于所有的 " "若每当有 " "就必有" "则称 " "(5) 若对于所有的 " "若每当有 " "就必有" "则称 " " a) 一个关系可以既不是自反关系 又不是反自反关系. 例如A={1,2,3}上关系: {(1,1),(1,2),(2,3)}。 b) 一个关系既可以是对称的 又可以是反对称的. 例如A={1,2,3}上的关系: {(1,1),(2,2),(3,3)}。 " "2. 说明" " 3.定理 设 是集合A上的关系, 则 (1) 是自反的当且仅当 。 (2) 是对称的当且仅当 。 (2) 是反对称的当且仅当 。 (5) 是传递的当且仅当 , 即" " 例1 设A={1,2,3,4},试判定下列A上的关系的性质。 (1) ={(1,1),(1,2),(2,3),(1,3),(1,4)}; (2) ={(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)}; (3) ={(1,3),(2,1)}; (4) = , 即空关系; (5) =A×A, 即全域关系; " "解: " "(2) 自反的, 对称的, 传递的;" "(3) 反自反的, 反对称的;" "(4) 反自反的, 对称的,反对称的,可传递的;" "(5) 自反的, 对称 的, 可传递的。" "(1) 反对称的,传递的; " " 例2 指出下列五种二元关系的性质。 (1) 实数集合上的“小于等于”关系。 自反的, 反对称的,可 传递的。 (2) 集合上的“包含”关系。 自反的, 反对称的,可传递的。 (3) 正整数集合上的“整除|”关系。 自反的, 反对称的, 可传递的。 (4) 平面上直线集合上的“垂直⊥”关系。 反自反的,对称的。 (5) 平面上直线集合上“平行//”关系 。 自反的,对称的,可传递的。" " 4.关系的性质在关系矩阵和关系图中的特点" " 二、二元关系的闭包 设 是集合A上的关系, 我们希望 具有某些有用的性质, 比如说自反性。如果不具有自反性, 我们通过在其中添加一部分序偶来改造, 得到新的关系 , 使得其具有自反性。但又不希望它与 相差太多, 换句话说, 添加的序偶要尽可能的少。满足这些要求的就称为 的自反闭包。除自反闭包外还有对称闭包和传递闭包等。" " 1.定义 设 是集合A上的关系, 的自反闭包 (对称闭包或传递闭包)是A上关系 它满足下列条件: (1) 是自反的(对称的或可传递的); (2) ; (3) 对A上任何包含 的自反(对称或 可传递)关系 , 有 。 注: 将自反闭包记为 , 对称闭包记为 将传递闭包记为 。" " 定理 设 是集合A上的关系:则 (1) ; (2) ; (3) 。 推论: 设 是有限集合A上的关系, 若#(A)=n, 则 。" "2. 求闭包的方法" "注:由" "的关系图构造" "的关系图的方法:" "对于" "的图中的每个结点" "ai" ",找出从" "ai" "经有限长的路能够到达(有路)的结点," "这些结点在" "的图中,边必须由" "ai" "指向它们。" " 3.定理 设 是集合A上的关系, 则: (1) 是自反的当且仅当 ; (2) 是对称的当且仅当 ; (3) 是传递的当且仅当 ; " " 4.定理 设 是集合A上的关系: (1)若 是自反的, 则 也是自反的。 (2)若 是对称的, 则 也是对称的。 (3)若 是传递的, 则 也是传递的。 5.定理 设 是A上的关系, 且 , 则有 , , 。 " "由等价关系的对称性也称b等价于a。" "一、 等价关系的定义" "2.6 等价关系" " 定义 " "设" "是集合A上的一个关系, " "若它是自反的, 对称的且可传递的," "则称" "为A上的一个等价关系。" "设" "是集合A上的一个等价关系, " "若a" "b成立," "注:" "则说a等价于b, " " 例1 在中国人组成的集合上定义的“同姓”关系, 它具备自反、对称、传递的性质, 因此是一个等价关系。 例2 平面上直线集合上的“平行”关系是等价关系, 而其上的“垂直”关系不是等价关系, 因为它既不是自反的,也不是传递的。 例3 平面上三角形的“全等、相似”关系是等价关系。 例4 “朋友”关系不是等价关系,因为它不是传递的。 例5 集合的“包含”关系不是等价关系, 因为它不是对称的。 " " 例6 设A={1,2,…,8}, 如下定义A上的关系 R: R ={(a,b)|a,b∈A, a≡b(mod3)}. 其中a≡b(mod3)叫做a与b模3相等, 即a与b除以3的余数相等(即3整除|a-b|). 判定R是否为A上的一个等价关系? 解: 因为有任意a∈A, a≡a(mod3) 对任意a,b∈A, 若a≡b(mod3), 则a≡b(mod3) 对任意a,b,c∈A, 若a≡b(mod3), b≡c(mod3) 则有a≡c(mod3), 所以R是A上的等价关系。 该关系的关系图如下图所示: " " 从图中可以看出, 关系图被分成三个互不连通的部分。 每一个部分中的数两两都等价(有关系), 不同部分中的数则不等价(没有关系)。 通过等价关系给出的每一部分叫此等价关系的等价类。 " "={b|b∈A, a " "二、 等价关系的等价类" "1.定义 " "设" "是集合A上的一个等价关系, " "则由A中等价于a的全体元素所组成的集合" "称为由元素a所生成的等价类。" "用" "表示," " 即:" "b}" "2.等价类的性质 (1) 对于任意a∈A, 有a a, 因此a∈ , 即A中每一个元素所生成的等价类非空。 (2) 若a b, 则 , 即彼此等价的元素属于同一个等价类。 (3) 若a b, 则 , 即彼此不等价的元素属于不同的等价类, 且这些等价类没有公共元素。 " " 注: 集合A上的任意一个等价关系定义A的一个分划, 每一个等价类就是一个分划块。" "3. 等价分划" " 定理 " "设" "是集合A上的等价关系, " "则等价类" "的集合{ " "|a∈A}" "构成集合A的一个分划。" "由等价关系 " "的等价类所" "导出的等价分划," "组成的A的分划" "称为A上由" "记为" "例8 设A={0,1,2,3,4,5}上的关系 ={(0,0),(1,1),(2,2),(3,3),(1,2),(1,3),(2,1) (2,3),(3,1),(3,2),(4,4),(4,5),(5,4),(5,5)} 求它在A上所导出的等价分划。 " " 解:显然此关系 是自反的,对称的和可传递的, 因此是一等价关系, 它在A上所导出的等价分划为: " "={[0],[1],[4]}={{0},{1,2,3},{4,5}}" "导出等价分划。" " 注:由定理知‘分划’的概念和 ‘等价’的概念在本质上是相同的。 " " 4.定理 " "设" "是集合A上的一个分划, " "则存在A上的等价关系 " "使得" "是A上由" " 例9 求出A={a,b,c}上所有的等价关系。 解:先给出A上的所以划分: " "={{a},{b},{c}}," "={{a},{b,c}}, " "={{a,c},{b}, " "={{a,b},{c}}, " "={{a,b,c}}。" "再给出每个划分所对应的等价关系为:" "={(a,a),(b,b),(c,c)}," "={(a,a),(b,b),(c,c),(b,c),(c,b)}," "={(a,a),(c,c),(a,c),(c,a),(b,b)}," "={(a,a),(b,b),(a,b),(b,a),(c,c)} ," "={(a,a),(b,b),(c,c),(a,b),(a,c),(b,a),(b,c)(c,b), (c,a)} 。" "的秩。 " "三、 等价关系的商集" " 1.定义 " "设" "是集合A上的等价关系, " "则等价类的集合{ " "|a∈A}" "称为A关于 " "的商集, " "用" "表示。" "的基数称为 " "商集" "2.7 偏序" " 1.定义 集合A上的一个关系 , 如果它是 自反的, 反对称的和可传递的, 则称此关系是A上的一个偏序关系, 或简称为偏序, 用符号‘≤’ 去表示。" "一、 偏序的定义" " 2.说明 设≤是集合A上的偏序关系, 对于 任意的a,b∈A, 如果有a≤b或者b≤a 则称a和b是可比的, 否则称a和b不可比的。" " 2.定义 一个集合A上的偏序, 若对于A上的 每一个非空子集S, 在S中存在 一个元素as(称为S的最小元素), 使得对于所有的s∈S, 有as≤s, 则称它为A上的一个良序。" " 1.定义 一个集合A上的偏序, 如果对 所有的a,b∈A, 有a ≤ b或b ≤a, 则称它为A上的一个全序。 " "二、全序和良序" " 例1 定义在实数集R上的‘小于或等于’关系≤, 显然是R上的偏序关系, 它也是R上的一个全序, 但是它不是R上的良序。 如(0,1)是R的一个子集, 但是(0,1)中无最小元素。 例2 定义在正整数集N上的‘小于或等于’关系≤ 是N上的偏序关系, 也是全序和良序。 例3 定义在正整数集N上的“整除|”关系 是一个偏序关系, 但不是全序也不是良序。 因为显然对于 3,5∈N, 既没有3|5, 也没有5|3, 所以不是全序。 而对于N的子集{3,5}没有最小元, 则不是良序。" " 3.结论: (1) 一个集合A上的全序或良序一定是偏序, 但是偏序却不一定是全序和良序。 (2) 一个偏序若是良序, 则一定也是全序 (3) 全序不一定是良序 " " 设A上定义的偏序关系≤, 1. 用结点表示A中的每一个元素。 省略自回环。 2. 若a≤b, 则结点a出现在结点b的下面。 省略方向,规定方向自下朝上。 3. 若a≤c,c≤b,则省略a到b的连线。 " "三、 偏序的关系图——次序图(Hasse图)" " 例5 (1)集合X={2,3,6,12,24,36}上的整除关系 是一个偏序, 画出其次序图。 (2)集合S={a,b,c}的幂集上的包含关系 是一个偏序, 画出其次序图。 " "解: (1)的次序图见图(a), (2)的次序图见图(b)。








































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