離散數(shù)學(A)卷

1、一、單項選擇題(本大題共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)4.設i是虛數(shù)，是復數(shù)乘法運算，則G=<1,-1,i

2、,-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ù)集， 定義為x xy=xy, x,yZD.Z，+，Z是整數(shù)集，+是數(shù)的加法運算7.設A=1,2,3，A上二元關(guān)系R的關(guān)系圖如下：R具有的性質(zhì)是

3、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-y,A(x,y):x<y.下列公式在R下為真的是( )A.( x)( y)( z)(A(x,y)A(f(x,z

4、),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.是約束變元但不是自由變元14.若P：他聰明；Q：他用功；則“他雖聰明，但不用功”，可符號化為( )A.P

5、Q 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(A),則x,y最大下界是_，最小上界是_。20.設函數(shù)f:XY,如果對X中的任意兩個不同的

6、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,y R，則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是相容的，若H1H2Hn是_，則稱H1,H2,Hn是不相容的。25.判斷一個語句是否為命

7、題，首先要看它是否為 ，然后再看它是否具有唯一的 。三、計算題 (共30分)26.(4分)設有向圖G=(V,E)如下圖所示，試用鄰接矩陣方法求長度為2的路的總數(shù)和回路總數(shù)。  27.(5)設A=a,b,P(A)是A的冪集， 是對稱差運算，可以驗證<P(A)， >是群。設n是正整數(shù)，求(a-1ba)n a-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的最大，最小元，極大、極小元，上界，下確界，下界，下確界。29.(6分)求(

8、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(x)( x)B(x)五、應用題(共

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

10、7.D 8.C 9.D 10.B11.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)n a-nbnan= (a-1)nbnan= 當n是奇數(shù)時，(a-1ba)n a-nbnan=a-1ba (a

11、-1)nbnan=a-1ba a-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=(v1,v4), e8=(v4,v3)e9=(v3,v

12、5), 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) (換名) x1 y1(F(x1,y)G(x,y1) x2H(x2) x1 y1(F(x1,y1)G(x,y1) x2H(x2) x1 y1 x2(F(x1,y1)G(x,y1)H(x2)四、證明題32.設T中有x片樹葉，y個分支點。于是T中有x+y個頂點，有x+y-1 條邊

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

14、f=f IA=f,故IA是F， 中的幺元(4) fF,因為f是雙射函數(shù)，故其逆函數(shù)是存在的，也是A到A的雙射函數(shù)，且有f f-1=f-1 f=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：他是計算機系研究生r：他學過DELPHI語言s:他學過C+語言t:他會編程序前提：(pq)(rs),(rs)t結(jié)論：pt證p P(附加前提)pq TI(pq)(rs) P(前提引入)rs TIr TIrs TI(rs)t P(前提引入)t TI