资源描述：
《离散数学复习题2》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、离散数学09a得分一、填空题：(每空2分，共14分)1、命题公式PvQtR的对偶式为2、对于公式Hr(P(x)vQ(x)),P(x):x二1,Q(x):x=2,当论域为{1,2}时，其公式取值为3、设个体域为A={a、b},贝ij3x(F(x)aG(x))消去量词后为。4、群的等幕元有个，是，零元有个。5.任一有向图中，度数为奇数的结点有个。得分二、单选题：(每小题2分，共10分)1、BxByP(x,y)的否定是().(A)y),(B)y),2、设I.Q.R分别是整数集合、有理数集合、实数集合，且+,则下列代数系统不能构成环的是()。(A)
2、.〈1,+,*>(B).<1,一，*>3、下列命题公式为重言式的是()(A),p-*(pVq)(B).(pVnp)fq(C)-nP(x,y),(D)3x3y—)P(x,y)一，*是数的加法，减法和乘法运算，(C).〈Q,+,*>(D).〈R,+,*>(C).qA~
3、q(D).p-*-
4、q4、设G是有n个结点m条边的连通平面图，且有k个面，则k等于()。(C)n+m-2(D)m~n+2o(A)m+n+2(B)n-m-25、在下图中()是欧拉图。得分三、计算题(共40分)1、(10分)求下面公式的主析取范式和主合取范式：(「Px/「Q)T(P㈠「①2、(
5、10分)图中给出了偏序集合〈A,R＞的哈斯图,这里A={a,b,c,d,可。(1)下列关系式哪个是真？aRb,dRa,cRe,bRe,aRa.bRc,dRe□(2)求出A的最小元素和最大元素，若不存在，则指出不存在。(3)求出A的极大元素和极小元素，若不存在，则指出不存在。(4)求出子集{b,c,d},{c,〃,£},{a,b,c}的上界和下界，并指出这些子集的上确界和下确界，若不存在，则指出不存在3.（5分）画出树叶权为：1,3,5,6,13,16,16,18的最优树，并求111此最优树的树权。4、（5分）求下图所示的有权图的最优生成树。5.（10
6、分）有向图如图所示，求（1）图的邻接矩阵A,（2）图中a到d长度为4的通路数，（3）图屮长度为4的通路总数有多少条？其中有儿条冋路?（4）写出图的可达性矩阵。并说明图的连通性。a得分四、证明题：（共20分）1、（10分）设〈H,小是群〈G,宜>的子群,G中的二元关系R定义为，R={:y-,*XGH},试证明：R是G上的等价关系。2、（10分）给定一个代数系统v/,©,®>,对于任何a,heI,有a㊉b=a+b-l^a®b=a+b-axb,证明v/,㊉>是一个含有幺元的可交换环。（”+”，”-“，”x”分别表示普通的加法，减法和乘法）得分五、
7、（10分）符号化下面的句子，并构造推理证明。如果一个人怕困难，那么他就不会获得成功，每个人或者获得成功或者失败过，有些人未曾失败过，所以有些人不怕困难。得分六、（6分）设汕二{0,1,2,3},f：N4->N4定义如下:[x+1mHo当X+1H40>,当兀+1=4令F二{f。,F,f2,f3},其中f。为叫上恒等函数。给定一代数结构〈F,答案A一、填空题：（每空2分，共14分）1、—iPa-1QvR2、1,（F（a）aG（a））v（F（b）aG（b））,4、1,单位元，0,5、偶数二、选择题：（每小题2分，共10分）1、A,2、B,3、A,4、D,5
8、、C三、计算题（共4（）分）1、（10分）解：主析取范式（-iPv-iQ）T（P㈠一iQ）二（PaQ）v（-,PaQ）v（「QaP）（5分）主合取范式（iPv-iQ）T（P㈠「Q）二PvQ（10分）2、（10分）解：（1）dRa,aRa为真,其余是假。（1分）（2）A的最小元素不存在，A的最大元素是a（3分）（3）A的极大元是a,极小元素是d和e（5分）（4）{b,c,d}的上界为a,下界为d,且其lub=a,gib二d（7分）{c,d,e}的上界为c和a,下界不存在，且其lub=c（8分）{a,b,c}的上界为a,下界为d,且其lub=a,glb=
9、do（10分）3.（5分）解：最优生成树为：（5分）3.（5分）解：此最优树的权为1*6+1*6+5*5+6*4+13*3+18*2+16*2*2二200（2分）（5分）5.（10分）解:邻接矩阵为4=01101010.10010010m3=12301230（3分）A“中第一行第四列元素为3,故G中a到d长度为4的通路数为3条。（5分）（7分）G中长度通路为4的通路总数为64条，英中主对角线元素之和为14,说明G中长度为4的回路为14。可达性矩阵为P=a+a2+a3+a4=]II11111四、证明题（共20分）1、（10分）证明：对任意xgG,由10、,*>是群vG,子群，所以x~]x=eeHeR,R是自反的;（2分）若wR,有«xgH,
