关于礼物的作文-描写月亮的作文

《离散数学》教案
第一章 集合与关系
集合是数学中最基本的概念，又是 数学各分支、自然科学及社会科学各领域的最普
遍采用的描述工具。集合论是离散数学的重要组成部分， 是现代数学中占有独特地位的
一个分支。
G. Cantor(康脱)是作为数学分支的集合 论的奠基人。1870年前后，他关于无穷序
列的研究导致集合论的系统发展。1874年他发表了关于 实数集合不能与自然数集合建
立一一对应的有名的证明。1878年，他引进了两个集合具有相等的“势 ”的概念。然
而，朴素集合论中包含着悖论。第一个悖论是布拉利-福尔蒂的最大序数悖论。1901年
罗素发现了有名的罗素悖论。1932年康脱也发表了关于最大基数的悖论。集合论的现
代公理 化开始于1908年策梅罗所发表的一组公理，经过弗兰克尔的加工，这个系统称
为策梅罗- 弗兰克尔集合论（ZF），其中包括1904年策梅罗引入的选择公理。另外一种
系统是冯·诺伊曼- 伯奈斯-哥德尔集合论。公理集合论中一个有名的猜想是连续统假设
（CH）。哥德尔证明了连续统假设 与策梅罗-弗兰克尔集合论的相容性，科恩证明了连续
统假设与策梅罗- 弗兰克尔集合论的独立性。现在把策梅罗-弗兰克尔集合论与选择公理
一起称为ZFC系统。
一、学习目的与要求
本章目的是介绍集合的基本概念，讲授集合运算的基本理论，关系的定义 与运算。
通过本章的学习，使学生了解集合是数学的基本语言，掌握主要的集合运算方法和关系
运算方法，为学习后续章节打下良好基础。
二、知识点
1．集合的基本概念与表示方法；
2．集合的运算；
3．序偶与笛卡尔积；
4．关系及其表示、关系矩阵、关系图；
5．关系的性质，符合关系、逆关系；
6．关系的闭包运算；
7．集合的划分与覆盖、等价 关系与等价类；相容关系；
8．序关系、偏序集、哈斯图。

三、要求
1．识记
集合的层次关系、集合与其元素间的关系，自反 关系、对称关系、传递关系的识别，
复合关系、逆关系的识别。
2．领会
领会下列概念：两个集合相等的概念几证明方法，关系的闭包运算，关系等价性证
明。

集合论的基本概念与运算
1.1.1 集合的概念
集合不能 精确定义。集合可以描述为：一个集合把世间万物分成两类,一些对象属
于该集合，是组成这个集合的成 员，另一些对象不属于该集合。可以说，由于一个集合
的存在，世上的对象可分成两类，任一对象或属于 该集合或不属于该集合，二者必居其
一也只居其一。
直观地说，把一些事物汇集到一起组成一 个整体就叫集合，而这些事物就是这个集
合的元素或成员。
例如：方程x－1＝0的实数解集合；26个英文字母的集合；坐标平面上所有点的
集合；……
集合通常用大写的英文字母A,B,C,…,来标记，元素通常用小写字母a,b,c,…,来
表示。例如自然数集合N(在离散数学中认为0也是自然数)，整数集合Z，有理数集合
Q，实数集合R ，复数集合C等。
集合的表示方法：表示一个集合的方法通常有三种：列举法、描述法和归纳定义
法。
(1) 列举法 列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起
来。在 能清楚地表示集合成员的情况下可使用省略号。
例如 A={a，b，c，…，z}，Z={0，±1，±2，…}都是合法的表示。
(2) 描述法 用谓词来概括集合中元素的属性来表示这个集合。
例如 B＝{x|x∈R∧x－1＝0}表示方程x－1＝0的实数解集。
许多集合可以用两种方法来表示， 如B也可以写成{-1，1}。但是有些集合不可以
用列元素法表示，如实数集合。
(3) 归纳定义法：节再讨论。
属于、不属于：元素和集合之间的关系是隶属关系，即属于或不属于，属于记 作
∈，不属于记作

。例如A＝{a，{b，c}，d，{{d}}}，这里a∈A， {b，c}∈A，d∈A，
{{d}}∈A，但b

A，{d}

A 。b和{d}是A的元素的元素。
外延公理：两个集合A和B相等，当且仅当它们有相同的成员。
集合的元素是彼此不同的：如果同一个元素在集合中多次出现应该认为是一个元
素。
如 {1，1，2，2，3}＝{1，2，3}。
集合的元素是无序的：如{1，2，3}＝{3，1，2}。
22
2

1.1.2 集合间的关系
定义1.1.1 设A， B为集合，如果B中的每个元素都是A中的元素，则称B是A的
子集合，简称子集。这时也称B被A包含 ，或A包含B，记作B

A。称B是A的扩集。
包含的符号化表示为：B

A


x(x∈B→x∈A)。如果B不被A包含，则记作
B

A。
例如 N

Z

Q

R

C，但Z

N。显然对任何集合A都有A

A。
注意 ：属于关系和包含关系都是两个集合之间的关系，对于某些集合可以同时成立
这两种关系。例如A＝{a ，{a}}和{a}，既有{a}∈A，又有{a}

A。前者把它们看成是
不同层次 上的两个集合，后者把它们看成是同一层次上的两个集合，都是正确的。
定义1.1.2 设A，B 为集合，如果B

A且B≠A，则称B是A的真子集，记作B

A。
如果B不是A的真子集，则记作B

A。真子集的符号化表示为：B

A
B

A∧B≠A。
例如 N

Z
Q

R

C，但N

N。
为方便起见，所讨 论的全部集合和元素是限于某一论述域中，即使这个论述域有时
没有明确地指出，但表示集合元素的变元 只能在该域中取值。此论述域常用U表示，并
称为全集。
定义1.1.3 不含任何元素的 集合叫空集，记作

。空集可以符号化表示为

＝
{x|x≠x}。
例如{x|x∈R∧x+1=0}是方程x+1=0的实数解集，因为该方程无实数解，所以是空
集。
定理 空集是一切集合的子集。
证：对任何集合A，由子集定义有
A x(xxA)
，右边的蕴涵式
因前件为假而为真命题，所以
A
也为真。
推论 空集是唯一的。
证：假设存在空集

1
和
2
，由定理有

1

2
，
2

1
。根据集合相等的定
义，有

1

2
。
含有n个元素的集合简称n元集，它的含有m(m≤n)个元素的子集叫做它的 m元子
集。任给一个n元集，怎样求出它的全部子集呢？举例说明如下。
例1.1.1 A＝{1,2,3}，将A的子集分类：
22

0元子集，也就是空集，只有一 个：

；1元子集，即单元集：{1}，{2}，{3}；
2元子集：{1,2}，{1,3}，{2,3}； 3元子集：{1,2,3}。
一般地说，对于n元集A，它的0元子集有
C
n
个，1元子集有
C
n
个，…，m元子
m01nn
n
集有
C
n
个，…， n元子集有
C
n
个。子集总数为
C
n
C
n
LC
n
2
个。
0
1
全集与空集在本章中起重要作用，注意掌握它们的基本概念。
注意：∈与

的联系与区别。
(1) ∈表示集合的元素（可以为集合）与集合本身的从属关系，
(2)

表示两个集合之间的包含关系。
例如：对于集合A={a,b,c},{a}是A 的子集：{a}

A，a是A的元素：a∈A。
注意：不要写成{a}∈A和a

A。
a{a}
，但
a {a}
；
{}
是一元集，而不是空集。
|{}|1
，
||0
。
1.1.3 集合的运算
集合的交、并和差运算
1. 集合交、并、差运算的定义（注意集合运算与逻辑运算的对应关系）
定义 设
A
和
B
是集合，
(1)
A
和
B的交记为
AIB
，定义为：
AIB{x|xAxB}
；
(2)
A
和
B
的并记为
AUB
，定义为：
AUB{x|xAxB}
；
(3)
A
和
B
的 差记为
AB
，定义为：
AB{x|xAxB}
。
例：设
A{a,b,c,d}
，
B{b,c,e}
，则
AIB{b,c}
，
AUB{a,b,c,d,e}
，
AB{a, d}
，
BA{e}

定义：如果
A,B
是两个集合，< br>AIB
，那么称
A
和
B
是不相交的。如果
C是
一个集合的族，且
C
中的任意两个不同元素都不相交，那么称
C
是（两两）不相交集
合的族。
2. 集合的并和交运算的推广（广义交、广义并）

n
个集合
I
A
i
A
1< br>IA
2
ILIA
n
{x|xA
1
xA
2
LxA
n
}
，
i1
n
U
A AUA
i1
i1
n
2
ULUA
n
{x|x A
1
xA
2
LxA
n
}
，

无穷可数个集合：
I

i1
A
i
 A
1
IA
2
IL
，
U
A
i
A< br>1
UA
2
UL

i1
一般情形：
SC
I
S{x|S(SCxS)}
（
C
），
S C
U
S{x|S(SCxS)}

3. 集合交、并、差运算的性质：
(1) 交换律
AIBBIA
，
AUBBUA
，
(2) 结合律
(AIB)ICAI(BIC)
，
(AUB)UCAU(BUC)
.
(3) 分配律
AU(BIC)(AUB)I(AUC)
，
AI(BUC)(AIB)U(AIC)

(4) 幂等律
AIAA
,
AUAA
,
(5) 同一律
AUA
,
AIUA
，
(6) 零 律
AUUU

AI
,
(7) 吸收律
AU(AIB)A
，
AI(AUB)A
，
(8) 德摩根律
A(BUC)(AB)I(AC)

A(BIC)(AB)U(AC)

(9) (a)
AA
, (b)
ABA
, (c)
AAUB
, (d)
AIBA
,
(e) 若
A B
，
CD
,则
(AUC)(BUD)
，
(AIC) (BID)
,
(f) 若
AB
，则
AIBA
, (g) 若
AB
，则
AUBB
，
(h)
AIBAAUBBAB
。
证：利用运算的定义（与逻辑运算的关系）或已证明的性质。

集合的补运算
1. 集合的补运算的定义
定义：设
U
是论述域而
A
是< br>U
的子集，则
A
的（绝对）补为：
BA
当且仅当
AUBU
和
AIB
。
2. 集合补运算的性质：
(1) 矛盾律
AIA
； (2) 排中律
AUAU
；
(3) 德摩根律
U
，
U
，
AUBAIB
，
AIBAUB
；
(4) 双重否定律（
A
的补的补是
A
）：
AA
；(5) 若
AB
，则
BA
。
例：证明A－(B∪C)＝(A－B)∩( A－C)。
证对任意的x，
x∈A－(B∪C)

x∈A∧x

B∪C

x∈A∧┐(x∈B∨x∈C)
________________

x∈A∧(┐x∈B∧┐x∈C)

x∈A∧x

B∧x

C

(x∈A∧x

B)∧(x∈A∧x

C)

x∈A－B)∧x∈A－C

x∈(A－B)∩(A－C)
所以 A－(B∪C)＝(A－B)∩( A－C)。
例：证明A∩E＝A。
证对任意的x，x∈ A∩E

x∈A∧x∈E

x∈A(因为x∈E是恒真命题)，所以A
∩E＝A。
注意：以上证明的基本思想是：设P，Q为集合公式，欲证P＝Q，即证P
< br>Q∧Q

P
为真。
也就是要证对于任意的x有 x∈P
< br>x∈Q和x∈Q

x∈P成立。对于某些恒等式
可以将这两个方向的推理合到一 起，就是 x∈P

x∈Q。
不难看出，集合运算的规律和命题演算的某些规律是一 致的，所以命题演算的方法
是证明集合恒等式的基本方法。
证明集合恒等式的另一种方法是利用已知的恒等式来代入。
例：证明A∪(A∩B)＝A。
证 A∪(A∩B)＝(A∩E)∪(A∩B)＝A∩(E∪B)＝A∩(B∪E)＝A∩E＝A。
例：证明等式A－B＝A∩～B。

证对于任意的x，x∈A－B
< br>x∈A∧x

B

x∈A∧x∈～B

x∈A∩～B ，
所以A－B＝A∩～B。
注意：上式把相对补运算转换成交运算，这在证明有关相对补的恒等式中是很有用
的。
例：证明(A－B)∪B＝A∪B
证 (A－B)∪B＝(A∩～B)∪B＝(A∪B)∩(～B∪B)＝(A∪B)∩E＝A∪B。
例：证 明命题A∪B＝B

A∩B＝A

A－B＝

。
证
(1) 证A∪B＝B

A

B，对于任意的x， < br>x∈A

x∈A∨x∈B

x∈A∪B

x∈B(因 为A∪B＝B)，所以A

B。
(2) 证A

B
A∩B＝A。显然有A∩B

A，下面证A

A∩B，对于任意的x，
x∈A

x∈A∧x∈A

x∈A∧x∈B(因为A
B)

x∈A∩B，由集合相等的定义有
A∩B＝A。
(3) 证A∩B＝A

A－B＝

。
A－B＝A∩～B＝(A∩B)∩～ B(因为A∩B＝A)＝A∩(B∩～B)＝A∩

＝

。
(4) 证A－B＝


A∪B＝B。A∪B＝B∪(A－B)＝B∪

＝B 。
注意：上式给出了A

B的另外三种等价的定义，这不仅为证明两个集合之间的包
含关系提供了新方法，同时也可以用于集合公式的化简。
例：化简((A∪B∪C)∩(A∪B))－((A∪(B－C))∩A)。
解因为A∪B

A∪B∪C，A

A∪(B－C)，故有
((A∪B∪C)∩(A∪B))－((A∪(B－C))∩A)＝(A∪B)－A＝B－A。
定义：两集合
A,B
的环和（对称差）定义为：
环和：
AB(AB)U(BA){x|xAxBxAxB}

2. 环和与环积的性质：
(1)
AB(AUB)I(AUB)(AUB)(AIB)
，
(2)
ABAB
，
BAAB
，
(3)
(AB)CA(BC)
，
CI(AB)(CIA)(CIB)
；
(4)
AA
，
AA
，

(5)
ABACBC

例：已知A

B＝A

C，证明B＝C。
证 已知A

B＝A

C，所以有
A

(A

B)＝A

(A

C)

(A
A)

B＝(A

A)

C

< br>
B＝


C

B


＝ C



B＝C。
3. 集合运算的文氏图表示
注意：如果没有特殊说明，任何两个集合都画成相交的。
幂集合
定义：设A
是一个集合，
A
的幂集是
A
的所有子集的集合，即

(A){B|BA}
。
若
A
是
n
元集，则< br>
(A)
有
2
n
个元素。
例：若
A< br>，则

(A){}
；若
A{1,2}
，则
< br>(A){,{1},{2},{1,2}}
。
对任意集合
A
：< br>

(A)
，
A

(A)
。
集合运算的顺序：为了使得集合表达式更为简洁，我们对集合运算的优先顺序做如下
规定：称广义交，广 义并，幂集，绝对补运算为一类运算，交，并，补，环和，环积
运算为二类运算。一类运算优先于二类运 算；一类运算之间由右向左顺序进行；二类运
算之间由括号决定先后顺序。
1.2
1.2.1集合的笛卡儿积与二元关系
定义 1 由两个元素x和y（允许x=y）组成的 序列记作，称为二重组或有
序对或序偶，其中x是它的第一元素（分量），y是它的第二元素 （分量）。
有序对具有以下性质：
1．当x≠y时，≠； 2．=的充分必要条件是x=u且y=v。
注意：这些性质是二元集{x,y} 所不具备的。例如当x≠y时有{x,y}={y,x}。原因
在于有序对中的元素是有序的，而集合中 的元素是无序的。
例1 已知=<5,2x+y>，求x和y。
解 由有序对相等的充要条件有x+2=5，2x+y=4，解得x=3，y=-2。
定义2 设a
1
,a
2
,K,a
n
是
n(n2)
个元素，定义
关系及其表示

为
n
重组。
注意 ：
n
重组是一个二重组，其中第一个分量是
n1
重组。如
2,3 ,5
代表
2,3,5
而不代表
2,3,5
，按定 义后者不是三重组，并且
2,3,52,3,5
。
n
重 组
a
1
,a
2
,L,a
n1
,a
n< br>
与
b
1
,b
2
,L,b
n1
,b
n

相等当且仅当
a
i
b
i
，1in
。
定义3 设A，B为集合，用A中元素为第一元素，B中元素为第二元 素构成有序
对。所有这样的有序对组成的集合叫做A和B的笛卡儿积（叉积），记作A×B。
笛卡儿积的符号化表示为A×B={|x∈A∧y∈B}。
集合
A
1
,A
2
,K,A
n
（
n2
）的叉积记为A
1
A
2
LA
n
或
A
i，定义为
i1
n
例2 设A={a,b}, B={0,1,2}，则
A×B={,,,,,}；
B×A={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>}。
由排列组合的知识不难证明，如果|A|=m，|B|=n，则|A×B|=mn。
笛卡儿积的运算性质
(1).对任意集合A，根据定义有 A×

=

,

×A=

；
(2).一般地说，笛卡儿积运算不满足交换律，即A×B≠B×A(当A≠

∧B≠

∧A
≠B时)；
(3)．笛卡儿积运算不满足结合律，即(A×B)×C≠A×( B×C)(当A≠

∧B≠

∧
C≠

时)；
(4).笛卡儿积运算对并和交运算满足分配律，即
A×(B∪C)=(A×B)∪(A×C)； (B∪C)×A=(B×A)∪(C×A)；
A×(B∩C)=(A×B)∩(A×C)； (B∩C)×A=(B×A)∩(C×A)。
我们证明其中第一个等式。
证 任取，
∈A×(B∪C)

x∈A∧y∈B∪C

x∈A∧(y∈B∨y∈C)

(x∈A∧y∈B) ∨(x∈A∧y∈C)

∈A×B∨∈A×C

∈(A×
B∪A×C)

所以有 A×(B∪C) = (A×B)∪(A×C)。
(5)．A

C∧B

D
< br>A×B

C×D
性质5的证明和性质4类似，也采用命题演算的方法。
注意：性质5的逆命题不成立，可分以下情况讨论。
(a) 当A=B=

时，显然有A

C和B

D成立。
(b) 当A≠

且B≠

时，也有A

C和B< br>
D成立。证明如下：任取x∈A，由于
B≠

,必存在y∈B，因此 有x∈A∧y∈B

∈A×B

∈C×D
< br>x∈C∧y∈
D

x∈C，
从而证明了A

C。同理可证B

D。
(c) 当A=< br>
而B≠

时，有A

C成立，但不一定有B
D成立。
反例：令A=

，B={1}，C={3}，D={4}。
(d) 当A≠

而B=

时，有B

D成立，但 不一定有A

C成立。反例类似于(c)。
例3 设A={1,2},求P(A)×A。
解 P(A)×A={

,{1},{2},{1,2}}×{1,2}
={<

,1>,<

,2>,<{1},1>,<{1},2>,<{2},1>,<{2 },2>,<{1,2},1>,<{1,2},2>}
例4 设A，B，C，D为任意集合，判断以下命题是否为真，并说明理由。
(1) A×B=A×C

B=C； (2) A-(B×C)=(A-B)×(A-C)；
(3) A=B∧C=D

A×C=B×D； (4) 存在集合A，使得A

A×A。
解(1) 不一定为真。当A=

，B={1},C={2}时，有A×B=

=A×C，但B≠C。
(2) 不一定为真。当A=B={1},C={2}时有A-(B×C)={1}–{<1,2>}={1}，
(A-B)×(A-C)=

×{1}=


(3) 为真。由等量代入的原理可证。
(4) 为真。当A=

时有A

A×A成立。
定理1：若
A< br>i
(i1,2,K,n)
都是有限集合，则
|A
1
A2
LA
n
||A
1
|g|A
2
|gLg |A
n
|
。
定义4 如果一个集合满足以下条件之一：（1）集合非空， 且它的元素都是有序对；
（2）集合是空集；则称该集合为一个二元关系，记作R。二元关系也可简称为 关系。
对于二元关系
R
，若
x,yR
，则称
x,y
有关系
R
，可记作
xRy
；若

x,y R
，则记作
xRy
。一般地
x,yy,x
，因此
xRyyRx
。
例1
R
1
{1,2,a,b}< br>，
R
2
{1,2,a,b}
，则
R
1
是二元关系，
R
2
不是二
aR
1
b
元关系，只是一 个集合，除非将a和b定义为有序对。根据以上记法可以写成
1R
1
2
，等。
定义5 设
A,B
为集合，
AB
的任何子集所定义的二 元关系叫做从
A
到
B
的二元
关系，特别地，当
AB
时，则叫做
A
上的二元关系。
A
1
A
2
L A
n
的子集称为
A
1
A
2
LA
n< br>上的一个
n
元关系，当
A
1
A
2
LA
n
时称为
A
上的一个
n
元关系。
例2
A{0,1}
,
B{1,2,3}
，那么
R
1
{0 ,2}
，
R
2
AB
，
R
3
，
R
4
{0,1}
等都是从
A
到
B的二元关系，而其中
R
3
和
R
4
同时也是
A< br>上的二元关
系。
注：可把
A
到
B
的二元关系看成是
AUB
上的二元关系或
(AUB)
上的二元关系。
二元关系的数目 ：集合
A
上的二元关系的数目依赖于
A
中的元素数。如果
|A|n
，
n
那么
|AA|n
，
AA
的子集就有2
个。每一个子集代表一个
A
上的二元关系，所
2
2
2
以
A
上有
2
个不同的二元关系。例如
|A|3
， 则
A
上有
2
n
2
3
2
512
个 不同的二元关系。
如果
|A
i
|m
i
，则
|A< br>1
A
2
LA
n
|m
1
m
2
Lm
n
，因此
A
1
A
2
LA
n
上有
2
m
1
m
2
Lm
n
个不同的
n
元关系。
一些重要关系：
(1) 空关系：若
R
，则
R
称为空关系；
(2) 全域关系：
E
A
{x,y|xAyB}AB

(3) 恒等关系：
A
上的二元关系
I
A
{x,x| xA}
称为恒等关系。
(4) 小于或等于关系：
L
A
{x ,y|x,yAxy}
，这里
AR
；

(5) < br>B
上的整除关系：
D
B
{x,y|x,yBx
整除
y}
，这里
AZ
（非零整
数集）；
(6)
A
上的包含关系：
R

{x,y|x,yAxy}
，这里
A
是集合族。
例3 设
A{1,2,3}
，
B{a ,b}
，
C

(B){,{a},{b},{a,b}}
，则

L
A
{1,1,1,2,1,3,2,2,2,3 ,3,3}
，
C
上的包含关系：
R

{, ,,{a},,{b},,{a,b},{a},{a},

{a} ,{a,b},{b},{b},{b},{a,b},{a,b},{a,b}}
。
类似的还可以定义大于等于关系，小于关系，大于关系，真包含关系等等。
关系是有序对的集 合，因此对它可进行集合运算，运算结果定义一个新的关系。例
如：设
R
和
S
是给定集合上的关系，则
RUS
，
RIS
，
RS
，
R
分别称为关系
R
与
S
的并关系，交关系，差关系和R的 补关系。这样一来，可以从已知关系派生出各种
新关系。
二元关系
A
到
B
的二元关系可以用一个图来形象地表示。
定义6 设R
是
A
到
B
的一个二元关系，则
A
叫着关系< br>R
的前域，
B
叫着关系
R
的陪域；
D(R){x| y(x,yR)}
称为关系
R
的定义域；
R(R){y|x( x,yR)}
称为关系
R
的值域。
关于关系的定义域、值域的一些性质：
D(RUS)D(R)UD(S)
；
D(RIS)D(R)ID(S)
；
R(RUS)R(R)UR(S)
；
D(RIS)R(R)IR(S)
。
证明 （证明第一个式子，其余类似）
1.2.2关系矩阵与关系图
(1) 集合表示法：非空关系都是元素为有序对的集合。

(2) 关系图：设
A{ x
1
,x
2
,K,x
n
}
，
R
是
A
上的关系，令图
GV,E
，其中
顶点集合
VA< br>，边集为
E
，对于
x
i
,x
j
V
，满足
x
i
,x
j
Ex
i
Rx
j
，则称图
G
为
R
的关系图，记作
G
R
。

1x
i
Rx
j
A{x,x,K,x}
(3)关 系矩阵：设，
12n
，
R
是
A
上的关系，令
rij


0xRx
ij

(i,j1,2,K,n )


r
11
r
12

r
21< br>r
22

则
(r
ij
)

MM< br>

r
n1
r
n2
L
L
O
L
r
1n


r
2n

称为关系
R
的关系矩阵，记作
M
R
。
M


r
nn

例 空关系的关系矩阵为全
0
矩阵：
M
A
0
； 全域关系的关 系矩阵为全
1
矩阵，
记为
J
；相等关系的关系矩阵为单位矩阵：M
I
A
I
。
基于关系
R
与关系矩阵
M
R
互相唯一决定的特性，可用关系矩阵有效地刻画关系的许
多性质。如对于有限集 A上的任意关系
R
与
S
：
RSM
R
M
S
；
RSM
R
M
S
。

关系的运算
1.3.1关系的逆
%
定义1 设
R
是从
A
到
B
的二元关系，关系
R
的逆（
R
的逆关系）记为
R
，定义
如下：
%
当
A
上的关系
R
具有对称性时，
RR
。
相等关系的逆是相等关系；空关系的逆是空关系；全域关系的逆是全域关系。
%
列举 法：把
R
中每个有序对的第一和第二成分都加以交换，就可得到逆关系
R
的< br>所有元素。
%
。 对
xA
和
yB
来说，这意味 着
xRyyRx
关系矩阵：将
M
R
的行和列交换即可得到
M
R
%
，即
M
R
%
M
R
（M
R
表示
M
R
的转
置）。
T
T%
关系图：颠倒
R
的关系图中的每条弧（有向边）的箭头，就得到
R的关系图。
逆关系的性质：
(1) 设
R,R
1
,R
2
都是从
A
到
B
的二元关系，则
%
%
RR
%
RR
%
U
R
%
；(c)
R
I
%
I
R
%
；(d)
%
(a)
(R)R
；(b)
R
1
U
2121212
%
R
%
； R
1

%
R
2
R
12
%
%
，
%
R
%
； (e)
RR
（
RABR
）； (f)
R
1< br>R
2
R
12
%
R
%
。
R
2
)R
(2) 设
R
1
是从
A到
B
的关系，
R
2
是从
B
到
C
的关系，则
(R
1
%
21
1.3.2关系的合成
定义2 设
R
1
是从
A
到
B
的关系，
R
2
是从
B
到
C
的关系，则
R
1
与
R
2
的合成（右
复合）为从
A
到
C
的关系，记为R
1
R
2
或
R
1
gR
2
（其 中
g
表示合成运算），定义为
R
1
R
2
{a ,c|aAcCb(bBa,bR
1
b,cR
2)}
。

例1 设
A{1,2,3,4}
，
B{2,3,4}
，
C{1,2,3}
，
R
1
是从A
到
B
的关系，
R
2
是从
B
到
C
的关系：
R
1
{x,y|xy6}{2,4,3, 3,4,2}
，
R
2
{y,z|yz1}{2,1 ,3,2,4,3}
。
分别用列举法、图示法、关系矩阵表示关系的合成
R
1
gR
2
，
R
2
gR
1
。
例2 设
A{1,2,3,4,5}
，
R
1
和
R
2
都是
A
上的二元关系，如果
R
1
{1,2,3,4,2,2}
，
R
2
{4,2,2,5,3,1,1,3}
，
分别用列举法、图示法、关系矩阵表示关系的合成
R
1
R
2
，R
2
R
1
，
(R
1
R
2
)R
1
，
R
1
(R
2
R
1
)
，
R
1
R
1
，
R
2
R2
等。
合成关系的性质：
(1) 设
R
是从
A到
B
的关系，
I
A
,I
B
分别是
A, B
上的相等关系，则
I
A
RRI
B
R
；
(2) 如果关系
R
1
的值域与
R
2
的定义域的交 集为空集，则合成关系
R
1
R
2
是空关
系；
(3) 关系的合成关于交和并的分配律：
设
R
1
是从
A
到
B
的关系，
R
2
,R
3
是从
B
到
C
的关系，
R
4
是从
C
到
D< br>的关系，则
(a)
R
1
(R
2
UR
3< br>)(R
1
R
2
)U(R
1
R
3
)
，(b)
R
1
(R
2
IR
3
)(R< br>1
R
2
)I(R
1
R
3
)
；
(c)
(R
2
UR
3
)R
4
(R2
R
4
)U(R
3
R
4
)
，(d)
(R
2
IR
3
)R
4
(R
2
R
4
)I(R
3
R
4
)
；
(4) 关系的合成满足结合律：
设
R
1
,R
2
,R
3< br>分别是从
A
到
B
，
B
到
C
，
C
到
D
的关系，则
(R
1
R
2
)R3
R
1
(R
2
R
3
)
。

1.3.3 关系的幂
定义3设
R
是集合
A
上的二元关系，则
R
的
n
次幂记为
R
n
，
nN
为任一自然数，
定义为：(1)
R
0
为
A
上的相等关系，
R{x,x|xA}
(2)
R
n1
R
n
R
。
关系的幂运算的性质：
0010
(1) 对
A
上的任意关系
R
1
,R2
有：
R
1
R
2
I
A
，
R
1
R
1
R
1
I
A
R
1
R
1
；
0
(2) 设
R
是集合
A上的二元关系，
m,nN
，则
RRR
mnmn
，
(R)R
mnmn
；
(3) 设
|A|n
，
R是集合
A
上的一个二元关系，则存在
i
和
j
，
0ij2
n
使
2
R
i
R
j
；
(4) 循环性质：设
R
是集合
A
上的二元关系，若存在
i
和
j
，
ij
，使
RR
，
则
(a) 对所有
k0
，
R
ik
ij
R
jk
； (b) 对所有
k,m0
，
R
imdk
 R
ik
（其中
012j1
；(c) 令
S{R,R,R,L, R}
，则
R
的每一次幂是
S
的元素，即对
dji
）
nN
，
R
n
S
。
关系的幂的计算： < br>给定
A
上的关系
R
和自然数
n
，怎样计算
R
呢？若
n
是
0
或
1
，结果是很简单的。
下面考虑
n2
的情况。
如果
R
是用集合表达式给出的， 可以通过
n1
次合成计算得到
R
。
如果
R
是用 关系矩阵
M
给出的，则
R
的关系矩阵是
M
，即
n< br>个矩阵
M
之积。
与普通矩阵乘法不同的是，其中的相加是逻辑加，即
1 11,10011,000
。
如果R是用关系图
G
给出的 ，可以直接由图
G
得到
R
的关系图
G

。
G

的顶点集
与
G
相同。考察
G
的每个顶点
x
i
，如果在
G
中从
x
i
出发经过
n< br>步长的路径到达顶点
n
nn
n
n

x
j
，则在
G

中加一条从
x
i
到
x
j
的边。当把所有这样的边都找到以后，就得到图
G

。
例3 设
A{a,b,c,d}
，
R{a,b,b,a,b,c,c,d }
，求
R
的各次
幂，分别用矩阵和关系图表示。

0

1
解
R
的关系矩阵为
M


0


0

1

0
2
MMM


0


0

1

0
43
MMM


0


0
42
100


010

234，则
R,R,R
的关系矩阵分别是
001


000

01


10

，

00
00

010

01

101

10
32
，
MMM


00000


000

00
010


101



000

000

53246因此
MM
，
RR
，
L
。所以可以得到
R RRL
，

1

0
0
357
0
RRRL
，而
R
，即
I
A
的关系矩阵为
M 


0


0
次幂的关系矩阵都得到了。 000


100

。至此，
R
各

010

001

用关系图的方法得到
R,R,R,R,L
的关系图如下图所示。
合成关系的矩阵表达
二元集
{T,F}{1,0}
上的布尔运算：
①
TFFTTTT
，
FFF
；
1001111
，
0123
000
；
②
TFFTFFF
，
TTT
；
1001000
，
111
；

③
¬TF
，
¬FT
；
¬10
，
¬01
；
④ 配合
,
的其他性质(结合律、分配律等)可计算更复杂的式子。
注
{0,1}
关于上述两个运算构成二元数域。
(0,1)
-矩阵的布尔运算：
对于
mn
的
(0,1)
矩阵
M
R
(r
ij
)
mn
，
M
S
(s
ij
)
mn
，定义下列运算：
¬MR
(¬r
ij
)
mn
，
M
R
M< br>S
(r
ij
s
ij
)
mn
，
M
R
M
S
(r
ij
s
ij
)
mn
；
对
mn
和
np
的
(0,1)
矩阵
M
R
(r
ij
)
mn
和
M
S
(r
ij
)
np
：
M
R
M
S
((r
ik
s
kj
))
mp
。
k1
n
例4 对全
0
矩阵
0
，全
1
矩阵
J
有
零律：
0
MM
0

0
，
JMMJJ
；
同一律：
0
MM
，
JMM
。
用关系矩阵的布尔运算研究关系的运算：
定理：设
X{x
1
,x
2
,L,x
m
}
，
Y{y
1
,y
2
,L,y
n
}
，
Z{z
1
,z
2< br>,L,z
p
}
，
R
是
X
到
Y
的关系，
M
R
(a
ij
)
mn
是
m n
矩阵，
S
是
Y
到
Z
的关系，
M
S
(b
ij
)
np
是
np
矩
阵，则< br>M
RS
(c
ij
)M
R
M
S
，这里
c
ij
(a
ik
b
kj
)
，
i1,2,L,m
，
j1,2,L,p
。
k1
n
设
R,S
是
X
到
Y
的关系，
M
R
(a
ij
)
，
M
S
(b
ij
)
，
c
ij
是运算后得到新关系的关
系矩阵的元素，则
M
R
I
S
M
R
M
S
，
c
ij
a
ij
b
ij
；
M
R
U
S
M
R
M
S
，
c
ij
a
ij
b
ij
；
M
R
，
c
ij
¬a
ij
；
M
RS
M
R
M
S
，
c
ij
a
ij
¬b
ij
。
定理：关系矩阵的乘法是可结合的。

证明：利用关系合成的可结合律： (M
R
M
S
)M
T
M
RS
 M
T
M
(RS)T
M
R(ST)
M
R
M
ST
M
R
(M
S
M
T)
。
借助关系矩阵及其运算还可导出其他一些结论，如：
R
为
A
上的传递关系
RRRM
R
2
M
R
；
R
为
A
上的自反关系
I
A
RIM
R
。

本节要求：
1. 掌握关系的合成运算、关系的幂运算的概念及性质；
2. 能分别利用关系的不同的表示方法（集合的 表示法、图示法、关系矩阵、关系图）
对关系进行合成和幂运算。
关系的性质
定义1 设
R
是
A
上的一个二元关系，
(1) 若对< br>A
中的每一
x
，
xRx
，则称
R
是自反的；
(2) 若对
A
中的每一
x
，
xRx
，则称R
是反自反的；
(3) 若对每一
x,yA
，
xRy
蕴含着
yRx
，则称
R
是对称的；
(4) 若对每一
x ,yA
，
xRy
，
yRx
蕴含着
xy
，则称< br>R
是反对称的；
(5) 若对每一
x,y,zA
，
xRy
，
yRz
蕴含着
xRz
，则称
R
是传递的。 对于
A
上的任意关系
R
，对应于不同的关系特性的关系图和关系矩阵的性 质（如
下表）：
(1)
R
是自反的
x(xAxRx )
M
R
主对角元全为
1
G
R
每一节点
有自回路；
)
M
R
主对角元全为
0
G
R< br>每一节点(2)
R
是反自反的
x(xAxRx
无自回路
(3)
R
是对称的
xy(xAyAxRyyRx)
M
R
是对称矩阵
G
R
有向边是成对出现的（若有从
a
到
b
的弧，则必有 从
b
到
a
的弧）；

(4)
R
是反对称的
xy(xAyAxRyyRxxy)
< br>ij(i,j{1,2,K,n}(a
ji
1)(a
ij
0))
；
G
R
中若有从
a
到
b
的 弧，则必没有从
b
到
a
的弧；
(5)
R
是传递的
xyz(xAyAzAxRyyRzxRz)

G
R
中若从
a
到
b
有一条路径，则从
a
到
b
有一条弧。

逻
辑
表
达
式
集合
表达式

2
自反性 反自反性 对称性 反对称性 传递性

关系 主对角线 主对角线
若
r
ij
1
，且
ij
，
对
M
中
1
所在位
矩阵是对称矩阵
则
r
ji
0

置，
M
中相应的
位置都是
1

如果顶点
x
i
到
x
j
如果两点之间有
边，一定是一条有
有边，
x
j
到
x
k
有
矩阵
元素全是
1

元素全是
0

如果两个顶点之
关系图
每个顶点
都有环
每个顶点 间有边，一定是
都没有环 一对方向相反的
边(无单边)
向边(无双向边)
边，则从
x
i
到
x
k
也有边
关系的性质和运算之间的联系：
设
R
1
和
R
2< br>是
A
上的关系，它们都具有某些共同的性质。在经过并，交，相对补，
%
，
RR
等是求逆或复合运算以后，所得到的新关系
R
1
UR2
，
R
1
IR
2
，
R
1
R
2
，
R
1
12

否还能保持原来关系的性质呢 ？有关的结论给在下表中，其中的√和×分别表示“能保
持”和“不一定能保持”的含义。







自反性
√
√
√
×
√
反自反性
√
√
√
√
×
对称性
√
√
√
√
×
反对称性
√
√
×
√
×
传递性
√
√
×
×
×