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

一、單項選擇題（每題2分，共20分）1.下列語句中，（）是命題。A.請把門關(guān)上B.\(x+5>6\)C.地球外的星球上也有人D.下午有會嗎？2.設(shè)集合\(A=\{1,2,3\}\)，則\(A\)上的二元關(guān)系\(R=\{(1,1),(2,2)\}\)是（）A.自反的B.對稱的C.傳遞且反自反的D.對稱且傳遞的3.若\(A=\{a,b\}\)，\(B=\{1,2\}\)，則\(A\timesB\)的元素個數(shù)為（）A.1B.2C.3D.44.設(shè)\(G\)是一個有\(zhòng)(n\)個結(jié)點的無向完全圖，則\(G\)的邊數(shù)為（）A.\(n(n-1)\)B.\(n(n-1)/2\)C.\(n^2\)D.\(n^2-1\)5.命題公式\((p\land\negq)\lor(\negp\landq)\)的成真賦值是（）A.00,01B.01,10C.10,11D.00,116.設(shè)集合\(A=\{a,b,c\}\)，\(A\)上的等價關(guān)系\(R=\{(a,a),(b,b),(c,c),(a,b),(b,a)\}\)，則\(A\)關(guān)于\(R\)的商集\(A/R\)為（）A.\(\{\{a\},\{b\},\{c\}\}\)B.\(\{\{a,b\},\{c\}\}\)C.\(\{\{a\},\{b,c\}\}\)D.\(\{\{a,b,c\}\}\)7.一個連通平面圖\(G\)有5個頂點，8條邊，則\(G\)的面數(shù)為（）A.4B.5C.6D.78.設(shè)\(f:A\toB\)，\(g:B\toC\)是兩個函數(shù)，若\(g\circf\)是雙射函數(shù)，則（）A.\(f\)是單射，\(g\)是滿射B.\(f\)是滿射，\(g\)是單射C.\(f\)和\(g\)都是雙射D.\(f\)和\(g\)都是單射9.設(shè)\(P(x):x\)是奇數(shù)，\(Q(x):x\)是偶數(shù)，個體域為整數(shù)集，則公式\(\forallx(P(x)\lorQ(x))\)的真值為（）A.真B.假C.不確定D.以上都不對10.集合\(A=\{1,2,3,4\}\)上的關(guān)系\(R=\{(1,2),(2,3),(3,4)\}\)的傳遞閉包\(t(R)\)為（）A.\(\{(1,2),(2,3),(3,4),(1,3),(2,4),(1,4)\}\)B.\(\{(1,2),(2,3),(3,4)\}\)C.\(\{(1,4)\}\)D.\(\{(1,2),(2,3),(3,4),(1,3),(2,4)\}\)答案：1.C2.D3.D4.B5.B6.B7.B8.A9.A10.A二、多項選擇題（每題2分，共20分）1.以下哪些是命題邏輯中的基本聯(lián)結(jié)詞（）A.\(\neg\)（否定）B.\(\land\)（合?。〤.\(\lor\)（析?。〥.\(\to\)（蘊含）E.\(\leftrightarrow\)（等價）2.設(shè)集合\(A=\{1,2,3\}\)，則\(A\)上的關(guān)系\(R\)為自反關(guān)系的有（）A.\(\{(1,1),(2,2),(3,3)\}\)B.\(\{(1,1),(2,2),(3,3),(1,2)\}\)C.\(\{(1,1),(2,2)\}\)D.\(\{(1,1),(2,2),(3,3),(1,3),(3,1)\}\)3.下列關(guān)于圖的說法正確的是（）A.無向圖中所有頂點的度數(shù)之和等于邊數(shù)的2倍B.有向圖中所有頂點的入度之和等于出度之和C.連通圖一定存在生成樹D.完全圖\(K_n\)的邊數(shù)為\(n(n-1)\)4.設(shè)\(A=\{a,b\}\)，則\(A\)的冪集\(P(A)\)包含的元素有（）A.\(\varnothing\)B.\(\{a\}\)C.\(\{b\}\)D.\(\{a,b\}\)5.以下哪些是謂詞邏輯中的有效式（）A.\(\forallxP(x)\to\existsxP(x)\)B.\(\existsx(P(x)\landQ(x))\leftrightarrow\existsxP(x)\land\existsxQ(x)\)C.\(\forallx(P(x)\toQ(x))\landP(a)\toQ(a)\)D.\(\forallx\forallyR(x,y)\to\forally\forallxR(x,y)\)6.設(shè)\(f:A\toB\)是一個函數(shù)，下列說法正確的是（）A.若\(f\)是單射，則對于任意\(x_1,x_2\inA\)，當\(x_1\neqx_2\)時，\(f(x_1)\neqf(x_2)\)B.若\(f\)是滿射，則對于任意\(y\inB\)，存在\(x\inA\)使得\(f(x)=y\)C.若\(f\)是雙射，則\(f\)既是單射又是滿射D.若\(|A|=|B|\)，則\(f\)一定是雙射7.下列哪些集合運算滿足結(jié)合律（）A.并運算\(\cup\)B.交運算\(\cap\)C.差運算\(-\)D.對稱差運算\(\oplus\)8.對于一個布爾代數(shù)\((B,\land,\lor,\neg,0,1)\)，以下哪些等式成立（）A.\(a\land1=a\)B.\(a\lor0=a\)C.\(a\land\nega=0\)D.\(a\lor\nega=1\)9.設(shè)\(G\)是一個群，\(a,b\inG\)，則以下正確的是（）A.\((ab)^{-1}=b^{-1}a^{-1}\)B.\(a^ma^n=a^{m+n}\)（\(m,n\)為整數(shù)）C.\((a^m)^n=a^{mn}\)（\(m,n\)為整數(shù)）D.若\(ab=ba\)，則\((ab)^n=a^nb^n\)（\(n\)為整數(shù)）10.以下哪些圖是歐拉圖（）A.連通且每個頂點度數(shù)均為偶數(shù)的無向圖B.有向圖中每個頂點的入度等于出度的連通圖C.存在歐拉回路的圖D.存在歐拉通路的圖答案：1.ABCDE2.ABD3.ABC4.ABCD5.ACD6.ABC7.ABD8.ABCD9.ABCD10.ABC三、判斷題（每題2分，共20分）1.命題“如果\(1+1=3\)，那么雪是黑的”是真命題。（）2.集合\(A\)上的恒等關(guān)系\(I_A\)是等價關(guān)系。（）3.一個圖是哈密頓圖，則一定是歐拉圖。（）4.若\(A\subseteqB\)且\(B\subseteqC\)，則\(A\subseteqC\)。（）5.謂詞公式\(\forallx\existsyP(x,y)\)和\(\existsy\forallxP(x,y)\)是等價的。（）6.一個函數(shù)\(f:A\toB\)，若\(|A|<|B|\)，則\(f\)不可能是滿射。（）7.集合的對稱差運算滿足交換律和結(jié)合律。（）8.在布爾代數(shù)中，\(a\land(b\lorc)=(a\landb)\lor(a\landc)\)。（）9.群中一定存在單位元。（）10.無向圖\(G\)有生成樹的充要條件是\(G\)連通。（）答案：1.√2.√3.×4.√5.×6.√7.√8.√9.√10.√四、簡答題（每題5分，共20分）1.簡述集合的三種表示方法。答案：列舉法，將集合中的元素一一列舉出來，如\(\{1,2,3\}\)；描述法，用元素的共同性質(zhì)描述集合，如\(\{x|x是偶數(shù)\}\)；圖示法，用文氏圖直觀表示集合關(guān)系。2.什么是命題公式的主析取范式？答案：對于給定命題公式，將其等價變換為僅由極小項的析取組成的形式。極小項是含有公式中所有命題變元且每個變元以原變量或否定形式出現(xiàn)一次的合取式，主析取范式唯一。3.簡述關(guān)系的性質(zhì)有哪些。答案：自反性，集合\(A\)上關(guān)系\(R\)，\(\foralla\inA\)有\(zhòng)((a,a)\inR\)；對稱性，\((a,b)\inR\)則\((b,a)\inR\)；傳遞性，\((a,b)\inR\)且\((b,c)\inR\)則\((a,c)\inR\)；反自反性，\(\foralla\inA\)有\(zhòng)((a,a)\notinR\)；反對稱性，\((a,b)\inR\)且\((b,a)\inR\)則\(a=b\)。4.簡述圖的連通分量的概念。答案：無向圖\(G\)的極大連通子圖稱為\(G\)的連通分量。即子圖\(H\)是\(G\)的連通分量，\(H\)連通且\(G\)中不存在包含\(H\)且比\(H\)更大的連通子圖。五、討論題（每題5分，共20分）1.討論命題邏輯和謂詞邏輯的聯(lián)系與區(qū)別。答案：聯(lián)系：命題邏輯是謂詞邏輯的基礎(chǔ)，謂詞邏輯包含命題邏輯。區(qū)別：命題邏輯以原子命題為基本單位，不分析內(nèi)部結(jié)構(gòu)；謂詞邏輯深入分析命題內(nèi)部的個體、謂詞和量詞，表達能力更強，能處理更復雜的邏輯關(guān)系。2.討論等價關(guān)系在實際生活中的應(yīng)用。答案：在實際生活中，等價關(guān)系應(yīng)用廣泛。如在分類問題上，根據(jù)某些屬性將事物歸為等價類，像商品按功能、質(zhì)量等分類；在數(shù)據(jù)處理中，可對等價數(shù)據(jù)進行統(tǒng)一處理，減少冗余，提高效率；在社交網(wǎng)絡(luò)中，根據(jù)共同興趣等劃分不同群體。3.討論圖論在計算機科學中的應(yīng)用。答案：在計算機科學中，