离散数学试卷及答案.doc

一、 填空 10% （每小题 2分）1、 设是由有限布尔格诱导的代数系统，S是布尔格，中所有原子的集合，则 。2、 集合S=，上的二元运算*为*那么，代数系统中的幺元是 , 的逆元是 。3、 设I是整数集合，Z3是由模3的同余类组成的同余类集，在Z3上定义+3如下：，则+3的运算表为 ；是否构成群 。4、 设G是n阶完全图，则G的边数m= 。5、 如果有一台计算机，它有一条加法指令，可计算四数的和。现有28个数需要计算和，它至少要执行 次这个加法指令。二、 选择 20% （每小题 2分）1、 在有理数集Q上定义的二元运算*，有，则Q中满足（ ）。A所有元素都有逆元； B、只有唯一逆元；C、时有逆元； D、所有元素都无逆元。2、设S=0，1，*为普通乘法，则是（ ）。A半群，但不是独异点； B、只是独异点，但不是群；C、群； D、环，但不是群。3、图 给出一个格L，则L是（ ）。A、分配格； B、有补格； C、布尔格； D、 A,B,C都不对。2、 有向图D= ，则长度为2的通路有（ ）条。A、0； B、1； C、2； D、3 。3、 在Peterson图中，至少填加（ ）条边才能构成Euler图。A、1； B、2； C、4； D、5 。三、 判断 10% （每小题 2分）1、 在代数系统中如果元素的左逆元存在，则它一定唯一且。（ ）2、 设是群的子群，则中幺元e是中幺元。（ ）3、 设， +,为普通加法和乘法，则代数系统是域。（ ）4、 设G=是平面图，|V|=v, |E|=e，r为其面数，则v-e + r=2。（ ）5、 如果一个有向图D是欧拉图，则D是强连通图。（ ）四、证明 46%1、 设，是半群，e是左幺元且，使得，则是群。（10分）2、 循环群的任何非平凡子群也是循环群。（10分）3、 设aH和bH是子群H在群G中的两个左陪集，证明：要末，要末 。（8分）4、 设，是一个含幺环，|A|3，且对任意，都有，则不可能是整环（这时称是布尔环）。（8分）5、 若图G不连通，则G的补图是连通的。（10分）五、布尔表达式 8%设是布尔代数上的一个布尔表达式，试写出其的析取范式和合取范式。六、图的应用 16%1、 构造一个结点v与边数e奇偶性相反的欧拉图。（6分）2、 假设英文字母，a，e，h，n，p，r，w，y出现的频率分别为12%，8%，15%，7%，6%，10%，5%，10%，求传输它们的最佳前缀码，并给出happy new year的编码信息。（10分）一、填空 10%（每小题2分）+30120012112022011、；2、，；3、 是；4、；5、9一、 选择 10%（每小题 2分）题目12345答案CBDBD二、 判断 10%（每小题2分）题目12345答案NYYNY三、 证明 46%1、（10分）证明：（1）(2) e 是之幺元。事实上：由于e是左幺元，现证e是右幺元。（3）由（2），（3）知：为群。2、（10分）证明：设是循环群,G=(a)，设是的子群。且，则存在最小正整数m，使得：，对任意，必有，故： 即：所以 但m是使的最小正整数，且，所以r=0即：这说明S中任意元素是的乘幂。 所以是以为生成元的循环群。3、（8分）证明：对集合，只有下列两种情况：（1） ； （2）对于，则至少存在，使得，即有，这时任意，有，故有同理可证：所以 4、（8分）证明：反证法：如果，是整环，且有三个以上元素，则存在即有： 这与整环中无零因子条件矛盾。因此不可能是整环。5、（10分）证明：因为G=不连通，设其连通分支是，则有两种情况：（1） u , v，分别属于两个不同结点子集Vi，Vj，由于G(Vi) , G(Vj)是两连通分支，故(u , v)在不G中，故u , v 在中连通。（2） u ,v ，属于同一个结点子集Vi，可在另一结点子集Vj中任取一点w，故(u , w),(w , v )均在中，故邻接边( u ,w ) ( w , v ) 组成的路连接结点u和v，即u , v在中也是连通的。五、布尔表达式 8%函数表为：00000011010001111000101111011111析取范式：合取范式：六、 树的应用 16%1、（6分）解：2、（10分）解：根据权数构造最优二叉树：传输它们的最佳前缀码如上图所示，happy new year的编码信息为：10 011 0101 0101 001 110 111 0100 001 111 011 000 附：最优二叉树求解过程如下：一、单项选择题(本大题共15小题，每小题1分，共15分)1.设P：天下大雨,Q：他在室内运动,命题“除非天下大雨，否则他不在室内运动”可符合化为（）A.PQB.PQC.PQD.PQ2.下列命题联结词集合中，是最小联结词组的是（）A.， B.，C.，D.，3.下列命题为假命题的是（）A.如果2是偶数，那么一个公式的析取范式惟一B.如果2是偶数，那么一个公式的析取范式不惟一C.如果2是奇数，那么一个公式的析取范式惟一D.如果2是奇数，那么一个公式的析取范式不惟一4.谓词公式x(P(x)$yR(y)Q(x)中变元x是（）A.自由变元B.约束变元C.既不是自由变元也不是约束变元D.既是自由变元也是约束变元5.若个体域为整数减，下列公式中值为真的是（）A.x$y(x+y=0) B.$yx(x+y=0)C.xy(x+y=0) D.$x$y(x+y=0)6.下列命题中不正确的是（）A.xx-xB.xx-xC.A=xx,则xA且xAD.A-B=A=B7.设P=x|(x+1)24，Q=x|x2+165x,则下列选项正确的是（）A.PQB.PQC.QPD.Q=P8.下列表达式中不成立的是（）A.A(BC)=(AB) (AC) B.A(BC)=(AB) (AC)C.(AB)C=(AC) (BC) D.(A-B) C=(AC)-(BC)9.半群、群及独异点的关系是（）A.群独异点半群B.独异点半群群C.独异点群半群D.半群群独异点10.下列集合对所给的二元运算封闭的是（）A.正整数集上的减法运算B.在正实数的集R+上规定*为a*b=ab-a-b a,bR+C.正整数集Z+上的二元运算*为x*y=min(x,y) x,yZ+D.全体nn实可逆矩阵集合Rnn上的矩阵加法11.设集合A=1，2，3，下列关系R中不是等价关系的是（）A.R=,B.R=,C.R=,D.R=,12.下列函数中为双射的是（）A.f：ZZ,f(j)=j(mod)B.f：NN,f(j)=C.f：ZN,f(j)=|2j|+1D.f：RR,f(r)=2r-1513.设集合A=a,b, c上的关系如下，具有传递性的是（）A.R=,B.R=,C.R=,D.R=14.含有5个结点，3条边的不同构的简单图有（）A.2个B.3个C.4个D.5个15.设D的结点数大于1，D=是强连通图，当且仅当（）A.D中至少有一条通路B.D中至少有一条回路C.D中有通过每个结点至少一次的通路D.D中有通过每个结点至少一次的回路二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上正确答案。错填、不填均无分。16.设A=1,2,3，B=3,4,5，则AA=_，AB=_。17.设A=1,2,3,4,5，RAA，R=，,，则R的自反闭包r(R)=_。对称闭包t(R)=_。18.设P、Q为两个命题，德摩根律可表示为_，吸收律可表示为_。19.对于公式x(P(x)Q(x)，其中P(x)x=1,Q(x)x=2,当论域为1,2时，其真值为_ ,当论域为0,1,2时，其真值为_。20.设fRR,f(x)=x+3,gRR,g(x)=2x+1,则复合函数,。21.3个结点可构成_个不同构的简单无向图，可构成_个不同构的简单有向图。22.无向图G=如左所示，则G的最大度(G)=_，G的最小度(G)=_。23.设图G,V=v1,v2,v3,v4,若G的邻接矩阵，则deg-(v1)=_ _,deg+(v4)=_。24.格L是分配格，当且仅当L既不含有与_同构的子格，也不含有与_同格的子格。25.给定集合A=1,2,3,4,5，在集合A上定义两种关系：R=,S=,，则，。三、计算题（本大题共5小题，第26、27题各5分，第28、29题各6分，第30题8分，共30分）26.设A=a,b,c,d，A上的等价关系R=,IA，画出R的关系图，并求出A中各元素的等价类。27.构造命题公式（PQ） （PQ）的真值表。28.求下列公式的主析取范式和主合取范式：P（QP）（PQ）29.设A=a, b, c, d, e，R为A上的关系，R=，, , , IA，试画的哈斯图，并求A中的最大元，最小元，极大元，极小元。30.给定图G如图所示，（1）G中长度为4的路有几条？其中有几条回路？（2）写出G的可达矩阵。四、证明题（本大题共3小题，第31、32题各6分，第33题8分，共20分）31.设（L，）是格，试证明：a, b, c L, 有a（bc）（ab）（ac）；a（bc）（ab）（ac）。32.设R是A上的自反和传递关系，如下定义A上的关系T，使得x, yA，TR(y, x)R。证明T是A上的等价关系。33.设有G=, V的结点数|V|=n，称该图为n阶图，若从结点vi到vj存在路，证明从vi到vj必存在长度小于等于n-1的一条路。五、应用题（本大题共2小题，第34题7分，第35题8分，共15分）34.构造下面推理的证明。每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不喜欢步行。35.今要将6人分成3组（每组2个人）去完成3项任务。已知每个人至少与其余5个人中的3个人能相互合作。（1）能否使得每组的2个人都能相互合作？（2）你能给出几种不同的分组方案？2008年4月全国自考离散数学参考答案一填空题（每小题2分，共10分）1. 谓词公式的前束范式是_ xyP(x)Q(y) _。2. 设全集则AB =_2_，_4,5_，_ 1,3,4,5 _3. 设，则_ c,a,c,b,c,a,b,c _，_。4. 在代数系统（N，+）中，其单位元是0，仅有 _1_ 有逆元。5如果连通平面图G有个顶点，条边，则G有_e+2-n_个面。二选择题（每小题2分，共10分）1. 与命题公式等价的公式是（ ）（A） （B） （C） （D）2. 设集合,A上的二元关系不具备关系( )性质（A） (A)传递性 (B)反对称性 (C)对称性 (D)自反性3. 在图中,结点总度数与边数的关系是( )(A) (B) (C)(D) 4. 设D是有n个结点的有向完全图,则图D的边数为( )(A) (B) (C) (D)5. 无向图G是欧拉图,当且仅当( )(A) G的所有结点的度数都是偶数 (B)G的所有结点的度数都是奇数(C)G连通且所有结点的度数都是偶数 (D) G连通且G的所有结点度数都是奇数。三计算题（共43分）1. 求命题公式的主合取范式与主析取范式。（6分）解：主合取方式：pqr(pqr)(pqr)(pqr)= 0.2.4主析取范式：pqr(pqr) (pqr) (pqr) (pqr) (pqr)= 1.3.5.6.72. 设集合上的二元关系R的关系矩阵为,求的关系矩阵，并画出R，的关系图。（10分）3 无向图G有12条边，G中有6个3度结点，其余结点的度数均小于3，问G中至少有多少个结点？（10分）解：G（V,E），| E |=V，d（Vi）3,设至少有x个节点，由握手定理得：212=d（Vi）63+(x-6)328故G中至少有9个节点。4 求下面两个图的最小生成树。（12分）5. 试判断是否为格？说明理由。（5分）解：（Z,）是格，理由如下：对于任意aZ，aa成立，满足自反性；对于任意aZ，bZ，若ab且ba，则a=b，满足反对称性；对于任意a，b，cZ，若ab，bc，则ac，满足传递性；而对于任意a，bZ，ab，b为最小上界，a为最大下界，故（Z，）是格。（注：什么是格？）四证明题（共37分）1. 用推理规则证明。（10分）证明： 编号公式依据（1）（BC）C前提（2）BC，C（1）（3）B（2）（4）AB（3）（5）A（3）（4）（6）（AD）前提（7）AD（6）（8）D（5）（6）2. 设R是实数集，。求证：都是满射，但不是单射。（10分）证明：要证f是满射，即yR,都存在（x1，x2）RR，使f（x1，x2）=y，而f（x1，x2）=x1+x2，可取x1=0，x2=y，即证得；再证g是满射，即yR，,都存在（x1，x2）RR，使g（x1，x2）=y，而g（x1，x2）=x1x2，可取x1=1，x2=y，即证得；最后证f不是单射，f（x1，x2）=f（x2，x