资源描述：
《《离散数学》期终试题-软件学院-2004-6.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、选择题20分10题多选题1,LetB={ø},A=ρ(ρ(B)),findthecorrectonesinfollowingstatements:(1)Ø∈A(2){Ø,{Ø}}∈A(3){Ø,{{Ø}}∈A(4){Ø,{{Ø}}A2,LetRbearelationonA={1,2,3,…,10},R={(x,y)
2、x+y=10,x,y∈A},thenRis:(1)reflexive(2)symmetric(3)transitive(4)antisymmetric3,Let
3、A
4、=n,howmanybinaryoperationscanwedefin
5、eonA:2nn2(1)2n(2)n2(3)n(4)n4,operationdefinedasfollowing,whichonescannotmake({a,b},*)amonoid?(1)(2)(3)(4)5,whichonesarelatticesinthefollowingposets?(1)(2)(3)(4)6，LetdirectedgraphD=,then:(1),EV×V(2),EV×V(3)E=V×V(4)V×VE7,Inaconnectedundirectedgraphwithnvertices,thenumberofed
6、gesis(1)atleastn-1(2)atleastn(3)atmostn(n-1)/2(4)atmostn2/28,whichoneistautology?(1)(P∧(P→Q))→Q(2)P→(P∨Q)(3)P→(P∧Q)（4）(P→Q)→Q9,Inthefollowingsentences,whichoneistrue?(1),(2),(3),(4),10,Howmanynumbersmustbechosenfrom1to25toensurethatoneofthemisamultipleofanother?(1)12(2)13(3)14(
7、4)15计算题25分1,Letpbetheproposition“Iwilldoeveryexerciseinthisbook”andqbetheproposition“Iwillgetan‘A’inthiscourse.”Expresseachofthefollowingasacombinationofpandq:a),Iwillgetan‘A’inthiscourseonlyifIwilldoeveryexerciseinthisbook.b),Iwillgetan‘A’inthiscourseandIwilldoeveryexerciseint
8、hisbook.c),EitherIwillnotgetan‘A’inthiscourseorIwillnotdoeveryexerciseinthisbook.d),Formetogetan‘A’inthiscourseitisnecessaryandsufficientthatIdoeveryexerciseinthisbook.2,Whatisthecoefficientofx12y13intheexpansionof(2x-3y)25?3,computetheconnectivityrelationforRdefinedbythefollow
9、ingmatrix(detailstepsneeded):4,FrompointA,usePrim’salgorithmtofindaminimumspanningtreeinthefollowinggraph（detailstepsneeded）:EA3D2F46J7G53I6H5B3C22K14L6725,findamaximumflowinthefollowingnetworkbyusingthelabelingalgorithm.(Detailstepsneeded).21332244236431证明题：40分5题证明题(1),Letkbea
10、positiveinteger.showthat1k+2K+…+nkisO(nk+1).IsitO(nk)?Why?(2),Letn=p1p2…pk,wherethepiaredistinctprimes.ShowthatDnisaBooleanalgebra.(3),Showthatisomorphismrelationisanequivalentrelation.Ishomomorphismanequivalentrelationtoo?Why?(4),LetAisaBooleanalgebra.Defineoperation*asfollowi
11、ng:a*b=(a∧~b)∨(~a∧b)showthat(A,*)isanAbeliangroup.(5),
