離散數學考試試題a卷及答案

一、單項選擇題（每題2分，共10題）1.設集合\(A=\{1,2,3\}\)，\(A\)上的關系\(R=\{(1,1),(2,2),(3,3)\}\)，則\(R\)是（）A.自反的B.對稱的C.傳遞的D.以上都是2.命題公式\(\neg(p\toq)\)的主合取范式是（）A.\(p\land\negq\)B.\(\negp\landq\)C.\(p\lor\negq\)D.\(\negp\lorq\)3.下列不是圖的度數列的是（）A.\((1,1,2,2)\)B.\((1,2,3,4)\)C.\((2,2,2,2)\)D.\((1,2,2,3)\)4.設\(A\),\(B\)為集合，\(|A|=m\)，\(|B|=n\)，則從\(A\)到\(B\)的函數個數為（）A.\(m^n\)B.\(n^m\)C.\(m+n\)D.\(m\timesn\)5.一個無向圖有\(5\)個頂點，若它是連通圖，則最少有（）條邊A.\(3\)B.\(4\)C.\(5\)D.\(6\)6.設\(P(x)\)：\(x\)是質數，\(Q(x)\)：\(x\)是偶數，命題“有的質數是偶數”符號化為（）A.\(\forallx(P(x)\toQ(x))\)B.\(\existsx(P(x)\landQ(x))\)C.\(\forallx(P(x)\landQ(x))\)D.\(\existsx(P(x)\toQ(x))\)7.集合\(\{a,b,c\}\)的冪集的元素個數是（）A.\(3\)B.\(6\)C.\(7\)D.\(8\)8.若\(A=\{1,2,3\}\)，\(R=\{(1,2),(2,3),(1,3)\}\)，則\(R\)的傳遞閉包\(t(R)\)是（）A.\(R\)B.\(\{(1,2),(2,3),(1,3)\}\)C.\(\{(1,2),(2,3),(1,3),(2,2),(3,3)\}\)D.\(A\timesA\)9.無向完全圖\(K_4\)的邊數為（）A.\(4\)B.\(5\)C.\(6\)D.\(8\)10.命題公式\(p\to(q\tor)\)與下列（）等價A.\((p\landq)\tor\)B.\(p\land(q\tor)\)C.\((p\toq)\tor\)D.\(p\toq\lorr\)答案：1.D2.A3.B4.B5.B6.B7.D8.A9.C10.A二、多項選擇題（每題2分，共10題）1.下列命題為真的有（）A.\(\varnothing\in\{\varnothing\}\)B.\(\varnothing\subseteq\{\varnothing\}\)C.\(\varnothing\in\varnothing\)D.\(\varnothing\subseteq\varnothing\)2.以下哪些是命題（）A.明天天氣晴朗。B.\(x+3\gt5\)C.\(2+2=4\)D.請關上門！3.設\(A=\{1,2,3,4\}\)，\(R\)是\(A\)上的關系，\(R=\{(1,2),(2,3),(3,4),(4,1)\}\)，則\(R\)具有（）性質A.自反性B.非自反性C.對稱性D.非對稱性4.下列哪些圖是歐拉圖（）A.無奇數度頂點的連通圖B.恰有兩個奇數度頂點的連通圖C.完全圖\(K_3\)D.完全二部圖\(K_{2,2}\)5.對于集合\(A\)，\(B\)，\(C\)，下列等式成立的是（）A.\(A-B\cupC=(A-B)\cup(A-C)\)B.\(A\cap(B\cupC)=(A\capB)\cup(A\capC)\)C.\(\overline{A\capB}=\overline{A}\cup\overline{B}\)D.\(\overline{A\cupB}=\overline{A}\cap\overline{B}\)6.設\(P\)，\(Q\)為命題變元，下列等價式正確的是（）A.\(P\toQ\Leftrightarrow\negP\lorQ\)B.\(P\landQ\Leftrightarrow\neg(\negP\lor\negQ)\)C.\(P\oplusQ\Leftrightarrow(P\land\negQ)\lor(\negP\landQ)\)D.\(P\leftrightarrowQ\Leftrightarrow(P\toQ)\land(Q\toP)\)7.以下哪些是集合\(A=\{a,b,c\}\)上的二元關系（）A.\(\varnothing\)B.\(\{(a,a)\}\)C.\(A\timesA\)D.\(\{(a,b),(b,c)\}\)8.一個樹有\(n\)個頂點，則它（）A.有\(n-1\)條邊B.是連通圖C.無回路D.是二部圖9.設\(A=\{1,2\}\)，\(B=\{3,4\}\)，則\(A\timesB\)的元素有（）A.\((1,3)\)B.\((1,4)\)C.\((2,3)\)D.\((2,4)\)10.命題公式\((p\landq)\tor\)的成假賦值有（）A.\(000\)B.\(010\)C.\(110\)D.\(100\)答案：1.ABD2.AC3.BD4.AD5.BCD6.ABCD7.ABCD8.ABC9.ABCD10.C三、判斷題（每題2分，共10題）1.空集是任何集合的真子集。（）2.若\(A\subseteqB\)且\(B\subseteqA\)，則\(A=B\)。（）3.命題公式\((p\toq)\land\negq\to\negp\)是重言式。（）4.無向圖的度數列一定是非負整數數列。（）5.集合\(A\)上的恒等關系\(I_A\)是等價關系。（）6.一個圖如果是哈密頓圖，則一定是歐拉圖。（）7.謂詞公式\(\forallxP(x)\to\existsxP(x)\)是永真式。（）8.設\(R\)是\(A\)上的關系，若\(R\)是對稱的，則\(R^{-1}=R\)。（）9.二叉樹的葉子結點個數一定比分支結點個數多\(1\)。（）10.若函數\(f:A\toB\)是單射，則\(|A|\leq|B|\)。（）答案：1.×2.√3.√4.√5.√6.×7.√8.√9.×10.√四、簡答題（每題5分，共4題）1.求集合\(A=\{1,2,3\}\)上關系\(R=\{(1,2),(2,3),(3,1)\}\)的對稱閉包\(s(R)\)。答案：\(s(R)=R\cupR^{-1}\)，\(R^{-1}=\{(2,1),(3,2),(1,3)\}\)，所以\(s(R)=\{(1,2),(2,3),(3,1),(2,1),(3,2),(1,3)\}\)。2.用真值表判斷命題公式\((p\lorq)\land\negp\toq\)的類型。答案：列真值表：|\(p\)|\(q\)|\(p\lorq\)|\(\negp\)|\((p\lorq)\land\negp\)|\((p\lorq)\land\negp\toq\)||:-----:|:-----:|:-----:|:-----:|:-----:|:-----:||\(0\)|\(0\)|\(0\)|\(1\)|\(0\)|\(1\)||\(0\)|\(1\)|\(1\)|\(1\)|\(1\)|\(1\)||\(1\)|\(0\)|\(1\)|\(0\)|\(0\)|\(1\)||\(1\)|\(1\)|\(1\)|\(0\)|\(0\)|\(1\)|該命題公式是重言式。3.已知無向圖\(G\)有\(6\)個頂點，度數分別為\(1,1,2,2,2,4\)，問\(G\)有幾條邊？答案：根據握手定理\(\sum_{v\inV}d(v)=2e\)（\(V\)是頂點集，\(e\)是邊數），\(\sum_{v\inV}d(v)=1+1+2+2+2+4=12\)，所以\(2e=12\)，得\(e=6\)條邊。4.將命題“所有大學生都要學習高等數學”符號化并給出解釋。答案：設\(P(x)\)：\(x\)是大學生，\(Q(x)\)：\(x\)要學習高等數學，則符號化為\(\forallx(P(x)\toQ(x))\)。解釋：對于任意一個對象\(x\)，如果\(x\)是大學生，那么\(x\)就需要學習高等數學。五、討論題（每題5分，共4題）1.討論關系的自反性、對稱性、傳遞性在實際生活中的例子及應用。答案：自反性如一個班級里“同學關系”，每個學生和自己是同學，有自反性，便于構建社交圈子。對稱性像“朋友關系”，若\(A\)是\(B\)朋友，\(B\)也是\(A\)朋友，利于平等社交。傳遞性如在一些親屬關系中，若\(A\)是\(B\)長輩，\(B\)是\(C\)長輩，則\(A\)是\(C\)長輩，用于厘清家族關系。2.在離散數學中，圖論有哪些實際應用領域？舉例說明。答案：在計算機網絡領域，用圖表示網絡拓撲結構，頂點是設備，邊是連接，便于分析數據傳輸路徑。在交通規劃上，城市為頂點，道路為邊，分析運輸路線。社交網絡中，用戶為頂點，好友關系為邊，可研究信息傳播規律。3.說明命題邏輯和謂詞邏輯的區別與聯系。