離散數(shù)學(xué)考試試題及答案

一、單項選擇題1.下列語句中，（）是命題。A.請把門關(guān)上B.\(x+5>6\)C.地球外的星球上也有人D.下午有會嗎？答案：C2.設(shè)\(A=\{1,2,3\}\)，則下列關(guān)系\(R\)中不是等價關(guān)系的是（）A.\(R=\{(1,1),(2,2),(3,3)\}\)B.\(R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}\)C.\(R=\{(1,1),(2,2),(3,3),(1,3)\}\)D.\(R=\{(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2),(1,3),(3,1)\}\)答案：C3.設(shè)\(P\)：我將去打球，\(Q\)：我有時間。命題“我將去打球，僅當(dāng)我有時間時”符號化為（）A.\(P→Q\)B.\(Q→P\)C.\(P?Q\)D.\(?P∨?Q\)答案：A4.集合\(A=\{a,b,c\}\)，\(A\)上的二元關(guān)系\(R=\{(a,a),(b,b),(a,c)\}\)，則關(guān)系\(R\)的對稱閉包\(s(R)\)是（）A.\(R∪I_A\)B.\(R\)C.\(R∪\{(c,a)\}\)D.\(R∩I_A\)答案：C5.設(shè)\(G\)是連通平面圖，有\(zhòng)(v\)個結(jié)點，\(e\)條邊，\(r\)個面，則\(r=（）\)A.\(e-v+2\)B.\(v+e-2\)C.\(e-v-2\)D.\(e+v+2\)答案：A6.下列公式中（）是永真式。A.\((P∧?P)?Q\)B.\(?(P→Q)∧Q\)C.\((P→Q)∧(Q→P)\)D.\((P∨?P)→Q\)答案：C7.設(shè)\(A=\{a,b\}\)，則\(P(A)\)的元素個數(shù)為（）A.2B.3C.4D.8答案：C8.設(shè)\(R\)是集合\(A\)上的偏序關(guān)系，則\(R\)不具有的性質(zhì)是（）A.自反性B.對稱性C.反對稱性D.傳遞性答案：B9.一個無向圖有\(zhòng)(5\)個頂點，若它是連通圖，則最少有（）條邊。A.4B.5C.6D.7答案：A10.設(shè)\(F(x)\)：\(x\)是人，\(G(x)\)：\(x\)犯錯誤，命題“沒有不犯錯誤的人”符號化為（）A.\(\forallx(F(x)∧G(x))\)B.\(\neg\existsx(F(x)→\negG(x))\)C.\(\neg\existsx(F(x)∧\negG(x))\)D.\(\neg\forallx(F(x)→G(x))\)答案：C二、多項選擇題1.以下哪些是命題公式（）A.\(P\)B.\(P∨Q\)C.\((P→Q)∧R\)D.\(P+Q\)答案：ABC2.設(shè)集合\(A=\{1,2,3,4\}\)，下列關(guān)系\(R\)是\(A\)上的函數(shù)的有（）A.\(R=\{(1,2),(2,3),(3,4),(4,1)\}\)B.\(R=\{(1,2),(2,3),(3,2)\}\)C.\(R=\{(1,2),(2,2),(3,2),(4,2)\}\)D.\(R=\{(1,2),(1,3),(3,4)\}\)答案：AC3.下列哪些集合運算性質(zhì)是正確的（）A.\(A∪(B∩C)=(A∪B)∩(A∪C)\)B.\(A∩(B∪C)=(A∩B)∪(A∩C)\)C.\(A-(B∪C)=(A-B)∩(A-C)\)D.\(A-(B∩C)=(A-B)∪(A-C)\)答案：ABCD4.以下關(guān)于圖的說法正確的是（）A.簡單圖中沒有環(huán)和重邊B.連通圖一定是簡單圖C.完全圖中任意兩個頂點之間都有邊D.二部圖中沒有奇數(shù)長度的回路答案：ACD5.設(shè)\(A=\{a,b,c\}\)，則\(A\)上的二元關(guān)系有（）種。A.\(2^3\)B.\(3^2\)C.\(2^{3×3}\)D.\(512\)答案：CD6.下列公式中，哪些是邏輯等價的（）A.\(P→Q\)與\(\negP∨Q\)B.\(\neg(P∧Q)\)與\(\negP∨\negQ\)C.\(P?Q\)與\((P→Q)∧(Q→P)\)D.\(\forallx(P(x)→Q(x))\)與\(\forallxP(x)→\forallxQ(x)\)答案：ABC7.以下哪些是格（）A.集合\(A\)的冪集\(P(A)\)關(guān)于包含關(guān)系B.正整數(shù)集合關(guān)于整除關(guān)系C.實數(shù)集合關(guān)于小于等于關(guān)系D.任意集合\(A\)上的所有二元關(guān)系關(guān)于包含關(guān)系答案：ABC8.一個圖\(G\)是歐拉圖的充要條件是（）A.\(G\)是連通圖B.\(G\)中所有頂點的度數(shù)都是偶數(shù)C.\(G\)中所有頂點的度數(shù)都是奇數(shù)D.\(G\)有歐拉回路答案：ABD9.設(shè)\(R\)是集合\(A\)上的關(guān)系，若\(R\)是（），則\(R\)是等價關(guān)系。A.自反的B.對稱的C.傳遞的D.反對稱的答案：ABC10.以下關(guān)于謂詞邏輯的說法正確的是（）A.量詞有全稱量詞和存在量詞B.謂詞公式可以進(jìn)行等價變換C.可以將命題邏輯中的推理規(guī)則推廣到謂詞邏輯D.謂詞邏輯比命題邏輯表達(dá)能力更強答案：ABCD三、判斷題1.“\(x+3>5\)”是命題。（）答案：錯誤2.集合\(A\)上的恒等關(guān)系\(I_A\)是等價關(guān)系。（）答案：正確3.若\(A?B\)且\(B?C\)，則\(A?C\)。（）答案：正確4.有向圖中所有頂點的入度之和等于所有頂點的出度之和。（）答案：正確5.命題公式\((P∧\negP)∨Q\)是矛盾式。（）答案：錯誤6.集合\(A\)上的關(guān)系\(R\)是對稱的當(dāng)且僅當(dāng)\(R=R^{-1}\)。（）答案：正確7.完全二叉樹中，若有\(zhòng)(n\)個葉子結(jié)點，則分支結(jié)點數(shù)為\(n-1\)。（）答案：正確8.謂詞公式\(\forallxP(x)→\existsxP(x)\)是永真式。（）答案：正確9.一個圖\(G\)是哈密頓圖，則\(G\)一定是連通圖。（）答案：正確10.若\(R\)是集合\(A\)上的偏序關(guān)系，則\(A\)中一定存在最大元。（）答案：錯誤四、簡答題1.簡述集合的三種表示方法。答案：列舉法，即將集合中的元素一一列舉出來，如\(A=\{1,2,3\}\)；描述法，用元素所具有的共同性質(zhì)來描述集合，如\(B=\{x|x\)是偶數(shù)\(\}\)；文氏圖法，用圖形直觀地表示集合及集合間的關(guān)系，通常用矩形表示全集，圓表示子集等。2.解釋什么是命題公式的主析取范式和主合取范式。答案：主析取范式是由極小項的析取組成的命題公式。極小項是一個簡單合取式，每個命題變元或其否定恰好出現(xiàn)一次且僅一次。主合取范式是由極大項的合取組成的命題公式，極大項是一個簡單析取式，每個命題變元或其否定恰好出現(xiàn)一次且僅一次。任何命題公式都可等值轉(zhuǎn)化為唯一的主析取范式和主合取范式。3.什么是函數(shù)？函數(shù)有哪些類型？答案：設(shè)\(A\)、\(B\)是集合，如果對于\(A\)中任意一個元素\(x\)，按照某種對應(yīng)法則\(f\)，在\(B\)中有唯一確定的元素\(y\)與之對應(yīng)，則稱\(f\)是從\(A\)到\(B\)的函數(shù)。函數(shù)類型有：單射函數(shù)，若\(x_1≠x_2\)時，\(f(x_1)≠f(x_2)\)；滿射函數(shù)，\(B\)中任意元素都有原像；雙射函數(shù)，既是單射又是滿射的函數(shù)。4.簡述圖的連通性概念。答案：在無向圖中，如果從頂點\(u\)到頂點\(v\)存在路徑，則稱\(u\)和\(v\)是連通的。若圖中任意兩個頂點都是連通的，則該圖是連通圖。否則是非連通圖。在有向圖中，若任意兩個頂點間至少存在一條單向通路，則是單向連通圖；若任意兩個頂點間都存在雙向通路，則是強連通圖；若其基圖是連通圖，則是弱連通圖。五、討論題1.討論等價關(guān)系在實際生活中的應(yīng)用。答案：等價關(guān)系在生活中應(yīng)用廣泛。比如在學(xué)生分組中，可根據(jù)成績、興趣等因素定義等價關(guān)系進(jìn)行分組。在社交網(wǎng)絡(luò)里，根據(jù)朋友關(guān)系的某種等價定義，可劃分不同社交圈子。在商品分類中，依據(jù)商品的功能、價格區(qū)間等確定等價關(guān)系來分類擺放。通過等價關(guān)系，能將復(fù)雜的事物按照一定規(guī)則分類，便于管理、分析和研究，提高生活和工作效率。2.談?wù)劽}邏輯和謂詞邏輯的聯(lián)系與區(qū)別。答案：聯(lián)系：命題邏輯是謂詞邏輯的基礎(chǔ)，謂詞邏輯包含了命題邏輯的內(nèi)容。命題邏輯中的命題可以看作是謂詞邏輯中不含個體變元的特殊情況。區(qū)別：命題邏輯以簡單命題為基本單位，不涉及命題內(nèi)部結(jié)構(gòu)；謂詞邏輯深入到命題內(nèi)部，分析個體、謂詞和量詞。命題邏輯表達(dá)能力有限，謂詞邏輯能更精確地表達(dá)復(fù)雜的自然語言和數(shù)學(xué)命題，推理能力也更強，適用范圍更廣。3.分析圖論在計算機科學(xué)中的應(yīng)用。答案：在計算機科學(xué)中圖論應(yīng)用眾多。在數(shù)據(jù)結(jié)構(gòu)里，圖可用于表示網(wǎng)絡(luò)結(jié)構(gòu)、數(shù)據(jù)庫中的實體關(guān)系等。在算法設(shè)計中，最短路徑算法如迪杰斯特拉算法基于圖論，用于解決網(wǎng)絡(luò)路由、導(dǎo)航等問題。在人工智能領(lǐng)域，知識圖譜以圖的形式存儲和表示知識。在操作系統(tǒng)中，進(jìn)程資源分配圖可分析進(jìn)程死鎖