购买
下载掌阅APP,畅读海量书库
立即打开
畅读海量书库
扫码下载掌阅APP

§1.2 经典关系

1.2.1 集合的直积

在日常生活中,有许多事物是成对出现的,且具有一定的顺序。例如,上、下;左、右;平面上点的坐标等。任意两个元素 x y 配成一个有序的对( x y ),称为 x y 的序对或称序偶,有序是指当 x y 时,( x y )≠( y x );( x y )=( x ', y ') x =x', y = y '。

定义1.6 X Y 是两个非空集合,由 X 的元素与 Y 的元素搭配成的全体序偶组成一个集合,称为 X Y 的直积(或笛卡尔积),记为 X × Y 。即 X × Y ={( x y )| x X y Y }。

例1.1 X ={1,2}, Y ={0,2},则

X × Y ={(1,0),(1,2),(2,0),(2,2)};

Y × X ={(0,1),(0,2),(2,1),(2,2)}。

一般地, X × Y Y × X 。即,如果把集合的直积作为集合之间的运算,那么该运算不满足交换律。

两个集合的直积可推广为多个集合的直积。

1.2.2 经典二元关系

关系是一个基本概念。客观世界中的事物之间普遍存在着某种联系,这种联系就称为关系,其中最简单的就是二元关系。在日常生活中有“父子关系”,“朋友关系”、“师生关系”等,在数学上有“大于关系”、“等于关系”等。而序偶又可以表达两个对象之间的关系。于是,引进下面的定义。

定义1.7 X Y 为非空集合,则 X × Y 的子集 R 称为从 X Y 的二元关系。特别地,当 X = Y 时,称之为 X 上的二元关系,以后把二元关系简称为关系。

若( x y )∈ R ,则称 x y 有关系,记为 xRy ;若( x y )∉ R ,则称 x y 没有关系,记为 R 的特征函数:

为方便,特征函数 χ R x y )常简记为 R x y )。

例1.2 X ={1,4,7,8}, Y ={2,3,6},定义关系 R x < y ,称 R 为“小于”关系。于是 R ={(1,2),(1,3),(1,6),(4,6)}。

例1.3 X 为实数集,则子集 R ={( x y )|( x y )∈ X × X y = x }是实数集上元素间的“相等”关系。

例1.4 X ={1,2,3,4,5,6}, X 上的整除关系定义为:

R ={( x y )| x | y x y X }={(1,1),…,(1,6),(2,4),(2,6),(3,6)}。

1.2.3 关系的运算

定义1.8 R R 1 R 2 P X × Y ),定义:

并: R 1 R 2 ={( x y )|( x y )∈ R 1 或( x y )∈ R 2 };

交: R 1 R 2 ={( x y )|( x y )∈ R 1 且( x y )∈ R 2 };

余: R c ={( x y )|( x y )∉ R };

逆: R -1 ={( y x )|( x y )∈ R }∈ P Y × X );

合成:设 R 1 P X × Y ), R 2 P Y × Z ),则 R 1 R 2 的合成 R 1 ° R 2 P X × Z )定义为: R 1 ° R 2 ={( x z )|∃ y Y ,( x y )∈ R 1 且( y z )∈ R 2 }。

例1.5 X ={1,2,3}, Y ={ a b c d }, Z ={甲,乙},若

R 1 ={(1, a ),(1, c ),(2, b ),(3, a ),(3, d )}∈ P X × Y ),

R 2 ={( a ,甲),( c ,甲),( b ,乙),( d ,乙)}∈ P Y × Z ),

={(1,甲),(3,甲),(2,乙),(3,乙)}∈ P X × Z )。

1.2.4 特征关系

关系的特征函数称为特征关系。

定义1.9 R P X × Y ),则 R 的特征函数

称为 R 的特征关系。 fR x y )可理解为 x y 具有 R 的程度。

若从特征关系的角度看关系的运算,则有

(ⅰ) x y )∈ X × Y

(ⅱ) x y )∈ X × Y

(ⅲ) x y )∈ X × Y x y )=1- fR x y );

(ⅳ) x y )∈ X × Y y x )= fR x y );

(ⅴ) R 1 P X × Y ), R 2 P Y × Z ),则 x z )∈ X × Z

(ⅵ) R 1 R 2 x y )∈ X × Y 1 2;

(ⅶ) R 1 = R 2 x y )∈ X × Y 1 2 。

1.2.5 关系的矩阵表示

关系的表示方法很多,除了用直积的子集表示外,对于有限论域情形,用矩阵表示在运算上更为方便。有限集之间的关系可用矩阵表示。设

X ={ x 1 x 2 ,…, x n }, Y ={ y 1, y 2 ,…, y m }, R P X × Y )  (1.3)

R 写成矩阵,有

矩阵的行数 n X 中元素的个数,列数 m Y 中元素的个数, r ij =1 x i Ry j 。关系矩阵中的元素或是0或是1,在数学上把诸元素只是0或1的矩阵称为布尔(Boole)矩阵。因此,任何普通二元关系的矩阵都是布尔矩阵。

例1.6 X ={2,3}, Y ={1,2,3,4},从 X Y 的小于关系为

R 可写成矩阵形式

R ={( x y )| x < y x X y Y }={(2,3),(3,4),(2,4)}  (1.5)

关系的各种运算可在矩阵中进行。

R 1 =( r ij n×m R 2 =( s ij n×m ,则

R 1 R 2 =(m ax( r ij s ij )) n × m R 1 R 2 =(min( r ij s ij )) n × m =(1- r ij n × m R -1 R 的转置。

如果两关系均用矩阵表示,则复合关系可用类似于矩阵乘法的方法得到,“乘”换成“取小”,“加”换成“取大”。

例1.8 X ={ x 1 x 2 x 3 x 4 }, Y ={ y 1, y 2 y 3 }, Z ={ z 1 z 2 z 3 },从 X Y 的关系 R ={( x 2 y 3 ),( x 3 y 1 ),( x 4 y 3 )}, Y Z 的关系 Q ={( y 2 z 3 ),( y 3 z 1 )},求

解:

从而, ={( x 2 z 1 ),( x 4 z 1 )}。与定义式直接运算的结果一致。

1.2.6 等价关系与划分

定义1.10 R X 上的关系,若 x X ,有 xRx ,即 χ R x x )=1,则称 R 是自反的。

x y X ,若 xRy yRx ,即 χ R x y )= χ R y x ),则称R是对称的。

x y z X ,若 xRy yRz xRz ,即 χ R x y )=1, χ R y z )=1, χ R x z )=1,则称 R 是传递的。

设N为自然数集,N上的关系“<”具有传递性,但不具有自反性和对称性。

P X )为 X 的幂集, P X )上的关系“ ”具有自反性和传递性,但不具有对称性。

为了将集合的元素进行分类,下面引进一个重要的关系——等价关系。

定义1.11 设集合 X 上的二元关系 R 具有自反性、对称性和传递性,则称 R X 上的等价关系,此时 xRy 又称为 x 等价于 y ,记为 x y

比如,“同龄关系”,数学上的“=”都是等价关系,而朋友关系不是等价关系,因为它不具有传递性。

集合 X 上的等价关系的重要性在于可以将集合 X 分成适当的子集(实际上就是将集合 X 进行分类),为此又引进下面的定义。

定义1.12 X 是非空集, X i X 的一些非空子集,若∪ X i = X ,且 X i X j =∅( i j ),则称集合族 {…, X i …}为 X 的一个划分,称集 X i 为这个划分的一个类( i I I 为指标集),以∏表示划分,即为∏= { X i | X i X ,且 x X 恰属于 X i }。

划分∏的每一个元素称为一个块,也称为划分的一个类。

当划分的块数为有限时,划分∏也可表示为∏={ X 1 X 2 ,…, X n }, n 为块数。

显然,对有限集而言,它的划分块数一定是有限的。

例1.9 X ={1,2,3,4},则∏ 1 ={{1},{2},{3},{4}},∏ 2 ={{1,2},{3},{4}},∏3={{1,2,3},{4}},∏4={{1,2},{3,4}},∏5={{1,2,3,4}}等都是 X 的划分,但∏'={{1},{2,3}},∏″={{1},{2,3},{2,4}}等不是 X 的划分。

下面的定理说明了集合 X 上的等价关系与划分(即分类)之间的联系。

定理 集合 X 上的任一等价关系可以确定 X 的一个划分(即分类);反过来,集合 X 的任一划分(即分类)可以确定 X 上的一个等价关系。

例1.10 设论域 X = {某高校全体本科生(四年制)},在 X 上定义了 R 1 =“同年级关系”,显然“同年级关系”是一个等价关系。因此,关系 R 1 X 划分为四个不同的年级: X ={ X 1 X 2, X 3 X 4 },其中 X i 表示 i 年级, i =1,2,3,4。这就表明,论域 X 上的等价关系 R 1 (同年级关系)可以确定一个划分(分类): X ={ X 1 X 2, X 3 X 4 }。

例1.11 设论域 X = {某高校学生},在论域 X 上有一个划分(分类): X ={男生,女生}={ Y 1 Y 2 },因为这个划分是按性别划的,所以这个划分可以确定 X 上的一个关系 R 2 =“同性别关系”。显然,“同性别关系”= R 2 是一个等价关系。

定义1.13 R 是集合 X 上的关系,若关系 R 是自反的、对称的,则称 R 是相似关系。

例如朋友关系、同学关系都是相似关系。

与等价关系一样,相似关系的应用也是非常广泛的。 YRsW1+0GSeh7h3cvpZHW7hPfEqFbpaSMtJMhXb0b+3DB4sIFRWygYktHUGnVQ9uO

点击中间区域
呼出菜单
上一章
目录
下一章
×