离散数学试题与答案

试卷二试题与参考答案一、填空1、 P：你努力， Q：你失败。2、 “除非你努力，否则你将失败”符号化为；“虽然你努力了，但还是失败了”符号化为。2、论域 D=1，2 ，指定谓词 PP (1,1)P (1,2)P (2,1)P (2,2)TTFF则公式x yP( y, x) 真值为。3 设 A=2， 3， 4， 5， 6 上的二元关系 R x, y | xy x是质数 ，则R=（列举法）。R 的关系矩阵RM=。4、设 A=1 ，2，3 ，则 A 上既不是对称的又不是反对称的关系R=；A 上既是对称的又是反对称的关系R=。5、设代数系统 ，其中 A=a ， b，c,*abcaabcbbbccccb则幺元是；是否有幂等性；是否有对称性。6、 4 阶群必是群或群。7、下面偏序格是分配格的是。8、 n 个结点的无向完全图Kn 的边数为，欧拉图的充要条件是。二、选择1、在下述公式中是重言式为（）A (P Q)(PQ) ； B ( PQ )( P Q) (QP) ；C (PQ)Q ； D P (P Q) 。2、命题公式(PQ )( Q P)中极小项的个数为（），成真赋值的个数为（）。A 0；B 1；C 2；D 3 。3、设 S ,1,1,2 ，则2 S有（）个元素。A3； B 6； C 7； D 8 。4、设 S 1,2, 3 ，定义 SS上的等价关系R a,b, c, d | a,bSS, c, dS S, a d b c 则由 R产 生的 SS上一个划分共有（）个分块。A4； B 5； C 6； D 9 。5、设 S 1, 2, 3 ， S 上关系 R 的关系图为则 R 具有（）性质。A自反性、对称性、传递性；B反自反性、反对称性；C反自反性、反对称性、传递性；D 自反性 。6、设, 为普通加法和乘法，则（） S, ,是域。A S x | x a b 3 , a,b Q B S x | x 2n , a, b ZC S x | x 2n 1, n ZD S x | x Z x 0 = N 。7、下面偏序集（）能构成格。8、在如下的有向图中，从V1 到 V4 长度为 3 的道路有（）条。A1；B 2；C 3；D 4 。9、在如下各图中（）欧拉图。10、10、设 R 是实数集合， “”为普通乘法，则代数系统 是（）。A群；B独异点；C 半群。三、证明1、设 R 是 A 上一个二元关系，Sa, b| (a,bA)(对于某一个cA, 有a,cR且c, bR)试证明若R是A 上一个等价关系，则S 也是A 上的一个等价关系。2、 用逻辑推理证明：所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。3、若无向图G中只有两个奇数度结点，则这两个结点一定连通。m1 ( n 1)(n 2)24、设 G是具有 n 个结点的无向简单图，其边数2，则 G是 Hamilton图。四、计算1、设 是一个群，这里+6 是模 6 加法， Z6=0 ，1 ， 2 ， 3 ， 4 ， 5，试求出的所有子群及其相应左陪集。2、权数 1， 4， 9， 16， 25， 36， 49， 64， 81， 100 构造一棵最优二叉树。试卷二参考答案：一、 填空1、PQ ； P Q2、 T3、 R=,；11111111110001111111000004、 R=,；R=,5、 a ；否；有6、 Klein四元群；循环群7、 B1 n(n1)8、 2；图中无奇度结点且连通二、选择题目12345678910答案B、 DD； DDBDABBBB、 C三、 明1、（ 1）S 自反的a A，由 R 自反，( a, aR)( a, aR) ，a, aS（ 2）S 称的a, bAa, bS( a,cR)( c,bR)S 定义(a, cR) (c, bR)R 对称b, aSR 传递（ 3）S 的a, b, cAa, bSb, cS(a, dR)(d , bR) (b, eR)(e, cR)(a, bR)(b, cR)R 传递a, cSS 定义由（ 1）、（ 2）、（3）得； S 是等价关系。2、 明： P(x) ： x 是个舞蹈者；Q(x)： x 很有 度；S(x) ：x 是个学生；a ：王 上述句子符号化 ：前提： x(P( x)Q( x) 、 S(a) P(a) ： x(S(x) Q (x) 3 分 S( a) P(a)前提引入 x(P( x)Q( x)前提引入 P( a)Q(a) US P(a)化 Q( a).假言推理 I S( a)化 S( a) Q(a)合取 x(S(x)Q (x) EG 11 分、 明：b1 , b2B ,(b1 b2 )f 满射a1 , a2 A使f ( a1 )b1 , f (a2 )b2 , 且 f (a1 )f (a2 ), 由于 f是函数 ,a1a2又 g (b1 ) x | (xA) ( f ( x) b1 ),g(b2 ) x | ( xA)( f (x)b2 )a1 g(b1 ), a2g(b2 )但 a1 g(b2 ), a2g(b1 )g(b1 )g(b2 )由b1 , b2 任意性知 , g为单射 。4、证明：设 G中两奇数度结点分别为u 和 v，若 u ， v 不连通，则G至少有两个连通分支G1、G2 ，使得 u 和 v 分别属于 G1 和 G2，于是 G1 和 G2 中各含有1 个奇数度结点，这与图论基本定理矛盾，因而 u， v 一定连通。5、证明：证 G中任何两结点之和不小于n。反证法： 若存在两结点u，v 不相邻且 d(u)d (v)n1, 令 V1 u, v ，则 G-V1 是具有 n-2 个 结 点 的 简 单 图 ， 它 的 边 数m 1 (n 1)( n 2) 2 ( n 1)2, 可 得m1 (n 2)(n 3)12，这与11G中G=G-V 为 n-2 个结点为简单图的题设矛盾，因而任何两个相邻的结点度数和不少于n。所以 G为 Hamilton图.四、计算解：子群有 ； ； 6660的左陪集： 0， 1 ； 2， 3； 4， 50， 3的左陪集： 0 ，3； 1 ， 4 ； 2， 50， 2， 4 的左陪集： 0， 2， 4；1 ， 3 ， 5Z 的左陪集： Z 。66