离散数学试题与答案WORD

1、文档可能无法思考全面，请浏览后下载! 试卷二试题与参考答案一、填空1、 P：你努力，Q：你失败。2、 “除非你努力，否则你将失败”符号化为 ；“虽然你努力了，但还是失败了”符号化为 。2、论域D=1，2，指定谓词PP (1,1)P (1,2)P (2,1)P (2,2)TTFF则公式真值为 。3设A=2，3，4，5，6上的二元关系，则R= （列举法）。R的关系矩阵MR= 。4、设A=1，2，3，则A上既不是对称的又不是反对称的关系R= ；A上既是对称的又是反对称的关系R= 。5、设代数系统<A，*>，其中A=a，b，c,*a b cabca b cb b cc c b则幺元是 ；是

2、否有幂等 性 ；是否有对称性 。6、4阶群必是 群或 群。7、下面偏序格是分配格的是 。6 / 68、n个结点的无向完全图Kn的边数为 ，欧拉图的充要条件是 。二、选择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反自反性、反对称性、传递性；

3、 D自反性 。6、设 为普通加法和乘法，则（ ）是域。A BC D= N 。7、下面偏序集（ ）能构成格。8、在如下的有向图中，从V1到V4长度为3 的道路有（ ）条。A1； B2； C3； D4 。9、在如下各图中（ ）欧拉图。10、10、设R是实数集合，“”为普通乘法，则代数系统<R ，×> 是（ ）。A群； B独异点； C半群 。三、证明1、设R是A上一个二元关系，试证明若R是A上一个等价关系，则S也是A上的一个等价关系。2、 用逻辑推理证明：所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。3、若无向图G中只有两个奇数度结点，则这两个结点一定

4、连通。4、设G是具有n个结点的无向简单图，其边数，则G是Hamilton图。四、计算 1、设<Z6,+6>是一个群，这里+6是模6加法，Z6=0 ，1，2，3，4，5，试求出<Z6,+6>的所有子群及其相应左陪集。2、权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。试卷二参考答案：一、 填空 1、； 2、T 3、R=<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,

5、6>,<4,5>,<4,6>,<5,2>,<5,3>,<5,4>,<5,5>,<5,6>； 4、R=<1,2>,<1,3>,<2,1>；R=<1,1>,<2,2>,<3,3> 5、a ；否；有 6、Klein四元群；循环群 7、 B 8、；图中无奇度结点且连通二、选择 题目12345678910答案B、DD；DDBDABBBB、C三、证明1、（1） S自反的，由R自反，（2） S对称的（3） S传递的由（1）、（2）、（3）得；S是等

6、价关系。2、证明：设P(x)：x 是个舞蹈者； Q(x) ：x很有风度； S(x)：x是个学生； a：王华上述句子符号化为：前提：、 结论： 3分前提引入前提引入US化简 假言推理I化简合取EG11分、证明 ：。4、证明：设G中两奇数度结点分别为u 和v，若 u，v不连通，则G至少有两个连通分支G1、G2 ，使得u和v分别属于G1和G2，于是G1和G2中各含有1个奇数度结点，这与图论基本定理矛盾，因而u，v一定连通。5、证明： 证G中任何两结点之和不小于n。反证法：若存在两结点u，v 不相邻且,令，则G-V1是具有n-2个结点的简单图，它的边数,可得，这与G1=G-V1为n-2个结点为简单图的题设矛盾，因而G中任何两个相邻的结点度数和不少于n。所以G为Hamilton图.四、 计算 解：子群有<0,+6>；<0,3,+6>；<0,2,4,+6>；<Z6