《离散数学》习题1B

1B第1页共8页一、单选题（20小题，每小题2分，共40分）得分1、设，则有（）个元素。A．3；B．6；C．7；D．82、下列等价式不成立的是（）.A．;B．C．D．3、谓词公式中量词（）辖域是（）．A． B．C． D．4、设={1，2，3}，上的二元关系=，则的对称闭包是（）．A． B． C． D．5、下面哪一种图不一定是树（）．A．无圈连通图；B．有个结点条边的无圈图；C．每对结点间都有路的图；D．无圈但增加一条边，就得到一个且仅有一个圈．6、任何无向图G中结点间的连通关系是（）。A.良序关系 B.偏序关系C.全序关系 D.等价关系7、谓词演算中，是的有效结论，其理论依据是（）．A．全称指定规则（US）C．全称推广规则（UG）B．存在指定规则（ES）D．存在推广规则（EG）．8、设是图的邻接矩阵，，则为（）．A．结点的度数；B．结点的度数；C．结点的入度；D．图中由到长度为的路径的条数．9、下列等价公式正确的是（）。A．；B．；C．；D．．10、设是正实数集，Ｒ是实数集，ｆ：ｆ，则ｆ是（）．A．是入射不是满射 B．是满射不是入射C．既非入射也非满射 D．是双射11、具有个结点的完全图是欧拉图，则为()。A．偶数；B．奇数；C．9；D．10．12、下列哪个命题是假命题（）．A．如果2+2=4，则太阳从东方升起；B．如果2+2=4，则太阳从西方升起；C．如果2+24，则太阳从东方升起；D．如果2+24，则太阳从西方升起．13、集合上的等价关系，其等价类的集合｛｝称为（）．A．与的并集，记为∪ B．与的交集，记为∩C．与的商集，记为／ D．与的差集，记为－．14、下列各图是欧拉图的是（）．15、设A为一非空集合，则上的真包含关系不具有的性质是()A．自反性B．反自反性C．反对称性D．可传递性16、设N为自然数集，：NN，则是()．A．是入射不是满射 B．既非入射也非满射C．是满射不是入射 D．是双射17、，其中，为集合的对称差运算，则方程的解为（）。A．；B．；C．；D．18、n阶完全图的边数为（）。A．n(n-1)/2；B．n-1；C．n+1；D．2n(n-1)19、给定命题公式：（PQ）（PR），与之等价的是（）A．P（QR）B．P（QR）C．P（QR）D．P（QR）20、若集合的基数为4，则集合上的共有（）个不同的等价关系．A．15B．16C．14D．12二、填空题（20小题，每空1分，共20分）得分1、设A为任一集合，则．2、完全图K5的边数是。3、设是A到B的函数，若使是B到A的函数，必须满足4、设个体域，消去公式中的量词，则∧。5、设,则的双射共有．6、在偏序集中，，≤是上的整除关系，则的最大元是7、设是集合上的具有自反性、对称性、反对称性和传递性的二元关系，则的关系矩阵是。8、设是图的邻接矩阵，，则图中由到长度为的路径的条数为．9、写出下表中所定义的命题联结词00011011011110、设，上的二元关系=，则具有性。11、设上的关系的关系图如下，从关系图可知具有的性质是．12、设表示“我将去书店”，表示“我有时间”，则命题“我将去书店，仅当我有时间”符号化为。13、设T是具有n个结点的一棵完全二元树，则T中树叶数为14、设命题公式的真值表为00000101001110010111011100101100则命题公式的主析取范式为。15、一棵有9个叶结点的完全三叉树，有个内点．16、设集合，R和S均为A上的二元关系，且，则_17、公式的真值表中共有种真值指派。18、设,则=．其中表示集合的幂集．19、在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除关系，则集合={2,3,4,6}的最大元是20、对谓词公式（（x）P（x）（y）Q（y））（x）R（x）中约束变元应用变换规则所得到的前束范式是三、简答题（4小题，每小题6分，共24分）得分1、下图给出的赋权图表示七个城市及架起城市间直接通讯线路的预测造价，试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小造价。2、以给定权2，4，5，8，13，15，18，25构造一棵最优二叉树．3、设集合A={a,b,c,d,e}上的偏序关系“”={}，画出偏序关系“”的哈斯图。4、对有向图，通过邻接矩阵解下列问题：（1）从到长度为4的路有几条？（2）中长度为3的回路有几条？四、证明题（2小题，