離散數學試卷2【精品多篇】

離散數學試卷 篇一

誠信應考，考試作弊將帶來嚴重後果！華南理工大學期末考試 《離散數學》試卷A 注意事項：1.考前請將密封線內填寫清楚；2.所有答案請直接答在試卷上；3．考試形式：閉卷；4.本試卷共五大題，滿分100分，考試時間120分鐘

一、填空題（本大題共12小題，每小題2分，共24分）1．求合式公式xP（x)→xQ(x,y)的前束範式________________。2．設集合A={a, b, {a,b}， }， B = {{a,b}， }，求B-A=_____________． 3．設p與q的真值為0,r,s的真值為1則命題(s(q(rp)）)（rp)的真值是__________.4．設R是在正整數集合Z上如下定義的二元關係Rx,y(x,yZ)(xy1，0)則它一共有個有序對，且有自反性、對稱性、傳遞性、反自反性和反對稱性各性質中的性質。5．公式x(P(x)→Q(x,y)）→S(x)中的自由變元為________________，約束變元為________________。6．設有命題T(x): x 是火車，C(x): x是汽車，Q(x, y): x跑得比y快，那麼命題“有的汽車比一些火車跑得快”的邏輯表達式是______________________.7．設G是n階m條邊的無向圖，若G連通且m=__________則G是無向樹。8．設X={1，2，3}，f：X→X，g：X→X，f={，,}，g={，,}，則f-1g=________________，gf=________________。9.不能再分解的命題稱為________________，至少包含一個聯結詞的命題稱為《離散數學》試卷A

________________．

10、連通無向圖G含有歐拉回路的充分必要條件是 11．設集合A={，{a}}，則A的冪集P(A，|P(A)|=_____________________________。

12、設G = ， G’ = 為兩個圖（同為無向圖或有向圖）， 若E’  E且_______________, 則稱G’是G的子圖， 若E’  E且_______________, 則稱G’是G的生成子圖。

二、單選題（本大題共12小題，每小題2分，共26分）

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

A.(p∨┐p)→q．B．p→(p∨q)C．q∧┐qD．(p→p)→q

2．下列語句中為命題的是()

A．你好嗎？

B．人有6指。C．我所説的是假的。D．明天是晴天。3.設D=為有向圖，V={a, b, c, d, e, f}， E={，，,，}是（）

A．強連通圖

C．弱連通圖 B．單向連通圖 D．不連通圖

4．集合A＝{a，b，c}上的下列關係矩陣中符合偏序關係條件的是()

10

1011A．

001

11001011011110 B．010C．110D．010 11010010111

5．設A={1，2，3}，A上二元關係S={，，，}，則S是（）

A．自反關係 B．傳遞關係C．對稱關係D． 反自反關係

6、設A={a,b,c,d}，A上的等價關係R={，， ，}∪IA，則對應於R的A的劃分是（）

A．{{a}，{b, c}，{d}}

C．{{a}，{b}，{c}，{d}} B．{{a, b}，{c}， {d}} D．{{a, b}， {c,d}}

7、以下非負整數列可簡單圖化為一個歐拉圖的是()

A.{2, 2, 2, 2, 0}B.{4, 2, 6, 2, 2}

C.{2, 2, 3, 4, 1}D.{4, 2, 2, 4, 2}

8、設論域D＝{a，b }，與公式xA（x)等價的命題公式是(）

A．A(a)∧A(b)B．A(a)→A(b)C．A(a)∨A(b)D．A(b)→A(a)

9、一棵樹有3個4度頂點，4個2度頂點其餘都是樹葉，求這棵樹有多少個樹葉頂點()

A.12B.8C.10D.1

310、有ABC三個人猜測甲乙丙三個球隊中的冠軍。各人的猜測如下:

A: 冠軍不是甲，也不是乙。B: 冠軍不是甲，而是丙。C: 冠軍不是丙，而是甲。已知其中有一個人説的完全正確。一個人説的都不對，而另外一人恰有一半説對了。據此推算，冠軍應該是()

A．甲B.乙C.丙D.不確定

11．如第11題圖所示各圖，其中存在哈密頓迴路的圖是()

12．設C（x): x是國家級運動員，G(x): x是健壯的，則命題“沒有一個國家級運動員不是健壯的”可符號化為(）

（A)x(C(x)G(x)）（B)x(C(x)G(x)）

（C)x(C(x)G(x)）（D)x(C(x)G(x)）

三．計算題（30分）

1．用等值演算法求取求下列公式：（PQ）(P∨Q)的合取範式（5分）

2．圖G如下圖所示，求圖G的最小生成樹。（5分）

3．有向圖D如圖所示，求D的關聯矩陣M(D)（5分）

4、化簡表達式（（(A(BC））

A)（B(BA)）)(CA)（7分）

5．設R={，，，，，}，求r（R)和s(R)，並作出它們及R的關係圖(8分）

五．證明題（22分）

1．構造下面推理的證明（5分）

前提：pq，pr，st，sr，t

結論：q

2．設A={1, 2, 3, 4}， 在AA定義的二元關係R，u,v，x,yAA, uRxuy +xv

證明R是AA上的等價關係。（5分）

3．已知A、B、C是三個集合，證明A-(B∪C)=(A-B)∩(A-C)（6分）

4． 無向圖G = ，且|V|=n, |E|=m, 試證明以下兩個命題是等價命題

1）G中每對頂點間具有唯一的通路，2）G連通且n=m+1。（6分）

離散數學試卷1 篇二

離散數學試題（1）

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

在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題後的括號內。錯選、多選或未選均無分。

1．下列是兩個命題變元p，q的小項是（）

A．p∧┐p∧qB．┐p∨q

C．┐p∧qD．┐p∨p∨q

2．令p：今天下雪了，q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號化為（）

A．p→┐q

C．p∧q

B．p∨┐q D．p∧┐q B．x+y=10 D．x mod 3=2 3．下列語句中是命題的只有（）A．1+1=10C．sinx+siny<0

4．下列等值式不正確的是（）

A．┐（x）A（x）┐A

B．（x）（B→A(x)）B→（x）A(x)

C．（x）（A(x)∧B(x)）（x）A(x)∧（x）B(x)

D．（x）（y）（A(x)→B(y)）（x）A(x)→（y）B(y)

5．謂詞公式（x）P(x,y)∧（x）(Q(x,z)→（x）（y）R(x,y,z)中量詞x的轄域是（）

A．（x）Q（x,z)→（x）（y）R(x,y,z)）

B．Q(x,z)→（y）R(x,y,z)

C．Q(x,z)→（x）（y）R(x,y,z)

D．Q(x,z)

6．設R為實數集，函數f：R→R，f(x)=2x，則f是（）

A．滿射函數

C．雙射函數B．入射函數 D．非入射非滿射

7．設A={a,b,c,d}，A上的等價關係R={，，,}∪IA，則對應於R的A的劃

分是（）

A．{{a}，{b,c}，{d}}B．{{a,b}，{c}，{d}}

C．{{a}，{b}，{c}，{d}}D．{{a,b}，{c,d}}

8．設A={Ø}，B=P（P(A)），以下正確的式子是（）

A．{Ø，{Ø}}∈B

C．{{Ø}，{{Ø}}}∈BB．{{Ø，Ø}}∈B D．{Ø，{{Ø}}}∈B

9．設X，Y，Z是集合，一是集合相對補運算，下列等式不正確的是（）

A．(X-Y)-Z=X-(Y∩Z)

B．(X-Y)-Z=(X-Z)-Y

C．(X-Y)-Z=(X-Z)-(Y-Z)

D．(X-Y)-Z=X-(Y∪Z)

10．設*是集合A上的二元運算，稱Z是A上關於運算*的零元，若（）

A．xA,有x*Z=Z*x=Z

B．ZA，且xA有x*Z=Z*x=Z

C．ZA，且xA有x*Z=Z*x=x

D．ZA，且xA有x*Z=Z*x=Z

離散數學試題（1）

11．在自然數集N上，下列定義的運算中不可結合的只有（）

A．a*b=min(a,b)

B．a*b=a+b

C．a*b=GCD（a,b)(a,b的最大公約數）

D．a*b=a(mod b)

12．設R為實數集，R={x|x∈R∧x>0}，*是數的乘法運算，是一個羣，則下列集

合關於數的乘法運算構成該羣的子羣的是（）

A．{R中的有理數}

+C．{R中的自然數}

A．是交換羣 +++

B．{R中的無理數} D．{1，2，3} B．是加法羣 D．*對是可分配的 +13．設是環，則下列正確的是（）C．對*是可分配的14．下列各圖不是歐拉圖的是（）

15．設G是連通平面圖，G中有6個頂點8條邊，則G的面的數目是（）

A．2個面B．3個面

C．4個面D．5個面

第二部分非選擇題（共85分）

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

請在每小題的空格中填上正確答案。錯填、不填均無分。

16．一公式為之充分必要條件是其析取範式之每一析取項中均必同時包含一命題變元及其否定；一公式為之充分必要條件是其合取範式之每一合取項中均必同時包含 一命題變元及其否定。

17．前束範式具有形式(Q1V1)(Q2V2)„(QnVn)A，其中Qi(1≤i≤n)為，A為的謂詞公式。

18．設論域是{a,b,c}，則（x）S(x)等價於命題公式；（x）S(x)等價於命題公式。

19．設R為A上的關係，則R的自反閉包。

20．某集合A上的二元關係R具有對稱性，反對稱性，自反性和傳遞性，此關係R，其關係矩陣是。

21．設是一個偏序集，如果S中的任意兩個元素都有和，則稱S關於≤

構成一個格。

22．設Z是整數集，在Z上定義二元運算*為a*b=a+b+a·b，其中+和·是數的加法和乘法，則代數系統的幺元是，零元是。

23．如下平面圖有2個面R1和R2，其中deg(R1)=，deg(R2)=。

24．無向圖G具有一條歐拉回路，當且僅當G是。

25．在下圖中，結點v2的度數是，結點v5的度數是。

三、計算題（本大題共6小題，第26—27小題每小題4分，第28、30小題每小題5分，第29、31小題每小題6分，共30分）

26．（4分）求出從A={1,2}到B={x,y}的所有函數，並指出哪些是雙射函數，哪些是滿射函

數。

27．（4分）如果論域是集合{a,b,c}，試消去給定公式中的量詞：（y）（x）(xy0)。

28．（5分）設A={a,b,c }，P（A）是A的冪集，是集合對稱差運算。已知

是羣。

在羣

中，①找出其幺元。②找出任一元素的逆元。③求元素x使滿足{a}x={b}。

29．（6分）用等值演算法求公式┐(p→q)

(p→┐q)的主合取範式

30．（5分）畫出5個具有5個結點5條邊的非同構的無向連通簡單圖。

31．（6分）在偏序集中，其中Z={1,2,3,4,6,8,12,14}，≤是Z中的整除關係，求集合D={2,3,4,6}的極大元，極小元，最大元，最小元，最小上界和最大下界。

四、證明題（本大題共3小題，第32~33小題每小題6分，第34小題8分，共20分）

32．（6分）用等值演算法證明（（q∧s）→r)∧(s→(p∨r)）（s∧(p→q)）→r

33．（6分）設n階無向樹G=中有m條邊，證明m=n-1。

34．（8分）設P={Ø，{1}，{1,2}，{1,2,3}}，是集合P上的包含關係。

（1）證明：

是偏序集。

（2）在（1）的基礎上證明

是全序集

五、應用題(15分）

35．（9分）在謂詞邏輯中構造下面推理的證明：每個在學校讀書的人都獲得知識。所以如

果沒有人獲得知識就沒有人在學校讀書。（個體域：所有人的集合）

離散數學試卷二十三試題與答案 篇三

試卷二十三試題與答案

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

1．命題公式P(QP)是（）。

A、矛盾式；B、可滿足式；C、重言式；D、等價式。

2．下列各式中哪個不成立（）。

A、x（P(x)Q(x)）xP(x)xQ(x)；

B、x（P(x)Q(x)）xP(x)xQ(x)；

C、x（P(x)Q(x)）xP(x)xQ(x)；

D、x(P(x)Q)xP(x)Q。

3．謂詞公式x（P(x)yR(y)）Q(x)中的 x是（）。

A、自由變元；B、約束變元；

C、既是自由變元又是約束變元；D、既不是自由變元又不是約束變元。

4．在0 之間應填入（）符號。

A、=；B、；C、；D、。

5．設 是偏序集，BA，下面結論正確的是（）。

A、B的極大元bB且唯一；B、B的極大元bA且不唯一；

C、B的上界bB且不唯一；D、B的上確界bA且唯一。

6．在自然數集N上，下列（）運算是可結合的。

（對任意a,bN）

A、abab；B、abmax(a,b)；

C、aba5b；D、abab。

7．Q為有理數集N，Q上定義運算*為a*b = a + b – ab ，則的幺元為（A、a；B、b；C、1；D、0。

8．給定下列序列，（）可以構成無向簡單圖的結點度數序列。

A、（1，1，2，2，3）；B、（1，1，2，2，2）；

C、（0，1，3，3，3）；D、（1，3，4，4，5）。

9．設G是簡單有向圖，可達矩陣P(G)刻劃下列（）關係。

A、點與邊；B、邊與點；C、點與點；D、邊與邊。

10．一顆樹有兩個2度結點，1個3度結點和3個4度結點，則1度結點數為（A、5；B、7；C、9；D、8。

。）。）

二、填空：（每空1分，本大題共15分）

1．在自然數集中，偶數集為N1、奇數集為N2，則N1N2=；

N1N2 =。

2．設X{1,2,3,4}，R{1,2，2,4，3,3}，則

r(R)=；s(R)= ；t(R)=。

3．設R為集合A上的等價關係，對aA，集合[a]R=，稱

為

元

素

a

形

成的R

等

價

類，[a]R，因

為。

4．任意兩個不同小項的合取為，全體小項的析取式為。

5．設Q(x):x為偶數，P(x):x為素數，則下列命題：（1）存在唯一偶素數；（2）至多有一個偶素數；分別形式化：（1）；

（2）。

6．設T為根樹，若，則稱T為m元樹；

若則稱T為完全m叉樹。

7．含5個結點，4條邊的無向連通圖（不同構）有 個，它們是。

三、判斷改正題：（每小題2分，本大題共20分）

1．命題公式（A(AB)）B是一個矛盾式。（）2．任何循環羣必定是阿貝爾羣，反之亦真。（）3．根樹中最長路徑的端點都是葉子。（）4．若集合A上的關係R是對稱的，則R



1也是對稱的。（）

5．數集合上的不等關係（≠）可確定A的一個劃分。（）6．設集合A、B、C為任意集合，若A×B = A×C，則B = C。（）7．函數的複合運算“。”滿足結合律。（）8．若G是歐拉圖，則其邊數e合結點數v的奇偶性不能相反。（）9．圖G為（n ， m）圖，G的生成樹TG必有n個結點。（）10．使命題公式P(QR)的真值為F的真值指派的P、Q、R值分別是T、F、F。（）

四、簡答題（每小題5分，本大題共25分）

1．設H,和K,都是羣G,的子羣，問HK,和HK,是否是

G,的子並説明理由。

3，4，9}，B{2，4，7，10,12}，從A到B的關係 2．設A{2，R{a,baA,bB,且a整除b}，試給出R的關係圖和關係矩陣，並説明此

關係是否為函數？為什麼？

3．設S,是半羣，OL是左零元，對任xS,xOL是否是左零元？為什麼？

4．某次會議有20人蔘加，其中每人至少有10個朋友，這20人擬圍一桌入席，用圖論知識説明是否可能每人鄰做的都是朋友？（理由）

5．通過主合取範式，求出使公式（PQ）R的值為F的真值指派。

五、證明題：（共30分）

1．設R為集合A上的二元關係，如果R是反自反的和可傳遞的，則R一定是反對稱的。

2．試證明若G,是羣，HG，且任意的aH，對每一個xG，有axxa，則H,是G,的子羣。

3．設G是每個面至少由k（k3）條邊圍成的連通平面圖，試證明為結點數，e為邊數。

4．符號化下列各命題，並説明結論是否有效（用推理規則）。任何人如果他喜歡美術，他就不喜歡體育。每個人或喜歡體育，或喜歡音樂，有的人不喜歡音樂，因而有的人不喜歡美術。答案

e

k(v2)k

2，其中v

一、單項選擇題：

1．N

2;

。r(R){1,2，2,4，3,3，1,1，2,2，4,4}，2．

s(R){1,2，2,4，3,3，2,1，4,2}，RRR{1,4，3,3}，RRR{3,3}，RRR{3,3}，所以，t(R){1,2，2,4，3,3，1,4}。

3．[a]R{xxA,aRx}；a[a]R。4．永假式（矛盾式），永真式（重言式）。5．（1）x（（Q(x）P(x)）y（Q(y)P(y)xy)）。（2）xy(Q(x)P(x)Q(y)P(y)xy)。

6．每個結點的出度都小於等於m；除葉子外，每個結點的出度都等於m。7．3。

三、判斷改正題：

1．×命題公式（A(AB)）B是一個重言式。2．×任何循環羣必定是阿貝爾羣，但反之不真。3．×根樹中最長路徑的端點不都是葉子。

4．√5．×≠不能確定A的一個劃分。6．√7．√

8．×歐拉圖其邊數e和結點數v的奇偶性可以相反。9．√10．√

四、簡答題

1．解：HK,是 G,的子羣，HK,不一定是G,的子羣。a,bHK,則的子羣，a,bH,a,bK,由

H,和K,都是G,



ab



1H且ab

1

K,ab

1

HK,HK,是G,的子羣。

如：G = {1，5，7，11}，：模12乘，則G,為羣。且H = {1，5}，K = {1，7}，H,和K,皆為G,的子羣，但HK{1,5,7}，HK,不是G,的子羣。因為 5711HK，即運算不封閉。

2．解：R{2,2，2,4，2,10，2,12，3,12，4,4，4,12}則R的關係圖為： R的關係矩陣為

10

00

1010

0000

1000

1110

M

R

關係R不是A到B的函數，因為

元素2，4的象不唯一（或元素9無象）

3．解：xOL仍是左零元。因為yS，由於OL是左零元，所以，OLyOL，又S,為半羣，所以*可結合。

所以，(xOL)yx(OLy)xOL，所以，xOL仍是左零元。

4．解：可能。將人用結點表示，當兩人是朋友時相應結點間連一條邊，則得一個無向圖

GV,E，20人圍一桌，使每人鄰做都是朋友，即要找一個過每個點一次且僅

一次得迴路。由題已知，u,vV,deg(u)10,deg(v)10，deg(u)deg(v)20，由判定定理，G中存在一條漢密爾頓迴路。即所談情況可能。

5．解：

原式(PQ)R（PQ）R（PR）（QR）

（PQR）（PQR）(PQR)（PQR）M100M110M

010

∴使公式（PQ）R的值為F的真值指派為：

P:1



Q:0R:0；

P:1



Q:1R:0；

P:0



Q:1R:0。

五、證明題：

1．證明：假設R不是反對稱的，則 x,yR,性，∴ x,xR 此與R反自反矛盾，∴R反對稱。

y,xR,xy 由R的傳遞

2．證明：（1）設羣G,的幺元為e，則xG有 xeex，∴eH即H非空。（2）a,bH，則 xG 有 axxa,bxxb，從而

(ab

1)x(ab

1

11)x(bb

1)

a(bb)xb

1

(ax)b

1

1

x(ab)，abH

故 H,是G,的子羣。

3．解：設連通平面圖G有t個面：r1,r2,，rt則有 ver2，deg(ri)k,2k



tt

又有題意，deg(ri)kt

i1

又

e

deg(r)2e

i

i1，∴2ekt，teve

2k

e2

kk2

(v2)

。從而，∴。

4．解：設P(x)：x喜歡美術，Q(x)：x喜歡體育，R(x)：x喜歡音樂。論域：人。

命題形式化為：前提：x（P(x)Q(x)），x（Q(x)R(x)），xR（x)結論：xP(x)。證明：（1）xR(x)P(2)R(a)ES(1)(3)x(Q(x)R(x)）P（4)Q(a)R(a)US(4)(5)Q(a)T(2)(4)I(6)x(P(x)Q(x)）P(7)P(a)Q(a)US(6)(8)P(a)T(5)(7)I(9)xP(x)EG(8)∴ 結論有效。

離散 篇四

集合一、知識點（建議看書）

1、集合（類、族、蒐集）的定義：能作為整體論述的事物的整體。

元素（成員）：組成集合的每個事物。

基數（勢）：有限集合的元素個數，記為A2、集合的表示方法：①列舉法A={1，2，3}、②描述法A={a|aI0a5}、③歸納定義法。

3、區別{A}與A、{空集}與空集。

4、集合間的包含關係。（P55-P56）

5、並、交和差運算的定義及運算律。（P59-P60）

6、補運算定義、性質。德-摩根定律。（P61-P62）

7、並和交運算的擴展。（P63）

8、環和（對稱差）與環積的定義、性質。（P64）

9、冪集合：A是一集合，A的冪集合p(A)，是A的所有子集的集合。

n個元素的集合A，其冪集的元素個數是2n。

10、集合的歸納定義：（1）基礎條款；（2）歸納條款；（3）極小性條款。

歸納證明的步驟：（1）基礎步驟；（2）歸納步驟。

數學歸納法第一原理（P74）；數學歸納法第二原理（P76）

11、自然數的歸納定義。（P72）

12、二重組（序偶）：兩個元素a1、a2組成的序列記作。a1、a2分別稱為二重組的第一分量和第二分量。

=當且僅當a=c,b=d;。

n重組的定義（P84）

13、叉積（笛卡爾乘積）的定義、運算律。（P84）

二、練習題

1、列出下列每一集合的元素和全部子集。（知識點4）

{a,b,c}、{a,{b,c}}、{{a,{b,c}}}

2、證明下列各式。

（a）(AB)BAB

（b）C(AB)(CA)(CB)

（c）A(AB)AB3、證明如果CA且CB，那麼CAB（也就是AB是包含在A和B中的最大集合）

4、設A、B、C和D是任意集合，試證明：

(AB)(CD)(AC)(BD)

5、設A={0,1}，構成集合p(A)A。