一、单项选择题（每小题3分，本题共15分）
1．若集合A＝{ a，{a}}，则下列表述正确的是( A )． A．{a} A B．{{{a}}} A 2．命题公式（P∨Q）的合取范式是 ( C ) A．（P∧Q） B．（P∧Q）∨（P∨Q） 3．无向树T有8个结点，则T的边数为( B )． A．6 B．7 C．8 4．图G如图一所示，以下说法正确的是 ( B )． A．a是割点 B．{b, c}是点割集
C．{a，{a}} A D． A
C．（P∨Q） D． （ P∧ Q） D．9 C．{b, d}是点割集 D．{c}是点割集
图一
5．下列公式成立的为( D )． A． P∧ Q P∨Q B．P Q P Q 二、填空题（每小题3分，本题共15分）
6．设集合A={2, 3, 4}，B={1, 2, 3, 4}，R是A到B的二元关系，
C．Q P P D． P∧(P∨Q) Q
R { x,y x A且y B且x y} 则R的有序对集合为 {<2, 2>，<2, 3>，<2, 4>，<3, 3>}，<3, 4>，<4, 4>}__．
7．如果R是非空集合A上的等价关系，a A，b A，则可推知R中至少包含 <a, a >，< b, b > 等元素．
8．设G＝<V, E>是有4个结点，8条边的无向连通图，则从G中删去 5 条边，可以确定图G的一棵生成树．
9．设G是具有n个结点m条边k个面的连通平面图，则m等于 n+k 2 ． 10．设个体域D＝{1, 2}，A(x)为“x大于1”，则谓词公式
( x)A(x)的真值为 真（或T，或1） ．
三、逻辑公式翻译（每小题6分，本题共12分） 11．将语句“今天考试，明天放假．”翻译成命题公式． 解: 设P：今天考试，Q：明天放假． 则命题公式为：P∧Q． 12．将语句“我去旅游，仅当我有时间．”翻译成命题公式． 解: 设P：我去旅游，Q：我有时间， 则命题公式为：P Q． 四、判断说明题（每小题7分，本题共14分） 判断下列各题正误，并说明理由．
13．如果图G是无向图，且其结点度数均为偶数，则图G是欧拉图． 解: 错误． 当图G不连通时图G不为欧拉图．
14．若偏序集<A，R>的哈斯图如图二所示，则集合A的最大元为a，最小元是f． 解: 错误． 集合A的最大元与最小元不存在， a是极大元，f是极小元，．
图二
五．计算题（每小题12分，本题共36分） 15．设谓词公式
解:
( x)(A(x,y) ( z)B(y,x,z))，试（1）写出量词的辖域； （2）指出该公式的自由变元和约束变元．
（1） x量词的辖域为(A(x,y) ( z)B(y,x,z))， z量词的辖域为B(y,x,z), （2）自由变元为(A(x,y) ( z)B(y,x,z))中的y， 约束变元为x与z．
16．设集合A={{1},1,2}，B （3）A×B．
解: （1）A B ={{1},2} （2）A∩B ={1} （3）A×B={<{1},1>，<{1},{1,2}>，<1,1>，<1, {1,2}>，<2,1>，<2, {1,2}>}
17．设G=<V，E>，V={ v1，v2，v3，v4 }，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4) }，试（1）给出G的图形表示；（2）写出其邻接矩阵；（3）求出每个结点的度数；（4）画出其补图的图形．
解: （1）G的图形表示为(如图三)：
0
0
（2）邻接矩阵：图三 1
0
010
011101110
（3）v，v，v，v结点的度数依次为1，2，3，2 （4）补图如图四所示： 图四
六、证明题（本题共8分）
18．设A，B是任意集合，试证明：若A A=B B，则A=B．
证明：设x A，则<x，x> A A，
因为A A=B B，故<x，x> B B，则有x B， 所以A B． 设x B，则<x，x> B B， 因为A A=B B，故<x，x> A A，则有x A，所以B A． 故得A=B．
1