离散数学期末考试试题及答案

,则a,b∈Ai,即b,a∈Ai,所以bRa,故R对称。Р"a,b,c∈A,若aRb 且bRc,则a,b∈Ai及b,c∈Aj。因为i≠j时Ai∩Aj=F,故i=j,即a,b,c∈Ai,所以aRc,故R传递。Р总之R是A上的等价关系。Р七、若f:A→B是双射,则f-1:B→A是双射(15分)。Р证明:对任意的x∈A,因为f是从A到B的函数,故存在y∈B,使<x,y>∈f,<y,x>∈f-1。所以,f-1是满射。Р对任意的x∈A,若存在y1,y2∈B,使得<y1,x>∈f-1且<y2,x>∈f-1,则有<x,y1>∈f且<x,y2>∈f。因为f是函数,则y1=y2。所以,f-1是单射。Р因此f-1是双射。Р八、设<G,*>是群,<A,*>和<B,*>是<G,*>的子群,证明:若A∪B=G,则A=G或B=G(10分)。Р证明假设A≠G且B≠G,则存在aÎA,aÏB,且存在bÎB,bÏA(否则对任意的aÎA,aÎB,从而AÍB,即A∪B=B,得B=G,矛盾。)Р对于元素a*bÎG,若a*bÎA,因A是子群,a-1ÎA,从而a-1 * (a*b)=b ÎA,所以矛盾,故a*bÏA。同理可证a*bÏB,综合有a*bÏA∪B=G。Р综上所述,假设不成立,得证A=G或B=G。Р九、若无向图G是不连通的,证明G的补图是连通的(10分)。Р证明设无向图G是不连通的,其k个连通分支为、、…、。任取结点、∈G,若和不在图G的同一个连通分支中,则[,]不是图G的边,因而[,]是图的边;若和在图G的同一个连通分支中,不妨设其在连通分支(1≤≤)中,在不同于的另一连通分支上取一结点,则[,]和[,]都不是图G的边,,因而[,]和[,]都是的边。综上可知,不管那种情况,和都是可达的。由和的任意性可知,是连通的。Р离散数学试题(B卷答案5)Р一、(10分)求命题公式Ø(P∧Q)«Ø(ØP®R)的主合取范式。