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是非平面图。