2016離散數(shù)學(xué)練習(xí)題-(答案修改)

#/9由關(guān)系圖可以看出R是等價(jià)關(guān)系.等價(jià)類為：或?qū)憺椋篈/R={{1,3,6},{2,5},{4}}3．判斷下圖是否為二部圖？若是,找出它的互補(bǔ)結(jié)點(diǎn)子集.它是否為哈密頓圖？f若是,找出一條哈密頓回路.f四、證明題.設(shè)A={<x,y>1x,y為正整數(shù)}，在A上定義二元關(guān)系當(dāng)且僅當(dāng)x—y=u—v.證明：R是一個(gè)等價(jià)關(guān)系.證明：所以R自反的.任取<x,y>,<u,v>所以R是對(duì)稱的.任取<x,y>,<u,v>,<s,t>所以R是傳遞的.因此,R是等價(jià)關(guān)系..設(shè)A={<a,b>1a,b為正整數(shù)}，在A上定義二元關(guān)系R如下：<a,b>R<c,d>當(dāng)且僅當(dāng)a+b=c+d.證明：R是一個(gè)等價(jià)關(guān)系.證明：任取<a,b>所以R自反的.任取<a,b>,<c,d>所以R是對(duì)稱的.任取<a,b>,<c,d>,<e,f>所以R是傳遞的.因此,R是等價(jià)關(guān)系..用一階邏輯的推理理論證明：.設(shè)代數(shù)系統(tǒng)V=<Z,十>,Z={0,1,2,3,4,5},十為模6加法.證明：Z關(guān)于十運(yùn)算66 6構(gòu)成群.證明：集合Z顯然非空.6<1>Va,beZ，a十beZ從而集合Z十關(guān)于運(yùn)算是封閉的.6 6, 6<2>Va,b,ceZ，有(a十b)十c=a十(b十c>故運(yùn)算十是可結(jié)合的.6<3>VaeZ,a十0=a，故。是<Z,十〉中的幺元.66<4>VacZ，因?yàn)閍十(6-a)=0,因此6.a是a的逆元6由此上知<Z,十〉是群65.設(shè)A是集合,P<A>是A的冪集合,十是對(duì)稱差運(yùn)算，證明<P<A>,十>構(gòu)成群.五、應(yīng)用題〔未給出參考答案的自己完成〕.構(gòu)造下列推理的證明.如果今天是星期一,則要進(jìn)行英語(yǔ)或離散數(shù)學(xué)考試.如果英語(yǔ)老師有會(huì),則不考英語(yǔ).今天是星期一,英語(yǔ)老師有會(huì),所以進(jìn)行離散數(shù)學(xué)考試.〔給答案〕.構(gòu)造下列推理的證明.小王是理科學(xué)生,則他的數(shù)學(xué)成績(jī)很好.如果小王不是文科學(xué)生,則他一定是理科學(xué)生.小王的數(shù)學(xué)成績(jī)不好,所以小王是文科學(xué)生..用一階邏輯推理證明前提：Vx(F(x)f「G(x)),Vx(F(x)vH(x)),3x「H(x)結(jié)論：3x「G(x)證明：〔1〕Vx(F(x)vH(x))前提引入〔2〕F(x)vH(x)〔1〕V-〔3〕3x—iH(x)前提引入〔4〕—H(x)〔3〕3-〔5〕F(x)〔2〕〔4〕析取三段論〔6〕Vx(F(x)——G(x))前提引入〔7〕F(x)——G(x)〔6〕V-〔8〕—G(x)〔5〕〔7〕假言推理〔9〕3—G(x)〔8〕3+.今有于a,b,c,d,e,f7個(gè)人，已知下列事實(shí)：a會(huì)講英語(yǔ)；b會(huì)講英語(yǔ)和漢語(yǔ)；c會(huì)講英語(yǔ)、意大利語(yǔ)和俄語(yǔ)；d會(huì)講日語(yǔ)和漢語(yǔ)；e會(huì)講德國(guó)和意大利語(yǔ)；f會(huì)講法語(yǔ)、日語(yǔ)和俄語(yǔ)；g會(huì)講法語(yǔ)和德語(yǔ).試問(wèn)這七個(gè)人應(yīng)如何排座位,才能使每個(gè)人都能和他身邊的人交談？解：用結(jié)點(diǎn)表示人，用邊表示連接的兩個(gè)人能講同一種語(yǔ)言構(gòu)造出圖G如下：在G中存在著一條哈密頓回路如下,根據(jù)這條回路安排座位，就能夠使每個(gè)人都能和他身邊的人交談.．一次學(xué)術(shù)會(huì)議的理事會(huì)共有20個(gè)人參加,他們之間有的互相認(rèn)識(shí)但有的