题型
一、填空题
1、设集合A有n个元素，那么A的幂集P(A)的元素个数为____________。 2、谓词公式?xF(x)?Q(x,y)中的前束范式为______________。 3、设集合A＝{a,b,{a,b}}，B＝{{a,b}},则B-A=_____________。
4、设集合A＝{0,1}，B＝{1,2},则A×B=_____________________________________。 5．已知图G中有1个1度结点，2个2度结点，3个3度结点，则G的边数是 。
二、单项选择题
1、下列各命题中真值为真的命题有（ ）。
A. 2+2=4当且仅当3是奇数 B. 2+2=4当且仅当3不是奇数 C. 2+2≠4当且仅当3是奇数 D. 2+2=4仅当3不是奇数 2、设个体域D={a,b}，与公式?xA(x)等价的公式是( )。
A. A(a)?A(b) B. A(a)?A(b) C. A(a)?A(b) D. A(b)?A(a)
3、令F(x):x是人，G(x):x是犯错误，则命题“没有不犯错误的人”可符号化为（ ）。 A.?x(F(x)?G(x)) B.??x(F(x)??G(x)) C.??x(F(x)?G(x)) D.??x(F(x)??G(x)) 4、下列命题公式不是永真式的是( )。
A. (p?q)?p B . p?(q?p) C. ?p?(q?p) D. (p?q)?p 5、设X={1,2,3},Y={a,b,c},f={<1,b>,<2,a>,<3,a>},则以下命题正确的是( )。 A．f是从X到Y的二元关系，但不是从X到Y的函数
B．f是从X到Y的函数，但不是满射的，也不是单射的
C．f是从X到Y的满射，但不是单射 D．f是从X到Y的双射
6、设集合A={a, b, c}，A上的二元关系R={
7、设集合A={1,2,3,4}，A上的等价关系R={ <3,2>, <2,3>}?IA，则对应于R的划分是（ ）。
A. {{1},{2,3},{4}} B. {{1,3},{2,4}} C. {{1,3},{2},{4}} D. {{1},{2},{3},{4}}
8、图G1如图1所示，以下说法正确的是( )。 A. a是割点 B. {b,c}是点割集 C. {b,d}是点割集 D. c是割点
a b c 图1 G1 d 9、设集合S={1,-1}，下面定义的哪种运算关于集合S是封闭的( )。 A. 普通的减法运算 B. 普通的加法运算 C. 普通的乘法运算 D. 以上均不是
10、集合A={2,3,6,12,24,36}上的偏序关系R的哈斯图G2如图2所 示，则集合B={2,3,6}的最小元为（ ）。 A. 2 B. 3 C. 2和3 D. 不存在
24 12 6 2 3 36 图2 G2 三、推理及证明题
1、已知A，B，C是三个集合，证明：A-(B?C)=(A-B)-C. 2、构造下面推理的证明。
前提：A，A→B，A→C，B→(D→?C) 结论：?D
四、综合应用题
1、利用等值演算法求命题公式（P?Q）?R的主合取范式并给出其成真赋值和成假赋值。
2、设集合Ａ={a，b，c}上的二元关系R={?a，b?，?b，a?，?b，c?}，求R的自反闭包r(R)，对称闭包s(R)及传递闭包t(R)。 3、设有向图D如图G3所示,回答下列问题： （1）求图D的邻接矩阵；
（2）求图D中长度为2的通路数； （3）求图D中长度为2的回路数； （4）求图D的可达矩阵。
4、如图4-1和图4-2所示的两个图G4，G5： （1）试判断它们是否为欧拉图？并说明理由； （2）若是欧拉图，请写出一条欧拉回路；
（3）若不是欧拉图，请问至少添加几条边，能够使其成为欧拉图。
c
a b b d e a e
f j g i d c h
图4-1 G4 图4-2 G5
5、设R为实数集合，在R上定义二元运算*，?x,y?R，有
x*y?x?y?xy
（1）验证二元运算*是否满足结合律； （2）求二元运算*的单位元； （3）对实数x，求其逆元。