【计算机】南理工离散数学A卷附答案

南京理工大学课程考试试卷(学生考试用)课程名称：离散数学A学分：45大纲编号试卷编号：考试方式：闭卷满分分值：100考试时间：120分钟组卷日期：20XX年1月2日组卷教师(签字)朱保平审定人(签字)金忠学生班级：计算机学院09级(6分)试把下列语句翻译为谓词演算公式(1)某些人喜欢所有明星；(2)并非“所有人均喜欢电脑游戏”。(6分)把下列数论语句化为特征函数%为平方数且％为偶数；%是y的倍数或%小于等于y。(6分)已知公理：(A)(PaQ)TP(PaQ)TQ(PT(QT(PaQ))(D)」「PTP及分离规则和代入规则。试用假设推理证明下面公式为本系统中的定理(PTQ)T((「「PaR)T(QaR))(8分)试把函数h(%1,%2,%3,%J=f(g1(%1,b),%5,g2(%2,%3),4)(其中b为自然数)化为(m,n)标准迭置。(6分)已知知识的符号表示3%(P(%)aVy(D(y)TL(%,y)))V%(P(%)TVy(Q(y)T「L(%,y)))结论：V%(D(%)T「Q(%))试用霍恩子句逻辑程序证明之。(8分)已知：A={{①},{1}},B={{〃}}。试求2a；B义2a。（6分）已知A,B,C是三个非空集合，f为A到B的映射，g为B到C的映射。证明：如果gf是A到C的双射，则f为A到B的单射，g为B到C的满射。（6分）（G,•）是群，（”,•）是（G,•）的子群，〜是G上的二元关系，对于任意的a,bgG,a〜b0b-i-agH。试证明（1）〜为G上的等价关系；（2）对于VagG，有[a]=a•H。1 ”,、（8分）已知Q*=Q-{0},Q是有理数集，Vm,ngZ,n*m=7nm，证明（Q*,*）是群。（6分）G=（V,E）是一个简单连通图。且G是一个二部图（偶图），相应地顶点分类为{匕,V2}，且I匕闺匕I。证明G不是哈密尔顿图。（8分）（1）画一个10个顶点欧拉图但非哈密尔顿图，它是简单无向图，有奇数条边；（2）画一个10个顶点哈密尔顿图但不是欧拉图，它是简单无向图，有偶数条边。（6分）设G=（V,E）是连通图，且egE。证明：e为G的割边（即拿去此边后，G变成不连通的两部分）当且仅当e在G的每棵生成树中。（6分）设（H,*）是群（G,*）的子群，如果A={xIxgG,x*H=H*x}，证明（A,*）是（G,*）的子群。（8分）T是一棵树。试证明T为二部图；…—n2（2）若G=（V,E）是二部图，且IVI=n,IEI=m，试证明m<--o4（6分）G=（V,E）是一个简单无向图。若IVI>11,则G或G是非平面图。南京理工大学课程考试试卷答案及评分标准课程名称： 离散数学 学分4.5分 教学大纲编号：06022104-试卷编号：考试方式： 闭卷 满分分值：」W—考试时间：」20—分钟.（共6分，每小题3分）TOC\o"1-5"\h\z解（1）3x（P（x）A（Vy（S（y）fL（x，y）））） 3分（2）「Vx（P（x）f（Vy（G（y）fL（x，y））））或「Vx（P（x）f（3y（G（y）aL（x，y）））） 3分注：本大题为基本题，考核自然语言的谓词表示方法。.（共6分，每小题3分）（1）N2（N2（x&[%良]2）+N2rs（x,2）） 3分（2）N2rs（x,y）•（N2（x&y）=min（N2rs（x,y）,N2（x&y）） 3分注：本大题为基本题，考核特征函数的表示方法。.（共6分）证明：（1）PfQ 前提假设（2）「「PaR 前提假设（「।「।PaR）—f「1-1P 公理（A）（「「PaR）fR 公理（B）（5）「「P （2）（3）分离（6）R （2）（4）分离（7）「「PfP 公理（D）（8）P （5）（7）分离（9）Q （1）（8）分离（10）（Qf（Rf（QaR）） 公理（C）（11）Rf（QAR）） （9）（10）分离（12）QaR （6）（11）分离由假设推理证明过程的定义知PfQ,「「PAR|-QaR由推理定理知（PfQ）f（（「「PaR）f（QaR））注：本大题为基本题，考核命题演算的假设推理系统。4.（共8分）h（xjx2,x3,xJ=f（g1a41,SbOI41），144,g2（142,143）,S40141）（xjx2,x3,x5）——8分

.(6分)证明：P(a)L(a,y)-D(y)-P(x),Q(yj,L(x,y1)D(b) 3分{a/x}(1)(3)归结{b/y1}(5)(6)归结 3分{a/x}(1)(3)归结{b/y1}(5)(6)归结{b/y}(2)⑺归结(4)(8)归结 3分-Q(y1),L(a,yJ-L(a,b)—D(b)0注：本大题为基本题，考核命题演算的归结推理系统.(共8分，每小题4分)解：(1)2a=曲，4{{1}},{仲}}}-------4分Bx2a={({a}g),({a},A),({a},{{1}}),({a},{{6}})}注：本大题为基本题，幕集和积集的定义.(6分)假设g。f是A到C的双射。TOC\o"1-5"\h\z先证f是A到B的单射。采用反证法。如果f不是A到B的单射，则存在％Wx3,使得f(x)=f(x)，于是g(f(x))=g(f(x))，即g。f(x1)=g。f(x2),这与g。f是单1 2 1 2射矛盾，即证得f为A到B的单射。 3分再证g为B到C的满射。由g。f的满射性质，对于任意的ceC，存在aeA，使得g。f(a)=c，即有f(f(a))=c。记b=f(a)，即有g(b)=c，即证得g为B到C的满射。 3分注：本大题为基本题，考核单射和满射的证明方法。.(共6分)证明：(1)对于任意的aeG，:a-1•a=eeH，丁a〜a，故〜是自反的。对于任意的a,beG,若a〜b,则有b-1•aeH，.二(b-1•a)-1=a-1•beH，.二b〜a，故〜是对称的。对于任意的a,b,ceG，若a〜b,b〜c,则有b-1•aeH且c-1•beH,/.(c-1•b)•(b-1•a)=c-1•aeH,「.a〜c,即〜是传递的。这样，〜是G上的一个等价关系。 3分(2)先证[a]=a•H。对于任意的xe[a],x〜a,即有x-1•aeH,即存在

heH,x-i-a=h。/.x=a-h-1ga-H。故[a]ca•H。再证，a•Hc[a]。对于任意的yca•H，即有heH，使得y=a-h，于是，TOC\o"1-5"\h\za-1•y=h♦H,/.a〜y,ye[a]，故a•Hc[a]。综上所述，[a]=a•H 3分注：本大题综合题，考核等价关系，群、陪集的定义、集合相等的证明方法。.（8分）证明：（1）封闭性。对于Va,beQ*,a*b=iabeQ*。 2分7（2）结合律。对于Va,b,ceQ*,a*（b*c）=a⑤ibc=+abc=（a*b）*c 2分（3）幺元7。因为VaeQ*,a⑤7=+a7=a=7⑤a 2分7（4）逆元。VaQ*，其逆元为49，因为VaeQ*,a⑤好=+a的=7=妗⑤a 2分a a7a a注：本大题为基本题，考核群的定义。.（共6分）证明：不妨假设IV1I<IV2I，根据二部图的定义知，从图中去掉V1中的顶点后，得到IV2I个连通分支。因为所得到的连通分支数目221大于所去掉的顶点数目211，即W（G-V1）=IV2I>IV1I,即哈密尔顿图的必要条件得不到满足，所以图G不是哈密尔顿图。注：本大题为综合题，考核二部图、哈密尔顿图的必要条件等。（共8分，每小题4分）注：本大题为基本题，考察哈密尔顿图和欧拉图定义等。.（共6分）证：先证必要性。假定e为G的割边。用反证法。如果e不是在G的每棵生成树中，则存在G的一棵生成树T，e不在T中。因为生成树T是连通的，而e不在T中表明拿去边e后，图G仍然连通，所以与e为G的割边的假定矛盾。矛盾表明e在G的每棵生成树中。 3分再证充分性。假定边e是在G的每棵生成树中。用反证法。如果e不是G的割边，则从图G中拿去此边后所得到的子图G1仍然连通。由子图G1得到的生成树也是图G的生成树，但该生成树中不包含边e，这与e是在G的每棵生成树中的假定矛盾。矛盾表明e是G的割边。注：本大题为综合题，考核连通图、生成树、割边等相关概念。13证：假设e是群G的幺元。显然，有e*H=H*e=H,所以eeA,即A非空集。对于Va,beA，即有a*H=H*a,b*H=H*b。下面要证a*beA。先证(a*b)*HuH*(a*b)，对于Vxe(a*b)*H，存在heH，使得x=(a*b)*h。显然x=(a*b)*h，因为b*heb*H=H*b，所以存在heH，使得b*h=h*b。于是，x=a*(h*b)=(a*h)*b，所以存在i i i iheH，使得b*h=h*b。于是x=a*(h*b)=(a*h)*b，又因为a*hea*H=H*a，所以存在heH，使得a*h=h*a，于是，x=(h*a)*b=h*(a*b)eH*(a*b)。 3分同理可证H*（a*b）u（a*b）*H。所以有H*（a*b）=（a*b）*H，即证得a*beA对于VaeA，即有a*H=H*a。下面要证a_1eA。先证a-1*HuH*a-1。对于xea-1*H，存在heH，使得x=a*%。显然，x-1=h-1*a。因为h-1eH，故x-1eH*a=a*H，所以存在々eH，使得x-1=a*々，于是x=h1T*a-1eH*a-1。同理可以证得H*a-1ua-1*H。所以有H*a-1=a-1*H，即证得a_】eA。 3分注：本大题为提高题，考察群、子群、陪集、集合的相等等原理。14.（共8分，每小题4分）（1）因为T是一棵树，所以T中没有回路，也可以说T中回路长度都为0（0为偶数），这样根据二部图的等价定义（即所有回路长度均为偶数）知：T是二部图。 ------4分TOC\o"1-5"\h\z（2）假设二部图G的顶点分类为（V1V2）。不妨记n1=IV1l,n2=IV2l。显然，n1+n2=n，而且n1<n1n2，于是m<n1n2<（"1+<）2=q 4分\o"CurrentDocument"4 4注：本大题为提高题，考核树、二部图等相关性质。15（共6分）证明：用反证法。设G和G的