判断下列命题对错（每小题前标记√或×）（总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分）设集合A的阶数|A|=3，则幂集|P(A)|=___8___。设A是全集E的子集，则A⨁E=__A-E__。若集合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}}__。偏序关系是指满足自反、反对称、传递的二元关系。命题P→Q的主合取范式是¬P⋁Q。有向连通图是欧拉图的充分必要条件是图中每个顶点的入度和出度相等。设赋权图的顶点集是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___。命题逻辑中，吸收律是指如下两个等价式：_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⇒P⋀R解：Q→SPSP¬QT①②P⋁QP¬Q→PT④PT③⑤P→RPRT⑥⑦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)⋀(¬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标记为(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。证毕。
本文档为【离散数学试卷+答案】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483