离散数学复习题

离散数学123一、填空20%（每空2分）：1．若对命题P赋值1，Q赋值0，则命题QP的真值为。2．命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化为3．公式))(()(SQPQP的对偶公式为4．图的对偶图为5．若关系R是等价关系，则R满足性质。6．关系R的传递闭包t(R)=。7．代数系统,A是群，则它满足8．设,,,,BA和是两代数系统，f是从,,,,BA到的同态映射，则f具有性质。9．树T的边数e与点数v有关系。二、选择10%（每小题2分）：1．如果解释I使公式A为真，且使公式BA也为真，则解释I使公式B为（）。A、真；B、假；C、可满足；D、与解释I无关。2．设baA,，则P（A）×A=（）。A、A；B、P（A）；C、bAaAbbabbaaaba,,,,},{,},{,},{,},{,,,,；D、AbAabbbaabaaba,,,,}{,,}{,,}{,,}{,,,,,。3．设集合A，B是有穷集合，且nBmA,，则从A到B有（）个不同的双射函数。A、n；B、m；C、!n；D、!m。4．设K={e,a,b,c}，,K是Klein四元群，则元素a的逆元为（）。A、e；B、a；C、b；D、c。5．一个割边集与任何生成树之间（）。A、没有关系；B、割边集诱导子图是生成树；C、有一条公共边；D、至少有一条公共边。离散数学124三、逻辑推理12%：符号化命题“每个学术会的成员都是工人并且是专家，有些成员是青年人，所以有的成员是青年专家”；并用演绎方法证明上面推理。（F(x)：x是学术会成员；H(x)：x是工人；G(x)：x是专家；R(x)：x是青年人）四、8%：求集合),3,2,1(10nnxxAn的并与交。五、12%：在实数平面上，画出关系，并判定关系的特殊性质。七、10%：求图中的一棵最小生成树。八、10%：求图的邻接矩阵和可达矩阵。九、10%：证明：如果G是无向简单图且2，则G包含一条长度不小于1的基本回路。一、填空20%（每空2分）1．n个命题变元有个互不等价的极小项。2．按De-Morgan定理，ininAAAA121=。3．公式)(RQP的主析取范式为。4．设P(x)：x是大象，Q(x)：x是老鼠，R(x,y)：x比y重，则命题“大象比老鼠重”的符号化为离散数学1255．设},,{cbaX，X上的关系R的关系矩阵是111011101RM，则RRM。6．在具有n个结点的有向图中，任何基本通路的长度都不超过。7．任何图的点连通度)(G，边连通度)(G，最小点度)(G的关系为8．结点数n（3n）的简单连通平面图的边数为m，则m与n的关系为。9．群G的非空子集H是G的子群当且仅当若x,yH则。10．代数系统,,A是环，若对运算“·”还满足则,,A是整环。二、选择10%（每小题2分）1．集合},2{NnxxAn对（）运算封闭。A、加法；B、减法；C、乘法；D、yx。2．设I为整数集合，m是任意正整数，mZ是由模m的同余类组成的同余类集合，在mZ上定义运算]mod)[(][][mjiji，则代数系统mmZ,最确切的性质是（）。A、封闭的代数系统；B、半群；C、独异点；D、群。3．设,N是偏序格，其中N是自然数集合，“≤”是普通的数间“小于等于”关系，则Nba,有ba（）。A、a；B、b；C、max(a，b)；D、min(a，b)。4．连通非平凡的无向图G有一条欧拉回路当且仅当图G()。A、只有一个奇度结点；B、只有两个奇度结点；C、只有三个奇度结点；D、没有奇度结点。5．设无向图EVG,是连通的且mEnV,若（）则G是树。A、M=N+1；B、n=m+1；C、63nm；D、63mn。三、12%逻辑推理：离散数学126符号化命题“有些病人相信医生，但是没有病人相信法轮功，因此医生都不信法轮功”。用演绎法证明其结论。（P(x)：x是病人，D(x)：x是医生，Q(x)：x是法轮功练习者，L(x,y)：x相信y）四、序关系8%：设},,,,{54321xxxxxA，偏序集RA,的Hass图为求①A中最小元与最大元；②},,{543xxx的上界和上确界，下界和下确界。五、函数8%设ZYgYXf::和是映射且使得fg是满射，若g是入射，证明f是满射。六、图8%设G是连通简单平面图，结点数为n（3n），边数为m，面数为r，则42nr。七、树的应用12%设7个符号在通讯中使用的频率如下：a：35%，b：20%，c：15%，d：10%，e：10%，f：5%，g：5%编一个相应的二元前缀码，使通讯中出现的符号尽可能地减少，并画出对应的二叉树及求二叉树的过程。九、子群12%若H是G的子群，Gba,，则bHaHHab1。一、问答10%已知定义在集合},,,{dcba上的运算*如下表：试问：1）},,,,{dcba是代数系统否？（）2）},,,,{dcba是子群否？（）3）},,,,{dcba是群否？（）*abcdaabcdbbadcccdbaddcab离散数学1274）},,,,{dcba有单位元否？（）5）},,,,{dcba满足交换律否？（）二、填空10%下表中的运算均定义在实数集上，请在相应的空格中打“√”或填上具体实数（不满足或无该项者不填）+-×结合律交换律幺元（含左、右幺元）零元（含左、右零元）三、有向图的矩阵表示应用15%已知某有向图的邻接矩阵如下：00011011110001004321vvvvA试求：3v到1v的长度为4的有向路径的条数。四、图的同构15%下面两图是否同构，若是给出点集间的同构映射。v1v2v3v4离散数学128五、树的性质15%已知某树有2个2度结点、3个3度结点、4个4度结点，问有几个叶子点（无其它度数点）。六、最小生成树15%使用普里姆算法求下图的最小生成树七、自同构映射10%令},,,2{为普通加法QbabammR，定义映射g：RR为2)2(babag，试证：g是,R到,R的自同构映射。八、群与子群10%设,G是阶为6的群，证明它至多有一个阶为3的子群。一、单项选择题：（每小题1分，本大题共15分）1．设A={1，2，3，4，5}，下面（）集合等于A。A、{1，2，3，4，5，6}；B、}25{2xxx是整数且；C、}5{xxx是正整数且；D、}5{xxx是正有理数且。2．设A={{1，2，3}，{4，5}，{6，7，8}}，下列各式中（）是错的。A、A；B、{6，7，8}A；C、{{4，5}}A；D、{1，2，3}A。3．六阶群的子群的阶数可以是（）。离散数学129A、1，2，5；B、2，4；C、3，6，7；D、2，3。4．设BAS，下列各式中（）是正确的。A、domSB；B、domSA；C、ranSA；D、domSranS=S。5．设集合X，则空关系X不具备的性质是（）。A、自反性；B、反自反性；C、对称性；D、传递性。6．下列函数中，（）是入射函数。A、世界上每个人与其年龄的序偶集；B、、世界上每个人与其性别的序偶集；B、一个作者的专著与其作者的序偶集；D、每个国家与其国旗的序偶集。7．,*G是群，则对*（）。A、满足结合律、交换律；B、有单位元，可结合；C、有单位元、可交换；D、每元有逆元，有零元。8．下面（）哈斯图所描述的偏序关系构成分配格。9．下列（）中的运算符都是可交换的。A、,,；B、,；C、,,；D、,。10．设G是n个结点、m条边和r个面的连通平面图，则m等于（）。A、n+r-2；B、n-r+2；C、n-r-2；D、n+r+2。11．n个结点的无向完全图nK的边数为（）。A、)1(nn；B、2)1(nn；C、)1(nn；D、2)1(nn。12．下列图中（）是根树。A、},,,,,{},,,,{1dcbaaadcbaG；B、},,,,,{},,,,{2dcdbbadcbaG；离散数学130C、},,,,,{},,,,{3acdabadcbaG；D、},,,,,{},,,,{4ddcabadcbaG。13．设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列（）命题的真值为真。A、RQP；B、SPR；C、RQS；D、)()(SQRP。14．下面（）命题公式是重言式。A、RQP；B、)()(QPRP；C、)()(RQQP；D、))()(())((RPQPRQP。15．设L(x)：x是演员，J(x)：x是老师，A(x,y)：x钦佩y，命题“所有演员都钦佩某些老师”符号化为（）。A、)),()((yxAxLx；B、))),()(()((yxAyJyxLx；C、)),()()((yxAyJxLyx；D、)),()()((yxAyJxLyx。二、填空题：（每空1分，本大题共15分）1．设}2,121{ZxxxxM整除，被，}3,121{ZxxxxN整除，被，则NM，NM。2．在一个有n个元素的集合上，可以有种不同的关系，有种不同的函数。3．若关系R是反对称的，当且仅当关系矩阵中，在关系图上。4．设fg是一个复合函数，若g和f都是满射，则fg为，若g和f都是入射，则fg是。5．三阶群有个（不同构），其运算表为。6．设图G=V，E，},,,{4321vvvvV的邻接矩阵0001001111011010A，则1v的入度)(deg1v=，4v的出度)(deg4v=，从2v到4v的长离散数学131度为2的路有条。7．命题公式)))(((RQQPPA的主合取范式为，其编码表示为。三、判断改正题：判断下列各题是否正确，正确的划“√”，错误的划“×”，并加以改正。（每小题2分，本大题共20分）1．A，B，C为任意集合，若CABA，则B=C。（）2．设R是实数集，R上的关系},,2,{Ryxyxyxf，R是相容关系。（）3．设A，≤是偏序集，AB，则B的极大元Bb且唯一。（）4．谓词公式)()()(yyRxxQxxP的前束范式是))()()((yRzQxPyzx。（）5．在代数系统S,中，若一个元素的逆元是唯一的，其运算必是可结合的。（）6．每一个有限整环一定是域，反之也对。（）7．有割点的连通图可能是哈密尔顿图。（）8．)()())()((xxBxxAxBxAx。（）9．无多重边的图是简单图。（）10．设,,A是布尔代数，则,,A一定为有补分配格。（）四、简答题：（每小题5分，本大题共20分）1．设1R和2R是A上的任意二元关系，如果1R和2R是自反的，21RR是否也是自反的，为什么？如果1R和2R是对称的，21RR是对称的吗？2．如图给出的赋权图表示六个城市fedcba,,,,,及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小总造价。3．设S=R-{-1}（R为实数集），abbaba。离散数学132（1）说明,S是否构成群；（2）在S中解方程732x。4．将公式)()((RPRQP）划为只含有联结词，的等价公式。五、证明题：（共30分）1．设}9,,3,2,1{A，在AA上定义关系RdcbaR,,,:当且仅当cbda，证明R是AA上的等价