级本《离散》(A)答案.docVIP

计算机系07级本科《离散数学》考试题（A） 参考答案 一、选择填空（共20分, 每小题2分） 1.C 2.B 3.A 4.C 5.B 6.C 7.A 8.B 9.A 10.D 二、填空（共2分，每小题2分） 1. 00,10 非重言式的可满足式 2. 交换群，独异点（或幺半群、单元半群均可） 3.{Φ,{c}，{d}，{c，d}}， ={〈c,a〉,b,b,d,a,d,b} 4. {2,3} ,. {1,4} 5． n-k,n(n-1) 6.RU{1,4}， {1,4,2,2}。 7. (不唯一，与此等值的前束范式均可) 8. =(143) =(134) 9．6, -4 10．13,7 三 1. √ 2. √ 3.× 4.× 5.× 四.(每小题5分,共15分) 1．已知X={1，2，3},写出的所有双射。 解：X上共有6个双射，它们是： f1＝{a,a,b,b,c,c}, f2＝{a,a,b,c,c,b} f3＝{a,b,b,a,c,c}, f4＝{a,b,b,c,c,a} f5＝{a,c,b,a,c,b}, f6＝{a,c,b,b,c,a} 2．画出一棵叶权为2，2，2，3，3，4的最优二叉树并计算出树权。 解：图略。 W（T）=41 （注：图不唯一，只要树权为41的均为正确的） 3. 求公式的主析取范式和主合取范式 主合取范式;主析取范式 (注:本题可用等值演算,也可用真值表求) 五、（每小题10分，共20分） 1、(10分) 已知偏序集〈X,R〉,其中X={a,b,c,d,}, Y={a,b}, R的关系矩阵为 1.用集合的列举法写出R; 2.画出R的哈斯图； 3.找出X的极大元、极小元、最大元、最小元； 4.找出Y的上界、下界、最小上界、最大下界。 解:(1). R={a,c,a,d,〈b,a, ,b,c,b,d, (3分) (2). 哈斯图略(3分) (3)．X的极大元c,d、极小元b、最大元无、最小元b；(2分) (4). Y的上界a,c,d、下界b、最小上界a、 最大下界b。(2分) 2．已知有向图G=V,E,其中v={a,b,c,d}，E={a,b,b,a,b,c, b,b,b,d,c,a ,c,d,d,c,d,d} (1).求出各点的入度序列、出度序列 (2).判定图G是否为欧拉图？，是否哈密顿图？并说明理由。 (3).写出G的邻接矩阵； (4).找出所有长度小于等于2的回路的条数. 解:1. 各点的入度序列:2 ,2,2,3 各点的出度序列:1 ,4,2,2 (2分) 2.不是欧拉图,因为有的点的入度不等于出度. (2分) 是哈密顿图 ,存在一个包含所有结点的哈密顿路（圈） abdca (2分) 3. (2分) 4. 所有长度小于等于2的回路共有8条(2分) 六、证明题（每小题10分，共20分） 1．给出下列推理证明的规则， 前提：， 结论： 证明:(1) P; (2) T(1) EI规则; (3) P; (4) T(3) UI规则; (5) T(2)化简规则; (6) T(4)(5)假言推理规则; (7) T(2)化简规则; (8) T(5)(7)析取三段论; (9) T(8) EG规则。 2． Zn={0,1,2,…,n-1 },在Zn上定义二元运算·: x·y=(x+y) mod n, 其中+、-是普通加法、减法，证明Zn，· 是循环群。 证(1)对任意x,y∈Zn, 因 x·y=(x+y) mod n∈Zn 所以·是二元运算, Zn，·是代数系统;（2分） (2) 对任意x,y,z∈Zn,因 (x·y) ·z=((x+y) mod n) ·z=(x+y+z) mod n x·(y·z)=x·((y+z) mod n)=(x+y+z) mod n 有(x·y) ·z= x·(y·z) 所以·满足结合律, Zn，·是半群; （2分） 对任意x, 因 0·x=x·0=x 所以,0是单位元; （2分） (4) , 对任意x∈Zn且时, x·(n-x)=(n-x) ·x=0 所以 由(1)(2(3)(4)知Zn，·是群;