06級(jí)離散數(shù)學(xué)期末試題A答案

PAGEPAGE206級(jí)離散數(shù)學(xué)期末試題A答案一、計(jì)算題（本題共20分，每小題5分）1、設(shè)A={1,2,3,4}，A上的二元關(guān)系R定義如下：R={<1,2>,<2,2>,<2,4>,<3,4>}，求其自反閉包、對(duì)稱(chēng)閉包。解：自反閉包對(duì)稱(chēng)閉包2、設(shè)N是自然數(shù)集合，定義N上的二元關(guān)系R={<x,y>|x∈N，y∈N，x+y是偶數(shù)}，求關(guān)系R的等價(jià)類(lèi)。解關(guān)系R的等價(jià)類(lèi)有[1]R={1,3,5,……}，[0]R={0,2,4,……}3、設(shè)集合，A上的整除關(guān)系，是否為上的偏序關(guān)系？若是，則：（1）畫(huà)出的哈斯圖；（2）求的極大元和的極小元。解是上的偏序關(guān)系。（1）的哈斯圖：（2）A的極大元為9，15；極小元為3，5。4、畫(huà)出五個(gè)6階非同構(gòu)的無(wú)向樹(shù)解可能的度數(shù)列:(1)1,1,1,1,1,5；(2)1,1,1,1,2,4；(3)1,1,1,1,3,3；(4)1,1,1,2,2,3；(5)1,1,2,2,2,2(1(1)(2)(4a(4b)(5)(3)二、判斷題（本題共15分，每小題5分）1、對(duì)給定的集合A={1,2,3,4,5},B={6,7,8,9,10}和f={<1,8>,<3,9>,<4,10>,<2,6>,<5,9>}，判斷是否構(gòu)成能函數(shù)f:A→B,如果能，說(shuō)明是否為滿射、單射、雙射的；如果不能，說(shuō)明理由。解：因?yàn)锳={1,2,3,4,5},B={6,7,8,9,10},f={<1,8>,<3,9>,<4,10>,<2,6>,<5,9>}所以能構(gòu)成函數(shù)f:A→B，既不是單射也不是滿射2、判斷下圖是否為歐拉圖，是否有歐拉通路，為什么？解：不是歐拉圖.因?yàn)橛腥攵群统龆炔煌慕Y(jié)點(diǎn)；有歐拉通路，因?yàn)橛袃蓚€(gè)結(jié)點(diǎn)入度和出度不同，且一個(gè)結(jié)點(diǎn)的入度比出度大1，另一個(gè)結(jié)點(diǎn)的入度比出度小1。3、下圖中的關(guān)系R為A={1，2，3}上的關(guān)系，判斷其是否具有自反、對(duì)稱(chēng)和傳遞性并寫(xiě)出該關(guān)系的集合表示及關(guān)系矩陣。解R={<1,1>,<1,2>,<2,1>,<1,3>,<3,1>},不自反也不反自反；對(duì)稱(chēng),不反對(duì)稱(chēng)；不傳遞.三、（本題共10分，每小題5分）1、設(shè)個(gè)體域D={a,b,c},消去公式"x(F(x)?G(x))中的量詞:解"x(F(x)?G(x))?(F(a)?G(a))ù(F(b)?G(b))ù(F(c)?G(c))2、求B??pù(púqú?r)的主合取范式解因?yàn)?p?(?púqúr)ù(?púqú?r)ù(?pú?qúr)ù(?pú?qú?r)?M4ùM5ùM6ùM7púq得B?M1ùM4ùM5四、（本題共10分）給定有向圖D:如下圖所示：求：(1)圖D的鄰接矩陣；(2)v1到v4,v4到v1長(zhǎng)為3的通路各有多少條；(3)v1到自身長(zhǎng)為1,2,3的回路各有多少條；(4)長(zhǎng)為3的通路共有多少條?其中有多少條回路；(5)長(zhǎng)度小于等于3的回路共有多少條?vv1v2v3v4解（1）（2）v1到v4長(zhǎng)為3的通路有3條,v4到v1長(zhǎng)為3的通路有0條；（3）v1到自身長(zhǎng)為1,2,3的回路各有1條（4）長(zhǎng)3為的通路共有13條，其中有1條回路（5）長(zhǎng)度小于等于3的回路共有5條五、（本題10分）設(shè)<R,＊>是一個(gè)代數(shù)系統(tǒng)，＊是R上的一個(gè)二元運(yùn)算，使得對(duì)于R中的任意元素a、b有a＊b=a+b+a·b（·為普通的乘法運(yùn)算）。證明<R,＊>是獨(dú)異點(diǎn)并求出其幺元。證明（1）"a?R，0＊a=0+a+0·a=a；a＊0=a+0+a·0=a，所以，0是幺元。（2）要證明＊運(yùn)算滿足結(jié)合律，即"a、b、c?R(a＊b)＊c=a＊(b＊c)(a＊b)＊c=（a+b+a·b）＊c=（a+b+a·b）+c+（a+b+a·b）·c=a+b+c+ab+ac+bc+abc同理，a＊(b＊c)=a+b+c+ab+ac+bc+abc所以<R,＊>是獨(dú)異點(diǎn)。六、證明題（本題共30分，每小題10分）1、在自然推理系統(tǒng)中構(gòu)造下面推理的證明。如果王小紅努力學(xué)習(xí)，她一定取得好成績(jī)。若王小紅貪玩或不按時(shí)完成作業(yè)，她就不能取得好成績(jī)。所以，如果王小紅努力學(xué)習(xí)，她就不貪玩并且按時(shí)完成作業(yè)。（其中p：王小紅努力學(xué)習(xí)；q：王小紅取得好成績(jī)；r：王小紅貪玩；s：王小紅按時(shí)完成作業(yè)。）前提：p?q，(r∨?s)??q結(jié)論：p?(?r∧s)證明①p?q前提引入②(r∨?s)??q前提引入③?(r∨?s)∨?q②置換④q??(r∨?s)③置換⑤p??(r∨?s)①④假言三段論⑥p?(?r∧s)⑤置換2、在自然推理系統(tǒng)F中，構(gòu)造下面推理的證明前提："x(F(x)?G(x)∧H(x)),($x)（F(x)∧R（x））結(jié)論：($x)（F(x)∧R（x）∧G(x)）證明：(1)($x)（F(x)∧R（x））P(2)F(c)∧R(c)(1),EI(3)"x(F(x)?G(x)∧H(x))P(4)F(c)?G(c)∧H(c)(3),UI(5)F(c)(2),化簡(jiǎn)(6)G(c)∧H(c)(4),(5),I假言推理(7)R(c)(2),化簡(jiǎn)(8)G(c)(6),化簡(jiǎn)(9)F(c)∧R(c)∧G(c)(5),(7),(8),合取(10)($x)（F(x)∧R（x）∧G(x)）(9)EG3、設(shè)V=<Z,+>，"a?Z，令fa:Z?Z，fa(x)=ax，證明fa是V的自同態(tài)，當(dāng)a為何值時(shí)fa為自同構(gòu)。證明因?yàn)?x,y?Z，有fa(x+y)=a(x+y)=ax