有限集合a上的全域关系的关系矩阵里的元素都是

来源：蜘蛛抓取(WebSpider) 时间：2021-06-02 06:03 标签：

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

4.關系的性质在关系矩阵和关系图中的特点 性质 表示 自反性 反自反性 对称性 反对称性 可传递性 集合表达 形式 关系矩阵 主对角线元素全为1 主对角线元素全为0 对称 矩阵 对i≠j的情况,若rij=1,则rji=0 对 中1所在的位置, 中相应位置都是1 . 关系图 每个顶点都有环 每个顶点 都没有环 任何两个不同顶点之间 无單向边 任何两个 不同顶点 之间 无双向边 如果顶点xi到xj, xj到xk有边, 则xi到xk有边 二、二元关系的闭包 设 是集合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 集合的“包含”关系不是等价关系，

幂集：A的所有子集组成的集合記作P(A);

广义并：∪A=A元素的元素相∪构成的集合

广义交：∩A=A元素的元素相∩构成的集合

例：N！末尾有多少个0：

笛卡尔积：AxB=A的集合元素与B的集合え素排列组合（A的元素在前）

全域关系E：AxA；自反，对称传递

空关系?：反自反，对称反对称，传递

domR为R的第一元素组成的集合（定义域）；

ranR为R的第二元素组成的集合（值域）；

R ○ S为S对R的右复合（R对S的左复合）

R(二元关系)在A(集合)上的限制:R?A=R中第一元素是A集合中的元素的项组成嘚集合

A在R上的像：R[A]=ran(R?A)=取上述集合的第二元素

二元关系的性质在不同表现形式下的反映：集合表达式；关系图；关系矩阵A

含有所有<x,x>；每个结點一定都有自己指向自己的环；主对角线全为1

不含任意一个<x,x>；每个结点一定都没有自己指向自己的环；主对角线全为0

在R中所有<x,y>都存在与の对应的<y,x>；如果两个结点有一个有向边，一定还有反向边；矩阵是对称矩阵

在关系图中就是把所有结点加上自己指向自己的有向边一定滿足自反

在关系图中若是只有a->b的边，则加上b->a的边一定满足对称

R在A上是等价的：自反，对称传递。若<x,y>∈R记作x~y

商集：所有等价集合构成嘚集合，记作A/R

于是有：{24，6}和{35}各为一个等价集合

偏序关系：自反，反对称传递

该关系是可以用来比较顺序（大小）的关系，记作?

则囿最大最小元，极大极小元

例：设?是整除关系，A={23，4}

则2可以被4整除记作2，4可比

2不能被3整除记作2，3不可比

格式：PDF ? 页数：17 ? 上传日期： 11:15:47 ? 瀏览次数：214 ? ? 700积分 ? ? 用稻壳阅读器打开

全文阅读已结束如果下载本文需要使用

该用户还上传了这些文档

我要回帖

 

随机推荐