您好,欢迎访问三七文档
北航10秋学期《离散数学》模拟题一一、单项选择题(本大题共15小题,每小题2分,共30分)1.∑中所有有限长度的串形成的集合记为∑*,容易证得∑*上的连接运算不满足交换律,但满足(A)A.结合律B.分配律C.幂等律D.吸收律2.Klein群中元素a,b,c的阶为(B)。A.1B.2C.3D.43.群G的元素x的所有幂的集合为G的子群,称由x生成的子群。记为(A).A.xB.(x)C.xD.[x]4.交换环是指乘法满足(A)。A.交换律B.结合律C.分配律D.吸收律5.至少有(B)元素的含单位元、无零因子环称为除环。A.一B.二C.三D.四6.∨,∧满足(C)的格称为分配格A.交换律B.结合律C.分配律D.幂等律7.若L为有限布尔代数,则(B)正整数n,L与含有n个元素的集合A的幂集同构。A.不存在B.存在C.有可能存在8.有向图D的顶点v作为边的始点的次数之和称为v的出度,记为d+(v),v作为边的终点的次数之和称为v的入度,记为d-(v),v的度数d(v)=(A)。A.d+(v)+d-(v)B.d+(v)C.d-(v)D.d+(v)*d-(v)9.若通路Г=v0e1v1e2…e1v1中所有顶点互不相同(所有边自然互不相同)时称为(B)A.初级回路B.路径C.复杂通路D.迹10.在n阶图中,若一顶点存在到自身的回路,则必存在从该顶点到自身的长度不超过(B)的回路。A.n-1B.nC.n+1D.2n11.“人总是要死的”谓词公式表示为(C)。(论域为全总个体域)M(x):x是人;Mortal(x):x是要死的。A.)()(xMortalxM;B.)()(xMortalxMC.))()((xMortalxMx;D.))()((xMortalxMx12.公式))()((xQxPxA的解释I为:个体域D={2},P(x):x3,Q(x):x=4则A的真值为(A)。A.1;B.0;C.可满足式;D.无法判定。13.下列等价关系正确的是(B)。A.)()())()((xxQxxPxQxPx;B.)()())()((xxQxxPxQxPx;C.QxxPQxPx)())((;D.QxxPQxPx)())((。14.下列偏序集(C)能构成格。15.设}4,41,3,31,2,21,1{s,*为普通乘法,则[S,*]是(D)。A.代数系统;B.半群;C.群;D.都不是。参考答案:1-5ABAAB6-10CBABB11-15CABCD二、填空题(本大题共4题,16题2分,其它每空3分,共20分)16、设格中表达式E=(a⊕b)×(c⊕d),则E的对偶表达式E*=_______________。考核知识点:格的对偶表达式,参见教材P144参考答案:(a×b)⊕(c×d)17、设集合A={a,b,c,d,e},A上半序关系R的哈斯图如下图所示,则A的极大元为__________,极小元为__________。考核知识点:半序关系的极值,参见教材P93参考答案:ac,d18、由集合运算的基本定律:(1)A∩A=A,满足__________律;(2)A∪E=E,满足__________律;(3)A∩E=A,满足__________律;(4)A∩~A=φ,满足__________律。考核知识点:集合的运算律,参见教材P65-67参考答案:等幂律零一律同一律互补律三、问答题(本大题共3小题,每小题10分,共30分)19.求命题公式RPRQPPRQ)())((的真值.考核知识点:命题公式的真值表,参见教材P5参考答案:RPRQPPRQ)())((RPRQPPRQ)()(RPQQRP)(120、设集合A={0,1,2,3,4,5,6}上的偏序关系R如下:R={0,1,0,2,0,3,0,4,0,5,0,6,4,6,2,5,3,5}IA做偏序集A,R的哈斯图,并求B={0,2,3}的极大元、极小元、最大元和最小元。考核知识点:偏序关系的极值,参见教材P93参考答案:A={0,1,2,3,4,5,6},B={0,2,3},哈斯图如右图.B的极大元:2,3,B的极小元:0B的最大元:无B的最小元:021、解释N如下:个体域DN为全体自然数的集合DN中特定元素a=0DN上函数yxyxgyxyxf),(,),(D上谓词),(yxF为yx在解释N下,判断公式的真假:(1)个体域为自然数集合DN;(2)DN上特定函数yxyxgyxyxf),(,),(。考核知识点:前束范式,参见教材P48参考答案:(1)在解释N下,,00),(xaxg,0),,(xxaxgF公式xaxgxF),,(成为具体命题:“任自然数等于0”。显然为假命题。(2)在解释N下,zyxfzFyx),,(成为zyxzyx,即“任二自然数的和仍为自然数”。显然为真命题。四、证明题(本题共2小题,每小题10分,共计20分)22.证明如果非空集合A上的二元关系R和S是偏序关系,则SR也是A上的偏序关系。考核知识点:偏序关系的判定,参见教材P91参考答案:①SRxxSxxRxxAx,,,,,,所以SR有自反性;②,,Ayx因为R,S是反对称的,yxxyyxSxySyxRxyRyxSxyRxySyxRyxSRxySRyx),,(),,(),,(),,(,,所以,RS有反对称性.③Azyx,,,因为R,S是传递的,SRzySRyx,,SzyRzySyxRyx,,,,SzySyxRzyRyx,,,,SRzxSzxRzx,,,所以,SR有传递性。总之,R是偏序关系。23.设A,B,C为三个集合,证明若CA.则(AB)CA(BC)考核知识点:集合的运算参见P65参考答案:CxBAxCBAx)(CxBxAx)()()(CxBxCxAx)()(CBAxCBxAx即)()(CBACBA北航10秋学期《离散数学》模拟题二一、单项选择题(本大题共15小题,每小题2分,共30分)1.设集合A={1,2,3},A上的关系R={(1,1),(2,2)},则R不具有关系的(A)性质。A.自反性B.对称性C.传递性D.反对称性2.设集合A={a,b,c},A上关系R的关系图如下图所示,则R具有(B)。A.自反性、对称性、传递性B.自反性、传递性C.对称性、反对称性D.对称性、反对称性、传递性3.设命题公式G=(PQ),H=P(QP),则G与H的关系是(A)。A.B.C.G=HD.以上都不是4.下面给出的一阶逻辑等价式中,(B)是错的。A.x(A(x)∨B(x))=xA(x)∨xB(x)B.x(A(x)∨B(x))=xA(x)∨xB(x)C.xA(x)=x(A(x))D.AxB(x)=x(AB(x))5.如下图所示,半序集中哪个不是格?(B)6.设(B,·,+,-,0,1)是布尔代数,a,b是B中元素,a≤b,则下面(C)公式不成立。HGGHA.a·=0B.+b=1C.a+=1D.+=7.下图是(C)。A.完全图B.平面图C.哈密顿图D.欧拉图8.已知图G的相邻矩阵为,则G的边数与分枝数为(B)A.5,3B.4,2C.5,1D.6,49.若干能等值地表示出全部(合式)公式(真值函数)的逻辑联结词集合称为(A)A.全功能集B.功能集C.全功能联结词集合D.特殊联结词集合10.下列不是极小全功能集的是(D)A{┐,∨}B.{┐,∧}C.{┐,→}D.{∨,→}11.设}}2,1{},1{,{S,则S2有(D)个元素。A.3;B.6;C.7;D.8。12.设}3,2,1{S,定义SS上的等价关系},,,,|,,,{cbdaSSdcSSbadcbaR则由R产生的SS上一个划分共有(B)个分块。A.4;B.5;C.6;D.9。13.设}3,2,1{S,S上关系R的关系图为,则R具有(D)性质。A.自反性、对称性、传递性;B.反自反性、反对称性;C.反自反性、反对称性、传递性;D.自反性。14.设,为普通加法和乘法,则(A),,S是域。A.},,3|{QbabaxxSB.},,2|{ZbanxxSC.},12|{ZnnxxSD.}0|{xZxxS=N。bababa010101001000001110000010015.下面偏序集(B)能构成格。参考答案:1-5ABABB6-10CCBAD11-15DBDAB二、填空题(本题共5小题,每题4分,共20分)16、已知}}a{,{=A,那么2A=________________。考核知识点:幂集参见P65参考答案:{,{},{{a}},{,{a}}}17、设{(0,0)、(0,2),(2,0),(3,2)}则的定义域为____________,值域为___________。考核知识点:函数的域参见P93参考答案:{023}D,,{0,2}R18、已知#,#AnBm(nm)问存在___________个不同的A到B上的内射。考核知识点:映射参见P97参考答案:(1).....(1)nmAmmmn19、整数集上的四则运算中不能保证封闭性的是_________________。考核知识点:整数集合运算的封闭性参见P66参考答案:减法和除法20、写出群中生成元的定义_____________________________________。考核知识点:群的生成元参见P131参考答案:g为生成元,则任给群中的一元素a,那么存在整数K,使得Kag三、问答题(本题共3小题,每小题10分,共计30分)21、一棵树有1个结点度数为5,2个结点度数为4,5个结点度数为2,14个结点度数为1,问度数为3的结点有几个?考核知识点:树的结点,参见P177参考答案:设T是(n,m)图,度为3的结点数为x,则n=1+2+5+14+x=22+x由握手定理2m=1deg()1524521413niiVx5810143373xx2(221)373xx42375x答:有5个度数为3的结点。22.设σ,τ,φ是实数集合R上的三个映射,其中,σ(x)=x/5,τ(x)=2x+3,φ(x)=x2+1对x∈R,试求复合映射σ·τ,τ·σ,τ·τ,τ·φ和σ·φ·τ,并指出这些映射中哪些是双射?考核知识点:映射,参见P97参考答案:σ·τ(x)=(2x+3)/5;τ·σ(x)=2x/5+3;τ·τ(x)=4x+9;τ·φ(x)=2x2+5;σ·φ·τ(x)=(4x2+12x+10)/5其中σ·τ,τ·σ,τ·τ是双射。23、F=)P∧)Q∨P¬((¬∨Q是什么类型的公式?说明理由。考核知识点:重言式参见P8参考答案:(())(()())QPQPQPPQP()11QQPQQPP所以为重言式。24.设(L,≤)是一个分配格,x,y是格中任意元素,如果对格中某个元素a,有a×x=a×y,a⊕x=a⊕y,则x=y。考核知识点:分配格,参见P148参考答案:.x=x⊕(x×a)=(x⊕x)×(x⊕a)=x×(a⊕y)=(x×a)⊕(x×y)=(a×y)⊕(x×y)=(a⊕x)×y=(a⊕y)×y=y北航10春学期《离散数学》考试模拟题一一、单项选择题(本大题共15小题,每小题2分,共30分)1、设G是有6
本文标题:《离散数学》模拟题
链接地址:https://www.777doc.com/doc-2800728 .html