： 名姓装 订 ： 线号学 ： 级班 哈尔滨工程大学试卷 考试科目：离散数学A（061121，061131） 考试时间： 2008.07.09 9:00-11:00 题号 一 二 三 四 五 总分 分数 评卷人 一、 填空题（每小题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． 第1页 共2页 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．
第2页 共 2页
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)． ??0100?MR??1010????0001?， ???0000????1010???0101??010?M??0101????1010??1?101??R2???0000?，MR3?0000?，MR4??0??????0000?， ??0000???0000????0000????1111?因此M??1111??t(R)?00的传递闭包为 ?01?，从而R???0000??t(R)={?a，a?，?a，b?，?a，c?，?a，d?，?b，a?，?b，b?，?b，c?，?b，d?，?c，d?}． 第3页 共4页 4. 设G=
* a
b c （3）求b的逆元b-1和c的逆元c-1
．
a a
b c （4）G是否为阿贝尔群？
b b
c a （5）求G的生成元和所有子群． c c
a
b
解 （１）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的生成元群是和
第4页 共 4页
装订线 ： 名姓装 订 ： 线号学 ： 级班 5. 设有向图D如图，求 v1 v4 （1）D中v1到自身长度小于或等于3的回路数； （2）D中v1到v3长度小于或等于3的通路数； v2 v3 （3）D中长度为3的回路数． ??1110?解 有向图D如的邻接矩阵为A??1010????0001?，易得 ???1100????1110?110?121?A2??1010???1??1010???2?111????0001??001???1????0??1100? ??1100????1100????2120????1110?121??332?A3??1010???2??1111??4??3221????0001??100???????2120? ??110??10???2120????3232????7563?A?A2?A3??5342????3221? ???6452??（1）D中v1到自身长度小于或等于3的回路数有7条； （2）D中v1到v3长度小于或等于3的通路数有6条； （3）D中长度为3的回路数有10条． 第5页 共6页 四、 证明题（共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上的等价关系．
第6页 共 6页
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上的反对称关系． 第7页 共8页 第8页 共 8页
装订线
相关推荐：
loading