《离散数学习题集(十五套)》由会员分享，可在线阅读，更多相关《离散数学习题集(十五套)（80页珍藏版）》请在金锄头文库上搜索。
1、离散数学试题与答案试卷一一、填空 20% 每题2分1设 N：自然数集，E+ 正偶数 那么 。2A，B，C表示三个集合，文图中阴影局部的集合表达式为 A B C 。3设P，Q 的真值为0，R，S的真值为1，那么的真值= 。4公式的主合取范式为 。5假设解释I的论域D仅包含一个元素，那么 在I下真值为 。6设A=1，2，3，4，A上关系图为那么 R2 = 。7设A=a，b，c，d，其上偏序关系R的哈斯图为那么 R= 。8图的补图为 。9设A=a，b，c，d ，A上二元运算如下：*a b c dabcda b c db c d ac d a bd a b c那么代数系统的幺元是 ，有逆元的元素为 ，
2、它们的逆元分别为 。10以下图所示的偏序集中，是格的为 。 二、选择 20% 每题 2分1、以下是真命题的有A ； B；C ； D 。2、以下集合中相等的有 A4，3；B，3，4；C4，3，3；D 3，4。3、设A=1，2，3，那么A上的二元关系有 个。 A 23 ； B 32 ； C ； D 。4、设R，S是集合A上的关系，那么以下说法正确的选项是 A假设R，S 是自反的， 那么是自反的； B假设R，S 是反自反的， 那么是反自反的； C假设R，S 是对称的， 那么是对称的； D假设R，S 是传递的， 那么是传递的。5、设A=1，2，3，4，PAA的幂集上规定二元系如下那么PA/ R= AA
3、 ；BP(A) ；C1，1，2，1，2，3，1，2，3，4；D，2，2，3，2，3，4，A6、设A=，1，1，3，1，2，3那么A上包含关系“的哈斯图为 7、以下函数是双射的为 Af : IE , f (x) = 2x ； Bf : NNN, f (n) = ；Cf : RI , f (x) = x ； Df :IN, f (x) = | x | 。注：I整数集，E偶数集， N自然数集，R实数集8、图 中 从v1到v3长度为3 的通路有 条。A 0；B 1；C 2；D 3。9、以下图中既不是Eular图，也不是Hamilton图的图是 10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点
4、那么该树有 个4度结点。A1；B2；C3；D4 。三、证明 26%、 R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当 和在R中有在R中。8分、 f和g都是群到的同态映射，证明是的一个子群。其中C= (8分)、 G= (|V| = v，|E|=e ) 是每一个面至少由kk3条边围成的连通平面图，那么， 由此证明彼得森图Peterson图是非平面图。11分四、逻辑推演 16%用CP规那么证明下题每题 8分1、2、五、计算 18%1、设集合A=a，b，c，d上的关系R= , , , 用矩阵运算求出R的传递闭包t (R)。 9分2、如以下图所示的赋权图表示某七个城市及预先算出它们之间的一
5、些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。分试卷一答案：一、填空 20% 每题2分1、0，1，2，3，4，6； 2、；3、1； 4、； 5、1；6、, , , ；7、, IA ；8、9、a ；a , b , c ,d ；a , d , c , d ；10、c; 二、选择 20% 每题 2分题目12345678910答案C DB、CCADCADBA三、证明 26%1、 证：“ 假设由R对称性知，由R传递性得 “ 假设，有 任意 ，因假设 所以R是对称的。假设， 那么 即R是传递的。2、 证，有 ，又 是 的子群。3、 证：设G有r个面，那么，即 。而 故即得
6、。8分彼得森图为，这样不成立，所以彼得森图非平面图。3分 二、 逻辑推演 16%1、 证明：P附加前提TIPTITITIPTICP2、证明 P附加前提USPUSTIUGCP三、 计算 18%1、 解： ， ，t (R)= , , , , , , , , 2、 解： 用库斯克Kruskal算法求产生的最优树。算法略。结果如图：树权C(T)=23+1+4+9+3+17=57即为总造价。试卷二试题与答案一、填空 20% 每题2分1、 P：你努力，Q：你失败。“除非你努力，否那么你将失败的翻译为 ；“虽然你努力了，但还是失败了的翻译为 。2、论域D=1，2，指定谓词PP (1,1)P (1,2)P (
7、2,1)P (2,2)TTFF那么公式真值为 。2、 设S=a1 ，a2 ，a8，Bi是S的子集，那么由B31所表达的子集是 。3、 设A=2，3，4，5，6上的二元关系，那么R= 列举法。R的关系矩阵MR= 。5、设A=1，2，3，那么A上既不是对称的又不是反对称的关系R= ；A上既是对称的又是反对称的关系R= 。*a b cabca b cb b cc c b6、设代数系统，其中A=a，b，c,那么幺元是 ；是否有幂等 性 ；是否有对称性 。7、4阶群必是 群或 群。8、下面偏序格是分配格的是 。9、n个结点的无向完全图Kn的边数为 ，欧拉图的充要条件是 。10、公式的根树表示为 。二、选
8、择 20% 每题2分1、在下述公式中是重言式为 A；B；C； D。2、命题公式 中极小项的个数为 ，成真赋值的个数为 。A0； B1； C2； D3 。3、设，那么 有 个元素。A3； B6； C7； D8 。4、 设，定义上的等价关系那么由 R产 生的上一个划分共有 个分块。A4； B5； C6； D9 。5、设，S上关系R的关系图为那么R具有 性质。A自反性、对称性、传递性； B反自反性、反对称性；C反自反性、反对称性、传递性； D自反性 。6、设 为普通加法和乘法，那么 是域。A BC D= N 。7、下面偏序集 能构成格。8、在如下的有向图中，从V1到V4长度为3 的道路有 条。A1； B2； C3； D4 。9、在如下各图中 欧拉图。10、设R是实数集合，“为普通乘法，那么代数系统 是 。A群； B独异点； C半群 。三、证明 46%1、 设R是A上一个二元关系，试证明假设R是A上一个等价关系，那么S也是A上的一个等价关系。9分2、 用逻辑推理证明：所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。11分3、 假设是从A到B的函数，定义一个函数对任意有，证明：假设f是A到B的满射，那么g是从B到 的单射。10分
