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

班级：学号：姓名：装订线第1页共6页第2页共6页一、填空题（每小题3分，共15分）1.设F(x)：x是苹果，H(x，y)：x与y完全相同，L(x，y)：x=y，则命题“没有完全相同的苹果”的符号化（利用全称量词）为xy(F(x)F(y)L(x，y)H(x，y))．2.命题“设L是有补格，在L中求补元运算‘′’是L中的一元运算”的真值是0．3.设G={e，a，b，c}是Klein四元群，H=a是G的子群，则商群G/H={a，b，c}}={{e，a}，{b，c}}．4.设群G=P({a，b，c})，，其中为集合的对称差运算，则由集合{a，b}生成的子群{a，b}={，a，b}}．5.已知n阶无向简单图G有m条边，则G的补图有n(n-1)/2-m条边．二、选择题（每小题3分，共15分）1.命题“只要别人有困难(p)，小王就会帮助他(q)，除非困难已经解决了(r)”的符号化为【B】A．(pr)q．B．(rp)q．C．r(pq)．D．r(qp)．2.设N为自然数集合，“”为通常意义上的小于等于关系，则偏序集N，是【C】A．有界格．B．有补格．C．分配格．D．布尔代数．3.设n(n3)阶无向图G=V，E是哈密尔顿图，则下列结论中不成立的是【D】A．V1V，p(G-V1)V1．B．En．C．无1度顶点．D．(G)n/2．4.设A={a，b，c}，在A上可以定义个二元运算，其中有个是可交换的，有个是幂等的．【A】A．39，36，36．B．39，36，33．C．36，36，33．D．39，36，39．5.下列图中是欧拉图的有【C】A．K4，3．B．K6．C．K5．D．K3，3．三、计算与简答题（每小题8分，共40分）1.利用等值演算方法求命题公式(pq)(qp)的主合取范式；利用该主合取范式求公式的主析取范式，并指出该公式的成真赋值和成假赋值．(pq)(qp)(pq)(qp)(pq)(qp)(pqp)(qqp)qppqM1此为公式的主合取范式．该公式的主析取范式是m0m2m3．公式的成真赋值为00，10，11．公式的成假赋值为01．哈尔滨工程大学试卷考试科目：离散数学（041121，041131-32）考试时间：2007.01.1614:00-16:30题号一二三四五总分分数评卷人装订线第3页共6页第4页共6页2.求群Z18，18的所有生成元和子群，画出Z18，18的子群格，指出该子群格的全下界、全上界和有补元，并求其补元．与18互质的数有1，5，7，11，13，17，因此，1，5，7，11，13，17是群Z18，18的生成元．18的因数有1，2，3，6，9，18，因此，群Z18，18的子群有1=Z18，18，2={0，2，4，6，8，10，12，14，16}，18，3={0，3，6，9，12，15}，18，6={0，6，12}，18，9={0，9}，18，18={0}，18．Z18，18的子群格为{18，9，6，3，2，1}，，其哈斯图为全下界为18，全上界为1，18’=1，1’=18，2’=9，9’=2，3和6没有补元．3.若R1，R2均是非空集合A上的等价关系，那么R1，R2的交R1∩R2、并R1∪R2和复合R1○R2也是A上的等价关系吗？若是，证明你的结论．R1∩R2是A上的等价关系．事实上，(1)因R1，R2是A上的自反关系，有IAR1，IAR2，因此，IAR1∩R2，即R1∩R2是A上的自反关系．(2)因R1，R2是A上的对称关系，有R1＝R1-1，R2＝R2-1，而(R1∩R2)-1=R1-1∩R2-1=R1∩R2，因此，R1∩R2是A上的对称关系．(3)因R1，R2是A上的传递关系，有R12R1，R22R2，而(R1∩R2)2=(R1∩R2)(R1∩R2)=R12∩R22∩R1R2∩R2R1R12∩R22R1∩R2，因此，R1∩R2是A上的传递关系．4.设无向连通图G如下图，求其最小生成树T及T的权W(T)，写出G的对应于T的基本回路系统和基本割集系统．G的最小生成树T如图（以实线表示），权W(T)=11．G的对应于T的基本回路系统为{Cbd，Ccd，Cde}，其中Cbd=bdab，Ccd=cdabc，Cde=dead．G的对应于T的基本割集系统为{Sab，Sad，Sae，Sbc}，其中Sab={ab，bd，cd}，Sad={ad，bd，cd，de}，Sae={ae，de}，Sbc={bc，cd}．5.设Ｂ，，，′，0，1是布尔代数，a，b，cB，化简公式(ab)(a(bc)’)c．(ab)(a(bc)’)c=(ab)(a(b’c’))c=(ab)((a(b’c’))c)=(ab)((ac)(b’c’c))=(ab)(ac)=(a(ac))(bac)=(ac)(acb)=ac1183265414ecbad班级：学号：姓名：装订线第5页共6页第6页共6页四、证明题（共20分）1.在自然推理系统中，构造推理证明：前提：x(F(x)G(x))结论：xF(x)xG(x)证明：(1)xF(x)附加前提引入(2)xF(x)(1)置换(3)F(c)(2)EI规则(4)x(F(x)G(x))前提引入(5)F(c)G(c)(4)UI规则(6)G(c))(3)(5)析取三段论(7)xG(x)(6)EG规则2.设代数系统A，是独异点，e是其单位元．若aA，有aa=e，证明：A，是Abel群．证明：由于对aA，有aa=e，因此，A中任意元素a都有逆元，且a=a-1．又A，是有单位元的独异点，从而A，是群．a，bA，有abA，且a=a-1，b=b-1，(ab)-1=ab．又(ab)-1=b-1a-1=ba，因此ab=ba，即A，是Abel群．3.证明：若无向图G为欧拉图，则G无桥．证明：（1）假设G中有桥，不妨设e=(u，v)为其一座桥．这样，从中删去边e=(u，v)后，所得图G’一定不连通（G’至少含有两个连通分支）．由于G为欧拉图，因此它是连通图，且有经过每条边一次且仅一次的回路，这条回路必经过G的所有顶点．从而存在顶点v1，v2，…，vs，使得uv1v2…vsvu是G的一条回路．从G中删去边e=(u，v)后，所得图G’仍有从u到v的通路uv1v2…vsv，这样G’仍是连通图．矛盾．因此，G中一定无桥．（2）由于G为欧拉图，其每个顶点的度数均为偶数．假设G中有桥，不妨设e=(u，v)为其一座桥．这样，从中删去边e=(u，v)后，所得图G’至少有两个连通分支．而且，顶点u，v的度数都是奇数，这与每个连通分支为图矛盾（与握手定理矛盾），因此，G中一定无桥．五、应用题（10分）今有a，b，c，d，e，f和g七人，已知a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲德语和意大利语；f会讲法语、日语和俄语；g会讲法语和德语，试问：如何将这七个人安排围坐在一张圆桌上，使得每个人都可和他身边的人交谈．以a，b，c，d，e，f和g七人为顶点，如果两人有共同语言，连接这两个顶点，以此为边做一个图，如右图．在图中如果能找到一条哈密尔顿回路，则将这七个人安排围坐在一张圆桌上，每个人都可和他身边的人交谈．该回路为abdfgeca．cbfgdea