第一篇：離散數(shù)學試題

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

月

一、單項選擇題（每小題3分，本題共15分）

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

A．2?AB．{1}?A

C．1?AD．2 ? A

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

()．

A．6B．4C．3D．

53．設無向圖G的鄰接矩陣為

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

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

A．1B．7C．6D．14 4．設集合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．若無向樹T有5個結點，則T的邊數(shù)為．

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

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

10．(?x)(A(x)→B(x，z)∨C(y))中的自由變元有．

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

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

12．將語句“他去操場鍛煉，僅當他有時間．”翻譯成命題公式．

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

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

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

14．設G是一個有4個結點10條邊的連通圖，則G為平面圖．

五．計算題（每小題12分，本題共36分）

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

16．設A={{1}, 1, 2}，B={ 1, {2}}，試計算

（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)}，對應邊的權值依次為1、2、3、1、4及5，試

（1）畫出G的圖形；

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

（3）求出G權最小的生成樹及其權值．

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

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

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

試題解答

(供參考)

一、單項選擇題（每小題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．設P：今天上課，（2分）則命題公式為：P．（6分）

12．設 P：他去操場鍛煉，Q：他有時間，（2分）則命題公式為：P ?Q．（6分）

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

13．錯誤．（3分）因為A中元素2沒有B中元素與之對應，故f不是A到B的函數(shù)．（7分）

14．錯誤．（3分）不滿足“設G是一個有v個結點e條邊的連通簡單平面圖，若v≥3，則e≤3v-6．”（7分）

五．計算題（每小題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

權為：1+1+3=5

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

18．證明：設?x?A，因為R自反，所以x R x，即< x, x>?R；

又因為S自反，所以x R x，即< x, x >?S．即< x, x>?R∩S故R∩S自反．

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

第二篇：08離散數(shù)學試題

離散數(shù)學試題

一、填空（共36分）

1、命題公式P?Q的真值為假，當且僅當。

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

3、設10階平面圖G有5個面，則G中有條邊。

4．設A={1，2，3，4，5，6，7}，R是A上的模4同余關系，則關系R＝。

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

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

7．R是非空集合上的偏序關系，當且僅當R具有

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

二、解答題（共24分）。

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

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

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

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

三、證明題（共40分）

1．（10分）構造下面推理的證明（個體域取學生的集合）：

每個一年級學生至少有一個高年級學生作他的輔導員。凡理科學生的輔導員皆是理科學生。小王是理科一年級學生。因此，至少有一個理科高年級學生。

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

3．4． 證明命題的等價關系：證明在無向完全圖Kn

頓圖。（6分）

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

交換群，f是G的自同構。（8分）

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

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

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

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

D.初級回路

2.設G是連通簡單平面圖，G中有11個頂點5個面，則G中的邊是（）A.10

B.12

C.16

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

B.〈{-1},·〉

C.〈{i},·〉

D.〈{-i},·〉

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

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

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

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

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

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

B.R

C.R∪{〈c,a〉}

D.R∩IA 9.設X={a,b,c},Ix是X上恒等關系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R為X上的等價關系，R應?。ǎ〢.｛〈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.設解釋R如下：論域D為實數(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.設B是不含變元x的公式，謂詞公式(?x)(A(x)→B)等價于（）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)中變元x（）A.是自由變元但不是約束變元 B.既不是自由變元又不是約束變元 C.既是自由變元又是約束變元 D.是約束變元但不是自由變元

14.若P：他聰明；Q：他用功；則“他雖聰明，但不用功”，可符號化為（）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.在一棵根樹中，僅有一個結點的入度為______，稱為樹根，其余結點的入度均為______。17.A={1,2,3,4}上二元關系R={〈2，4〉，〈3，3〉，〈4，2〉}，R的關系矩陣MR中m24=______,m34=______。18.設〈s,*〉是群，則那么s中除______外，不可能有別的冪等元；若〈s,*〉有零元，則|s|=______。19.設A為集合，P(A)為A的冪集，則〈P(A)，是格，若x,y∈P(A),則x,y最大下界是______，?〉最小上界是______。

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

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

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

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

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

27.(5)設A={a,b},P(A)是A的冪集，?是對稱差運算，可以驗證

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

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

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

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

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

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

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

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

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

證明：〈F, ?〉是群。

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

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

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

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

參考答案

一、單項選擇題(本大題共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.陳述句

真值

三、計算題

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

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

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

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

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

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

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

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

當n是奇數(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)偏序關系R的哈斯圖為

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

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

下界：4，下確界4；

上界：無，上確界：無

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上的權，則

a1

取a1的e1∈T,a2的e2∈T,a3的e3∈T,a4的e4∈T,a5的e5∈T,即，T的總權和=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.設T中有x片樹葉，y個分支點。于是T中有x+y個頂點，有x+y-1 條邊，由握手定理知T中所有頂點的度數(shù)之的

x?y

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

i?又樹葉的度為1，任一分支點的度大于等于2

且度最大的頂點必是分支點，于是

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,因為f和g都是A到A的雙射函數(shù)，故f?g也是A到A的雙射函數(shù)，從而集合F關于運算?是封閉的。

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

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

(4)?f∈F,因為f是雙射函數(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)

五、應用題

35.令p：他是計算機系本科生

q：他是計算機系研究生

r：他學過DELPHI語言

s:他學過C++語言

t:他會編程序

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

結論：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個人排在圓桌旁，使得任一人認識其旁邊的兩個人。

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

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

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

第四篇：離散數(shù)學試題A卷

離散數(shù)學試題A卷

一、單項選擇題（本大題共10小題，每小題2分，共20分）

1．下列命題公式中不是重言式的是（）．

A．p→(q→r)

C．p→(p→p)B．p→(q→p)D．(p→(q→r))(q→(p→r))

2．設個體域是整數(shù)集，則下列命題的真值為真的是（）

A．yx(x·y=1)

C．xy(x·y=y2)B．xy(x·y≠0)D．yx(x·y=x2)

3．關于謂詞公式（x）(y)(P(x,y)∧Q(y,z))∧

(x)p(x,y),下面的描述中錯誤的是（）．．

A．（x）的轄域是（y）（P（x,y）∧Q(y,z)）

B．z是該謂詞公式的約束變元

C．（x）的轄域是P（x,y）D．x是該謂詞公式的約束變元

4．設有代數(shù)系統(tǒng)G=〈A，*〉，其中A是所有命題公式的集合，*為命題公式的合取運算，則G的幺元是（）

A．矛盾式

C．可滿足式 B．重言式 D．公式p∧q

5．設A={?}，B=P（P（A）），以下不正確的式子是（）．

A．{{? }，{{? }}，{?，{? }}}包含于B

C．{{?，{? }}}包括于B B．{{{? }}}包含于B D．{{? }，{{?，{? }}}}包含于B

6．設Z是整數(shù)集，E={…，-4，-2，0，2，4，…}，f：Z→E，f（x）=2x，則f（）

A．僅是滿射

C．是雙射 B．僅是入射 D．無逆函數(shù)

7．設A={1，2，3，4，5}，A上二元關系R={〈1，2〉，〈3，4〉，〈2，2〉}，S={〈2，4〉，〈3，1〉，〈4，2〉}，則S-1?R-1的運算結果是（）

A．{〈4，1〉，〈2，3〉，〈4，2〉} C．{〈4，1〉，〈2，3〉，〈2，4〉}

B．{〈2，4〉，〈2，3〉，〈4，2〉} D．{〈2，2〉，〈3，1〉，〈4，4〉}

8．在實數(shù)集合R上，下列定義的運算中不可結合的是（）．A．a(chǎn)*b=a+b+2ab C．a(chǎn)*b=a+b+ab

B．a(chǎn)*b=a+b D．a(chǎn)*b=a-b

9．設無向圖中有6條邊，有一個3度頂點和一個5度頂點，其余頂點度為2，則該圖的頂點數(shù)是（）A．3 C．

5B．4 D．6

10．設無向圖G的邊數(shù)為m，結點數(shù)為n，則G是樹等價于（）A．G連通且m=n+1 C．G連通且m=2n

B．G連通且n=m+

1D．每對結點之間至少有一條通路

二、填空題（本大題共10小題，每小題2分，共20分）

11．不能再分解的命題稱為____________，至少包含一個聯(lián)結詞的命題稱為____________。

12．在命題演算中，五個聯(lián)結詞的含義是由其____________表唯一確定的，而不是由其類似的____________

語言的含義確定。

13．使公式（x）（y）（A（x）→B（y））?（（x）A（x）→（y）B（y））成立的條件是____________

不含有y，____________不含有x。

14．設A為任意集合，請?zhí)钊脒m當?shù)倪\算符，使式子A____________A=?；A____________~A=?成立。15．設A={0，1，2，3，6}，R={〈x,y〉|x≠y∧(x,y∈A)∧y≡x(mod 3)}，則domR=____________，ranR=____________。

16．稱集合S是給定非空集合A的覆蓋：若S={S1，S2，…，Sn}，其中Si?A，Si≠?，i=1，2，…，n，且____________；進一步若____________，則S是集合A的劃分。

17．對實數(shù)的普通加法和乘法，____________是加法的冪等元，____________是乘法的冪等元。18．在代數(shù)系統(tǒng)〈A，*〉中，A={a}，*是A上二元運算，則該代數(shù)系統(tǒng)的單位元是____________，零元

是____________。

19．設〈A，?〉是偏序集，若A中____________都有最小上界和____________則稱A關于偏序?構成格。20．若一條路中，所有邊均不相同，則此路稱作____________；若一條路中所有的結點均不相同，則稱此

路為____________。

三、計算題（本大題共5小題，每小題6分，共30分）21．求命題公式(P?Q)?(?P??Q)的真值表。

22．試求謂詞公式?x(P(x)??xQ(x,y)??yR(x,y))?A(x,y)中，?x,?x,?y的轄域，試問R(x,y)和A(x,y)

中x,y是自由變元，還是約束變元？

23．求命題公式（p→q）→（q∨p）的主析取范式。

24．設代數(shù)系統(tǒng)(Z,*)，其中Z是整數(shù)集，二元運算定義為?a,b?Z,a*b?a?b?2，?a?Z，求a的逆元。

25．已知圖D(如下圖)的鄰接矩陣為

v1v2v3v

01

求從v2到v4長度為2和從v3到v3長度為2的通路條數(shù)，并將它們具體寫出。

v1?0

A(D)=v2?1

?v3?0?v4?1

1??0 ?1??0?

四、證明題（本大題共2小題，每小題6分，共12分）

26．設〈{a,b},*〉是半群，其中a*a=b，證明：（1）a*b=b*a；（2）b*b=b。

27．若一棵樹恰有2個結點的度數(shù)為1，則它必是一條歐拉路。

五、應用題（本大題共3小題，每小題6分，共18分）

28．設I是整數(shù)集，<，>，＝，?，?，≠是Ｉ上的二元關系，分別表示小于，大于、等于、小于等于，大于等于，不等于，那么這些關系會滿足什么性質(zhì)？試填寫下表。

29.完成下列推理：只要今天天氣不好，就一定有考生不能提前進入考場，當且僅當所有考生提前進入考場，考試才能準時進行。所以，如果考試準時進行，那么天氣就好。

30．75個兒童到公園游樂場，他們在那里可以騎旋轉(zhuǎn)木馬，坐滑行鐵道，乘宇宙飛船，已知其中20人這

三種東西都乘過，其中55人至少乘坐過其中的兩種。若每樣乘坐一次的費用是0.5元，公園游樂場 總共收入70元，求有多少兒童沒有乘坐過其中任何一種。

第五篇：離散數(shù)學試題及解答

離散數(shù)學

2^m*n

一、選擇題（2*10）

1．令P：今天下雨了，Q：我沒帶傘，則命題“雖然今天下雨了，但是我沒帶傘”可符號化為（（A）P→?Q（C）P∧Q）。

（B）P∨?Q（D）P∧?Q

2．下列命題公式為永真蘊含式的是（）。

（A）Q→（P∧Q）（B）P→（P∧Q）（C）（P∧Q）→P（D）（P∨Q）→Q

3、命題“存在一些人是大學生”的否定是(A)，而命題“所有的人都是要死的”的否定是（）。

（A）所有人都不是大學生，有些人不會死（B）所有人不都是大學生，所有人都不會死（C）存在一些人不是大學生，有些人不會死（D）所有人都不是大學生，所有人都不會死

4、永真式的否定是（）。

（A）永真式（B）永假式

（C）可滿足式（D）以上均有可能

5、以下選項中正確的是（）。

（A）0= ?

（B）0 ? ?

（C）0∈?

（D）0??

6、以下哪個不是集合A上的等價關系的性質(zhì)？（）

（A）自反性

（B）有限性

（C）對稱性

（D）傳遞性

7、集合A={1,2,…,10}上的關系R={|x+y=10,x,y∈A}，則R的性質(zhì)為（）。

（A）自反的

（B）對稱的

（C）傳遞的，對稱的（D）傳遞的

8．設D=為有向圖，V={a, b, c, d, e, f}, E={, , , , }是（）。

（A）強連通圖（B）單向連通圖（C）弱連通圖（D）不連通圖

9、具有6個頂點，12條邊的連通簡單平面圖中，每個面都是由（）條邊圍成？

（A）

2（B）4

（C）（D）5 10．連通圖G是一棵樹，當且僅當G中（）。

（A）有些邊不是割邊（B）每條邊都是割邊（C）無割邊集

（D）每條邊都不是割邊

二、填空題（2*10）

1、命題“2是偶數(shù)或-3是負數(shù)”的否定是________。

2、設全體域D是正整數(shù)集合，則命題?x?y(xy=y)的真值是______。

3、令R(x):x是實數(shù)，Q(x):x是有理數(shù)。則命題“并非每個實數(shù)都是有理數(shù)”的符號化表示為________。

4、公式(?P?Q)?(?P??Q)化簡為________。

5、設A∩B=A∩C，A∩B=A∩C，則B________C。

6、設A={2,4,6}，A上的二元運算*定義為：a*b=max{a,b}，則在獨異點中，單位元是________，零元是________。

7、任一有向圖中，度數(shù)為奇數(shù)的結點有________(奇數(shù)/偶數(shù))個。8．如下無向圖割點是________，割邊是________。

三、（10分）設A、B和C是三個集合，則A?B??(B?A)。

四、（15分）某項工作需要派A、B、C和D 4個人中的2個人去完成，按下面3個條件，有幾種派法？如何派？(1)若A去，則C和D中要去1個人；(2)B和C不能都去；(3)若C去，則D留下

五、（15分）設A={1,2,3},寫出下列圖示關系的關系矩陣，并討論它們的性質(zhì)：

六、（20分）畫一個圖使它分別滿足：（1）有歐拉回路和哈密爾頓回路；（2）有歐拉回路，但無條哈密爾頓回路；（3）無歐拉回路，但有哈密爾頓回路；（4）既無歐拉回路，又無哈密爾頓回路。

A C

B A C

B A C B 答案：

一、選擇題：

2、C

7、B

3、A

8、C

4、B

9、C

5、D

10、B

1、D

6、B

二、填空： 1、2不是偶數(shù)且-3不是負數(shù)

2、F

3、??x(R(x)?Q(x))

4、?P

5、等于 6、2，6

7、偶數(shù)

8、d，e5

三、證明：

A?B??x(x∈A→x∈B)∧?x(x∈B∧x?A)??x(x?A∨x∈B)∧?x(x∈B∧x?A)???x(x∈A∧x?B)∧??x(x?B∨x∈A)???x(x∈A∧x?B)∨??x(x∈A∨x?B)??(?x(x∈A∧x?B)∧?x(x∈A∨x?B))??(?x(x∈A∧x?B)∧?x(x∈B→x∈A))??(B?A)。

四、解

設A：A去工作；B：B去工作；C：C去工作；D：D去工作。則根據(jù)題意應有：A?C?D，?(B∧C)，C??D必須同時成立。因此(A?C?D)∧?(B∧C)∧(C??D)?(?A∨(C∧? D)∨(?C∧D))∧(?B∨?C)∧(?C∨?D)?(?A∨(C∧? D)∨(?C∧D))∧((?B∧?C)∨(?B∧?D)∨?C∨(?C∧?D))?(?A∧?B∧?C)∨(?A∧?B∧?D)∨(?A∧?C)∨(?A∧?C∧?D)∨(C∧? D∧?B∧?C)∨(C∧? D∧?B∧?D)∨(C∧? D∧?C)∨(C∧? D∧?C∧?D)∨(?C∧D∧?B∧?C)∨(?C∧D∧?B∧?D)∨(?C∧D∧?C)∨(?C∧D∧?C∧?D)?F∨F∨(?A∧?C)∨F∨F∨(C∧? D∧?B)∨F∨F∨(?C∧D∧?B)∨F∨(?C∧D)∨F ?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D∧?B)∨(?C∧D)?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D)?T 故有三種派法：B∧D，A∧C，A∧D。

五、?000???（1）R={<2,1>,<3,1>,<2,3>};MR=?101?;它是反自反的、反對稱的、傳遞的；

?100????011???（2）R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>};MR=?101?;它是反自反的、?110???對稱的；

?011???（3）R={<1,2>,<2,1>,<1,3>,<3,3>};MR=?100?;它既不是自反的、反自反的、?001???也不是對稱的、反對稱的、傳遞的。

六、