南京大学—计算机专业考研复习资料—离散复试题.docx

《南京大学—计算机专业考研复习资料—离散复试题.docx》由会员分享，可在线阅读，更多相关《南京大学—计算机专业考研复习资料—离散复试题.docx（2页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2013 年l.t(R)传递闭包，S (R)为对称闭包，r(R)为自反闭包；证明t(s(r(R)为等价关系2 .G为pM阶群，p为素数，证明G存在(n-l)阶子群. (1)证明3-正则图节点数必为偶数；(2)画出2个不同构的6阶3-正则图3 .证明若e(S2-3v+2)/2, G连通(e为边数,V为点数).是一个谓词证明题2012 年1、设A是一集合，s=p(A)-A-空集，*、证明(s,包含符号)不含最大元和最小元。二、求s的所有极小元组成的集合和所有极大元组成的集合。三、s的极小元组成的集合与极大元组成的集 合等势。2、G为群，S为G的子群，证明S的左右陪集数目相等。3、用一元谓词逻辑证明

2、：已知：一、Vx(p(x,x”(p(xM-p(c,c)；二、mx(p(x,x)用上述条件可以推出 p(c,c).4、s=xl,x2，,xn为平面上点的集合，且任意点间距离至少为1,证明这些点至多有3n对距离为1的点，注意(xi,xj)与(xjzxi)是一样的。5、G是简单无向图，且不含k4 (4阶完全图)，证明|E|=l/3x(V*V),|E|和|V|分别为G的边数和点数。参考答案1、课件上有一样的2、离散,屈婉玲，高教第十章P189页3、离散，屈婉玲，高教第五章P69页，用量词辖域收缩与扩张等值式”可以将任意转为存在。4、先证明任意一点至多与3个点距离为1。以任意点Xi画半径为1的圆，与Xi

3、距离为1的点只能分布在圆周上，该圆周长为3.14又因为圆周上的各点距 离至少为2,所以圆周上只能有3个点。再利用归纳假设证明题目假设n个点至多有3n对距离为1的点。现有n+1个点，因为对于新加的点，至多有3个点与它距离为1,所以至多有3n+3对距离为1的点，得证5、那个任意选取一个K3,那么其他任意一个节点到这三个点只能由两边，那么这三个点的边数和为5,是 在顶点为n+1的情况下，忘说这个了，选了一个K3,剩下n-2个顶点，这n-2个顶点到这三个点做多有2*(n-2)条边，那么这三个点的边数和就是2* (n-2)+3 = 2n-l,所以必存在一个点的关联边数小于等于(2n-l)/3, 那么把这

4、一个点和关联的边删除，剩下的就是N个顶点的图，由归纳法N个顶点的不含K4的图边数为NA2/3, 那么N+1个顶点的边数必小于阴2/3+(211)/3 (N+l)A2/32011 年1 .R 为 A 上的等价关系,|A|=njR|=rjA/R| =t，证明 n2=rt.al=(0 110) o2=(0 -ii0)(两个是二阶复数矩阵)，证明为8阶群。0为矩阵乘法，G为01、。2的 任意辕或乘积的集合。2 .证明6阶简单连通图G,在G中或其补图中存在3阶完全子图。3 .证明任意简单连通图均存在生成树。4 .在命题逻辑中，定义-*p q p-*qTTFTFTFTFFFF证明使用和-*可以表示所有的命

5、题连接词。5 .证明Vx(p(x)fq(x)与，(p(x)Aq(x)(表示逻辑非)参考答案1、因为|A/R|=t,所以有t个等价类，设每个等价类中的关系个数为Xi,则所有等价类的关系个数之和为|R| 即 Xl2+X22+Xt2=rrt-n2 = t*(Xl2+X22+.+Xt2)- (Xl+X2+.+Xt)2=(Xl-X2)2+(Xl-X3)2+.+(Xl-Xt)2+(X2-X3)2+.+(X3-X4)2+.PS:无法理解最后一个式子的可以用t=2,3,4来试下2、未做出正确答案3、书本P295 50题，第十四章课后习题最后一题4、宋方敏课件第26讲5、原来的答案不见了，大家自己做吧，该题比较

6、简单6、未做出正确答案2010 年一S T是定义在集合A上的关系，T (X)是X的传递闭包 (1)S, T是A上的对称关系,证明对称当且仅当5。丁=丁。5(2) S, T 是 A 上的关系，证明 T (SUT) =T (T (S) UT (T)二.G是奇数阶的Abel群，证明G中所有元素之积为单位元三.H和K是群G的正规子群，且HcK=e,证明：hH且kK,有hk=kh四.G的顶点数大于3且u、v属于V, u、v不相邻，且满足D (u) +D (v) =n。证明G为Hamilton图当且 仅当G+e为Hamilton图，e为u、v新边五用一阶谓词逻辑推导证明(VxA-B)-(mxA-B),B与

7、X无关。参考答案一、(1)用定理证明很简单(2) VSCT(S), TUT ASUTct (S) UT (T) AT (SUT) ct (T (S) UT (T) VT(S)CT (SUT) , T(T)ct (SUT)T (S) UT (T) CT (SUT)又7T (S) UT (T)为传递的 AT (S) UT (T) =T (T (S) UT (T) AT (T (S) UT (T) ) ct (SUT)二、先取a属于G，令a*是a的逆元，注意a不等于a*,因为若他们相等则a的阶是2,这与G的阶是奇数矛盾(Lagrange定理)。故G中除e外，任意a与a*成对存在。 G中所有元素之积，由于G为Abel群，可交换a与a*在一起，最后结果为单位元。三、k逆hk属于H, h逆也属于H,他们乘起来为h逆k逆hk,也自然属于H h逆k逆h属于K, k也属于K,他们乘起来为h逆k逆hk,也自然属于k 所以 h 逆 k 逆 hkHcK=e, h 逆 k 逆 hk=e,hk=kh四、P306第10题(书上课后习题)五、原式化成(任意xA且非B)或(非存在xA或B)然后对或分配任意xA或B或任意X非A然后任意、(A或非A)或B所以为1