第三章 集合与关系

第三章集合与关系第1页，课件共117页，创作于2023年2月§3.4关系及其表示[定义3-5.1]若则是一个二元关系。即：序偶作为元素的任何集合。２．关系表示方法（1）枚举法（直观法、列举法）设R表示二元关系，用表示特定的序偶，若，则也可写成：xRy。\第2页，课件共117页，创作于2023年2月§3.4关系及其表示例：二元关系定义如图：可写成：由定义可见：关系是一个集合，∴定义集合的方法都可以来定义关系。第3页，课件共117页，创作于2023年2月§3.4关系及其表示（2）谓词公式表示法前面讲述，一个集合可用谓词公式来表达，所以关系也可用谓词公式来表达。例：实数集合R上的“>”关系可表达为：大于关系：“>”= 父子关系：“F”=第4页，课件共117页，创作于2023年2月§3.4关系及其表示（3）关系矩阵表示法规定：(a)二元关系<x,y>中的序偶中左元素表示行，右元素表示列；(b)若，则在对应位置记上“1”，否则为“0”。第5页，课件共117页，创作于2023年2月§3.4关系及其表示例1：设并定义为列出关系矩阵：第6页，课件共117页，创作于2023年2月§3.4关系及其表示

是Ｘ→Ｙ的全域关系，

例2：设X={a,b,c},Y={1,2},R2是Ｘ→Ｙ的关系，第7页，课件共117页，创作于2023年2月§3.4关系及其表示（4）关系图表示法规定：(a)把Ｘ、Ｙ集合中的元素以点的形式全部画在平面上；(b)若，则xi和yi之间画一箭头弧线，反之不画任何联线。例：是X中的二元关系，第8页，课件共117页，创作于2023年2月§3.4关系及其表示用关系图表示：第9页，课件共117页，创作于2023年2月§3.4关系及其表示３．关系的定义域和值域：[定义]设S是一个二元关系，D(s)是所有客体x的集合，对于一些y来说，若有，则称D(s)为S的定义域（简称“域”），即设R(S)是所有客体y的集合，对于一些X来说，若有，则称集合R(S)是S的值域（简称“值”）,即：第10页，课件共117页，创作于2023年2月§3.4关系及其表示

例：X={1,2,3,4,5,6},R为X到Y的二元关系：，则一般情况，称X为R的前域，称Y为R的陪域。第11页，课件共117页，创作于2023年2月§3.4关系及其表示４．关系和笛卡尔乘积笛卡尔乘积的任何子集都可以定义一种二元关系。例：X={1,2,3,4}，Y={1,2}，则均为二元关系。

第12页，课件共117页，创作于2023年2月§3.4关系及其表示５．三个特殊关系：空白关系，全域关系，恒等关系[定义]集合X2定义了X集合中的一种关系，通称为X中的全域关系，用Ex表示：空集也是的一个子集，它也定义了一种关系称为空白关系；X集合中的恒等关系，

在全域关系和恒等关系中前域=定义域，陪域=值域。第13页，课件共117页，创作于2023年2月§3.4关系及其表示例：Ｘ=｛Ｔ，Ｆ｝则同一域上的关系,可进行集合的所有运算。第14页，课件共117页，创作于2023年2月§3.5关系的性质１．自反性：

[定义]设Ｒ是Ｘ集合中的二元关系，对于每一个（所有的）有,则称Ｒ是自反关系,X中R是自反的例：设是自反的关系。R的关系矩阵第15页，课件共117页，创作于2023年2月§3.5关系的性质[定义]设R是X中的二元关系，对于每一个，有xx，则称R是反自反的关系，表示成：R是X中的反自反的关系xx。例：设X={1,2,3},

第16页，课件共117页，创作于2023年2月§3.5关系的性质２．对称性[定义]设R是X中的二元关系，对于每一个来讲，如果每当有xRy，则必有yRx，则称R是X中的对称关系，并表示成：R是X中的对称关系

S4既不是自反的，又不是反自反的第17页，课件共117页，创作于2023年2月§3.5关系的性质例：设X={1,2,3},R={<1,1><2,1><1,2><3,2><2,3>}则R是对称的关系[定义]设R是X集合中的二元关系，对于每一个

来讲，如果每当xRy和yRx就必有x=y，则称R是反对称的关系。第18页，课件共117页，创作于2023年2月§3.5关系的性质即当且仅当X中的R才是反对称的。讨论定义：（1）前件为“T”，则x=y也为“T”,则为反对称的；（2）前件为“F”，则有三种情况：后件（x=y）不论是真还是假，命题公式为“T”。下面举例说明：第19页，课件共117页，创作于2023年2月§3.5关系的性质例：设X={a,b,c}均是反对称的第20页，课件共117页，创作于2023年2月§3.5关系的性质例：X={a,b,c},下列关系不是对称的，也不是反对称的第21页，课件共117页，创作于2023年2月§3.5关系的性质X上的恒等关系是自反、对称、反对称的。第22页，课件共117页，创作于2023年2月§3.5关系的性质X上的全域关系：

是自反的，对称的

X上的空关系是反自反、对称、反对称的。第23页，课件共117页，创作于2023年2月§3.5关系的性质３．传递性：

[定义]设R是X中的二元关系，对于每一个来说，如果每当

，就必有

则称R是可传递的，并表示成：X中R可传递讨论定义：（1）前件为“T”，

则xRz也为“T”，R是可传递的；（2）前件为“F”，有三种情况后件不论是真还是假，命题为“T”，则R是可传递的

第24页，课件共117页，创作于2023年2月§3.5关系的性质

例：设X={a,b,c}，则下列关系均是可传递的第25页，课件共117页，创作于2023年2月§3.5关系的性质下列关系是不可传递的：第26页，课件共117页，创作于2023年2月§3.5关系的性质４．确定二元关系性质举例（1）设X={1,2,3}，反自反，反对称，可传递的；反对称的；第27页，课件共117页，创作于2023年2月§3.5关系的性质自反，对称，反对称，可传递的；自反，对称，可传递的；反自反的，对称的，反对称的，可传递的。第28页，课件共117页，创作于2023年2月§3.5关系的性质（2）若

，则X上的空关系自反的，反自反的，对称的，反对称的，可传递的。从定义上看前件为假，后件不论是真还是假，命题为“T”，第29页，课件共117页，创作于2023年2月3.6关系的运算一、关系的集合运算：关系是有序对集合，集合的元素对关系仍然适用。定理1：设R和S是从A到B的两个关系，则R∩S，R∪S，R-S，~R，R⊕S仍是从A到B的关系。第30页，课件共117页，创作于2023年2月3.6关系的运算二、复合关系：引例：a，b，c三人，a，b是兄妹关系，b，c是母子关系，则a，c是舅甥关系。如设R是兄妹关系，S是母子关系，则R与S的复合T是舅甥关系，而S与R复合是母女关系。又如：R是父子关系，R与R的复合是祖孙关系。第31页，课件共117页，创作于2023年2月3.6关系的运算1、复合关系的定义（关系的复合运算）定义3-7.1：设X，Y，Z是三个集合，设R为X到Y的关系，S为Y到Z的关系，则R◦S为R和S的复合关系，表示为：第32页，课件共117页，创作于2023年2月3.6关系的运算1、复合关系的定义（关系的复合运算）说明：（1）R与S能进行复合的必要条件是R的值域所属集合B与S定义域所属集合B是同一集合，否则就不能复合。（2）<x，z>有这个复合关系的定义为至少有一个中间桥梁的元素y，使<x,y>∈R与<y,z>∈S（3）RS为新的二元关系（4）RSX×Z第33页，课件共117页，创作于2023年2月3.6关系的运算例1：设A={1,2,3,4,5},B={3,4,5},C={1,2,3},R是A到B的关系，S是B到C的关系。R={<x,y>|x+y=6}={<1,5>,<2,4>,<3,3>}S={<y,z>|y-z=2}={<3,1><4,2><5,3>}则R◦S=？R◦S={<1,3>，<2,2>，<3,1>}第34页，课件共117页，创作于2023年2月3.6关系的运算例2：设A={1,2,3,4,5}，R,S均为A→A的关系，且R={<1,2><3,4><2,2>}S={<4,2><2,5><3,1><1,3>}S◦R={<4,2><3,2><1,4>}∴“◦”是不可交换的。则R◦S={<1,5><3,2><2,5>}第35页，课件共117页，创作于2023年2月3.6关系的运算∴“◦”是不可交换的。说明：（1）R是A到B的关系，S是B到C的关系，R◦S有定义，而S◦R根本不能复合。（2）若A=C，则R◦S是A上的关系，而S◦R是B上的关系，不可能相等。（3）若A=B=C，R、S均为A上的关系，R◦S和S◦R也是A上的关系，一般地R◦S和S◦R不可能相等。第36页，课件共117页，创作于2023年2月3.6关系的运算定理：设则有：复合关系图可见复合关系满足结合律

第37页，课件共117页，创作于2023年2月3.6关系的运算由关系复合的结合律可知关系R本身所组成的复合关系可以写成：R◦R，R◦R◦R，…，分别记作R（2），R（3），…定义：给定集合X，R是X中的二元关系，设nN，则R的n次幂Rn可以定义为：（1）R0=X集合中的恒等关系

（2）Rn+1=

Rn◦R

第38页，课件共117页，创作于2023年2月3.6关系的运算例3设R，S是I+中的二元关系，且则：第39页，课件共117页，创作于2023年2月3.6关系的运算例4若|X|=n，则X中的二元关系R的幂次值是有限的。一般不用求出超过X的基数次幂。

第40页，课件共117页，创作于2023年2月3.6关系的运算2、复合关系的矩阵表示设有三个集合：

设R为X到Y的关系，S为Y到Z的关系：而|X|=m,|Y|=n,|Z|=p，则关系矩阵第41页，课件共117页，创作于2023年2月3.6关系的运算2、复合关系的矩阵表示例5：设X={1,2,3,4,5},R,S均是X中的二元关系，R={<1,2><3,4><2,2>},S={<4,2><2,5><3,1><1,3>}第42页，课件共117页，创作于2023年2月3.6关系的运算３．逆关系

[定义3-7.2]设X,Y是二个集合，若R是X→Y的关系，从Y→X的关系，称为R的逆关系，用表示，或用Rc表示。讨论定义：（1）只要将R中每一个序偶中的元素全部调换位置,就可得到R的逆关系

，故||=|R|（2）设的关系矩阵为的转置矩阵；（3）在R的关系图中，只要把所有箭头改换方向就可得到的关系图。（自回路箭头改变与否无关）

第43页，课件共117页，创作于2023年2月3.6关系的运算3、逆关系例6：X={0,1,2}，R={<0,0><0,1><1,2><2,2>},={<0,0><1,0><2,1><2,2>},第44页，课件共117页，创作于2023年2月3.6关系的运算定理3-7.1设R，R1，R2都是从A到B的二元关系，则下列各式成立。第45页，课件共117页，创作于2023年2月3.6关系的运算定理3-7.2设T为从X到Y的关系，S为从Y到Z的关系，证明第46页，课件共117页，创作于2023年2月3.6关系的运算例：

，试求：

第47页，课件共117页，创作于2023年2月3.6关系的运算第48页，课件共117页，创作于2023年2月3.6关系的运算定理3-7.3设R为X上的二元关系，则（1）R是对称的，当且仅当R=Rc（2）R是反对称的，当且仅当R∩Rc

Ix第49页，课件共117页，创作于2023年2月3.6关系的运算证明：①充分性：R是对称的对于任一②必要性：R是对称的，∴对任一∴R一定是对称的∴第50页，课件共117页，创作于2023年2月§3.7关系的闭包运算[定义3-8.1]给定集合X，R是X中的二元关系，若有另一关系R’满足下列条件：（1）R’是自反的（对称，可传递的）；（2）（3）对于任一自反（对称，传递的）关系R’’，若，则

则称R’是R的自反（对称，传递的）闭包，并依次用r(R),s(R),t(R)来表示之。第51页，课件共117页，创作于2023年2月§3.7关系的闭包运算讨论定义：（1）由（2）知，R’是在R的基础上添加元素（有序对）；（2）由（1）知，R添加元素其目标是使R’具有自反性（对称性、传递性）（3）由（3）知，在添加后使之具有自反性的所有关系中R’是最小的一个，即要在保证其具有自反性的前提下，要尽量少添加元素，没必要的元素不要加入。第52页，课件共117页，创作于2023年2月§3.7关系的闭包运算例：设X={a,b},R={<a,a><a,b>}，r(R)={<a,a><a,b><b,b>},s(R)={<a,a><a,b><b,a>},t(R)={<a,a><a,b>}=R例：求t(R)需要特别小心，要进行多次添项。设X={a,b,c},R={<a,b><b,c><c,a>}，求r(R),s(R),t(R)解：r(R)=s(R)=t(R)={<a,b><b,c><c,a><a,c><b,a><c,b><a,a><b,b><c,c>}第53页，课件共117页，创作于2023年2月§3.7关系的闭包运算从关系图中可以看到：（1）r（R）是在R的基础上添加自回路，使得每点均有自回路。（2）s（R）是在R中两点间只有一条弧的情况下，再添加一条反向弧，使得两点间或是0条弧，或是两条弧，原来两点间没有弧不能添加。（3）t（R）是在R中如结点a通过有向路能通到x，则添加一条从a到x的有向弧，其中包括如a能达到自身，则必须添从a到a的自回路。第54页，课件共117页，创作于2023年2月§3.7关系的闭包运算[定理3-8.1]给定集合X，R是X中的二元关系，那么：（1）当且仅当r(R)=R，则R是自反的；（2）当且仅当s(R)=R，则R是对称的；（3）当且仅当t(R)=R，则R是可传递的。第55页，课件共117页，创作于2023年2月§3.7关系的闭包运算[定理3-8.2]R是X中的二元关系是X中的恒等关系，则有证明：按定义证：（1）设，则R’是自反的，

（3）设有任一R’’也是自反的，且则第56页，课件共117页，创作于2023年2月§3.7关系的闭包运算[定理3-8.3]给定集合X，R是X中的二元关系，则有[定理3-8.4]设X是一集合，R是X中的二元关系，则：第57页，课件共117页，创作于2023年2月§3.7关系的闭包运算例：X={a,b,c},R={<a,b><b,c><c,a>}，|X|=3,则[定理3-8.5]设|X|=n，R是X中的二元关系，则第58页，课件共117页，创作于2023年2月§3.7关系的闭包运算说明：Rk的每条弧就是在R中，任何一点x，经过k条弧组成的有向路到达y，则<x，y>∈Rk而传递闭包t(R)就是在R中如点x经过任何条弧能到达y，则x到y应直接有一条有向弧，故定理[3-8.4]就是t(R)要在R的基础上并上R2，R3…而如A是有限集合|A|=n，如在x点有超过n步能到达y点，则必有一条更短的有向路，至多n步可以到达y，所以得到[3-8.5]。第59页，课件共117页，创作于2023年2月§3.7关系的闭包运算例：X={a,b,c,d},R={<a,b><b,c><c,d>},则第60页，课件共117页，创作于2023年2月§3.7关系的闭包运算[定理]设X是一集合，R是X中的二元关系，则有：（1）r(S(R))=S(r(R));（2）r(t(R))=t(r(R));（3）t(S(R))S(t(R))。第61页，课件共117页，创作于2023年2月§3.7关系的闭包运算证明：（1）r(S(R))常用下列符号表示一些闭包：“R加”：

，传递闭包，

“R星”：

，自反可传递闭包，

第62页，课件共117页，创作于2023年2月§3.7关系的闭包运算例：设X={a,b,c},R={<a,b><c,c>}（1）rS(R)=r{<a,b><b,a><c,c>}={<a,b><b,a><c,c><a,a><b,b>}Sr(R)=s{<a,b><c,c><a,a><b,b>}={<a,b><b,a><c,c><a,a><b,b>}（2）rt(R)=r{<a,b><c,c>}={<a,b><c,c><a,a><b,b>}tr(R)=t{<a,b><c,c><a,a><b,b>}={<a,b><c,c><a,a><b,b>}（3）tS(R)=t{<a,b><c,c><b,a>}={<a,b><c,c><b,a><a,a><b,b>}St(R)=S{<a,b><c,c>}={<a,b><c,c><b,a>}

∴t(S(R))

St(R)

第63页，课件共117页，创作于2023年2月§3.8集合的划分和覆盖[定义1]给定一非空集合A，又设若（1）（2）则称S为A的覆盖。例1：S={a,b,c}，A={{a,b},{b,c}}，B={{a},{a,b},{c}}，C={{a},{b},{c}}，D={{a},{b},{a,c}}均为S的覆盖。第64页，课件共117页，创作于2023年2月§3.8集合的划分和覆盖[定义1]给定一非空集合A，又设若（1）（2）则称S为A的覆盖。例2：四个半圆覆盖一正方形。第65页，课件共117页，创作于2023年2月§3.8集合的划分和覆盖[定义2]给定一非空集合S，设非空集合如果有：或（i,j=1,2…,m）则称集合A是集合S的一个划分。第66页，课件共117页，创作于2023年2月§3.8集合的划分和覆盖讨论定义：（1）划分和覆盖主要差别在第（2）条；（2）划分A中的元素，称为划分的类，在定义中均是A中的一个类，类的个数称为划分的秩；（3）若A为有限集合，则A的秩是有限的，为|A|，若A为无限集合，则划分的秩是无限的；（4）集合的划分必定是一个覆盖，而覆盖不一定是划分；（5）集合S上的秩最大的划分称最大划分，最小的称最小划分。第67页，课件共117页，创作于2023年2月§3.8集合的划分和覆盖例3：设S={a,b,c}，下列均为S的一个划分：=2（秩）；最大划分，秩为3；最小划分，秩为1。=2（秩）；=2（秩）；第68页，课件共117页，创作于2023年2月§3.8集合的划分和覆盖例4：四个直角三角形组成了正方形的一个划分秩=4第69页，课件共117页，创作于2023年2月§3.8集合的划分和覆盖[定义]设A和A’是非空集合S的二种划分，并可表示成：

若A’的每一个类

都是A的某一个类的子集，则称划分A’是划分A的加细，或讲A’加细了A，若A’加细了A且则称A’是A的真加细。讨论定义：A’加细了A，一定有|A’|≥|A|（秩），若|A’|>|A|，则一定为真加细。第70页，课件共117页，创作于2023年2月§3.8集合的划分和覆盖例：S={a,b,c,d}，S的划分：A={{a,b},{c,d}},A’={{a}{b}{c,d}}，则A’是A的真加细A’’={{a}{b}{c}{d}},则A’’是A的真加细第71页，课件共117页，创作于2023年2月§3.9等价关系与等价类[定义3-10.1]设R为定义在集合A上的一个关系，若R是自反的、对称的和传递的，则R称为等价关系。如果R是一个等价关系，<a，b>∈R称a等价于b，记作a~b。

（1）在一群人的集合上年龄相等的关系是等价关系，而朋友关系不一定是等价关系，因为它可能不是传递的。（2）命题公式间的逻辑等值关系是等价关系。（3）集合上的恒等关系和全域关系都是等价关系。（4）在同一平面上直线之间的平行关系，三角形之间的相似关系都是等价关系。第72页，课件共117页，创作于2023年2月§3.9等价关系与等价类例1A={1，2，3，4，5，6，7}，R是A上的“模3同余”关系，为整数}即x≡y(mod3)试验证R是等价关系，画出R的关系图，列出R的关系矩阵

第73页，课件共117页，创作于2023年2月§3.9等价关系与等价类（2）R的关系矩阵

解：（1）R={<1,1><1,4><1,7><2,2><2,5><3,3><3,6><4,1><4,4><4,7><5,2><5,5><6,6><6,3><7,7><7,4><7,1>}从图中可以看出，该等价关系将A分成3个类{1,4,7},{2,5,8},{3,6},类内均有关系，而类间均没有关系R满足自反、对称和可传递的，∴R是一等价关系第74页，课件共117页，创作于2023年2月§3.9等价关系与等价类[定义]设m∈I+x，y∈I，若对于某个整数n有：（x-y）=n×m，则称x模m等于y，记作：x≡y(modm)

[定理]任何集合X

I，（I的任何子集X中）的模m等价，是一个等价关系。

第75页，课件共117页，创作于2023年2月§3.9等价关系与等价类[定义3-10.2]设R为集合A上的等价关系，对于任何a∈A，集合[a]R

={x|x∈A，aRx}称为元素a形成的R等价类。讨论定义：（1）等价类[a]R是一个集合，由定义可见[a]R

A

（2）[a]R中的元素是等价关系中，所有与a具有关系的元素所组成的集合，且[a]R≠

第76页，课件共117页，创作于2023年2月§3.9等价关系与等价类例：设X=N，关系R={可被3整除}

是一等价关系，则R可以找出三个等价类：={0，3，6，9…}，此集合中的元素除以3的余数为“0”；

={1，4，7，10…}，此集合中的元素除以3的余数为“1”；={2，5，8，11…}，此集合中的元素除以3的余数为“2”。第77页，课件共117页，创作于2023年2月§3.9等价关系与等价类例：设X={a,b,c,d}，R是X中的等价关系，R={<a,a><b,b><a,b><b,a><c,c><d,d><c,d><d,c>}则第78页，课件共117页，创作于2023年2月§3.9等价关系与等价类[定理]设X是一个集合，R是X中的等价关系，则（1）若，则

（2）若xRy，则（3）

（3）若xy，则第79页，课件共117页，创作于2023年2月§3.9等价关系与等价类例：X为全班同学的集合，则班中同姓关系是一个等价关系，（1）任何一个人均∈某一个等价类，王某某∈[王]

R

张某∈

[张]R…

（2）任何二个姓的等价类，只有二种可能一种：[王]R=[李]R

二种：[王]R[李]R=

（3）全班同学的集合=同姓关系等价类的并集=[王][李]…（4）所有等价类的集合，一定导致全班同学集合的一个划分：A={[王]R，[李]R….}第80页，课件共117页，创作于2023年2月§3.9等价关系与等价类[定理3-10.2]设X是一非空集合，R是X中的等价关系，R等价类的集合{[x]R|x∈X}是X的一个划分，且此集合称为X按R的商集，用表示之。例：设X={x1,x2…..xn}

（1）X集合中的全域关系，，它是一个等价关系，∴X按

R1的商集它形成了X的一个最小划分第81页，课件共117页，创作于2023年2月§3.9等价关系与等价类（2）X中的恒等关系它形成了X的一个最大划分例：X为全班同学的集合，|X|=n,(n∈N)（1）同学关系R1是一个等价关系，

（2）按指纹的相同关系R2是一个等价关系，它形成了全班同学的最大划分第82页，课件共117页，创作于2023年2月§3.9等价关系与等价类（3）同姓关系R3是一等价关系{[张]R3，[李]R3，…}它形成了全班同学的既不是最大，又不是最小划分第83页，课件共117页，创作于2023年2月§3.9等价关系与等价类[定理3-10.3]X是一非空集合，A为X的一个划分，且 A={A1,A2,….An}，则由A导出的X中的一个等价关系

例：X＝{a,b,c,d}，A={{a,b},{c,d}}则R＝({a,b}×{a,b})({c,d}×{c,d})={<a,a>,<a,b>,<b,a>,<b,b>,<c,c>,<c,d>,<d,c>,<d,d>}

由此我们看到：集合X上的等价关系与X的划分之间有对应关系。第84页，课件共117页，创作于2023年2月§3.10相容关系[定义3-11.1]给定一个集合X，R是X中的二元关系，如果R是自反、对称的，则称R是相容关系。例：设X={ball,bed,dog,let,egg},5个英文单词定义X中一个二元关系：R={

有相同的字母}则R是自反的，对称的，但不可传递∵(ballRbed)(bedRegg)(ballRegg)则R={<1,1><1,2><2,1><1,4><4,1><2,2><2,3><3,2><2,4><4,2><2,5><5,2><3,3><3,5><5,3><4,4><4,5><5,4><5,5>}第85页，课件共117页，创作于2023年2月§3.10相容关系第86页，课件共117页，创作于2023年2月§3.10相容关系[定义3-11.2]设X是一个集合，R是X上的相容关系，假定AX，若对于A中任意两个元素a1，a2有a1Ra2，称A是由相容关系R产生的相容类。第87页，课件共117页，创作于2023年2月§3.10相容关系[定义3-11.3]设X是一个集合，R是X中的相容关系，假定AX，若任一x∈A都与A中的其它所有元素有相容关系，而（X-A）中没有一个元素与A中的所有元素有相容关系，则称子集A为相容关系R的一个最大相容类。

例：上例中

均是X中的最大相容类,且定义了X的一个覆盖。同样已知X集合的一个覆盖第88页，课件共117页，创作于2023年2月§3.10相容关系则一定可以求出相对应的相容关系来：讨论等价关系和相容关系后可得到结论：集合X上的相容关系R的所有最大相容类集合{A1,A2,….Am}构成集合X的一个覆盖。即：而集合X上的等价关系R的所有等价类集合构成X的一个划分第89页，课件共117页，创作于2023年2月§3.10相容关系求最大相容类的方法：关系图法：确定最大完全多边形每个顶点都与其他所有顶点相联结的多边形。(1)孤立结点是最大的完全多边形；(2)二个相互联结的结点是最大完全多边形；(3)三角形是三个结点的最大完全多边形；第90页，课件共117页，创作于2023年2月§3.10相容关系(4)四个结点；(5)五个结点;画出简化相容关系的关系图后，先结点最多的完全多边形，以后逐次减少。第91页，课件共117页，创作于2023年2月§3.10相容关系例：已知相容关系图，求出最大相容类第92页，课件共117页，创作于2023年2月§3.10相容关系最大相容类集合为第93页，课件共117页，创作于2023年2月3.11序关系1、偏序关系[定义3-12.1]设R是非空集合A上的关系，如果R具有自反性、反对称性和传递性，则R是A上的偏序关系，并把关系R记作“”。序偶<A，>称作偏序集。讨论定义：（1）“”不是指普通实数中的≤关系，而是代表更为普遍的关系（具有自反，反对称和可传递性的关系）；（2）如果<x，y>∈，则记作xy，读作“x小于或等于y”第94页，课件共117页，创作于2023年2月3.11序关系1、偏序关系例1、设集合A={a，b，c}，A上的关系R为：R={<a，a>，<a，b>，<a，c>，<b，b>，<b，c>，<c，c>}，从关系图来验证R是偏序关系第95页，课件共117页，创作于2023年2月3.11序关系例2、设A是非零自然数集，R是A上的整除关系，验证R是偏序关系。（1）

x∈A，因x能整除x，∴R具有自反性。（2）

x，y∈A，如x能整除y，且y能整除x，则x=y。即<x，y>∈R，<y，x>∈R，则x=y，即R具有反对称性。（3）

x，y，z∈A，如<x，y>∈R，<y，z>∈R，即x能整除y，y能整除z，则x能整除z，∴<x，z>∈R，∴R具有传递性。∴R是A上的偏序关系。第96页，课件共117页，创作于2023年2月3.11序关系2、拟序关系设R是非空集合A上的关系，如果R具有反自反性和传递性，则R是A上的拟序关系，并把关系R记作“”。序偶<A，>称作拟序集。讨论定义：（1）“”不是指普通实数中的＜关系，而是代表拟序关系；（2）如果<x，y>∈，则记作xy，读作“x小于y”第97页，课件共117页，创作于2023年2月3.11序关系2、拟序关系例3、A={1，2，3，4}，R是A上的大于关系。R={<a，b>|a>b，a，b∈A>则R={<2，1>，<3，1>，<3，2>，<4，1>，<4，2>，<4，3>}注：<3，1>∈R，在实数中3大于1，因其是拟序关系，写作“31”，读作“3小于1”，该小于是拟序的“小于”，而不同于真正实数中的小于。

第98页，课件共117页，创作于2023年2月3.11序关系2、拟序关系定理：设R是集合A上的拟序关系，则R是反对称的。证明：（反证法）设R不是反对称的。则a，b∈A，a≠b且<a，b>∈R,<b，a>∈R，因R是传递的，∴<a,a>∈R，<b,b>∈R。与R是反自反的矛盾，∴R具有反对称性。

第99页，课件共117页，创作于2023年2月3.11序关系2、拟序关系定理：设R是集合A上的拟序关系，则R是反对称的。说明：（1）由自反性和传递性可以推出反对称（2）拟序关系具有反自反性、反对称性和可传递性。（3）拟序和偏序的区别在于反自反性和自反性。若R是偏序关系，则R-IA是拟序关系若R是拟序关系，则R∪IA是偏序关系

第100页，课件共117页，创作于2023年2月3.11序关系3、全序关系[定义3-12.4]设R是A上的偏序关系，

若

a，b∈A，则ab和ba，两者必居其一，则称R为A上的全序关系，或称线序关系。（1）整除关系R，集合的包含关系，公式的重言蕴含关系均是偏序关系。（2）实数中的<，>，集合的真子集均是全序关系。（3）实数中的≤，≥是全序关系。第101页，课件共117页，创作于2023年2月3.11序关系4、哈斯图描述偏序集的关系图，可以简化为哈斯图，其简化规则为：（1）用“”表示R中的结点（2）所有结点的自回路均省略（3）省略所有弧上的箭头，适当排列A中的元素位置，如ab，则a画在b的下方。（4）如ab，bc，则必有ac，a到b有边，b到c有边，则a到c的无向弧必须省略。第102页，课件共117页，创作于2023年2月3.11序关系4、哈斯图例4、画出下列偏序集合的哈斯图。（1）<{1,2,3,4,5,6},R>R={<1,1><2,2><3,3><4,4><5,5><6,6><1,2><1,3><1,4><1,5><1,6><2,4><2,6><3,6>}第103页，课件共117页，创作于2023年2月3.11序关系4、哈斯图例4、画出下列偏序集合的哈斯图。（2）A={a,b,c>，包含关系R

是上的偏序关系。则<,R

>是偏序集，其哈斯图如下：第104页，课件共117页，创作于2023年2月3.11序关系4、哈斯图例4、画出下列偏序集合的哈斯图。（3）A={1,2,3，4>，≤是实数上的小于等于关系，因<A，≤>不仅是偏序关系，而且是全序关系，全序关系的哈斯图是一条线故又称线序，即任何两个元素均存在大小关系。第105页，课件共117页，创作于2023年2月3.11序关系例5、已知偏序集合<A，>的哈斯图如图，写出集合A和关系第106页，课件共117页，创作于2023年2月3.11序关系5、最大元、最小元、极大元、极小元定义：设<A，>是偏序集，集