04-05-2计算机03级离散考题(A) 下载本文

一、判断题 :将判定结果真(T)或假(F)直接填入到题前的括号中。(共15分,每题1分)

( ) 1. 设A=?,B={?,{?}},则B-A={{?}}。 ( ) 2. ??{?}且??{?}。

( ) 3. 集合A上的恒等关系既是A上的等价关系,也是A上的偏序关系。 ( ) 4. 集合A={1, 2, 3}上的二元关系R={<1, 2>, <1, 3>}是可传递的。

( ) 5. 设A是集合,N是自然数集合,R是实数集合,如果K[A]?K[N],则K[A]=K[R]。 ( ) 6. 全序集一定是良序集。

( ) 7. 设是4阶群,则一定不能成为某14阶群的子群。 ( ) 8. 4阶群不一定都是阿贝尔群。

( ) 9. 设是群,e是关于运算 * 的幺元,?a?G,若a ?e,则一定不是等幂元。 ( )10. 设是7阶群,则G中至少有一个元素的阶等于该群的阶。 ( )11. 设为格,|L|=n,则为有界格。

( )12. 设R是A={1, 2, 3, 6}上的整除关系,则< A, R >是有补分配格。

( )13. 设为格,其诱导的代数系统为,a, b?L,则a ? b = a和a ? b = b至少有一个成立。

( )14. 存在7个结点的自补图。 ( )15. 不存在奇数条边的自对偶图。 二、填空题。(共18分,每空1分):

1.?P ? Q的主析取范式为_________________________________________,主合取范式为___________________________________。

2.集合A={{?, {?}}, ?},B={{?}, ?},则A?B =__________________,A-B=___________________,集合A?B=________________________________。 集合A的幂集P(A)的基数为____________________。

3.设R是集合A={a,b,c}上的二元关系,且R={},则R的自反闭包r(R)=_________________________________________________, 对称闭包s(R)=_______________________________________________________。

4.设R是集合A={1, 2, 3, 4, 5}上的二元关系,R={<1, 1>, <1, 2>, <2, 1>, <2, 2>, <3, 3>, <4, 4>, <4, 5>, <5, 4>, <5, 5>}是等价关系,由R所诱导的A的划分为

________________________________,R的不同等价类的个数为___________。

5.设集合|A|=4,则A上可以定义_____个二元关系,_____个等价关系,____个自反关系。 6.设R是实数集合,f和g是R到R的函数,x?R,且f(x)= 3x+1,g(x)= x2,那么f?g(x)=__________________。

7.圆心在x轴上的单位圆的集合的基数为___________。

8.设 *,?是定义在集合A上的两个可交换的二元运算,如果对于任意的x,

y?A,都有x *(x ? y ) = x,x ? ( x *y ) = x,则称运算*和运算?满足_______律。 9.设< L, ≤>是有n个原子的有限布尔格,则 |L| =______________。 10.若T是有n个结点的完全二叉树,则T有______片树叶。 三、选择题。(共7分,每题1分) 1.下列命题中,________为假命题。

A.太阳从西方出来,当且仅当雪是黑的 B.如果雪是黑的,那么太阳从西方出来 C.如果雪是黑的,那么太阳从东方出来 D.或者雪是黑的,或者太阳从西方出来

2.设|A|=3,|B|=2,则从A到B可以定义______个函数;

A.6 B.8 C.9 D.64

3.函数f:X?Y可逆的充要条件是_______;

A.X = Y B.X与Y有相同的基数 C.f 为满射 D.f为双射 4.设S为一有限集,P(S)为S的幂集,?、?、?分别为集合的并、交、对称 差运算,则________。

A.< P(S), ?>为群 B.< P(S), ?>为群 C.< P(S), ?>为群 D.以上都真

5.设S为一有限集,P(S)为S的幂集,?、?、?分别为集合的并、交、对称 差运算,则S为________的零元。

A.< P(S), ?> B.< P(S), ?> C.< P(S), ?> D.以上都不真

6.设f:R?R+,其中R为实数集合,R+为正实数集合,f(x)=ex,则______。

A.f(x)为满同态而非单一同态 B.f(x)为单一同态而非满同态 C.f(x)为同构映射 D.以上都不真

7.以下_______不是树T的定义,其中n为T中的结点数,m为其边数。

A. 连通,无回路 B. 无回路的无向图 C. 连通并且m=n-1 D. 无回路且m=n-1 四、翻译题。(共20分,每小题2分) 1.找出各原子命题,并符号化下列命题:

1)我将去新华书店,除非天下雨。 2)只有好好复习,才能取得好成绩。 3)王刚与李强组成一个研究小组。 4)生命不息战斗不止。 5)我们不能既工作又聊天。

2.将下述语句分别表示成仅含有I(x)、E(x)、O(x)、S(x,y)、G(x,y)所组成的谓词公式,

其中:

I(x):x是整数 E(x):x是偶数 O(x):x是奇数 S(x,y):x=y G(x,y):x?y 1)所有整数或者是偶数,或者是奇数。

2)所有偶数都是整数。 3)存在最小的正偶数。

4)对所有的整数x,当且仅当x是偶数时,x+1是奇数。 5)不存在比所有奇数都大的偶数。 五、用推理规则证明:(共6分,每题3分) 1.P ? ( Q ? R ),?S ? ?Q,P ? ?S ? R

2.?x ( P( x) ? Q( x) ), ?x( P( x) ? R( x)) ? ?x (Q( x)? R( x)) 六、(共8分)

1.设A、B为集合,P(A)、P(B)分别为它们的幂集,证明:若A=B,则

P(A) = P(B)

2.设A={1,2,3,6,9,54},D是A上的整除关系。 1)画出的哈斯图;

2)是否为格?若是格,是否分配格?是否有补格?是否布尔格? 七、(共6分)下列代数系统哪个是群?若是群,指出其幺元以及每个元素的逆元。 1. ,其中G={an| n整数},a是正实数,*为普通乘法;

2.,其中S是集合,P(S)是其幂集,?是集合的对称差运算。 八、(共10分)

1. 求图1的邻接矩阵及可达性矩阵,并用矩阵运算的方法计算从v1到v3长度为2的路有多少条。(6分)

2. 画一棵带权为1,3,5,7,9,11,13的最优二叉树T,并计算它的权W(T)。 (4分) v1v4v 2 v3 图1 图2

九、(共10分,每题5分)

21.设简单G=,且|V|=v,|E|=e,证明:若有e?Cv?1?2,则G是汉密尔顿图。

2.证明图2是非平面图。