離散數(shù)學a(答案)

1、離散數(shù)學A卷閉卷、70學時、 填空選擇題每空1分，共26分1、 給定命題公式如下：p q r。該公式的成真賦值為 A，成假賦值為B,公式的類型為C。供選擇的答案A:無；全體賦值； 010，100，101，111；010, 100，101，110，111。B:無；全體賦值； 000，001，011 :000，010，110。C:重言式；矛盾式；可滿足式。2、在公式xPyQx,y yRx, y中，x 的轄域是Pz Qx,z_，y的轄域是Rx,z。3、設 Z+=x I x ZA X>0, n 1, n 2, n 3是 Z+的 3 個劃分。n 1=x I x Z+, n 2=S1,S2,S 1

2、為素數(shù)集，S2=Z+-S1. n 3= Z+,13個劃分塊中最多的是A,最少的是B.劃分n 1對應的是Z+上的C, n 2對應的是Z+上的D, n 3對應的是Z+ 上的E.供選擇的答案A:,B: n 1, n 2, n 3.C:,D:,E: 整除關系；全域關系；包含關系；小于等于關系；恒等關系； 含有兩個等價類的等價關系；以上關系都不是。24、設 f : R R, f(x) x x2 x33 g : RR,g(x)=x+2,那么 f ° g(x)為2f(x) (x 2) x 12 x 12_c/ r x2x3f: R Rf(x)為f (x)X,g0x3是 A，f -1 B ,g -1

3、 C.供選擇的答案A :單射不滿射；滿射不單射； 不單射也不滿射：雙射;B :，C :：不是反函數(shù)；是反函數(shù)；任課班級：114051-4、5、設G=0 , 1, 2, 3，假設。為模4乘法，那么<G,。>構成A， 假設為模4加法，那么<G，是B階群，且是C o G中的2階兀是D , 4階元是E o供選擇的答案A ;群；半群，不是群；B :有限：無限。C:Klein四元群；置換群；循環(huán)群;D ，E ：0;1和3;2o6、 設A, V ,人是代數(shù)系統(tǒng)，二元運算V和人對于 A是封閉的。如果對于 A中任意的元素a，b，c滿足交換律、 結合律和_吸收律，那么稱A，V，A 是格。7、6個

4、頂點11條邊的所以可能的非同構的連通的簡單的非平面圖有4_個，其中有2個含子圖K3,3,有_2_個含與K5同胚子圖。二、計算題：每題5分，任選6題，共30分321、計算幕集 PA o Axx R x 2 x x 20答：PA=巾,-1,1,2,-1,1,-1,2,1,2,-1,1,210011000 R000110002、設S= 1，2, 3, 4，R是S上的二元關系，其關系矩陣為 求R的關系表達式。 dom R=?,ra n R=? R° R中有幾個有序對？ R1的關系圖中有幾個環(huán)?答：關系表達示：<1,1>,<1,4>,<2,1>,<4,

5、1>,<3,4> dom R=1,2,3,4,ra n R=1,4 7 13、S= QXQ, Q為有理數(shù)集，*為S上的二元運算，任意<a, b>, <x, y>, S 有<a, b>*<x , y> = <ax, ay+ b> *運算在S上具有哪些主要性質； *運算有無單位元，零元？如果有請指出，并求S中所有可逆元素的逆元。答：*運算不是可交換的；可結合的；在 a=0且b Q或者1, 0時滿 足幕等律。1, 0為*運算的單位元。對任意a,b Q x Q，只要 a<>0都存在逆元<1/a,-b/a&g

6、t; ;不存在零元。任課班級：114051-4、4、有向圖D如圖1-1所示,求D中長度為4的通路總數(shù)是多少?并指出其中有多少條是回路?圖1-102100010A00010011答：a2=0021000100110012a3=001300110012002300340012002300355、當n和m從A4可看出,A4=中長度為4的通路有23條，其中7條為回路。為何值時，完全二部圖Kn,m是歐拉圖；哈密頓圖；平面圖；非平面圖。答：n和m都是正偶數(shù)；n=m且n>=2；*=2；n>=3, m>=3&設無向樹T由7片樹葉，其余頂點的度數(shù)均為 3，求T中3度頂點數(shù)， 能畫出幾棵

7、具有此種度數(shù)的非同構的無向樹？答: T中有5個3度頂點。設T中有x個3度頂點，那么T中的頂點數(shù)n=7+x, 邊數(shù)m=n-1=6+x，由握手定理的方程2m=12+2x=3x+7解出x=5,T的度數(shù)列為1,1, 1，1，1，1，1, 3, 3, 3，3, 3。有兩棵非同構的樹。7、在圖1-2所示的無向圖G中，黑線邊所示的子圖為 G的一棵生成樹T,求 G的對應于T的根本回路系統(tǒng)。對應生成樹的弦分別為 e6,e7,e8,e10,e11。設它們對應的根本回路分別為C1,C2, C3, C4.C5，從對應的弦開始，按逆時針也可都按順時針的順序寫出它們，分別為C1 = e6e4e5 C2 = e7e2e1

8、C3 = e8e9e2e1 C4 = e10e3e5e2 C5 = e11e3e5e2e9此圖的圈秩為5,根本回路系統(tǒng)為C1,C2,C3,C4,C5任課班級：114051-4、111051-2任課教師：孫明三、證明題(每題6分，任選4題，共24分)1、 設Hi和H2是群G, *的兩個互不包含的子群，證明G中存在一個元素， 它既不屬于Hi,也不屬于H2。證明：因為Hi H2,所以存在a Hi且a H2,又因為H2 Hi,所以存在 b H2,且 b Hi,顯然 a*b G，因為 a Hi,Hi,*是G,* 的子 群，可推出b Hi,這與b Hi矛盾。同理可證，a*b H22、證明歐拉圖中必沒有割邊

9、。證明：主要利用“無向圖中，奇度頂點的個數(shù)為偶數(shù)這一結論用反證法， 設歐拉圖中含有割邊。由于歐拉圖中每一個頂點的度數(shù)為偶數(shù)，所以割邊的兩 個端點也是偶數(shù)度頂點。刪去割邊后，構成兩個連通分支，每個連通分支都含 有割邊的一個端點；此時每一個連通分支中僅有一個奇數(shù)度頂點，這與矛 盾。所以，歐拉圖中沒有割邊。3、設L , 是格，任取 a L,令 S= x I x L Axa證明S, 是L的子格。證明：對于任意的x,y S,必有x a和y a,所以x V y a,x A y a,故x Vy S, x A y S,因此S, 是L, 的子格。4、設G是6階無向簡單圖，證明G或它的補圖中存在3個頂點彼此相鄰。

10、證明：設6個頂點的簡單圖為G,考察G中的任意一個頂點a,那么，另 外5個頂點中的任何一個頂點，要么在圖G中與a鄰接，要么在圖G '中與a鄰接。這樣，就把5個結點分成兩類，將會必有一類至少含有三個頂點。不妨假 設其中的3個頂點為b, c, d。該圖必是圖G*的子圖(這里圖G*可能是G或者 是G')。如果邊(b,c),(c,d),(b,d)中有一條邊在 G*擇優(yōu)3個頂點鄰接。如果邊 (b,c),(c,d),(b,d)都不在G*中，那么必在G*的補圖(或是圖G '或者是G)中，因 此，必有3個頂點鄰接。5、設n階m條邊的平面圖是自對偶圖，證明 m=2n-2.證明；設G*圖是G

11、的對偶圖，所以G必為連通的平面圖，且n*=r,m*=m,r*=n 于是n=n*=r，由歐拉公式可知，n-m+r=2=n-m+n 得m=2n-2&驗證K5和K3,3都是極小非平面圖。答：畫圖舉例。四、應用題(每題10分，共20分)1、在自然推理系統(tǒng)F中，證明下面推理：每個喜歡步行的人都不喜歡騎自行車。每個人或者喜歡騎自行車或者喜 歡乘汽車。有的人不喜歡乘汽車。所以有的人不喜歡步行。(個體域為人類集合)。解：設P(x): x喜歡步行； Q(x) : x喜歡乘汽車； R(x): x喜歡騎自行 車；此題符號化為 前題：x(P(x) - n R(x), x(R(x) V Q(x) , x 門 Q

12、(x) 結論： x q P(x) x q Q(x)前提引入 x(R(x) V Q(x)前提引入任課班級：114051-4、111051-2任課教師：孫明4 門Q(c) R(c) V Q(c) x(P(x) - n R(x) P(c)- n R(c) R(c) 門P(c) x n P(x)El規(guī)那么Ul規(guī)那么 前提引入 UI規(guī)那么析取三段論拒取式EG規(guī)那么2、今有n個人，他們中的任何二人和起來認識其余的n-2個人。證明：當n?3時，這n個人能排成一列，使得中間的任何人都認識兩旁的人，而兩旁 的人認識左邊(或右邊)的人。而當 n?4時，這n個人能排成一個圓圈，使得 每個人都認識兩旁的人。解：設n個人分別為Vi,V2,Va,Vn,V=,V2,Va,Vn為頂點集。假設V 與V認識，就在代表它們的頂點間連一條無向邊，得邊集E，于是的無向簡單圖G=<V,E>對于任意V,Vj V,假設V與V不相鄰，那么對任意Vk V, (k<>i,k<>j ) 必與V或V相鄰。否那么與條件矛盾。不妨假設，與V相鄰，與V不相鄰。那么Vk與V所代表的