2019春季學(xué)期離散數(shù)學(xué)語(yǔ)音答疑提綱下(全書考試內(nèi)容)2019春季學(xué)期離散數(shù)學(xué)語(yǔ)音答疑提綱下(全書考試內(nèi)容)2019春季學(xué)期離散數(shù)學(xué)語(yǔ)音答疑提綱下(全書考試內(nèi)容)xxx公司2019春季學(xué)期離散數(shù)學(xué)語(yǔ)音答疑提綱下(全書考試內(nèi)容)文件編號(hào)：文件日期：修訂次數(shù)：第1.0次更改批準(zhǔn)審核制定方案設(shè)計(jì)，管理制度2019春季學(xué)期《離散數(shù)學(xué)》語(yǔ)音答疑提綱(下)本次語(yǔ)音答疑分兩步完成。第一，回答全書各部分問題。第二，指出全書考試范圍，并給出例題，加以分析。一．2019春季學(xué)期期末考題在參考書中內(nèi)容的分配:集合論部分（共40分）集合的基本概念及運(yùn)算(第三章，2選擇題;共4分).關(guān)系及函數(shù)(第四章，4選擇題-2關(guān)系，2函數(shù);1綜合.共20分).群論(第九章，2題單選;1綜合.共16分).圖論部分（共30分）圖,圖-樹關(guān)系(第五，七章，8選擇題-圖2，圖-樹關(guān)系6;1綜合.共30分).邏輯學(xué)部分（共30分）邏輯學(xué)(第一，二章，8選擇題（7題命題邏輯）;1綜合.共30分).二.參考書第五版各章節(jié)考試范圍內(nèi)的知識(shí)點(diǎn)及例題第三章集合的基本概念和運(yùn)算1.集合的基本概念要求掌握：集合與元素的關(guān)系—屬于或不屬于；（***）集合與集合間的關(guān)系—子集與集合叫包含，相互包含叫相等；子集為集合的元素時(shí)也叫屬于關(guān)系。例題1:設(shè)集合A={1，{2}，a，4，3}，則有2∈A[非];單項(xiàng)選擇題：例題2:A,B，C為任意集合，則他們的共同子集是[D]A．A；B．B；C．C；D．?。例題3：設(shè)集合A={1，{2}，a，4，3}，下面命題為真是[B]A．2∈A；B．1∈A；C．5∈A；D．{2}A。例題4:設(shè)集合A={1，{2}，a，4，3}，則有2（）A。此題為填空題,把2與集合A的關(guān)系填在()內(nèi).*****請(qǐng)比較例題1，3，4，那個(gè)最容易；那個(gè)最難！*****2.集合的基本運(yùn)算重點(diǎn)掌握：五大基本運(yùn)算定義的表達(dá)式。例如,并運(yùn)算的”或”,交運(yùn)算的”且”字的意義.例題：N,Z+分別是自然數(shù)集合,正整數(shù)集合,則[C]A．N=Z++{0}B．N=Z++0C．N=Z+∪{0}D．N=Z+.∪(第四章關(guān)系及函數(shù)1.關(guān)系的基本概念重點(diǎn)掌握：關(guān)系的定義，關(guān)系來(lái)自有序?qū)Γ行驅(qū)?lái)自集合的笛卡兒積；A到B的二元關(guān)系以及A上的二元關(guān)系的條件；2.關(guān)系的五大性質(zhì)及其判斷—難點(diǎn)在于傳遞性的判斷。重點(diǎn)掌握：五大性質(zhì)的判別方式；當(dāng)然，難點(diǎn)在于傳遞性的判斷。量變引起質(zhì)變的示例：等價(jià)關(guān)系—同時(shí)具備自反、對(duì)稱、傳遞性質(zhì)；等價(jià)類，商集與劃分的對(duì)應(yīng)性。例題1、設(shè)A={1，2，3}，A上的關(guān)系R={〈1，3〉，〈3，1〉}∪IA，試求：給出R的關(guān)系圖。1。。2說(shuō)明：每個(gè)頂點(diǎn)都有圈；1到3。及3到1各有一條有向3線。由關(guān)系圖說(shuō)明R的性質(zhì)。自反，對(duì)稱，傳遞。給出合成（R。R）={〈1，3〉，〈3，1〉}∪IA。給出商集A/R的表達(dá)式及所有元素。A/R={{1，3}，{2}}。給出商集A/R所對(duì)應(yīng)的劃分∏?！?{{1，3}，{2}}。試問：你能悟出等價(jià)關(guān)系或商集與劃分的關(guān)系嗎！例題2、設(shè)A={a，b}，B={1，2}，A到B的雙射函數(shù)的數(shù)目是4個(gè)[非]。例題3、設(shè)函數(shù)ｆ：Ｎ→Ｎ，ｆ（ｎ）＝２ｎ＋１，Ｎ為自然數(shù)集合，則函數(shù)性質(zhì)為［Ａ］A．只為單射B．只為滿射C．雙射D．Ａ,Ｂ,Ｃ都不是．.例題4、集合A={1，2，3}，關(guān)系R={〈2，3〉，〈3，2〉}具有[D]***A．自反性；B．反對(duì)稱性；C．傳遞性；D．反自反性。3.關(guān)系及函數(shù)的運(yùn)算重點(diǎn)掌握：求域；求逆；合成運(yùn)算是難點(diǎn)-請(qǐng)看專題討論。例題1:設(shè)ｆ(x)＝ｘ+１，ｇ(x)＝ｘ-１都是從實(shí)數(shù)集合Ｒ到Ｒ的函數(shù)，則ｆ。ｇ＝[D]A．x+1；B．x-1；C．x2；D．x。第九章群論初步1.代數(shù)系統(tǒng)的基本概念重點(diǎn)掌握：二元運(yùn)算必須是函數(shù)；定義了二元運(yùn)算的集合既是代數(shù)系統(tǒng)，代數(shù)系統(tǒng)的封閉性；代數(shù)系統(tǒng)中二元運(yùn)算滿足結(jié)合律算律的重要意義；2.代數(shù)系統(tǒng)中的特殊元素與半群、獨(dú)異點(diǎn)及群的聯(lián)系重點(diǎn)掌握：代數(shù)系統(tǒng)中結(jié)合律算律與半群的關(guān)系—半群的判別；半群中的幺元—獨(dú)異點(diǎn)，每個(gè)元素都有其逆元的獨(dú)異點(diǎn)為群。例題1:自然數(shù)N與其上的普通加法+構(gòu)成的代數(shù)系統(tǒng)〈N，+〉是[C]A．只是代數(shù)系統(tǒng)；B．半群；C．含幺半群；D．群.例題2、設(shè)Z為整數(shù)集合，在Z上定義二元運(yùn)算*，對(duì)于所有x，y∈Z都有x*y=x+y；驗(yàn)證〈Z，*〉能否構(gòu)成代數(shù)系統(tǒng)何種代數(shù)系統(tǒng)為什麼要求有根據(jù)地回答：1、滿足封閉性，構(gòu)成代數(shù)系統(tǒng)。2、經(jīng)驗(yàn)證滿足結(jié)合律，所以為半群。3、幺元為0，所以為幺半群。(經(jīng)解聯(lián)立方程組).4、設(shè)y是x的逆，所以有y=–x。(解聯(lián)立方程組得到)5、結(jié)論：構(gòu)成群。例題3、設(shè)Z為整數(shù)集合，在Z上定義二元運(yùn)算*，對(duì)于所有x，y∈Z都有x*y=x+y-2；驗(yàn)證〈Z，*〉能否構(gòu)成代數(shù)系統(tǒng)何種代數(shù)系統(tǒng)為什麼要求有根據(jù)地回答：1、滿足封閉性，構(gòu)成代數(shù)系統(tǒng)。2、經(jīng)驗(yàn)證滿足結(jié)合律，所以為半群。3、幺元為2，所以為幺半群。(經(jīng)解聯(lián)立方程組).4、設(shè)y是x的逆，所以有y=4–x。(解聯(lián)立方程組得到)5、結(jié)論：構(gòu)成群。例題4、設(shè)Z為整數(shù)集合，在Z上定義二元運(yùn)算*，對(duì)于所有x，y∈Z都有x*y=x+y+2；驗(yàn)證〈Z，*〉能否構(gòu)成代數(shù)系統(tǒng)何種代數(shù)系統(tǒng)為什麼要求有根據(jù)地回答：1、滿足封閉性，構(gòu)成代數(shù)系統(tǒng)。2、經(jīng)驗(yàn)證滿足結(jié)合律，所以為半群。3、幺元為-2，所以為幺半群。(經(jīng)解聯(lián)立方程組).4、設(shè)y是x的逆，所以有y=-4–x。(解聯(lián)立方程組得到)5、結(jié)論：構(gòu)成群。試問：－4的逆為何你能說(shuō)明白嗎！另，x*y=x+y改成x*y=x–y你會(huì)解碼！

第五章圖論1.圖的基本概念重點(diǎn)掌握：階的概念；度的概念：完全圖，補(bǔ)圖概念；母圖與子圖—引出生成圖與導(dǎo)出圖概念的差別；握手定理—度數(shù)之和=2倍邊；握手定理應(yīng)用—圖這一章的所有計(jì)算題的理論依據(jù)。2.圖的分割重點(diǎn)掌握：割集概念—注意割點(diǎn)或橋的特點(diǎn)。請(qǐng)留心割集與基本割集的聯(lián)系。例題1、９階無(wú)向簡(jiǎn)單連通圖Ｇ中，頂點(diǎn)間的最大距離為[A]A．8；B．9；C．10；D．11。第七章樹1.樹的基本概念重點(diǎn)掌握：定義—連通而無(wú)回路，m=n-1；生成樹—引出樹枝、弦、基本回路、基本割集概念。2.根樹重點(diǎn)掌握：根樹的來(lái)源及特點(diǎn)定義；最優(yōu)二元樹及最佳前綴碼。特別要求:必須掌握?qǐng)D----樹關(guān)系.例題1:每條邊都是橋的無(wú)向連通圖必是樹。[是]例題2、n階無(wú)向連通圖G有m條邊，T為G的一棵生成樹，則G對(duì)應(yīng)T的基本回路數(shù)目為[D]A．n；B．n-1；C．m-n；D．m-n+1。例題3、非平凡無(wú)向樹T是連通圖[是]。例題4、根樹中的樹葉都在樹的最高層。[非]例題5、填空題：（1）n階非平凡無(wú)向樹至少兩片樹葉。（2）、圖G（m，n）的階數(shù)n為10，則其生成樹的邊數(shù)為9。例題6、在網(wǎng)上傳輸GOODBYE的最佳前綴碼。每個(gè)字母出現(xiàn)頻率分別為：G、D、B、E、Y：14%，O：28%；(可以對(duì)符號(hào)出現(xiàn)頻率歸一,如下圖右;也可以不歸一,某符號(hào)出現(xiàn)次數(shù)即為權(quán),下圖左).。100（近似）7.42。。563..428。。28。。282..1.2.2。。14。。....141414141111所以，得到編碼如下：G（000），D（001），B（100），E（101），Y（01），O（11）。試問：你能算出傳遞ＧＯＯＤＢＹＥ共用多少位二進(jìn)制碼字？為了說(shuō)明白這個(gè)問題,讓我分兩方面下手:先說(shuō)由沒有歸一的樹葉的權(quán)得到的結(jié)果:G,D,B,E分別用3位二進(jìn)制碼，共12位。加上Y=用2位。再加上兩個(gè)O的4位。總共18位。用樹的權(quán)W(T)=累加wixhi(即每片樹葉的權(quán)x樹葉的高度，加在一起)=1x3+1x3+1x3+1x3+1x2+2x2=18.還有一個(gè)辦法，即把所有分支點(diǎn)的權(quán)加起來(lái)，也是18.請(qǐng)看：要回答傳遞一組符號(hào)所需二進(jìn)制碼總數(shù)設(shè)個(gè)問題，可以的把每個(gè)符號(hào)的碼字?jǐn)?shù)加起來(lái)；或從樹的權(quán)的辦法得到。二者相同。再說(shuō)歸一后得到的結(jié)果：把每個(gè)符號(hào)所用碼字?jǐn)?shù)，加起來(lái)，共18位。但是，若用樹的權(quán)W(T)=4個(gè)14x3加起來(lái)，再加上1個(gè)14x2，再加上28x2,等于252。這個(gè)權(quán)與沒有歸一化得到的結(jié)果是如何不同呀！歸一化的概念是：傳輸100個(gè)按某種頻率（即14，14,14,14,14,28）出現(xiàn)一組符號(hào)所用二進(jìn)制碼數(shù)。我講這些，是為了讓大家得到一個(gè)計(jì)算傳遞一組符號(hào)總共用二進(jìn)制碼數(shù)的簡(jiǎn)單方法。第一章命題邏輯1.基本概念重點(diǎn)掌握：命題—命題定義及簡(jiǎn)單命題；5個(gè)基本聯(lián)結(jié)詞+簡(jiǎn)單命題=復(fù)合命題；簡(jiǎn)單命題的符號(hào)化；2.命題公式及其規(guī)范形式重點(diǎn)掌握：公式的賦值—成真、成假賦值，真值表—公式的類型；范式及主范式—析取范式與合取范式；主范式中極小項(xiàng)與極大項(xiàng)關(guān)系。例題以填空形式給出：例題1、命題公式﹃ｐ→ｑ的類型是（可滿足)式。例題2、命題公式﹃q的主合取范式為(∏(1))。例題以是非形式給出：例題3、命題公式﹃ｐ→ｑ的類型是可滿足式[是]。例題4、命題公式﹃q的主合取范式為∏(1)[是]。例題以選擇形式給出：例題5、命題公式﹃ｐ→ｑ的類型是[C]A．永真式；B．永假式；C．可滿足式；D．不是公式。例題6、命題公式﹃q的主合取范式為[B]A．∏(0)；B．∏(1)；C．0；D．1。3.推理理論重點(diǎn)掌握：定義推理正