远程离散数学题库答(08秋格式)北大

本试卷共3页，第1页北京大学现代远程教育2008年秋季学期期末考试试卷A1.T为无向连通图G(m,n)的一棵生成树，则对应T的基本回路数为（m-n+1）[是]2、每条边都是桥的无向连通图必是树。[是]3、非平凡无向树T至少1片树叶[非]4、11阶无向连通图G中有17条边，其任一棵生成树T中必有6条树枝[非]5、无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有8个顶点.[是]6、二元正则树有奇数个顶点。[对]7、n（n≥1）阶有向完全图都是有向欧拉图。[对]8、无向连通图G（m,n）的每一条边都可以成为他的某一生成树的树枝。[x]9、边数m等于n-1的n阶无向图都是树。[x]10、10阶无向连通图G有m条边，则生成树T对应的基本割集数目为9［］11．树Ｔ有ｍ条边，ｎ个顶点，则有ｎ＝ｍ＋１［是］12．（１，２，３，４，５，６）可以是一个图的顶点度数列［非］13．作为有向图中有向边始点的次数叫出度。[是]14．10阶无向简单图G中有6个奇数度顶点，其补图中必有４个奇数度顶点[是]15．10、11阶无向简单连通图G中，顶点间的最大距离是11[x]11、11条边的图G中，所有顶点的度数之和为22[]12、11阶无向简单图G中有6个奇数度顶点，其补图中必有5个奇数度顶点[x]13、图Ｇ中２个３度顶点，３个４度顶点，４个５度顶点，则Ｇ中有１８条边．[]14、10阶无向连通图G有m条边，则生成树T对应的基本割集数目为9。［］15.边数m等于n-1的n阶无向图都是树。[X]16.无向树的任何边都是桥。[]17.无向连通图G（n，m）的每一棵生成树都有n-1条树枝。[]18、无向连通图G（n，m）的每一条边都可以成为他的某一生成树的树枝。[X]19、一棵树中有i个顶点的度数为i（i=2，…k），其余顶点都是树叶。当k=4时，问树叶多少片？（10分）三、填空题.(每题2分，共16分）1、个体域是人类，则命题”人固有一死”应符号化为(xF（x）)。2、命题应为能判断对错的(陈述)句。本试卷共3页，第2页3、令p：天下雨；q：乘汽车。命题’’如果天下雨，则乘汽车’’符号化为(ｐ→ｑ)4、任一个命题公式至少(1)个主析取范式.5、命题”明天不下雨，也没有太阳，将是阴天。”应符号化为(┐p∧┐q∧r).6、命题公式p的主合取范式为(∏(0))7、命题公式p∧┐q∧r的主析取范式为(∑(5))8、个体域为自然数集合,则x+y=y+x(是)命题。１３．令F（x）：x是兔子；G（y）：y是乌龟；H（x，y）：x比y跑得快。将命题“所有兔子不比某些乌龟跑得快”符号化为：（x（F（x）→﹃彐y（G（y）∧H（x，y））））14、设个体域是自然数集合，p代表xy彐zF（x－y=z），则p(是假)命题。15、令p代表一阶逻辑公式G（x）与G（y）等值，则p（是假）命题。1６．命题公式（﹁ｐ∧ｐ）→ｑ的类型是（永真式）．17．任何图中，度数为奇数的顶点个数为（偶数）18．在命题逻辑中，任何命题公式都(有唯一的一个)主合取范式.19．设域为正整数集合，命题x彐y（x＞y）的真值为（０）20令p：经一堑；q：长一智。命题’’只有经一堑，才能长一智’’符号化为[B]A．p→q；B．q→p；C．p∧q；D．﹁q→﹁p21.p：天气好；q：我们去游玩．将命题＂除非天气好，否则我们不去游玩＂符号化为［Ｂ］A．p→q；B．q→p；C．p∧q；D．﹁q→﹁p22.命题公式ｐ→(ｐ∧ｑ)为假的赋值是ｐ,ｑ分别为（（１，０））23、明天不下雨，也没有太阳，将是阴天。┐p∧┐q∧r。24、人固有一死。x（F（x）→G（x））。25、有的汽车不见得比所有的火车跑得慢。x(F(x))y(G(y)﹁L（x,y）））。26、x+3y=3y+x。符号化为：P或xy(F(f(x,y),g(x,y))。本试卷共3页，第3页27、即使张三和李四考分相等，也只有一人被我校录取。P∧（（q∧┐r）∨（┐q∧r））。28.任何命题公式都有唯一的主析取范式和唯一的主合取范式[是]29.任何命题公式都有唯一的与其等值的析取范式和唯一的与其等值的合取范式[非]30.任何命题公式都有唯一的与其等值的析取范式和唯一的与其等值的合取范式[非]31.任何命题公式都有唯一的与其等值的析取范式[非]32.任何命题公式都有唯一的与其等值的合取范式[非]33.公式A有n个命题变元,其主析取范式中有k个极小项,m个极大项,则m+k=2n[是]34.有n个命题变元的永真式,其主析取范式中有k=2n极小项,则极大项数m=0[是]35.有n个命题变元的永假式,其主析取范式中有k=0个极小项,则极大项数m=2n[是]36.有n个命题变元的可满足式,其主析取范式中有k个极小项,m个极大项,则0k2n且0m2n[是]37.公式﹃(q→p)∧p的类型是永假式[是]38.命题”这台机器不能用”应符号化为(﹃F（a）或﹃P)四、设S={1，2，3}，S上的关系R如下：R={〈x，y〉︱x能被y整除}，试完成下列要求（每要求3分，共12分）1、给出R的所有元素。R={〈2，1〉〈3，1〉}∪IS。2、给出ranR的表达式。ranR={1，2，3}3、指出R的性质。自反，反对称，传递。4、给出domR的表达式。domR={1，2，3}。2、设A={-2，-1，0，1，2}，R={〈x，y〉︱︱x︱=︱y︱}是集合A上的二元关系，试求：（1）R的表达式。={〈-2，2〉，〈-1，1〉，〈2，-2〉，〈1，-1〉}∪IA-2。。-1（2）R的关系图。0。。1。2（3）R的性质。自反，对称，传递。３．设集合Ａ＝｛ａ，ｂ，ｃ，ｄ，ｅ｝，｛｛ａ，ｃ，ｄ｝，｛ｂ，ｅ｝｝是Ａ上的一个划分．求（１）给出有确定的等价关系Ｒ＝｛＜ａ，ｃ＞＜ｃ，ａ＞＜ｃ，ｄ＞＜ｄ，ｃ＞＜ｄ，ａ＞＜ａ，ｄ＞＜ｂ，ｅ＞＜ｅ，ｂ＞｝∪IA．（２）给出Ｒ的图示．（３）给出Ａ的元素的自然映射ｇ（ｘ）：ｇ（ａ）＝ｇ（ｃ）＝ｇ（ｄ）＝｛ａ，ｃ，ｄ｝；ｇ（ｂ）＝ｇ（ｅ）＝｛ｂ，ｅ｝本试卷共3页，第4页4.设S={2，4，6，8}，S上的关系R如下，完成诸项要求。（分）。R={〈2，2〉，〈2，8〉，〈4，2〉，〈6，8〉，〈8，2〉}。1、domR={2,4,6,8}2、ranR={2,8}3、说明R的性质。4、求复合R。R的表达式。5.若关系R具有对称性，则复合R。R也具有对称性。∵对称性，∴R=R-1，对复合（R。R）求逆，有（R。R）-1=R-1。R-1=RR，得证。6.集合S={-3，-1，0，1，3}，R是X上的二元关系，根据Ri（z）如下的谓语表达式，对于所有x，y∈X，分别列出Ri（z），i=1，2，3的元素z。1、R1={〈x，y〉x，y∈S∧x＜y}。=2、R2={〈x，y〉x，y∈S∧y-1＜x＜y+2}。=3、R3={〈x，y〉x，y∈S∧x2≤y}。=1、R1={〈x，y〉x，y∈S∧x＜y}。={-3,-1,-3,0,-3,1,-3,3,-1,0,-1,1,-1,3,0,1,0,3,1,3}。2、R2={〈x，y〉x，y∈X∧y-1＜x＜y+2}。={-3,-1,-3,1,-1,1,0,-1,1,0,1,3}。3、R3={〈x，y〉x，y∈X∧x2≤y}。={-1,1,0,0,1,1}。五、1.设Z为整数集合，在Z上定义二元运算。，对于所有x，y∈Z都有x。y=x+y-6，试问〈Z，。〉能否构成群，为什麽？（分）答：二元运算满足结合律，半群；有幺元6，独异点；每个元素都有逆，群。2.设Z为整数集合，在Z上定义二元运算*，对于所有x，y∈Z都有x*y=x+y；试问〈Z，*〉能否构成群，为什麽？（分）答：二元运算满足结合律，半群；有幺元0，独异点；每个元素都有逆，群。3.设A={0，1}，〈A，*〉中的二元运算*表如下右。回答下列问题，并说明为什么。本试卷共3页，第5页1、〈A，*〉能否构成代数系统？（5分）1、因为封闭性，所以能构成代数系统。2、〈A，*〉为何种代数系统？（10分）2、满足结合律，是半群；有单元0，所以是单元半群。六、奥运年欢送外国朋友时,在网上传输GOODBYE的最佳前缀码,共用多少位二进制码。(12分).1、最优二元树T；2.18位；3、每个字母的码字；每个字母出现频率分别为：G、D、B、E、Y：14%，O：28%；(也可以不归一,某符号出现次数即为权).。100（近似）42。。5628。。28。。28。。14。。14141414所以，得到编码如下：G（000），D（001），B（100），E（101），Y（01），O（11）。2、8个字母在通讯中出现的频率分别是A=30%；B=20%；C=15%；D=11%；E=9%；F=6%；G=5%；H=4%；以此百分数为权重，求：（共15分）。100（1）最优二元树T：60。30．。30。4015．。C20。。209．。FE。。DH．。G（2）T的权W（T）=274（3）每个字母的编码：A（01），B（11），C（001），D（101），E（100），F（0001），G（00001），H（00000）。3、奥运会到了,给外国友人发电子邮件”福娃”--Friendlies的最佳前缀码共用二进制码多少位?(12分)1、最优二元树T；2.30位；3、每个字母的码字；F--000,r--001,i--01,n--1000,d--1001,e--101,l--110,s--111.*二元运算表*01001111本试卷共3页，第6页七、用构造证明法证明下面推理的正确性（12分）1.如果天下雨,则不上体育课.天下雨了.所以我们不上体育课.前提：P→﹁q,p;结论：﹁q.推理正确。2.用附加前提法证明下面的推理：前提：P，q∨﹁r，q→（p→s）。结论：r→s推理正确。3.若他学计算机专业，他必定学好离散数学。若他不是学英语的，他必是学计算机的。他没有学好离散数学。所以，他是学英语的。4.凡大熊猫都产在中国。欢欢是只大熊猫。所以，欢欢产在中国。一、集合关系1），∈，，，；Ø，。2)∪，∩，－，～，⊕。3)，∈，，，Ø，。∪，∩，－，～，⊕,≠,│.二、逻辑学符号1、xF（x）→（x彐yG（x，y）→xF（x））。2、（（彐xF（x）∨彐yG（y））∧﹃彐yG（y））→彐xF（x）。三.功能完备集合:{﹁,∧,∨,→,←→}