离散数学复习题5.doc

08B得分一、单项选择题(每小题2分，共10分)1.下列命题公式等值的是( )2. 设全体域D是正整数集合，确定下列命题的真值为真的命题是：（ )(A) x$y (xy=y)(B) $xy(x+y=y) (C) $xy(x+y=x) (D) x$y(y=2x) 3. 设集合A0,b,B=1,b,3,则AB上的恒等关系是 ( ). (A) , (B), (C) , (D) ,4. 已知集合Aa,b,c上的二元关系R的关系矩阵MR，那么R( )，(A) , (B) , (C) , (D) , 5. 命题公式是（ ） (A)矛盾式 (B). 可满足式 (C). 重言式 (D). 等值式得分二、填空题(每小题2分，共10分)1. 设命题公式G：P(QP)，则使公式G为假的真值指派是 。2. .设1,2,3,4,5,6，B=2,3,4，从到B的关系x,y|x=y2，则R-1= 3. 设个体域D1,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=,S=, 试用定义求，,，并画出其关系图。5(10分)写出图4-3的邻接矩阵 并求从b到d长度为3和从a到c长度为4的通路条数。图4-3得分四证明题(每小题10分，共20分)1. （10分）设R是集合A上的对称关系和传递关系，试证明：若对aA,$bA，使得R,则R是等价关系. 2. （10分）在群中，（1）如果对任意元素有，则是阿贝尔群。（2）如果对任何元素，有，则是一个阿贝尔群。得分五、（10分）用CP规则证明：。得分六、（10分）设为群,a为G中给定元素。定义函数f：GG，使得对每一xG有f(x)=a*x*a-1证明：f是到的自同构。答案一、单项选择题(每小题3分，共15分)1.C 2. A 3.B 4.D 5.A二、填空题(每小题3分，共15分) 1. (1,0)；(1,1); 2. 3. A(1)A(2)(B(1)B(2); 4. 6; 5. 单位元. 三、计算题(40分)1.(10分)解： 此为主合取范式、主析取范式：2.(5分) 解：3. (5分)解：易知，二元运算满足交换律. 对aZ, a*2=a+22a2*a，即2Z是单位元. (2分) aZ, a的逆元记作a1, 有(单位元) a1=4a (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分) aA,$bA，使得R，因为R是对称的，故R; (6分) 又R是传递的，R，RR,由元素a的任意性，知R是自反的. (9分) 所以，R是等价关系. 2证明：（1）因为，所以，又，因此得证。（5分）（2）因为有，又，群中可约律成立，所以，因此得证。 （10分）五、（10分）证明：（1） P（附加前提）（2