2025年山大離散數(shù)學(xué)期末試題及答案一、選擇題（每題3分，共30分）1.設(shè)集合\(A=\{1,2,3\}\)，\(B=\{2,3,4\}\)，則\(A\capB\)等于（）A.\(\{1,2,3,4\}\)B.\(\{2,3\}\)C.\(\{1,4\}\)D.\(\varnothing\)答案：B。根據(jù)交集的定義，\(A\capB\)是由既屬于\(A\)又屬于\(B\)的所有元素組成的集合，所以\(A\capB=\{2,3\}\)。2.命題公式\((p\landq)\top\)是（）A.重言式B.矛盾式C.可滿足式D.以上都不對(duì)答案：A。通過(guò)真值表法，列出\((p\landq)\top\)的真值表：|\(p\)|\(q\)|\(p\landq\)|\((p\landq)\top\)||---|---|---|---||\(T\)|\(T\)|\(T\)|\(T\)||\(T\)|\(F\)|\(F\)|\(T\)||\(F\)|\(T\)|\(F\)|\(T\)||\(F\)|\(F\)|\(F\)|\(T\)|對(duì)于命題變?cè)猏(p\)和\(q\)的所有可能賦值，公式的值都為真，所以該命題公式是重言式。3.設(shè)\(R\)是集合\(A\)上的等價(jià)關(guān)系，\(A=\{1,2,3\}\)，\(R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}\)，則\(A\)中元素\(3\)所在的等價(jià)類\([3]_R\)為（）A.\(\{1\}\)B.\(\{2\}\)C.\(\{3\}\)D.\(\{1,2,3\}\)答案：C。根據(jù)等價(jià)類的定義，對(duì)于集合\(A\)上的等價(jià)關(guān)系\(R\)，元素\(a\)所在的等價(jià)類\([a]_R=\{x\inA|(a,x)\inR\}\)。對(duì)于元素\(3\)，滿足\((3,x)\inR\)的\(x\)只有\(zhòng)(3\)本身，所以\([3]_R=\{3\}\)。4.無(wú)向圖\(G=(V,E)\)中，頂點(diǎn)\(v\)的度數(shù)\(d(v)\)是指（）A.與\(v\)相鄰的頂點(diǎn)數(shù)B.與\(v\)關(guān)聯(lián)的邊數(shù)C.從\(v\)出發(fā)的邊數(shù)D.到達(dá)\(v\)的邊數(shù)答案：B。在無(wú)向圖中，頂點(diǎn)的度數(shù)是指與該頂點(diǎn)關(guān)聯(lián)的邊的數(shù)目。5.設(shè)\(f:A\toB\)是一個(gè)函數(shù)，若對(duì)于任意的\(y\inB\)，都存在\(x\inA\)使得\(f(x)=y\)，則稱\(f\)是（）A.單射B.滿射C.雙射D.以上都不對(duì)答案：B。滿射的定義就是對(duì)于函數(shù)\(f:A\toB\)，\(B\)中的每一個(gè)元素在\(A\)中都有原像，即對(duì)于任意的\(y\inB\)，都存在\(x\inA\)使得\(f(x)=y\)。6.設(shè)\(G\)是一個(gè)\(n\)階無(wú)向連通圖，其邊數(shù)為\(m\)，則\(m\)滿足（）A.\(m\geqn-1\)B.\(m\leqn-1\)C.\(m=n-1\)D.\(m=n\)答案：A。根據(jù)無(wú)向連通圖的性質(zhì)，一個(gè)\(n\)階無(wú)向連通圖至少有\(zhòng)(n-1\)條邊，當(dāng)它是樹(shù)時(shí)邊數(shù)恰好為\(n-1\)，所以\(m\geqn-1\)。7.謂詞公式\(\forallx(P(x)\toQ(x))\)中，\(\forallx\)的轄域是（）A.\(P(x)\)B.\(Q(x)\)C.\(P(x)\toQ(x)\)D.整個(gè)公式答案：C。在謂詞公式中，量詞后面括號(hào)內(nèi)的公式就是該量詞的轄域，所以\(\forallx\)的轄域是\(P(x)\toQ(x)\)。8.設(shè)\(A=\{a,b,c\}\)，\(A\)上的冪集\(\mathcal{P}(A)\)的元素個(gè)數(shù)為（）A.3B.6C.8D.9答案：C。若集合\(A\)有\(zhòng)(n\)個(gè)元素，則其冪集\(\mathcal{P}(A)\)的元素個(gè)數(shù)為\(2^n\)。因?yàn)閈(A\)中有\(zhòng)(3\)個(gè)元素，所以\(\mathcal{P}(A)\)的元素個(gè)數(shù)為\(2^3=8\)。9.設(shè)\(G\)是一個(gè)有\(zhòng)(n\)個(gè)頂點(diǎn)的簡(jiǎn)單圖，若\(G\)中任意兩個(gè)不相鄰的頂點(diǎn)的度數(shù)之和大于等于\(n-1\)，則\(G\)是（）A.歐拉圖B.哈密頓圖C.平面圖D.二分圖答案：B。根據(jù)哈密頓圖的判定定理，若\(G\)是一個(gè)有\(zhòng)(n\)個(gè)頂點(diǎn)的簡(jiǎn)單圖，且\(G\)中任意兩個(gè)不相鄰的頂點(diǎn)的度數(shù)之和大于等于\(n-1\)，則\(G\)是哈密頓圖。10.設(shè)\(S=\{1,2,3\}\)，\(S\)上的運(yùn)算\(\ast\)定義為：\(a\astb=\max\{a,b\}\)，則\((S,\ast)\)是（）A.半群B.獨(dú)異點(diǎn)C.群D.阿貝爾群答案：A。-封閉性：對(duì)于任意\(a,b\inS\)，\(a\astb=\max\{a,b\}\inS\)，滿足封閉性。-結(jié)合律：設(shè)\(a,b,c\inS\)，\((a\astb)\astc=\max\{\max\{a,b\},c\}=\max\{a,b,c\}\)，\(a\ast(b\astc)=\max\{a,\max\{b,c\}\}=\max\{a,b,c\}\)，滿足結(jié)合律。但不存在單位元，所以\((S,\ast)\)是半群。二、填空題（每題3分，共15分）1.設(shè)集合\(A=\{1,2,3\}\)，\(B=\{2,3,4\}\)，則\(A\cupB=\)______。答案：\(\{1,2,3,4\}\)。根據(jù)并集的定義，\(A\cupB\)是由所有屬于\(A\)或者屬于\(B\)的元素組成的集合。2.命題公式\(\neg(p\landq)\)等價(jià)于______。答案：\(\negp\lor\negq\)。這是根據(jù)德摩根律，\(\neg(p\landq)\equiv\negp\lor\negq\)。3.設(shè)\(R\)是集合\(A=\{1,2,3\}\)上的關(guān)系，\(R=\{(1,2),(2,3),(3,1)\}\)，則\(R\)的傳遞閉包\(t(R)=\)______。答案：\(\{(1,2),(2,3),(3,1),(1,3),(2,1),(3,2),(1,1),(2,2),(3,3)\}\)?？梢酝ㄟ^(guò)Warshall算法或者逐步推導(dǎo)來(lái)計(jì)算傳遞閉包。例如，因?yàn)閈((1,2)\inR\)且\((2,3)\inR\)，所以\((1,3)\int(R)\)等。4.設(shè)無(wú)向圖\(G\)有\(zhòng)(n\)個(gè)頂點(diǎn)，\(m\)條邊，且\(G\)是連通圖，則\(G\)的生成樹(shù)有______條邊。答案：\(n-1\)。連通圖的生成樹(shù)是一個(gè)連通且無(wú)回路的子圖，對(duì)于\(n\)個(gè)頂點(diǎn)的無(wú)向連通圖，其生成樹(shù)的邊數(shù)為\(n-1\)。5.設(shè)\(f:\mathbb{Z}\to\mathbb{Z}\)定義為\(f(x)=2x+1\)，則\(f\)是______（單射、滿射、雙射）。答案：?jiǎn)紊洹?單射證明：假設(shè)\(f(x_1)=f(x_2)\)，即\(2x_1+1=2x_2+1\)，移項(xiàng)可得\(2x_1=2x_2\)，從而\(x_1=x_2\)，所以\(f\)是單射。-滿射判斷：對(duì)于任意的\(y\in\mathbb{Z}\)，若\(y=2x+1\)，則\(x=\frac{y-1}{2}\)，當(dāng)\(y\)為偶數(shù)時(shí)，\(x\notin\mathbb{Z}\)，所以\(f\)不是滿射，也就不是雙射。三、簡(jiǎn)答題（每題10分，共30分）1.畫(huà)出集合\(A=\{1,2,3,4\}\)上的整除關(guān)系\(R\)的哈斯圖，并指出該偏序集的極大元、極小元、最大元和最小元。解：-首先確定整除關(guān)系\(R=\{(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)\}\)。-哈斯圖的繪制：將\(1\)畫(huà)在最底層，\(2\)和\(3\)畫(huà)在第二層，\(4\)畫(huà)在第三層，\(1\)分別與\(2\)、\(3\)、\(4\)有連線，\(2\)與\(4\)有連線。-極大元：\(3\)，\(4\)。極大元是指在偏序集中沒(méi)有比它更大的元素與之可比的元素。-極小元：\(1\)。極小元是指在偏序集中沒(méi)有比它更小的元素與之可比的元素。-最大元：無(wú)。因?yàn)椴淮嬖谝粋€(gè)元素能大于等于集合中的所有元素。-最小元：\(1\)。因?yàn)閈(1\)小于等于集合中的其他所有元素。2.已知有向圖\(G=(V,E)\)，其中\(zhòng)(V=\{v_1,v_2,v_3,v_4\}\)，\(E=\{(v_1,v_2),(v_2,v_3),(v_3,v_4),(v_4,v_1)\}\)，判斷該有向圖是否為強(qiáng)連通圖、單向連通圖和弱連通圖，并說(shuō)明理由。解：-強(qiáng)連通圖：對(duì)于有向圖\(G\)中任意兩個(gè)頂點(diǎn)\(u\)和\(v\)，都存在從\(u\)到\(v\)的路徑和從\(v\)到\(u\)的路徑。在該有向圖中，\(v_1\tov_2\tov_3\tov_4\tov_1\)，任意兩個(gè)頂點(diǎn)之間都可以相互到達(dá)，所以該有向圖是強(qiáng)連通圖。-單向連通圖：若對(duì)于有向圖\(G\)中任意兩個(gè)頂點(diǎn)\(u\)和\(v\)，至少存在從\(u\)到\(v\)或者從\(v\)到\(u\)的路徑。因?yàn)槭菑?qiáng)連通圖，必然滿足單向連通圖的條件，所以該有向圖是單向連通圖。-弱連通圖：將有向圖的邊視為無(wú)向邊后得到的無(wú)向圖是連通的。把該有向圖的邊視為無(wú)向邊后，得到的無(wú)向圖是連通的，所以該有向圖是弱連通圖。3.用謂詞邏輯符號(hào)化下列命題：“所有的大學(xué)生都喜歡學(xué)習(xí)，有的大學(xué)生喜歡運(yùn)動(dòng)”。解：設(shè)\(S(x)\)表示“\(x\)是大學(xué)生”，\(L(x)\)表示“\(x\)喜歡學(xué)習(xí)”，\(P(x)\)表示“\(x\)喜歡運(yùn)動(dòng)”。-“所有的大學(xué)生都喜歡學(xué)習(xí)”可符號(hào)化為\(\forallx(S(x)\toL(x))\)。-“有的大學(xué)生喜歡運(yùn)動(dòng)”可符號(hào)化為\(\existsx(S(x)\landP(x))\)。所以整個(gè)命題可符號(hào)化為\(\forallx(S(x)\toL(x))\land\existsx(S(x)\landP(x))\)。四、證明題（每題10分，共20分）1.證明：\((p\toq)\land(q\tor)\to(p\tor)\)是重言式。證明：方法一：真值表法列出\((p\toq)\land(q\tor)\to(p\tor)\)的真值表：|\(p\)|\(q\)|\(r\)|\(p\toq\)|\(q\tor\)|\((p\toq)\land(q\tor)\)|\(p\tor\)|\((p\toq)\land(q\tor)\to(p\tor)\)||---|---|---|---|---|---|---|---||\(T\)|\(T\)|\(T\)|\(T\)|\(T\)|\(T\)|\(T\)|\(T\)||\(T\)|\(T\)|\(F\)|\(T\)|\(F\)|\(F\)|\(F\)|\(T\)||\(T\)|\(F\)|\(T\)|\(F\)|\(T\)|\(F\)|\(T\)|\(T\)||\(T\)|\(F\)|\(F\)|\(F\)|\(T\)|\(F\)|\(F\)|\(T\)||\(F\)|\(T\)|\(T\)|\(T\)|\(T\)|\(T\)|\(T\)|\(T\)||\(F\)|\(T\)|\(F\)|\(T\)|\(F\)|\(F\)|\(T\)|\(T\)||\(F\)|\(F\)|\(T\)|\(T\)|\(T\)|\(T\)|\(T\)|\(T\)||\(F\)|\(F\)|\(F\)|\(T\)|\(T\)|\(T\)|\(T\)|\(T\)|對(duì)于命題變?cè)猏(p\)、\(q\)和\(r\)的所有可能賦值，公式的值都為真，所以該命題公式是重言式。方法二：邏輯等價(jià)推導(dǎo)\((p\toq)\land(q\tor)\to(p\tor)\)\(\equiv\neg((\negp\lorq)\land(\negq\lorr))\lor(\negp\lorr)\)（根據(jù)蘊(yùn)含等值式）\(\equiv(\neg(\negp\lorq)\lor\neg(\negq\lorr))\lor(\negp\lorr)\)（根據(jù)德摩根律）\(\equiv((p\land\negq)\lor(q\land\negr))\lor(\negp\lorr)\)（根據(jù)德摩根律）\(\equiv(p\land\negq)\lor(q\land\negr)\lor\negp\lorr\)\(\equiv((p\land\negq)\lor\negp)\lor((q\land\negr)\lorr)\)\(\equiv((p\lor\negp)\land(\negq\lor\negp))\lor((q\lorr)\land(\negr\lorr))\)（根據(jù)分配律）\(\equiv(T\land(\negq\lor\negp))\lor((q\lorr)\landT)\)\(\equiv\negq\lor\negp\lorq\lorr\)\(\equiv(\negq\lorq)\lor\negp\lorr\)\(\equivT\lor\negp\lorr\)\(\equivT\)所以該命題公式是重言式。2.設(shè)\(G=(V,E)\)是一個(gè)無(wú)向連通圖，\(T\)是\(G\)的一棵生成樹(shù)，證明：\(G\)中任意一條不屬于\(T\)的邊\(e\)與\(T\)構(gòu)成一個(gè)唯一的回路。證明：-存在性：設(shè)\(e=(u,v)\)是\(G\)中不屬于\(T\)的邊。因?yàn)閈(T\)是\(G\)的生成樹(shù)，所以\(T\)是連通的，在\(T\)中存在從\(u\)到\(v\)的唯一路徑\(P\)。那么邊\(e\)與路徑\(P\)就構(gòu)成了一個(gè)回路\(C\)。-唯一性：假設(shè)存在兩個(gè)不同的回路\(C_1\)和\(C_2\)都由邊\(e\)與\(T\)構(gòu)成。那么\(C_1-e\)和\(C_2-e\)是\(T\)中兩條不同的從\(u\)到\(v\)的路徑，這與樹(shù)中任意兩個(gè)頂點(diǎn)之間存在唯一路徑相矛盾。所以\(G\)中任意一條不屬于\(T\)的邊\(e\)與\(T\)構(gòu)成一個(gè)唯一的回路。五、應(yīng)用題（15分）某公司要在\(A\)、\(B\)、\(C\)、\(D\)四個(gè)城市之間建立通信網(wǎng)絡(luò)，已知各城市之間鋪設(shè)線路的費(fèi)用如下表所示：||\(A\)|\(B\)|\(C\)|\(D\)||---|---|---|---|---||\(A\)|0|3|4|7||\(B\)|3|0|5|6||\(C\)|4|5|0|2||\(D\)|7|6|2|0|請(qǐng)用Pr