第一篇：西安交通大學(xué)1999年研究生入學(xué)考試離散數(shù)學(xué)試題

西安交通大學(xué)1999年研究生入學(xué)考試 離散數(shù)學(xué)試題(30分)

請(qǐng)判斷下列各題的正確性。

⑴ 2∩2=2ABA∩B。

⑵ AB=A當(dāng)且僅當(dāng)B=?。

⑶(A′C)(B′D)=(AB)′(CD)。

⑷ 設(shè)|A|=5，則A上恰有31個(gè)不同的等價(jià)關(guān)系。

⑸ 設(shè)R非空集合A上的關(guān)系，R是A上可傳遞的，當(dāng)且僅當(dāng)R○RíR。

⑹ 若R1，R2均為非空集合A上的等價(jià)關(guān)系，那么R1○ R2也為A上的等價(jià)關(guān)系。

⑺ 設(shè)

為半序集，?1SíP，若S有上界，則S必有上確界。

⑻ 設(shè)N為自然數(shù)集合，I為整數(shù)集合，′是算術(shù)乘法，則與同構(gòu)。

⑼ 設(shè)是群，則G中至少有一個(gè)二階元素。

⑽ 設(shè)為整環(huán)，|R|=n，則是域。

⑾ 設(shè)為域，為的子環(huán)，則為整環(huán)。

⑿ 設(shè)為格，|L|=n，則為有界格。

⒀ 存在7個(gè)結(jié)點(diǎn)的自補(bǔ)圖。

⒁ 下圖為平面圖。

圖1 題1(14)

⒂ 下圖為哈密爾頓圖。

圖2 題1(15)圖

2(8分)

設(shè)(G,*)為循環(huán)群，生成元為a，設(shè)(A,*)和(B,*)均為(G,*)的子群，而a和a分別為(A,*)和(B,*)的生成元。

① 證明(A∩B,*)是(G,*)的子群。

② 請(qǐng)問：(A∩B)是否為循環(huán)群。如果是，請(qǐng)給出其生成元。

3(10分)

設(shè)(A,?,?)是環(huán)，A={f |f是A到A的函數(shù)}。定義A上的運(yùn)算à和*如下，設(shè)f,g?A, 對(duì)于任意的x?A。

(fàg)(x)=f(x)?g(x)；

(f*g)(x)=f(x)?g(x)；

證明：(A,à,*)是環(huán)。

4(6分)

設(shè)A=和B=是兩個(gè)格，f是A到B的同態(tài)函數(shù)。證明A的同態(tài)象是B的子格。(注：A的同態(tài)象即：f(L1)={f(x)|x?L1})。

5(8分)

設(shè)G=（V,E）是簡(jiǎn)單的無(wú)向平面圖，證明G中至少有一個(gè)結(jié)點(diǎn)的度數(shù)小于等于5。

6(10分)

設(shè)G是連通的無(wú)向圖，且有2k>0個(gè)奇結(jié)點(diǎn)，證明：G中存在各邊不重復(fù)的k條簡(jiǎn)單路P1，P2，…，Pk，使得 A

A

A

A

i

j

E(G)=E(P1)∪E(P2)∪…∪E(Pk)。

7(8分)

設(shè)個(gè)體域?yàn)檎麛?shù)集合，將下述語(yǔ)句分別表示成僅含有N(e)、P(e)、Q(e)、E(e1,e2)、L(e1,e2)、D(e1,e2)所組成的謂詞公式：其中各謂詞定義如下：

N(e)： e是自然數(shù)，P(e)： e是素?cái)?shù)，Q(e)： e是偶數(shù)，E(e1,e2)：e1=e2，L(e1,e2)：e1

② 并非所有的素?cái)?shù)都不是偶數(shù)。

8(8分)

判斷下列邏輯關(guān)系是否成立。若成立，請(qǐng)用指派分析法給出證明。否則，請(qǐng)給出相應(yīng)的指派。

① $x(?A(x)→B(x))→“xC(x)T”x(B(x)→C(x))；

② $x(A(x)→“yB(x,y))T?”y$xB(x,y)→“xA(x)。

9(12分)

構(gòu)造形式推理過程：

① ?R(?PúS), Q→?S╞ P→(Q→R)；

② $x(A(x)→”yB(y))，“x(B(x)→$yC(y))╞ ”xA(x)→$yC(y)。

第二篇：北京大學(xué)1997年研究生入學(xué)考試離散數(shù)學(xué)試題

北京大學(xué)1997年研究生入學(xué)考試 離散數(shù)學(xué)試題（共50分）(7分)

在一階邏輯自然推理系統(tǒng)F中，構(gòu)造下面推理的證明。個(gè)體域是人的集合。

“每位科學(xué)家都是勤奮的，每個(gè)勤奮又身體健康的人在事業(yè)中都會(huì)獲得成功。存在著身體健康的科學(xué)家。所以，存在著事業(yè)獲得成功的人或事業(yè)半途而廢的人。”

2(8分)

在某次研討會(huì)的休息時(shí)間，3名與會(huì)者根據(jù)王教授的口音分別作出下述判斷：

甲說：王教授不是蘇州人，是上海人。

乙說：王教授不是上海人，是蘇州人。

丙說：王教授既不是上海人，也不是杭州人。

王教授聽后，笑曰：你們3人中有一人全說對(duì)了，有一人全說錯(cuò)了，還有一人對(duì)錯(cuò)各半。

試用邏輯演算法判斷王教授是哪里人？

3(3分)

設(shè)根樹T有17條邊，12片樹葉，4個(gè)4度內(nèi)點(diǎn)，1個(gè)3度內(nèi)點(diǎn)。求T的樹根的度數(shù)。

4(7分)

設(shè)無(wú)向圖G是n(n≥3)個(gè)頂點(diǎn)的極大平面圖，證明G的對(duì)偶圖G*的邊連通度l(G)≥2，并且G*是3-正則圖(Δ(G)=d(G)=k的無(wú)向圖G稱作k-正則圖)。

5(4分)

設(shè)R={| x,y?nùx+3y=12}，求R2。

6(6分)

設(shè)A為集合，B=P(A)-{?}-{A}，且B≠?。

求偏序集的極大元，極小元，最大元和最小元。

7(4分)

設(shè)A={1,2,3}，f?AA，且f(1)=f(2)=1，f(3)=2，定義G：A→P(A)，G(x)=f-1(x)。說明G有什么性質(zhì)(單射、滿射和雙射)，計(jì)算值域ranG。

8(4分)

設(shè)I是格L的非空子集，如果

(1)“a,b?I，有aúb?I，(2)”a?I，“x?L，有x≤aTx?I。

則稱I是格L的理想。

證明：格L的理想是一個(gè)子格。

9(7分)

設(shè)G為n階群，a?G。令

H={xax-1|x?G}，N(a)={x|x?Gùax=xa}。

證明：

① |H|=[G:N(a)]；

② 設(shè)C={x|x?Gù”y?G(xy=yx)}是群G的中心，且|C|=m，則|H|∣n/m。

第三篇：離散數(shù)學(xué)試題

中央電大離散數(shù)學(xué)試題

月

一、單項(xiàng)選擇題（每小題3分，本題共15分）

1．若集合A={1，{2}，{1，2}}，則下列表述正確的是()．

A．2?AB．{1}?A

C．1?AD．2 ? A

2．已知一棵無(wú)向樹T中有8個(gè)頂點(diǎn)，4度、3度、2度的分支點(diǎn)各一個(gè)，T的樹葉數(shù)為

()．

A．6B．4C．3D．

53．設(shè)無(wú)向圖G的鄰接矩陣為

?01111??10011????10000???11001????11010??

則G的邊數(shù)為()．

A．1B．7C．6D．14 4．設(shè)集合A={a}，則A的冪集為()．

A．{{a}}B．{a，{a}}

C．{?，{a}}D．{?，a}

5．下列公式中()為永真式．

A．?A??B ? ?A??BB．?A??B ? ?(A?B)

C．?A??B ? A?BD．?A??B ? ?(A?B)

二、填空題（每小題3分，本題共15分）

6．命題公式P??P的真值是

7．若無(wú)向樹T有5個(gè)結(jié)點(diǎn)，則T的邊數(shù)為．

8．設(shè)正則m叉樹的樹葉數(shù)為t，分支數(shù)為i，則(m-1)i

9．設(shè)集合A={1，2}上的關(guān)系R＝{<1, 1>,<1, 2>}，則在R中僅需加一個(gè)元素，就可使新得到的關(guān)系為對(duì)稱的．

10．(?x)(A(x)→B(x，z)∨C(y))中的自由變?cè)校?/p>

三、邏輯公式翻譯（每小題6分，本題共12分）

11．將語(yǔ)句“今天上課．”翻譯成命題公式．

12．將語(yǔ)句“他去操場(chǎng)鍛煉，僅當(dāng)他有時(shí)間．”翻譯成命題公式．

四、判斷說明題（每小題7分，本題共14分）

判斷下列各題正誤，并說明理由．

13．設(shè)集合A={1，2}，B={3，4}，從A到B的關(guān)系為f={<1, 3>}，則f是A到B的函數(shù)．

14．設(shè)G是一個(gè)有4個(gè)結(jié)點(diǎn)10條邊的連通圖，則G為平面圖．

五．計(jì)算題（每小題12分，本題共36分）

15．試求出（P∨Q）→（R∨Q）的析取范式．

16．設(shè)A={{1}, 1, 2}，B={ 1, {2}}，試計(jì)算

（1）（A∩B）（2）（A∪B）（3）A ?（A∩B）．

17．圖G=，其中V={ a, b, c, d }，E={(a, b),(a, c),(a, d),(b, c),(b, d),(c, d)}，對(duì)應(yīng)邊的權(quán)值依次為1、2、3、1、4及5，試

（1）畫出G的圖形；

（2）寫出G的鄰接矩陣；

（3）求出G權(quán)最小的生成樹及其權(quán)值．

六、證明題（本題共8分）

18．試證明：若R與S是集合A上的自反關(guān)系，則R∩S也是集合A上的自反關(guān)系．

中央電大2010年7月離散數(shù)學(xué)

試題解答

(供參考)

一、單項(xiàng)選擇題（每小題3分，本題共15分）

1．B2．D3．B4．C5．B

二、填空題（每小題3分，本題共15分）

6．假（或F，或0）

7．48．t-

19． <2, 1>

10．z，y

三、邏輯公式翻譯（每小題6分，本題共12分）

11．設(shè)P：今天上課，（2分）則命題公式為：P．（6分）

12．設(shè) P：他去操場(chǎng)鍛煉，Q：他有時(shí)間，（2分）則命題公式為：P ?Q．（6分）

四、判斷說明題（每小題7分，本題共14分）

13．錯(cuò)誤．（3分）因?yàn)锳中元素2沒有B中元素與之對(duì)應(yīng)，故f不是A到B的函數(shù)．（7分）

14．錯(cuò)誤．（3分）不滿足“設(shè)G是一個(gè)有v個(gè)結(jié)點(diǎn)e條邊的連通簡(jiǎn)單平面圖，若v≥3，則e≤3v-6．”（7分）

五．計(jì)算題（每小題12分，本題共36分）

15．（P∨Q）→（R∨Q）? ┐(P∨Q)∨（R∨Q）（4分）

?(┐P∧┐Q)∨（R∨Q）（8分）

?(┐P∧┐Q)∨R∨Q（析取范式）（12分）

16．（1）（A∩B）={1}（4分）

（2）（A∪B）={1, 2, {1}, {2}}（8分）

（3）A?（A∩B）={{1}, 1, 2}（12分）

17．（1）G的圖形表示如圖一所示：ad1

5b c（3分）圖一

（2）鄰接矩陣：

?0?1?10111?1??（6分）??1101?

?1110??

（3）最小的生成樹如圖二中的粗線所示：

a 3d5

b圖二1c

權(quán)為：1+1+3=5

六、證明題（本題共8分）

18．證明：設(shè)?x?A，因?yàn)镽自反，所以x R x，即< x, x>?R；

又因?yàn)镾自反，所以x R x，即< x, x >?S．即< x, x>?R∩S故R∩S自反．

10分）12分）（4分）（6分）（8分）（（

第四篇：08離散數(shù)學(xué)試題

離散數(shù)學(xué)試題

一、填空（共36分）

1、命題公式P?Q的真值為假，當(dāng)且僅當(dāng)。

2、設(shè)F(x)：x是整數(shù)，G(x):x是自然數(shù)，則命題“并不是每個(gè)整數(shù)都是自然數(shù)”符號(hào)化為。

3、設(shè)10階平面圖G有5個(gè)面，則G中有條邊。

4．設(shè)A={1，2，3，4，5，6，7}，R是A上的模4同余關(guān)系，則關(guān)系R＝。

5．六階循環(huán)群的所有生成元為，所有子群為。

6．設(shè)集合S??a,b,c?，S上所有互不相同的等價(jià)關(guān)系的數(shù)目為。

7．R是非空集合上的偏序關(guān)系，當(dāng)且僅當(dāng)R具有

8．僅用聯(lián)結(jié)詞?來表示P?Q為。

二、解答題（共24分）。

1． 求等價(jià)于下面公式的前束合取范式與前束析取范式。（10分）??x??P?x????y????z?Q?x,y???(?z)R(y,x)??

2． 整數(shù)集合Z上的二元運(yùn)算*定義為x*y判斷?Z,*?是不?x?y?2，是群？如果是，求出它的單位元以及每個(gè)元素的逆元。（8分）

3． 設(shè)A,B,C是三個(gè)集合，函數(shù)f:A?B，函數(shù)g:B?C。若函數(shù)

g?f:A?C是雙射，則f和g一定都是雙射函數(shù)嗎？若是，請(qǐng)給出證明；若否，請(qǐng)舉例說明。（6分）

三、證明題（共40分）

1．（10分）構(gòu)造下面推理的證明（個(gè)體域取學(xué)生的集合）：

每個(gè)一年級(jí)學(xué)生至少有一個(gè)高年級(jí)學(xué)生作他的輔導(dǎo)員。凡理科學(xué)生的輔導(dǎo)員皆是理科學(xué)生。小王是理科一年級(jí)學(xué)生。因此，至少有一個(gè)理科高年級(jí)學(xué)生。

2．（8分）證明在至少含有3個(gè)節(jié)點(diǎn)的簡(jiǎn)單連通平面圖中，至少有一個(gè)節(jié)點(diǎn)的度數(shù)小于等于5。

3．4． 證明命題的等價(jià)關(guān)系：證明在無(wú)向完全圖Kn

頓圖。（6分）

5． 設(shè)G為群，?P?Q????P?Q????P?Q?（8分）?n?3?中任意刪去3條邊后，所得到的圖是哈密f:G?G，?x?G有f?x??x?1。證明當(dāng)且僅當(dāng)G是

交換群，f是G的自同構(gòu)。（8分）

第五篇：離散數(shù)學(xué)試題+答案

004km.cn 專注于收集各類歷年試卷和答案

一、單項(xiàng)選擇題(本大題共15小題，每小題1分，共15分)在每小題列出的四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)是符合題目要求的，請(qǐng)將正確選項(xiàng)前的字母填在題后的括號(hào)內(nèi)。1.一個(gè)連通的無(wú)向圖G，如果它的所有結(jié)點(diǎn)的度數(shù)都是偶數(shù)，那么它具有一條（）A.漢密爾頓回路

B.歐拉回路 C.漢密爾頓通路

D.初級(jí)回路

2.設(shè)G是連通簡(jiǎn)單平面圖，G中有11個(gè)頂點(diǎn)5個(gè)面，則G中的邊是（）A.10

B.12

C.16

D.14 3.在布爾代數(shù)L中，表達(dá)式(a∧b)∨(a∧b∧c)∨(b∧c)的等價(jià)式是（）A.b∧(a∨c)B.(a∧b)∨(a’∧b)C.(a∨b)∧(a∨b∨c)∧(b∨c)D.(b∨c)∧(a∨c)4.設(shè)i是虛數(shù)，·是復(fù)數(shù)乘法運(yùn)算，則G=<{1,-1,i,-i},·>是群，下列是G的子群是（）A.<{1},·>

B.〈{-1},·〉

C.〈{i},·〉

D.〈{-i},·〉

5.設(shè)Z為整數(shù)集，A為集合，A的冪集為P(A),+、-、/為數(shù)的加、減、除運(yùn)算，∩為集合的交運(yùn)算，下列系統(tǒng)中是代數(shù)系統(tǒng)的有（）A.〈Z，+，/〉

B.〈Z，/〉 C.〈Z，-，/〉

D.〈P(A)，∩〉 6.下列各代數(shù)系統(tǒng)中不含有零元素的是（）A.〈Q，*〉Q是全體有理數(shù)集，*是數(shù)的乘法運(yùn)算

B.〈Mn(R),*〉,Mn(R)是全體n階實(shí)矩陣集合，*是矩陣乘法運(yùn)算 C.〈Z，?〉，Z是整數(shù)集，?定義為x?xy=xy,?x,y∈Z D.〈Z，+〉，Z是整數(shù)集，+是數(shù)的加法運(yùn)算

7.設(shè)A={1,2,3}，A上二元關(guān)系R的關(guān)系圖如下： R具有的性質(zhì)是 A.自反性 B.對(duì)稱性 C.傳遞性 D.反自反性

8.設(shè)A={a,b,c}，A上二元關(guān)系R={〈a,a〉，〈b,b〉〈,a,c〉}，則關(guān)系R的對(duì)稱閉包S(R)是（）A.R∪IA

B.R

C.R∪{〈c,a〉}

D.R∩IA 9.設(shè)X={a,b,c},Ix是X上恒等關(guān)系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R為X上的等價(jià)關(guān)系，R應(yīng)取（）A.｛〈c,a〉，〈a,c〉｝

B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉}

D.{〈a,c〉，〈c,b〉} 10.下列式子正確的是（）A.?∈?

B.???

C.{?}??

D.{?}∈?

11.設(shè)解釋R如下：論域D為實(shí)數(shù)集，a=0,f(x,y)=x-y,A(x,y):x

004km.cn 專注于收集各類歷年試卷和答案

D.(?x)(?y)(A(x,y)→A(f(x,a),a))12.設(shè)B是不含變?cè)獂的公式，謂詞公式(?x)(A(x)→B)等價(jià)于（）A.(?x)A(x)→B

B.(?x)A(x)→B C.A(x)→B

D.(?x)A(x)→(?x)B 13.謂詞公式(?x)(P(x,y))→(?z)Q(x,z)∧(?y)R(x,y)中變?cè)獂（）A.是自由變?cè)皇羌s束變?cè)?B.既不是自由變?cè)植皇羌s束變?cè)?C.既是自由變?cè)质羌s束變?cè)?D.是約束變?cè)皇亲杂勺冊(cè)?/p>

14.若P：他聰明；Q：他用功；則“他雖聰明，但不用功”，可符號(hào)化為（）A.P∨Q

B.P∧┐Q

C.P→┐Q

D.P∨┐Q 15.以下命題公式中，為永假式的是（）A.p→(p∨q∨r)

B.(p→┐p)→┐p C.┐(q→q)∧p

D.┐(q∨┐p)→(p∧┐p)

二、填空題(每空1分，共20分)16.在一棵根樹中，僅有一個(gè)結(jié)點(diǎn)的入度為______，稱為樹根，其余結(jié)點(diǎn)的入度均為______。17.A={1,2,3,4}上二元關(guān)系R={〈2，4〉，〈3，3〉，〈4，2〉}，R的關(guān)系矩陣MR中m24=______,m34=______。18.設(shè)〈s,*〉是群，則那么s中除______外，不可能有別的冪等元；若〈s,*〉有零元，則|s|=______。19.設(shè)A為集合，P(A)為A的冪集，則〈P(A)，是格，若x,y∈P(A),則x,y最大下界是______，?〉最小上界是______。

20.設(shè)函數(shù)f:X→Y,如果對(duì)X中的任意兩個(gè)不同的x1和x2，它們的象y1和y2也不同，我們說f是______函數(shù)，如果ranf=Y，則稱f是______函數(shù)。

21.設(shè)R為非空集合A上的等價(jià)關(guān)系，其等價(jià)類記為〔x〕R。?x,y∈A，若〈x,y〉∈R，則 〔x〕R與〔y〕R的關(guān)系是______，而若〈x,y〉?R，則〔x〕R∩〔y〕R=______。

22.使公式(?x)(?y)(A(x)∧B(y))?(?x)A(x)∧(?y)B(y)成立的條件是______不含有y，______不含有x。23.設(shè)M(x):x是人，D(s):x是要死的，則命題“所有的人都是要死的”可符號(hào)化為(?x)______,其中量詞(?x)的轄域是______。24.若H1∧H2∧?∧Hn是______，則稱H1,H2,?Hn是相容的，若H1∧H2∧?∧Hn是______，則稱H1,H2,?Hn是不相容的。

25.判斷一個(gè)語(yǔ)句是否為命題，首先要看它是否為，然后再看它是否具有唯一的。

三、計(jì)算題(共30分)26.(4分)設(shè)有向圖G=(V,E)如下圖所示，試用鄰接矩陣方法求長(zhǎng)度為2的路的總數(shù)和回路總數(shù)。

27.(5)設(shè)A={a,b},P(A)是A的冪集，?是對(duì)稱差運(yùn)算，可以驗(yàn)證

是群。設(shè)n是正整數(shù)，求({a}-1{a})n?{a}-nn{a}n 28.(6分)設(shè)A={1,2,3,4,5},A上偏序關(guān)系

R={〈1，2〉，〈3，2〉，〈4，1〉，〈4，2〉，〈4，3〉，〈3，5〉，〈4，5〉}∪IA;

004km.cn 專注于收集各類歷年試卷和答案

(1)作出偏序關(guān)系R的哈斯圖

(2)令B={1,2,3,5}，求B的最大，最小元，極大、極小元，上界，下確界，下界，下確界。29.(6分)求┐(P→Q)?(P→┐Q)的主合取范式并給出所有使命題為真的賦值。

30.(5分)設(shè)帶權(quán)無(wú)向圖G如下，求G的最小生成樹T及T的權(quán)總和，要求寫出解的過程。

31.(4分)求公式┐((?x)F(x,y)→(?y)G(x,y))∨(?x)H(x)的前束范式。

四、證明題(共20分)32.(6分)設(shè)T是非平凡的無(wú)向樹，T中度數(shù)最大的頂點(diǎn)有2個(gè)，它們的度數(shù)為k(k≥2),證明T中至少有2k-2片樹葉。

33.(8分)設(shè)A是非空集合，F(xiàn)是所有從A到A的雙射函數(shù)的集合，?是函數(shù)復(fù)合運(yùn)算。

證明：〈F, ?〉是群。

34.(6分)在個(gè)體域D={a1,a2,?，an}中證明等價(jià)式：

(?x)(A(x)→B(x))?(?x)A(x)→(?x)B(x)

五、應(yīng)用題(共15分)35.(9分)如果他是計(jì)算機(jī)系本科生或者是計(jì)算機(jī)系研究生，那么他一定學(xué)過DELPHI語(yǔ)言而且學(xué)過C++語(yǔ)言。只要他學(xué)過DELPHI語(yǔ)言或者C++語(yǔ)言，那么他就會(huì)編程序。因此如果他是計(jì)算機(jī)系本科生，那么他就會(huì)編程序。請(qǐng)用命題邏輯推理方法，證明該推理的有效結(jié)論。

36.(6分)一次學(xué)術(shù)會(huì)議的理事會(huì)共有20個(gè)人參加，他們之間有的相互認(rèn)識(shí)但有的相互不認(rèn)識(shí)。但對(duì)任意兩個(gè)人，他們各自認(rèn)識(shí)的人的數(shù)目之和不小于20。問能否把這20個(gè)人排在圓桌旁，使得任意一個(gè)人認(rèn)識(shí)其旁邊的兩個(gè)人?根據(jù)是什么?

參考答案

一、單項(xiàng)選擇題(本大題共15小題，每小題1分，共15分)

1.B

2.D

3.A

4.A

5.D

6.D

7.D

8.C

9.D

10.B

11.A

12.A

13.C

14.B

15.C

二、填空題 16.0 17.1

0 18.單位元

19.x∩y

x∪y 20.入射

滿射

21.［x］R=［y］R

 22.A(x)

B(y)23.(M(x)→D(x))

M(x)→D(x)

004km.cn 專注于收集各類歷年試卷和答案

24.可滿足式

永假式(或矛盾式)25.陳述句

真值

三、計(jì)算題

?1100??1010???26.M=??

1011????0011???2?2?M=??2??1110?111???

121?011??M2ij?18,ij?6 ?M2i?1??i?1j?144

G中長(zhǎng)度為2的路總數(shù)為18，長(zhǎng)度為2的回路總數(shù)為6。

27.當(dāng)n是偶數(shù)時(shí)，?x∈P(A),xn=?

當(dāng)n是奇數(shù)時(shí)，?x∈P(A),xn=x

于是：當(dāng)n是偶數(shù)，(｛a｝-1｛b｝｛a｝)n?｛a｝-n｛b｝n｛a｝n

=??(｛a｝-1)n｛b｝n｛a｝n=?????

當(dāng)n是奇數(shù)時(shí)，(｛a｝-1｛b｝｛a｝)n?｛a｝-n｛b｝n｛a｝n

=｛a｝-1｛b｝｛a｝?(｛a｝-1)n｛b｝n｛a｝n

=｛a｝-1｛b｝｛a｝?｛a｝-1｛b｝｛a｝=? 28.(1)偏序關(guān)系R的哈斯圖為

(2)B的最大元：無(wú)，最小元：無(wú)；

極大元：2，5，極小元：1，3

下界：4，下確界4；

上界：無(wú)，上確界：無(wú)

29.原式?(┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(P→Q))

((P→Q)∨(P→┐Q))∧(┐(P→┐Q)∨┐(P→Q))

(┐P∨Q∨┐P∨┐Q)∧(┐(┐P∨┐Q)∨(P∧┐Q))

(┐(P∧┐Q)∨(P∧┐Q))

(P∧Q)∨(P∧┐Q)

P∧(Q∨┐Q)

P∨(Q∧┐Q)

(P∨Q)∧(P∨┐Q)

命題為真的賦值是P=1,Q=0和P=1,Q=1

004km.cn 專注于收集各類歷年試卷和答案

30.令e1=(v1,v3)，e2=(v4,v6)

e3=(v2,v5)，e4=(v3,v6)

e5=(v2,v3)，e6=(v1,v2)

e7=(v1,v4)，e8=(v4,v3)

e9=(v3,v5)，e10=(v5,v6)

令ai為ei上的權(quán)，則

a1

取a1的e1∈T,a2的e2∈T,a3的e3∈T,a4的e4∈T,a5的e5∈T,即，T的總權(quán)和=1+2+3+4+5=15 31.原式?┐(?x1F(x1,y)→?y1G(x,y1))∨?x2H(x2)

(換名)

?┐?x1?y1(F(x1,y)→G(x,y1))∨?x2H(x2)

??x1?y1┐(F(x1,y1)→G(x,y1))∨?x2H(x2)

??x1?y1?x2(┐(F(x1,y1)→G(x,y1))∨H(x2)

四、證明題

32.設(shè)T中有x片樹葉，y個(gè)分支點(diǎn)。于是T中有x+y個(gè)頂點(diǎn)，有x+y-1 條邊，由握手定理知T中所有頂點(diǎn)的度數(shù)之的

x?y

?d(vi)=2(x+y-1)。

i?又樹葉的度為1，任一分支點(diǎn)的度大于等于2

且度最大的頂點(diǎn)必是分支點(diǎn)，于是

x?y

?d(vi)≥x·1+2(y-2)+k+k=x+2y+2K-4 i?1

從而2(x+y-1)≥x+2y+2k-4

x≥2k-2 33.從定義出發(fā)證明：由于集合A是非空的，故顯然從A到A的雙射函數(shù)總是存在的，如A上恒等函數(shù)，因此F非空

(1)?f,g∈F,因?yàn)閒和g都是A到A的雙射函數(shù)，故f?g也是A到A的雙射函數(shù)，從而集合F關(guān)于運(yùn)算?是封閉的。

(2)?f,g,h∈F,由函數(shù)復(fù)合運(yùn)算的結(jié)合律有f?(g?h)=(f?g)?h故運(yùn)算?是可結(jié)合的。

(3)A上的恒等函數(shù)IA也是A到A的雙射函數(shù)即IA∈F,且?f∈F有IA?f=f?IA=f,故IA是〈F，?〉中的幺元

(4)?f∈F,因?yàn)閒是雙射函數(shù)，故其逆函數(shù)是存在的，也是A到A的雙射函數(shù)，且有f?f-1=f-1?f=IA,因此f-1是f的逆元

由此上知〈F，?〉是群

34.證明(?x)(A(x)→B(x))? ?x(┐A(x)∨B(x))

004km.cn 專注于收集各類歷年試卷和答案

?(┐A(a1)∨B(a1))∨(┐A(a2)∨B(a2))∨?∨(┐A(an)∨B(an)))

?(┐A(a1)∨A(a2)∨?∨┐A(an)∨(B(a1)∨B(a2)∨?∨(B(an))

?┐(A(a1)∧A(a2)∧?∧A(an))∨(┐B(a1)∨B(a2)∨?∨(B(an))

?┐(?x)A(x)∨(?x)B(x)?(?x)A(x)→(?x)B(x)

五、應(yīng)用題

35.令p：他是計(jì)算機(jī)系本科生

q：他是計(jì)算機(jī)系研究生

r：他學(xué)過DELPHI語(yǔ)言

s:他學(xué)過C++語(yǔ)言

t:他會(huì)編程序

前提：(p∨q)→(r∧s),(r∨s)→t

結(jié)論：p→t

證①p

P(附加前提)

②p∨q

T①I

③(p∨q)→(r∧s)

P(前提引入)

④r∧s

T②③I

⑤r

T④I

⑥r(nóng)∨s

T⑤I

⑦(r∨s)→t

P(前提引入)

⑧t

T⑤⑥I 36.可以把這20個(gè)人排在圓桌旁，使得任一人認(rèn)識(shí)其旁邊的兩個(gè)人。

根據(jù)：構(gòu)造無(wú)向簡(jiǎn)單圖G=,其中V={v1,v2,?，V20}是以20個(gè)人為頂點(diǎn)的集合，E中的邊是若任兩個(gè)人vi和vj相互認(rèn)識(shí)則在vi與vj之間連一條邊。

?Vi∈V,d(vi)是與vi相互認(rèn)識(shí)的人的數(shù)目，由題意知?vi,vj∈V有d(vi)+d(vj)?20,于是G中存在漢密爾頓回路。

設(shè)C=Vi1Vi2?Vi20Vi1是G中一條漢密爾頓回路，按這條回路的順序按其排座位即符合要求。