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

試卷二十三試題與答案

一、單項選擇題：（每小題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．設< A，? > 是偏序集，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（范文）

離散數學試題（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},jdb3l39rxn9}B．{{a,b},{c},jdb3l39rxn9}

C．{{a},{b},{c},jdb3l39rxn9}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分）在謂詞邏輯中構造下面推理的證明：每個在學校讀書的人都獲得知識。所以如

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

第三篇：離散數學試卷

誠信應考,考試作弊將帶來嚴重后果！華南理工大學期末考試 《離散數學》試卷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={<1, 2>,<2,3>,<3,1>},g={<1,2>,<2,3>,<3,3>}，則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={<1，1>，<1，2>，<3，2>，<3，3>}，則S是（）

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

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

A．{{a},{b, c},jdb3l39rxn9}

C．{{a},{b},{c},jdb3l39rxn9} B．{{a, b},{c}, jdb3l39rxn9} 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={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求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分）

第四篇：離散數學試題與答案

《離散數學》試題及答案

一、選擇題：本題共5小題，每小題3分，共15分，在每小題給出的四個選項中，只有一項是符合題目要求的。

1.命題公式(P?Q)?Q為()

(A)矛盾式(B)可滿足式(C)重言式(D)合取范式

2．設P表示“天下大雨”，Q表示“他在室內運動”，則命題“除非天下大雨，否則他不在室內運動”符號化為（）。

(A)． P?Q；(B)．P?Q；(C)．?P??Q；(D)．?P?Q．

3.設集合A={{1,2,3}, {4,5}, {6,7,8}}，則下式為真的是()

(A)1?A(B){1,2, 3}?A

(C){{4,5}}?A(D)??A

4.設A＝{1,2},B={a,b,c},C={c,d}, 則A×(B?C)=()

(A){<1,c>,<2,c>}(B){,<2,c>}(C){,}(D){<1,c>,}

5.設G如右圖：那么G不是().(A)哈密頓圖；(B)完全圖；

(C)歐拉圖；(D)平面圖.二、填空題：本大題共5小題，每小題4分，共20

6.設集合A={?,{a}}，則A的冪集P(A7.設集合A={1,2,3,4 }, B={6,8,12}, A到B的關系R＝{?x,y?y?2x,x?A,y?B},那么R1＝－

8.在“同學，老鄉，親戚，朋友”四個關系中_______是等價關系.9.寫出一個不含“?”的邏輯聯結詞的完備集.10.設X＝{a,b,c}，R是X上的二元關系，其關系矩陣為

?101??，那么R的關系圖為 MR＝?100????100??

三、證明題（共30分）

11.（10分）已知A、B、C是三個集合，證明A∩(B∪C)=(A∩B)∪(A∩C)

12.（10分）構造證明：(P?(Q?S))∧(?R∨P)∧Q?R?S

（0,1）13.（10分）證明與[0,1)，[0,1)與[0,1]等勢。

四、解答題(共35分)

14.（7分）構造三階幻方（以1為首項的9個連續自然數正好布滿一個3?3方陣，且方陣中的每一行, 每一列及主、副對角線上的各數之和都相等.）

15.（8分）求命題公式(P?Q)?(?P??Q)的真值表.16.（10分）設R1是A1＝{1,2}到A2＝(a,b,c)的二元關系，R2是A2到A3＝{?,?}的二元關系，R1= {<1,a>,<1,b>,<2,c>}, R2={,}

畢節學院《離散數學 》課程試卷

求R1?R2的集合表達式.17.（10分）某項工作需要派A、B、C和D 4個人中的2個人去完成，按下面3個條件，有幾種派法？如何派？

三個條件：(1)若A去，則C和D中要去1個人；(2)B和C不能都去；

(3)若C去，則D留下。

一、單項選擇題(每小題3分，共15分)

1.B2.C3.C4.A5.B

二、填空題(每小題4分，共20分)

6.{?,{?},{{a}},{?,{a}}}

7.{<6,3>,<8,4> }8.老鄉

9.{?,?}或{?,?} 或 {?}或 {?}

10.見

f(0)?0??111?························································································ 10分 ,n?1,?A ·?f()?n?1n?n

??f(x)?x,x?[0,1)?A

14.85 1 2 7 6

填對每個格得1分。

15.表中最后一列的數中，每對1個數得2分.?110?16.MR1???,(2分)001??

MR2?01??(4分)??01????00??

?01??01???01?(6分)???00?????00???110? MR1?R2????001?

R1?R2?{?1,??}(10分)

17.解設A：A去工作；B：B去工作；C：C去工作；D：D去工作。則根據題意應有：A?C?D，?(B∧C)，C??D必須同時成立。······························································································ 2分 因此(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 ··································································································································· 8分

畢節學院《離散數學 》課程試卷

故有三種派法：B∧D，A∧C，A∧D。······································································· 10分

畢節學院《離散數學 》課程試卷

第五篇：離散數學考試試題(A卷及答案)

離散數學考試試題（A卷及答案）

一、（10分）判斷下列公式的類型（永真式、永假式、可滿足式）？ 1)((P?Q)∧Q)?((Q∨R)∧Q)2)?((Q?P)∨?P)∧(P∨R)3)((?P∨Q)?R)?((P∧Q)∨R)解：1)永真式；2）永假式；3)可滿足式。

二、（8分）個體域為{1，2}，求?x?y（x+y=4）的真值。

解：?x?y（x+y=4）??x（（x+1=4）∨（x+2=4））

?（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+1=4））?（0∨0）∧（0∨1）?1∧1?0

三、（8分）已知集合A和B且|A|=n，|B|=m，求A到B的二元關系數是多少？A到B的函數數是多少？

解：因為|P(A×B)|=2|A×B|=2|A||B|=2mn，所以A到B的二元關系有2mn個。因為|BA|=|B||A|=mn，所以A到B的函數mn個。

四、（10分）已知A={1,2,3,4,5}和R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>}，求r(R)、s(R)和t(R)。

解：r(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>} s(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<3,2>,<4,3>,<4,5>} t(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<1,3>,<2,2>,<2,4>,<1,4>}

五、(10分)75個兒童到公園游樂場，他們在那里可以騎旋轉木馬，坐滑行鐵道，乘宇宙飛船，已知其中20人這三種東西都乘過，其中55人至少乘坐過其中的兩種。若每樣乘坐一次的費用是0.5元，公園游樂場總共收入70元，求有多少兒童沒有乘坐過其中任何一種。

解 設A、B、C分別表示騎旋轉木馬、坐滑行鐵道、乘宇宙飛船的兒童組成的集合，|A∩B∩C|＝20，|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|＝55，|A|＋|B|＋|C|＝70/0.5＝140。

由容斥原理，得

|A∪B∪C|＝|A|＋|B|＋|C|―|A∩B|―|A∩C|―|B∩C|＋|A∩B∩C| 所以

|A∩B∩C|＝75－|A∪B∪C|＝75－(|A|＋|B|＋|C|)＋(|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|)＋|A∩B∩C|＝75－140＋55＋20＝10 沒有乘坐過其中任何一種的兒童共10人。

六、（12分）已知R和S是非空集合A上的等價關系，試證：1）R∩S是A上的等價關系；2）對a∈A，[a]R∩S=[a]R∩[a]S。

解：?x∈A，因為R和S是自反關系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。

?x、y∈A，若∈R∩S，則∈R、∈S，因為R和S是對稱關系，所以因∈R、∈S，因而∈R∩S，故R∩S是對稱的。?x、y、z∈A，若∈R∩S且∈R∩S，則∈R、∈S且∈R、∈S，因為R和S是傳遞的，所以因∈R、∈S，因而∈R∩S，故R∩S是傳遞的。

總之R∩S是等價關系。

2）因為x∈[a]R∩S?∈R∩S?∈R∧∈S? x∈[a]R∧x∈[a]S? x∈[a]R∩[a]S 所以[a]R∩S=[a]R∩[a]S。

七（10分）設A、B、C、D是集合，f是A到B的雙射，g是C到D的雙射，令h：A×C?B×D且?∈A×C，h()＝。證明h是雙射。

證明：1）先證h是滿射。

?∈B×D，則b∈B，d∈D，因為f是A到B的雙射，g是C到D的雙射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在∈A×C，使得h()＝＝，所以h是滿射。

2）再證h是單射。

?、∈A×C，若h()＝h()，則＝，所以f(a1)＝f(a2)，g(c1)＝g(c2)，因為f是A到B的雙射，g是C到D的雙射，所以a1＝a2，c1＝c2，所以＝，所以h是單射。綜合1）和2），h是雙射。

八、（12分）是個群，u∈G，定義G中的運算“?”為a?b=a*u-1*b，對任意a,b∈G，求證：也是個群。

證明：1）?a,b∈G，a?b=a*u-1*b∈G，運算是封閉的。

2）?a,b,c∈G，（a?b）?c=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=a?（b?c），運算是可結合的。3）?a∈G，設E為?的單位元，則a?E=a*u-1*E=a，得E=u，存在單位元。

4）?a∈G，a?x=a*u-1*x=E，x=u*a-1*u，則x?a=u*a-1*u*u-1*a=u=E，每個元素都有逆元。所以也是個群。

九、（10分）已知：D=，V={1,2,3,4,5}，E={<1,2>,<1,4>,<2,3>,<3,4>,<3,5>,<5,1>}，求D的鄰接距陣A和可達距陣P。

解：D的鄰接距陣A和可達距陣P如下：

A= 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0

0 0 1 0 0

P= 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1

十、（10分）求葉的權分別為2、4、6、8、10、12、14的最優二叉樹及其權。

解：最優二叉樹為

權＝148

離散數學考試試題（B卷及答案）

一、（10分）求命題公式?(P∧Q)??(?P?R)的主合取范式。

解：?(P∧Q)??(?P?R)?（?(P∧Q)??(?P?R)）∧（?(?P?R)??(P∧Q)）?（(P∧Q)∨(?P∧?R)）∧（(P∨R)∨(?P∨?Q)）?(P∧Q)∨(?P∧?R)?(P∨?R)∧（Q∨?P）∧（Q∨?R）

?(P∨Q∨?R)∧(P∨?Q∨?R)∧（?P∨Q∨R）∧（?P∨Q∨?R）?M1∧M3∧M4∧M5

二、（8分）敘述并證明蘇格拉底三段論

解：所有人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。符號化：F（x）：x是一個人。G（x）：x要死的。A：蘇格拉底。命題符號化為?x（F（x）?G（x）），F（a）?G（a）證明：

（1）?x(F(x)?G(x))P（2）F(a)?G(a)T(1),US（3）F(a)P（4）G(a)T(2)(3),I

三、（8分）已知A、B、C是三個集合，證明A∩(B∪C)=(A∩B)∪(A∩C)證明：∵x? A∩（B∪C）? x? A∧x?（B∪C）

? x? A∧（x?B∨x?C）

?（x? A∧x?B）∨（x? A∧x?C）? x?（A∩B）∨x? A∩C ? x?（A∩B）∪（A∩C）

∴A∩（B∪C）=（A∩B）∪（A∩C）

四、（10分）已知R和S是非空集合A上的等價關系，試證：1）R∩S是A上的等價關系；2）對a∈A，[a]R∩S=[a]R∩[a]S。

解：?x∈A，因為R和S是自反關系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。

?x、y∈A，若∈R∩S，則∈R、∈S，因為R和S是對稱關系，所以因∈R、∈S，因而∈R∩S，故R∩S是對稱的。

?x、y、z∈A，若∈R∩S且∈R∩S，則∈R、∈S且∈R、∈S，因為R和S是傳遞的，所以因∈R、∈S，因而∈R∩S，故R∩S是傳遞的。

總之R∩S是等價關系。

2）因為x∈[a]R∩S?∈R∩S?

∈R∧∈S? x∈[a]R∧x∈[a]S? x∈[a]R∩[a]S 所以[a]R∩S=[a]R∩[a]S。

五、(10分)設A＝{a，b，c，d}，R是A上的二元關系，且R＝{，，，}，求r(R)、s(R)和t(R)。

解 r(R)＝R∪IA＝{，，，，，，，} s(R)＝R∪R＝{，，，，，} R＝{，，，} R＝{，，，} R＝{，，，}＝R

t(R)＝?R＝{，，，，，，，，} i?1?i

4232-

1六、(15分)設A、B、C、D是集合，f是A到B的雙射，g是C到D的雙射，令h：A×C?B×D且?∈A×C，h()＝。證明h是雙射。

證明：1）先證h是滿射。

?∈B×D，則b∈B，d∈D，因為f是A到B的雙射，g是C到D的雙射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在∈A×C，使得h()＝＝，所以h是滿射。

2）再證h是單射。

?、∈A×C，若h()＝h()，則＝，所以f(a1)＝f(a2)，g(c1)＝g(c2)，因為f是A到B的雙射，g是C到D的雙射，所以a1＝a2，c1＝c2，所以＝，所以h是單射。

綜合1）和2），h是雙射。

七、(12分)設是群，H是G的非空子集，證明是的子群的充要條件是若a，b?H，則有a*b?H。

證明：? ?a,b∈H有b∈H，所以a*b∈H。??a∈H，則e=a*a∈H-1-

1-1-1a=e*a∈H ∵a,b∈H及b∈H，∴a*b=a*（b）∈H ∵H?G且H≠?,∴*在H上滿足結合律 ∴是的子群。

八、（10分）設G=是簡單的無向平面圖，證明G至少有一個結點的度數小于等于5。

解：設G的每個結點的度數都大于等于6，則2|E|=?d(v)≥6|V|，即|E|≥3|V|，與簡單無向平面圖-

1-1

-1-1-1的|E|≤3|V|-6矛盾，所以G至少有一個結點的度數小于等于5。九.G=,A={a,b,c},*的運算表為：(寫過程，7分)

（1）G是否為阿貝爾群？

（2）找出G的單位元；（3）找出G的冪等元（4）求b的逆元和c的逆元 解：（1）(a*c)*(a*c)=c*c=b=a*b=(a*a)*(c*c)(a*b)*(a*b)=b*b=c=a*c=(a*a)*(b*b)(b*c)*(b*c)=a*a=a=c*b=(b*b)*(c*c)所以G是阿貝爾群

（2）因為a*a=a a*b=b*a=b a*c=c*a=c 所以G的單位元是a（3）因為a*a=a 所以G的冪等元是a（4）因為b*c=c*b=a，所以b的逆元是c且c的逆元是b

十、(10分)求葉的權分別為2、4、6、8、10、12、14的最優二叉樹及其權。

解：最優二叉樹為

權＝148 5