第3章集合与关系上机练习答案

应用离散数学集合与关系PAGE杭电－周丽、方景龙第三章PAGE3第3章集合与关系上机练习编写下列程序并计算至少1个算例1．已知含n个元素的某集合的子集A和B，用位串表示法求A∪B，A∩B，Ac，A−B和AB。（1）程序代码defset_bit_operation(n,A_bits,B_bits):#全集掩码：n位全1full_mask=(1<<n)-1union=A_bits|B_bits#A∪Binter=A_bits&B_bits#A∩BcompA=full_mask^A_bits#A补集AcdiffAB=A_bits&(~B_bits)#A-BsymAB=A_bits^B_bits#对称差A⊕Bprint(f"全集位数n={n}")print(f"A={bin(A_bits)[2:].zfill(n)}")print(f"B={bin(B_bits)[2:].zfill(n)}")print(f"A∪B={bin(union)[2:].zfill(n)}")print(f"A∩B={bin(inter)[2:].zfill(n)}")print(f"A^c={bin(compA)[2:].zfill(n)}")print(f"A-B={bin(diffAB)[2:].zfill(n)}")print(f"A⊕B={bin(symAB)[2:].zfill(n)}")if__name__=="__main__":#示例：n=3，U={a0,a1,a2}#A={a0,a2}→101(2)=5;B={a1,a2}→110(2)=6n=3A=5B=6set_bit_operation(n,A,B)（2）测试算例全集位数n=3A=101B=110A∪B=111A∩B=100A^c=010A-B=001A⊕B=0112．已知含n个元素的某集合的子集A和B，用位串表示法判断是否有AB。（1）程序代码defis_subset(n,A,B):"""n:全集元素个数A,B:十进制整数（位串形式）returnTrue:A⊆B;False:A不包含于B"""if(A&B)==A:flag=Trueelse:flag=False#输出位串sA=bin(A)[2:].zfill(n)sB=bin(B)[2:].zfill(n)print(f"n={n}")print(f"A位串:{sA}")print(f"B位串:{sB}")ifflag:print("结论：A⊆B")else:print("结论：A⊈B")returnflagif__name__=='__main__':#测试1A⊆Bn=4A=3#0011B=11#1011is_subset(n,A,B)print("-"*20)#测试2不包含A2=5#0101B2=3#0011is_subset(n,A2,B2)（2）测试算例n=4A位串:0011B位串:1011结论：A⊆Bn=4A位串:0101B位串:0011结论：A⊈B修改n,A,B三个数值即可更换集合。3．已知含n个元素的某集合的子集A和B，用位串表示法判断是否有A=B。（1）程序代码defis_equal(n,A,B):#转为n位二进制字符串strA=bin(A)[2:].zfill(n)strB=bin(B)[2:].zfill(n)print(f"n={n}")print(f"A:{strA}")print(f"B:{strB}")ifA==B:print("判定：A=B")returnTrueelse:print("判定：A≠B")returnFalseif__name__=="__main__":#测试1：相等n=3A1=5#101B1=5is_equal(n,A1,B1)print("-"*20)#测试2：不等A2=5B2=6#110is_equal(n,A2,B2)（2）测试算例n=3A:101B:101判定：A=Bn=3A:101B:110判定：A≠B4．给定某有限集上的一个二元关系，求这个关系的逆关系。（1）程序代码definverse_relation(R):#逐个翻转有序对R_inv={(y,x)for(x,y)inR}returnR_invif__name__=="__main__":#给定原二元关系（集合形式）R={<1,2>,<1,3>,<2,3>,<3,1>}print("原关系R=",R)R_inv=inverse_relation(R)print("逆关系R⁻¹=",R_inv)（2）测试算例原关系R={<1,2>,<1,3>,<2,3>,<3,1>}逆关系R⁻¹={<2,1>,<3,1>,<3,2>,<1,3>}5．给定某有限集上的两个二元关系，求这两个关系的复合关系。（1）程序代码defrelation_composite(R,S):"""计算两个二元关系的复合关系R∘S:paramR:二元关系，集合/列表，元素为有序对(x,y):paramS:二元关系，集合/列表，元素为有序对(y,z):return:复合关系（集合）"""res=set()forx,midinR:formid2,zinS:ifmid==mid2:res.add((x,z))returnres#==========测试用例==========if__name__=="__main__":#测试用例1（课本经典例题）print("=====测试用例1=====")R1={(1,2),(2,3),(3,4)}S1={(2,1),(3,2),(4,3)}C1=relation_composite(R1,S1)print(f"R1={R1}")print(f"S1={S1}")print(f"R1∘S1={C1}\n")#测试用例2（含重复路径，验证自动去重）print("=====测试用例2=====")R2={(1,1),(1,2)}S2={(1,3),(2,3)}C2=relation_composite(R2,S2)print(f"R2={R2}")print(f"S2={S2}")print(f"R2∘S2={C2}")（2）测试算例=====测试用例1=====R1={(1,2),(2,3),(3,4)}S1={(2,1),(3,2),(4,3)}R1∘S1={(1,1),(2,2),(3,3)}=====测试用例2=====R2={(1,1),(1,2)}S2={(1,3),(2,3)}R2∘S2={(1,3)}6．给定有限集上二元关系的关系矩阵，确定这个关系是否是自反的或反自反的。（1）程序代码defjudge_reflex(matrix):"""根据关系矩阵判断二元关系的自反性、反自反性:parammatrix:二维列表，二元关系的关系矩阵（必须是方阵）:return:字符串，判定结果"""#第一步：校验是否为方阵n=len(matrix)forrowinmatrix:iflen(row)!=n:return"错误：输入不是n阶方阵，非法关系矩阵！"#第二步：遍历主对角线reflex=Trueanti_reflex=Trueforiinrange(n):val=matrix[i][i]ifval!=1:reflex=Falseifval!=0:anti_reflex=False#第三步：返回判定结论ifreflex:return"该关系是自反关系"elifanti_reflex:return"该关系是反自反关系"else:return"该关系既不自反，也不反自反"#==========多组测试用例==========if__name__=="__main__":#测试用例1：自反矩阵m1=[[1,1,0],[0,1,1],[1,0,1]]print("测试用例1：",judge_reflex(m1))#测试用例2：反自反矩阵m2=[[0,1],[1,0]]print("测试用例2：",judge_reflex(m2))#测试用例3：混合矩阵m3=[[1,0,1],[0,0,1],[1,1,1]]print("测试用例3：",judge_reflex(m3))#测试用例4：非方阵（非法输入）m4=[[1,0],[0]]print("测试用例4：",judge_reflex(m4))（2）测试算例测试用例1：该关系是自反关系测试用例2：该关系是反自反关系测试用例3：该关系既不自反，也不反自反测试用例4：错误：输入不是n阶方阵，非法关系矩阵！7．给定有限集上二元关系的关系矩阵，确定这个关系是否是对称的或反对称的。（1）程序代码defjudge_sym_antisym(matrix):"""根据关系矩阵判断二元关系的对称性、反对称性:parammatrix:二维列表，二元关系的n阶关系矩阵:return:判定结果字符串"""#校验是否为合法方阵n=len(matrix)forrowinmatrix:iflen(row)!=n:return"错误：输入不是n阶方阵，非法关系矩阵！"sym=Trueanti_sym=True#双重循环遍历矩阵所有元素foriinrange(n):forjinrange(n):#检查对称性ifmatrix[i][j]!=matrix[j][i]:sym=False#检查反对称性：i≠j时，禁止两侧同时为1ifi!=jandmatrix[i][j]==1andmatrix[j][i]==1:anti_sym=False#分类返回结果ifsymandanti_sym:return"既是对称关系，又是反对称关系"elifsym:return"是对称关系，不是反对称关系"elifanti_sym:return"是反对称关系，不是对称关系"else:return"既不是对称关系，也不是反对称关系"#==========多组测试用例==========if__name__=="__main__":#测试1：对称、非反对称m1=[[0,1,0],[1,0,1],[0,1,0]]print("测试用例1：",judge_sym_antisym(m1))#测试2：反对称、非对称m2=[[1,1,0],[0,0,1],[0,0,0]]print("测试用例2：",judge_sym_antisym(m2))#测试3：既是对称又是反对称（非对角线全0）m3=[[1,0,0],[0,0,0],[0,0,1]]print("测试用例3：",judge_sym_antisym(m3))#测试4：既不对称也不反对称m4=[[1,1,0],[0,0,1],[1,0,0]]print("测试用例4：",judge_sym_antisym(m4))#测试5：非法非方阵m5=[[1,0],[0]]print("测试用例5：",judge_sym_antisym(m5))（2）测试算例测试用例1：是对称关系，不是反对称关系测试用例2：是反对称关系，不是对称关系测试用例3：既是对称关系，又是反对称关系测试用例4：既不是对称关系，也不是反对称关系测试用例5：错误：输入不是n阶方阵，非法关系矩阵！8．给定有限集上二元关系的关系矩阵，确定这个关系是否是传递的。（1）程序代码defis_transitive_matrix(matrix):"""根据关系矩阵判断二元关系是否传递:parammatrix:二维列表，n阶关系矩阵:return:判定结果字符串"""n=len(matrix)#校验是否为方阵forrowinmatrix:iflen(row)!=n:return"错误：输入不是n阶方阵，非法关系矩阵！"#三重循环验证传递性定义foriinrange(n):forkinrange(n):forjinrange(n):ifmatrix[i][k]==1andmatrix[k][j]==1andmatrix[i][j]==0:return"该关系不是传递关系"return"该关系是传递关系"#==========多组测试用例==========if__name__=="__main__":#测试1：传递关系m1=[[1,0,1],[0,1,0],[0,0,1]]print("测试用例1：",is_transitive_matrix(m1))#测试2：非传递关系（存在传递反例）m2=[[0,1,0],[0,0,1],[0,0,0]]print("测试用例2：",is_transitive_matrix(m2))#测试3：空关系（全0矩阵，一定传递）m3=[[0,0],[0,0]]print("测试用例3：",is_transitive_matrix(m3))#测试4：恒等关系（仅对角线为1，一定传递）m4=[[1,0,0],[0,1,0],[0,0,1]]print("测试用例4：",is_transitive_matrix(m4))#测试5：非法非方阵m5=[[1,0],[0]]print("测试用例5：",is_transitive_matrix(m5))（2）测试算例测试用例1：该关系是传递关系测试用例2：该关系不是传递关系测试用例3：该关系是传递关系测试用例4：该关系是传递关系测试用例5：错误：输入不是n阶方阵，非法关系矩阵！9．给定一个正整数n，确定n元集合上传递关系的个数。（1）程序代码1（适合n<4）defis_transitive(matrix):"""判断n阶0-1矩阵是否对应传递关系"""n=len(matrix)foriinrange(n):forkinrange(n):forjinrange(n):#出现m_ik=1,m_kj=1但m_ij=0→不传递ifmatrix[i][k]==1andmatrix[k][j]==1andmatrix[i][j]==0:returnFalsereturnTruedefnum_to_matrix(num,n):"""将整数num转为n阶0-1关系矩阵（行优先）"""total_bits=n*n#转为二进制字符串，去掉前缀'0b'，左侧补0至total_bits位bin_str=bin(num)[2:].zfill(total_bits)mat=[]idx=0foriinrange(n):row=[]forjinrange(n):row.append(int(bin_str[idx]))idx+=1mat.append(row)returnmatdefcount_transitive_relations(n):"""统计n元集合上传递关系的个数"""ifn<1:return0total=0max_num=2**(n*n)#遍历所有可能的0-1矩阵fornuminrange(max_num):mat=num_to_matrix(num,n)ifis_transitive(mat):total+=1returntotal#==========主程序：交互输入+运行==========if__name__=="__main__":try:n=int(input("请输入正整数n（集合元素个数）："))ifn<=0:print("请输入大于0的正整数！")else:cnt=count_transitive_relations(n)print(f"{n}元集合上传递关系的总个数：{cnt}")exceptValueError:print("输入非法，请输入整数！")(2)程序代码2（适合n=4）defis_transitive(matrix):n=len(matrix)foriinrange(n):forkinrange(n):ifmatrix[i][k]==0:continue#m_ik=0，无需后续判断forjinrange(n):ifmatrix[k][j]==1andmatrix[i][j]==0:returnFalsereturnTruedefnum_to_matrix(num,n):total_bits=n*nbin_str=bin(num)[2:].zfill(total_bits)mat=[]idx=0foriinrange(n):row=[int(bin_str[idx+j])forjinrange(n)]idx+=nmat.append(row)returnmatdefcount_transitive_relations(n):ifn<1:return0total=0max_num=2**(n*n)fornuminrange(max_num):mat=num_to_matrix(num,n)ifis_transitive(mat):total+=1returntotalif__name__=="__main__":n=int(input("请输入正整数n："))res=count_transitive_relations(n)print(f"传递关系总数={res}")(3)测试算例请输入正整数n（集合元素个数）：11元集合上传递关系的总个数：2请输入正整数n（集合元素个数）：22元集合上传递关系的总个数：13请输入正整数n（集合元素个数）：33元集合上传递关系的总个数：171请输入正整数n（集合元素个数）：44元集合上传递关系的总个数：399410．给定一个正整数n，确定n元集合上等价关系的个数。（1）程序代码defcount_equivalence(n):"""计算n元集合上等价关系的个数（贝尔数）:paramn:正整数，集合元素个数:return:等价关系总数"""ifn<1:return1#空集#初始化二维数组dp[n+1][n+1]存放第二类斯特林数S(i,j)dp=[[0]*(n+1)for_inrange(n+1)]#边界条件foriinrange(1,n+1):dp[i][1]=1#划分为1个子集dp[i][i]=1#每个元素单独一个子集#递推计算斯特林数foriinrange(2,n+1):forkinrange(2,i):dp[i][k]=k*dp[i-1][k]+dp[i-1][k-1]#求和得到贝尔数bell=0forkinrange(1,n+1):bell+=dp[n][k]returnbell#批量测试标准用例if__name__=="__main__":test_n=[1,2,3,4,5,6,7]fornumintest_n:print(f"n={num}，等价关系个数：{count_equivalence(num)}")（2）测试算例n=1，等价关系个数：1n=2，等价关系个数：2n=3，等价关系个数：5n=4，等价关系个数：15n=5，等价关系个数：52n=6，等价关系个数：203n=7，等价关系个数：87711．给定有限集上二元关系的关系矩阵，求这个关系自反闭包的关系矩阵。（1）程序代码defget_reflex_closure(matrix):"""根据关系矩阵求解自反闭包的关系矩阵:parammatrix:二维列表，原二元关系的n阶关系矩阵:return:自反闭包矩阵；非方阵返回错误提示"""n=len(matrix)#校验是否为n阶方阵forrowinmatrix:iflen(row)!=n:return"错误：输入不是合法n阶方阵！"#深拷贝原矩阵，避免修改原数据closure=[row.copy()forrowinmatrix]#主对角线全部置1foriinrange(n):closure[i][i]=1returnclosure#==========多组测试用例==========if__name__=="__main__":#测试用例1：3阶矩阵（对角线不全为1）print("=====测试用例1=====")m1=[[0,1,1],[0,0,1],[1,0,0]]res1=get_reflex_closure(m1)forrowinm1:print(row)print("自反闭包：")forrowinres1:print(row)#测试用例2：2阶矩阵（原矩阵已是自反矩阵）print("\n=====测试用例2=====")m2=[[1,0],[1,1]]res2=get_reflex_closure(m2)forrowinm2:print(row)print("自反闭包：")forrowinres2:print(row)#测试用例3：非法非方阵print("\n=====测试用例3=====")m3=[[1,0],[0]]print(get_reflex_closure(m3))（2）测试算例=====测试用例1=====[0,1,1][0,0,1][1,0,0]自反闭包：[1,1,1][0,1,1][1,0,1]=====测试用例2=====[1,0][1,1]自反闭包：[1,0][1,1]=====测试用例3=====错误：输入不是合法n阶方阵！12．给定有限集上二元关系的关系矩阵，求这个关系对称闭包的关系矩阵。（1）程序代码defget_sym_closure(matrix):"""计算二元关系对称闭包的关系矩阵:parammatrix:原n阶关系矩阵（二维列表）:return:对称闭包矩阵；非方阵返回错误提示"""n=len(matrix)#校验是否为n阶方阵forrowinmatrix:iflen(row)!=n:return"错误：输入不是合法n阶方阵！"#第一步：构造转置矩阵mat_t=[[0]*nfor_inrange(n)]foriinrange(n):forjinrange(n):mat_t[i][j]=matrix[j][i]#第二步：布尔或运算，得到对称闭包closure=[[0]*nfor_inrange(n)]foriinrange(n):forjinrange(n):closure[i][j]=matrix[i][j]ormat_t[i][j]returnclosure#==========多组测试用例==========if__name__=="__main__":#测试用例1：原矩阵不对称print("=====测试用例1=====")m1=[[1,0,0],[1,0,0],[0,1,0]]res1=get_sym_closure(m1)print("原矩阵：")forrinm1:print(r)print("对称闭包：")forrinres1:print(r)#测试用例2：原矩阵本身就是对称矩阵（闭包=自身）print("\n=====测试用例2=====")m2=[[0,1,1],[1,1,0],[1,0,0]]res2=get_sym_closure(m2)print("原矩阵：")forrinm2:print(r)print("对称闭包：")forrinres2:print(r)#测试用例3：非法非方阵print("\n=====测试用例3=====")m3=[[1,0],[0]]print(get_sym_closure(m3))（2）测试算例=====测试用例1=====原矩阵：[1,0,0][1,0,0][0,1,0]对称闭包：[1,1,0][1,0,1][0,1,0]=====测试用例2=====原矩阵：[0,1,1][1,1,0][1,0,0]对称闭包：[0,1,1][1,1,0][1,0,0]=====测试用例3=====错误：输入不是合法n阶方阵！13．查找求解传递闭包的瓦舍尔算法的有关内容，然后用瓦舍尔算法找出下面集合{a,b,c,d,e}上关系的传递闭包。（1）{<a,c>,<b,d

>,<c,a>,<d,b>,<e,d

>}（2）{<b,c>,<b,e>,<c,e>,<d,a>,<e,b>,<e,c>}（3）{<a,b>,<a,c>,<a,e>,<b,a>,<b,c>,<c,a>,<c,b>,<d,a>,<e,d>}（1）程序代码defpairs_to_matrix(pairs,n):"""有序对集合→生成n阶初始关系矩阵:parampairs:下标形式的有序对列表，如[(0,2),(1,3)]:paramn:矩阵阶数（本题n=5）:return:0-1关系矩阵"""mat=[[0]*nfor_inrange(n)]fori,jinpairs:mat[i][j]=1returnmatdefwarshall(mat):"""Warshall算法：原地计算传递闭包矩阵:parammat:初始关系矩阵:return:传递闭包矩阵"""n=len(mat)#遍历每一个中间结点kforkinrange(n):#遍历所有起点iforiinrange(n):#遍历所有终点jforjinrange(n):#布尔更新：M[i][j]=M[i][j]or(M[i][k]andM[k][j])mat[i][j]=mat[i][j]or(mat[i][k]andmat[k][j])returnmatdefmatrix_to_pairs(mat,idx2elem):"""传递闭包矩阵→还原为原集合的有序对集合:parammat:传递闭包矩阵:paramidx2elem:下标→元素映射字典:return:有序对列表"""n=len(mat)res=[]foriinrange(n):forjinrange(n):ifmat[i][j]==1:res.append(f"<{idx2elem[i]},{idx2elem[j]}>")returnres#=====================全局配置=====================#下标→集合元素idx2elem={0:'a',1:'b',2:'c',3:'d',4:'e'}#元素→下标elem2idx={'a':0,'b':1,'c':2,'d':3,'e':4}n=5#集合元素个数，5阶矩阵#=====================求解三组关系=====================if__name__=="__main__":#==========(1)第一组关系==========print("=====（1）原关系：{<a,c>,<b,d>,<c,a>,<d,b>,<e,d>}=====")p1=[(0,2),(1,3),(2,0),(3,1),(4,3)]mat1=pairs_to_matrix(p1,n)closure1=warshall(mat1)print("传递闭包关系矩阵：")forrowinclosure1:print(row)pairs1=matrix_to_pairs(closure1,idx2elem)print("传递闭包有序对集合：")print("{"+",".join(pairs1)+"}\n")#==========(2)第二组关系==========print("=====（2）原关系：{<b,c>,<b,e>,<c,e>,<d,a>,<e,b>,<e,c>}=====")p2=[(1,2),(1,4),(2,4),(3,0),(4,1),(4,2)]mat2=pairs_to_matrix(p2,n)closure2=warshall(mat2)print("传递闭包关系矩阵：")forrowinclosure2:print(row)pairs2=matrix_to_pairs(closure2,idx2elem)print("传递闭包有序对集合：")print("{"+",".join(pairs2)+"}\n")#==========(3)第三组关系==========print("=====（3）原关系：{<a,b>,<a,c>,<a,e>,<b,a>,<b,c>,<c,a>,<c,b>,<d,a>,<e,d>}=====")p3=[(0,1),(0,2),(0,4),(1,0),(1,2),(2,0),(2,1),(3,0),(4,3)]mat3=pairs_to_matrix(p3,n)closure3=warshall(mat3)print("传递闭包关系矩阵：")forrowinclosure3:print(row)pairs3=matrix_to_pairs(closure3,idx2elem)print("传递闭包有序对集合：")print("{"+",".join(pairs3)+"}")（2）测试算例=====（1）原关系：{<a,c>,<b,d>,<c,a>,<d,b>,<e,d>}=====传递闭包关系矩阵：[1,0,1,0,0][0,1,0,1,0][1,0,1,0,0][0,1,0,1,0][0,1,0,1,1]传递闭包有序对集合：{<a,a>,<a,c>,<b,b>,<b,d>,<c,a>,<c,c>,<d,b>,<d,d>,<e,b>,<e,d>,<e,e>}=====（2）原关系：{<b,c>,<b,e>,<c,e>,<d,a>,<e,b>,<e,c>}=====传递闭包关系矩阵：[0,0,0,0,0][0,1,1,0,1][0,1,1,0,1][1,0,0,1,0][0,1,1,0,1]传递闭包有序对集合：{<a,a>,<b,b>,<b,c>,<b,e>,<c,b>,<c,c>,<c,e>,<d,a>,<d,d>,<e,b>,<e,c>,<e,e>}=====（3）原关系：{<a,b>,<a,c>,<a,e>,<b,a>,<b,c>,<c,a>,<c,b>,<d,a>,<e,d>}=====传递闭包关系矩阵：[1,1,1,1,1][1,1,1,1,1][1,1,1,1,1][1,1,1,1,1][1,1,1,1,1]传递闭包有序对集合：{<a,a>,<a,b>,<a,c>,<a,d>,<a,e>,<b,a>,<b,b>,<b,c>,<b,d>,<b,e>,<c,a>,<c,b>,<c,c>,<c,d>,<c,e>,<d,a>,<d,b>,<d,c>,<d,d>,<d,e>,<e,a>,<e,b>,<e,c>,<e,d>,<e,e>}14．设计一个算法，用它求解包含一个给定关系的最小等价关系，然后上机编程，给出算例。（1）算法设计算法EquivalenceClosure(M,n)//输入：n阶0-1关系矩阵M，集合元素个数n//输出：等价闭包矩阵M_eq//1.计算自反闭包MrMr←复制矩阵Mforifrom0ton-1:Mr[i][i]←1//2.计算对称闭包Mrs=Mr∨Mr^TMrT←矩阵转置(Mr)Mrs←新建n阶零矩阵forifrom0ton-1:forjfrom0ton-1:Mrs[i][j]←Mr[i][j]orMrT[i][j]//3.Warshall算法求传递闭包（最终等价闭包）M_eq←复制矩阵Mrsforkfrom0ton-1://中间结点kforifrom0ton-1://起点iforjfrom0ton-1://终点jM_eq[i][j]←M_eq[i][j]or(M_eq[i][k]andM_eq[k][j])returnM_eq（2）程序代码defpairs_to_matrix(pairs,n):"""有序对列表→n阶0-1关系矩阵"""mat=[[0]*nfor_inrange(n)]fori,jinpairs:mat[i][j]=1returnmatdefmatrix_transpose(mat):"""矩阵转置"""n=len(mat)t=[[0]*nfor_inrange(n)]foriinrange(n):forjinrange(n):t[i][j]=mat[j][i]returntdefmatrix_bool_or(a,b):"""两个同阶方阵做布尔或运算"""n=len(a)res=[[0]*nfor_inrange(n)]foriinrange(n):forjinrange(n):res[i][j]=1if(a[i][j]orb[i][j])else0returnresdefwarshall(mat):"""Warshall算法：求传递闭包矩阵"""n=len(mat)m=[row.copy()forrowinmat]forkinrange(n):foriinrange(n):forjinrange(n):m[i][j]=m[i][j]or(m[i][k]andm[k][j])returnmdefmatrix_to_pairs(mat,idx2elem):"""关系矩阵→还原为有序对集合"""n=len(mat)pairs=[]foriinrange(n):forjinrange(n):ifmat[i][j]==1:pairs.append(f"<{idx2elem[i]},{idx2elem[j]}>")returnpairsdefget_min_equivalence_relation(pairs,n,elem_map):"""核心函数：求包含给定关系的最小等价关系:parampairs:原关系有序对（下标形式）:paramn:集合元素个数:paramelem_map:下标→元素映射字典:return:等价闭包矩阵、等价闭包有序对"""#步骤1：原关系矩阵M=pairs_to_matrix(pairs,n)#步骤2：求自反闭包MrMr=[row.copy()forrowinM]foriinrange(n):Mr[i][i]=1#步骤3：求对称闭包Mrs=Mr∨Mr^TMrT=matrix_transpose(Mr)Mrs=matrix_bool_or(Mr,MrT)#步骤4：求传递闭包（最终等价闭包）M_eq=warshall(Mrs)#转换为有序对eq_pairs=matrix_to_pairs(M_eq,elem_map)returnM_eq,eq_pairs#=====================主程序入口=====================if__name__=="__main__":#通用调用模板：修改此处参数即可测试不同算例print("=====包含给定关系的最小等价关系求解程序=====")（3）算例测试统一规则：集合元素映射为下标，例如a↔0，b↔1，c↔2，d↔3，e↔4。算例1：基础二元集合（简单链关系）输入集合A={a,b}，原关系R={<a,b>}，元素映射：idx2elem={0:'a',1:'b'}，有序对下标形式：pairs=[(0,1)]（1）执行代码在主程序中追加以下代码：print("\n算例1：A={a,b},R={<a,b>}")n1=2idx2elem1={0:'a',1:'b'}pairs1=[(0,1)]mat_eq1,res_pairs1=get_min_equivalence_relation(pairs1,n1,idx2elem1)print("最小等价关系矩阵：")forrowinmat_eq1:print(row)print("最小等价关系有序对集合：")print("{"+",".join(res_pairs1)+"}")（2）测试结果算例1：A={a,b},R={<a,b>}最小等价关系矩阵：[1,1][1,1]最小等价关系有序对集合：{<a,a>,<a,b>,<b,a>,<b,b>}算例2：三元集合（链式关系）输入集合A={a,b,c}，原关系R={<a,b>,<b,c>}元素映射：idx2elem={0:'a',1:'b',2:'c'}，有序对：pairs=[(0,1),(1,2)]（1）执行代码在主程序中追加以下代码：print("\n算例2：A={a,b,c},R={<a,b>,<b,c>}")n2=3idx2elem2={0:'a',1:'b',2:'c'}pairs2=[(0,1),(1,2)]mat_eq2,res_pairs2=get_min_equivalence_relation(pairs2,n2,idx2elem2)print("最小等价关系矩阵：")forrowinmat_eq2:print(row)print("最小等价关系有序对集合：")print("{"+",".join(res_pairs2)+"}")（2）测试结果算例2：A={a,b,c},R={<a,b>,<b,c>}最小等价关系矩阵：[1,1,1][1,1,1][1,1,1]最小等价关系有序对集合：{<a,a>,<a,b>,<a,c>,<b,a>,<b,b>,<b,c>,<c,a>,<c,b>,<c,c>}算例3：五元集合（沿用之前Warshall例题）输入集合A={a,b,c,d,e}，原关系R={<a,c>,<b,d>,<c,a>,<d,b>,<e,d>}元素映射：idx2elem={0:'a',1:'b',2:'c',3:'d',4:'e'}有序对下标：pairs=[(0,2),(1,3),(2,0),(3,1),(4,3)]（1）执行代码在主程序中追加以下代码：print("\n算例3：A={a,b,c,d,e},R={<a,c>,<b,d>,<c,a>,<d,b>,<e,d>}")n3=5idx2elem3={0:'a',1:'b',2:'c',3:'d',4:'e'}pairs3=[(0,2),(1,3),(2,0),(3,1),(4,3)]mat_eq3,res_pairs3=get_min_equivalence_relation(pairs3,n3,idx2elem3)print("最小等价关系矩阵：")forrowinmat_eq3:print(row)print("最小等价关系有序对集合：")print("{"+",".join(res_pairs3)+"}")（2）测试结果[1,0,1,0,0][0,1,0,1,1][1,0,1,0,0][0,1,0,1,1][0,1,0,1,1]算例4：原关系本身就是等价关系（边界测试）输入集合A={a,b}，原关系已是等价关系：R={<a,a>,<b,b>,<a,b>,<b,a>}（1）执行代码在主程序中追加以下代码：print("\n算例4：原关系为等价关系")n4=2idx2elem4={0:'a',1:'b'}pairs4=[(0,0),(0,1),(1,0),(1,1)]mat_eq4,res_pairs4=get_min_equivalence_relation(pairs4,n4,idx2elem4)print("最小等价关系有序对集合：")print("{"+",".join(res_pairs4)+"}")（2）测试结果print("\n算例4：原关系为等价关系")n4=2idx2elem4={0:'a',1:'b'}pairs4=[(0,0),(0,1),(1,0),(1,1)]mat_eq4,res_pairs4=get_min_equivalence_relation(pairs4,n4,idx2elem4)print("最小等价关系有序对集合：")print("{"+",".join(res_pairs4)+"}")15．编程给出一个有5个元素的集合上的所有偏序。（1）程序代码defbuild_reflex_matrix(num,n=5):"""根据整数num生成n阶自反矩阵（对角线固定为1）:paramnum:整数，对应非对角线20位二进制取值:paramn:集合元素个数，本题固定n=5:return:5阶自反0-1矩阵"""mat=[[0]*nfor_inrange(n)]bit_idx=0#记录当前取到第几个二进制位#转为20位二进制字符串，左侧补0bin_str=bin(num)[2:].zfill(20)foriinrange(n):forjinrange(n):ifi==j:#自反：对角线强制置1mat[i][j]=1else:#非对角线依次填充二进制位mat[i][j]=int(bin_str[bit_idx])bit_idx+=1returnmatdefis_antisymmetric(mat):"""判断矩阵是否满足反对称性"""n=len(mat)foriinrange(n):forjinrange(n):ifi!=jandmat[i][j]==1andmat[j][i]==1:returnFalsereturnTruedefis_transitive(mat):"""判断矩阵是否满足传递性"""n=len(mat)foriinrange(n):forkinrange(n):ifmat[i][k]==0:continueforjinrange(n):ifmat[k][j]==1andmat[i][j]==0:returnFalsereturnTruedefmatrix_to_pairs(mat,idx2elem):"""关系矩阵转为有序对集合，方便直观展示"""n=len(mat)pairs=[]foriinrange(n):forjinrange(n):ifmat[i][j]==1:pairs.append(f"<{idx2elem[i]},{idx2elem[j]}>")returnpairsdeffind_all_posets(n=5):"""查找n元集合上所有偏序关系"""all_posets=[]total_bits=n*n-n#非对角线位数，n=5时为20max_num=2**total_bits#元素下标映射idx2elem={0:'a',1:'b',2:'c',3:'d',4:'e'}print(f"开始遍历，候选矩阵总数：{max_num}...")fornuminrange(max_num):#1.生成自反矩阵mat=build_reflex_matrix(num,n)#2.校验反对称ifnotis_antisymmetric(mat):continue#3.校验传递ifis_transitive(mat):all_posets.append(mat)returnall_posets,idx2elem#=====================主程序入口=====================if__name__=="__main__":#求解5元集合所有偏序poset_list,elem_map=find_all_posets(n=5)total=len(poset_list)#输出统计结果print("="*60)print(f"5元集合{{a,b,c,d,e}}上偏序关系总个数：{total}")print("="*60)#输出前10个偏序作为样例（全部4231个过长，仅展示典型）sample_cnt=10print(f"\n【展示前{sample_cnt}个偏序关系样例】\n")foridx,matinenumerate(poset_list[:sample_cnt],1):print(f"第{idx}个偏序")print("关系矩阵：")forrowinmat:print(row)#转换为有序对pairs=matrix_to_pairs(mat,elem_map)print("有序对集合：")print("{"+",".join(pairs)+"}\n")（2）测试算例开始遍历，候选矩阵总数：1048576...============================================================5元集合{a,b,c,d,e}上偏序关系总个数：4231============================================================16．给定一个有限偏序集，求这个偏序集的极小元、极大元、最小元和最大元。（1）算法设计算法FindExtremum(M,idx2elem)n←len(M)min_elems←空列表//极小元下标max_elems←空列表//极大元下标least←空列表//最小元下标greatest←空列表//最大元下标//查找极小元、极大元fori←0ton-1:is_min←Trueis_max←Trueforj←0ton-1:ifj≠iandM[j][i]=1:is_min←Falseifj≠iandM[i][j]=1:is_max←Falseifis_min:min_elems.append(i)ifis_max:max_elems.append(i)//查找最小元fori←0ton-1:flag←Trueforj←0ton-1:ifM[i][j]≠1:flag←Falsebreakifflag:least.append(i)//查找最大元fori←0ton-1:flag←Trueforj←0ton-1:ifM[j][i]≠1:flag←Falsebreakifflag:greatest.append(i)//下标转元素名res_min←[idx2elem[x]forxinmin_elems]res_max←[idx2elem[x]forxinmax_elems]res_least←[idx2elem[x]forxinleast]res_greatest←[idx2elem[x]forxingreatest]returnres_min,res_max,res_least,res_greatest（2）程序代码defget_extremum(mat,idx2elem):"""求解偏序集的极小元、极大元、最小元、最大元:parammat:偏序关系矩阵（n阶方阵）:paramidx2elem:下标->集合元素名称映射字典:return:极小元列表,极大元列表,最小元列表,最大元列表"""n=len(mat)min_indices=[]#极小元下标max_indices=[]#极大元下标least_idx=[]#最小元下标greatest_idx=[]#最大元下标#1.遍历所有元素，找极小元、极大元foriinrange(n):is_minimal=Trueis_maximal=Trueforjinrange(n):#判定极小元：存在j≠i且M[j][i]=1→不是极小元ifj!=iandmat[j][i]==1:is_minimal=False#判定极大元：存在j≠i且M[i][j]=1→不是极大元ifj!=iandmat[i][j]==1:is_maximal=Falseifis_minimal:min_indices.append(i)ifis_maximal:max_indices.append(i)#2.查找最小元：对所有j，M[i][j]==1foriinrange(n):is_least=Trueforjinrange(n):ifmat[i][j]!=1:is_least=Falsebreakifis_least:least_idx.append(i)#3.查找最大元：对所有j，M[j][i]==1foriinrange(n):is_greatest=Trueforjinrange(n):ifmat[j][i]!=1:is_greatest=Falsebreakifis_greatest:greatest_idx.append(i)#下标还原为元素名称min_elems=[idx2elem[k]forkinmin_indices]max_elems=[idx2elem[k]forkinmax_indices]le