离散数学教案 - 图文(2)

(A?B)?C?A?(B?C)

定理3.4.1 设A、B和C为任意三个集合，则有 （1）A?(B?C)?(A?B)?(A?C) （2）A?(B?C)?(A?B)?(A?C) （3）(A?B)?C?(A?C)?(B?C) （4）(A?B)?C?(A?C)?(B?C)

证明 （1）设x,y?A?(B?C)?x?A?y?B?C ?x?A?(y?B?y?C)

?(x?A?y?B)?(x?A?y?C) ?x,y?A?B?x,y?A?C ?x,y?(A?B)?(A?C)

因此， A?(B?C)?(A?B)?(A?C)。

（4）设x,y?(A?B)?C?x?A?B?y?C ?(x?A?x?B)?y?C

?(x?A?y?C)?(x?B?y?C) ?x,y?A?C?x,y?B?C ?x,y?(A?C)?(B?C) 因此， (A?B)?C?(A?C)?(B?C)。 定理3.4.2 设A、B和C为三个非空集合，则有 A?B?A?C?B?C?C?A?C ?证明 设A?B，对任意的x,y，

x,y?A?C?x?A?y?C

?x?B?y?C

?x,y?B?C

因此， A?C?B?C。

反之，若A?C?B?C，取y?C，则对?x，有

x?A?x?A?y?C??x,y?A?C

x,y?B?C?x?B?y?C

?x?B

因此，A?B。

定理的第二部分A?B?C?A?C?B，证明类似。

定理3.4.3 设A、B、C和D为四个非空集合，则A?B?C?D的充要条件为A?C且B?D。

证明 若A?B?C?D，对任意的x?A,y?B，有

(x?A)?(y?B)?x,y?A?B?x,y?C?D

?(x?C)?(y?D) 即 A?C,B?D。

79

反之，若A?C且B?D，设任意x?A,y?B，有

A?(y? )B x,y?A?B?(x?)?(x?C)?(y?D)

?x,y?C?D

因此， A?B?C?D。

对于有限个集合可以进行多次笛卡尔积运算。为了与有序n元组一致，我们约定：

A1?A2?A3?(A1?A2)?A3

A1?A2?A3?A4?(A1?A2?A3)?A4

?((A1?A2)?A3)?A4

一般地，A1?A2???An?(A1?A2???An?1)?An

?{x1,x2,?,xnx1?A1?x2?A2???xn?An}

故A1?A2???An是有序n元组构成的集合。

A?A??A，记为A, 这里A?A特别地，同一集合的n次直积????????nnnn?1?A。

例如，{1,2}?{1,2}?{1,2}?{1,1,1,2,2,1,2,2}?{1,2} ?{1,1,1,1,1,2,1,2,1,1,2,2,

2,1,1,2,1,2,2,2,1,2,2,2}

32 ?{(1,1,1),(1,1,2),(1,2,1),(1,2,2),(2,1,1),(2,1,2),(2,2,1),(2,2,2)}

此处，A?2,A?2?8。一般地，若 A?m,则A33n?m。

n3.5 关系及其表示

3.5.1 关系的定义

在日常生活中我们都熟悉关系这词的含义，例如，父子关系、上下级关系、朋友关系等。

我们知道，序偶可以表达两个客体、三个客体或n个客体之间的联系，因此可以用序偶表达关系这个概念。

例如，机票与舱位之间有对号关系。设X表示机票的集合，Y表示舱位的集合，则对于任意的x?X和y?Y，必有x与y有对号关系和x与y没有对号关系两种情况的一种。令R表示“对号”关系，则上述问题可以表达为xRy或xRy，亦可记为x,y?R或x,y?R，因此，我们看到对号关系R是序偶的集合。

定义3.5.1 设X、Y是任意两个集合，则称直积X?Y的任一子集为从X到Y的一个二元关系(Binary Relation )。二元关系亦简称关系，记为R，R?X?Y。

X到Y的二元关系R，如图3-4所示。

80

图3-4

集合X到Y的二元关系是第一坐标取自X、第二坐标取自Y的序偶集合。如果序偶

x,y?R，也说x与y有关系R，记为xRy；如果序偶x,y?R，则说x与y没有关系R，

记为xRy。

当X?Y时，关系R是X?X的子集，这时称R为集合X上的二元关系。 例3.5.1 （1）设A?{a,b}，B?{2,5,8}，则

A?B?{a,2,a,5,a,8,b,2,b,5,b,8}，

令

R1?{a,2,a,8,b,2} R2?{a,5,b,2,b,5} R3?{a,2}

因为R1?A?B，R2?A?B，R3?A?B，所以R1，R2和R3均是由A到B的关系。 （2）>={x,yx,y是实数且x?y}是实数集上的大于关系。 定义3.5.2 设R为X到Y的二元关系，由x,y或前域(Domain)，记作domR或D(R)，即

domR?{x(?y)(x,y?R)}

使x,y?R的所有y组成的集合称为R的值域(Range)，记作ranR，即

ranR?{y(?x)(x,y?R)}。

R的定义域和值域一起称作R的域(Field)，记作FLDR，即

FLDR? domR?ranR

?R的所有x组成的集合称为R的定义域

显然，domR?X，ranR?Y，FLDR?domR?ranR?X?Y

例3.5.2 设A?{1,3,7}，B?{1,2,6}，H?{1,2,1,6,7,2}，求domH，ran H和FLDH。

解 domH?{1,7}，ran H?{2,6}，FLDH?{1,2,6,7}。 例3.5.3 设X?{2,3,4,5}，求集合X上的关系“?”、dom?及ran?。 解 ??{2,3,2,4,2,5,3,4,3,5,4,5}

dom??{2,3,4} ran??{3,4,5}

3.5.2 几种特殊的关系

1．空关系

对任意集合X，Y，??X?Y，??X?X，所以?是由X到Y的关系，也是X上的关系，称为空关系(Empty Relation)。

2．全域关系

因为X?Y?X?Y，X?X?X?X，所以X?Y是一个由X到Y的关系，称为由X到Y的全域关系(Universal Relation)。X?X是X上的一个关系，称为X上的全域关系，通常记作EX，即

EX?{xi,xjxi,xj?X}。

81

例3.5.4 若H?{f,m,s,d}表示家庭中父、母、子、女四个人的集合，确定H上的全域关系和空关系，另外再确定H上的一个关系，并指出该关系的前域和值域。

解 设H上同一家庭的成员的关系为H1，

H1?{f,f,f,m,f,s,f,d,m,f,m,m,m,s,m,d,

s,f,s,m,s,s,s,d,d,f,d,m,d,s,d,d}

设H上的互不相识的关系为H2，H2??，则H1为全域关系，H2为空关系。 设H上的长幼关系为H3，

H3?{f,s,f,d,m,s,m,d}

domH3?{f,m} ranH3?{s,d} 3．恒等关系

定义3.5.3 设IX是X上的二元关系且满足IX??x,xx?X)?，则称IX是X上的恒等关系(Identical Relation)。

例如，A?{1,2,3}，则IA??1,1,2,2,3,3?。

因为关系是序偶的集合，因此，可以进行集合的所有运算。 定理3.5.1 若Q和S是从集合X到集合Y的两个关系，则Q、S的并、交、补、差仍是X到Y的关系。

证明 因为 Q?X?Y,S?X?Y,

故 Q?S?X?Y,Q?S?X?Y

S?(X?Y?S)?X?Y Q?S?(Q?S)?X?Y

例3.5.5 若A?{1,2,3,4}，R1?{x,yR2?{x,y(x?y)/2?A,x,y?A}，

(x?y)/3?A,x,y?A}，求R1?R2 ，R1?R2，R1?R2和R1。

解 R1?{3,1,4,2}，R2?{4,1}，

R1?R2??

R1?R2?{3,1,4,2,4,1}

R1?R2?R1 R1?EA?R1

?{1,1,1,2,1,3,1,4,2,1,2,2,2,3,2,4, 3,2,3,3,3,4,4,1,4,3,4,4}

3.5.3 关系的表示 1．集合表示法

因为关系是序偶的集合，因此可用表示集合的列举法或描述法来表示关系。例如，例3.5.1的（1）中的关系R1，R2和R3及例3.5.2中的关系H，均是用列举法表示的关系；而例3.5.1的（2）中的关系?和例3.5.5中的关系R1，R2都是用描述法表示的关系。

有限集合间的二元关系R除了可以用序偶集合的形式表达以外，还可用矩阵和图形表示，

82

以便引入线性代数和图论的知识来讨论。

2．矩阵表示法

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

当xi,yj?R当xi,yj?R (i?1,2?,m,j?;1?,2,n。

如果R是有限集合X上的二元关系或X和Y含有相同数量的有限个元素，则MR是方阵。

例3.5.6 若A?{a1,a2,a3,a4,a5}，B?{b1,b2,b3}，

R?{a1,b1,a1,b3,a2,b2,a2,b3,a3,b1,a4,b2,a5,b2}，写出关系矩阵MR。

解

?1?0???1??0?0?010111??1?0? ?0?0??5?3MR 例3.5.7 设X?{1,2,3,4}，写出集合X上的大于关系>的关系矩阵。 解 >?{2,1,3,1,3,2,4,1,4,2,4,3}

?0?1???1??1001100010??0? 0??0? M?3．关系图表示法

有限集合的二元关系也可用图形来表示。设集合X??x1,x2,?,xm?到Y??y1,y2,?,yn?上的一个二元关系为R，首先我们在平面上做出m个结点分别记作x1,x2,?,xm，另外做n个结点分别记作y1,y2,?,yn。如果xiRyj，则从结点xi至结点yj做一有向弧，其箭头指向yj，如果xiRyj，则xi,yj之间没有线段连接。用这种方法连接起来的图称为R的关系图。

例3.5.8 画出例3.5.6的关系图。 解 本题的关系图如图3-11所示：

83

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库离散数学教案 - 图文(2)在线全文阅读。