离散数学第4章

第4章关系14-1.关系及其运算关系的基本概念“关系”是一个很基本的概念,为了用数学的方法来研究和讨论各种关系,下面从集合论的观点来描述关系.例:设A={a,b,c,d,e,f},a,b,c,d,e,f分别表示６个男人,其中a是b和c的父亲,b是d的父亲,c是e和f的父亲.则这6个人中所有符合父子关系的两个人可分别用有序偶(a,b),(a,c),(b,d),(c,e),(c,f)来表示，则集合Ｒ＝｛(a,b),(a,c),(b,d),(c,e),(c,f)｝可完整地描述出集合Ａ中元素的父子关系．称R为集合上的一个关系(父子关系).例:Ａ＝｛１，２，３｝上的小于关系可表示为Ｒ＝｛(1,2),(1,3),(2,3)}2两个集合之间的关系设A={a,b,c,d},B={m,p,e},A中的元素a,b,c,d分别表示4位中学教师,B中的元素m,p,e分别表示数学课程、物理课程和英语课程。如果a和b是数学教师，c是物理教师，d是英语教师。则有序偶:(a,m),(b,m)(c,p),(d,e)表示了这4位教师和他们所讲授课程的关系。由这些有序偶作为元素构成的集合R={（a,m),(b,m)(c,p),(d,e)}

称为A到B的二元关系。二元关系的实质是什么？3关系的实质由于二元关系就是符合某种特定要求的有序偶的集合.因此A到B的二元关系应是笛卡儿乘积A×B的子集A上的二元关系应是A上的笛卡儿乘积A×A的子集。为了便于对二元关系进行一般性的讨论，下面把二元关系的概念抽象化，即抽象地把二元关系看做是笛卡儿乘积的子集。4二元关系的定义定义设A,B是集合，R是笛卡儿乘积A×B的子集，则称R为A到B的一个二元关系。例如:设A={a,b,c,d},B={x,y,z},令R={(a,y),(b,x),(b,y),(d,x)}由于R是A×B的子集，所以R是A到B的一个二元关系。类似,可定义n元关系.5n元关系的定义定义6二元关系的定义

对于二元关系R,如果

(a,b)∈R，也可记作aRb，并称a与b有关系R。如果(a,b)

R，也可记作aRb，并称a与b没有关系R。定义

设A是集合，R是A上的笛卡儿乘积A×A的子集，则称R为A上的一个二元关系。例如:设A={1，2，3，4，5},R={（1，1）,（2，5）,（3，1）,（4,3）,(4,5)}，由于R是A×A的子集，所以R为A上的一个二元关系。7二元关系的定义域和值域定义

设S是A到B的二元关系，使(x,y)∈S的所有x组成的集合称为S的定义域，记作D(S)；使(x,y)∈S的所有y组成的集合称为S的值域，记作C(S)或R(S)。易知:D(S)就是S的所有有序偶的第一个元素构成的集合,C(S)就是S的所有有序偶的第二个元素构成的集合.8求关系的定义域和值域例如:设

则R的定义域D(R)，值域C(R)9例1例1:设A={2，4，6，8}，R是A上的小于关系，即当a,b∈A且a<b时，（a,b）∈R，求R及D(R),C(R)

解:R={（2，4）,（2，6）,（2，8）,（4，6）,（4，8）,（6，8）}.

R的定义域D(R)={2，4，6}，

R的值域C(R)={4，6，8}。10例2例2:设A={2，3，4，6，12}，R是A上的整除关系，即当a,b∈A且a能整除b时，（a,b）∈R，求R及D(R),C(R)

解:A上有整除关系为R={（2，2）,（2，4）,（2，6）,（2，12）,（3，3）,（3，6）,（3，12）,（4，4）,（4，12）,（6，6）,（6，12）,（12，12）}，

R的定义域D(R)={2，3，4，6，12}，

R的值域C(R)={2，3，4，6，12}。11例3例3

设A={a,b}，B={x，y}，写出所有A到B的二元关系。

，

12例3例3

设A={a,b}，B={x，y}，写出所有A到B的二元关系。

解:由于，所以，由此可知，A×B共有子集数为

=16，即共有16种A到B的二元关系：，

13例3的说明此例说明，当时，A到B共可定义种不同的二元关系。问:在一个有n个元素的集合A上，可以有多少种不同的二元关系？答：共有种．14三种特殊的关系对于任意集合，空集和集合本身都是它的子集，常称这两种子集为平凡子集。定义笛卡儿乘积A×B的两个平凡子集，空集和A×B本身称为集合A到B的空关系和全域关系。定义设R是A上的二元关系且满足则称R为A上的恒等关系，并记作。15例子例4:设集合A={1，2，3}，R是A上的二元关系，当a,b∈A且a×b>0时，（a,b）∈R。则R={（1，1）,（1，2）,（1，3）,（2，2）,（2，1）,（2，3）,（3，1）,（3，2）,（3，3）}

所以R是A上的全域关系。若令当a,b∈A且a×b<0时，（a,b）∈R，则R=即R是A上的空关系。例5:设A={a,b,c,d},则A上的恒等关系={(a,a),(b,b),(c,c),(d,d)}。练习162关系的表示方法1.关系矩阵

设集合，R是A到B的二元关系，令则称为R的关系矩阵.17关系的表示方法例1:设

R是A到B的二元关系，且则R的关系矩阵为

A是行，B是列18关系的表示方法设,R为A上的二元关系,令则n阶方阵称为R的关系矩阵19关系的表示方法例2

设A={1,2,3,4,5},R是A上的小于等于关系,即当a≤b时,(a,b)∈R。求R的关系矩阵。解:易知A上的小于等于关系为R={（1,1),(1,2),(1,3),(1,4),(1,5),(2,2),(2,3),(2,4),(2,5),(3,3),(3,4),(3,5),(4,4),(4,5),(5,5)}其关系矩阵为20关系的表示方法2.关系图设集合，R是A到B的二元关系。R的图形表示是在平面上用n个点分别表示A中的元素；再在平面上画出m个点分别表示B中元素；当

时，从点至画一条有向边，其箭头指向，否则就不画边。例3:R是A到B的二元关系，且则R的关系图为？

a2a1a3a4a5b1b2b3b421关系的表示方法当R是A上的二元关系时，经常采用如下的图形表示方法：在平面上仅仅画n个点分别表示A中的元素，当时，从点

至画一条有向边，箭头指向

。例如，，R是A上的二元关系，且则R的关系图为

22小结二元关系的表示方法（它们可唯一相互确定）集合表达式关系矩阵（用矩阵表示关系，便于在计算机中对关系进行存储和计算，并可充分利用矩阵的结论）关系图（关系图直观清晰，是分析关系性质的方便形式，但它不便于进行运算）练习233.关系的运算关系的交、并、差、对称差、补设R和S是集合A上的两个二元关系,则

R∩S,R∪S,R-S,R+S,～R

仍是A上的二元关系.24关系的运算例：X={a,b,c}，Y={1，2}，关系R={(a,1),(b,2),(c,1)}S={(a,1),(b,1),(c,1)}则：R∪S={(a,1),(b,1),(b,2),(c,1)}R∩S={(a,1),(c,1)}E={(a,1),(a,2),(b,1),(b,2),(c,1),(c,2),}R=E-R={(a,2),(b,1),(c,2)}练习25

复合关系1.复合关系的定义定义

R是A到B的二元关系，S是B到C的二元关系，R和S的复合记作RοS，它是A到C的二元关系，仅当

(a,b)∈R，且(b,c)∈S时，(a,c)∈RοS。例:设，R是A到B的二元关系，S是B到C的二元关系，且

则R和S的复合

26用关系图法求复合关系

RSABCa1b1c1

a2b2c2

a3b3c3b427用关系图法求复合关系由R和S的关系图得，复合关系

RSAAAa1

a1

a1a2

a2

a2a3

a3

a3a4

a4

a4a5

a5

a528复合关系的矩阵表示定理

R是A到B的二元关系，其关系矩阵为，S是B到C的二元关系，其关系矩阵为，复合关系RοS是A到C的二元关系，其关系矩阵为，则

注意:按普通矩阵乘法求,只不过是将乘法改为布尔乘,加法改为布尔加.29例1设A={1，2，3}，B={a,b,c,d},C={x,y,z}，R是A到B的二元关系，R={(1,a),(1,b),(2,b),(3,c)}，S是B到C的二元关系，S={(a,x),(b,x),(b,y),(b,z)}。求复合关系RοS的关系矩阵.解:因为所以30例2设A={1，2，3，4}，R和S都是A上的二元关系，R={（1，1），（1，2），（2，3），（2，4），（3，2），（4，3），（4，4）}，S={（1，2），（1，3），（2，3），（2，4），（3，3），（4，3）},求复合关系RοS的关系矩阵。

解:

RοS={(1,2),(1,3),(1,4),(2,3),(3,3).(3,4),(4,3)}练习31二元关系的幂二元关系的复合可产生一个新的二元关系，因此二元关系的复合也是二元关系的一种运算。由于二元关系与其关系矩阵一一对应，复合关系RοS的关系矩阵等于R的关系矩阵与S的关系矩阵的乘积，而矩阵的乘法是满足结合律的，所以关系的复合也满足结合律，即

(RοS)οT=Rο(SοT)二元关系的幂由于二元关系的复合满足结合律,所以二元关系的幂是有意义的.32逆关系定义

设R是A到B的二元关系，如果把R中的每一个有序偶中的元素顺序互换，所得的B到A的二元关系称为R的逆关系，记作例1:设A={x,y,z},B={a,b}，R是A到B的二元关系，且有

R={(x,a),(y,b),(z,a)}

则R的逆关系是B到A的二元关系，且有

33逆关系例2:设A={1,2,3,4},R是A上的二元关系,且有

R={(1,2),(2,3),(3,4)}

则其逆关系

由逆关系的定义可知如果二元关系R的关系矩阵为，则的转置矩阵就是逆关系的关系矩阵，即

如果把R的关系图中每条有向边的方向颠倒，就得到逆关系的关系图。34逆关系又由矩阵的运算法则可知由此可得以下定理。定理

设R是A到B的二元关系，S是B到C的二元关系，则练习354-2关系的重要性质关系的基本类型：１．自反的二元关系２．反自反的二元关系３．对称的二元关系４．反对称的二元关系５．可传递的二元关系

或称为关系的性质：自反性、反自反性、对称性、反对称性、可传递性361.自反的二元关系定义

设R是A上的二元关系，如果对于A中每一个元素x，都有(x,x)∈R，则称R是自反的，也称R具有自反性。例1:A={a,b,c},A上的二元关系

R={(a,a),(b,b),(c,c),(a,c),(c,b)}，则R是自反的二元关系。例2:设A={1,2,3,4},R={(1,1),(2,2),(3,4),(4,2)},因为3∈A,但(3,3),所以R不是A上的自反关系.371.自反的二元关系例3：设A={1,2,3},1.R是A上的小于关系,即当a<b时,(a,b)∈R。求R的关系矩阵。2.S是A上的等于关系,即当a=b时,(a,b)∈R。求S的关系矩阵。解:R={(1,2)(1,3)(2,3)}381.自反的二元关系一个集合的关系R是自反的：当且仅当关系矩阵的对角线元素都为1。例：A={a,b,c},A上的二元关系R={(a,a),(b,b),(c,c),(a,c),(c,b)}R是自反关系392.反自反的二元关系定义

R是A上的二元关系，如果对于A中每一个元素x,都有(x,x),则称R是反自反的，也称R具有反自反性。例1:设A={a,b,c},R={(a,c),(b,a),(b,c),(b,b)}因为(b,b)∈R,则R不是A上的反自反关系。例2:设A={1，2，3}，R是A上的小于关系，即Ｒ＝｛(1,2),(1,3),(2,3)}由于(1,1),(2,2),(3,3)都不属于R，所以R是A上的反自反关系。402.反自反的二元关系例3:设A={1,2,3},R={(1,2),(2,3),(3,2),(3,3)},S={(1,1),(2,2),(2,3),(3,3)},则

R既不是A上的反自反关系(因(3,3)∈R),

也不是A上的自反关系(因(1,1))

S是A上的自反关系,但不是反自反关系.注意:一个关系R如果不是自反关系，不一定是反自反关系.412.反自反的二元关系一个集合的关系R是反自反的：当且仅当关系矩阵的对角线元素都为0。例：A={a,b,c},A上的二元关系R={(a,b),(a,c),(c,b)}R是反自反关系423.对称的二元关系定义

R是A上的二元关系，每当(x,y)∈R时，就一定有(y,x)∈R，则称R是对称的，也称R具有对称性。例1:设A={a,b,c},R={(a,b),(b,a),(a,c),(c,a)}，所以R是对称的。例2:设A={1,2,3,4}上的二元关系

R={(1,1),(1,2),(2,1),(3.3),(4,3),(4,4)},因为(4,3)∈R但(3,4)。所以R不是对称的。433.对称的二元关系一个集合的关系R是对称的：当且仅当关系矩阵关于对角线对称。例：A={a,b,c，d},A上的二元关系R={(a,b),(a,d),(b,a),(b,c),(c,b), (c,d),(d,a),(d,c),(d,d)}R是对称关系443.对称的二元关系例：A={a,b,c，d},A上的二元关系R={(a,b),(a,d),(b,a),(d,d)}R不是对称关系454.反对称的二元关系定义

R是A上的二元关系，当x≠y时，如果(x,y)∈R，则必有(y,x)

，称R是反对称的，也称R具有反对称性。例1:A={1,2,3,}上的关系R={(1,2),(2,2),(3,1)},则R是反对称的.但S={(1,2),(1,3),(2,2),(3,1)}不是反对称的.因为1≠3但(1,3)∈S,且(3,1)∈S464.反对称的二元关系例2:

设A={2，3，4，6，}，R是A上的整除关系(即当a,b∈A且a能整除b时，（a,b）∈R)，问R是否是A上的反对称关系?解:因为R={（2，2）,（2，4）,（2，6）,（3，3）,（3，6）,（4，4）,（6，6）}由定义知：R是反对称的.例3:实数集合上的小于关系和小于等于关系都是反对称的.474.反对称的二元关系关系R是反对称的，则其关系矩阵为：如果rij=1,并且i≠j，则rji=0A={2，3，4，6，}R={(2,4),(2,6),(3,6)}484.反对称的二元关系例4:设A={a,b,c,d}上的关系R={(a,a),(b,c),(c,d),(d,c)},

S={(a,a),(b,b),(d,d)},则

R既不是对称的(因为(b,c)∈R但(c,b)),也不是反对称的(因为(c,d)∈R且(d,c)∈R)

而S既是对称的,也是反对称的.494.反对称的二元关系小结注意:对称关系和反对称关系不是两个相互否定的概念.

存在既是对称的也是反对称的二元关系,也存在既不是对称的也不是反对称的二元关系.505.可传递的二元关系定义

设R是A上的二元关系，每当(x,y)∈R且(y,z)∈R时，必有(x,z)∈R，则称R是可传递的，也称R具有可传递性。例1:实数集上的小于关系和小于等于关系都是可传递关系.如：a<b,b<c则a<c515.可传递的二元关系例2:设A={a,b,c}上的关系R={(a,a),(a,b),(b,c),(a,c)},S={(a,b),(c,b)},T={(a,b),(b,b),(b,c)},则R,S,T是否可传递？

R,S是可传递的,T不是可传递的

因为T中有(a,b)∈T,(b,c)∈T但(a,c),所以T不是可传递关系52例3设A={a,b,c}，R是A上的二元关系，R={(a,a),(b,b),(a,b),(a,c),(c,a)}，问：R是自反的吗？是反自反的吗？是对称的吗？是反对称的吗？是可传递的吗？解由于c∈A，而(c,c)，所以R不是自反的。由于(a,a)∈R，(b,b)∈R，所以R不是反自反的。由于(a,b)∈R，而(b,a)，所以R不是对称的。由于(a,c)∈R，且(c,a)∈R，所以R不是反对称的。由于(c,a)∈R且(a,c)∈R，但(c,c)，所以R不是可传递的。53自反,反自反,对称,反对称,可传递关系判定方法

定义法关系矩阵法关系图法54几种基本关系的关系矩阵和关系图的特征表达方式自反性反自反性对称性反对称性传递性关系矩阵主对角线元素全是1.主对角线元素全是0.矩阵是对称矩阵.如果,且,则.

对中1所在的位置,在M中相应的位置也都是1.

关系图每个顶点都有环.每个顶点都没有环.如果两个顶点之间有边,一定是一对方向相反的边(无单边).

如果两个顶点之间有边,一定是一条有向边(无双向边).

如果顶点到有边,到有边,则从到有边.

55例1：判断关系的性质设A={1，2，3}，分析A上的下述5个关系各具有哪些性质？

L={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}N={<1,3>,<2,3>}S={<1,2>,<2,1>,<1,3>}G={<1,1>,<1,2>,<2,3>}56

L={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}1.自反性：对角线全为1，所以具自反性√矩阵对称，所以具对称性√

3.对称性：对角线全不为0，所以不具自反性×2.反自反性：不具反对称性×

4.反对称性：5.传递性：具传递性√关系矩阵法57N={<1,3>,<2,3>}1.自反性：对角线全为0，所以不具自反性

×矩阵不对称，所以不具对称性×

3.对称性：对角线全为0，所以具自反性√2.反自反性：具反对称性√

4.反对称性：5.传递性：具传递性√关系矩阵法58S={<1,2>,<2,1>,<1,3>}1.自反性：所有点均无环，所以不具自反性

×出现单边，所以不具对称性×

3.对称性：所有点均无环，所以具自反性√2.反自反性：出现双边，不具反对称性×4.反对称性：5.传递性：不具传递性×关系图法59G={<1,1>,<1,2>,<2,3>}1.自反性：存在点无环，所以不具自反性

×出现单边，所以不具对称性×

3.对称性：点1有环，所以不具自反性×2.反自反性：没有出现双边，具反对称性√4.反对称性：5.传递性：不具传递性×关系图法60例2：A={1，2，3}，R1=Ø，R2=A×A，试判断两关系的性质。R1：反自反对称反对称传递R2：自反对称传递R2={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}61例题３设R1,R2为A上的对称关系，证明R1∩R2也是A上的对称关系。

所以(x,y)和(y,x)成对的出现在R1∩R2中，R1∩R2是对称关系思考R1∪R2是对称的吗？62例题４设为A上的反对称关系，则不一定是A上的反对称关系。

例如

这里R1,R2都是A上的反对称关系，但

R1∪R2

不是A上的反对称关系，却是对称的。思考:R1∩R2

在A上是否是反对称的?是反对称的！63例5设R是集合A上的二元关系，如果R⊇R2，证明R是传递关系。证明当存在(a,b)∈R，(b,c)∈R时，由复合关系的定义可知，必有(a,c)∈R2

，而R⊇R2

，所以(a,c)∈R，由此证得R是传递关系。证毕。练习64§4-3关系的闭包运算1.自反闭包、对称闭包、传递闭包的定义定义：

R是A上的二元关系，若A上二元关系R′满足（1）R′是自反的（对称的，传递的）（2）R′⊇R（3）对于任何自反的（对称的，传递的）二元关系R〞如果R〞⊇R，则有R〞⊇R′则称R′为R的自反闭包（对称闭包，传递闭包）。65

关系上的闭包运算由上述定义可知，R的自反闭包（对称闭包，传递闭包）R′：是含有R并且具有自反性质（对称性质，传递性质）的“最小”的二元关系。通常把二元关系R的自反闭包记作r(R)，对称闭包记作s(R)，传递闭包记作t(R)。例：A={1,2,3}R={(1,1),(2,2)}R1={(1,1),(2,2),(3,2),(3,3)}R2={(1,1),(2,2),(3,3)}R3={(1,1),(2,2),(1,2),(3,2),(3,3)}哪一个关系是R的自反闭包？包含R，并且自反，并且元素个数最少66关系的闭包运算分析求R的自反闭包比较简单，只需把所有

(a,a)∉R的有序对补上即可。求R的对称闭包也比较简单，每当(a,b)∈R，而(b,a)∉R时，把有序偶(b,a)添加到R上即得。

67关系的闭包运算分析求二元关系的传递闭包并不是一件容易的事情。例如：A={a,b,c,d},R={(a,b),(b,c),(c,d)}。易见:R不是传递关系，在R中有:

(a,b)∈R和(b,c)∈R，但(a,c)∉R

(b,c)∈R和(c,d)∈R，但(b,d)∉R如果把有序对(a,c)和(b,d)添加到R中去，使之扩充为R1，所以R1仍然不是传递关系，也即R1不是R的传递闭包。R1={(a,b),(b,c),(c,d),(a,c),(b,d)}但是，由于(a,c)∈R1和(c,d)∈R1,而(a,d)∉R1，68总结：求闭包的算法设R为A上的关系，则有69总结：求闭包的算法证明（3）先证：根据数学归纳法：1)根据闭包的定义，R⊆t(R)，所以n=1时R1⊆t(R)成立2)首先假设当n≥1时，Rn⊆t(R)成立，则再看看任意(x,y)∈Rn+1时，(x,y)是否也属于t(R)。因为：Rn+1

=Rn·R，根据复合关系的定义，必存在(x,c)∈Rn,(c,y)∈R,才能满足复合关系。因此又可以得到(x,c)∈t(R)，(c,y)∈t(R),根据传递闭包的定义，(x,y)∈t(R).

根据包含的定义，所以Rn+1⊆t(R)3)所以:70总结：求闭包的算法再证：1)假设(x,y)∈,(y,z)∈必存在(x,y)∈Rs，(y,z)∈Rt,因此：(x,z)∈Rs•Rt=Rs+t,所以(x,z)

∈所以对于关系来说，它是传递的。包含R的传递关系都包含了t(R)，所以两个集合互相包含，只能说明两者相等，所以71总结：求闭包的算法可以证明，当A为有限集：72求闭包的例子：例1：设A={a,b,c,d}，A上的关系R={(a,b),(b,a),(b,c),(c,d)}

求r(R)、s(R)、t(R)73例1（续）R={(a,b),(b,a),(b,c),(c,d)}74关系矩阵下闭包的构造方法设关系R,r(R),s(R),t(R)的关系矩阵分别为M,Mr,Ms和Mt,则

Mr

=M+EMs=M+M

T

Mt=M+M2+M3+…E是和M同阶的单位矩阵,MT是M的转置矩阵.注意在上述等式中矩阵的元素相加时使用逻辑加.75例：A={a,b,c},R={(a,b),(b,c),(c,a)}

求r(R),S(R)和t(R)r(R)=M+E=r(R)={(a,b),(b,c),(c,a),(a,a),(b,b),(c,c)}76例：A={a,b,c},R={(a,b),(b,c),(c,a)}

求r(R),S(R)和t(R)(续1)s(R)=M+MT=s(R)={(a,b),(b,c),(c,a),(a,c),(b,a),(c,b)}77例：A={a,b,c},R={(a,b),(b,c),(c,a)}

求r(R),S(R)和t(R)(续2)t(R)=M+M2+M3=s(R)={(a,b),(b,c),(c,a),(a,c),(b,a),(c,b),(a,a),(b,b),(c,c)}}MM2M378

关系图下闭包的构造方法设关系R,r(R),s(R),t(R)的关系图分别记为G,Gr,Gs,Gt

,则Gr,Gs,Gt

的顶点集与G的顶点集相等.除了G的边以外,以下述方法添加新边：3.考察G的每个顶点xi,找从xi出发的每一条路径，如果从xi到xj存在路径，但没有边，就加上这条边.当检查完所有的顶点后就得到图Gt

.

1.考察G的每个顶点,如果没有环就加上一个环，最终得到Gr

.2.考察G的每条边,如果有一条xi到xj

的单向边,i≠j,则在G中加一条xj

到xi的反方向边，最终得到Gs.

79实例例1设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>},R和r(R),s(R),t(R)的关系图如下图所示.Rr(R)s(R)t(R)练习80求传递闭包的算法Warshall算法:(1）置新矩阵

是关系矩阵）（2）置j=1，i=1（3）对所有i，如果，则对k=1,2,…,n，置

(4)j=j+1（5）如果j≤n，则转到步骤（3），否则停止。81例题：求传递闭包设求R的传递闭包。

解利用Warshall算法，求解步骤如下。先写出R的关系矩阵82例题：求传递闭包83用程序实现算法：#include"stdafx.h"#include<iostream.h>int

main(int

argc,char*argv[]){

intR[5][5]={0,1,0,0,0, 0,0,1,0,0, 1,0,0,0,0,0,0,0,0,1, 0,0,0,1,0};

inttR[5][5];

for(inti=0;i<5;i++)//copyRtotR {

for(intj=0;j<5;j++)

tR[i][j]=R[i][j]; }

84

for(intj=0;j<5;j++) {

for(inti=0;i<5;i++) {

if(tR[i][j]==1) {

for(intk=0;k<5;k++)

tR[i][k]=tR[i][k]||tR[j][k]; } } //print

for(inta=0;a<5;a++) {

for(intb=0;b<5;b++)

cout<<tR[a][b]<<"";

cout<<endl; }

cout<<endl; }}854-4等价关系和相容关系集合的覆盖与划分1.覆盖给定非空集合S，有非空集合A={A1,A2,…Am}。若Ai⊆S，Ai≠空集(i=1,2,…m)且则称集合A为集合S的覆盖。86等价关系例如：S={a,b,c}A={{a,b},{a,c}}B={{a},{a,c},{b}}C={{a},{a,c}}A、B是S的覆盖C不是S的覆盖87等价关系2.划分：给定非空集合S，有非空集合A={A1,A2,…Am}。若Ai⊆S，Ai≠空集(i=1,2,…m)且，还有Ai∩Aj=空集，则称集合A为集合S的划分。88等价关系例如：S={a,b,c}A={{a,b},{a,c}}B={{a},{c},{b}}C={{a},{b,c}}D={{a,b,c}}A是S的覆盖,但不是划分B、C、D是S的划分。89例题例1设A＝{a,b,c,d},

给定π1,π2,π3,π4,π5,π6如下：

π1={{a,b,c},{d}}，π2={{a,b},{c},{d}}

π3={{a},{a,b,c,d}},π4={{a,b},{c}}

π5={

,{a,b},{c,d}},π6={{a,{a}},{b,c,d}}

则π1和π2

是A的划分,其他都不是A的划分.

为什么？90等价关系的定义与实例定义

设R为非空集合上的关系.如果R是自反的、对称的和传递的,则称R为A上的等价关系.设R是一个等价关系,若(x,y)∈R,称x等价于y,记做x～y.

实例

设A={1,2,…,8},如下定义A上的关系R：

R={(x,y)|x,y∈A∧x≡y(mod3)}

其中x≡y(mod3)叫做x与y

模3相等,即x除以3的余数与y除以3的余数相等.91等价关系的验证验证模3相等关系R为A上的等价关系,因为

x∈A,有x≡x(mod3)

x,y∈A,若x≡y(mod3),则有y≡x(mod3)

x,y,z∈A,若x≡y(mod3),y≡z(mod3),

则有x≡z(mod3)自反性、对称性、传递性得到验证92A上模3等价关系的关系图设A={1,2,…,8},

R={<x,y>|x,y∈A∧x≡y(mod3)}

93等价关系的验证例：所有三角形间的相似关系是等价关系。证：

1）三角形A与它自己相似，满足自反性。

2）三角形A与B相似，则可以反过来说B与A相似，满足对称性。

3）三角形A与B相似，B与C相似，则可推断出A与C相似，满足传递性。所以：所有三角形间的相似关系是等价关系94思考题A={1,2,3,4}R={(1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1),(4,4)},判断R是否是等价的。自反对称不传递所以不是等价关系95思考题R是整数Z上的关系R={(a,b)|a∈Z,b∈Z,a=b∨a=-b}求证R是等价关系96等价类定义设R为非空集合A上的等价关系,

x∈A，令

[x]R

={y|y∈A∧xRy

}称[x]R

为x关于R的等价类,简称为x的等价类,简记为[x].实例A={1,2,…,8}上模3等价关系的等价类：

[1]=[4]=[7]={1,4,7}

[2]=[5]=[8]={2,5,8}

[3]=[6]={3,6}97等价类的性质

定理1

设R是非空集合A上的等价关系,则

(1)

x∈A,[x]是A的非空子集.

(2)

x,y∈A,如果xRy,则[x]=[y].

(3)

x,y∈A,如果xy,则[x]与[y]不交.

(4)∪{[x]|x∈A}=A，即所有等价类的并集就是A.

(5)A中每个元素必属于某个等价类。98实例A={1,2,…,8}上模3等价关系的等价类：

[1]=[4]=[7]={1,4,7}，

[2]=[5]=[8]={2,5,8}，

[3]=[6]={3,6}

以上3类两两不交，

{1,4,7}{2,5,8}{3,6}={1,2,…,8}99商集定义

设R为非空集合A上的等价关系,以R的所有等价类作为元素的集合称为A关于R的商集,记做A/R,A/R={[x]R

|x∈A

}实例

A={1,2,…,8}，A关于模3等价关系R的商集为

A/R={{1,4,7},{2,5,8},{3,6}}

A关于恒等关系和全域关系的商集为：

A/IA

={{1},{2},…,{8}}

A/EA

={{1,2,…,8}}100等价关系与划分的一一对应商集A/R就是A的一个划分

不同的商集对应于不同的划分

例：

给出A＝{1,2,3}上所有的等价关系任给A的一个划分π,如下定义A上的关系R：

R={<x,y>|x,y∈A∧x

与y在π的同一划分块中}

则R为A上的等价关系,且该等价关系确定的商集就是π.

求解思路：先求出A的所有划分,然后根据划分写出对应的等价关系.101等价关系与划分之间的对应π1,π2和π3分别对应等价关系R1,R2和R3.

R1={<2,3>,<3,2>}∪IA，R2={<1,3>,<3,1>}∪IA

R3={<1,2>,<2,1>}∪IAπ4对应于全域关系

EA，π5对应于恒等关系

IA102练习：1.判断下列关系是否为等价关系？(1)A={a,b,c,d}R={(a,a),(b,a),(b,b),(c,c),(d,d),(d,c)}(2)A={1,2,3,4}R={(1,1),(1,2),(1,3),(2,1),(2,2),(3,1),(2,3),(3,3),(4,4),(3,2),(5,5)}答案：(1)不是（b，a)无(a,b),对成性不满足

(2)是103练习：2.A={1,2,3,4},在幂集P(A)上定义二元关系如下：R={(S,T)|S,T∈P(A),|S|=|T|},写出商集P(A)/R1042.A={1,2,3,4},在幂集P(A)上定义二元关系如下：R={(S,T)|S,T∈P(A),|S|=|T|},写出商集P(A)/R首先P(A)=?P(A)={Ø,{1},{2},{3},{4},{1,2}{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}}16个元素！R关系：P(A)中每个元素，作为集合，元素个数相同的作为一个等价类。共5个等价类：（1）[Ø]（2）[{1}]={{1},{2},{3},{4}}（3）[{1,2}]={{1,2}{1,3},{1,4},{2,3},{2,4},{3,4}}（4）[{1,2,3}]={{1,2,3},{1,2,4},{1,3,4},{2,3,4}}（5）[{1,2,3,4}]={{1,2,3,4}}P(A)={[Ø],[{1}],[{1,2}],[{1,2,3}],[{1,2,3,4]}105相容关系定义1： 给定集合A上的关系r，若r是自反的，对称的，则称r是相容关系。所以：等价关系一定是相容关系相容关系不一定是等价关系106相容关系定义2： 设是R集合A上的相容关系，若C

A，如果对于C中任意两个元素a1,a2有a1Ra2，称C是相容关系R产生的相容类。107例1：设集合X={2166，243，375，648，455}X中的关系R为：

R={(x,y)|x,y∈X，并且x和y中有相同数字}检验它的自反性：xRx成立检验它的对称性：xRy成立，自然也yRx成立检验它的传递性：x1=2166,x2=243,x3=375(x1,x2)∈R,(x2,x3)∈R,但是(x1,x3)∈R,不满足传递性所以是一个相容关系！108相容关系上述例子对应的关系矩阵：由于相容关系是自反、对称，所以考察矩阵，可以发现对角线元素都为1，并且是对称矩阵。109相容关系所以可以把关系矩阵简化表示：去掉对角线及其以上的元素！110相容关系在关系图上：由于相容关系是自反的和对称的，所以每个节点必定有环，两个节点出现边的话，一定是成对出现。所以进行简化：去掉环，把一对有向边变换成一根线段，没有方向。上面例子对应的简化关系图：x1x2x3x4x5111相容关系设R是集合A上的相容关系，不能真包含在任何其它相容类中的相容类，称作最大相容类。记作Cr。112偏序关系定义

非空集合A上的自反、反对称和传递的关系，称为A上的偏序关系.

实例集合A上的恒等关系IA是A上的偏序关系.

小于等于关系,整除关系和包含关系也是相应集合上的偏序关系.113偏序关系的定义常常把集合A以及A上的偏序关系R合在一起统称为偏序集，记作（A，R）。由于偏序关系是自反的、反对称的、传递的二元关系，所以一般用符号“≤”表示偏序。当(a,b)∈R，时，常记作a≤b，偏序集也常记作（A，≤）。114线性次序定义

设R是集合A上的偏序，如果对每个x,y∈A，必有x≤y或y≤x

，则称R是线性次序的(全序的)，或称R是集合A上的线性次序关系。易知：在线性次序关系中，任意两个元素都是有关系的。115线性次序例１．在整数集合中，大于等于关系是线性序关系。例２．设Ａ＝{1,3,6,12,24},≤是整除关系

,则≤是线性次序的,并且对A中元素有

1≤3≤6≤12≤24116线性次序例3：集合{1，2，4，8}，{1，3，6}，{1，3，9，27}，{1，5，10，20}上的整除关系都是线性次序的。

117线性次序查字典，英文单词也有顺序，例如boy在book后面，我们把这种顺序叫做字典顺序。字典顺序也是一个偏序关系，由所有单词构成的集合，按照字典顺序排列，也是一个线性次序。118偏序关系的哈斯图表示定义

设R是集合A上的偏序关系，a和b是A中的元素，如果(a,b)∈R，且在A中没有其他元素c，使得

(a,c)∈R，(c,b)∈R，则称元素b盖住a。例1:A={1，2，3，4，5，6，8，10，12，16，24}，R是A上的整除关系，由“盖住”的定义可知，元素4盖住2；但元素8并不盖住2，因为有元素4，使得(2,4)∈R和(4,8)∈R，所以8不盖住2。利用元素间的盖住关系，能较方便地画出偏序关系的哈斯图(即关系图的简化)．119画哈斯图的方法用平面上的点代表集合中的元素，当b盖住a时，代表b的点应画在代表a的点的上方，并用直线段连接．否则不画线．上面例1:A={1，2，3，4，5，6，8，10，12，16，24}，R是A上的整除关系，Ｒ的哈斯图如下：

241612864103251120A={a,b,c,d,e,f,g,h}

R={<b,d>,<b,e>,<b,f>,<c,d>,<c,e>,<c,f>,<d,f>,<e,f>,<g,h>}∪IA

哈斯图实例（续）例5:已知偏序集<A,R>的哈斯图如右图所示,试求出集合A和关系R的表达式.

121偏序集中的特殊元素定义

设(A，≤)是偏序集，如果A中存在元素a，使得A中没有其他元素x，满足x≤a，则称a为A中的极小元。定义

设(A，≤)是偏序集，如果A中存在元素a，使得A中没有其他元素x，满足a≤x，则称a为A中的极大元。122偏序集中的特殊元素例1:A={2，3，4，6，8，12，16,24}，≤是A上的整除关系。其哈斯图见图1。由定义可知，(A，≤)的极小元为2和3，极大元为16和24。

2416

1286432

图1123偏序集中的特殊元素定义

设(A，≤)是偏序集，如果A中存在元素a，使得对于A中任何元素x，都有a≤x，则称a为A中的最小元。定义

设(A，≤)是偏序集，如果A中存在元素a，使得对于A中任何元素x，都有x≤a，则称a为A中的最大元。注意:最大(小)元与极大(小)元的区别124偏序集中的特殊元素例2:A={1，2，3，4，6，12}，≤是整除关系，其哈斯图见下图2。

1246231

图2

由上图可知，1是最小元，12是最大元。125偏序集中的特殊元素在很多情况下,需要考虑偏序集A的子集B的极小元,极大元,最小元和最小元等特殊元素以及其他特殊元素.定义

设(A，≤)是偏序集，B是A的子集，如果子集B中存在元素b，使得子集B中没有其他元素x，满足x≤b，则称b为子集B中的极小元；同样，如果在子集B中存在元素b，使得子集B中没有其他元素x，满足b≤x，则称b为子集B中的极大元。定义

设(A，≤)是偏序集，B是A的子集，如果子集B中存在元素b，使得对于子集B中任何元素x，都有b≤x，则称b为子集B中的最小元；同样，如果在子集B中存在元素b，使得对于子集B中任何元素x，都有x≤b，则称b为子集B中的最大元。126特殊元素的性质

对于有穷集，极小元和极大元必存在，可能存在多个.

最小元和最大元不一定存在，如果存在一定惟一.

最小元一定是极小元；最大元一定是极大元.

孤立结点既是极小元，也是极大元.127偏序集中的特殊元素例3:A={1，2，3，4，5，6，10，12}，≤是A上的整除关系。其哈斯图见右。

在子集{1，2，3，6}中，1是极小元也是最小元；6是极大元也是最大元。在子集{2，3，4，12}中，2和3是极小元；但没有最小元；12是极大元也是最大元。在子集{2，5，6}中，2和5是极小元，而5还是极大元，6也是极大元，但此子集中没有最小