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

一、單項(xiàng)選擇題（每題2分，共10題）1.設(shè)集合\(A=\{1,2,3\}\)，\(A\)上的關(guān)系\(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.下列不是圖的度數(shù)列的是（）A.\((1,1,2,2)\)B.\((1,2,3,4)\)C.\((2,2,2,2)\)D.\((1,2,2,3)\)4.設(shè)\(A\),\(B\)為集合，\(|A|=m\)，\(|B|=n\)，則從\(A\)到\(B\)的函數(shù)個(gè)數(shù)為（）A.\(m^n\)B.\(n^m\)C.\(m+n\)D.\(m\timesn\)5.一個(gè)無向圖有\(zhòng)(5\)個(gè)頂點(diǎn)，若它是連通圖，則最少有（）條邊A.\(3\)B.\(4\)C.\(5\)D.\(6\)6.設(shè)\(P(x)\)：\(x\)是質(zhì)數(shù)，\(Q(x)\)：\(x\)是偶數(shù)，命題“有的質(zhì)數(shù)是偶數(shù)”符號化為（）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\}\)的冪集的元素個(gè)數(shù)是（）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\)的邊數(shù)為（）A.\(4\)B.\(5\)C.\(6\)D.\(8\)10.命題公式\(p\to(q\tor)\)與下列（）等價(jià)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二、多項(xiàng)選擇題（每題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.請關(guān)上門！3.設(shè)\(A=\{1,2,3,4\}\)，\(R\)是\(A\)上的關(guān)系，\(R=\{(1,2),(2,3),(3,4),(4,1)\}\)，則\(R\)具有（）性質(zhì)A.自反性B.非自反性C.對稱性D.非對稱性4.下列哪些圖是歐拉圖（）A.無奇數(shù)度頂點(diǎn)的連通圖B.恰有兩個(gè)奇數(shù)度頂點(diǎn)的連通圖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.設(shè)\(P\)，\(Q\)為命題變元，下列等價(jià)式正確的是（）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\}\)上的二元關(guān)系（）A.\(\varnothing\)B.\(\{(a,a)\}\)C.\(A\timesA\)D.\(\{(a,b),(b,c)\}\)8.一個(gè)樹有\(zhòng)(n\)個(gè)頂點(diǎn)，則它（）A.有\(zhòng)(n-1\)條邊B.是連通圖C.無回路D.是二部圖9.設(shè)\(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.無向圖的度數(shù)列一定是非負(fù)整數(shù)數(shù)列。（）5.集合\(A\)上的恒等關(guān)系\(I_A\)是等價(jià)關(guān)系。（）6.一個(gè)圖如果是哈密頓圖，則一定是歐拉圖。（）7.謂詞公式\(\forallxP(x)\to\existsxP(x)\)是永真式。（）8.設(shè)\(R\)是\(A\)上的關(guān)系，若\(R\)是對稱的，則\(R^{-1}=R\)。（）9.二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)一定比分支結(jié)點(diǎn)個(gè)數(shù)多\(1\)。（）10.若函數(shù)\(f:A\toB\)是單射，則\(|A|\leq|B|\)。（）答案：1.×2.√3.√4.√5.√6.×7.√8.√9.×10.√四、簡答題（每題5分，共4題）1.求集合\(A=\{1,2,3\}\)上關(guān)系\(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\)有\(zhòng)(6\)個(gè)頂點(diǎn)，度數(shù)分別為\(1,1,2,2,2,4\)，問\(G\)有幾條邊？答案：根據(jù)握手定理\(\sum_{v\inV}d(v)=2e\)（\(V\)是頂點(diǎn)集，\(e\)是邊數(shù)），\(\sum_{v\inV}d(v)=1+1+2+2+2+4=12\)，所以\(2e=12\)，得\(e=6\)條邊。4.將命題“所有大學(xué)生都要學(xué)習(xí)高等數(shù)學(xué)”符號化并給出解釋。答案：設(shè)\(P(x)\)：\(x\)是大學(xué)生，\(Q(x)\)：\(x\)要學(xué)習(xí)高等數(shù)學(xué)，則符號化為\(\forallx(P(x)\toQ(x))\)。解釋：對于任意一個(gè)對象\(x\)，如果\(x\)是大學(xué)生，那么\(x\)就需要學(xué)習(xí)高等數(shù)學(xué)。五、討論題（每題5分，共4題）1.討論關(guān)系的自反性、對稱性、傳遞性在實(shí)際生活中的例子及應(yīng)用。答案：自反性如一個(gè)班級里“同學(xué)關(guān)系”，每個(gè)學(xué)生和自己是同學(xué)，有自反性，便于構(gòu)建社交圈子。對稱性像“朋友關(guān)系”，若\(A\)是\(B\)朋友，\(B\)也是\(A\)朋友，利于平等社交。傳遞性如在一些親屬關(guān)系中，若\(A\)是\(B\)長輩，\(B\)是\(C\)長輩，則\(A\)是\(C\)長輩，用于厘清家族關(guān)系。2.在離散數(shù)學(xué)中，圖論有哪些實(shí)際應(yīng)用領(lǐng)域？舉例說明。答案：在計(jì)算機(jī)網(wǎng)絡(luò)領(lǐng)域，用圖表示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，頂點(diǎn)是設(shè)備，邊是連接，便于分析數(shù)據(jù)傳輸路徑。在交通規(guī)劃上，城市為頂點(diǎn)，道路為邊，分析運(yùn)輸路線。社交網(wǎng)絡(luò)中，用戶為頂點(diǎn)，好友關(guān)系為邊，可研究信息傳播規(guī)律。3.說明命題邏輯和謂詞邏輯的區(qū)別與聯(lián)系。