离散数学试题(2008)_A(答案)

班级：学号：姓名：装订线第1页共8页第2页共8页一、填空题（每小题3分，共15分）1.谓词公式xF(x)∧xG(x)的前束范式为x(F(x)∧G(x))．2.设V1=R,+,V2=R,，其中+和为普通加法和乘法，令:RR,(x)=ex,则是从V1到V2的单同态映射．3.设无向连通图G有6个顶点9条边,T为G的生成树，对应T的基本割集系统中的基本割集个数为5，基本回路系统中的基本回路个数为4．4.设A={1，2，3，4，5}，P(A)，构成群，其中为集合的对称差，则B={1，4，5}的逆为B．5.n阶无向简单图G的==n-1，则G为Kn．二、选择题（每小题3分，共15分）1.命题公式¬(pq)↔(¬p¬q)的类型是【A】A．重言式．B．非重言式的可满足式．C．矛盾式．D．简单析取式．2.无向树T中有4度，3度，2度顶点各1个，其余顶点都是树叶，则T中树叶片数为【B】A．1．B．5．C．7．D．8．3.下列图中是哈密尔顿图的是【D】A．K1，1．B．K2．C．K3，4．D．K5．4.下列图中那一个是欧拉图【D】A．K3，3．B．K3，4．C．K4．D．K4，4．5.有理数集上定义二元运算*为a*b=a+b-ab，运算*的零元【C】A．0．B．a．C．1．D．b．三、计算与简答题（每小题10分，共50分）1.求(rp)(q(pr))的主析取范式，并给出成真赋值．解A=(rp)(q(pr))(rp)(qp)(qr)(pr)(pq)(qr)((pr)(qq))((pq)(rr))((qr)(pp))(pqr)(pqr)(pqr)(pqr)m1m3m6m7公式的成真赋值为001，010，110，111．哈尔滨工程大学试卷考试科目：离散数学A（061121，061131）考试时间：2008.07.099:00-11:00题号一二三四五总分分数评卷人装订线第3页共8页第4页共8页2.设A={1,2,3,4,6,8,12,24}，B={1,2,3,4}，D为整除关系．(1)画出偏序集A,D的哈斯图．(2)求B的极大元、极小元、最大元、最小元、最小上界，最大下界．(3)A,D是否构成格？说明理由．解（１）偏序集A,D的哈斯图如下图．（２）B的极大元是3和4；极小元是1；无最大元；最小元是1；无最小上界；最大下界1．（３）A,D构成格，因为A中任意两个元素均有最小上界和最大上界．3.设集合Ａ={a，b，c，d}上的二元关系R={a，b，b，a，b，c，c，d}，用关系矩阵求R的传递闭包t(R)．0000100001010010RM，00000000101001012RM，00000000010110103RM，00000000101001014RM，因此0000100011111111)(RtM，从而R的传递闭包为t(R)={a，a，a，b，a，c，a，d，b，a，b，b，b，c，b，d，c，d}．4.设G=A，*，A={a，b，c}，*的运算表为：（1）找出G的单位元；（2）找出G的幂等元；（3）求b的逆元b-1和c的逆元c-1．（4）G是否为阿贝尔群？（5）求G的生成元和所有子群．解（１）G的单位元为a．（２）G的幂等元为a．（３）b的逆元b-1=c和c的逆元c-1=b．（４）G是阿贝尔群，因为运算表是对称的．（５）由于b0=a，b1=b，b2=c；c0=a，c1=c，c2=b，因此，b和c都是G的生成元．G的生成元群是b和c，即G=b=c．根据拉格朗日定理，G的子群只能是一阶和三阶群，从而G的子群是只有a={a}和G．*abcaabcbbcaccab班级：学号：姓名：装订线第5页共8页第6页共8页5.设有向图D如图，求（1）D中v1到自身长度小于或等于3的回路数；（2）D中v1到v3长度小于或等于3的通路数；（3）D中长度为3的回路数．解有向图D如的邻接矩阵为0011100001010111A，易得0212001111111212001110000101011100111000010101112A2323021212232334021200111111121200111000010101113A254612232435365732AAA（1）D中v1到自身长度小于或等于3的回路数有7条；（2）D中v1到v3长度小于或等于3的通路数有6条；（3）D中长度为3的回路数有10条．四、证明题（共20分）1.在一阶逻辑中构造下面推理的证明前提：.x(F(x)G(x)),x(G(x)R(x)),xR(x)结论：xF(x)证明(1)xR(x)前提引入(2)R(a)(1)EI规则(3)x(G(x)R(x))前提引入(4)G(a)R(a)(3)UI规则(5)G(a)(2)(4)析取三段论(6)x(F(x)G(x))前提引入(7)F(a)G(a)(6)UI规则(8)F(a)(5)(7)拒取式(9)xF(x)(8)EG规则2.设G，*是群，H，*为G，*的子群，在G上定义关系R：a，bG，a，bRhH，使得a=b*h，证明R是G上的等价关系．证明由于G，*是群，有单位元eG.，且eH．（１）aG，由a=a*e，有a，aR，即R是自反关系．（２）a，bG，若a，bR，则hH，使得a=b*h，这样，b=a*h-1，且h-1H，即b，aR，所以，R是对称关系．（３）a，b，cG，若a，bR，b，cR，则h1，h2H，使得a=b*h1，b=c*h2，这样，a=c*h2*h1，且h2*h1H，即a，cR，因此，R是传递关系．所以，R是G上的等价关系．v3v2v4v1装订线第7页共8页第8页共8页3.设R，S为一非空集合A上的反对称关系，证明R∩S也是A上的反对称关系．证明因为R，S为一非空集合上A的反对称关系，所以R∩R-1IA，S∩S-1IA，其中IA表示集合A上的恒等关系．(R∩S)∩(R∩S)-1=(R∩S)∩(R-1∩S-1)=(R∩R-1)∩(S∩S-1)IA∩IA=IA因此，R∩S也是A上的反对称关系．