离散数学试题与答案

1、试卷二试题与参考答案填空1、P:你努力，Q:你失败。2、“除非你努力，否则你将失败”符号化为;“虽然你努力了，但还是失败了”符号化为2、论域D=1，2，指定谓词PP(1,1)P(1,2)P(2,1)P(2,2)TTFF贝U公式xyP（y,x）真值为。3设A=2,3,4,5,6上的二元关系Rx,y|xyX是质数，则R=（列举法）。R的关系矩阵MR=4、设A=1,2,3，则A上既不是对称的又不是反对称的关系R=A上既是对称的又是反对称的关系R=。5、设代数系统A,*，其中A=a,b,c,*abcaabcbbbccccb则幺元是;是否有幕等性;是否有对称性6、4阶群必是群或群。7、下面偏序格是分配格

2、的是。CA)的（C）、选择1、在下述公式中是重言式为（）A(PQ)(PQ);B.(PQ)(PQ)(QP）;C.(PQ)Q.D.P(PQ)。2、命题公式(PQ)(QP)中极小项的个数为（）,成真赋值的个数为（）。A0;B.1|;C.2;D.3。3、设S，1，1,2，则2s有（）个元素。A.3;B.6;C.7;D.8。4、设S1,2,3,定义SS上的等价关系Ra,b,c,dIa,bSS,c,dSS,adbc则由R产生的SS上一个划分共有（）个分块。A.4;5、设S1,2,3,S上关系则R具有（R的关系图为BA.自反性、对称性、传递性;反自反性、反对称性;6、设-为普通加法和乘法，则（)S,是域。A

3、.Sx|xab3a,bQB.Sx|x2n,a,bZC.Sx|x2n1,nZd.Sx|xZx0=N7、下面偏序集（）能构成格。C.反自反性、反对称性、传递性;.自反性。DO8、在如下的有向图中，从Vi到V4长度为3的道路有(【D)条。A.1;B.4。)欧拉图。IDa是（)。”为普通乘法，则代数系统10、10、设R是实数集合,A.群；B.独异点；C.半群。三、证明1、设R是A上一个二元关系,Sa,b|(a,bA)(对于某一个cA,有a,cR且c,bR)试证明若R是A上一个等价关系，则S也是A上的一个等价关系。2、用逻辑推理证明：所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度

4、。3、若无向图G中只有两个奇数度结点，则这两个结点一定连通。1m(n1)(n2)24、设G是具有n个结点的无向简单图，其边数2，则G是Hamilton图。四、计算1设以,+6是一个群，这里+6是模6加法，Z6=0,1，,3,4,5，试求出Z6,+6的所有子群及其相应左陪集。2、权数1，4，9，16，25,36,49,64,81，100构造一棵最优二叉树。试卷二参考答案:一、填空1、PQ；PQ2、T3、R=,；11111111110001111111000004、R=,；R=,5、a;否；有6、Klein四元群；循环群、选择7、B题目12345678910答案B、DD;DDBDABBBB、C】n

5、(n1)8、2;图中无奇度结点且连通三、证明1、(1)S自反的aA，由R自反，(a,aR)(a,aR)，a,a(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(P(x)Q(x) P(a)Q(a) P(a) Q(a

6、). S(a) S(a)Q(a) x(S(x)Q(x)S(a)P(a)结论:前提引入前提引入US化简假言推理I化简合取EGx(S(x)Q(x)3分11分3、证明R,b2B,gb2)f满射ai,a2使f(3!)d,f(a2)b2,且f(ajf),由于f是函数,又g(bjx|(xA)(f(x)bj,g2)x|(xA)(f(x)b?)aig(bj,a?gd)但a!g(b2),a?g(bjg(bjg(b2)由bi,b2任意性知，g为单射。4、证明：设G中两奇数度结点分别为u和v，若u,v不连通，则G至少有两个连通分支G、G,使得u和v分别属于G和G,于是G和Ga中各含有1个奇数度结点，这与图论基本定理矛盾，因而u,v一定连通。5、证明：证G中任何两结点之和不小于n。反证法：若存在两结点u,v不相邻且d(u)d(v)n1,令Mu，v，则g-v是具1m-(n1)(n2)2(n1)有n-2个结点的简单图，它的边数2,可得1m-(n2)(n3)12，这与G=G-V1为n-2个结点为简单图的题设矛盾，因而G中任何两个相