离散数学复习题5_免费下载

《离散数学复习题5_免费下载》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、08B得分一、单项选择题(每小题2分，共10分)1.下列命题公式等值的是()2.设全体域D是正整数集合，确定下列命题的真值为真的命题是：（)(A)"x$y(xy=y)　　　　(B)$x"y(x+y=y)　　(C)$x"y(x+y=x)　　　(D)"x$y(y=2x)　　3.设集合A＝{0,b},B={1,b,3},则AÈB上的恒等关系是().(A){<0,0>,<1,1>,<3,3>}(B){<0,0>,<1,1>,,<3,3>}(C){<1,1>,,<3,3>}(D){<0,1>,<1,b>,<3,0>}4.已知集合A＝{a,b,

2、c}上的二元关系R的关系矩阵MR＝，那么R＝()，(A){,,,}(B){,,,}(C){,,,}(D){,,,}5.命题公式是（）(A)．矛盾式(B).可满足式(C).重言式(D).等值式得分二、填空题(每小题2分，共10分)1.设命题公式G：P®Ø(Q®P)，则使公式G为假的真值指派是。2..设Ａ＝｛1,2,3,4,5,6｝，B={2,3,4}，从Ａ到B的关系Ｒ＝｛〈x,y〉

3、x=y2｝，则R-1=3

4、.设个体域D＝{1,2},那么谓词公式消去量词后的等值式为。4.设有向图D＝的邻接矩阵为A(D)=，那么½E½＝。5.代数系统是一个群，则G的等幂元是。得分三、计算题(40分)1.(10分)求命题公式的主合取范式、主析取范式。2.(5分)求下面有权图的最优生成树。3．(5分)设代数系统，其中Z是整数集，二元运算定义为，"，求(1)的单位元（2）a的逆元（3）判断“*”是否可结合4.(10分)设集合A={1,2,3,4}，上的二元关系分别为：R={<1,1>,<1,2>,<2,4>,<3,1>,<3,3>},S={<1,3>

5、,<2,2>,<4,4>,<3,2>,},试用定义求，，，，,，并画出其关系图。5．(10分)写出图4-3的邻接矩阵并求从b到d长度为3和从a到c长度为4的通路条数。图4-3得分四．证明题(每小题10分，共20分)1.（10分）设R是集合A上的对称关系和传递关系，试证明：若对"aÎA,$bÎA，使得ÎR,则R是等价关系.2.（10分）在群中，（1）如果对任意元素有，则是阿贝尔群。（2）如果对任何元素，有，则是一个阿贝尔群。得分五、（10分）用CP规则证明：。得分六、（10分）设为群,a为G中给定元素。定义函

6、数f：G→G，使得对每一xÎG有f(x)=a*x*a-1证明：f是到的自同构。答案一、单项选择题(每小题3分，共15分)1.C2.A3.B4.D5.A二、填空题(每小题3分，共15分)1.(1,0)；(1,1);2.<2,4>3.A(1)ÚA(2)Ú(B(1)ÙB(2));4.6;5.单位元.三、计算题(40分)1.(10分)解：此为主合取范式、主析取范式：2.(5分)解：3.(5分)解：易知，二元运算满足交换律.∵对"aÎZ,a*2=a+2－2＝a＝2*a，即2ÎZ是单位元.(2分)"aÎZ,a的逆元记作a－1,有(单位元)a－1=4－a

7、(5分)4.(10分)解：={}={}={}={}={}（4分）其关系图如下图所示。（每图1分）4123R-S213S-R2431123434212341（10分）5.(10分)A(D)=A2(D)=A3(D)=A4(D)=(4分)从矩阵A2(D)可知，从b到d长度为3的通路有1条.(7分)从矩阵A4(D)a到c长度为4的通路有16条.(10分)四、证明题(每小题10分，共20分)1.证明：已知R是对称关系和传递关系，只需证明R是自反关系.(3分)"aÎA,$bÎA，使得ÎR，因为R是对称的，故ÎR;(6分)又R是传递的，ÎR，

8、,a>ÎRÞÎR,由元素a的任意性，知R是自反的.(9分)所以，R是等价关系.2．证明：（1）因为，，所以，又，，因此得证。（5分）（2）因为有，又，群中可约律成立，所以，因此得证。（10分）五、（10分）证明：（1）P（附加前提）（2）P（3）T（1）（2）I（4）P（5）P(5分)（6）T（4）（5）I（7）T（1）（6）I（8）T（3）（7）I（9）CP(10分)