资源描述：
《离散数学试题2014-03（2014_12_26)_参考答案与评分标准》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、参考答案与评分标准（共7页）一.名词解释：（10分）1、群：设〈G,*〉是一个代数系统，其中G是非空集合，*是6上一个二元运算,如果满足：（1）运算*是封闭的；（2）运算*是可结合的；（3）存在幺元e；（4）对于每一个元素xeG,存在它的逆元x"。则称（G,*）是一个群。2、整环：设〈A,+,・）是一个代数系统，如果满足：（1）〈A,+）是阿贝尔群；（2）（A,e）是可交换的独异点，且无零因子；（3）运算•对于运算+是可分配的。则称〈A,+,・〉是一个整环。3、分配格：设是由格〈A,今所诱导的代数系统。如果对任意的a,b,ceA满足：（1）（7A（Z?VC）=（<7AZ?）V（6ZAC）；（
2、2）（7V（Z?AC）=（<7VZ?）A（aVC）则称〈A,®是分配格。4、同余关系：〈A,*〉是一个代数系统，并设R是A上的一个等价关系。如果当va,b>,gR时，有va*c,b*〃R。则称R为A上关于运算*的同余关系。5、布尔表达式：设（A,v,a/）是一个布尔代数，并且在这个布尔代数上定义布尔表达式如下：（1）A中任何元素是一个布尔表达式；（2）任何变元是一个布尔表达式；（3）如果©和乞是布尔表达式，那么，e,ve2）和（弓心2）也都是布尔表达式。第一题评分标准：若答出要点，不再扣分了，出错适当扣分。二、证明：AB=(A㊉B)(AB)(io分)证明：右边=(A-B)(B-A
3、)(AB)=(A〜B)(B〜A)(AB)(2)=(4(BB))(B~A)(3)=A(BA)(4)=(AB)(AA)(5)=AB二方［边(6)⑴第二题评分标准:(2)(3)(4)(5)各2分，(1)(6)各1分，出错折半给分。三、求命题公式(P^Q)aR的主析取范式和主合取范式。(io分)解：(PQ)AR=(-1PvQ)AR=PaR)V(QaR)=Pa(Qv-1Q)aR)v((Pv-.P)aQaR)=(-iPaQaR)v(-iPa—iQaR)v(PaQaR)v(—iPaQaR)=(—iPa-iQaR)v(—iPaQaR)v(PaQaR)=m()oivmoiivmrn二工中(主析取范式)(Q->
4、P)AR<=>n(主合取范式)JLJLO.2,4.5.6■Mg)aM0I0aM1(XJaMl01aMll0=(PvQvR)a(Pv—iQvR)a(—)PvQvR)a(—iPvQv—iR)a(—iPv—iQvR)第三题评分标准：写出主析取范式得6分，写出主合取范得4分，没有具体写出大项扣1分。也可以用真值表方法求解。四、令g/是一个复合函数，证明：如果g和/是双射，那么g/是双射。(10分)证明：设/:XTY,g:YTZ,则g/:XtZ如果g和f是双射，则g和f既是满射又是入射。(1)对任意zeZ,因为g是满射，所以必有y^Y,使得z=g(y),乂因为/是满射，所以必有xwX,使得y=/(x)
5、从而，对任意zeZ,必存在xeX,使得z=g(y)=g(/O))=g/(兀)，因此，g/:XtZ是满射。⑵令%!，X2GX,假设X]HX2，由于.f是入射，所以有/(兀])工/(兀2)，又因为g是入射,所以有g(/3))Hg(/02))，即：g/(兀2)于是/(西)Hg/(兀2)因此，gf：X—Z是入射。第四题评分标准：证明正确给10分，满射与入射证明各为5分，出错折半给分。五、形式化以下命题，并用推理规则证明其结论。如果一个人怕困难就不会获得成功；所有的人或者是获得成功的或者是失败的；存在着没有失败的人。所以，存在着不怕困难的人。(注：假设论域为人)(10分)证：设A(x):X怕困难。B(
6、x):x获得成功。C(x):x失败。则：(Vx)(A(x)—「3(兀)),(Vx)(3(兀)vC(x)),(3x)^C(x)n(3x)r4(兀)(1)(3x)-1C(x)P(2)—C(d)ES(1)(3)(Vx)(B(x)vC(jr))P(4)B(a)vC(g)US(3)(5)B(a)—iC(6f)T(4),E(6)-iC(tz)tB(a)T(5),I(7)B(a)T(2),(6),I(8)(Vx)(A(x)P(9)t4(€Z)—》-B(d)US(8)(10)―(a)T(7),(9),I(11)(3x)—iA(x)EG(10)第五题评分标准：正确写出谓词得2分，正确写出要证明的谓词公式再得2
7、分，谓词演算正确得6分。出错折半给分。(注：不用异或用析取也算正确)，另外，把失败看成是成功的否定，少用一个谓词也算正确。六、设/和g都是从群＜4*＞到群＜5A＞的同态映射，证明＜*＞是群＜人*＞的一个子群，其中，C={x
8、xgABf(x)=g(x)}(io分)证明：显然CoA,对任意的a,bwC,则有/(tz)=g(a),/(b)=^(b)＜＞因为/和都是g同态映射，所以有/(沪)=./@)T,g(b)=g
