搜索
北京工业大学2013——2014学年第一学期《离散数学》考试试卷A卷一、判断下列命题对错（每小题前标记√或×）（总20分）（）1.集合的交运算关于对称差运算满足分配律。（）2.对于集合A，A⨁A=A。（）3.集合的差运算满足结合律。（）4.集合A上的关系都是自反的。（）5.若R,S都是A上的自反关系，则复合关系R∘S也是自反关系。（）6.若𝑅1,𝑅2都是A上的等价关系，则复合关系𝑅1∘𝑅2也是等价关系。（×）7.合取范式都不是析取范式。（√）8.命题的主析取范式不是唯一的。（）9.无向图的总度数是偶数。（√）10.无回路的无向连通图称为树。二、填空题题目（每空3分，总30分）1.设集合A的阶数|A|=3，则幂集|P(A)|=_______。2.设A是全集E的子集，则A⨁E=_______。3.若集合A={1,2,3,4,5,6,7,8}，R是A上模为3的同余关系，则等价类[1]𝑅=_______，商集A/R=_______。4.偏序关系是指满足_______的二元关系。5.命题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的最短路长是_______。8.命题逻辑中，吸收律是指如下两个等价式：_______和_______。三、（10分）设集合A={1,2,3,4,6,8,12,16}，R是A上的整除关系，证明R是A上的偏序关系并画出R的哈斯图。四、（10分）证明下列推理：P→R,P⋁Q,Q→S,¬S⇒P⋀R五、（10分）求（PQ）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}）七、（10分）证明下列永真蕴含式：P⋀(P→Q)⇒Q(P∧(P→Q))→Q⇔(p∧(┐P∨Q))→Q⇔┐((P∧┐P)∨(P∧Q))∨Q⇔┐(F∨(P∧Q))∨Q⇔┐(P∧Q)∨Q⇔┐P∨┐Q∨Q⇔┐P∨T⇔T所以原式是永真式