3.4 关系及其表示

第三章集合3.4关系及其表示课程大纲CONTENTS01关系的基本概念定义、定义域、值域、域。02三种特殊的关系空关系、全域关系、恒等关系。03关系的表示方法序偶集合、关系图、关系矩阵。引言：什么是关系？核心思想关系是描述两个或多个事物之间相互联系的基本概念。它存在于我们生活的方方面面，例如人与人之间的朋友关系、商品与价格的对应关系等。在离散数学中，为了进行严格的逻辑推理与运算，我们将关系进行数学抽象，把它定义为：“有序对（序偶）的集合”本节学习目标▢理解关系的基本数学定义与集合表示。▢掌握关系的基本要素：定义域、值域和域。▢认识三种基础的特殊关系：空关系、全域关系与恒等关系。▢熟练运用三种方式表示关系：集合列举、关系图与关系矩阵。定义3.16：二元关系(BinaryRelation)定义原文若一个集合的元素都是序偶(OrderedPairs)，称该集合是一个二元关系，简称“关系(Relations)”，通常记为大写字母R。注：这是关系最本质的数学定义——关系即集合。符号表示•若序偶<x,y>在集合R中：

<x,y>∈R或xRy•若序偶<x,y>不在集合R中：

<x,y>∉R或xRy(在R上画一斜线)通俗理解•当xRy为真时：

读作“x对y有关系R”。•当xRy为假时：

读作“x对y没有关系R”。就像在生活中，我们说“甲和乙是朋友”，本质上就是序偶(甲,乙)属于“朋友”这个关系集合。关系的基本概念：定义域、值域与域定义3.17定义域(Domain)domR={x|存在y，<x,y>∈R}即关系R中所有有序对的第一个元素组成的集合。定义3.18值域(Range)ranR={y|存在x，<x,y>∈R}即关系R中所有有序对的第二个元素组成的集合。定义3.19域(Field)FLDR=domR⋃ranR即关系R的定义域与值域的并集，包含了关系中所有元素。▍关系模型图解直观理解：关系R的定义域是前域的子集，值域是后域的子集。它们之间的关系可以用映射图清晰地表示出来：左边集合映射到右边集合，所有被“射出”的元素构成定义域，所有被“射入”的元素构成值域。例题3.21：计算定义域、值域和域题目：已知集合A={a,b,c}，集合B={1,2,3}，关系R={<a,2>,<b,1>,<b,3>}。请根据定义计算关系R的定义域、值域以及域。定义域(domR)定义：找出关系R中所有序偶里的第一个元素，并将它们组成集合。domR={a,b}值域(ranR)定义：找出关系R中所有序偶里的第二个元素，并将它们组成集合。ranR={1,2,3}域(FLDR)定义：该关系的定义域和值域的并集，即所有出现在序偶中的元素的集合。FLDR={a,b,1,2,3}定义3.20：从X到Y的关系&X上的关系从X到Y的关系设有任意两个集合X和Y，直积X×Y的子集，称为X到Y的(二元)关系。理解要点：关系本质上是有序对的集合，并非指通常语境下的“关联”或“联系”。X上的关系当集合X和Y为同一个集合时，关系R是X×X的子集，此时称R为X上的二元关系。应用场景：在集合论和计算机科学中，我们最常研究的是同一个集合内部元素之间的关系，例如“相等”、“小于”或“连通”关系。重要计数公式若集合A和B均为有限集，且元素个数分别为|A|=n，|B|=m，则从A到B的所有不同关系的数量为：2n×m这是因为|A×B|=n×m，其子集个数为2的基数次方。例题3.22：穷举所有可能的关系题目描述假设集合A={a,b}，集合B={c,d}请试写出从集合A到集合B的所有不同的二元关系。解题思路Step1.求笛卡尔积(A×B)先计算集合A与B的笛卡尔积，得出两个集合元素所有可能的有序对组合。Step2.求幂集(P(A×B))找出笛卡尔积集合的所有子集（即其幂集）。根据定义，幂集中的每一个元素都是一个从A到B的关系。最终结论16种计算公式：

2^(|A|×|B|)=2^(2×2)=163.4.2三种特殊的关系空关系(EmptyRelation)定义：当R=∅时，称R为从集合A到集合B的空关系。理解：集合A中的元素与集合B中的元素之间不存在任何关联。全域关系(UniversalRelation)定义：当R=A×B时，称R为从集合A到集合B的全域关系。理解：集合A中的每一个元素都与集合B中的每一个元素相关联。恒等关系(IdentityRelation)定义：IA={<x,x>|x∈A}。即关系由所有形如<x,x>的有序对构成。理解：集合中的每一个元素都只与它自身相关，不与任何其他元素相关。例题3.23：求全域关系和恒等关系题目：设集合A={a,b,c,d}，求集合A上的全域关系EA和恒等关系IA。全域关系EA包含集合A中所有元素构成的笛卡尔积A×A的全部序偶。EA={<a,a>,<a,b>,<a,c>,<a,d>,

<b,a>,<b,b>,<b,c>,<b,d>,

<c,a>,<c,b>,<c,c>,<c,d>,

<d,a>,<d,b>,<d,c>,<d,d>}恒等关系IA仅包含集合A中每个元素与其自身构成的序偶。IA={<a,a>,<b,b>,<c,c>,<d,d>}3.4.3关系的表示方法关系本质上是序偶的集合。除了最直观的集合形式外，我们在图论和矩阵分析中，通常会采用更具视觉直观性的关系图和便于代数运算的关系矩阵来表示。这三种方法在逻辑上完全等价，且可以相互转换。01.序偶集合表示法(SetofOrderedPairs)最基础的表示方法，通过枚举集合中所有满足关系定义的有序二元组来完整刻画关系。💡示例：整数集合A={1,2,3,4}上的“整除”关系RR={<1,1>,<1,2>,<1,3>,<1,4>,<2,2>,<2,4>,<3,3>,<4,4>}关系的表示方法：关系图基本绘制规则Step1.设定结点

将关系涉及的两个集合（如集合A和集合B）中的每一个元素，都作为图中的独立“结点”（通常用小圆圈○来表示）。Step2.绘制有向边

如果有序对<ai,bj>属于关系R，则从表示ai的结点出发，向表示bj的结点画一条带箭头的直线，箭头方向代表关系的方向。示例：学生选课关系R在该示例中，左侧是“学生集合”，右侧是“课程集合”。箭头直观地展示了：王珊选修了离散数学，张华选修了操作系统，陈红选修了计算机网络，而李想目前未选择任何课程。关系的表示方法：关系矩阵核心定义设两个有限集合A={a₁,a₂,...,aₙ}和B={b₁,b₂,...,bₘ}，R是从A到B的二元关系。R的关系矩阵(MatrixofRelation)记作MR，是一个n行m列的矩阵。其中矩阵中的每个元素值由如下规则确定：•MR[i][j]=1，当且仅当<ai,bj>∈R•MR[i][j]=0，当且仅当<ai,bj>∉R注：关系矩阵直观地将“存在关系”映射为1，“不存在关系”映射为0，非常便于计算机进行数据存储和算法计算。实例解析假设我们有集合：

A={a,b,c}，B={1,2}

关系R={<a,2>,<b,1>,<b,2>,<c,1>}根据定义，R的3×2阶关系矩阵如下：关系表示方法的转换序偶集合→关系矩阵1.确定顺序：首先明确集合A和集合B的元素排列顺序，这决定了矩阵的行列索引。2.构建矩阵：创建一个维度为|A|×|B|的二维矩阵，矩阵初始值通常设为0。3.填充数值：遍历所有序偶<a_i,b_j>，在矩阵中第i行第j列的位置填入1，其余位置保持0。关系矩阵→关系图1.确定节点：根据矩阵的行数和列数，在平面上画出所有的节点，通常用小圆圈或点表示，并标注对应的元素名称。2.绘制有向边：逐行逐列遍历矩阵，若矩阵中位置(i,j)的值为1，则从第i个节点向第j个节点绘制一条带箭头的有向线段。关系图→序偶集合1.遍历边集：检查关系图中的每一条有向边，不遗漏任何连接。2.构造序偶：对每一条有向边，将其起点作为序偶的第一个元素，终点作为第二个元素，写成<起点,终点>的形式，并将所有这样的序偶放入一个集合中。本节核心知识点回顾关系的定义关系本质上是序偶的集合，描述了集合元素之间的某种联系或对应规则。基本概念描述关系结构的三大要素：

•定义域(DomR)：所有序偶第一元素的集合

•值域(RanR)：所有序偶第二元素的集合

•域(FldR)：定义域与值域的并集特殊关系集合论中定义的三种典型关系：

•空关系：不含任何序偶的关系

•全域关系：包含笛卡尔积中所