2005离散A答案.docx

总分三四五六七八九I将分II.格FiS命电符号化(B分)I、收音机不响是因为电池没电/或见开关没仃打JhPl收青机响:Q：电池仃也R：l<.-1P-(11QV-IR)2、除拿你克我去或齐绐我买书,否则税不去.P：你解我去，Q：你给我买招；R：我去-1(PVQIR3、不是所有.的运动员称是收炼员，Pco*R处运动员：Q(x”息型战嫉31Vx(P(X)-QiX)4、任何一个11然数不暴奇依政史黑三UP(X>:x½fl<Sft;Q<X>RX>:XV(P<x)-<Q(x)IR(X)得分三.12分)"断卜面命8!的直值，并说明原囚.1 .若RWSA上的伸通关黛,则R'也是柴合A上的付通关收、(3分)ACagU>)WN:<i,h>R,.<b>R,.M一定的<I2(RCCgWR.曲干R站件赛的.Dq：>WR.瑞以打<WR,.即R'足蜒命R上的传珏天葛.，2分2 .四阶林中。行四阶元。3分)WfrttI分)ClCin网论价中没”四的元(2分)3 .至少含3个无点的标不足有补格<3分)/(<15>)WW：元素个较大干等于3的膑中.除全上界和金卜界舛，R怆元来勿没”#元.所以至少含3个花家的金不足力补的.4 .如果图G星不逢闻的那么Jl朴图己一定是连通图,(3分)«命Mll分即知(fttu.vHC).寰s'，不如接.刎住不中有边(d),所以元中u。,足连动的；疝汉在G中u与y用找.MJutjv住G的用个if划分左Ih于GIM；4通肛所以C&右月个波动分上GlYI).iwev(G>.÷tfGl>fni.<),<.v>.f½ftC中9"出“、.所以G2妾通的、(2分)东北大学考试试卷（A卷）2001-2005学年第2学期课程名称：离欣数学O*得分学号*一.单选国（10分）：1、定集合S:Ih加.3和条合R=Ha>2,3Z>>以下是真命也的/HD).：.WCSR.)s：C.(allRaMl3h4)：2、0X=氐l>.cl.MI佛的.无关系有(C)和.：A.9B.81:C.512U256姓名*；3、i&R,和R：是北空集介A上的等价关系下述各式是A上等价美系的孙（C）a.Uxaj-r.b.Rr也OCRJD.rtRRj>：4.花I钟300的婺数中不能被3和7栋除的孙<D冲.、A.128R.142C.171U172*：5、下列关系.健构成函数的为1B>.R,-(<x<.xf>(.6X)<.+xr)<10lB.<xl.,>I<l.x,R>-：.H卜I、：6、P足个次数.1"型个Parte环群WG中犷(D)个生成元.：.IB.2:c.pur-Q7、令<G>是/Mt中G=(ahc设U是幺元，！Wb*c=A>.：B、丁是个完全二叉例.有。个叶子靖点，则盯边B）条.lK.：<nIlC.n,R211l9. <A.W>是布尔格.当Il仅当它是DJ格.：A,打补B,分配：C.何MR盯扑分配*：10.下面代数於筑是环的MC卜：.»B.<P（E>.>U>C.“旧.电n>D.<1.>得分六.“0分）设A为正整数典介.R是A.定义的二元关系：且仅力N=yu时才上«x.y>.<u.v»R.(I)试证明RAi等价关条.(6分)(2)ittA=(l2.4).求AN时R的有9u(4分)I、迂明；(>7nb-hn<a,b>R<b>则R是自反的2分)(2)若<n,b>R<c.d>由鹿Udbc叩山:曲W<c,b>ft<8,b>如R条劝称的(2)(3)若<n,b>R<c,d>.<c.d>R<e.f>.fhg.:<i=bc.ci'=d<则a<icf=tcdefiaf=be：<%b>R<.f>即R是恰速的2分由以上可将R是AXA上的等价关索证毕2、VizAXA=(<I.I>.<I>.<I<4>.<2.I>.<2.2>.<2.4>.<4.I>.<4.2>.<4.4>)R-AXA上的等价关累，由egR6dAQMbc打当R的等价关系图如下：QQ<4,1XJ<l,4r>由网可将SXAg1<I.I>.<2J>.<44>)4<J>.<2(4>).<1X<4>).(<1,4>.(<4.l>)I（4分.写出一个元/,分1分）:得分:四,46分)求(P-71R的本自双数R和主析取范式.j(17)<->R<X(-U,V-tQR)V(PAQ)A-<)：8TRVJQmRIV(00,TO<->pR)(-.QVQ>IV('-PVP)(FAR”V(PQ)'T)：OTFIQR>V(-4>QR>V(PA-?AR)V(PQ-<)三即为Kl式的主所取范式"分)可见主析取他R包畲小项m11m5.11u.所以其上台取范武中包含的大Ja：时应为M<1M2,M<.Nb.即丘式的主合取范式为I：U,VQVR><PV-OVR)<-J,VQVR)<VWY>(2分)M：班累两个与犹余品由公式»M加正一个为3分：仪八：Q由正脸的根得分4?看=,工得分I分.：I得分I.五.(6分)设VG>是一个而*WG如!Rf是从G到G的映射使用财手卷j个xWG，WWftxX=*x*1.试证明f是从G到G的自同构映射.封证明，。)首先正RX)为双财南数：证f(x)为人则H三h任取z.内WG.I1.xiKn 假设KXI)=Rx2)即axa"=AxJa1. 山琳的消去性可知XI=X:.与XlWX,相矛AkO所以ftx)KaX：),R0f(x雇人”的.(2分)证在x)为调射曲t:<Hr-yG,由群中方程的可解性,可知必存在：xG.M>*a=ax.UPy=ax*a,.所以。x)为演财函数.(2分)三2)证明同构等R成立尊由SJ和偶：f(x,QWx,a'1-a*ex*a'':=>x*aaJ*xrJRz/在XA：即f是从G到G的门同构映射C(2分)得分八一18分)用帚词逻辑推理方法，证明卜面推理的仃效性(耍求技犯较M观定的格式,朽写推理过程)3x(A(>V)><B<y)C<.v,y>H.Vx<A(x>Vy(D(y>-<<.x.y>>)=3-ay(B<y),-J)ly)证明：<>3x(A(x)AVy(B(y)-C(x.y)P(2>A<i>)AVy(B(y)-C(n,y)>ES(HA<8)TI1«)Vy(B(y)-C(a.y)1.(2分)Vx(x)-Vy(D(y)-C(x,y)>P6)A<a)-Vy(y)-X(n,y>)1.SVy(y)-c>y)>T<3)(6)I11(2分)(B)B(b)-*C(a,b>US«)<9)DaOrYQ.b)1.S皿Caeb)-DooT<9)E.<10B<b)-,0(b)T<8三I(>(2分)g-B(WV-IXb)T<10E.OD-t(B<b)AD(b)rg氏<WVy-.(B(y)AD(y)>IiGCS<W-3y(B(y)D(y)7OOEa(2分):得分I七,1。分）设*某个醉.RJftC中等侑关系.定义为：M11fz11.b.cG.：卸果有<MbMc>ER>.cCR.乂定义典含H为：H=>:xG,ft<x.e>R,aJC中幺元）6求证<11.必<&的子群.：证明1（川定义证明）；（DiiH是G上的非空子朱：（2分）：由TyQf是个楙畲有幺元c，由已知象Slft<eCWRu是Il中的元武.：所以HtG上的非空子维（2>i三在H上涓足N闭性,3分）任取、I,MWH,由H定义可知：<x,e>GR.<x,c>GR：由<XhOER得Vx,*c.x1*xr,>R,再由R的定义可和Ve.xl,>eR：由丁R是等价关奈.由传迩性得vq>ER.*：Wft<*l,x.x2.Xl,>R.W<xX2,C>eR.1I<X2eH9运。“在H上是对巧的.：（3）i£“*”在Il上有幺元：2分：由丁两个系线的运算相同.U然G中的幺元eAJH中的幺元.（4>证H中每个元求郁仃逆元I（3分）j任取WH,由2中的证明可用<ux,>WR,由于R是好价关京，由对你7ftfl<xl.e>eR.即xWH所以H中句个元京都有咫元.：续上所逐.。广肝的定义乙刈6产«8仁的F；*j注:用调义中方法2迂用，划等空子集的证明N2分,时阳性和兀武可逆的证明A分别得4分:川讲义中法4证叫修空f象的荏明3分.R½ea*beH的正I叨知7分，1t.求右图所示加第有向图的可达性机阵人«分）V.3%得分九.（20分）ras½1. 个荷冷无向阳七个靖点的慢数分别为665,1.3.3.U向这样的图是否存在？若存在，请画出相应的图,ftM.说明理由.（3分）O答I不存在】分：内为7个帘点中有2个收数为6所以其它节点的慢数H小为2,不可使存：在2度节点。（2分）2. ift<l>A个归序集其中A=l2.3.4»6.9.加54»2161.R是A卜的整除英泰.（1）演山R的哈斯图I（2）求AM,6.9）的极大值横小施,小上界和最大下界（3）试网R.W见告为格,若足.判斯其是行为分配格行衿格别布尔格并收明理由?ri'1R的哈斯图如右国所示（2） B=（4A9J的筱大值和微小岫为46.9最小上界为216,Ai大小界为I（2分（3RW足为格,是分配格,闪为不含有五元索等分配于Mh不是有补格，因为其中元索2.3、6没有补元故也不是加尔格25»3. G是个连遗平面图,G与其对偶图网构称之为白何程），如JKGfiJ个玷点则G芍军少条边?为什么？（3分答：Gft2v2“分）由于G城自对蜴图,故G的玷点数与其而故相忖由欧抢公式vc+r=2W：C=Vr2=8v2=2v2即G"2v2条边.（2分）