【定理3.8.1】设A=?A1，A2，…，Ar?与B=?B1，B2，…，Bs?是C的两种划分，则集合X=?Ai∩Bj|i=1,…,r，j=1,…,s，Ai∩Bj≠??也是C的划分。证明:⑴先证Ai∩Bj?C由A，B是C的划分知，Ai?C，Bj?C，所以Ai∩Bj?C。第三章：集合与关系第94页，共139页，星期日，2025年，2月5日⑵再证:(A1∩B1)∪(A1∩B2)∪…∪(A1∩Bs)∪(A2∩B1)∪(A2∩B2)∪…∪(A2∩Bs)∪…(Ar∩B1)∪(Ar∩B2)∪…∪(Ar∩Bs)=(A1∩(B1∪B2∪…∪Bs))∪…∪(Ar∩(B1∪B2∪…∪Bs))=(A1∪A2∪…∪Ar)∩(B1∪B2∪…∪Bs)=C∩C=C第三章：集合与关系第95页，共139页，星期日，2025年，2月5日⑶最后证X中的元素是两两互不相交的。在X中取任意两个不同元素，Ai∩Bh与Aj∩Bk，分三种情况讨论：①设i≠j，h=k(Ai∩Bh)∩(Aj∩Bk)=(Ai∩Aj)∩(Bh∩Bk)=?∩(Bh∩Bk)=?②设i≠j，h≠k(Ai∩Bh)∩(Aj∩Bk)=(Ai∩Aj)∩(Bh∩Bk)=?∩?=?③设i=j，h≠k(Ai∩Bh)∩(Aj∩Bk)=(Ai∩Aj)∩(Bh∩Bk)=(Ai∩Aj)∩?=?第三章：集合与关系第96页，共139页，星期日，2025年，2月5日【定义3.8.3】定理3.8.1中定义的集合X叫做原来两种划分A和B的交叉划分。【定义3.8.4】设A=?A1，A2，…，Ar?与B=?B1，B2，…，Bs?是C的两种划分，如果?Ai?A，?Bk?B，使得Ai?Bk。则称A是B的加细，也称A是B的细分。【定理3.8.2】任何两种划分的交叉划分都是原来两种划分的一种加细。证明：设A=?A1，A2，…，Ar?与B=?B1，B2，…，Bs?是C的两种划分。X=?Ai∩Bj|i=1,…,r，j=1,…,s，Ai∩Bj≠??是A和B的交叉划分。因为Ai∩Bj?Ai，Ai∩Bj?Bj，所以X是A的一种加细，也是B的一种加细。第三章：集合与关系第97页，共139页，星期日，2025年，2月5日§3.9等价关系与等价类等价关系是最重要、最常见的二元关系之一。它有良好的性质。在计算机科学和计算机技术、信息科学和信息工程中都有广泛的应用。目前对等价关系的研究是深入而完备的。本节介绍等价关系的主要结论。【定义3.9.1】设R?X×X，如果R是自反的，对称的和传递的，则称R是X上的等价关系。设R是等价关系，若?x,y??R，称x等价于y。因为等价关系是自反的和对称的，所以等价关系的关系矩阵主对角线全为1且是对称阵；其关系图每一个结点上都有自回路且每两个结点间如果有边，一定有方向相反的两条边。第三章：集合与关系第98页，共139页，星期日，2025年，2月5日【定义】设R是A上的二元关系，n为自然数，R的n次幂记为Rn，定义为：⑴R0=IA⑵Rn+1=Rn°R由该定义可以看出，A上的任何二元关系的0次幂都相等，等于A上的恒等关系IA。由该定义还可以看出：R1=R0°R=IA°R=RR2=R1°R=R°RR3=R2°R=(R°R)°R……因为复合运算满足结合律，所以R3又可以写成：R3=R°R°R同样的道理Rn也可以写成：Rn=第三章：集合与关系第62页，共139页，星期日，2025年，2月5日例如,在【例3.6.1】中R2=R°R=??1,2?,?2,2??