离散数学试卷+答案.docx

《离散数学试卷+答案.docx》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、A

3、=3，则幂集

4、P(A)

5、=___8___

6、。2.设A是全集E的子集，则A⨁E=__A-E__。3.若集合A={1,2,3,4,5,6,7,8}，R是A上模为3的同余关系，则等价类[1]R=_{1,4,7}__，商集A/R=__{{1,4,7}，{2,5,8}，{3,6}}__。4.偏序关系是指满足自反、反对称、传递的二元关系。5.命题P→Q的主合取范式是¬P⋁Q。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_

7、__。8.命题逻辑中，吸收律是指如下两个等价式：_P⋁(P⋀Q)⇒P__和_P⋀(P⋁Q)⇒P__。三、（10分）设集合A={1,2,3,4,6,8,12,16}，R是A上的整除关系，证明R是A上的偏序关系并画出R的哈斯图。证明：R是A上的整除关系，即当a,b∈A，a能整除b时，(a,b)∈R。易知a能整除a，得(a,a)∈R，即R是自反的二元关系；易知(b,a)∉R，即R是反对称的二元关系；当c∈A，c能整除a时，c也能整除b，即若(c,a)∈R，(a,b)∈R时，有(c,b)∈R，即R是传递的二元关系。故R是A上的偏序关系。四、（10分）证明下列推理：P→R,P⋁Q,Q→S,¬S⇒

8、P⋀R解：①Q→SP②SP③¬QT①②④P⋁QP⑤¬Q→PT④⑥PT③⑤⑦P→RP⑧RT⑥⑦⑨P⋀RT⑥⑧五、（10分）求(P⟷Q)→R的主析取范式和主合取范式。解：先列出(P⟷Q)→R的真值表：PQR(P⟷Q)→R00000011010101111000101111011111由表可知，(P⟷Q)→R⟺m001⋁m010⋁m011⋁m101⋁m101⋁m110⋁m111(P⟷Q)→R⟺M000⋁M100所以(P⟷Q)→R的主析取范式为：(¬P⋀¬Q⋀R)⋁(¬P⋀Q⋀¬R)⋁(¬P⋀Q⋀R)⋁(P⋀¬Q⋀R)⋁(P⋀Q⋀¬R)⋁(P⋀Q⋀R)(P⟷Q)→R的主合取范式为：(P⋁Q⋁R

9、)⋀(¬P⋁Q⋁R)六、（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

10、标记为(a2)，因为b1已不是M中边的端点，说明已找到一条长通路a4b3a2b1。再用增长通路中不属于M的边代替属于M的边，于是可得匹配M’={a1b2,a2b1,a3b4,a4b3}如下图，由于V1中仅有4个顶点，所以M’是最大匹配。七、（10分）证明下列永真蕴含式：P⋀(P→Q)⇒Q证明：(P⋀P→Q)→Q⟺(P⋀¬P⋁Q)→Q⟺0⋁P⋀Q→Q⟺¬P⋁¬Q⋁Q⟺1由此可见(P⋀P→Q)→Q是永真式，即P⋀(P→Q)⇒Q。证毕。