離散數(shù)學自學考試真題附答案打印版

1、精選文檔全國2002年4月離散數(shù)學試題課程代碼：02324一、單項選擇題(本大題共15小題，每小題1分，共15分)在每小題列出的四個選項中只有一個選項是符合題目要求的，請將正確選項前的字母填在題后的括號內(nèi)。1.一個連通的無向圖G，假如它的全部結(jié)點的度數(shù)都是偶數(shù)，那么它具有一條( )A.漢密爾頓回路 B.歐拉回路C.漢密爾頓通路 D.初級回路2.設G是連通簡潔平面圖，G中有11個頂點5個面，則G中的邊是( )A.10 B.12 C.16 D.143.在布爾代數(shù)L中，表達式(ab)(abc)(bc)的等價式是( )A.b(ac)B.(ab)(ab)C.(ab)(abc)(bc)D.(bc)(ac)

2、4.設i是虛數(shù)，·是復數(shù)乘法運算，則G=<1,-1,i,-i,·>是群，下列是G的子群是( )A.<1,·> B.-1,· C.i,· D.-i,·5.設Z為整數(shù)集，A為集合，A的冪集為P(A),+、-、/為數(shù)的加、減、除運算，為集合的交運算，下列系統(tǒng)中是代數(shù)系統(tǒng)的有( )A.Z，+，/ B.Z，/C.Z，-，/ D.P(A)，6.下列各代數(shù)系統(tǒng)中不含有零元素的是( )A.Q，*Q是全體有理數(shù)集，*是數(shù)的乘法運算B.Mn(R),*,Mn(R)是全體n階實矩陣集合，*是矩陣乘法運算C.Z，Z是整數(shù)集，定義為xxy

3、=xy,x,yZD.Z，+，Z是整數(shù)集，+是數(shù)的加法運算7.設A=1,2,3，A上二元關(guān)系R的關(guān)系圖如下：R具有的性質(zhì)是A.自反性B.對稱性C.傳遞性D.反自反性8.設A=a,b,c，A上二元關(guān)系R=a,a，b,b,a,c，則關(guān)系R的對稱閉包S(R)是( )A.RIA B.R C.Rc,a D.RIA9.設X=a,b,c,Ix是X上恒等關(guān)系，要使Ixa,b，b,c，c,a，b,aR為X上的等價關(guān)系，R應取( )A.c,a，a,c B.c,b，b,aC.c,a，b,a D.a,c，c,b10.下列式子正確的是( )A. B. C. D.11.設解釋R如下：論域D為實數(shù)集，a=0,f(x,y)=x

4、-y,A(x,y):x<y.下列公式在R下為真的是( )A.( x)( y)( z)(A(x,y)A(f(x,z),f(y,z)B.( x)A(f(a,x),a)C.(x)(y)（A(f(x,y),x)D.(x)(y)(A(x,y)A(f(x,a),a)12.設B是不含變元x的公式，謂詞公式(x)(A(x)B)等價于( )A.(x)A(x)B B.(x)A(x)BC.A(x)B D.(x)A(x)(x)B13.謂詞公式(x)(P(x,y)(z)Q(x,z)(y)R(x,y)中變元x( )A.是自由變元但不是約束變元B.既不是自由變元又不是約束變元C.既是自由變元又是約束變元D.是約束變元

5、但不是自由變元14.若P：他聰慧；Q：他用功；則“他雖聰慧，但不用功”，可符號化為( )A.PQ B.PQ C.PQ D.PQ15.以下命題公式中，為永假式的是( )A.p(pqr) B.(pp)pC.(qq)p D.(qp)(pp)二、填空題(每空1分，共20分)16.在一棵根樹中，僅有一個結(jié)點的入度為_，稱為樹根，其余結(jié)點的入度均為_。17.A=1,2,3,4上二元關(guān)系R=2，4，3，3，4，2，R的關(guān)系矩陣MR中m24=_,m34=_。18.設s,*是群，則那么s中除_外，不行能有別的冪等元；若s,*有零元，則|s|=_。19.設A為集合，P(A)為A的冪集，則P(A)，是格，若x,yP

6、(A),則x,y最大下界是_，最小上界是_。20.設函數(shù)f:XY,假如對X中的任意兩個不同的x1和x2，它們的象y1和y2也不同，我們說f是_函數(shù)，假如ranf=Y，則稱f是_函數(shù)。21.設R為非空集合A上的等價關(guān)系，其等價類記為xR。x,yA，若x,yR，則xR與yR的關(guān)系是_，而若x,yR，則xRyR=_。22.使公式(x)( y)(A(x)B(y)(x)A(x)(y)B(y)成立的條件是_不含有y，_不含有x。23.設M(x):x是人，D(s):x是要死的，則命題“全部的人都是要死的”可符號化為(x)_,其中量詞(x)的轄域是_。24.若H1H2Hn是_，則稱H1,H2,Hn是相容的，若

7、H1H2Hn是_，則稱H1,H2,Hn是不相容的。25.推斷一個語句是否為命題，首先要看它是否為 ，然后再看它是否具有唯一的 。三、計算題 (共30分)26.(4分)設有向圖G=(V,E)如下圖所示，試用鄰接矩陣方法求長度為2的路的總數(shù)和回路總數(shù)。27.(5)設A=a,b,P(A)是A的冪集，是對稱差運算，可以驗證<P(A)，>是群。設n是正整數(shù)，求(a-1ba)na-nbnan28.(6分)設A=1,2,3,4,5,A上偏序關(guān)系 R=1，2，3，2，4，1，4，2，4，3，3，5，4，5IA;(1)作出偏序關(guān)系R的哈斯圖(2)令B=1,2,3,5，求B的最大，最小元，極大、微小元

8、，上界，下確界，下界，下確界。29.(6分)求(PQ)(PQ)的主合取范式并給出全部使命題為真的賦值。30.(5分)設帶權(quán)無向圖G如下，求G的最小生成樹T及T的權(quán)總和，要求寫出解的過程。31.(4分)求公式(x)F(x,y)(y)G(x,y)(x)H(x)的前束范式。四、證明題 (共20分)32.(6分)設T是非平凡的無向樹，T中度數(shù)最大的頂點有2個，它們的度數(shù)為k(k2),證明T中至少有2k-2片樹葉。33.(8分)設A是非空集合，F(xiàn)是全部從A到A的雙射函數(shù)的集合，是函數(shù)復合運算。 證明：F, 是群。34.(6分)在個體域D=a1,a2,，an中證明等價式： (x)(A(x)B(x)(x)A

9、(x)(x)B(x)五、應用題(共15分)35.(9分)假如他是計算機系本科生或者是計算機系爭辯生，那么他肯定學過DELPHI語言而且學過C+語言。只要他學過DELPHI語言或者C+語言，那么他就會編程序。因此假如他是計算機系本科生，那么他就會編程序。請用命題規(guī)律推理方法，證明該推理的有效結(jié)論。36.(6分)一次學術(shù)會議的理事會共有20個人參與，他們之間有的相互生疏但有的相互不生疏。但對任意兩個人，他們各自生疏的人的數(shù)目之和不小于20。問能否把這20個人排在圓桌旁，使得任意一個人生疏其旁邊的兩個人?依據(jù)是什么?答案：一、單項選擇題(本大題共15小題，每小題1分，共15分) 1.B 2.D 3.

10、A 4.A 5.D 6.D 7.D 8.C 9.D 10.B 11.A 12.A 13.C 14.B 15.C二、填空題16.0 117.1 018.單位元 119.xy xy20.入射 滿射21.xR=yR 22.A(x) B(y)23.(M(x)D(x) M(x)D(x)24.可滿足式 永假式(或沖突式)25.陳述句 真值三、計算題26. M= M2= G中長度為2的路總數(shù)為18，長度為2的回路總數(shù)為6。27.當n是偶數(shù)時，xP(A),xn= 當n是奇數(shù)時，xP(A),xn=x 于是：當n是偶數(shù)，(a-1ba)na-nbnan =(a-1)nbnan= 當n是奇數(shù)時， (a-1ba)na-

11、nbnan =a-1ba(a-1)nbnan =a-1baa-1ba=28.(1)偏序關(guān)系R的哈斯圖為 (2)B的最大元：無，最小元：無； 極大元：2，5，微小元：1，3 下界：4， 下確界4； 上界：無，上確界：無29.原式(PQ)(PQ)(PQ)(PQ) (PQ)(PQ)(PQ)(PQ) (PQPQ)(PQ)(PQ) (PQ)(PQ) (PQ)(PQ) P(QQ) P(QQ) (PQ)(PQ) 命題為真的賦值是P=1,Q=0和P=1,Q=130.令e1=(v1,v3), e2=(v4,v6) e3=(v2,v5), e4=(v3,v6) e5=(v2,v3), e6=(v1,v2) e7=

12、(v1,v4), e8=(v4,v3) e9=(v3,v5), e10=(v5,v6) 令ai為ei上的權(quán)，則 a1<a2<a3<a4<a5=a6=a7=a8<a9=a10 取a1的e1T,a2的e2T,a3的e3T,a4的e4T,a5的e5T,即， T的總權(quán)和=1+2+3+4+5=1531.原式(x1F(x1,y)y1G(x,y1)x2H(x2) (換名) x1y1(F(x1,y)G(x,y1)x2H(x2) x1y1(F(x1,y1)G(x,y1)x2H(x2) x1y1x2(F(x1,y1)G(x,y1)H(x2) 四、證明題32.設T中有x片樹葉，y個分支

13、點。于是T中有x+y個頂點，有x+y-1 條邊，由握手定理知T中全部頂點的度數(shù)之的 =2(x+y-1)。 又樹葉的度為1，任一分支點的度大于等于2 且度最大的頂點必是分支點，于是 x·1+2(y-2)+k+k=x+2y+2K-4 從而2(x+y-1)x+2y+2k-4 x2k-233.從定義動身證明：由于集合A是非空的，故明顯從A到A的雙射函數(shù)總是存在的，如A上恒等函數(shù)，因此F非空 (1)f,gF,由于f和g都是A到A的雙射函數(shù)，故fg也是A到A的雙射函數(shù)，從而集合F關(guān)于運算是封閉的。 (2)f,g,hF,由函數(shù)復合運算的結(jié)合律有f(gh)=(fg)h故運算是可結(jié)合的。 (3)A上的

14、恒等函數(shù)IA也是A到A的雙射函數(shù)即IAF,且fF有IAf=fIA=f,故IA是F，中的幺元 (4)fF,由于f是雙射函數(shù)，故其逆函數(shù)是存在的，也是A到A的雙射函數(shù)，且有ff-1=f-1f=IA,因此f-1是f的逆元 由此上知F，是群34.證明(x)(A(x)B(x) x(A(x)B(x) (A(a1)B(a1)(A(a2)B(a2)(A(an)B(an) (A(a1)A(a2)A(an)(B(a1)B(a2)(B(an) (A(a1)A(a2)A(an)(B(a1)B(a2)(B(an) (x)A(x)(x)B(x) (x)A(x)(x)B(x)五、應用題35.令p：他是計算機系本科生 q：他

15、是計算機系爭辯生 r：他學過DELPHI語言 s:他學過C+語言 t:他會編程序 前提：(pq)(rs),(rs)t 結(jié)論：pt 證 p P(附加前提) pq TI (pq)(rs) P(前提引入) rs TI r TI rs TI (rs)t P(前提引入) t TI36.可以把這20個人排在圓桌旁，使得任一人生疏其旁邊的兩個人。 依據(jù)：構(gòu)造無向簡潔圖G=<V,E>,其中V=v1,v2,，V20是以20個人為頂點的集合，E中的邊是若任兩個人vi和vj相互生疏則在vi與vj之間連一條邊。 ViV,d(vi)是與vi相互生疏的人的數(shù)目，由題意知vi,vjV有d(vi)+d(vj)20

16、,于是G中存在漢密爾頓回路。 設C=Vi1Vi2Vi20Vi1是G中一條漢密爾頓回路，按這條回路的挨次按其排座位即符合要求。全國2004年4月高等教育自學考試離散數(shù)學試題課程代碼：02324第一部分 選擇題 （共15分）一、單項選擇題（本大題共15小題，每小題1分，共15分）1下列是兩個命題變元p，q的小項是（ ）AppqBpqCpqDppq2令p：今日下雪了，q：路滑，則命題“雖然今日下雪了，但是路不滑”可符號化為（ ）ApqBpqCpqDpq3下列語句中是命題的只有（ ）A1+1=10Bx+y=10Csinx+siny<0Dx mod 3=24下列等值式不正確的是（ ）A(x)A(x

17、)AB(x)(BA(x)B(x)A(x)C(x)(A(x)B(x)(x)A(x)(x)B(x)D(x)(y)(A(x)B(y)(x)A(x)(y)B(y)5謂詞公式(x)P(x,y)(x)(Q(x,z)(x)(y)R(x,y,z)中量詞x的轄域是（ ）A(x)Q(x,z)(x)(y)R(x,y,z)BQ(x,z)(y)R(x,y,z)CQ(x,z)(x)(y)R(x,y,z)DQ(x,z)6設R為實數(shù)集，函數(shù)f：RR，f(x)=2x，則f是（ ）A滿射函數(shù)B入射函數(shù)C雙射函數(shù)D非入射非滿射7設A=a,b,c,d，A上的等價關(guān)系R=<a,b>,<b,a>,<c,d&

18、gt;,<d,c>IA，則對應于R的A的劃分是（ ）Aa,b,c,dBa,b,c,dCa,b,c,dDa,b,c,d8設A=Ø，B=P(P(A)，以下正確的式子是（ ）AØ,ØBBØ,ØBCØ,ØBDØ,ØB9設X，Y，Z是集合，一是集合相對補運算，下列等式不正確的是（ ）A(X-Y)-Z=X-(YZ)B(X-Y)-Z=(X-Z)-YC(X-Y)-Z=(X-Z)-(Y-Z)D(X-Y)-Z=X-(YZ)10設*是集合A上的二元運算，稱Z是A上關(guān)于運算*的零元，若（ ）A有x*Z=Z*x=ZBZ

19、A，且有x*Z=Z*x=ZCZA，且有x*Z=Z*x=xDZA，且有x*Z=Z*x=Z11在自然數(shù)集N上，下列定義的運算中不行結(jié)合的只有（ ）Aa*b=min(a,b)Ba*b=a+bCa*b=GCD(a,b)(a,b的最大公約數(shù))Da*b=a(mod b)12設R為實數(shù)集，R+=x|xRx>0，*是數(shù)的乘法運算，<R+，*>是一個群，則下列集合關(guān)于數(shù)的乘法運算構(gòu)成該群的子群的是（ ）AR+中的有理數(shù)BR+中的無理數(shù)CR+中的自然數(shù)D1，2，313設<A,*,>是環(huán)，則下列正確的是（ ）A<A,>是交換群B<A,*>是加法群C對*是可安排的

20、D*對是可安排的14下列各圖不是歐拉圖的是（ ）15設G是連通平面圖，G中有6個頂點8條邊，則G的面的數(shù)目是（ ）A2個面B3個面C4個面D5個面其次部分 非選擇題（共85分）二、填空題（本大題共10小題，每空1分，共20分）16一公式為 之充分必要條件是其析取范式之每一析取項中均必同時包含一命題變元及其否定；一公式為 之充分必要條件是其合取范式之每一合取項中均必同時包含一命題變元及其否定。17前束范式具有形式(Q1V1)(Q2V2)(QnVn)A，其中Qi(1in)為 ，A為 的謂詞公式。18設論域是a,b,c，則(x)S(x)等價于命題公式 ；()S(x)等價于命題公式 。19設R為A上的

21、關(guān)系，則R的自反閉包r(R)= ，對稱閉包s(R)= 。20某集合A上的二元關(guān)系R具有對稱性，反對稱性，自反性和傳遞性，此關(guān)系R是 ，其關(guān)系矩陣是 。21設<S,>是一個偏序集，假如S中的任意兩個元素都有 和 ，則稱S關(guān)于構(gòu)成一個格。22設Z是整數(shù)集，在Z上定義二元運算*為a*b=a+b+a·b，其中+和·是數(shù)的加法和乘法，則代數(shù)系統(tǒng)<Z,*>的幺元是 ，零元是 。23如下平面圖有2個面R1和R2，其中deg(R1)= ，deg(R2)= 。24無向圖G具有一條歐拉回路，當且僅當G是 ，并且全部結(jié)點的度數(shù)都是 。25在下圖中，結(jié)點v2的度數(shù)是 ，結(jié)點

22、v5的度數(shù)是 。三、計算題（本大題共6小題，第2627小題每小題4分，第28、30小題每小題5分，第29、31小題每小題6分，共30分）26（4分）求出從A=1,2到B=x,y的全部函數(shù)，并指出哪些是雙射函數(shù)，哪些是滿射函數(shù)。27（4分）假如論域是集合a,b,c，試消去給定公式中的量詞：。28（5分）設A=a,b,c ，P（A）是A的冪集，是集合對稱差運算。已知<P(A),>是群。在群<P(A),>中，找出其幺元。找出任一元素的逆元。求元素x使?jié)M足ax=b。29（6分）用等值演算法求公式(pq)(pq)的主合取范式30（5分）畫出5個具有5個結(jié)點5條邊的非同構(gòu)的無向連通

23、簡潔圖。31（6分）在偏序集<Z,>中，其中Z=1,2,3,4,6,8,12,14，是Z中的整除關(guān)系，求集合D=2,3,4,6的極大元，微小元，最大元，最小元，最小上界和最大下界。四、證明題（本大題共3小題，第3233小題每小題6分，第34小題8分，共20分）32（6分）用等值演算法證明(qs)r)(s(pr)(s(pq)r33（6分）設n階無向樹G=<V，E>中有m條邊，證明m=n-1。34（8分）設P=Ø,1,1,2,1,2,3，是集合P上的包含關(guān)系。（1）證明：<P，>是偏序集。（2）在（1）的基礎上證明<P，>是全序集五、應用題

24、（本大題共2小題，第35小題9分，第36小題6分，共15分）35（9分）在謂詞規(guī)律中構(gòu)造下面推理的證明：每個在學校讀書的人都獲得學問。所以假如沒有人獲得學問就沒有人在學校讀書。（個體域：全部人的集合）36（6分）設有a,b,c,d,e,f,g等七個人，已知a會講英語；b會講英語、漢語；c會講英、俄語；d會講日、漢語；e會講德語、俄語；f會講法語、日語；g會講法語、德語。試用圖論方法支配園桌座位，使每人都能與其身邊的人交談。全國2005年4月高等教育自學考試離散數(shù)學試題課程代碼：02324一、單項選擇題(本大題共15小題，每小題1分，共15分)在每小題列出的四個備選項中只有一個是符合題目要求的，

25、請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1.下列各圖是平面圖的是( ) 2.設G是n個頂點的無向簡潔圖，則下列說法不正確的是 )A.若G是樹，則其邊數(shù)等于n-1B.若G是歐拉圖，則G中必有割邊C.若G中有歐拉路，則G是連通圖，且有零個或兩個奇度數(shù)頂點D.若G中任意一對頂點的度數(shù)之和大于等于n-1，則G中有漢密爾頓路3.格L是安排格的充要條件是L不含與下面哪一個選項同構(gòu)的子格( )A.鏈B.鉆石格C.五角格D.五角格與鉆石格4.設<G,*>是有限循環(huán)群，則下列說法不正確的是( )A.<G,*>的生成元是唯一的B.有限循環(huán)群中的運算*適合交換律C.G中存在一元

26、素a，使G中任一元素都由a的冪組成D.設a是<G,*>的生成元，則對任一正整數(shù)i，存在正整數(shù)j使a-i=aj5.在實數(shù)集合R上，下列定義的運算中是可結(jié)合的只有( )A.a*b=a+2bB.a*b=a+b-2abC.a*b=a-b+2abD.a*b=a-b-2ab6.設群G=<A,*>中,A的元素個數(shù)大于1，若元素aA的逆元素為bA，則a*b的運算結(jié)果是( )A.aB.bC.G中零元素D.G中幺元7.非空集合A上的二元關(guān)系R若是自反和對稱的，則R是( )A.偏序關(guān)系B.等價關(guān)系C.相容關(guān)系D.擬序關(guān)系8.下面的圖是A=1,2,3上關(guān)系R的關(guān)系圖G(R),從G(R)可推斷R

27、所具有的性質(zhì)是( )1。2。 3。A.自反，對稱，傳遞B.反自反，非對稱C.反自反，對稱，非傳遞D.反自反，對稱，反對稱，傳遞9.設A=1，2，3，B=a,b，下列二元關(guān)系R為A到B的函數(shù)的是( )A.R=<1,a>,<2,a>,<3,a>B.R=<1,a>,<2,b>C.R=<1,a>,<1,b>,<2,a>,<3,a>D.R=<1,b>,<2,a>,<3,b>,<1,a>10.設為空集，P(x)是集合x的冪集，下列論斷不正確的是( )A

28、. P(), P()B.P（），P（）C. P（P（），P（P（）D.P（P（）,P（P（）11.利用謂詞的約束變元改名規(guī)章和自由變元代入規(guī)章，可將如下公式：改寫成( )A. B. C. D. 12.設論域為整數(shù)集，下列謂詞公式中真值為假的是( )A.B. C. D. 13.在命題演算中，語句為真為假的一種性質(zhì)稱為( )A.真值B.陳述句C.命題D.謂詞14.設P：明每天晴；q：我去爬山；那么“除非明每天晴，否則我不去爬山?！笨煞柣癁? )A.B. C. D. 15.下列命題公式是永真式的是( )A. qB.C. D.二、填空題(本大題共10小題，每空1分，共20分)請在每小題的空格中填上正

29、確答案。錯填、不填均無分。16.一棵有6個葉結(jié)點的完全二叉樹，有_個內(nèi)點；而若一棵樹有2個結(jié)點度數(shù)為2，一個結(jié)點度數(shù)為3，3個結(jié)點度數(shù)為4，其余是葉結(jié)點，則該樹有_個葉結(jié)點。17.在一棵根樹中，有且只有一個結(jié)點的入度為_，其余全部結(jié)點的入度均為_。18.設<S,>是格，其中一個命題P是a(ab) (ac),則P的對偶命題是a_(ab)_(ac)。19.設Z是整數(shù)集，+是整數(shù)加法運算，則<Z,+>是群，其幺元是_，對任一整數(shù)i,其逆元是_。20.當f:XY是_函數(shù)時，f有逆函數(shù)，且f -1。f=_。21.設E=1,2,3,4,5,6,A=1,4,B=1,2,3,C=2,4

30、,則(AB)C=_,冪集P(AB)C)=_。22.設論域D=a,b,則(x)P(x)_,(x)(y)Q(x,y)_。23.使公式(x)(y)(A(x)B(y)(x)A(x)(y)B(y)成立的條件是_不含有y，_不含有x。24.由命題變元及其否定所組成的有限個析取式的合取式稱為_，由命題變元及其否定所組成的有限個合取式的析取式稱為_。25.不包含_的命題叫做原子命題，包含_的命題稱為復合命題。三、計算題(本大題共7小題，第26、28小題每小題5分，第27、31小題每小題7分，第29、30小題每小題8分，第32小題9分，共49分)26.用等值演算法，求P(QR)的主析取范式，并按P，Q，R挨次，

31、寫成編碼形式。27.設A=1,2,3，給定A上二元關(guān)系R=<1,1>,<1,2>,<2,3>，求r(R),s(R)和t(R)。28.求公式的前束范式。29.對如下有向圖D，求D中長度為4的路有多少條?其中回路有多少條?30.設A=a,abc,bc,bcd,bd，定義A上二元關(guān)系R=<x,y>|x,yA且字符串x包含于字符串y中，即R=IA<a,abc>,<bc,abc>,<bc,bcd>，可以驗證R是A上偏序關(guān)系。作出R的哈斯圖向R中最少添加幾個序偶可使之成為等價關(guān)系?求出該等價關(guān)系所確定的集合A的劃分。31.

32、某科研所要從3個項目A、B、C中選擇12個項目上馬，由于某種緣由，立項時要滿足以下條件：(1)若A上，則C也要上；(2)若B上，則C不能上；(3)若C不上，則A或B可以上。請找出全部的立項方案32.設有6個城市V1，V2，V6，它們之間有輸油管連通，其布置如下圖(a),Si(數(shù)字)中Si為邊的編號，括號內(nèi)數(shù)字為邊的權(quán)，它是兩城市間的矩離，為了保衛(wèi)油管不受破壞，在每段油管間派一連士兵看管，為保證每個城市石油的正常供應最少需多少連士兵看管?輸油管道總長度越短，士兵越好防守。求他們看管管道的最短的總長度。(要求寫出求解過程)四、證明題(本大題共2小題，每小題8分，共16分)33.證明(x) (P(x

33、) Q(x)(x)P(x)(x)Q(x)34.證明當每個結(jié)點的度數(shù)大于等于3時，不存在有7條邊的連通簡潔平面圖。全國2006年4月高等教育自學考試離散數(shù)學試題課程代碼：02324一、單項選擇題（本大題共15小題，每小題1分，共15分）在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1下列命題公式為重言式的是（ ）Ap (pq)B(pp)qCqqDpq2下列語句中不是命題的只有（ ）A這個語句是假的。B1+1=1.0C飛碟來自地球外的星球。D凡石頭都可練成金。3設p：我很累，q：我去學習，命題：“除非我很累，否則我就去學習”的符號化正確的

34、是（ ）ApqBpqCpqDpq4下列等價式正確的是（ ）AABCAD5在公式中變元y是（ ）A自由變元B約束變元C既是自由變元，又是約束變元D既不是自由變元，又不是約束變元6設A=1，2，3，A上二元關(guān)系S=<1，1>，<1，2>，<3，2>，<3，3>，則S是（ ）A自反關(guān)系B反自反關(guān)系C對稱關(guān)系D傳遞關(guān)系7設集合X為人的全體，在X上定義關(guān)系R、S為R=<a，b|a，bXa是b的父親，S=<a，b>|a，bXa是b的母親，那么關(guān)系<a，b>|a，bx a是b的祖母的表達式為（ ）ARSBR-1SCSRDRS-18

35、設A是正整數(shù)集，R=(x，y)|x，yAx+3y=12，則R (2，3，4，6×2，3，4，6)=（ ）A O/B<3，3>C<3，3>，<6，2>D<3，3>，<6，2>，<9，1>9下列式子不正確的是（ ）A(A-B)-C=(A-C)-BB(A-B)-C=A-(BC)C(A-B)-C=(A-C)-(B-C)DA-(BC)=(A-B) C10下列命題正確的是（ ）Al，21，2，l，2，3，1B1，21，l，2，l，2，3，2C1，21，2，1，2D1，21，2，2，l，2，311在下列代數(shù)系統(tǒng)中，不是環(huán)的只有

36、（ ）A<Z，+，*)，其中Z為整數(shù)集，+，*分別為整數(shù)加法和乘法。B(Q，+，*)，其中Q為有理數(shù)集，+，*分別為有理數(shù)加法和乘法。C<R，+，*>，其中R為實數(shù)集，+為實數(shù)加法，a*b=a+2b。D<Mn (R)，+，*>，其中Mn(R)為實數(shù)集n×n階矩陣結(jié)合，+，*是矩陣加法和乘法。12下列整數(shù)集對于整除關(guān)系都構(gòu)成偏序集，而能構(gòu)成格的是（ ）Al，2，3，4，5B1，2，3，6，12C2，3，7Dl，2，3，713結(jié)點數(shù)為奇數(shù)且全部結(jié)點的度數(shù)也為奇數(shù)的連通圖必定是（ ）A歐拉圖B漢密爾頓圖C非平面圖D不存在的14無向圖G是歐拉圖當且僅當G是連通的

37、且（ ）AG中各頂點的度數(shù)均相等BG中各頂點的度數(shù)之和為偶數(shù)CG中各頂點的度數(shù)均為偶數(shù)DG中各頂點的度數(shù)均為奇數(shù)15平面圖(如下)的三個面的次數(shù)分別是（）A11，3，4 B11，3，5C12，3，6 D10，4，3二、填空題（本大題共10小題，每小題2分，共20分）16求一個公式的主析取或主合取范式的方法，有_法和_法。17給定謂詞合式公式A，其中一部分公式形式為()B(x)或(x)B(x)，則量詞，后面所跟的x稱為_，而稱B為相應量詞的_。18設X，U，V，Y都是實數(shù)集，f1：XU，且fl(x)ex； f2：UV，且f2(u)u (1+u)；f3：VY，且f3(v)=cosv。那么f3f2f

38、1的定義域是_，而復合函數(shù)(f3f2f1)(x)= _。19集合X=a，b，c，d上二元關(guān)系R=<a，b>，<a，c>，<a，d>，<b，c>，<b，d>， <e，d>，則R的自反閉包r(R)= _，對稱閉包s(R)= _。20已知G=<l，-1，i，-i，·>(其中i=，是數(shù)的乘法)是群，則-l的階是_；i的階是_。21對代數(shù)系統(tǒng)<S，*>，其中*是S上的二元運算，若a，bS，且對任意的xS，都有a*x=x*a=x，b*x=x*b=b，則稱a為運算“*”的_，稱b為運算“*”的_。22設

39、<S，*>是群，則<S，*>滿足結(jié)合律和_；若S>l，S中不行能有_。23寫出如右有向圖的一條初級回路：_，其長度是_。24一個_且_的無向圖稱為樹。25在簡潔無向圖G=<V，E>中，假如V中的每個結(jié)點都與其余的全部結(jié)點鄰接，則該圖稱為_，假如V有n個結(jié)點，那么它還是_度正則圖。三、計算題(本大題共5小題，第26、27題各5分，第28、29題各6分，第30題8分，共30分)26若集合A=a，b，c的冪集為P(A)，集合B= O/， O/ 的冪集為P(B)，求P(A)P(B)。27構(gòu)造命題公式(p (q r)p的真值表。28求圖G<V，E>的

40、可達矩陣，其中Vv1,v2,v3,v4E(v1,v2), (v2,v3), (v2,v4), (v3,v2), (v3,v4), (v3,v1), (v4,v1)29求下列公式的主析取范式和主合取范式：（PQ）（PR）30設A2，3，4，6，8，12，24，R為A上整除關(guān)系，試畫<A，R>的哈斯圖，并求A中的最大元，最小元，極大元，微小元。四、證明題（本大題共3小題，第31、32小題各6分，第33題8分，共20分）31設M是偶數(shù)集，和·是數(shù)的加、乘運算，證明<M，·>是一個環(huán)。32設R是集合X上的二元關(guān)系，證明R是X上傳遞關(guān)系當且僅當RRR。33設G

41、是簡潔平面圖，G有n個頂點m條邊，且m<30，證明G中存在一項點v，d（v）4。五、應用題（本大題共2小題，第34題6分，第35題9分，共15分）34推斷下面推理是否正確，并證明你的結(jié)論。假如小王今日家里有事，則他不會來開會。假如小張今日看到小王，則小王今日來開會了。小張今日看到小王。所以小王今日家里沒事。35有6個村莊Vi，i=l，2，6欲修建道路使村村可通。現(xiàn)已有修建方案如下帶權(quán)無向圖所示，其中邊表示道路，邊上的數(shù)字表示修建該道路所需費用，問應選擇修建哪些道路可使得任二個村莊之間是可通的且總的修建費用最低?要求寫出求解過程，畫出符合要求的最低費用的道路網(wǎng)絡圖并計算其費用。全國2007

42、年4月高等教育自學考試離散數(shù)學試題課程代碼：02324一、單項選擇題（本大題共15小題，每小題1分，共15分）在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1下列命題公式中不是重言式的是（）Ap(qr) Bp(qp)Cp(pp)D(p(qr)(q(pr)2下列語句中為命題的是（）A這朵花是誰的？B這朵花真秀麗??！C這朵花是你的嗎？D這朵花是他的。3設個體域是整數(shù)集，則下列命題的真值為真的是（）Ayx(x·y=1)Bxy (x·y0)Cxy (x·y=y2)Dyx(x·y=x2)4關(guān)于謂詞公式（x

43、）(y)(P(x,y)Q(y,z)(x)p(x,y),下面的描述中錯誤的是（）A（x）的轄域是（y）（P（x,y）Q(y,z)）Bz是該謂詞公式的約束變元C（x）的轄域是P（x,y）Dx是該謂詞公式的約束變元5設論域D=a,b，與公式xA（x）等價的命題公式是（）AA（a）A（b）BA（a）A（b）CA（a）A（b）DA（b）A（a）6集合A=1，2，3上的下列關(guān)系矩陣中符合等價關(guān)系條件的是（）A BC D7設A=Ø，B=P（P（A），以下不正確的式子是（）AØ ，Ø ，Ø ，Ø 包含于BBØ 包含于BCØ ，Ø

44、包括于BDØ ，Ø ，Ø 包含于B8設Z是整數(shù)集，E=，-4，-2，0，2，4，f：ZE，f（x）=2x，則f（）A僅是滿射 B僅是入射C是雙射 D無逆函數(shù)9設A=1，2，3，4，5，A上二元關(guān)系R=1，2，3，4，2，2，S=2，4，3，1，4，2，則S-1R-1的運算結(jié)果是（）A4，1，2，3，4，2B2，4，2，3，4，2C4，1，2，3，2，4D2，2，3，1，4，410設有代數(shù)系統(tǒng)G=A，*，其中A是全部命題公式的集合，*為命題公式的合取運算，則G的幺元是（）A沖突式 B重言式C可滿足式D公式pq11在實數(shù)集合R上，下列定義的運算中不行結(jié)合的是（）Aa*b=a+b+2abBa*b=a+bCa*b=a+b+abDa*b=a-b12下列集合關(guān)于所給定的運算成為群的是（）A已給實數(shù)a的正整數(shù)次冪的全體，且a0，1，-1，關(guān)于數(shù)的乘法B全部非負整數(shù)的集合，關(guān)于數(shù)的加法C全部正有理數(shù)的集合，關(guān)于數(shù)的乘法D實數(shù)集，關(guān)于數(shù)的除法13設無向圖中有6條邊，有一個3度頂點和