内容发布更新时间 : 2025/5/1 7:26:57星期一 下面是文章的全部内容请认真阅读。
一、判断题 ：将判定结果真（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. 设
（ ） 9. 设
（ ）12. 设R是A={1, 2, 3, 6}上的整除关系，则< A, R >是有补分配格。
（ ）13. 设
（ ）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={
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）
2．
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=
2．证明图2是非平面图。