离散数学试卷答案

《离散数学试卷答案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一、判断下列命题对错(每小题前标记丿或X)(总20分)(V)1.集合的交运算关于对称差运算满足分配律。(X)2.对于集合A,A©A=Ao(X)3.集合的差运算满足结合律。(X)4.集合A上的关系都是自反的。(V)5.若R,S都是A上的自反关系，则复合关系RoS也是自反关系。(X)6.若都是A上的等价关系，则复合关系R^R2也是等价关系。(X)7.合取范式都不是析取范式。(X)8.命题的主析取范式不是唯一的。(V)9.无向图的总度数是偶数。(V)10.无回路的无向连通图称为树。二、填空题题目(每空3分，总30分)1.设

2、集合A的阶数

3、A

4、=3,则幕集IP(A)1=802.设A是全集E的子集，则A©E=_A1E_O3.若集合A二{1,2,3,4,567,8},R是A上模为3的同余关系，贝9等价类⑴严{1,4刀商集A/R二{{1,4,7},{2,5,8},{3,6}}。4.偏序关系是指满足自反、反对称、传递的二元关系。5.命题PtQ的主合取范式是-.PV0。6.有向连通图是欧拉图的充分必要条件是图中每个顶点的入度和出度相等。7.设赋权图的顶点集是V={a,b,c/d/e,z},令T二{b,c,d,e,z},已知指标DT(b)=6,DT(

5、c)=8,DT(d)=8,DT(e)=7,DT(z)=oo,则a到b的最短路长是_6。8.命题逻辑屮，吸收律是指如下两个等价式：PV(P/Q)=>P和PA(PVQ)=>P。三、(10分)设集合A二{1,2346&12J6},R是A上的整除关系，证明R是A上的偏序关系并画出R的哈斯图。证明：R是A上的整除关系，即当a,bGA,a能整除b时，(a,b)GRO易知a能整除a,得(a,a)eR,即R是自反的二元关系；易知(b,a)GR,即R是反对称的二元关系；当cWA,c能整除a时,c也能整除b,即若(c,a)6R,(a,

6、b)GR时，有(c,b)6R,即R是传递的二元关系。故R是A上的偏序关系。四、(20分)证明下列推理:PTR,PVQ,QTS,iSnP/R解①②③④⑤⑥⑦⑧⑨QtSPsP-»QT①②PVQPiQtPT④PT③⑤PtRPRT⑥⑦PART⑥⑧五、(10分)求(P・Q)tR的主析取范式和主合取范式。解：先列出(P・Q)tR的真值表：PQR(P—Q)tR00000011010101111000101111011111rfl表可知，(P・Q)tRomooiVmoioVmonVmjoiVmioiVmnoVmm(PiQ)tRqM

7、000VM100所以(P—Q)tR的主析取范式为：(iPAiQAR)V(-nPAQA-iR)V(-nPAQAR)V(PA-nQARlVfPAQA-iR)V(PAQAR)(P・Q)tR的主合取范式为：(PVQVR)A(^PVQVR)六、(10分)某单位有五个不同职位：bl,b2,b3,b4zb5,有四个申请者：al,a2,a3,a4,他们想申请的职位分别是：al(b2,b5),a2(bl,b3),a3(bl,b4),a4(b3,b4),如何安排他们的申请,才能使无职位的人最少？(要求利用匈牙利算法计算，初始对集取为M=

8、{alb2,a2b3,a3b4})解：(b3)(b4)(0)(a2)(a4)(a4)⑴由于a4是唯一的不是M中的端点，把a4标记为(0)。(2)将a4的邻接点b3和b4标记(a4)。(3)从b3出发,把a2标记(b3),从b4出发,把a3标记(b4)。⑷从a2出发，把bl标记为(a2),因为bl己不是M中边的端点，说明己找到一条长通路a4b3a2bl。再用增长通路中不属于M的边代替属于M的边，于是可得匹配M=alb2,a2bl,a3b4,a4b3｝如下图，由于％屮仅有4个顶点，所以M堤最大匹配。blb2b3b4七、(

9、10分)证明下列永真蕴含式：PA(PtQ)=Q证明：(PA(PTQ))TQ0(PA(-iPVQ))TQ0(OV(PAQ))-Q<=>-.PV-.QVQ由此可见(P/(PTQ))TQ是永真式，即P/(PtQ)=>Q。证毕。