華南農(nóng)業(yè)大學(xué) 離散數(shù)學(xué) 期末考試試卷及答案

華南農(nóng)業(yè)大學(xué)期末考試試卷（A卷）-第 一 學(xué)期 考試科目： 離散構(gòu)造 考試類型：（閉卷）考試 考試時(shí)間：120 分鐘學(xué)號(hào) 姓名 年級(jí)專業(yè) 題號(hào)一二三四五總分得分評(píng)閱人 林旭東 黃華偉 朱梅階 黃沛杰考試注意事項(xiàng)： 本試題分為試卷與答卷2部分。試卷有五大題，共4頁(yè)。所有解答必須寫在答卷上，寫在試卷上不得分。得分一、選擇題（本大題共 10 小題，每題 2 分，共 20 分）1、重言式的否認(rèn)是（ ）A、重言式 B、矛盾式 C、可滿足式 D、 A-C均有也許2、：在北京工作，：是北京人；則命題“在北京工作的人都是北京人。”可表達(dá)為_。A、 B、C、 D、3、設(shè) p:天冷, q:小王穿羽絨服，下列命題中，和命題“只要天冷，小王就穿羽絨服?！蓖瑯臃?hào)化為 p®q 的是_。A、如果天不冷，則小王不穿羽絨服。B、小王穿羽絨服僅當(dāng)天冷的時(shí)候。C、除非小王穿羽絨服，否則天不冷。D、只有天冷，小王才穿羽絨服4、下列哪個(gè)體現(xiàn)式錯(cuò)誤_。A、 B、 C、 D、 5、設(shè)，定義A上的關(guān)系，則R具有的性質(zhì)為_。A、自反的 B、對(duì)稱的C、傳遞的，對(duì)稱的 D、傳遞的6、設(shè)V=<R*,×>是代數(shù)系統(tǒng), R*為非零實(shí)數(shù)的集合，×為一般乘法，下面函數(shù)中是V 的自同態(tài)的是_。A、f(x)=2x B、f(x)= -x C、 f(x)=1/x D、f(x)=x+17、設(shè)V=<Z,+>是代數(shù)系統(tǒng), Z為整數(shù)的集合，+為一般加法在，則 (-2)-3= _。A、-8 B、8 C、-6 D、68、給定下列各序列，可以構(gòu)成無(wú)向簡(jiǎn)樸圖的度數(shù)序列為_。A、1,1,2,2,3 B、1,1,2,3,3 C、0,1,1,3,3 D、1,3,4,4,59、具有6 個(gè)頂點(diǎn)，12條邊的連通簡(jiǎn)樸平面圖中，次數(shù)為3的面有_個(gè)。A、5 B、 6C、 7D、 810、在下面所示的4個(gè)圖中，_不是單向連通圖。A、B、C、D、得分二、填空題（本大題共 15 空，每空 2 分，共 30 分）1、pq 的主合取范式是_。2、體現(xiàn)式中謂詞的個(gè)體域是，將其中的量詞消去，寫成與之等價(jià)的命題公式為_。3、若明天是星期一或星期三，我就有課。若有課，今天必備課。我今天下午備課。 因此，明天不是星期一和星期三。 將命題中的4個(gè)簡(jiǎn)樸命題依次符號(hào)化為，p：明天是星期一，q：明天是星期三，r：我有課，s：我備課。則推理的形式構(gòu)造為：前提：_；結(jié)論：_。4、的前束范式為：_。5、設(shè)R，S是集合上的兩個(gè)關(guān)系，其中，,則_。6、設(shè)偏序集的哈斯圖如右所示，若A的子集，則B的最大下界為_。7、在整數(shù)集上定義二元運(yùn)算，有，則有關(guān)運(yùn)算 的幺元是_。8、設(shè)a是12階群的生成元，則a3是 階元素9、若連通平面圖G有4個(gè)結(jié)點(diǎn)，3個(gè)面，則G有 條邊。10、在右邊的PERT圖中，核心途徑為_。11、一顆帶權(quán)為2,3,5,7,8,9的最優(yōu)2元樹，其權(quán)為_。12、1400 的不同的正因子個(gè)數(shù)為_。13、滿足等式的非負(fù)整數(shù)解的個(gè)數(shù)有_。14、n階無(wú)向樹至少有_片樹葉。（n>=2）得分1.5CM三、計(jì)算題：（6+4+6+6，共 22 分）1、設(shè)A=1, 2, 3, 4，R=<x，y>|xÎA，yÎA且x+y<5（1）寫出R的集合體現(xiàn)式和關(guān)系矩陣，畫出R的關(guān)系圖。（2）畫出關(guān)系R的自反閉包r(R)、對(duì)稱閉包s(R)和傳遞閉包t(R)的關(guān)系圖。2、分別畫出下面無(wú)向圖A的關(guān)聯(lián)矩陣和有向圖B的鄰接矩陣。v1v2v3v4圖Be1e2e3e5e4v1v2V4V3圖Ae2e1e3e4e53、求下面帶權(quán)圖中v1到其他頂點(diǎn)的最短途徑及相應(yīng)的權(quán)。v1v4v2v3v5v631064322244、設(shè)有5個(gè)都市，任意兩都市之間的鐵路造價(jià)如下（以百萬(wàn)元為單位）：W(v1, v2)=4, W(v1, v3)=7, W(v1, v4)=16, W(v1, v5)=10, W(v2,v3)=13, W(v2, v4)=8, W(v2, v5)=17, W(v3, v4 )=3, W(v3 ,v5)=10， W(v4, v5)=12。試求出連接5個(gè)都市的且造價(jià)最低的鐵路網(wǎng)。四、證明題：（本大題共 4 個(gè)小題，每題 6 分，共 24 分）1、用等值演算法證明下面的等值式2、設(shè) A為整數(shù)集合，在 A´A上定義二元關(guān)系R：<<x,y>,<u,v>>ÎR Û x+y = u+v，證明：R是A´A上的等價(jià)關(guān)系。3、符號(hào)化下列各命題，并闡明結(jié)論與否有效（用推理規(guī)則）。甲乙丙丁四人參與拳擊比賽，如果甲獲勝，則乙失敗；如果丙獲勝，則乙也獲勝，如果甲不獲勝，則丁不失敗。因此，如果丙獲勝，則丁不失敗。4、設(shè)<G, *>是群，給定aG，令H=y| y*a=a*y, yG，證明：<H, *>是G的子群。五、應(yīng)用題（共4分）若有n個(gè)人，每個(gè)人都恰有三個(gè)朋友，則n必為偶數(shù)。華南農(nóng)業(yè)大學(xué)期末考試參照答案（A卷）得分一、選擇題（本大題共 10 小題，每題 2 分，共 20 分）1B2D3C4C5B6C7D8B9D10C得分二、填空題（本大題共 15 空，每空 2 分，共 30 分）1、 ¬pq ； 2、； 3、 (pq)r, rs, s ； ¬p ¬q ；4、；5、； 6、 2 ；7、 2 ； 8、 4 ； 9、 5 ； 10、v1v3v7v8； 11、 83 ； 12、 24 ； 13、 165（或，或） 14、 2 得分1.5CM三、計(jì)算題：（6+4+6+6，共 22 分）1、 R的集合體現(xiàn)式： R的關(guān)系矩陣: R的關(guān)系圖： R的自反閉包r(R)關(guān)系圖： 對(duì)稱閉包s(R)關(guān)系圖： 傳遞閉包t(R)關(guān)系圖： 2、圖A的關(guān)聯(lián)矩陣： 圖B的鄰接矩陣： 3、解：用標(biāo)號(hào)法解題如下：r viv1v2v3v4v5v60034¥¥¥13/ v1413¥¥24/ v176¥376/ v31047/ v3959/ v4w034769v1到v2的最短途徑: v1 v2 ，相應(yīng)的權(quán)為3v1到v3的最短途徑: v1 v3 ，相應(yīng)的權(quán)為4v1到v4的最短途徑: v1 v3 v4 ，相應(yīng)的權(quán)為7v1到v5的最短途徑: v1 v3 v5 ，相應(yīng)的權(quán)為6v1到v6的最短途徑: v1 v3 v4 v6 ，相應(yīng)的權(quán)為94、 解：將本題用帶權(quán)圖來(lái)描述，如下圖(a)，于是求解此題便成為求帶權(quán)圖的最小生成樹問(wèn)題。按Kruskal算法，下圖中(b)-(e) 就是求解最小生成樹的過(guò)程。總造價(jià)=3+4+7+10=24萬(wàn)元得分四、證明題：（本大題共 4 個(gè)小題，每題 5 分，共 20 分）1、 證明：從左邊開始演算: 2、證明：(1)自反性：對(duì)于任意的(2)對(duì)稱性：對(duì)于任意的(3)傳遞性：對(duì)于任意的 3、證明：1. 解：設(shè)p: 甲獲勝； q：乙獲勝；r：丙獲勝；s：丁不敗（或丁獲勝）。前提為：； 結(jié)論為：（1）（2）（3）（4）（5）（6）（7）4、證明： 對(duì)于任一aG，e*a=a*e，群G的幺元 e H, 因此H是 G 的非空子集。 任取 a, bH，下面證明 a*b-1與 G 中所有的元素都可互換. "xG，有 (a*b-1) *x = a*b-1*x = a*b-1* (x-1) -1 = a* (x-1*b) -1 = a* (b*x-1) -1 = a* (x*b-1) = (a*x) *b-1 = (x*a) *b-1 = x* (a*b-1)由此可知，a*b-1 H 由子群鑒定定理可知<H, *>是G的子群。得分五、應(yīng)用題：（共4分）證明：證明：將每個(gè)人用結(jié)點(diǎn)表達(dá)，當(dāng)兩個(gè)人是朋友時(shí)，則相應(yīng)兩結(jié)點(diǎn)連一條邊，則得一無(wú)向圖。由于每個(gè)人恰有三個(gè)朋友，因此，由任意圖奇數(shù)度結(jié)點(diǎn)一定是偶數(shù)個(gè)，可知，此圖結(jié)點(diǎn)數(shù)一定是偶數(shù)。