离散数学试题(2006) - A（答案） - 图文

：名姓 装 订 ： 线号学 ：级班 哈尔滨工程大学试卷 考试科目：离散数学（041121，041131-32） 考试时间： 2007.01.16 14:00-16:30 题号 一 二 三 四 五 总分 分数 评卷人 一、 填空题（每小题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】 第1页 共2页 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． 第2页 共 2页 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}，??1? 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?没有补元． ?18?3. 若R 1，R2均是非空集合A上的等价关系，那么R1，R2的交R1∩R2、并R1∪R和复合R 21○ 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上的传递关系． 第3页 共4页 4. 设无向连通图G如下图，求其最小生成树T及T的权W(T)，写出G的对应于T的基本回路系统和基本割集系统． G的最小生成树T如图（以实 e 6 d 线表示），权W(T)=11． 5 G的对应于T的基本回路系统 4 2 3 4 c 为{Cbd，Ccd，Cde}，其中 Ca bd=bdab，Ccd=cdabc， 1 b 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 第4页 共 4页 装 订 线 ：名姓 装 订 ： 线号学 ：级班 四、 证明题（共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群．

第5页 共6页

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七人为 顶点，如果两人有共同语言，连接这 两个顶点，以此为边做一个图，如右 图． 在图中如果能找到一条哈密尔顿回路，则将这七个人安排围坐在一b a g 张圆桌上，每个人都可和他身边的人交谈．该回路为abdfgeca． c f 第6页 共 6页 d e ?

本文来源：https://www.bwwdw.com/article/mz7t.html