集合与关系节

集合与关系节第三章集合与关系3.4序偶与笛卡尔积3.5关系及其表示3.6关系的性质3.7关系的运算（复合关系和逆关系）3.8关系的闭包运算3.9相容关系与覆盖3.10等价关系与划分3.12偏序关系第2页,共87页，2024年2月25日，星期天2024/5/43-4序偶与笛卡尔积关系理论历史悠久。它与集合论、数理逻辑、组合学、图论和布尔代数都有密切的联系。关系是日常生活以及数学中的一个基本概念，例如：兄弟关系，师生关系、位置关系、大小关系、等于关系、包含关系等。第3页,共87页，2024年2月25日，星期天2024/5/43-4序偶与笛卡尔积另外，关系理论还广泛用于计算机科学技术，如计算机程序的输入、输出关系；数据库的数据特性关系；数据结构本身就是一个关系等。在某种意义下，关系是有联系的一些对象相互之间的各种比较行为。第4页,共87页，2024年2月25日，星期天2024/5/43-4序偶与笛卡尔积

序偶与笛卡尔积上,下；左，右；3<4；中国地处亚洲；平面上点的坐标（x,y）等。特征：成对出现、具有一定的顺序。定义

由两个元素x,y按照一定的次序组成的二元组称为有序偶对(序偶),记作<x,y>,其中x为第一个元素，y为第二个元素。第5页,共87页，2024年2月25日，星期天2024/5/4用序偶表示下列语句中的次序关系(1)平面上点A的横坐标是x,纵坐标是y,其中x,y∈R；(2)成都是四川的省会；(3)英语课本在书桌上；(4)左，右关系。解各语句的序偶表示如下：(1)<x,y>，x,y∈R；(2)<成都，四川>；(3)<英语课本，书桌>；(4)<左、右>。第6页,共87页，2024年2月25日，星期天2024/5/4定义6.2.2给定序偶<a,b>和<c,d>，如果a=c，b=d，则<a,b>=<c,d>。1.序偶可以看作是具有两个元素的集合，2.但是序偶中的两个元素具有确定的次序。即<a,b>≠<b,a>但是{a,b}={b,a}.第7页,共87页，2024年2月25日，星期天2024/5/4N重有序组定义由n个元素a1,a2,a3,…,an按照一定次序组成的n元组称为n重有序组(n-Type)(Vector)，记作:<a1,…,an>例用n重有序组描述下列语句。（1）中国四川成都电子科技大学计算机学院；（2）2006年9月10日18点16分25秒；（3）16减5再加3除以7等于2。解各语句的n重有序组表示如下：（1）<中国,四川,成都,电子科技大学,计算机学院>（2）<2006,9,10,18,16,25>；（3）<16,5,3,7,2>。定义给定n重有序组<a1,a2,...,an>和<b1,b2,…，bn>。如果ai＝bi(i＝1,2,…，n)，则<a1,a2,...,an>=<b1,b2,…，bn>。第8页,共87页，2024年2月25日，星期天2024/5/4笛卡尔乘积定义设A，B是两个集合，称集合：A×B＝{<x,y>|(x∈A)∧(y∈B)}为集合A与B的笛卡尔积DescartesProduct)。注意：（1）集合A与B的笛卡儿积A×B仍然是集合；（2）集合A×B中的元素是序偶，序偶中的第一个元素取自A，第二个元素取自B。第9页,共87页，2024年2月25日，星期天2024/5/4例设A={a},B={b,c},C=Φ,D={1,2}，请分别写出下列笛卡儿积中的元素。（1）A×B,B×A；（2）A×C,C×A；（3）A×(B×D),(A×B)×D。解根据笛卡儿积的定义，有（1）A×B={<a,b>,<a,c>},B×A={<b,a>,<c,a>}；（2）A×C=Φ,C×A=Φ；第10页,共87页，2024年2月25日，星期天2024/5/4解（续）（3）因为B×D={<b,1>,<b,2>,<c,1>,<c,2>}，所以A×(B×D)={<a,<b,1>>,<a,<b,2>>,<a,<c,1>>,<a,<c,2>>}。同理，(A×B)×D={<<a,b>,1>,<<a,b>,2>,<<a,c>,1>,<<a,c>,2>}。第11页,共87页，2024年2月25日，星期天2024/5/4注意由例我们可以看出：（1）笛卡儿积不满足交换律；（2）A×B=Φ当且仅当A=Φ或者B=Φ；（3）笛卡儿积不满足结合律；（4）对有限集A,B，有|A×B|=|B×A|=|A|×|B|。第12页,共87页，2024年2月25日，星期天2024/5/4集合相等

两个集合互相包含等式成立

两个集合相等定理设A,B,C是任意三个集合，则（1）A×(B∪C)=(A×B)∪(A×C)；（2）(B∪C)×A=(B×A)∪(C×A)；（3）A×(B∩C)=(A×B)∩(A×C)；（4）(B∩C)×A=(B×A)∩(C×A)。分析显然，待证等式两端都是集合第13页,共87页，2024年2月25日，星期天2024/5/4定理分析对（1）A×(B∪C)=(A×B)∪(A×C)

A×(B∪C)

(A×B)∪(A×C),(A×B)∪(A×C)

A×(B∪C)利用按定义证明方法，首先叙述包含关系的定义，即首先叙述A×(B∪C)

(A×B)∪(A×C)的定义：对任意<x,y>∈A×(B∪C)，…，有<x,y>∈(A×B)∪(A×C)，则A×(B∪C)

(A×B)∪(A×C)。同理可分析(A×B)∪(A×C)

A×(B∪C)。第14页,共87页，2024年2月25日，星期天2024/5/4定理证明（1）对任意<x,y>∈A×(B∪C)，由笛卡儿积的定义知，x∈A且y∈B∪C；由并运算定义知，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)。第15页,共87页，2024年2月25日，星期天2024/5/4定理证明（续）另一方面，对任意<x,y>∈(A×B)∪(A×C)，由并运算定义知,<x,y>∈A×B或者<x,y>∈A×C。由笛卡儿积的定义知,x∈A且y∈B或x∈A且y∈C。进一步有x∈A且y∈B∪C，从而<x,y>∈A×(B∪C)。所以(A×B)∪(A×C)

A×(B∪C)。于是，根据定理1.2.2，有A×(B∪C)=(A×B)∪(A×C)。(2)、(3)和(4)的证明作为练习，自证。第16页,共87页，2024年2月25日，星期天2024/5/4定理设A,B,C,D是任意四个集合，则(A×B)

(C×D)

A

C，B

D。证明充分性(

)：对任意<x,y>∈A×B，有x∈A且y∈B。又因为A

C，B

D，所以有x∈C且y∈D，即<x,y>∈C×D，从而(A×B)

(C×D)。第17页,共87页，2024年2月25日，星期天2024/5/4定理证明（续）必要性(

)：对任意的x∈A，y∈B，有<x,y>∈A×B。又因为(A×B)

(C×D)，所以<x,y>∈C×D。根据笛卡儿积的定义有x∈C且y∈D，从而A

C，B

D。综上所述，定理成立。第18页,共87页，2024年2月25日，星期天定理：若C，则AB(ACBC)(CACB)第19页,共87页，2024年2月25日，星期天2024/5/4定义设A1,A2,…,An是n个集合，称集合A1×A2×…×An

={<a1,a2,…,an>|(ai∈Ai)∧i∈{1,2,3,…,n}}为集合A1,A2,…,An的笛卡儿积(DescartesProduct)当A1=A2=…=An=A时，有A1×A2×…×An=An。第20页,共87页，2024年2月25日，星期天2024/5/4当集合A1,A2,…,An都是有限集时，|A1×A2×…×An|=|A1|×|A2|×…×|An|。第21页,共87页，2024年2月25日，星期天日常生活中，大家熟知一些常见关系,例：家庭集合，有父子关系、兄弟关系等。全校同学作为一个集合，有同班关系，同组关系。把任一序偶的集合确定了一个二元关系R,R中任一序偶<a,b>可记作<a,b>

R或aRb,不在R中的序偶<x,y>可记作<x,y>

R例：一组同学为集合A，A有4名同学，其中1，2同寝室，3，4同寝室。则：R={<1，1>，<1，2>，<2，1>，<2，2>，<3，3>，<3，4>，<4，3>，<4，4>}反映了同寝室关系，

3-5关系及其表示第22页,共87页，2024年2月25日，星期天

关系及其表示

定义

设A，B是任意两个集合，A×B的子集R称为从A到B的二元关系，当A=B时，称R为A上的二元关系。从上述定义可以看出A到B的二元关系，也是序偶的集合。若<a,b>∈R，则称a与b有关系R，记作aR

b。若，则称a与b没有关系R，记作。例如：设A={a,b,c,d},B={0,1}，则R={﹤a,0﹥,﹤b,0﹥,﹤c,1﹥}就是一个从A到B的二元关系。。第23页,共87页，2024年2月25日，星期天①：A×B的子集叫做A到B上的一个二元关系。

②：A1×A2×A3的子集叫做A1×A2×A3上的一个二元关系。

③:A1×A2×…An的子集叫做A1×A2×…An上的一个n元关系。

④:A×A×A×…A的子集叫做A上的n元关系。关系及其表示

第24页,共87页，2024年2月25日，星期天

关系及其表示

定义设A，B是两个集合，R是从A到B上的二元关系，则(1)若存在b∈B，使得<a,b>∈R，则所有这样的a∈A组成的集合，称为二元关系R的定义域。记作dom(R)或D(R)，即

(2)若存在a∈A，使得<a,b>∈R，则所有这样的b∈B组成的集合，称为二元关系R的值域。记作ran(R)或R(R)，即

R的定义域和值域一起称作R的域，记作FLDR，即FLDR=dom(R)∪ran(R)从X到Y的二元关系R，也可以用图解的方式表示，X和Y是两个集合。xi是集合X中的元素，yj是集合Y中的元素，当且仅当xiRyj时，才有一条从xi指向yj的有向边。第25页,共87页，2024年2月25日，星期天

关系及其表示图4.1.1图解表示法第26页,共87页，2024年2月25日，星期天例

设R1={<x，y>|（x，y

Z）∧(x≥y)} R2={<x，y>|（x，y

Z）∧(y=2x+1)} R3={<x，y>|（x，y

Z）∧(|x|=|y|=5)}都是定义在整数集Z上的关系，求他们的定义域，值域和域。解：

domR1=Z，ranR1=Z， fldR1=Z；

domR2=Z，ranR2={2y+1|y∈Z}，fldR2=Z；

domR3={5，-5}，ranR3={5，-5}，fldR3={5，-5}。例

设R={<1，2>，<1，3>，<2，4>，<4，3>}，则解：

domR={1，2，4}ranR={2，3，4}fldR={1，2，3，4}第27页,共87页，2024年2月25日，星期天定义

设R是A×A

×…×A的子集，若R=

,则称R为A的空关系。若R=A×A×…×A,则称R为A的全域关系。

R={<x,x>|x

A}称为A上恒等关系，记为IA

关系及其表示----几个特殊关系第28页,共87页，2024年2月25日，星期天

关系及其表示

定理若R和S是从集合A到B上的两个二元关系，则R和S的并、交、补、差也是A到B上的二元关系。证明：因为R和S是从集合A到B上的二元关系所以有R⊆A×B，S⊆A×B。从而有

即A∩B和A∪B都是A到B上的二元关系。又因为

所以~R和~S也是A到B上的二元关系。由于

故R-S也是A到B上的二元关系。第29页,共87页，2024年2月25日，星期天

关系的矩阵表示设X={a,b,c},Y={0,1,2,3}，R={<a,1>,

<b,2>,<c,0>}。可得关系R的矩阵表示如下：

由上例看出，给定从有限集X到Y的二元关系R，就可以构造出它的关系矩阵。给定两个有限集合和，并且R是从X到Y的二元关系。如果有

则称矩阵是R的关系矩阵，并记作。

第30页,共87页，2024年2月25日，星期天例

设X={x1，x2，x3，x4}，Y={y1，y2，y3}。X到Y的关系R为R={<x1，y1>，<x1，y3>，<x2，y3>，<x4，y2>}。则R的关系矩阵是例

设A={1，2，3，4}，A上的大于关系“＞”定义为={<2，1>，<3，1>，<3，2>，<4，1>，<4，2>，<4，3>}。则关系＞的关系矩阵是集合A中元素的排序是1，2，3，4，即1对应第1行、第1列，例如<2，1>就是第2行与第1列相交处的点，依此类推。第31页,共87页，2024年2月25日，星期天关系及其表示--关系的图形表示设画出R的关系图。解：R的关系图如图所示。

R的关系图

第32页,共87页，2024年2月25日，星期天3-6关系的性质定义3.6.1设R是集合A上的二元关系。若对任意一个a∈A，都有aRa，即<a,a>∈R

，则称R是自反的。即R是自反的。也就是说，在自反关系中，每个元素都和自己有关系。例如，设R是整数集上的≥关系，则R是自反的。因为对于任意一个整数a，都有a≥a成立。

定义3.6.2

设R是集合A上的二元关系。若对任意一个a∈A,都有，即，则称R是反自反的。即R是反自反的。也就是说，在反自反关系中，每个元素都和自己没有关系。例如，设R是整数集上的<关系，则R是反自反的。因为对于任意整数a，都有a<a

不成立。一个关系不是自反的，不一定就是反自反的。同样，一个关系不是反自反的，也不一定就是自反的。例如：在集合上定义的二元关系既不是自反的也不是反自反的。第33页,共87页，2024年2月25日，星期天3-6关系的性质定义3.6.3设R是集合A上的二元关系。若对任意的a,b∈A，当<a,b>∈R时，就有<b,a>∈R，则称R是对称的。即

R是对称的

例如，平面上各三角形集合中，三角形的相似关系是对称的。

定义3.6.4

设R是集合A上的二元关系。若对任意的a,b∈A，当<a,b>∈R且<b,a>∈R时，有a=b，则称R是反对称的。即

R是反对称的上述定义也可表述为：对任意的a,b∈A，若<a,b>∈R且a≠

b，则。例如，在A的幂集中各元素之间的⊆关系是反对称的。实数集合上的≤关系也都是反对称的。值得注意的是，存在既是对称的又是反对称的二元关系。如，恒等关系就是对称关系，同时也是反对称关系。又如，R既是对称的，也是反对称的。也有既不是对称的，又不是反对称的关系存在！！

第34页,共87页，2024年2月25日，星期天3-6关系的性质

定义3.6.5设R是集合A上的二元关系。若对任意的a,b,c∈A，当<a,b>∈R且<b,c>∈R时，就有<a,c>∈R，则称R是传递的。即

R是传递的在判定关系的传递性时，要对所有的有序对都检查之后，才能判断一个关系的传递性是否成立，因此，判断传递性是比较复杂的。例如，设，则关系R满足传递性。例

在所有人集合P上的关系，说明R的性质。解：R是自反的，因为每个人和自己有同一祖先；R是对称的，因为如果甲和乙有同一祖先，那么乙和甲也有同一祖先；R是传递的，因为若甲和乙有同一祖先，乙和丙有同一祖先，那么甲和丙也有同一祖先。第35页,共87页，2024年2月25日，星期天3-6关系的性质

判别关系的性质，也可以从关系矩阵和关系图上给予验证。（1）若关系是自反的，当且仅当在关系矩阵中，对角线上的所有元素都是1；在关系图上，每个节点都有一条自己到自己的边（或称圈）。（2）若关系是反自反的，当且仅当关系矩阵中对角线上的元素都为零；在关系图中，每个节点都没有自己到自己的边。（3）若关系是对称的，当且仅当其关系矩阵是对称的；在关系图上，任意两个节点间若有弧，必定是成对出现的。（4）若关系是反对称的，当且仅当关系矩阵以主对角线为对称的元素不能同时为1，且在关系图上两个不同节点间的弧不能成对出现。第36页,共87页，2024年2月25日，星期天任何集合上的相等关系实数集合上的小于等于关系非空集合上的空关系基数大于1的集合上的全域关系xRy

(x-y)/2是整数自反性反自反性对称性反对称性传递性Y

N

Y

Y

Y

Y

N

N

N

Y

NYYY

YYNYNYYNYNY举例第37页,共87页，2024年2月25日，星期天3-7关系的运算(复合关系和逆关系)

定义4.3.1

设R是从集合X到集合Y的二元关系，如果将R中每一对序偶的元素顺序互换，所得到的新的集合则称为R的逆关系，记作，即

由逆关系的定义可知，的关系图可以通过将R的关系图的所有有向弧逆转得到，它的关系矩阵可以通过将R的关系矩阵转置得到。例4.3.1设，求。解：。第38页,共87页，2024年2月25日，星期天3-7关系的运算(复合关系和逆关系)

定理

设R和S都是从X到Y的二元关系，则下列各式成立。（1）（2）（3）（4），这里~R表示（5）（6）若，则第39页,共87页，2024年2月25日，星期天3-7关系的运算(复合关系和逆关系)

定理

设R是A上的二元关系，则（1）R在A上是自反的，当且仅当。（2）R在A上是反自反的，当且仅当。（3）R在A上是对称的，当且仅当。（4）R在A上是反对称的，当且仅当。第40页,共87页，2024年2月25日，星期天3-7

关系的运算(复合关系和逆关系)

定义

设R是从集合X到集合Y的二元关系，S是从集合Y到Z的关系，则R◦

S称为R和S的合成关系，定义为

R▫

S称为关系的合成运算。设R是从集合到集合的关系，S是从集合到集合的关系，则是一个的矩阵，是一个的矩阵。依照普通矩阵乘法的运算，可以定义两个关系矩阵的合成运算。第41页,共87页，2024年2月25日，星期天3-7关系的运算(复合关系和逆关系)由上述前两个矩阵可以构造这两个矩阵的合成矩阵，记作。元素可由下式得到：其中。∨和∧的运算规则如下：

两个关系的合成运算，就是将布尔关系矩阵做乘法，所得结果即为合成关系矩阵。

第42页,共87页，2024年2月25日，星期天3-7关系的运算(复合关系和逆关系)定理设X,Y,Z和W都是集合。R是从集合X到Y的关系，S是从集合Y到Z的关系，T是从集合Z到W的关系。于是有(R◦

S)◦

T=R◦(S

◦

T)即关系的合成运算满足结合律。证明：对任意的<x,w>∈(R◦

S)◦

T，根据合成关系的定义可知，必然存在z∈Z，使得<x,z>∈(R◦

S)，<z,w>∈T。又因为<x,z>∈(R◦

S)，故必存在y∈Y，使得<x,y>∈R并且<y,z>∈S。由<y,z>∈S且<z,w>∈T，根据合成关系的定义知<y,w>∈(S

◦

T)，又因为<x,y>∈R且<y,w>∈S

◦

T，得到<x,w>∈R◦(S

◦

T)。故由<x,w>的任意性可知(R◦

S)◦

T⊆

R◦(S

◦

T)。同理可证R◦(S◦

T)⊆(R◦

S)◦

T。综上所述，得到(R◦

S)◦

T=R◦(S

◦

T)，即关系的合成运算满足结合律。

一般来说，关系的合成运算是不满足交换律的，即R◦

S

≠S

◦

R。

第43页,共87页，2024年2月25日，星期天3-7关系的运算(复合关系和逆关系)定义设R是集合X中的二元关系，n∈N（N是自然数集），于是R的n次幂定义为：（1），即是R中的恒等关系。（2）。定理设R是集合X中的二元关系。设m,n∈N。则有（1）（2）第44页,共87页，2024年2月25日，星期天3-7关系的运算(复合关系和逆关系)定理：设T为A到B的关系，S为B到C的关系，

证明：第45页,共87页，2024年2月25日，星期天3-7关系的运算(复合关系和逆关系)定理设A为含有n个元素的集合，R是A上的二元关系，则必存在s和t，使得

定理设R是A上的二元关系，则R在A上是传递的，当且仅当

第46页,共87页，2024年2月25日，星期天

例题设R是A上的一个二元关系，（1）如果R是自反的，则Rc一定是自反的吗？（2）如果R是对称的，则Rc一定是对称的吗？（3）如果R是传递的，则Rc一定是传递的吗？(4)如果R是反自反的，则Rc一定是反自反的吗？(5)如果R是反对称的，则Rc一定是反对称的吗？第47页,共87页，2024年2月25日，星期天3.8

关系的闭包运算

定义3.8.1设R是集合A上的二元关系。如果有另一A上的关系R’

满足：（1）R’是自反的；（2）R’

⊇R；（3）对A上的任意自反关系R’’，若R’’⊇R，则R’’⊇R’。那么称R’是R的自反闭包，并记作r(R)。定义3.8.2设R是集合A上的二元关系。如果有另一A上的关系R’满足：（1）R’是对称的；（2）R’

⊇R；（3）对A上的任意对称关系R’’，若R’’⊇R，则R’’⊇R’。那么称R’是R的对称闭包，并记作s(R)。定义3.8.3设R是集合A上的二元关系。如果有另一A上的关系R’满足：（1）R’是传递的；（2）R’

⊇R；（3）对A上的任意对称关系R’’，若R’’⊇R，则R’’⊇R’。那么称R’是R的传递闭包，并记作t(R)(也记作R+)。

第48页,共87页，2024年2月25日，星期天3.8

关系的闭包运算

定理3.8.1设R是集合A上的二元关系，则：(1)

自反闭包

(2)

对称闭包

（3）传递闭包特别地，若则

例3.8.1设X={1,2,3}，R是X中的二元关系，R={<1,2>,<2,3>,<3,1>}。求r(R)、s(R)和t(R)

第49页,共87页，2024年2月25日，星期天3.8

关系的闭包运算求关系R的传递闭包t(R)(也就是R+)的Warshall算法：(1)置新矩阵A:=MR(2)置i:=1(3)对所有j如果A[j,i]=1,则对k=1,2,…,nA[j,k]:=A[j,k]+A[i,k](4)i:=i+1(5)如果i≤n，则转到步骤(3),否则停止。第50页,共87页，2024年2月25日，星期天3.8

关系的闭包运算定理3.8.2设R是集合A上的二元关系，则（1）R是自反的，当且仅当r(R)=R；（2）R是对称的，当且仅当s(R)=R；（3）R是传递的，当且仅当t(R)=R。定理3.8.3设R是集合A上的二元关系，则（1）若R是自反的，则s(R)和t(R)也是自反的。（2）若R是对称的，则r(R)和t(R)也是对称的。（3）若R是传递的，则r(R)也是传递的。第51页,共87页，2024年2月25日，星期天3.8

关系的闭包运算定理3.8.4设R1和R2是集合A上的二元关系，且，则（1）（2）（3）二元关系的闭包仍然是二元关系，还可以求它的闭包。例如，R是A上的二元关系，r(R)是它的自反闭包，还可以求r(R)的对称闭包。r(R)的对称闭包记为s(r(R))，简记为sr(R)，读作R的自反闭包的对称闭包。其余类似。定理3.8.5设R是集合A上的二元关系，则（1）（2）（3）第52页,共87页，2024年2月25日，星期天3-9集合的划分和覆盖定义3-9.1设A为非空集合，S={S1,S2,…,Sm},其中SiA，Si≠，i=1,2,…m且则集合S称为集合A的覆盖。如果除了以上条件外，还满足Si

Sj=

(i≠j)，则集合S称为集合A的划分。第53页,共87页，2024年2月25日，星期天3-9集合的划分和覆盖

定义3-9.2若{A1,A2,…,Ar}和{B1,B2,…,Bs}都是集合A的划分，则其中所有Ai

Bj≠

组成的集合，称为是原来两种划分的交叉划分。定理3-9.1若{A1,A2,…,Ar}和{B1,B2,…,Bs}都是集合A的划分，则其交叉划分也是原集合A的一种划分。第54页,共87页，2024年2月25日，星期天3-9集合的划分和覆盖定义3-9.3给定集合A的任意两个划分{A1,A2,…,Ar}和{B1,B2,…,Bs}，若对于每一个Aj均有Bk使Aj

Bk,则划分{A1,A2,…,Ar}称为划分{B1,B2,…,Bs}的加细。定理3-9.2任何两种划分的交叉划分，都是原来各划分的一种加细。第55页,共87页，2024年2月25日，星期天3-9集合的划分和覆盖--例题例题1设{A1,A2,…,Am}是集合A的一个划分，我们定义A上的二元关系R,使<a,b>∈R当且仅当a和b在这个划分的同一块中，证明：R是自反的、对称的、传递的。例题2设{A1,A2,…,An}是集合A的划分,若A

B≠

，1≤i≤n,试证明{A1

B,A2

B,…,Ar

B}是集合A

B的划分。第56页,共87页，2024年2月25日，星期天3.10等价关系与等价类

定义3.10.1设R是定义在集合A上的二元关系，若R是自反的、对称的和传递的，则称R是等价关系。显然，若关系R是等价关系，则也必然是相容关系。反之，则不一定成立。例设，在集合A上定义关系R如下证明R是等价关系并画出其关系图。解：由R的定义可知，

R的关系图为：第57页,共87页，2024年2月25日，星期天3.10等价关系与等价类

下面来证明R是等价关系：（1）对于任意的，因为a-a可被3整除，故，因此R是自反的。（2）对于任意的，若，则a-b可被3整除，又因为b-a=-(a-b)，故b-a也可被3整除。即，因此R是对称的。（3）对于任意的，若，，则a-b和b-c均可被3整除，又因为a-c=(a-b)+(b-c)，故a-c也可被3整除。即，因此R是传递的。综上所述，知R是等价关系。第58页,共87页，2024年2月25日，星期天3.10等价关系与等价类定义3.10.2设R是集合A上的等价关系，对于任一，集合称为元素a形成的等价类。定理4.6.1设R是集合A上的等价关系，则有（1），是A的非空子集。（2），如果，则。（3），如果，则。（4）。（5）aRb当且仅当[a]R=[b]R定义4.6.3设R是非空集合A上的等价关系。由A中各元素生成的关于R的等价类的集合，称为A关于R的商集，记作。例如，例1中的集合A关于R的商集为

第59页,共87页，2024年2月25日，星期天练习题设集合A={1,2,3,4,5,6,7},说明A上的下列二元关系哪些是等价关系并求其等价类,如果不是说明原因。(1)R={<1,2>,<2,1>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<7,7>}(2)S={<1,1>,<2,2>,<3,3>,<4,5>,<5,4>,<6,7>,<7,6>,<4,4>,<5,5>,<6,6>,<7,7>}(3)T={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<7,7>,<1,2>,<3,4>,<5,6>,<6,7>}第60页,共87页，2024年2月25日，星期天3.10等价关系与等价类给定非空集合A，若有集合，其中，，且，同时有则称S是A的划分。定理3.10.2设R是非空集合A上的等价关系，则A关于R的商集A/R是集合A上的一种划分。

定理3.10.2给出了根据集合的等价关系求出其相应划分的方法。

定理3.10.3设S是非空集合A中的一种划分。,

在集合A上定义关系R如下：

则R是集合A中的等价关系。定理3.10.3给出了由集合的划分求等价关系的方法。第61页,共87页，2024年2月25日，星期天3.10等价关系与等价类注1：集合A上的等价关系R，决定了A的一个划分，该划分就是商集A/R注2：集合A的一个划分确定了A的元素之间的一个等价关系。定理：设R1和R2是非空集合A上的等价关系，则R1=R2当且仅当A/R1=A/R2其中A/R1={[a]R1|a∈A},A/R2={[a]R2|a∈A}第62页,共87页，2024年2月25日，星期天练习题一、已知集合A={1,2,3,4,5,6}上的划分S={{1,2},{3,4,5},{6}},求由此划分所确定的A上的等价关系。二、已知集合A={1,2,3,4,5,6}上的等价关系R={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>,<4,4>,<4,5>,<5,4>,<5,5>,<6,6>},求由此等价关系所确定的A上的划分。第63页,共87页，2024年2月25日，星期天3-11

相容关系定义3.11.1设R是集合A上的二元关系，若R是自反的和对称的，则称R是相容关系。例设A={cat,teacher,cold,desk,knife,by},在A上定义关系R如下

试画出R的关系图和关系矩阵，并说明R是相容关系。解：令则

的关系图如下面图4.5.1所示第64页,共87页，2024年2月25日，星期天3-11

相容关系

图4.5.1关系矩阵

从关系图和关系矩阵中可以看出，关系R是相容关系。因为在关系图中，每个节点都有环且任意两个节点之间如有连线，必有双向线；在关系矩阵中，其对角线上各元素均为1，且关系矩阵以对角线为轴对称。约定：相容关系的关系图上，不画出每个元素的环、每对双向线，只画出无向连线。相容关系的关系矩阵中，只画出主对角线以下的下三角矩阵。第65页,共87页，2024年2月25日，星期天3-11

相容关系

图4.5.2关系图图4.5.3关系矩阵第66页,共87页，2024年2月25日，星期天3.11相容关系

给定非空集合A，设有集合，其中，且，，且，则称集合S为集合A的覆盖。由覆盖可以构造相容关系。例如，设，，，则S和T均是A的覆盖，且两者不同。定理3.11.1给定集合A上的一个覆盖，由它确定的关系是相容关系。

从这个定理可以看出，给定集合A上的任一覆盖，就可以构造出与此覆盖相对应的一个相容关系。但是，请注意：

不同的覆盖可以构造出相同的相容关系。第67页,共87页，2024年2月25日，星期天相容类：设r是集合A上的相容关系，若C

A，如果对于C中任意两个元素a1,a2有a1ra2，称C是由相容关系r产生的相容类。第68页,共87页，2024年2月25日，星期天3-11

相容关系定义3.11.3设R是集合A中的相容关系，若有，使得对于任意的，必有，并且在中，没有任何一个元素与中的所有元素都有R关系，则称是由R产生的最大相容类。例如，例4.5.1中的相容关系有以下4个最大相容类：

由R所产生的所有最大相容类所构成的集合，称为集合A的完全覆盖。根据任意一个给定的集合A的相容关系R，求它的完全覆盖有两种常用的方法。第69页,共87页，2024年2月25日，星期天

在相容关系图中，最大完全多边形的顶点集合，就是最大相容类。所谓完全多边形，就是其每个顶点都与其它顶点连接的多边形。例如一个三角形是完全多边形，一个四边形加上两条对角线就是完全多边形。第70页,共87页，2024年2月25日，星期天求最大相容关系的关系图法例3.11.2设集合上的相容关系的简化关系图如图4.5.4所示，求出其完全覆盖。图4.5.4解：从图中可以看出，它的最大相容类为，则其完全覆盖为。第71页,共87页，2024年2月25日，星期天3-12偏序关系

定义3.12.1设R是集合A上的二元关系，若关系R满足自反性、反对称性和传递性，则称R是集合A上的一个偏序关系，并记作“≤”。集合A和集合A上的偏序关系“≤”所构成的序偶<A，≤>称作偏序集。例3.12.1在实数集P上，证明大于等于关系“≥”是偏序关系。证明：（1）对于任意的实数x，都有x≥x，故“≥”在实数集上是自反的。（2）对于任意的实数x和y，若有x≥y且y≥x，则必有x=y，故“≥”在实数集上是反对称的。（3）对于任意的实数x、y和z，若有x≥y，y≥z，则必有x≥z。故“≥”在实数集上是传递的。综上所述，“≥”是实数集上的偏序关系。<P，≥>是一个偏序集。第72页,共87页，2024年2月25日，星期天3-12偏序关系由于偏序关系满足自反性、反对称性和传递性，其关系图中的各元素就会呈现出一定的层次关系。因此，为了突出偏序关系中各元素的层次性，我们按如下规定对偏序关系的关系图进行化简，从而得到一种简明的关系图。（1）省略关系图中表示自反性的自己到自己的边（2）省略关系图中，可以通过传递关系表示出来的边。按上述约定化简了的关系图称为哈斯图（Hasse）下面给出其相关定义及画法。

第73页,共87页，2024年2月25日，星期天3.12偏序关系定义3.12.2在偏序集<A，≤>中，如果有x,y∈A，x≤y且，并且不存在其他元素，使得x≤z，z≤y，则称元素y盖住元素x。COVA={<x,y>|x,y∈A;y盖住x}画法：在哈斯图中，若有元素y盖住元素x，则将代表y的圆圈画在代表x的圆圈的上方。并且在y和x之间用直线相连。例3.12.2设集合，R是集合A上的整除关系。试画出<A，≤>的哈斯图。解：<A，≤>的哈斯图如下图所示。第74页,共87页，2024年2月25日，星期天3-12偏序关系定义3.12.3设R是集合A上的二元关系，若R关系满足反自反性和传递性，则称R是A上的拟序关系，并把

<

A，R

>称为拟序集，记作<

A，<

>。由拟序关系的定义可知，若R是拟序关系，则R必是反对称的。。在实数集上的小于关系“＜”和大于关系“＞”，集合A的幂集上的真包含关系“”等都是拟序关系。通过比较拟序关系和偏序关系，可以发现：拟序关系和偏序关系都是反对称的、可传递的。但前者是反自反的，后者是自反的。第75页,共87页，2024年2月25日，星期天链：设<A,≤>为偏序集，在A的一个子集中，如果每两个元素都有关系，则称这个子集为链。反链