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

班级： 学号： 姓名： 装 订 线第 1 页 共 8 页 第 2 页 共 8 页一、 填空题（每小题 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．V 1V，p( G-V1)V1． B．E n．C．无 1 度顶点． D．(G)n/2 ．4. 设 A={a，b，c}，在 A 上可以定义　 　个二元运算，其中有　　　　个是可交换的，有 　　　　个是幂等的． 【A】A．3 9，3 6，3 6． B．3 9，3 6，3 3．C． 36，3 6，3 3． D．3 9，3 6，3 9．5. 下列图中是欧拉图的有 【C 】A．K 4，3 ． B．K 6．C． K5． 　 D．K 3，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哈 尔 滨 工 程 大 学 试 卷考试科目：离散数学（041121，041131-32）考试时间：　2007.01.16 14:00-16:30题号 一 二 三 四 五 总分分数评卷人装 订 线第 3 页 共 8 页 第 4 页 共 8 页M1此为公式的主合取范式．该公式的主析取范式是m 0m2m3．公式的成真赋值为00，10，11．公式的成假赋值为01．2. 求群Z 18， 18的所有生成元和子群，画出 Z18， 18的子群格，指出该子群格的全下界、全上界和有补元，并求其补元．与18互质的数有1，5，7，11，13，17，因此，1，5，7，11，13，17是群Z 18， 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，R 2 均是非空集合 A 上的等价关系，那么 R1，R 2 的交R1∩R 2、并 R1∪R 2 和复合 R1○ R2 也是 A 上的等价关系吗？若是，证明你的结论．R1∩R 2是A上的等价关系．事实上，(1) 因R 1，R 2是A上的自反关系，有I AR1， IAR2，因此，IAR1∩R 2，即R 1∩R 2是A 上的自反关系．(2) 因R 1，R 2是A上的对称关系，有R 1＝R 1-1，R 2＝R 2-1，而(R1∩R 2)-1=R1-1∩R 2-1=R1∩R 2，因此，R 1∩R 2是A上的对称关系．(3) 因R 1，R 2是A上的传递关系，有R 12R1，R 22R2，而(R1∩R 2)2=(R1∩R 2)(R1∩R 2)=R12∩R 22∩R 1R2∩R 2R1R12∩R 22R1∩R 2，因此，R 1∩R 2是A 上的传递关系．4. 设无向连通图 G 如下图，求其最小生成树 T 及 T 的权 W(T)，写出 G 的对应于 T 的基本回路系统和基本割集系统．G的最小生成树T如图（以实线表示） ，权W( T)=11．G的对应于T的基本回路系统为{ Cbd，C cd，C de}，其中Cbd=bdab，C cd=cdabc，Cde=dead．G的对应于T的基本割集系统为{S ab，S ad，S ae，S bc}，其中Sab={ab，bd ，cd }，S ad={ad，bd，cd，de }，Sae={ae，de}，S bc={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)1183265414ecbad班级： 学号： 姓名： 装 订 线第 5 页 共 8 页 第 6 页 共 8 页=(ab)((ac)(b’ c’ c))=(ab)(ac)=(a(ac))(bac)=(ac)(acb)=ac四、 证明题（共 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，v 2，…，v s，使得uv 1v2…vsvu是G的一条回路．从G中删去边e=(u，v) 后，所得图 G’仍有从u到v的通路uv 1v2…vsv，这样G’ 仍是连通图．矛盾．因此，G中一定无桥．（2）由于G为欧拉图，其每个顶点的度数均为偶数．假设G中有桥，不妨设e=( u，v ) 为其一座桥．这样，从中删去边e=(u，v) 后，所得图 G’至少有两个连通分支．而且，顶点 u，v的度数都是奇数，这与每个连通分支为图矛盾（与握手定理矛盾） ，因此，G中一定无桥．五、 应用题（10 分）装 订 线第 7 页 共 8 页 第 8 页 共 8 页今有a，b，c，d，e ， f 和g七人，已知a会讲英语；b会讲英语和汉语；c 会讲英语、意大利语和俄语；d会讲汉语和日语；e 会讲德语和意大利语；f 会讲法语、日语和俄语；g会讲法语和德语，试问：如何将这七个人安排围坐在一张圆桌上，使得每个人都可和他身边的人交谈．以a，b，c， d，e ，f 和g七人为顶点，如果两人有共同语言，连接这两个顶点，以此为边做一个图，如右图．在图中如果能找到一条哈密尔顿回路，则将这七个人安排围坐在一张圆桌上，每个人都可和他身边的人交谈．该回路为abdfgeca．cbfgd ea。