离散数学试题与答案

离散数学试题与答案Tag内容描述：<p>1、离散数学复习资料_试卷_习题与答案离散数学总复习资料一、鸽笼原理与容斥原理1求证边长为1的正方形中放9个点，由这些点构成的三角形中，必有一个三角形面积小于。证：把该正方形均分成四个相同的小正方形，则由鸽笼原理知，必有一个小正方形内存在三个点，且这三个点构成的三角形面积小于。#2对一列个不同整数，任意排列，证明一定存在长为的上升子序列或下降子序列。证：设此序列为：，从开始上升子序列最长的长度为，下降子序列最长的长度为，每一个都对应了。若不存在长为的上升子序列或下降子序列，那么，形如的不同点对至多有个，而。</p><p>2、离散试卷及答案离散数学总复习资料一、鸽笼原理与容斥原理1求证边长为1的正方形中放9个点，由这些点构成的三角形中，必有一个三角形面积小于。证：把该正方形均分成四个相同的小正方形，则由鸽笼原理知，必有一个小正方形内存在三个点，且这三个点构成的三角形面积小于。#2对一列个不同整数，任意排列，证明一定存在长为的上升子序列或下降子序列。证：设此序列为：，从开始上升子序列最长的长度为，下降子序列最长的长度为，每一个都对应了。若不存在长为的上升子序列或下降子序列，那么，形如的不同点对至多有个，而有个，则由鸽笼原理。</p><p>3、编号题目答案题型分值大纲区分度1下列是真命题的有（）A、 ； B、；C、； D、 。答：C选择题2122下面命题公式（ ）不是重言式。A、； B、；C、； D、。答：C选择题22.133命题“没有不犯错误的人”符号化为（ ）。设是人，犯错误。A、； B、；C、； D、。答：D选择题23.134对自然数集合N，哪种运算不是可结合的，运算定义为任（ ）。A、； B、；C、； D、。答：B选择题28.135任意具有多个等幂元的半群，它（ ）。A、不能构成群； B、不一定能构成群；C、不能构成交换群；。</p><p>4、离散数学试题及答案一、填空题 1 设集合A,B，其中A1,2,3, B= 1,2, 则A - B____________________; r(A) - r(B) __________________________ .2. 设有限集合A, |A| = n, 则 |r(AA)| = __________________________.3. 设集合A = a, b, B = 1, 2, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________.4. 已知命题公式G(PQ)R，则G的主析取范式是_________________________________________________________________________________________.5.设G是完全二叉树，G有7个点，其中4个叶点，则。</p><p>5、离散数学题库与答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？(A)(1)Q=QP (2)Q=PQ (3)P=PQ (4)P(PQ)=P 答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别）2、下列公式中哪些是永真式？( )(1)(PQ)(QR) (2)P(QQ) (3)(PQ)P (4)P(PQ)答：（2），（3），（4） 可用蕴含等值式证明3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=PQ (2) PQ=P (3) PQ=PQ (4)P(PQ)=Q (5) (PQ)=P (6) P(PQ)=P答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都。</p><p>6、编号题目答案题型分值大纲难度1谓词公式x(P(x) $yR(y)Q(x)中量词x的辖域是（ ）。答：P(x) $yR(y)填空题23.132令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（ ）。答：x(R(x)Q(x)填空题23.133一棵无向树的顶点数n与边数m关系是()。答：m=n-1填空题27.134一个图的欧拉回路是一条通过图中( )的回路。答：所有边一次且恰好一次填空题26.435有n个结点的树，其结点度数之和是()。答：2n-2填空题26.436设T是一棵树，则T是一个连通且( )图。答：简单无回路填空题26.237任一有向图中，度数为奇数的结点有()个。</p><p>7、离散数学试题与答案试卷一一、填空 20% （每小题2分）1设 （N：自然数集，E+ 正偶数） 则 。2A，B，C表示三个集合，文图中阴影部分的集合表达式为 A BC。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的哈斯图为。</p>