二元关系

平顶山学院毕业论文(设计)

引言

在日常生活中，关系一词是大家在生活学习和工作中经常遇到和处理的概念，我们都熟知关系一词的含义，例如兄弟关系、上下级关系、位置关系等.在数学中关系可抽象为表达集合中元素之间的关系，如“4大于2”，“P在点a，b之间”.

在离散数学中关系是刻画元素之间相互联系的一个重要的概念，广泛应用于计算机科学技术如计算机程序的输入、输出关系，数据库的数据特性关系，其中关系数据库就是以关系及其运算作为理论基础的.近世代数利用等价关系将代数系统进行分类，进而加以研究.关系也是点集拓扑中一个重要概念，通过关系分类来研究集合元素之间的某种联系.熟练掌握关系的定义和性质,也是学好近世代数和点集拓扑的基础.

最基本的关系就是二元关系，就是集合中两个元素之间的某种相关性.例如

B可以从事?，有三个人A,B,C和四项工作?，?，?，?.已知A可以从事?和?，

C可以从事?和?，那么人和工作之间的对应关系可以记作:

R???A,??,?A,??,?B,??,?C,??,?C,???.

这是人的集合?A,B,C?到工作的集合??，?，?，??之间的二元关系.

一 基础知识

定义1?? 设A,B为集合，用A中元素为第一元素，B中元素为第二元素，

1构成有序对，所有这样的有序对组成的集合叫做A和B的笛卡尔积，记作A?B,符号化表示为A?B=??x,y?|x?A?y?B?.

定义2?? 如果一个集合满足以下条件之一：

1⑴集合非空，且它的元素都是有序对； ⑵集合是空集，

则称这个集合是一个二元关系，通常记作大写的英文字母R，二元关系也可简称为关系.对于二元关系R,如果有序对?x,y??R,可记为xRy,否则记为xRy.

1

二元关系的性质及二元关系的应用

例如R1???1,2?,?a,b??, R2???1,2?,a,b?，则R1为二元关系，R2不是二元关系，只是一集合，除非将a和b定义为有序对.

二元关系中特别重要的是从A到B的关系与A上的关系.

定义3?1? A,B 为集合，A?B的任何子集所定义的二元关系叫做从A 到

B的二元关系,特别当A?B时则叫做A上的二元关系.

集合A上的二元关系的数目依赖于A中的元素数，当A含有n个元素时即

|A|?n,则|A?A|?n2,A?A的子集有2n个，每一个子集代表一个A上的关系，

2

所以A上有2n个不同的关系.

定义4?2? 对任意的集合A都有三种特殊的关系：

①空集?是任何集合的子集当然也是A?A的子集，也是A上的关系，称为空关系.

②EA???x,y?x?A?y?A??A?A称为A上的全域关系. ③IA???x,x?|x?A?为A上的恒等关系. 给定集合A，定义几种常用的关系：

定义5?? A是实数集R的任意非空子集，则称A上的二元关系

22LA??x,y?x,y?A?x?y?,为A上的小于等于关系.

?定义6?? A?Z?,Z?为非0整数集，则称A上的二元关系

2DA??x,y?x,y?A?x整除y?,为A上的整除关系.

?定义7?? 设A是整数集Z的任意非空子集，n是任意正整数，则称A上的

2二元关系R???x,y?|x,y?A?x?y?modn??为A上的模n同余关系.

定义8?? 设?是由一些集合构成的集合族，则称?上的二元关系

2R?=??A,B?|A,B???A?B?为?上的包含关系.

例：设A??a,b?,求P?A?上的包含关系. 解：由于P?A????,?a?,?b?,?a,b??,

2

平顶山学院毕业论文(设计)

R?{??,??,??,?a??,??,?b??,??,?a,b??,??a?,?a??,??a?,?a,b??, ? ??b?,?b??,??b?,?a,b??,??a,b?,?a,b??}

在日常生活、生产活动和科学研究中，人们常用点表示事物，用点与点之

间是否有连线表示事物之间是否有某种关系，这样构成的图形就是图论中的图.

定义9?? 一个无向图G是一个有序的二元组V,E,其中

1⑴V是一个非空有穷集,称为顶点集,其元素称为顶点或结点.

⑵E是无序集V&V的有穷多重子集,称为边集,其元素称为无向边,简称为边.

定义10?? 一个有向图D是一个有序的二元组V,E,其中

1⑴V是一个非空有穷集,称为顶点集,其元素称为顶点或结点.

⑵E是笛卡尔积V?V的有穷多重子集，称为边集， 其元素称为有向边，简称边.

通常用图形来表示有向图和无向图:用小圆圈(或实心点)表示顶点,用顶点之间的连线表示无向图,用带箭头的连线表示有向边.

定义11??设D??V,E?为一个有向图，?vi,vj?V，若从vi到vj存在通路，

1则称vi可达vj，记作vi?vj.规定vi总是可达自身的，即vi?vi.若vi?vj且

vj?vi，则称vi与vj是相互可达的，记作vi?vj.规定vi?vi.

与定义9和定义10有关的还有下面一些概念和规定.

⑴无向图和有向图统称为图,但有时也常把无向图简称为图.通常用G表示无向图,D表示有向图,有时也用G泛指图(有向的或无向的).用V?G?,E?G?分别表示G的顶点集和边集, |V?G?|,|E?G?|分别是G的顶点数和边数.有向图也有类似的符号.

⑵设G?V,E为无向图, ek?(vi,vj)?E,称vi,vj为ek的端点,ek与vi(vj)关联.若vi?vj,则称ek与vi(vj)的关联次数为1;若vi?vj,则称ek与vi的关联次数为2，并称ek为环.如果顶点vl不与边ek关联,则称ek与vl的关联次数为0.

3

二元关系的性质及二元关系的应用

若两个顶点vi与vj之间有一条边连接,则称这两个顶点相邻.若两条边至少有一个公共端点,则称这两条边相邻.

⑶设D??V,E?为有向图, ek?(vi,vj)?E,称vi,vj为ek的端点, vi为ek的始点, vj为ek的终点，并称ek与vi(vj)关联.若vi?vj，则称ek为D中的环.

若两个顶点之间有一条有向边,则称这两个顶点相邻.若两个边中一条边的终点是另一条边的始点,则称这两条边相邻.

二 关系的三种表示方法

表示关系的方法有三种：集合表达式，关系矩阵和关系图.

2.1 集合表达式

由于关系是一种特殊的集合，当然可以用集合表达式表示. 例如:设A=?1,2,3,4?,则用集合表达式表示A上的关系R. ⑴R???x,y?|x是y的倍数?. ⑵R???x,y?|x/y是素数?.

解: ⑴ R=??4,4?,?4,2?,?4,1?,?3,3?,?3,1?,?2,2?,?2,1?,?1,1?? ⑵R???2,1?,?3,1?,?4,2??

2.2 关系矩阵和关系图?2?

关系矩阵可以用来表示有穷集A到B的关系与A上的关系，关系图只能表示有穷集A上的关系.当关系中的元素较多时，利用关系矩阵和关系图可以形象直观的表示关系.

设给定两个有限集合X?{x1,x2,?,xm}，Y?{y1,y2,?,yn}，对应于从X到Y的二元关系R有一个关系矩阵MR??jm?n?ri???1?xi,yj??R，其中 rij??

0?x,y??Rij?(i?1,2,?,m;j?1,2,?,n).如果R是有限集合X上的二元关系或X和Y含有相

同数量的有限个元素，则其关系矩阵MR是方阵.

4

平顶山学院毕业论文(设计)

而同时对应R的关系图就是在平面上用m个点分别表示X中的元素

x1,x2,...,xm，另外再在平面上画出n个点分别表示Y中的元素y1,y2,...,yn，如果集合X和Y中有相同的元素则用同一点表示.当?xi,yj??R时，则从点xi至yj画一条有向边，其箭头指向yj，否则就没有边联结.

例 从A??1,2,3?到B??a,b,c,d?的关系

R???1,a?,?1,c?,?2,b?,?3,b?,?3,d??， 通常将A和B中的元素设定为升序

?1010?? 0100顺序，则对应的关系矩阵为：MR??????0101??对应的关系图为：

1 2 3 a

b

c db

特别地，当R为A上的二元关系时，如果A?n，则对应于R的关系矩阵是

?14方阵中的元素aij应有??：n阶方阵，aij???0?ai,aj??R?ai,aj??R ?????? （★）

其关系图表示可以在平面上仅画n个点，有向边的规定不变.

例如A??1,2,3,4?,R???1,1?,?1,2?,?2,3?,?2,4?,?4,2??，则R的关系矩阵是

?1?0MR???0??0对应的关系图为

100101000?1?? 0??0? 5

本文来源：https://www.bwwdw.com/article/yqe2.html