离散数学试卷+答案.docx

一、 判断下列命题对错（每小题前标记或）（总20分）（）1.集合的交运算关于对称差运算满足分配律。（）2.对于集合A，AA=A。（）3.集合的差运算满足结合律。（）4.集合A上的关系都是自反的。（）5.若R,S都是A上的自反关系，则复合关系RS也是自反关系。（）6.若R1,R2都是A上的等价关系，则复合关系R1R2也是等价关系。（）7.合取范式都不是析取范式。（）8.命题的主析取范式不是唯一的。（）9.无向图的总度数是偶数。（）10.无回路的无向连通图称为树。二、 填空题题目（每空3分，总30分）1. 设集合A的阶数|A|=3，则幂集|P(A)|=_8_。2. 设A是全集E的子集，则AE=_A-E_。3. 若集合A=1,2,3,4,5,6,7,8，R是A上模为3的同余关系，则等价类1R=_1,4,7_，商集A/R=_1,4,7，2,5,8，3,6_。4. 偏序关系是指满足自反、反对称、传递的二元关系。5. 命题PQ的主合取范式是 PQ 。6. 有向连通图是欧拉图的充分必要条件是 图中每个顶点的入度和出度相等 。7. 设赋权图的顶点集是V=a,b,c,d,e,z，令T= b,c,d,e,z ，已知指标DT(b)=6，DT(c)=8，DT(d)=8，DT(e)=7，DT(z)=，则a到b的最短路长是_6_。8. 命题逻辑中，吸收律是指如下两个等价式：_ P(PQ) P_和_ P(PQ) P_。三、（10分）设集合A=1,2,3,4,6,8,12,16，R是A上的整除关系，证明R是A上的偏序关系并画出R的哈斯图。证明：R是A上的整除关系，即当a,bA，a能整除b时，(a,b) R。 易知a能整除a，得(a,a) R，即R是自反的二元关系； 易知(b,a) R，即R是反对称的二元关系； 当cA，c能整除a时，c也能整除b，即若(c,a) R，(a,b) R时，有(c,b) R，即R是传递的二元关系。故R是A上的偏序关系。四、（10分）证明下列推理：PR,PQ,QS,SPR解： QS P S P Q T PQ P QP T P T PR P R T PR T五、（10分）求(PQ)R的主析取范式和主合取范式。解：先列出(PQ)R的真值表：PQR(PQ)R00000011010101111000101111011111由表可知，(PQ)Rm001m010m011m101m101m110m111(PQ)RM000M100所以(PQ)R的主析取范式为：(PQR) (PQR)( PQR)( PQR)( PQR)( PQR)(PQ)R的主合取范式为：(PQR) (PQR)六、（10分）某单位有五个不同职位：b1,b2,b3,b4,b5，有四个申请者：a1,a2,a3,a4，他们想申请的职位分别是：a1(b2,b5)，a2(b1,b3)，a3(b1,b4)，a4(b3,b4)，如何安排他们的申请，才能使无职位的人最少？（要求利用匈牙利算法计算，初始对集取为M=a1b2,a2b3,a3b4）解： (b3) (b4) () (a2) (a4) (a4) (1)由于a4是唯一的不是M中的端点，把a4标记为()。(2)将a4的邻接点b3和b4标记(a4)。(3)从b3出发，把a2标记(b3)，从b4出发，把a3标记(b4)。(4)从a2出发，把b1标记为(a2)，因为b1已不是M中边的端点，说明已找到一条长通路a4b3a2b1。再用增长通路中不属于M的边代替属于M的边，于是可得匹配M=a1b2,a2b1,a3b4,a4b3如下图，由于V1中仅有4个顶点，所以M是最大匹配。七