第三章 二元关系备选

第三章二元关系备选第1页，课件共100页，创作于2023年2月§9等价关系与等价类试验证R是等价关系，画出R的关系图，列出R的关系矩阵解：（1）R={<1,1><1,4><1,7><2,2><2,5><3,3><3,6><4,1><4,4><4,7><5,5><5,2><6,6><6,3><7,7><7,4><7,1>}（2）R的关系矩阵第2页，课件共100页，创作于2023年2月§10相容关系例：已知相容关系图，求出最大相容类第3页，课件共100页，创作于2023年2月§10相容关系最大相容类集合为第4页，课件共100页，创作于2023年2月例题选讲例1.设A，B，C，D代表任意集合，判断以下命题是否恒真，如果不是，请举一反例。(1)ABCDACBD(2)ABCDA-DB-C(3)ABB=A(B-A)(4)A-B=B-AA=B解：(1)不为真。举反例如下：令A＝{1},B={1,4},C={2},D={2,3}则AB且CD，但AC＝BD，与结论矛盾。第5页，课件共100页，创作于2023年2月例题选讲(2)由于CD～D～C，又由AB可得A～DB～C即A－DB－C成立。(3)由于A(B－A)=AB故有： B=A(B－A)B=ABAB即AB的充要条件为B=AB或A=AB或A－B=第6页，课件共100页，创作于2023年2月例题选讲(4)易见，当A=B时，必有A-B=B-A由A-B=B-A得(A-B)B=(B-A)B 即：(A~B)B=(B~A)B 即：B-A=∴BA同理可证：AB从而得到：A＝B第7页，课件共100页，创作于2023年2月例题选讲例2.设：A、B是任意的集合(1)试证明(A)(B)=(AB)(2)(A)(B)=(AB)成立吗？为什么？解 ：(1)证明S(A)(B)，则S(A)且S(B)，因此：SA且SB

∴ SAB即S(AB)

∴ (A)(B)(AB)反之，设S(AB)，则SAB，第8页，课件共100页，创作于2023年2月例题选讲 因此 SA且SB ∴ S(A)且S(B) 于是 S(A)(B) ∴ (AB)(A)(B)由上知 (A)(B)＝(AB)(2)(A)(B)(AB)成立。其证明如下： 设：S(A)(B)，则S(A)或S(B)因此SA或SB ∴ SAB 即S(AB)故(A)(B)(AB)成立第9页，课件共100页，创作于2023年2月例题选讲 (AB)(A)(B)不成立设：S(AB)，则SAB。但此时无法推断SA，也无法推断SB，因此既不能得出S(A)，也不能得出 S(B)。例如：设A={a,c}，B={c,b}则AB={a,b,c}，设S={a,b}，则SAB即 S(AB)但S(A)且S(B)因此S(A)(B)第10页，课件共100页，创作于2023年2月例题选讲例3. 设S={1,2,3,…10}，≤是S上的整除关系，求<S,≤>的哈斯图，并求其中的最大元，最小元。最小上界，最大下界。分析：画哈斯图的关键在于确定结点的层次和元素间的盖住关系。画图的基本步骤是：(1)确定偏序集<A,≤>中的极小元，并将这些极小元放在哈斯图的最底层；(2)若第n层的元素已确定完毕，从A中剩余的元素中选取至少能盖住第n层中一个元素的元素，将这些元素放在哈斯图的第n+1层。第11页，课件共100页，创作于2023年2月例题选讲在排列结点的位置时，注意把盖住较多元素的结点放在中间，将只盖住一个元素的结点放在两边，以减少连线的交叉；(3)将相邻两层的结点根据盖住关系进行连线。第12页，课件共100页，创作于2023年2月例题选讲在画哈斯图时应该注意下面几个问题：(1)哈斯图中不应该出现三角形，如果出现三角形，一定是盖住关系没找对。纠正的方法是重新考察这3个元素在偏序集中的顺序，然后将不满足盖住关系的那条边去掉。(2)哈斯图中不应该出现水平线段。出现这种错误的原因在于没有将“较大”元素放在“较小”元素的上方。纠正时只要根据“大小”顺序将“较大”的元素放到更高的一层，将水平线改为斜线就可以了。(3)哈斯图中要尽量减少线的交叉。图形中线的交叉多少主要取决于同一层结点的排列顺序，第13页，课件共100页，创作于2023年2月例题选讲如果出现交叉过多，可以适当调整结点的排列顺序。最后，如何确定哈斯图中极大元、极小元、最大元、最小元、最小上界和最大下界。方法如下：(1)如果图中有孤立结点，那么这个结点既是极小元，也是极大元，并且图中既无最小元，也无最大元。（除只有唯一孤立结点的情况）(2)除了孤立结点以外，其它的极小元是图中所有向下通路的终点，其它的极大元是图中所有向上通路的终点。第14页，课件共100页，创作于2023年2月例题选讲例4.设Z+={x|xZx>0}，1，2是Z+的2个划分，

1={{x}|x

Z+}，

2={Z+}，求划分

1，2所确定的Z+上的等价关系。分析：等价关系和划分是两个不同的概念。等价关系是有序对的集合，而划分是子集的集合。但对于给定的集合A，A上的等价关系R和A的划分是一一对应的。即：<x,y>Rx和y在的同一划分块里。本题中，1的划分块都是单元集，没有含两个以上元素的划分块；第15页，课件共100页，创作于2023年2月例题选讲

2中只有一个划分块Z+，Z+包含了集合中的全体元素。∴R1就是Z+上的恒等关系；R2就是Z+上的全域关系。例5.对下面给定的集合A和B，构造从A到B的双射函数

分析：构造从集合A到B的双射函数，一般可采用下面的方法：(1)若A，B都是有穷集合，可以先用列元素的方法表示A，B第16页，课件共100页，创作于2023年2月例题选讲然后，顺序将A中的元素与B中的元素建立对应。(2)若A，B是实数区间，可以采用直线方程作为从A到B的双射函数。例如：A＝[1,2]，

B＝[2,6]是实数区间。先将A，B区间分别标记在直角坐标系的x轴和y轴上，过(1,2)和(2,6)两点的直线方程将A中的每个数映到B中的每一个数。因此，该直线方程：就是从A到B的双射函数。第17页，课件共100页，创作于2023年2月例题选讲这种通过直线方程构造双射函数的方法对任意两个同类型的实数区间(同为闭区间、开区间或半开半闭区间)都是适用的。此外，对于某些特殊的实数区间，可能选择其它严格单调的初等函数更方便。对于本题:(3)A是一个无穷集合，B是自然数集N只须将A中的元素排成一个有序序列，且指定这个序列的初始元素，这就叫做把A“良序化”。例如：构造从整数集Z到自然数集N的双射，如下排列：第18页，课件共100页，创作于2023年2月例题选讲

Z：0，-1，1，-2，2，-3，3，……. N：0，1，2，3，4，5，6，…….即：显然f是从Z到N的双射。第19页，课件共100页，创作于2023年2月3.4

例

题

选

解【例3.4.1】

设A、B为集合，已知A-B=B-A，证明：A=B。证明A-B=B-A

A∩～B=B∩～A

A∩～B∩B=B∩～A∩B

Φ=B∩～A

Φ=B-A

A

B①第20页，课件共100页，创作于2023年2月同理：A-B=B-A

A∩～B=B∩～A

A∩～B∩A=B∩～A∩A

A∩～B=Φ

A-B=Φ

B

A②由①、②可得：A=B

第21页，课件共100页，创作于2023年2月【例3.4.2】

设A、B为集合，证明：

P（A）∪P（B）P（A∪B）。并举例说明不能将“

”换成“=”。证明

x，x∈（P（A）∪P（B））

x∈P（A）∨x∈P（B）不妨设x∈P（A），则有{x}A{x}（A∪B），所以x∈P（A∪B），故P（A）∪P（B）P（A∪B）。第22页，课件共100页，创作于2023年2月例如，A={a,b}B={b,c}A∪B={a,b,c}，则P（A）={Φ,{a},{b},{a,b}},P(B)={Φ,{b},{c},{b,c}}P（A）∪P（B）={Φ,{a},{b},{c},{a,b},{b,c}}而P（A∪B）={Φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}}所以P（A）∪P（B）≠P（A∪B）。第23页，课件共100页，创作于2023年2月【例3.4.3】

设Ai是实数集合，它被定义为：则证明

（1）先证设则必存在某个自然数k，使x∈Ak，即则有x＜1，故x∈A0。所以第24页，课件共100页，创作于2023年2月（2）再证设x∈A0，即x＜1，故必有ε＞0，使x=1-ε，令则，即x∈Ak，所以故第25页，课件共100页，创作于2023年2月【例3.4.4】

证明（A-B）B=A∪B。证明

(A-B）B=（A∩～B）B

=（（A∩～B）-B）∪（B-（A∩～B））

=（A∩～B∩～B）∪（B∩～（A∩～B））

=（A∩～B）∪（B∩（～A∪B））

=（A∩～B）∪B=A∪B

第26页，课件共100页，创作于2023年2月习题三1．证明：如果B∈{{a}}，那么a∈B。2．试用描述法表示下列集合：(1)小于5的非负整数集合。(2)10与20之间的素数集合。(3)小于65的12的正倍数集合。(4）能被5整除的自然数的集合。第27页，课件共100页，创作于2023年2月3.选择适宜的客体域和谓词公式表示下列集合：(1)奇整数集合。(2)10的倍数集合。(3)永真式的集合。4．对任意元素a,b,c,d，证明：{{a},{a,b}}＝{{c}，{c，d}}当且仅当a=c且b=d第28页，课件共100页，创作于2023年2月5．"如果A∈B,B∈C，那么A∈C"对任意A,B,C都成立吗？都不成立吗？举例说明你的结论。6．列举出下列集合的元素：(1)S={x|x∈I(3＜x＜12)}，I为整数集合(2)S={x|x是十进制的数字}(3)S={x|(x=2)∨(x=5)}

第29页，课件共100页，创作于2023年2月7．下面命题的真值是否为真，说明理由。(1){a}{{a}}(2){a}∈{{a}}(3){a}∈{{a},a}(4){a}{{a},a}(5）(6）(7）(8）∈｛｝(9）对任意集合A，B，C，若A∈B，B

C则A∈C。(10）对任意集合A，B，C，若A∈B，B

C则A

C。(11）对任意集合A，B，C，若A

B，B∈C则A∈C。(12）对任意集合A，B，C，若A

B，B∈C则A

C。第30页，课件共100页，创作于2023年2月8．列举下列集合的所有子集:（1）｛｝（2）{1,{2,3}}(3){{1,{2,3}}}（4）｛｛｝｝(5){{1,2}{2,1,1},{2,1,1,2}}9．A、B、C均是集合，若A∩C=B∩C且A∪C=B∪C，则必有A=B。10.设A={a},求A的幂集P(A)以及A的幂集的幂集P(P(A))。11．设A、B、C、D为4个集合，已知A

B且C

D，证明：A∩C

B∩D。第31页，课件共100页，创作于2023年2月12．设A、B为集合，证明：

P（A）∩P（B）=P（A∩B）。13．证明定理3.2.3。14．设A、B、C为集合，证明：（A-B）-C=（A-C）-（B-C）。15．设A、B为集合，证明：（A-B）-C=A-（B∪C）。16．设A、B、C为集合，证明：（A∪B）-C=（A-C）∪（B-C）。17．证明：对任意集合A、B和C有，（A∩B）∪C=A∩（B∪C）的充分必要条件是C

A。第32页，课件共100页，创作于2023年2月18．设A、B、C是集合，若C

A，证明：（A∩B）∪C=A∩（B∪C）。19．设全集E={a，b，c，d，e，f，g}，子集A={a，b，d，e}，B={c，d，f，g}，C={c，e}，求下面集合：（1）～A∪～B（2）～（A

B）（3）（A∩B）∪（A∩C）第33页，课件共100页，创作于2023年2月20．设A，B是全集E的子集，已知～A～B，证明：B

A。21．设A、B为集合，且A

B，证明：～A∪B=E，其中E为全集。22．证明：（A-B）B=A∪B。23．设Bi是实数集合，它被定义为：证明：第34页，课件共100页，创作于2023年2月24．设某校有58个学生，其中15人会打篮球，20人会打排球，38人会踢足球，且其中只有3人同时会三种球，试求同时会两种球的学生共有几人。25．求1到500的整数中（1和500包含在内）分别满足以下条件的数的个数：（1）同时能被4，5和7整除。（2）不能被4和5，也不能被7整除。（3）可以被4整除，但不能被5和7整除。（4）可以被4或5整除，但不能被7整除。第35页，课件共100页，创作于2023年2月定理4.5.4对非空集合A上的关系R1、R2，则（1）r(R1)∪r(R2)=r(R1∪R2)（2）s(R1)∪s(R2)=s(R1∪R2)（3）t(R1)∪t(R2)t(R1∪R2)第36页，课件共100页，创作于2023年2月证明(1）和（2）的证明留作练习，下面仅证明（3）。因为R1∪R2

R1,由定理4.5.3知t(R1∪R2)t(R1)同理t(R1∪R2)t(R2)所以t(R1∪R2)t(R1)∪t(R2)第37页，课件共100页，创作于2023年2月4.11例

题

选

解【例4.11.1】证明：非空的对称、传递关系不可能是反自反关系。证明设R是集合A上的对称、传递关系，若R非空，则x，y∈A，有〈x,y〉∈R。由于R对称，因此〈y,x〉∈R，又由于R是传递的，因此〈x,x〉∈R。因此非空的对称、传递关系不可能是反自反关系。第38页，课件共100页，创作于2023年2月【例4.11.2】设R、S均是A上的等价关系，证明：R。S于A上等价iffS。R=R。S。证明""（先证必要性）

〈x,z〉

〈x,z〉∈S。R

y（〈x,y〉∈S∧〈y,z〉∈R）

y（〈z,y〉∈R∧〈y,x〉∈S）

(由于R、S均是对称的)

〈z,x〉∈R。S

〈x,z〉∈R。S(由于R。S于A上是对称的)故S。R=R。S。第39页，课件共100页，创作于2023年2月""（再证充分性）(1)x∈A，由于R、S均是自反的，因此〈x,x〉∈R且〈x,x〉∈S，所以〈x,x〉∈R。S，即R。S是自反的。(2)〈x,y〉

〈x,y〉∈R。S

t（〈x,t〉∈R∧〈t,y〉∈S）

t（〈t,x〉∈R∧〈y,t〉∈S）

(由于R、S均是对称的)

〈y,x〉∈S。R

〈y,x〉∈R。S(由于S。R=R。S)即R。S是对称的。第40页，课件共100页，创作于2023年2月(3)〈x,y〉，〈y,z〉

〈x,y〉∈R。S∧〈y,z〉∈R。S

〈x,y〉∈R。S∧〈y,z〉∈S。R(由于S。R=R。S)

〈x,z〉∈R。S。S。R

〈x,z〉∈R。(S。S)。R(关系的复合满足结合律)

〈x,z〉∈R。S。R（由于S传递，因此S。S

S）

〈x,z〉∈R。R。S（由于S。R=R。S)

〈x,z〉∈R。S（由于R传递，因此R。R

R）即R。S是传递的。第41页，课件共100页，创作于2023年2月【例4.11.3】设R、S均是A上的等价关系，证明：R∪S于A上等价iffR。S

R∪S且S。R

R∪S。证明""（先证必要性）

〈x,y〉∈R。S

t（〈x,t〉∈R∧〈t,y〉∈S）

t（〈x,t〉∈R∪S∧〈t,y〉∈R∪S）

〈x,y〉∈R∪S(由于R∪S传递)即R。S

R∪S。同理可证：S。R

R∪S。""（再证充分性）第42页，课件共100页，创作于2023年2月(1)x∈A，由于R、S均是自反的，因此〈x,x〉∈R且〈x,x〉∈S，所以〈x,x〉∈R∪S，即R∪S是自反的。(2)〈x,y〉

〈x,y〉∈R∪S〈x,y〉∈R∨〈x,y〉∈S

〈y,x〉∈R∨〈y,x〉∈S）

(由于R、S均是对称的)

〈y,x〉∈R∪S

即R∪S是对称的。第43页，课件共100页，创作于2023年2月【例4.11.4】设R、S均是非空集合A上的偏序关系，证明：R∩S也是A上的偏序关系。证明(1)x∈A，由于R、S均是自反的，因此有〈x,x〉∈R且〈x,x〉∈S，即〈x,x〉∈R∩S，故R∩S自反。(2)〈x,y〉∧x≠y

〈x,y〉∈R∩S〈x,y〉∈R∧〈x,y〉∈S

〈y,x〉R∧〈y,x〉S（由于R、S均是反对称的）

〈y,x〉R∩S

故R∩S反对称。第44页，课件共100页，创作于2023年2月(3)〈x,y〉，〈y,z〉

〈x,y〉∈(R∩S)∧〈y,z〉∈(R∩S)

(〈x,y〉∈R∧〈x,y〉∈S)∧(〈y,z〉∈R∧〈y,z〉∈S)

(〈x,y〉∈R∧〈y,z〉∈R)∧(〈x,y〉∈S∧〈y,z〉∈S)

〈x,z〉∈R∧〈x,z〉∈S（由于R、S均是传递的）

〈x,z〉∈R∩S

故R∩S传递。因此，R∩S也是偏序关系。第45页，课件共100页，创作于2023年2月【例4.11.5】A={a,b}上有多少不同的偏序关系？解因为偏序关系与哈斯图一一对应，所以只要画出所有不同的哈斯图，就可求出其不同的偏序关系，详见图4.11.1。所以该集合上共有3个不同的偏序关系。【例4.11.6】给出A={a,b,c}上既是等价关系又是偏序关系的R。

解R=IA

第46页，课件共100页，创作于2023年2月图4.11.1第47页，课件共100页，创作于2023年2月【例4.11.7】设A={1,2,3,4,5,6,9,24,54},R是A上的整除关系。(1)画出偏序关系R的

Hasse图。(2)求A关于R的极大元、极小元。(3)设B={2，3}，求B的上界和上确界。(4)找出〈A，R〉中的长度为4的反链。解（1）关系R的

Hasse图见图4.11.2。（2）A关于R的极大元：54，24，5；极小元：1，5。（3）B的上界：6，54，24；下界：1。（4）长度为4的反链：{4，5，6，9}。第48页，课件共100页，创作于2023年2月图4.11.2第49页，课件共100页，创作于2023年2月【例4.11.10】设f：A→B是函数，并定义一个函数g：B→P（A）。对于任意的b∈B，有

g（b）={x|（x∈A）∧（f（x）=b）}请证明：若f是A到B的满射，则g是B到P（A）的单射。证明对任意b1，b2∈B（b1≠b2），由于f是满射，因此a1，a2∈A，使得f（a1）=b1，f（a2）=b2。又由于b1∈b2且f是函数，因此a1≠a2。又g（b1）={x|（x∈A）∧(f（x）=b1）}g（b2）={x|（x∈A）∧（f（x）=b2）}第50页，课件共100页，创作于2023年2月因此有a1∈g（b1），a2(g（b2），但a1

g（b2），

a2g（b1），所以g（b1）≠g（b2），故g为单射。第51页，课件共100页，创作于2023年2月【例4.11.11】设X≠，R为XX上的关系，定义为

〈f,g〉∈R

Ranf=Rang

证明:R是XX上的等价关系，且存在双射φ：

XX/R→P（X）-{}.证明（1）①f∈XX，由于Ranf=Ranf，因此〈f,f〉∈R，即R是自反的。②〈f,g〉〈f,g〉∈R

Ranf=Rang

Rang=Ranf

〈g,f〉∈R即R是对称的。第52页，课件共100页，创作于2023年2月③〈f,g〉，〈g,h〉

〈f,g〉∈R∧〈g,h〉∈R(Ranf=

Rang)∧(Rang=Ranh)

Ranf=Ranh

〈f,h〉∈R

即R是传递的。综上，R是XX上的等价关系。第53页，课件共100页，创作于2023年2月（2）定义φ：XX/R→P（X）-{}：［f］R∈XX/R，φ（［f］R）=Ranf，于是φ（［f］R）=φ（［g］R）

Ranf=Rang

〈f,g〉∈R［f］R=［g］R

因而φ是单射。第54页，课件共100页，创作于2023年2月又A∈P（X）-{}，A

X，A≠，取定元素a∈A，定义f：X→X为则φ（［f］R）=Ranf=A，因而φ是满射。综上所述，存在双射φ：XX/R→P（X）-{}。第55页，课件共100页，创作于2023年2月【例4.11.12】设f：A→B，g：B→C是两个函数，证明：（1）若f。g是满射且g是单射，则f是满射。（2）若f。g是单射且g是满射，则f是单射。（注：这里函数的复合为右复合。）第56页，课件共100页，创作于2023年2月证明（1）b∈B，因为g是函数，所以存在c∈C，使得g（b）=c。由f。g是满射，对该元素c，存在a∈A，使得f。g（a）=c，即g（f（a））=c。由g（b）=c，所以g（f（a））=g（b）=c。由g是单射，所以有

f（a）=b。即b∈B，a∈A，使得f（a）=b。因此f是满射。第57页，课件共100页，创作于2023年2月（2）对任意b1，b2∈B（b1≠b2），由于f是单射，所以a1，a2∈A，使得f（a1）=b1，f（a2）=b2。由于b1≠b2且f是函数，所以a1≠a2。再由f。g是单射，可得

f。g（a1）≠f。g（a2），即

g（f（a1））≠g（f（a2）），所以g（b1）≠g（b2）。因此g是单射。第58页，课件共100页，创作于2023年2月【例4.11.13】设f：A→B是函数，并定义一个函数g：B→P（A）。对于任意的b∈B，有g（b）={x|（x∈A）∧（f（x）=b）}证明若f是A到B的满射，则g是B到P（A）的单射。证明如果f是A到B的满射，则对每个b∈B,至少存在一个a∈A,使f(a)=b,故g的定义域为B。第59页，课件共100页，创作于2023年2月若有b1,b2∈B,且b1≠b2,g(b1)={x|（x∈A）∧（f（x）=b1）}g（b2）={y|（y∈A）∧（f（y）=b2）}因为b1≠b2,f(x)≠f(y),而f是函数，故x≠y,所以g(b1)≠g(b2)。因此g是B到P（A）的单射。第60页，课件共100页，创作于2023年2月习题四1．已知A={},求P(A)×A。2．设A={1,2,3},R为实数集,请在笛卡儿平面上表示出A×R和R×A。3．以下各式是否对任意集合A，B，C，D均成立？试对成立的给出证明，对不成立的给出适当的反例。第61页，课件共100页，创作于2023年2月（1）(A-B)×C=(A×C)-(B×C)（2）(A∩B)×(C∩D)=(A×B)∩(C×D)（3）(A-B)×(C-D)＝(A×C)-(B×D)（4）(A∪B)×(C∪D)=(A×C)∪(B×D)第62页，课件共100页，创作于2023年2月4．设A,B,C,D为任意集合，求证：（1）若A

C，B

D，那么A×B

C×D。（2）若C,A×C

B×C，则A

B。（3）(A×B)-(C×D)＝((A-C)×B)∪(A×(B-D))。5．证明定理4.1.3中的（2）、（3）、（4）、（6）。6．证明定理4.1.4和定理4.1.5。第63页，课件共100页，创作于2023年2月7．给定集合A={1，2，3}，R，S均是A上的关系，R={〈1,2〉,〈2,1〉}∪IA，S={〈1,1〉,〈2,3〉}（1）画出R，S的关系图；（2）说明R，S所具有的性质；（3）求R

S。第64页，课件共100页，创作于2023年2月8．设A＝{0,1,2,3,4,5}，B={1,2,3}，用列举法描述下列关系，并作出它们的关系图及关系矩阵：（1）R1={〈x,y〉|x(A∩B∧y∈A∩B}（2）R2={〈x,y〉|x(A∧y∈B∧x=y2}（3）R3={〈x,y〉|x(A∧y∈A∧x+y=5}（4）R4={〈x,y〉|x(A∧y∈A∧k(x=k·y∧k∈N∧k＜2)}（5）R5={〈x,y〉|x(A∧y∈A∧(x=0∨2x＜3)}第65页，课件共100页，创作于2023年2月9．设R,S为集合A上任意关系，证明：（1）Dom(R∪S)=Dom(R)∪Dom(S)（2）Ran(R∩S)Ran(R)∩Ran(S)10．设A=｛1，2，3，4,5｝，A上关系

R=｛〈1，2〉，〈3，4〉，〈2，2〉｝,

S=｛〈4，2〉，〈2,5〉,〈3,1〉，〈1,3〉｝。试求R

S的关系矩阵。11．设A=｛1，2，3，4｝，A上关系

R＝｛〈1，4〉，〈3，1〉，〈3，2〉,〈4,3〉｝。求R的各次幂的关系矩阵。第66页，课件共100页，创作于2023年2月12．证明定理4.3.1中的（1）、（4）、（5）及（6）13．设A＝{a,b,c,d}，A上二元关系R1，R2分别为R1={〈b,b〉,〈b,c〉,〈c,a〉}R2={〈b,a〉,〈c,a〉,〈c,d〉,〈d,c〉}计算R1

R2，R2

R1，R2

1,R2

2。

第67页，课件共100页，创作于2023年2月14．设A={0，1，2，3}，R和S均是A上的二元关系:R={〈x，y〉|（y=x+1）∨（y=x/2）}S={〈x，y〉|（x=y+2）}（1）用列元素法表示R，S；（2）说明R，S所具有的性质；（3）求R

S。15．证明定理4.3.3中的（2）、（3）、（6）。第68页，课件共100页，创作于2023年2月16．设R1,R2,R3,R4,R5都是整数集上的关系，且xR1y|x-y|=1xR2y

x·y＜0xR3y

x|y(x整除y)xR4y

x+y=5xR5y

x=y

n(n是整数)请用T(True)和F(False)填写表4.1。

第69页，课件共100页，创作于2023年2月表4.1第70页，课件共100页，创作于2023年2月17．证明定理4.4.2和定理4.4.6。18．设A={0，1，2，3}，R

A×A且

R={〈x，y〉|x=y∨x(y∈A}。(1)画出R的关系图；(2)写出关系矩阵MR；(3)R具有什么性质？19．设A为一集合，|A|=n,试计算（1）A上有多少种不同的自反的（反自反的）二元关系（2）A上有多少种不同的对称的二元关系？（3）A上有多少种不同的反对称的二元关系？第71页，课件共100页，创作于2023年2月20．设R为A上的自反关系，证明：R是传递的iffR

R=R。并举例说明其逆不真。21．请判断下述的结论和理由正确吗？并说明理由。（1）如果R对称且传递，那么R必自反，因为由R对称可知xRy蕴涵yRx，而由R传递及xRy,yRx，可知xRx。（2）如果R反自反且传递，那么R必定是反对称的,因为若R对称可知xRy蕴涵yRx，而由R传递及xRy,yRx，可导出xRx,从而得到矛盾。第72页，课件共100页，创作于2023年2月22．证明：当关系R传递且自反时，R2＝R。23．设R、S、T均是集合A上的二元关系，证明：若R

S，则T

R

T

S。24．设R为集合A上任一关系，求证对一切正整数n有第73页，课件共100页，创作于2023年2月25．设R是集合A上的二元关系，R在A上是反传递的定义为：若〈x,y〉∈R,〈y,z〉∈R,则〈x,z〉R即x

y

z(xRy∧yRz→﹁xRz)。证明：R是反传递的，当且仅当（R

R）∩R=。第74页，课件共100页，创作于2023年2月26．证明定理4.5.1中的（2）。27．证明定理4.5.2中的（1）、（3）。28．证明定理4.5.3中的（1）、（2）。29．证明定理4.5.4中的（1）、（2）及对（3）t(R1∪R2)=t(R1)∪t(R2)举出反例。30．证明定理4.5.5中的（3）。第75页，课件共100页，创作于2023年2月31．设R是X={1,2,3,4，5}上的二元关系，R={〈1,2〉,〈2,1〉,〈1,5〉,〈5,1〉,〈2,5〉,〈5,2〉,〈3,4〉,〈4,3〉}∪IA。请给出关系矩阵并画出关系图；若R是等价关系，则求出等价类。32．若{{a,c,e},{b,d,f}}是集合A={a,b,c,d,e,f}的一个划分，求其等价关系R。33．若{{1，3，5}，{2，4}}是集合A={1,2,3,4,5}的一个划分，求其等价关系R。第76页，课件共100页，创作于2023年2月34．设S={1,2,3,4,5}且A=S×S,在A上定义关系R:〈a,b〉R〈a′,b′〉当且仅当ab′=a′b。（1）证明R是一个等价关系。（2）计算A/R。35．设R是集合A上的二元关系，R在A上是循环的充分必要条件是：若aRb并且bRc，则cRa。证明：R为等价关系当且仅当R是自反的和循环的。第77页，课件共100页，创作于2023年2月36．设R，S为A上的两个等价关系，且R

S。定义A/R上的关系R/S：〈［x］,［y］〉∈R/S当且仅当〈x,y〉∈S

证明：R/S为A/R上的等价关系。第78页，课件共100页，创作于2023年2月37．设{A1，Ａ

2,…，Am}为集合A的划分，证明：对任意集合B，{A1∩B，A2∩B，…，Am∩B}-{}必为集合A∩B的划分。38．设R1表示整数集上模m1相等关系，R2表示模

m2相等关系，π1，π2分别是R1，R2对应的划分。证明：π1细分于π2当且仅当m1是m

2的倍数。第79页，课件共100页，创作于2023年2月39．确定下面集合A上的关系R是不是偏序关系。（1）A=Z,aRb

a=2b

（2）A=Z,aRb

b2|a

（3）A=Z,aRb存在k使a=bk

（4）A=Z,aRb

a≤b

第80页，课件共100页，创作于2023年2月40．设A={a，b，c，d，e}，A上的偏序关系R={〈c,a〉,〈c,d〉}∪IA。(1)画出R的哈斯图；(2)(1)画出R的哈斯图；求A关于R的极大元和极小元。41．偏序集〈A，≤〉的哈斯图如图4.1所示。（1）用列举元素法求R；（2）求A关于R的最大元和最小元；（3）求子集{c，d，e}的上界和上确界；（4）求子集{a，b，c}的下界和下确界。第81页，课件共100页，创作于2023年2月图4.1第82页，课件共100页，创作于2023年2月图4.2第83页，课件共100页，创作于2023年2月42．图4.2为一偏序集〈A,R〉的哈斯图。（1）下列命题哪些为真？aRb，dRa，cRd，cRb，bRe，aRa，eRa；（2）画出R的关系图；（3）指出A的最大、最小元（如果有的话），极大、极小元；（4）求出子集B1={c,d,e},B2={b,c,d},B3={b,c,d,e}的上界、下界，上确界、下确界（如果有的话）。第84页，课件共100页，创作于2023年2月43．设R是集合A={a，b，c，d}上的偏序关系，关系矩阵为第85页，课件共100页，创作于2023年2月（1）写出R的表达式；（2）画出R的哈斯图；（3）求子集B={a，b}关于R的上界和上确界。44．对下列每一条件构造满足该条件的有限集和无限集各一个。（1）非空有序集，其中有子集没有最大元素。（2）非空有序集，其中有子集有下确界，但它没有最小元素。（3）非空有序集，其中有一子集存在上界，但它没有上确界。第86页，课件共100页，创作于2023年2月45．图4.3给出了集合S={a,b,c,d}上的四个关系图。请指出哪些是偏序关系图，哪些是全序关系图，哪些是良序关系图，并对偏序关系图画出对应的哈斯图。第87页，课件共100页，创作于2023年2月图4.3第88页，课件共100页，创作于2023年2月46．下列集合中哪些是偏序集合，哪些是全序集合，哪些是良序集合？（1）〈P(N),〉（2）〈P(N),〉（3）〈P{a},〉（4）〈P(),〉第89页，课件共100页，创作于2023年2月47．设R是集合S上的关系，S′S，定义S′上的关系R′为：R′＝R∩(S′×S′）。确定下述各断言的真假：（1）如果R传递，则R′传递。（2）如果R为偏序关系，则R′也是偏序关系。（3）如果〈S,R〉为全序集，则〈S′,R′〉也是全序集。（4）如果〈S,R〉为良序集，则〈S′,R′〉也是良序集。第90页，课件共100页，创作于2023年2月48．设〈A,≤〉为一有限全序集，|A|≥2，R是A×A上的关系，根据R下列各定义，确定〈A×A,R〉是否为偏序集、全序集或良序集。设x，y，u，v为A中任意元素。（1）〈x,y〉R〈u,v〉x≤u∧y≤v

（2）〈x,y〉R〈u,v〉x≤u∧x≠u∨(x=u∧y≤v)（3）〈x,y〉R〈u,v〉x≤u