文档介绍：一、单项选择题
设入={a, {a}}, P（A）表示集合A的幕集，下列哪一个是错的？（ ）
(a} e P(A) B, ( a } c P(A) C. ({a}}eP(A) D. ({a}}cP(A)
设入={1 ,2,3 }上的二元关系 R = (<1 , 1>,〈1 , 2〉，〈1 , 3〉，<3 ,
3> },则R具备性质（ ）
，传递的 B,反对称的
，自反的
集合A = {x, y, z }, B = {1, 2, 3},下列A到B的二元关系中，哪一个
能构成函数？（ ）
A. {<x, 1>, <x, 2>, <y, 1>, <z, 3>} B. {<x, 1>, <y, 3>}
C. {<x, 1>, <y, 3>, <z, 1>} D. {<x, 2>, <y, 3>, <y, 2>}
下列命题中（ ）是正确的。
欧拉图的子图一定是欧拉图。
哈密顿图的子图一定是哈密顿图。
平面图的子图一定是平面图。
树的子图一定是树。
1110
0 0 10
4 =
0 0 0 1
0 0 10A. 9 B. 10
设有向图〃的邻接矩阵为
）条。
则D中长度为3的通路总数有（
C. 11 D. 12
二、填空题
公式（PtQ）t（QaR）的主析取式为。
某班共有学生60人，其中有25人订杂志甲，26人订杂志乙，26人订杂志丙，
11人订杂志甲和乙，9人订杂志甲和丙，8人订杂志乙和丙，还有8人未订任何 杂志，则三种杂志都订的学生有 人。
设入=（2, 4, 5, 10, 12, 20}, R为A上的整除关系，则A的子集B= （4,
10, 12}的极大元为, 极小元为, 上界为, 下界 为 o
设f :N^NxN,f（n）=<n,n + l> ,则函数f是 （单射，满射还是 双射)。
设集台 A={ a , b , c , d , e}上的的划分 S ={{a, d} , ({b) , (c, e}), 则由划分S所确定的A上的等价关系R = o
用kruskal算法求得下图G的一棵最小生成树为
设连通平面图G有4个面，9条边，则G有 个结点。
三、解答题(4X8 = 32分)
将下列语句翻译成命题逻辑公式或谓词逻辑公式。
(4分)只有天下大雨，小明才乘公共汽车上学。
(4分)不是所有整数都是奇数。
设入={1, 2, 3}上的二元关系 R= {<1, 1>, <1, 3>, <2, 1〉},求 R 的关 系矩阵，关系图。
设/是A到A的满射，且fof = f，证明f = IA。这里IA表示A上的 恒等映射。
画图：(1) 一个既没有欧拉回路，又没有哈密尔顿回路的图；
(2) 一个具有欧拉回路和哈密尔顿回路的图，并具体指出这两个回路。
用哈夫曼算法求带权为2,3,6, 8,10,11的最优二元树并计算此最优树的权。
设一棵树T有7片树叶，3个度数为3的结点，其余结点的度数均为4,求T 的结点总数。
用二元有序完全树表示算术表达式
((a + b)xc-d)+(e + f) + gx(/? — F)
并分别用波兰符号法和逆波兰符号法表示上述算术表达式。
四、证明题
用演绎法证明下述论断的正确性。
PvQ,Pt「