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

装 订 线 班级： 学号： 姓名： 装 订 线 第 =page 4*2-1 7页 共 = NUMPAGES 4*28页 第 = PAGE 4*2 8页 共  = NUMPAGES 4*28页 第 =page 3*2-1 5页 共 = NUMPAGES 4*28页 第 = PAGE 3*2 6页 共  = NUMPAGES 4*28页 哈尔滨工程大学试卷 考试科目：离散数学（041121，041131-32） 考试时间：　2007.01.16 14:00-16:30 题号一二三四五总分分数评卷人 填空题（每小题3分，共15分） 设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))． 命题“设L是有补格，在L中求补元运算‘′’是L中的一元运算”的真值是　0　． 设G={e，a，b，c}是Klein四元群，H=?a?是G的子群，则商群G/H={?a?，?b，c}}={{e，a}，{b，c}}． 设群G=?P({a，b，c})，??，其中?为集合的对称差运算，则由集合{a，b}生成的子群?{a，b}? ={?，?a，b}}． 已知n阶无向简单图G有m条边，则G的补图有n(n-1)/2-m　　　　条边． 选择题（每小题3分，共15分） 命题“只要别人有困难(p)，小王就会帮助他(q)，除非困难已经解决了(r)”的符号化为 【B】 A．?(p?r)?q． B．(?r?p)?q． C．?r?(p?q)． D．?r?(q ? p)． 设N为自然数集合，“?”为通常意义上的小于等于关系，则偏序集?N，??是 【C】 A．有界格． B．有补格． C．分配格． D．布尔代数． 设n (n?3) 阶无向图G=?V，E?是哈密尔顿图，则下列结论中不成立的是 【D】 A．?V1?V，p(G-V1)??V1?． B．?E??n． C．无1度顶点． D．?(G)?n/2． 设A={a，b，c}，在A上可以定义　 　个二元运算，其中有　　　　个是可交换的，有　　　　个是幂等的． 【A】 A．39，36，36． B．39，36，33． C．36，36，33． D．39，36，39． 下列图中是欧拉图的有 【C】 A．K4，3． B．K6． C．K5． 　 D．K3，3． 计算与简答题（每小题8分，共40分） 利用等值演算方法求命题公式(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． 求群?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?， ??? ??? ?1? ??? ??? ?18? ?3?=?{0，3，6，9，12，15}，?18?， ?6?=?{0，6，12}，?18?， ?9?=?{0，9}，?18?， ?18?=?{0}，?18?． ?Z18，?18?的子群格为?{?18?，