重慶大學(xué)離散數(shù)學(xué)第3次1答案

1、作業(yè) 試卷總分:100 得分:100 一、填空題(共 (共 10 道試題,共 30 分) 1.設(shè)是非零實(shí)數(shù)乘法群，f:GG是同態(tài)映射，f(x)=1/x，則f(G)=_，Ker(f)=_。 答案:G；12.在一階謂詞邏輯中，將命題“沒有不能表示成分?jǐn)?shù)的有理數(shù)”符號化為_(設(shè)F(x):x是有理數(shù)；G(x):x能表示成分?jǐn)?shù)。) 答案:?x(F(x)?G(x)或?x(F(x)G(x)3.設(shè)A是素?cái)?shù)集合，B是奇數(shù)集合，則A-B=_。 答案:24.給定一個序列集合1，01，10，11，001，000，若去掉其中的元素_，則該序列集合構(gòu)成前綴碼。 答案:15.令a,b表示實(shí)數(shù)的閉區(qū)間，即a,b=x|axb，

2、f:0,1a,b定義為：f(x)=(b-a)x+a，則這個映射是_映射。 答案:雙射6.若解釋I的論域D僅包含一個元素，則圖在I下真值為_。 答案:17.邏輯學(xué)是一門研究_及_的科學(xué)。 答案:思維形式、思維規(guī)律8.設(shè)A=a，b，c，d，其上偏序關(guān)系R的哈斯圖為圖則 R=_ 。 答案: （a，a），（b，b），（c，c），（d，d），（a，b），（b，a），（c，d），（d，c） 9.設(shè)圖，定義A上的二元運(yùn)算為普通乘法、除法和加法，則代數(shù)系統(tǒng)中運(yùn)算*關(guān)于 _運(yùn)算具有封閉性。 答案: 乘法和除法 10.若PQ的值為0，則P的值為_，Q的值為_。 答案:假，假二、簡答題(共 (共 6 道試題,共 3

3、0 分) 1.將命題符號化：李強(qiáng)比王飛高。 答案:符號化為B(c,d)，其中，c：李強(qiáng)，d：表示王飛，B(x,y)：比高”。2.下列集合中，哪些是映射？并求映射的定義域和值域。 （1）S 1 =1,2,3?,2,3,4?,3,1,4?,4,1,4? （2）S 2 =1,2,3?,2,3,4?,3,3,2? （3）S 3 =1,2,3?,1,2,4?,2,3,4? （4）S 4 =1,2,3?,2,2,3?,3,2,3? 答案:（1）是映射。domS 1 =1,2,3,4，R S1 =, （2）是映射。domS 2 =1,2,3，R S2 =, （3）不是映射。 （4）是映射。domS 4 =1

4、,2,3，R S4 =3.設(shè)是一個群，這里+ 6 是模6加法，Z 6 =0 ，1，2，3，4，5，試求出的所有子群及其相應(yīng)左陪集。 答案: 4.設(shè)x=0,1,2,y=A,B,C,z=,，若有f:xY,g:YZ，其中， f=,g=a,，求(gf) -1 和f -1 g -1 。 答案:對任意2有a e(go(A)ax(xEA Agof(x)-z)naxxEAAay(yEXAf(x)-yAg(y)sz)-33r(xeAA yerAf(x)-yAg(y)-z)aay(yef(A)Ag(y)=a)ezeg(A)所以(go)(4)=g(r(A):5.給定兩個圖G1，G2（如下圖所示）： （1）試判斷它們

5、是否為歐拉圖、漢密爾頓圖？并說明理由。 （2）若是歐拉圖，請寫出一條歐拉回路。 圖 答案:（1）圖G1是歐拉圖。 因?yàn)閳DG1中每個結(jié)點(diǎn)的度數(shù)都是偶數(shù)。 圖G2是漢密爾頓圖。 因?yàn)閳DG2存在一條漢密爾頓回路（不惟一）： a(a, b)b(b, e) e(e, f) f (f, g) g(g, d) d(d, c) c(c, a)a （2）圖G1的歐拉回路為：（不惟一）： v1(v1, v2) v2 (v2, v3) v3 (v3, v4) v4 (v4, v5)v5 (v5, v2) v2 (v2, v6)v6 (v6, v4) v4 (v4, v1)v16.設(shè)R為實(shí)數(shù)集合，對xR，有f(x)=

6、x+2, g(x)=x-2 , h(x)=3x，求gf , hg, (hg)f與h(gf) 答案:gf=|xR hg=xR (hg)f=xR h(gf)=|xR 所以有h(gf)=(hg)f 。三、證明題(共 (共 4 道試題,共 40 分) 1.圖 答案: 2.G為n階無向簡單圖，邊數(shù)m=(n-1)(n-2)/2+2，證明G是漢密爾頓圖。 答案:證明：根據(jù)漢密頓圖的判別條件，在無向簡單圖G=中，若能找到u,v兩個頂點(diǎn)，使得deg(u)+deg(v)=|V| ，則G是哈密頓圖。 在該題中，|v|=n，首先，所有頂點(diǎn)的度數(shù)之和為： 2E=(n-1)(n-2)+4=n*n-3*n+6 其次，在該圖

7、中，任意去掉兩個頂點(diǎn)u和v后，一個有(n-2)個頂點(diǎn)的無向完全圖來說，共有(n-2)(n-3)/2條邊，即一個有(n-2)個頂點(diǎn)的無向圖中所有點(diǎn)的度數(shù)之和最大為(n-2)(n-3)=n*n-5n+6，所以，與頂點(diǎn)u和v相關(guān)的邊的度數(shù)之和大于等于(n*n-3n+6)-(n*n-5n+6)=2n，即deg(u)+deg(v)=n。所以G是哈密頓圖。3.設(shè)A和B是全集E的子集，利用運(yùn)算律證明：B(AB) A)=E。 答案:B(AB) A) =B(A A) (BA) (分配律) =B(?(BA) (互補(bǔ)律) =B(BA) (同一律) =B(BA) (德?摩根律) =(BB)A (結(jié)合律) =EA (互補(bǔ)律) =E4.證明K 3,3 圖不是平面圖。 答案: