離散數(shù)學(xué)樣卷十二套(含答案)

一、證明下列各題

1、（10分）證明蘊(yùn)涵式：P人（PfQ）nQ

2、（10分）證明：九g為1-1函數(shù)n/cig為1-1函數(shù)。

5、3、（10分）給定代數(shù)結(jié)構(gòu)（Mx〉和?0」｝，x），其中N是自然數(shù)集合，x是數(shù)的

乘法。設(shè)｛0,1｝,定義為：

，/、1n=2k,n,k$N

f（n）=<

0否則

試證〈Mx〉三〈｛0，l｝，x]

4、（10分）給定代數(shù)結(jié)構(gòu)（尺*〉，其中R是實(shí)數(shù)集合，對R中任意元。和"*定

義如下：a*b=a+b+axb

試證明:〈凡*〉是獨(dú)異點(diǎn)。

二、求下列各題的解：

1、試求下列公式的主析取范式和主合取范式（15分）:

（「尸「Q）

2、（15分）設(shè)氏={〈0，1），〈0,2〉，〈0,3〉，。，2〉,（1,3）,〈2,3〉},試求

⑴、R*R，⑵、/{1},⑶、5},（4）、此例，（5）、上刖］

3、（15分給定無向圖6=〈匕石），如圖，試求:

FED

（1）從A到D的所有基本鏈；

（2）從A到D的所有簡單鏈；

（3）長度分別是最小和最大的簡單圈;

（4）長度分別是最小和最大的基本圈;

（5）從A到D的距離。

4、45分）給定二部圖G=化，瓦匕），如圖

V,

一、證明下列各題

1、（10分）證明蘊(yùn)涵式：P—QnP-（PA°）

2、(10分)證明：AX(8—C)=(AXB)—(4XC)

3、(10分)給定群(°')，則伶')為Abel群

o(Wa)"b)(a,匕eGf(ab)2=a2b2)

4、（10分）給定代數(shù)結(jié)構(gòu)（S，*），其中S中元為實(shí)數(shù)有序?qū)Γ?定義為

[a,b）*（c,d）=（a+c,b+d+2bd）,試證｛S,*）是可交換獨(dú)異點(diǎn)。

二、求下列各題的解：

1、試求下列公式的主析取范式和主合取范式（15分）:

Pv（「Pr（Qv（「Q-?R）））

2、（15分）設(shè)/?={3/但0〉?，叫，試求“幻，5（我）和川）。

3、（15分）給定有向圖G—〈V'￡），如圖，試求:

（1）、各結(jié)點(diǎn)的出度、入度和度；

（2）、從W到v」的所有簡單路和基本路；

（3）、所有簡單回路和基本回路。

4、（15分）給定樹G,試求對應(yīng)二叉樹

一、證明下列各題

1、（10分）證明蘊(yùn)涵式：（/>一0）—。=/>丫。

2、（10分）證明：九g為1T函數(shù)n/Clg為1-1函數(shù)。

給定代數(shù)結(jié)構(gòu)〈N，x〉和《｛0」｝，'），其中N是自然數(shù)集合，x是數(shù)的乘

3、（10分）

法。設(shè)廣Nf｛0,1｝,定義為:

1n=2k,n,k&N

/（〃）=，

0否則

試證〈Mx〉三他1｝，X）。

4、(10分)給定代數(shù)結(jié)構(gòu)@，*〉，其中S中元為實(shí)數(shù)有序?qū)Γ?定義為

(a,by{c,d)=(a+c,b+d+2bd)f試證6*)是可交換獨(dú)異點(diǎn)。

二、求下列各題的解：

1、試求下列公式的主析取范式和主合取范式(15分):

R)))

2、(15分)設(shè)夫={〈0，1〉，〈0,2〉，〈0,3〉，。，2〉,〈1,3〉,〈2,3〉},試求

⑴、R*R，(2)、"{1},⑶、KT{1},(4)、R[{1}],(5)、內(nèi)刖]

3、(15分)給定有向圖G=〈')，如圖，試求:

V5V4吟

(1)、各結(jié)點(diǎn)的出度、入度和度；

(2)、從vi到V3的所有簡單路和基本路；

(3)、所有簡單回路和基本回路。

4、(15分)給定樹G,試求對應(yīng)二叉樹

專業(yè):信息與計(jì)算科學(xué)課程名稱：離散數(shù)學(xué)學(xué)分：3試卷編號（D）

課程編號：4114600考試方式：閉卷考試時間：120分鐘

擬卷入（簽字）:擬卷日期:審核人（簽字）:

得分統(tǒng)計(jì)表

N!題號—總分

救婚

得分

一、第一部分

1（10分）寫出下列公式的真值表

A=（pvq）

得分

閱卷人

D|P：

料已

2（10分）用等值演算法判斷下列公式的類型

q八一1Sfq）

3（10分）求主析取范式

4（10分）判斷下面推理是否正確

若今天是1號，則明天是5號.今天是1號.所以明天是5號.

5（10分）用歸繆法證明

前提：r->5,-is,p結(jié)論：

二、第二部分

1（10分）在一階邏輯中將下面命題符號化

-------------------正數(shù)都大于負(fù)數(shù)

得分

閱卷人

2（10分）設(shè)偏序集＜4＜＞如下圖所示，

求力的極小元、最小元、極大元、最大元.

設(shè)8={6,c,濟(jì)，求5的下界、上界、下確界、上確界.

3（10分）伍辦是12階循環(huán)群，寫出G的所有子群

4（10分）考慮110的正因子集合Si。關(guān)于gcd,1cm運(yùn)算構(gòu)成的布爾代數(shù).

寫出它所有的子布爾代數(shù)

5（10分）⑴對權(quán)1，4,9,16,25,36,49,64,81,100構(gòu)造一棵最優(yōu)二元樹，并求權(quán)和。

⑵求下圖的最小生成樹，并求最小權(quán)和

專業(yè):信息與計(jì)算科學(xué)課程名稱：離散數(shù)學(xué)學(xué)分：3試卷編號（E）

課程編號：4114600考試方式：閉卷考試時間：120分鐘

擬卷入（簽字）：擬卷日期：審核人（簽字）：

得分統(tǒng)計(jì)表

N!題號—總分

救婚

得分

一、第一部分

1（10分）寫出下列公式的真值表

B=(q->p)八qip

得分

閱卷人

D|P：

料已

2（10分）用等值演算法判斷下列公式的類型

3（10分）求主合取范式

4（10分）判斷下面推理是否正確

若今天是1號，則明天是5號.明天是5號.所以今天是1號

5（10分）用附加前提證明法構(gòu)造證明

前提：pvq,prr,r->-ns結(jié)論：slq

二、第二部分

1（10分）在一階邏輯中將下面命題符號化

有的無理數(shù)大于有的有理數(shù)

得分

閱卷人

2（10分）已知偏序集＜4曲的哈斯圖如下圖所示,

試求出集合力和關(guān)系7?的表達(dá)式.。

3（10分）設(shè)作｛&a,b,d是Klein四元群.給出G的所有自同構(gòu).

4（10分）寫出下圖中￡i,L?,￡3的原子。

?000

5（10分）寫出下圖所示樹產(chǎn)生的前綴碼

專業(yè):信息與計(jì)算科學(xué)課程名稱：離散數(shù)學(xué)學(xué)分：3試卷編號(F)

課程編號：4114600考試方式：閉卷考試時間：120分鐘

擬卷入(簽字)：擬卷日期：審核人(簽字)：

得分統(tǒng)計(jì)表

題號—總分

得分

一、第一部分

1(10分)寫出下列公式的真值表

得分

閱卷人

2(10分)用等值演算法判斷下列公式的類型

((/?A<7)v(/?A-,g))Ar)

3(10分)用主析取范式判兩個公式是否等值

(1)p->(q->r)與(pA<7)->r

(2)pf(qrr)與(p—><7)—>r

4（10分）證明｛J｝為聯(lián)結(jié)詞完備集

5（10分）直接證明法構(gòu)造證明

前提：（pv<7）->r,r->s,-is結(jié)論：

二、第二部分

1（10分）在一階邏輯中將下面命題符號化

（1）人都愛美（2）有人用左手寫字

得分個體域分別為

（a）介“人類集合”=｛xx是人｝

閱卷人（6）〃為全總個體域

2（10分）分別畫出下列各偏序集的哈斯圖，再求出最大元、最小元、極大元和極小元

A=（a,b,c,d,e）<=（<a,b>,<a,c>,<a,d>,<a,e>,<b,e>,<c,e>,<d,e>UIA

“、f^2x>3,、c

J（x）=<g（x）=x+2

3（10分）設(shè)f：RTR,g：RTRl-2*<3

求/bg,gQ/：如果/和g存在反函數(shù)，求出它們的反函數(shù).

4（10分）下圖中的人心,A和乙是否是有補(bǔ)格。

L.

5（10分）用Huffman算法產(chǎn)生最佳前綴碼

在通信中，八進(jìn)制數(shù)字出現(xiàn)的頻率如下:

0：25%1：20%

2：15%3：10%

4：10%5：10%

6：5%7：5%

求傳輸它們的最佳前綴碼，并求傳輸10000個按上述比例出現(xiàn)的八進(jìn)制數(shù)字需要多少

個

二進(jìn)制數(shù)字？若用等長的（長為3）的碼字傳輸需要多少個二進(jìn)制數(shù)字？

專業(yè):信息與計(jì)算科學(xué)課程名稱：離散數(shù)學(xué)學(xué)分：3試卷編號（G）

課程編號：411461考試方式：閱去考試時間：100分鐘

擬卷人（簽字）：擬卷日期：審核人（簽字）：

得分統(tǒng)表：

題號—三四總分

得分

得分閱卷人一、將下列命題符號化：（本題共4題，每題5分，滿分20分.）

1.小明學(xué)習(xí)和體育都好.

2.只有努力才能成功.

3.存在函數(shù)連續(xù)但不可導(dǎo)（論域?yàn)槿倐€體域）.

4.凡有理數(shù)均可表示成分?jǐn)?shù)（論域?yàn)槿倐€體域）.

得分閱卷人

計(jì)算題:（本題共3小題,滿分34分.）

1.求公式（P—°）A（PA°）的主析取范式和主合取范式（12分）.

2設(shè)A={1,2,3},A上的一兀關(guān)系R={(1,2),(2,2),(2,3)}.求“R)、s(R)及t(R)(12

分).

3.設(shè)4={1，2,3}，問人上共有多少個不同的等價關(guān)系（10分）.

三、應(yīng)用題：（本題共3小題，滿分30分.）

1.畫出集合A={1'2'3'4,6，12}上整除關(guān)系的哈斯圖，指出最大元、最小元、極

大元和極小元（12分）.

2.設(shè)〃=底,*）是半群，s={a,b,c,d},“*”運(yùn)算定義如下表（10分）:

（1）.證明U是一個循環(huán)含幺半群，并給出它的生成元;

*abcd

aabcd（2）.把U中的每個元素均表示成生成元的疑.

bbcda

ccdab

ddabc

3.設(shè)（4,+,x）是一個代數(shù)系統(tǒng)，A=[x\x=a+b“，。、人均為有理數(shù)，其中

“+"、“X”為普通加法和普通乘法，問(A,+,x)是否為域？為什么？(8分)

得分閱卷人四、證明題：(本題共2小題，滿分16分.)

1.給定代數(shù)系統(tǒng)0=(*，?)，丫=0?,卬=(2,*).設(shè)/是從。到"的同態(tài)，力是從V到

W的同態(tài).證明：力。/是從U到W的同態(tài).(8分)：

2.構(gòu)造下列推理的證明(8分)：

前提:Vx(A(x)-「8(x)),Vx(B(x)vC(x)),「VxC(x).

結(jié)論：引「A(x).

料t

：3.存在函數(shù)連續(xù)且可導(dǎo)（論域?yàn)槿倐€體域）.

4.有的有理數(shù)能被2整除（論域?yàn)槿倐€體域）.

黑二、計(jì)算題：（本題共3小題，滿分34分.）

1.化?階邏輯公式（vxP（x）vW2（y））fVxR（x）為前束范式（12分）.

2設(shè)4={。也（:},4上的二元關(guān)系7?={（。,6）,3,3,（仇0）}求，也）、s（R）及t（R）

（12分）.

3.設(shè)A={1,2,3,4},問A上共有多少個不同的等價關(guān)系（10分）

三、應(yīng)用題：（本題共3小題，滿分30分.）

1.畫出集合A={2,3,4,9,12}上整除關(guān)系的哈斯圖，指出極大元和極小元（12

分）.

2.設(shè)U=3*）是半群，s={a，b,c},“*”運(yùn)算定義如下表（10分）:

*abc

aabc（1）.證明U是一個循環(huán)含幺半群，并給出它的生成元；

bbca（2）.把U中的每個元素均表示成生成元的累.

ccab

A=x|』+碼,以b均為有理數(shù),其中

3.設(shè)（A+/）是一個代數(shù)系統(tǒng)，一

"+"、“x”為普通加法和普通乘法，問（A,+,x）是否為域？為什么？（8分）

得分閱卷人四、證明題：（本題共2小題，滿分16分.）

1.設(shè)/、g分別是兩代數(shù)系統(tǒng)（X，。），*，*）上的同態(tài)，其中（丫，*）可交換,令〃是從X到

丫的函數(shù)，對VxeX有：/7（x）=/（x）*g（x）.證明：人是從x到y(tǒng)的同態(tài).（8分）：

2.構(gòu)造下列推理的證明（8分）：

前提：P.{SAR）f-10）,P,—.

結(jié)論：「e

專業(yè)：信息與計(jì)算科學(xué)課程名稱：離散數(shù)學(xué)學(xué)分：3試卷編號（I）

課程編號：4114600考試方式：閑典考試時間：100分鐘

擬卷人（簽字）：擬卷日期：審核人（簽字）：

.-得分統(tǒng)表：

—.

W.題號—三四總分

姬

軟

—

：得分

：

得分閱卷人一、將下列命題符號化：（本題共4題，每題5分，滿分20分.）

1.只要努力過就不會后悔.

：2.我在城在.

D|P\

料日

3.所有孩子都崇拜某些偶像（論域?yàn)槿倐€體域）.

4.一切房子都不?樣大（論域?yàn)槿倐€體域）.

得分閱卷人

黑計(jì)算題:（本題共3小題,滿分34分.）

1.求公式（2八。）-R的主析取范式和主合取范式（12分）.

2.設(shè)4={1,2},4上的一兀關(guān)系7?={(1,2)}.求「也)、s(R)及t(R)(12分)

3.設(shè)4={1，2}，問A上共有多少個不同的等價關(guān)系（10分）.

得分閱卷人

三、應(yīng)用題：（本題共3小題，滿分30分.）

1.畫出集合A={2'3,4,7,8,9}上整除關(guān)系的哈斯圖，指出極大元和極小元（12

分）.

2『G={e,a,b,c}

,”為G上的二元運(yùn)算,“*”運(yùn)算定義如下表（10分）:

（1）.G是否能構(gòu)成一個群？

*eabc

eeabc（2）.G有何性質(zhì)？

aaecb

bbcea

ccbae

3.設(shè)（A，+d）是一個代數(shù)系統(tǒng),a、6均為有理數(shù)，其中

+”、“x”為普通加法和普通乘法，問（A,+,x）是否為域？為什么？（8分）

得分閱卷人四、證明題：（本題共2小題，滿分16分.）

1.設(shè)/：R-R，VxeR有/（x）=2x.證明：/是（尺+）上的自同構(gòu).（8分）:

2.構(gòu)造下列推理的證明（8分）：

前提：Vx（P（x）f。（幻）,一（「?！罚?

結(jié)論：主（iQ（x）△-1P（x））.

一、證明下列各題

得分

2：1、（10分）證明蘊(yùn)涵式：P人（P-?Q）n。

閱卷人

2、（10分）證明：￡g為IT函數(shù)n/Clg沏-1函數(shù)。

5、3、50分）給定代數(shù)結(jié)構(gòu)MM和40,1},X）,其中N是自然數(shù)集合,

x是數(shù)的

乘法。設(shè)廣Nr{0,1},定義為:

/（?）=':n-2k,n,keN

否則

試證〈Mx〉三〈{0,1}'X）。

4、（10分）給定代數(shù)結(jié)構(gòu)〈&*〉，其中R是實(shí)數(shù)集合，對R中任意元。和〃，*定

義如下：a*b=a+b+axb

試證明:〈&*〉是獨(dú)異點(diǎn)。

二、求下列各題的解：

得分

1、試求下列公式的主析取范式和主合取范式（15分）:

閱卷人（尸］。）

2、（15分）設(shè)尺={〈0，1〉，〈。，2〉，〈0,3〉，〈1，2〉,。,3〉,〈2,3）},試求

⑴、R*R，（2）、而傅，（3）、KT{1},⑷、RDM，（5）、內(nèi)刖］

3、（15分給定無向圖G=（V,￡），如圖，試求:

FED

（1）從A到D的所有基本鏈；

（2）從A到D的所有簡單鏈；

（3）長度分別是最小和最大的簡單圈;

（4）長度分別是最小利最大的基本圈;

（5）從A到D的距離。

4、（15分）給定二部圖G=化，區(qū)匕），如圖

匕

業(yè)：信息與計(jì)算科學(xué)課程名稱：離散數(shù)學(xué)學(xué)分：二_試卷編號

（K）

課程編號：4114600考試方式：閉卷考試時間：JOT.分鐘

擬卷人（簽字）：_______擬卷日期：_________審核人（簽字）：_______

得分統(tǒng)計(jì)表:

題號―■二總分

得分一、證明

得夕下列

閱卷人

1、（10分）證明蘊(yùn)涵式:P—QnPf(PAQ)

2、(10分)證明：AX(8—C)=(AX8)—(4XC)

3、(10分)給定群〈G，〉，則(G，)

為Abel群

222

<=>(Va)(Vb)(〃,bGG—>(6fh)=ab)

4、(10分)給定代數(shù)結(jié)構(gòu)C'*)，其中S中元為實(shí)數(shù)有序?qū)Γ?定義為

(a,b)*(c,d)=(a+c,b+d+2bd)試證⑸*〉是可交換獨(dú)異點(diǎn)。

得分二、求下列各題的解：

_i.______________1、試求下列公式的主析取范式和主合取范式(15分):

閱卷人Pv(~1P-v-R)))

2、(15分)設(shè)夫={@"〉，〈仇。，《⑷「試求”⑻屈幻和^氏)。

3、（15分）給定有向圖G=（V，E），如圖，試求:

（1）、各結(jié)點(diǎn)的出度、入度和度；

（2）、從vi到V3的所有簡單路和基本路；

（3）、所有簡單回路和基本回路。

4、（15分）給定樹G,試求對應(yīng)二叉樹

一、證明下列各題

1、（10分）證明蘊(yùn)涵式:(PTQ'TQOPTQ

2、（10分）證明：￡g為1T函數(shù)n/Clg為1-1函數(shù)。

3、（10分）給定代數(shù)結(jié)構(gòu)〈Mx）和（{0』}，x）,其中N是自然數(shù)集合,

X是數(shù)的乘

法。設(shè)廣Nf{0,1},定義為：

一、1，1=2k，〃,keN

八〃）=0否則

試證〈Mx〉三（{0,1},X）。

4、（10分）給定代數(shù)結(jié)構(gòu)〈S，*〉，其中S中元為實(shí)數(shù)有序?qū)Γ?定義為

（a,by（c,d）={a+c,b+d+2bd）f試證但*）是可交換獨(dú)異點(diǎn)。

二、求下列各題的解：

得分

1、試求下列公式的主析取范式和主合取范式（15分）:

閱卷人Pv（「P->（Qv（「Q->R）））

2、（15分）設(shè)—={〈0，1〉，〈0,2），〈0,3〉，。，2〉,。,3）,〈2,3?,試求

⑴、R*R，⑵、RT。},（3）、R"T{I},（4）、網(wǎng){吐（5）、穴IP}]

3、（15分）給定有向圖G—〈V'￡），如圖，試求:

（1）、各結(jié)點(diǎn)的出度、入度和度；

（2）、從W到v」的所有簡單路和基本路；

（3）、所有簡單回路和基本回路。

4、（15分）給定樹G,試求對應(yīng)二叉樹

答案:

一、1、

(「△(PfQ))fQ=「(P?PvQ))v?！?'o］Pv(Pv「Q)v。……2，

o「Pv(P△」Q)vQ......2'o(「PvP)人v」Q)vQ.......2'ov」Q)vQ

O「Pv(「QvQ)=T.......2'

或用推理方法，或用真值表方法(略)。

Clgy人VClgz。加人xgy△破人xgz

2、=xfy人對z=y=z......5分

“(/fig)—%△”(/Cig尸w<=>uf~'v/\ug~'v/\uf~'w/\ug~'w

=>uf~'v/\uf~］w=>v=w......5分

3、任給相，"GN,有三種情況：

(1)存在占水2cN,使機(jī)=2勺，〃=2%成立；......1分

(2)存在船％2GM使機(jī)=2自成立而不存在使〃=2與成立；或者反之；……1

分

(3)不存在配&eN,使機(jī)=2"〃=2"成立?！?分

對于(1),顯然有了(〃?x〃)=/(2e)=lJ(〃?)x/(〃)=/(2"x/(2*2)=lxl=l,即

/(mxn)=/(/M)x/(/i).……3分

對于(2)(3),均有/(加'")=/(加”/(〃)?！》?/p>

因?yàn)閒(mx〃)=0,加x〃#2*'f(m)xf(n)=0,m=2lc',n^2*2或％/2*'和〃=2*2

或加工2例和刀#2*2。……2分

綜上所述，/("zx〃)=/(加)x/(n),故〈N,x)，{0,l},x)。

4、首先證明*滿足結(jié)合律，任給x，y，zeR,因?yàn)?/p>

(x*y)*z=(x+y+xxy)*z=x+y+xxy+z+(x+y+xxy)xz

=/+y+z+xxy+xxz+yxz+xxyxz,

x*(y*z)=x*(y+z+yxz)=x+y+z+yxz+xx(y+z+yxz)

+y+z+yxz+xxy+xxz+xxyxz.

故a*y)*z=x*(y*z),因此，*滿足結(jié)合律。……5分

其次證明*有幺元0,任給xeR,有：°*x=0+x+°xx=x,x*°=x+0+xx°=x,

故0是*的幺元。……5分

綜上所述，依*〉是獨(dú)異點(diǎn)。

(「PV」。)-(P］。)=」(「PV「。)v((P-「Q)A(~,QTP))?―2'

=(尸△。)v((「尸v［。)A(QvP))??????2'

=(Pv((「Pv「。)A(PvQ)))A(2V((「Pv「。)A(PV。)))……2'

?(Pv-1Pv-n2)A(PvPve)A(ev^Pv-ne)A(PvPv2).......3'

二、］、o(PvQ)o%……3'

主析取范式為叫……3分

2、⑴、R*R={@2}，〈0,3〉,〈L3)}……3分

⑵、而{1}={〈1,2)43〉}……3分

⑶、內(nèi)={(叫}……3分

(4)、網(wǎng){1}]={2,3}……3分

⑸、/?-'{1!={0}……3分

3、(1)、從1至U〃的所有基本鏈共有10條，即：ABD,ABED,ABCD,ABCED,ABECD,AFED,

AFECD,AFEBD,AFEBCD,AFECBD.....3分

(2)、從月到〃的所有簡單鏈共有14條，即除(1)的10條外，還有ABCEBD,ABECBD,

AFEBCED,AFECBED....3分

(3)、長度最小的簡單圈共4個，即BCDB,BCEB,BDEB,CDEC,長度最大的簡單.圈

共2個,即ABCEBDEFA,AFEBCEDBA....3分

(4)、長度最小的基本圈共4個，即同(3)；長度最大的基本圈有2個，為ABDCEFA；

ABCDEFA...3分；

⑸、。(人。)=2。......3分

4、乂到匕的最大匹配有多個，如{〈匕，％)，〈匕，％〉，〈匕，丫6〉，。5，口9〉},得分情況根據(jù)具體解

題過程考慮。

(P->Q)f(Pf(P人Q))o(「PvQ)-(「尸V(FA2))??????2'

」(「尸v。)v(」Pv(P△Q))=(P人］。)v(「尸v(尸人Q))?―2'

=((P△vv((P人［。)v(P人Q))

=((PA「尸)A(「Pv」Q))v(((P△vP)人((PA［。))vQ))……2'

=(「P△「Q)v(尸△((Pv。)人(［。v2)))

=(「PA「。)V(PA((PvQ))=「PvvP........2'

一、1....2'

(x,y)GAx(5-C)<=>xGAAyG(5-C)....2'

C)....2'<^>(xGAAyeB)A(xeAAy^C)....2'

o(x,y〉EAx8A〈x,y)任AxC...2'=(x,y)￡(4x5)_(AxC)....2'

乙、

3、充分性：因?yàn)椤碐')是群，又對任意a/eG,有

(abY=a2b2=>(ab)(ab)=(aa)(bb)

=>a(ba)b=a(ab)b=>(ba)b=(ab)b

=>ha=ah....5'

可見，是可交換的，故(°')為Abel.

必要性：@)為Abel群，自然〈°，)是群；又對任意a/wG,有

(ab)2=(ah)(ab)=a(ba)h=a(ab)h

=(aa)(bb)=a2b2....5'

4、首先證明*是可結(jié)合的，任給SM，〈c,d〉,〈eJ)eS,有：

《a,b)*?d》*〈e,f)=ggb+d+2bd〉*&f〉

=<〃+c+e,》+d+/+2bd+2(/?+d+2bd?

=<〃+c+e,Z?+d+/+2hd+2bf+2df+4bdf)

伍b)*《c,cT)*(eQ)=(a,b)*〈c+d,d+f+2df)

=(a+c+e,b+e+/+2df+2b(d+/+

而=<〃+c+e,b+d+/+2hd+2hf+2df+4bdf),

故滿足結(jié)合律，6*)是半群。……5分

其次證明*有幺元〈.°)，任給("MeS,有

〈0,0)*〈。/)=(0+。,0+/?+2x0x6)=〈〃力)，

(a,b〉*〈0,0〉=〈a+0,b+0+2xbx0)=?/〉.因此，〈0，°〉是幺元?！?分

最后，證明*滿足交換律，任給〈"S)，(c,d)eS,有

{a,b)*{c,d)=(a+c,b+d+2hd)=(c,d)^{a,b)故*滿足見換律。......3分

綜上可知，⑸*)是可交換獨(dú)異點(diǎn)。

Pv(「P-(Qv(「QT/?)))0Pv(Pv(Qv(Qv/?)))……5，

二、］oPvQvRoM。.......5'

2r(R)={a，b),(b,c),(c,a),〈a,a)，8,0〉,〈c,c)}......5分

s(R)={〈a/〉，8，c),(c,a)，a，a〉,〈c,0〉,(a,c)}......5分

t(R)={(a,b),(b,c),(c,a),(a,c),(b,a),(c,b),(a,a),(b,b),(c,c)}...5分

+VV+VV+VV

￡/(I)=2,(/"(1)=1;J(2)=1,6/-(2)=2;J(3)=1,J-(3)=1;

++

d(y4)=2,J-(v4)=2;d(vs)=1,J-(v5)=1.

3、(1)、1(%)=3,1(嶺)=3,1(匕)=2,1(%)=4,1(以)=2.……§分

(2)、V>到匕的所有簡單路共4條，它們是V"4V3,叩235叩4匕#"3#"5叩2叩3.

匕到匕的所有基本路共2條，它們是：匕丫2V4匕，匕匕匕?……5分

(3)、所有基本回路共3條，它們是:叩4M，嶺14吁2”所有簡單回路除上3

個基本回路外，還有1個,它是4%匕嶺V4V5%……5分

4、根據(jù)解題過程分步給分。

((PfQ)->Q)->(PVQ)oT*Pv2)v2)v(PvQ)……1

=」((PA「Q)VQ)V(PVQ)=((「PVQ)AQ)V(PVQ)??-2'

((「PA「。)V(QA［。))v(Pv。)o((「PA「。)v(FvQ)……2'

一、1=(「PvPvQ)/\(「QvPvQ).......2'OTAT=T2'

或用真值表方法(略)。

xfr\gy^xfC\gz^xfy/\xgy/\xfz^xgz

2、=>^AVz=>y=z.......5'

w(/fig)/Ag)-1vvouf~lv/\ug~[v/\uf~]w/\ug~｛w

=>uf~xv/\uf~xw^>v=w....5r

3、任給如〃EM有三種情況：

(1)存在配火2wN,使用=2*〃=2人成立；……1分

(2)存在船&eN,使,〃=2自成立而不存在使〃=2和成立；或者反之；……1

分

(3)不存在占#2,使“=2",,〃=2八成立。1分

對于(1),顯然有“〃?*〃)=/(2收)=1j(⑼xf(n)=f(2k')xf(2壇)=1x1=1,即

f(mxn)=f(m)xf(n);...3分

對于(2)(3),均有/(加x")=/0〃)x/(〃)?！?分

因?yàn)榱?"[X")=o,加X"#2g/(rn)X/(〃)=0,加=2占，"#2*?或加/2&和〃=2壇

或7nH2*和九二2檢。...2分

綜上所述,/(加x〃)=/("z)x/(〃)，故〈Mx〉/。/”)。

4、首先證明*滿足結(jié)合律，任給％y，zeR,因?yàn)?/p>

(x*y)*z=(x+y+xxy)*z=x+y+xxy+z+(x+y+xxy)xz

=x+y+z+%xy+xxz+yxz+xxyxz,

x*(y*z)=x*(y+z+yxz)=x+y+z+yxz+xx(y+z+yxz)

同=x+y+z+yxz+xxy+xxz+冗xyxz.

故(x*y)*z=X*(y*Z),因此，*滿足結(jié)合律?！?分，其次證明*有幺元0,任給XeR,

有：0*x=0+x+0xx=x,x*0=x+0+xx0=x,故。是*的幺元。……5分

綜上所述，(民*〉是獨(dú)異點(diǎn)。

Pv(「Pf(Qv(「Qf??)))=Pv(Pv(Qv(QvR)))……5，

二、1、=PvQvR....5'<=>M0主合取范式，

主析取范式為：叫v嗎vm3V外vm5Vs.v叫。……5分

2、⑴、R*R=｛〈。，2〉，〈0,3〉,〈1,3))……3分

⑵、祈｛1｝=｛〈1,2〉,〈1,3)｝……3分⑶、k=｛〈L?！担?分

⑷、即｛1｝]=｛2,3｝……3分⑸、內(nèi)｛1｝=｛。｝……3分

，(“)=2,J-(v()=1；，(彩)=1,"一(彩)=2；△(匕)=1/一(也)=1；

++

d(v4)=2,J-(v4)=2；d(v5)=l,J-(v5)=l.

V3

3、⑴、^(I)=，^(V2)=3,J(V3)=2,J(V4)=4,J(V5)=2....5分

(2)、匕至-3的所有簡單路共4條，它們是斗2”3,叩2叩5叩4匕，叩必用4匕呼2“3.

匕到匕的所有基本路共2條，它們是：丫必丫4V3，W43……5分

(3)、所有基本回路共3條，它們是：匕匕以％匕，匕丫4丫5匕#2V4V3%。所有簡單回路除上3

個基本回路外,還有1個，它是“MV3V2彩……5分

4、根據(jù)解題過程分步給分。

專業(yè)：信息與計(jì)算科課程名稱：離散數(shù)學(xué)學(xué)分：上_試卷編號（D）

字______

一.、第一部分

I（10分）寫出下列公式的真值表

A=（內(nèi)。）—

pQrmq—ir(w)

000011

001001

010111

011100

100111

101100

110111

111100

每錯一處扣1分，扣到10分為止

2（10分）用等值演算法判斷下列公式的類型

QA->

（2，）

=QA-iJp/q)（蘊(yùn)涵等值式）

（2，）

0q八(pA-)q)（德摩根律）

（2，）

=IQ)（交換律，結(jié)合律）

(2，)

<=>/?A0（矛盾律）

（2，）

00（零律）

由最后一步可知，為矛盾式.

3（10分）求主析取范式

hTr

=(PAQ)V_T（析取范式）①

（0AQ）

=(7?AQ)/\(TV_r)

O(PA(?A—ir)v{p/\q/\r)

(3')

<=>gnh②

O(―,/A/jt?)A(—Ar

=(-1PA-iQA7)V(~yp/\(J/\r)V(pA-iQAr)V(°AQAr)

=ZZ7|VZ?iVZ%VZ^③

②，③代入①并排序，得

(?■>->(?)frO^v/zhvz^v小7砥(主析取范式)*J

4(10分)判斷下面推理是否正確

若今天是1號，則明天是5號.今天是1號.所以明天是5號.

解設(shè)R今天是1號，q：明天是5號.O')

(用等值演算法)

O-I((-I/A//7)A/?)v(zG)

o-i/A/-i(?vq°)

o1(2')

推理正確

5(10分)用歸繆法證明

前提：-i(pAQ)vr,r—s、->s,0結(jié)論：-yq

證明(用歸繆法)

(1')

①Q(mào)結(jié)論否定引入

②is前提引入。')

(1‘)

③「5前提引入

(1')

④-17②③拒取式

(1')

⑤->(PAQ)vr前提引入

(1')

⑥-1(PA<7)④⑤析取三段論

(19

⑦->內(nèi)-1。⑥置換

(19

⑧~?P①⑦析取三段論

(0

⑨P前提引入

(1')

10—10A/7⑧⑨合取

-、第i部分

1(10分)在一階邏輯中將下面命題符號化

正數(shù)都大于負(fù)數(shù)

令夕(x)：x為正數(shù)，C(y)：y為負(fù)數(shù)0)

L(x,負(fù):x>yG)

Vx(P(x)fVy(6(y)->￡(x,y)))U)

u>X/處y(Fd)八G5)負(fù))

2(10分)設(shè)偏序集<4w>如下圖所示，

求力的極小元、最小元、極大元、最大元.

設(shè)6={“c,M,求6的下界、上界、下確界、上確界.

解極小元：a,b,