2011年西安電子科技大學(xué)考研復(fù)試-離散

1、離散數(shù)學(xué)試題與答案試卷一一、填空 1設(shè) （N：自然數(shù)集，E+ 正偶數(shù)） 則 。2A，B，C表示三個(gè)集合，文圖中陰影部分的集合表達(dá)式為 A B C 。3設(shè)P，Q 的真值為0，R，S的真值為1，則的真值= 。4公式的主合取范式為 。5若解釋I的論域D僅包含一個(gè)元素，則 在I下真值為 。6設(shè)A=1，2，3，4，A上關(guān)系圖為則 R2 = 。7設(shè)A=a，b，c，d，其上偏序關(guān)系R的哈斯圖為則 R= 。8圖的補(bǔ)圖為 。9設(shè)A=a，b，c，d ，A上二元運(yùn)算如下：*a b c dabcda b c db c d ac d a bd a b c那么代數(shù)系統(tǒng)的幺元是 ，有逆元的元素為 ，它們的逆元分別為 。10

2、下圖所示的偏序集中，是格的為 。 二、選擇 20% （每小題 2分）1、下列是真命題的有（）A ； B； C ； D 。2、下列集合中相等的有（ ） A4，3；B，3，4；C4，3，3；D 3，4。3、設(shè)A=1，2，3，則A上的二元關(guān)系有（ ）個(gè)。 A 23 ； B 32 ； C ； D 。4、設(shè)R，S是集合A上的關(guān)系，則下列說法正確的是（ ） A若R，S 是自反的， 則是自反的； B若R，S 是反自反的， 則是反自反的； C若R，S 是對(duì)稱的， 則是對(duì)稱的； D若R，S 是傳遞的， 則是傳遞的。5、設(shè)A=1，2，3，4，P（A）（A的冪集）上規(guī)定二元系如下則P（A）/ R=（ ）AA ；BP

3、(A) ；C1，1，2，1，2，3，1，2，3，4；D，2，2，3，2，3，4，A6、設(shè)A=，1，1，3，1，2，3則A上包含關(guān)系“”的哈斯圖為（ ）7、下列函數(shù)是雙射的為（ ）Af : IE , f (x) = 2x ； Bf : NNN, f (n) = ；Cf : RI , f (x) = x ； Df :IN, f (x) = | x | 。（注：I整數(shù)集，E偶數(shù)集， N自然數(shù)集，R實(shí)數(shù)集）8、圖 中 從v1到v3長(zhǎng)度為3 的通路有（ ）條。A 0；B 1；C 2；D 3。9、下圖中既不是Eular圖，也不是Hamilton圖的圖是（ ）10、在一棵樹中有7片樹葉，3個(gè)3度結(jié)點(diǎn)，其余都

4、是4度結(jié)點(diǎn)則該樹有（ ）個(gè)4度結(jié)點(diǎn)。A1；B2；C3；D4 。三、證明 、 R是集合X上的一個(gè)自反關(guān)系，求證：R是對(duì)稱和傳遞的，當(dāng)且僅當(dāng) 和在R中有在R中。（8分）、 f和g都是群到的同態(tài)映射，證明是的一個(gè)子群。其中C= (8分)、 G= (|V| = v，|E|=e ) 是每一個(gè)面至少由k（k3）條邊圍成的連通平面圖，則， 由此證明彼得森圖（Peterson）圖是非平面圖。（11分）四、邏輯推演 16%用CP規(guī)則證明下題（每小題 8分）1、2、五、計(jì)算 18%1、設(shè)集合A=a，b，c，d上的關(guān)系R= , , , 用矩陣運(yùn)算求出R的傳遞閉包t (R)。 （9分）2、如下圖所示的賦權(quán)圖表示某七個(gè)

5、城市及預(yù)先算出它們之間的一些直接通信線路造價(jià)，試給出一個(gè)設(shè)計(jì)方案，使得各城市之間能夠通信而且總造價(jià)最小。（分）試卷一答案：一、填空 20% （每小題2分）1、0，1，2，3，4，6； 2、；3、1； 4、； 5、1；6、, , , ；7、, IA ；8、9、a ；a , b , c ,d ；a , d , c , d ；10、c; 二、選擇 20% （每小題 2分）題目12345678910答案C DB、CCADCADBA三、證明 26%1、 證：“” 若由R對(duì)稱性知，由R傳遞性得 “” 若，有 任意 ，因若 所以R是對(duì)稱的。若， 則 即R是傳遞的。2、 證，有 ，又 是 的子群。3、 證：設(shè)

6、G有r個(gè)面，則，即 。而 故即得 。（8分）彼得森圖為，這樣不成立，所以彼得森圖非平面圖。（3分） 一、 邏輯推演 16%1、 證明：P（附加前提）TIPTITITIPTICP2、證明 P（附加前提）USPUSTIUGCP二、 計(jì)算 18%1、 解： ， ，t (R)= , , , , , , , , 2、 解： 用庫斯克（Kruskal）算法求產(chǎn)生的最優(yōu)樹。算法略。結(jié)果如圖：樹權(quán)C(T)=23+1+4+9+3+17=57即為總造價(jià)。試卷五試題與答案一、填空15%（每空3分）1、設(shè)G為9階無向圖，每個(gè)結(jié)點(diǎn)度數(shù)不是5就是6，則G中至少有 個(gè)5度結(jié)點(diǎn)。2、n階完全圖，Kn的點(diǎn)數(shù)X (Kn) = 。

7、3、有向圖 中從v1到v2長(zhǎng)度為2的通路有 條。4、設(shè)R，+，是代數(shù)系統(tǒng)，如果R，+是交換群 R，是半群 則稱R，+，為環(huán)。5、設(shè)是代數(shù)系統(tǒng)，則滿足冪等律，即對(duì)有 。二、選擇15%（每小題3分）1、 下面四組數(shù)能構(gòu)成無向簡(jiǎn)單圖的度數(shù)列的有（ ）。A、（2，2，2，2，2）； B、（1，1，2，2，3）；C、（1，1，2，2，2）； D、（0，1，3，3，3）。2、 下圖中是哈密頓圖的為（ ）。3、 如果一個(gè)有向圖D是強(qiáng)連通圖，則D是歐拉圖，這個(gè)命題的真值為（ ）A、真； B、假。4、 下列偏序集（ ）能構(gòu)成格。5、 設(shè)，*為普通乘法，則S，*是（）。A、代數(shù)系統(tǒng)； B、半群； C、群； D、都

8、不是。三、證明 48%1、（10%）在至少有2個(gè)人的人群中，至少有2 個(gè)人，他們有相同的朋友數(shù)。2、（8%）若圖G中恰有兩個(gè)奇數(shù)度頂點(diǎn)，則這兩個(gè)頂點(diǎn)是連通的。3、（8%）證明在6個(gè)結(jié)點(diǎn)12條邊的連通平面簡(jiǎn)單圖中， 每個(gè)面的面數(shù)都是3。4、（10%）證明循環(huán)群的同態(tài)像必是循環(huán)群。5、（12%）設(shè)是布爾代數(shù)，定義運(yùn)算*為，求證B，*是阿貝爾群。四、計(jì)算22%1、在二叉樹中1） 求帶權(quán)為2，3，5，7，8的最優(yōu)二叉樹T。（5分）2） 求T對(duì)應(yīng)的二元前綴碼。（5分）2、 下圖所示帶權(quán)圖中最優(yōu)投遞路線并求出投遞路線長(zhǎng)度（郵局在D點(diǎn)）。答案：一、填空（15%）每空3 分1、 6；2、n；3、2；4、+對(duì)分

9、配且對(duì)+分配均成立；5、。二、選擇（15%）每小題3分題目12345答案A,BB,DBCD三、證明（48%）1、（10分）證明：用n個(gè)頂點(diǎn)v1，vn表示n個(gè)人，構(gòu)成頂點(diǎn)集V=v1，vn，設(shè)，無向圖G=（V，E）現(xiàn)證G中至少有兩個(gè)結(jié)點(diǎn)度數(shù)相同。事實(shí)上，（1）若G中孤立點(diǎn)個(gè)數(shù)大于等于2，結(jié)論成立。（2） 若G中有一個(gè)孤立點(diǎn)，則G中的至少有3個(gè)頂點(diǎn)，既不考慮孤立點(diǎn)。設(shè)G中每個(gè)結(jié)點(diǎn)度數(shù)均大于等于1，又因?yàn)镚為簡(jiǎn)單圖，所以每個(gè)頂點(diǎn)度數(shù)都小于等于n-1，由于G中n頂點(diǎn)其度數(shù)取值只能是1，2，n-1，由鴿巢原理，必然至少有兩個(gè)結(jié)點(diǎn)度數(shù)是相同的。2、（8分）證：設(shè)G中兩個(gè)奇數(shù)度結(jié)點(diǎn)分別為u，v。若 u，v不連

10、通則至少有兩個(gè)連通分支G1、G2，使得u，v分別屬于G1和G2。于是G1與G2中各含有一個(gè)奇數(shù)度結(jié)點(diǎn)，與握手定理矛盾。因而u，v必連通。3（8分）證：n=6,m=12 歐拉公式n-m+f=2知 f=2-n+m=2-6-12=8由圖論基本定理知：，而，所以必有，即每個(gè)面用3條邊圍成。4（10分） 證：設(shè)循環(huán)群A，的生成元為a，同態(tài)映射為f，同態(tài)像為f（A），*，于是都有對(duì)n=1有n=2, 有若n=k-1時(shí) 有對(duì)n=k時(shí)，這表明，f(A)中每一個(gè)元素均可表示為，所以f(A),*為f(a) 生成的循環(huán)群。5、證：（1） 交換律：有 （2） 結(jié)合律：有而：（3） 幺：有（4） 逆： 綜上所述：B，*是

11、阿貝爾群。四、計(jì)算（22%）1、（10分）（1）（5分）由Huffman方法,得最佳二叉樹為：（2）（5分）最佳前綴碼為：000，001，01，10，112、（12分） 圖中奇數(shù)點(diǎn)為E、F ，d(E)=3,d(F)=3,d(E,F)=28 p=EGF復(fù)制道路EG、GF，得圖G，則G是歐拉圖。由D開始找一條歐拉回路：DEGFGEBACBDCFD。道路長(zhǎng)度為：35+8+20+20+8+40+30+50+19+6+12+10+23=281。試卷四試題與答案一、 填空 10% （每小題 2分）1、 若P，Q，為二命題，真值為0 當(dāng)且僅當(dāng) 。2、 命題“對(duì)于任意給定的正實(shí)數(shù)，都存在比它大的實(shí)數(shù)”令F(x

12、)：x為實(shí)數(shù)，則命題的邏輯謂詞公式為 。3、 謂詞合式公式的前束范式為 。4、 將量詞轄域中出現(xiàn)的 和指導(dǎo)變?cè)粨Q為另一變?cè)?hào)，公式其余的部分不變，這種方法稱為換名規(guī)則。5、 設(shè)x是謂詞合式公式A的一個(gè)客體變?cè)?，A的論域?yàn)镈，A(x)關(guān)于y是自由的，則 被稱為存在量詞消去規(guī)則，記為ES。二、 選擇 1、 下列語句是命題的有（ ）。A、 明年中秋節(jié)的晚上是晴天； B、；C、當(dāng)且僅當(dāng)x和y都大于0； D、我正在說謊。2、 下列各命題中真值為真的命題有（ ）。A、 2+2=4當(dāng)且僅當(dāng)3是奇數(shù)；B、2+2=4當(dāng)且僅當(dāng)3不是奇數(shù)；C、2+24當(dāng)且僅當(dāng)3是奇數(shù)； D、2+24當(dāng)且僅當(dāng)3不是奇數(shù)；3、 下

13、列符號(hào)串是合式公式的有（ ）A、；B、；C、；D、。4、 下列等價(jià)式成立的有（ ）。A、；B、；C、 ； D、。5、 若和B為wff，且則（ ）。A、稱為B的前件； B、稱B為的有效結(jié)論C、當(dāng)且僅當(dāng)；D、當(dāng)且僅當(dāng)。6、 A，B為二合式公式，且，則（ ）。A、為重言式； B、；C、； D、； E、為重言式。7、 “人總是要死的”謂詞公式表示為（ ）。（論域?yàn)槿倐€(gè)體域）M(x)：x是人；Mortal(x)：x是要死的。A、； B、C、；D、8、 公式的解釋I為：個(gè)體域D=2，P(x)：x3, Q(x)：x=4則A的真值為（ ）。A、1； B、0； C、可滿足式； D、無法判定。9、 下列等價(jià)關(guān)系

14、正確的是（ ）。A、；B、；C、；D、。10、 下列推理步驟錯(cuò)在（ ）。PUSPESTIEGA、；B、；C、；D、三、 邏輯判斷 1、 用等值演算法和真值表法判斷公式的類型。（10分）2、 下列問題，若成立請(qǐng)證明，若不成立請(qǐng)舉出反例：（10分）（1） 已知，問成立嗎？（2） 已知，問成立嗎？3、 如果廠方拒絕增加工資，那么罷工就不會(huì)停止，除非罷工超過一年并且工廠撤換了廠長(zhǎng)。問：若廠方拒絕增加工資，面罷工剛開始，罷工是否能夠停止。（10分）四、計(jì)算1、 設(shè)命題A1，A2的真值為1，A3，A4真值為0，求命題的真值。（5分）2、 利用主析取范式，求公式的類型。（5分）五、謂詞邏輯推理 符號(hào)化語句：

15、“有些人喜歡所有的花，但是人們不喜歡雜草，那么花不是雜草”。并推證其結(jié)論。六、證明：設(shè)論域D=a , b , c，求證：。答案：一、 填空 10%（每小題2分）1、P真值為1，Q的真值為0；2、；3、；4、約束變?cè)?、，y為D的某些元素。二、 選擇 25%（每小題2.5分）題目12345678910答案A,CA,DC,DA,DB,CA,B,C,D,ECAB(4)三、 邏輯判斷 30%1、（1）等值演算法（2）真值表法P QA1 1111111 0010010 1100010 011111所以A為重言式。2、（1）不成立。若取但A與B不一定等價(jià)，可為任意不等價(jià)的公式。（2）成立。 證明：即：所

16、以故 。3、解：設(shè)P：廠方拒絕增加工資；Q：罷工停止；R罷工超壺過一年；R：撤換廠長(zhǎng)前提： 結(jié)論：PPTIPTITETI罷工不會(huì)停止是有效結(jié)論。四、計(jì)算 10%1、 解：2、它無成真賦值，所以為矛盾式。五、謂詞邏輯推理 15%解： 證明：PESTITIPUSTITEUSUSTIUG四、 證明10% 試卷十五試題與答案一、 填空 20% （每空 2分）1、 如果有限集合A有n個(gè)元素，則|2A|= 。2、 某集合有101個(gè)元素，則有 個(gè)子集的元素為奇數(shù)。3、 設(shè)S=a1，a2,，a8，Bi是S的子集，由B17表達(dá)的子集 ，子集a2,a6,a7規(guī)定為 。4、 由A1，A2,，An，生成的最小集的形式

17、為 ，它們的并為 集，它們的交為 集。5、 某人有三個(gè)兒子，組成集合A=S1,S2,S3，在A上的兄弟關(guān)系具有 性質(zhì)。6、每一個(gè)良序集必為全序集，而 全序集必為良序集。7、若是函數(shù)，則當(dāng)f是的 ，是f的逆函數(shù)。二、 選擇 15% （每小題 3分）1、 集合的冪集為（ ）。A、；B、；C、；D、2、 下列結(jié)果正確的是（ ）。A、；B、；C、；D、；E、；F、AA=A 。3、 集合的最小集范式為（ ）（由A、B、C生成）。A、 ； B、；C、 ； D、。4、 在（ ） 下有。A、；B、；C、；D、5、 下列二元關(guān)系中是函數(shù)的有（ ）。A、；B、；C、。三、 15% 用Warshall算法，對(duì)集合A

18、=1，2，3，4，5上二元關(guān)系R=,求t（R）。四、15%集合，C*上定義關(guān)系，則R是C*上的一個(gè)等價(jià)關(guān)系，并給出R等價(jià)類的幾何說明。五、計(jì)算 15%1、 設(shè)A=1，2，3，4，S=1，2，3，4，為A的一個(gè)分劃，求由S導(dǎo)出的等價(jià)關(guān)系。（4分）2、 設(shè)為整數(shù)集，關(guān)系為Z上等價(jià)關(guān)系，求R的模K等價(jià)關(guān)系的商集Z/R，并指出R有秩。（5分）3、 設(shè)A=1，2，3，4，5，A上的偏序關(guān)系為求A的子集3，4，5和1，2，3，的上界，下界，上確界和下確界。（6分）六、證明 20%1、 假定，且是一個(gè)滿射，g是個(gè)入射，則f是滿射。（10分）2、 設(shè)f，g是A到B的函數(shù)，證明。（10分）答案 一、填空 20%

19、（每空2分）1、2n；2、2100；3、a4，a8，B01000110（B70）；4、，全集，；5、反自反性、對(duì)稱性、傳遞性；6、有限；7、雙射。二、選擇 15%（每小題 3分）題目12345答案BB，EADB三、Warshall算法 15%解：1時(shí)，1,1=1, A =2時(shí)，M1,2=M4,2=1A=3時(shí)，A的第三列全為0，故A不變4時(shí)，M1,4=M2,4=M4,4=1A= 5時(shí)，M3,5=1 ，這時(shí)A=所以t (R)=, , 。四、 5%證明：對(duì)稱性：。自反性：傳遞性：若所以R是C*上等價(jià)關(guān)系。R兩等價(jià)類：；。五、計(jì)算 15%1、（4分）R= , , , , 。2、（5分）Z/R=0，1，

20、k-1 ，所以R秩為k。3、（6分）3，4，5：上界：1，3；上確界：3；下界：無；下確界：無；1，2，3：上界：1；上確界：1；下界：4；下確界：4。六、證明 20%1、（10分）證明：，由于g是入射，所以存在唯一使，又滿射，對(duì)上述c存在，使得，也即，由g單射，所以即：均存在使得，所以f滿射。2、（10分）證明：試卷十四試題與答案四、 填空 10% （每小題 2分）1、 設(shè)是由有限布爾格誘導(dǎo)的代數(shù)系統(tǒng)，S是布爾格，中所有原子的集合，則 。2、 集合S=，上的二元運(yùn)算*為*那么，代數(shù)系統(tǒng)中的幺元是 , 的逆元是 。3、 設(shè)I是整數(shù)集合，Z3是由模3的同余類組成的同余類集，在Z3上定義+3如下：

21、，則+3的運(yùn)算表為 ；是否構(gòu)成群 。4、 設(shè)G是n階完全圖，則G的邊數(shù)m= 。5、 如果有一臺(tái)計(jì)算機(jī)，它有一條加法指令，可計(jì)算四數(shù)的和。現(xiàn)有28個(gè)數(shù)需要計(jì)算和，它至少要執(zhí)行 次這個(gè)加法指令。五、 選擇 20% （每小題 2分）1、 在有理數(shù)集Q上定義的二元運(yùn)算*，有，則Q中滿足（ ）。1. 所有元素都有逆元； B、只有唯一逆元； C、時(shí)有逆元； D、所有元素都無逆元。2、 設(shè)S=0，1，*為普通乘法，則是（ ）。1. 半群，但不是獨(dú)異點(diǎn)； B、只是獨(dú)異點(diǎn)，但不是群；C、群； D、環(huán)，但不是群。3、圖 給出一個(gè)格L，則L是（ ）。A、分配格； B、有補(bǔ)格； C、布爾格； D、 A,B,C都不對(duì)。

22、3、 有向圖D= ，則長(zhǎng)度為2的通路有（ ）條。A、0； B、1； C、2； D、3 。4、 在Peterson圖中，至少填加（ ）條邊才能構(gòu)成Euler圖。A、1； B、2； C、4； D、5 。六、 判斷 10% （每小題 2分）1、 在代數(shù)系統(tǒng)中如果元素的左逆元存在，則它一定唯一且。（ ）2、 設(shè)是群的子群，則中幺元e是中幺元。（ ）3、 設(shè)， +,為普通加法和乘法，則代數(shù)系統(tǒng)是域。（ ）4、 設(shè)G=是平面圖，|V|=v, |E|=e，r為其面數(shù)，則v-e + r=2。（ ）5、 如果一個(gè)有向圖D是歐拉圖，則D是強(qiáng)連通圖。（ ）四、證明 46%1、 設(shè)，是半群，e是左幺元且，使得，則是群

23、。（10分）2、 循環(huán)群的任何非平凡子群也是循環(huán)群。（10分）3、 設(shè)aH和bH是子群H在群G中的兩個(gè)左陪集，證明：要末，要末 。（8分）4、 設(shè)，是一個(gè)含幺環(huán)，|A|3，且對(duì)任意，都有，則不可能是整環(huán)（這時(shí)稱是布爾環(huán)）。（8分）5、 若圖G不連通，則G的補(bǔ)圖是連通的。（10分）五、布爾表達(dá)式 8%設(shè)是布爾代數(shù)上的一個(gè)布爾表達(dá)式，試寫出其的析取范式和合取范式。六、圖的應(yīng)用 16%1、 構(gòu)造一個(gè)結(jié)點(diǎn)v與邊數(shù)e奇偶性相反的歐拉圖。（6分）2、 假設(shè)英文字母，a，e，h，n，p，r，w，y出現(xiàn)的頻率分別為12%，8%，15%，7%，6%，10%，5%，10%，求傳輸它們的最佳前綴碼，并給出happy

24、 new year的編碼信息。（10分）答案五、 填空 10%（每小題2分）+30120012112022011、；2、，；3、 是；4、；5、9六、 選擇 10%（每小題 2分）題目12345答案CBDBD七、 判斷 10%（每小題2分）題目12345答案NYYNY八、 證明 46%1、（10分）證明：（1）(2) e 是之幺元。事實(shí)上：由于e是左幺元，現(xiàn)證e是右幺元。（3）由（2），（3）知：為群。2、（10分）證明：設(shè)是循環(huán)群,G=(a)，設(shè)是的子群。且，則存在最小正整數(shù)m，使得：，對(duì)任意，必有，故： 即：所以但m是使的最小正整數(shù)，且，所以r=0即：這說明S中任意元素是的乘冪。 所以是以

25、為生成元的循環(huán)群。3、（8分）證明：對(duì)集合，只有下列兩種情況：（1）； （2）對(duì)于，則至少存在，使得，即有，這時(shí)任意，有，故有同理可證：所以 4、（8分）證明：反證法：如果，是整環(huán)，且有三個(gè)以上元素，則存在即有：這與整環(huán)中無零因子條件矛盾。因此不可能是整環(huán)。5、（10分）證明：因?yàn)镚=不連通，設(shè)其連通分支是，則有兩種情況：（1） u , v，分別屬于兩個(gè)不同結(jié)點(diǎn)子集Vi，Vj，由于G(Vi) , G(Vj)是兩連通分支，故(u , v)在不G中，故u , v 在中連通。（2） u ,v ，屬于同一個(gè)結(jié)點(diǎn)子集Vi，可在另一結(jié)點(diǎn)子集Vj中任取一點(diǎn)w，故(u , w),(w , v )均在中，故鄰接

26、邊( u ,w ) ( w , v ) 組成的路連接結(jié)點(diǎn)u和v，即u , v在中也是連通的。五、布爾表達(dá)式 8%函數(shù)表為：00000011010001111000101111011111析取范式：合取范式：六、 樹的應(yīng)用 16%1、（6分）解：2、（10分）解：根據(jù)權(quán)數(shù)構(gòu)造最優(yōu)二叉樹：傳輸它們的最佳前綴碼如上圖所示，happy new year的編碼信息為：10 011 0101 0101 001 110 111 0100 001 111 011 000 附：最優(yōu)二叉樹求解過程如下：試卷十試題與答案一、 填空 10% （每小題 2分）1、 若P，Q為二命題，真值為1，當(dāng)且僅當(dāng) 。2、 對(duì)公式中

27、自由變?cè)M(jìn)行代入的公式為 。3、 的前束范式為 。4、 設(shè)x是謂詞合式公式A的一個(gè)客體變?cè)?，A的論域?yàn)镈，A（x）關(guān)于y的自由的，則 被稱為全稱量詞消去規(guī)則，記為US。5、 與非門的邏輯網(wǎng)絡(luò)為 。二、 選擇 30% （每小題 3分）1、 下列各符號(hào)串，不是合式公式的有（ ）。A、； B、；C、； D、。2、 下列語句是命題的有（ ）。A、2是素?cái)?shù)；B、x+5 6；C、地球外的星球上也有人；D、這朵花多好看呀！。3、 下列公式是重言式的有（ ）。A、；B、；C、；D、4、 下列問題成立的有（ ）。A、 若，則； B、若，則；C、若，則； D、若，則。5、 命題邏輯演繹的CP規(guī)則為（ ）。A、 在

28、推演過程中可隨便使用前提；B、在推演過程中可隨便使用前面演繹出的某些公式的邏輯結(jié)果；C、如果要演繹出的公式為形式，那么將B作為前提，設(shè)法演繹出C；D、設(shè)是含公式A的命題公式，則可用B替換中的A。6、 命題“有的人喜歡所有的花”的邏輯符號(hào)化為（ ）。設(shè)D：全總個(gè)體域，F(xiàn)（x）：x是花，M(x) ：x是人，H(x,y)：x喜歡y A、；B、；C、；D、。7、 公式換名（ ）。A、；B、；C、；D、。8、 給定公式，當(dāng)D=a,b時(shí)，解釋（ ）使該公式真值為0。A、P(a)=0、P(b)=0；B、P(a)=0、P(b)=1；C、P(a)=1、P(b)=0；D、P(a)=1、P(b)=19、 下面蘊(yùn)涵關(guān)

29、系成立的是（ ）。A、；B、；C、；D、。10、下列推理步驟錯(cuò)在（ ）。PUSESUGEGA、；B、；C、；D、。三、 邏輯判斷 28%1、（8分）下列命題相容嗎？2、（10分）用范式方法判斷公式 是否等價(jià)。3、（10分）下列前提下結(jié)論是否有效？今天或者天晴或者下雨。如果天晴，我去看電影；若我去看電影，我就不看書。故我在看書時(shí)，說明今天下雨。四、 計(jì)算 12%1、（5分）給定3個(gè)命題：P：北京比天津人口多；Q：2大于1；R：15是素?cái)?shù)。 求復(fù)合命題：的真值。2、（7分）給定解釋I：D=2，3，L（x,y）為L(zhǎng)( 2 , 2 ) = L ( 3 , 3 ) = 1 , L ( 2 , 3 ) =

30、 L (3 , 2 )=0 ,求謂詞合式公式的真值。五、 邏輯推理20%1、（10分）所有有理數(shù)是實(shí)數(shù)，某些有理數(shù)是整數(shù)，因此某些實(shí)數(shù)是整數(shù)。2、（10分）符號(hào)化語句：“有些病人相信所有的醫(yī)生，但是病人都不相信騙子，所以醫(yī)生都不是騙子”。并推證其結(jié)論。答案九、 填空 15%（每小題3分）十、1、P，Q的真值相同；2、；3、；4、；5、。十一、 選擇 30%（每小題 3分）題目12345678910答案B、CA、CBC、DCDAB、CB、DC十二、 邏輯判斷 28%1、（8分）PAPBTIPTETIFTI所以不相容。2、（10分）所以兩式等價(jià)。3、設(shè)P：今天天晴，Q：今天下雨，R：我不看書，S：

31、我看電影符號(hào)化為：PPTITIPTETI結(jié)論有效。十三、 計(jì)算 12%1、（5分）解：P，Q是真命題，R是假命題。2、（7分）十四、 邏輯推理 20%1、（10分）解：設(shè)R(x)：x是實(shí)數(shù)，Q(x)：x是有理數(shù)，I(x)：x是整數(shù)符號(hào)化：前提：，結(jié)論：PESPUSTITITITIEG2、解：F(x)：x是病人，G(x)：x是醫(yī)生，H(x)：x是騙子，L(x,y)：x相信y符號(hào)化：前提：結(jié)論：PESTITIPUSTITEUSUSTIUG試卷十三試題與答案七、 填空 10% （每小題 2分）1、，*表示求兩數(shù)的最小公倍數(shù)的運(yùn)算（Z表示整數(shù)集合），對(duì)于*運(yùn)算的幺元是 ，零元是 。2、代數(shù)系統(tǒng)中，|A

32、|1，如果分別為的幺元和零元，則的關(guān)系為 。3、設(shè)是一個(gè)群，是阿貝爾群的充要條件是 。4、圖的完全關(guān)聯(lián)矩陣為 。5、一個(gè)圖是平面圖的充要條件是 。八、 選擇 10% （每小題 2分）1、 下面各集合都是N的子集，（ ）集合在普通加法運(yùn)算下是封閉的。A、x | x 的冪可以被16整除； B、x | x 與5互質(zhì)；C、x | x是30的因子； D、x | x是30的倍數(shù)。2、 設(shè)，其中表示模3加法，*表示模2乘法，則積代數(shù)的幺元是（ ）。A、； B、； C、； D、 。3、 設(shè)集合S=1,2,3,6，“”為整除關(guān)系，則代數(shù)系統(tǒng)是（ ）。A、域； B、格，但不是布爾代數(shù)； C、布爾代數(shù)； D、不是代

33、數(shù)系統(tǒng)。4、 設(shè)n階圖G有m條邊，每個(gè)結(jié)點(diǎn)度數(shù)不是k就是k+1，若G中有Nk個(gè)k度結(jié)點(diǎn)，則Nk=（ ）。A、nk； B、n(k+1)； C、n(k+1)-m； D、n(k+1)-2m 。5、 一棵樹有7片樹葉，3個(gè)3度結(jié)點(diǎn)，其余全是4度結(jié)點(diǎn)，則該樹有（ ）個(gè)4度結(jié)點(diǎn)。A、1； B、2； C、3； D、4 。三、判斷10% （每小題 2分）1、（ ）設(shè)S=1,2，則S在普通加法和乘法運(yùn)算下都不封閉。2、（ ）在布爾格中，對(duì)A中任意原子a，和另一非零元b，在或中有且僅有一個(gè)成立。3、（ ）設(shè)，+,為普通加法和乘法，則是域。4、（ ）一條回路和任何一棵生成樹至少有一條公共邊。5、（ ）沒T是一棵m叉

34、樹，它有t片樹葉，i個(gè)分枝點(diǎn)，則(m-1)i = t-1。四、證明 38%1、（8分）對(duì)代數(shù)系統(tǒng)，*是A上二元運(yùn)算，e為A中幺元，如果*是可結(jié)合的且每個(gè)元素都有右逆元，則（1）中的每個(gè)元素在右逆元必定也是左逆元。（2）每個(gè)元素的逆元是唯一的。2、（12分）設(shè)是一個(gè)布爾代數(shù)，如果在A上定義二元運(yùn)算，為，則是一阿貝爾群。3、（10分）證明任一環(huán)的同態(tài)象也是一環(huán)。4、（8分）若是每一個(gè)面至少由k(k3)條邊圍成的連通平面圖，則。五、應(yīng)用 32%1、 （8分）某年級(jí)共有9門選修課程，期末考試前必須提前將這9門課程考完，每人每天只在下午考一門課，若以課程表示結(jié)點(diǎn)，有一人同時(shí)選兩門課程，則這兩點(diǎn)間有邊（其

35、圖如右），問至少需幾天？2、 用washall方法求圖的可達(dá)矩陣，并判斷圖的連通性。（8分）3、 設(shè)有a、b、c、d、e、f、g七個(gè)人，他們分別會(huì)講的語言如下：a：英，b：漢、英，c：英、西班牙、俄，d：日、漢，e：德、西班牙，f：法、日、俄，g：法、德，能否將這七個(gè)人的座位安排在圓桌旁，使得每個(gè)人均能與他旁邊的人交談？（8分）4、 用 Huffman算法求出帶權(quán)為2，3，5，7，8，9的最優(yōu)二叉樹T，并求W（T）。若傳遞a ，b， c， d ，e， f 的頻率分別為2%， 3% ，5 %， 7% ，8% ，9%求傳輸它的最佳前綴碼。（8分）答案：十五、 填空 10%（每小題2分）1、1， 不

36、存在；2、；3、有；4、11100-100010-101-100-1-105、它不包含與K3, 3或K5在2度結(jié)點(diǎn)內(nèi)同構(gòu)的子圖。十六、 選擇 10%（每小題 2分）題目12345答案A，DBCDA十七、 判斷 10%題目12345答案YYNNN十八、 證明 38%1、（8分）證明：（1）設(shè)，b是a的右逆元，c是b的右逆元，由于，所以b是a的左逆元。（2）設(shè)元素a有兩個(gè)逆元b、c，那么a的逆元是唯一的。2、（12分）證明：乘 運(yùn)算在A上也封閉。群 即滿足結(jié)合性。幺 ,故全下界0是A中關(guān)于運(yùn)算的幺元。逆 ,即A中的每一個(gè)元素以其自身為逆元。交 即運(yùn)算具有可交換性。所以是Abel群。3、(10分)

37、證明:設(shè)是一環(huán),且是關(guān)于同態(tài)映射f的同態(tài)象。由是Abel群，易證也是Abel群。是半群，易證也是半群?，F(xiàn)只需證：對(duì)是可分配的。 于是同理可證因此也是環(huán)。5、（8分）證明：設(shè)G有r個(gè)面， 。十九、 應(yīng)用32%1、（8分）解：即為最少考試天數(shù)。用Welch-Powell方法對(duì)G著色：第一種顏色的點(diǎn) ，剩余點(diǎn)第二種顏色的點(diǎn) ，剩余點(diǎn)第三種顏色的點(diǎn) 所以3任構(gòu)成一圈，所以3故=3所以三天下午即可考完全部九門課程。2、（8分）解：1：A2，1=1，； 2： A4，2=1，3： A1，3=A2，3=A4，3=1，4： Ak，4=1，k=1，2，3，4，p中的各元素全為1，所以G是強(qiáng)連通圖，當(dāng)然是單向連通和

38、弱連通。3、（8分）解：用a,b,c,d,e,f,g 7個(gè)結(jié)點(diǎn)表示7個(gè)人，若兩人能交談可用一條無向邊連結(jié)，所得無向圖為此圖中的Hamilton回路即是圓桌安排座位的順序。Hamilton回路為a b d f g e c a。4、（8分）解：(1)（1） 用0000傳輸a、0001傳輸b、001傳輸c、01傳輸f、10傳輸d、11傳輸e傳輸它們的最優(yōu)前綴碼為0000，0001，001，01，10，11 。試卷十七試題與答案九、 判斷正誤 20% （每小題 2分）1、設(shè)A.B. C是任意三個(gè)集合。 （1）若AB且BC，則AC。 （ ） （2）若AB且BC，則AC。 （ ）（3）若AB且BC，則AC

39、。 （ ）（4）A。 （ ）（5）(AB)C=(AC)-(BC)。 （ ）2、可能有某種關(guān)系，既不是自反的，也不是反自反的。（ ）、若兩圖結(jié)點(diǎn)數(shù)相同，邊數(shù)相等，度數(shù)相同的結(jié)點(diǎn)數(shù)目相等，則兩圖是同構(gòu)的。（ ）、一個(gè)圖是平面圖，當(dāng)且僅當(dāng)它包含與3，3或5在度結(jié)點(diǎn)內(nèi)同構(gòu)的子圖。（ ）、代數(shù)系統(tǒng)中一個(gè)元素的左逆元并一定等于該元素的右逆元。（ ）、群是每個(gè)元素都有逆元的半群。（ ）十、 8% 將謂詞公式化為前束析取范式與前束合取范式。十一、 8%設(shè)集合a,b,c,d上的關(guān)系,寫出它的關(guān)系矩陣和關(guān)系圖，并用矩陣運(yùn)算方法求出的傳遞閉包。四、9%、畫一個(gè)有一條歐拉回路和一條漢密爾頓回路的圖。、畫一個(gè)有一條歐拉回路，但沒有一條漢密爾頓回路的圖。、畫一個(gè)有一條歐拉回路，但有一條漢密爾頓回路的圖。五、10% 證明：若圖是不連通的，則的補(bǔ)圖是連通的。六、10%證明：循環(huán)群的任何子群必定也是循環(huán)群。七、12%用規(guī)則證明：。八、10% 用推理規(guī)則證明下式：前提: 結(jié)論：S九、13%若集合（，），（，），（，），1、證明R是X上的等價(jià)關(guān)系。2、求出X關(guān)于R的商集。答案一、 填空 20%（每小題2分）題目123456（1）（2