上海海事大學(xué)2011年1月離散數(shù)學(xué)期末考試題

1、-裝 訂 線-上 海 海 事 大 學(xué) 試 卷2010 2011 學(xué)年第一學(xué)期期末考試 離散數(shù)學(xué) （A卷）班級 學(xué)號 姓名 總分 題 目得 分閱卷人1.(5)2.(6)在150位學(xué)生中，有109位同學(xué)在PASCAL,BASIC,C+中至少學(xué)習(xí)一門。假設(shè)45人學(xué)BASIC，61人學(xué)PASCAL，53人學(xué)C+，18人學(xué)BASIC和PASCAL，15人學(xué)BASIC和C+，23人學(xué)PASCAL和C+。(a)多少人三門語言都學(xué)？(b)多少人只學(xué)BASIC?(c)多少人一門都不學(xué)？3.(5)已知前提為：結(jié)論為：給出邏輯推理的過程。4.(6)設(shè)B=1,2,3,4,5，A=BB,定義A上的關(guān)系R如下：(u,v)

2、R(x,y)當(dāng)且僅當(dāng)u-v=x-y.(a) 證明R是等價關(guān)系。(b) 找出(2,3).(c) 計算A/R.5.(6)設(shè)定義f:ST如下：(a) 證明f是單射的。(b) 證明f是滿射的。(c) f有反函數(shù)嗎？若有的話，求出反函數(shù)。(d) 寫出的表達(dá)式和他的定義域和值域。(e) 是單射的嗎？說明原因。6.(5)設(shè)A=a,b,c,d且A上的關(guān)系R的矩陣如下(a) 證明R是偏序關(guān)系。(b) 畫出R的哈斯圖。7.(6)設(shè)D105代表正整數(shù)105的所有正約數(shù)的集合上由整除關(guān)系構(gòu)成的格。(a) 畫出此格的哈斯圖。(b) 寫出每個元素的補(bǔ)元素(c) 此格是否布爾代數(shù)？寫出它的原子集合。8.(6)布爾函數(shù)的真值

3、表如下：xyzf(x,y,z)00000010010101101001101111011110寫出f對應(yīng)的析取范式并盡量化簡。9.(5)完成下表使得二元運(yùn)算滿足交換律和冪等率。*abcacbcb10.(5)設(shè)G是一個群，幺元是e. 證明若G中存在x使得x2=x，則x=e.11.(5)設(shè)f是G1到G2的滿同態(tài)，G2是阿貝爾群。證明ker(f)包含了G1中所有形式為的元素，其中a,b是G1中的任意元素。12.(6)設(shè)S=1,-1,i,-i,且G=(S,普通復(fù)數(shù)乘法)(a) 證明H=1，-1是G的子群。(b) 確定H的所有左陪集。(c) 證明G和Z4同構(gòu)13.(6)有8個元素的群G的乘法表如下：ei

4、jkmnopeeijkmnopiijkepomnjjkeinmpokkeijopnmmmonpejiknnpmojekioonpmkiejppmonikje(a) 寫出G中階數(shù)是2的元素。(b) 寫出G中具有4個元素的子循環(huán)群及其生成元。(c) 寫出一個G中具有4個元素的非循環(huán)子群。(d) 列出G的所有3階子群。如果沒有的話說明理由。14.(6)已知簡單有向圖G=如下圖所示：v1v5v3v2v4(a) 用矩陣運(yùn)算的方法找出所有長度為2的路。(b) 用Warshall方法求出可達(dá)矩陣，再根據(jù)可達(dá)矩陣求圖G的強(qiáng)分圖。15.(6)一個藝術(shù)展覽安排在如下圖所示的5個房間中（圖中已標(biāo)注）。是否有一條路恰好經(jīng)過每個門一次看完展覽？如果有的話，在下圖上描出路徑。1234516.(5)畫出K5中的沒有公共邊的兩個漢密爾頓回路，17.(6)一顆根樹(T,v0)如下圖所示：v0v1v3v2v4v5v10v6v7v8v9(a) T的高度是多少？(b) 列出T的樹葉。(c) 包含v4的子樹有多少？(d) 列出v7的兄弟節(jié)點(diǎn)。(e)