离散数学a(答案)

1、离散数学A卷闭卷、70学时、 填空选择题每空1分，共26分1、 给定命题公式如下：p q r。该公式的成真赋值为 A，成假赋值为B,公式的类型为C。供选择的答案A:无；全体赋值； 010，100，101，111；010, 100，101，110，111。B:无；全体赋值； 000，001，011 :000，010，110。C:重言式；矛盾式；可满足式。2、在公式xPyQx,y yRx, y中，x 的辖域是Pz Qx,z_，y的辖域是Rx,z。3、设 Z+=x I x ZA X>0, n 1, n 2, n 3是 Z+的 3 个划分。n 1=x I x Z+, n 2=S1,S2,S 1

2、为素数集，S2=Z+-S1. n 3= Z+,13个划分块中最多的是A,最少的是B.划分n 1对应的是Z+上的C, n 2对应的是Z+上的D, n 3对应的是Z+ 上的E.供选择的答案A:,B: n 1, n 2, n 3.C:,D:,E: 整除关系；全域关系；包含关系；小于等于关系；恒等关系； 含有两个等价类的等价关系；以上关系都不是。24、设 f : R R, f(x) x x2 x33 g : RR,g(x)=x+2,那么 f ° g(x)为2f(x) (x 2) x 12 x 12_c/ r x2x3f: R Rf(x)为f (x)X,g0x3是 A，f -1 B ,g -1

3、 C.供选择的答案A :单射不满射；满射不单射； 不单射也不满射：双射;B :，C :：不是反函数；是反函数；任课班级：114051-4、5、设G=0 , 1, 2, 3，假设。为模4乘法，那么<G,。>构成A， 假设为模4加法，那么<G，是B阶群，且是C o G中的2阶兀是D , 4阶元是E o供选择的答案A ;群；半群，不是群；B :有限：无限。C:Klein四元群；置换群；循环群;D ，E ：0;1和3;2o6、 设A, V ,人是代数系统，二元运算V和人对于 A是封闭的。如果对于 A中任意的元素a，b，c满足交换律、 结合律和_吸收律，那么称A，V，A 是格。7、6个

4、顶点11条边的所以可能的非同构的连通的简单的非平面图有4_个，其中有2个含子图K3,3,有_2_个含与K5同胚子图。二、计算题：每题5分，任选6题，共30分321、计算幕集 PA o Axx R x 2 x x 20答：PA=巾,-1,1,2,-1,1,-1,2,1,2,-1,1,210011000 R000110002、设S= 1，2, 3, 4，R是S上的二元关系，其关系矩阵为 求R的关系表达式。 dom R=?,ra n R=? R° R中有几个有序对？ R1的关系图中有几个环?答：关系表达示：<1,1>,<1,4>,<2,1>,<4,

5、1>,<3,4> dom R=1,2,3,4,ra n R=1,4 7 13、S= QXQ, Q为有理数集，*为S上的二元运算，任意<a, b>, <x, y>, S 有<a, b>*<x , y> = <ax, ay+ b> *运算在S上具有哪些主要性质； *运算有无单位元，零元？如果有请指出，并求S中所有可逆元素的逆元。答：*运算不是可交换的；可结合的；在 a=0且b Q或者1, 0时满 足幕等律。1, 0为*运算的单位元。对任意a,b Q x Q，只要 a<>0都存在逆元<1/a,-b/a&g

6、t; ;不存在零元。任课班级：114051-4、4、有向图D如图1-1所示,求D中长度为4的通路总数是多少?并指出其中有多少条是回路?图1-102100010A00010011答：a2=0021000100110012a3=001300110012002300340012002300355、当n和m从A4可看出,A4=中长度为4的通路有23条，其中7条为回路。为何值时，完全二部图Kn,m是欧拉图；哈密顿图；平面图；非平面图。答：n和m都是正偶数；n=m且n>=2；*=2；n>=3, m>=3&设无向树T由7片树叶，其余顶点的度数均为 3，求T中3度顶点数， 能画出几棵

7、具有此种度数的非同构的无向树？答: T中有5个3度顶点。设T中有x个3度顶点，那么T中的顶点数n=7+x, 边数m=n-1=6+x，由握手定理的方程2m=12+2x=3x+7解出x=5,T的度数列为1,1, 1，1，1，1，1, 3, 3, 3，3, 3。有两棵非同构的树。7、在图1-2所示的无向图G中，黑线边所示的子图为 G的一棵生成树T,求 G的对应于T的根本回路系统。对应生成树的弦分别为 e6,e7,e8,e10,e11。设它们对应的根本回路分别为C1,C2, C3, C4.C5，从对应的弦开始，按逆时针也可都按顺时针的顺序写出它们，分别为C1 = e6e4e5 C2 = e7e2e1

8、C3 = e8e9e2e1 C4 = e10e3e5e2 C5 = e11e3e5e2e9此图的圈秩为5,根本回路系统为C1,C2,C3,C4,C5任课班级：114051-4、111051-2任课教师：孙明三、证明题(每题6分，任选4题，共24分)1、 设Hi和H2是群G, *的两个互不包含的子群，证明G中存在一个元素， 它既不属于Hi,也不属于H2。证明：因为Hi H2,所以存在a Hi且a H2,又因为H2 Hi,所以存在 b H2,且 b Hi,显然 a*b G，因为 a Hi,Hi,*是G,* 的子 群，可推出b Hi,这与b Hi矛盾。同理可证，a*b H22、证明欧拉图中必没有割边

9、。证明：主要利用“无向图中，奇度顶点的个数为偶数这一结论用反证法， 设欧拉图中含有割边。由于欧拉图中每一个顶点的度数为偶数，所以割边的两 个端点也是偶数度顶点。删去割边后，构成两个连通分支，每个连通分支都含 有割边的一个端点；此时每一个连通分支中仅有一个奇数度顶点，这与矛 盾。所以，欧拉图中没有割边。3、设L , 是格，任取 a L,令 S= x I x L Axa证明S, 是L的子格。证明：对于任意的x,y S,必有x a和y a,所以x V y a,x A y a,故x Vy S, x A y S,因此S, 是L, 的子格。4、设G是6阶无向简单图，证明G或它的补图中存在3个顶点彼此相邻。

10、证明：设6个顶点的简单图为G,考察G中的任意一个顶点a,那么，另 外5个顶点中的任何一个顶点，要么在图G中与a邻接，要么在图G '中与a邻接。这样，就把5个结点分成两类，将会必有一类至少含有三个顶点。不妨假 设其中的3个顶点为b, c, d。该图必是图G*的子图(这里图G*可能是G或者 是G')。如果边(b,c),(c,d),(b,d)中有一条边在 G*择优3个顶点邻接。如果边 (b,c),(c,d),(b,d)都不在G*中，那么必在G*的补图(或是图G '或者是G)中，因 此，必有3个顶点邻接。5、设n阶m条边的平面图是自对偶图，证明 m=2n-2.证明；设G*图是G

11、的对偶图，所以G必为连通的平面图，且n*=r,m*=m,r*=n 于是n=n*=r，由欧拉公式可知，n-m+r=2=n-m+n 得m=2n-2&验证K5和K3,3都是极小非平面图。答：画图举例。四、应用题(每题10分，共20分)1、在自然推理系统F中，证明下面推理：每个喜欢步行的人都不喜欢骑自行车。每个人或者喜欢骑自行车或者喜 欢乘汽车。有的人不喜欢乘汽车。所以有的人不喜欢步行。(个体域为人类集合)。解：设P(x): x喜欢步行； Q(x) : x喜欢乘汽车； R(x): x喜欢骑自行 车；此题符号化为 前题：x(P(x) - n R(x), x(R(x) V Q(x) , x 门 Q

12、(x) 结论： x q P(x) x q Q(x)前提引入 x(R(x) V Q(x)前提引入任课班级：114051-4、111051-2任课教师：孙明4 门Q(c) R(c) V Q(c) x(P(x) - n R(x) P(c)- n R(c) R(c) 门P(c) x n P(x)El规那么Ul规那么 前提引入 UI规那么析取三段论拒取式EG规那么2、今有n个人，他们中的任何二人和起来认识其余的n-2个人。证明：当n?3时，这n个人能排成一列，使得中间的任何人都认识两旁的人，而两旁 的人认识左边(或右边)的人。而当 n?4时，这n个人能排成一个圆圈，使得 每个人都认识两旁的人。解：设n个人分别为Vi,V2,Va,Vn,V=,V2,Va,Vn为顶点集。假设V 与V认识，就在代表它们的顶点间连一条无向边，得边集E，于是的无向简单图G=<V,E>对于任意V,Vj V,假设V与V不相邻，那么对任意Vk V, (k<>i,k<>j ) 必与V或V相邻。否那么与条件矛盾。不妨假设，与V相邻，与V不相邻。那么Vk与V所代表的