是良序集，则A的任何非空子集必有唯一极小元。 （ T ）8． 每一个良序关系必是全序关系。 （ T ）9． 连通的4度正则图一定没有桥。 （ F ）10．P阶连通图至少有 P条边。 二、单项选择（20）
（ A ）1．设P：我将去镇上 Q：我有时间。命题“我将去镇上，仅当我有时间”符号化为下列表达式中的哪个。
A. P→Q B. Q→P C. P→¬Q D. Q→¬P
（ A ）2. 下列各式中不正确的是：
A. x(P(x)∨Q(x)) xP(x)∨xQ(x) C. x(P(x)∨Q(x)) xP(x)∨xQ(x)
B. x(P(x)∧Q(x)) xP(x)∧xQ(x) D. x (P(x)∧Q) x P(x)∧Q
（ C ）3．若公式A(P,Q,R)的主合取范式为∏（0，1，4，5），则公式A(P,Q,R)的主析取范式为：
A. ∑（0，1，4，5） B. ∏（0，1，4，5） C. ∑（2，3，6，7） D. ∏（2，3，6，7）
（ D ）4． 集合{1, 2, 3, 4}上的二元关系R={<1, 1>, <2, 2>, <3, 4>}是
A. 入射
B. 满射 C. 双射 D. 以上答案都不对
（ A ）5． 若f、g是A上的双射，则
A. fg是双射
B. (fg)-1 =f-1g-1
C. fggf D. 以上答案都不对
（ B ）6．任何无向图中结点间的可达关系是：
A. 偏序关系 B. 等价关系 C. 相容关系 D. 拟序关系
（ D ）7. 设R是集合A上的关系，下列结论不正确的是
A. 若R是自反的，则s (R)是自反的 B. 若R是对称的，则t (R)是对称的 C. 若R是传递的，则r (R)是传递的 D. 若R是传递的，则s (R)是传递的
（ A ）8. 若fg是满射，下列结论正确的是
A. f必是满射 B. f必是单射 C. g必是满射
D. g必是单射
（ C ）9. 若简单连通平面图G有4个结点，3个面，则G有多少条边
A. 3
B. 4
C. 5
D. 2
（ B ）10. 给定下列序列，可构成无向简单图的结点度序列的是
三、 填空（14）
1． 集合A={1,2,3,4,5}上的等价关系R将导致集合A的一个划分，即商集A/R={{1,2},{3},{4,5}}，则R={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<1,2>,<2,1>,<4,5>,<5,4>}。 2． 一棵树有两个2度顶点，一个3 度顶点，三个4 度顶点，则该树有__9_片树叶 3． 若用谓词R(x)表示“x是实数”，L(x, y)表示“xA.（1，1，2，2，3） B.（1，1，2，2，2） C.（0，1，3，3，3） D.（1，3，4，4，5）P(1,1)TP(1,2)TP(2,1)TP(2,2)。则公式
Fxy(P(x,y)P(y,x))的真值为_T__。
5． 若A是n元集合（n>0），则有__2n_个不同的A上的即对称又反对称的关系。 6． 设集合A={a,b,c,d,e,f,g,h,i}上的偏序关系R的哈斯图如下图所示，
四、 计算与作图（共28分）
1． 设Ａ={3,6,9,15,,90,135,180}，｜为自然数的整除关系。画出<Ａ;｜>的Ｈasse图，并求{6,15,90}的上、下确界。（6分）
180 h i
e c a
f
d b
g
则集合{a,b,c}的上界有_c, e, f, h, i ，上确界是__c___。
{6,15,90}的上确界：90
135 90
下确界：3 （上下确界各1分）
6 9
15 （绘图4分）
3 2． 设A={a,b}，B={1,2,3,4}，f={,}是A到B的函数，试找出f的所有左逆和右逆（如果存在的话）。（8分）解：是单射，非满射，有4个左逆，无右逆 g1={<1,a>,<2,b>,<3,a>,<4,a>} g2={<1,a>,<2,b>,<3,a>,<4,b>} g3={<1,a>,<2,b>,<3,b>,<4,a>} g4={<1,a>,<2,b>,<3,b>,<4,b>}
3． 试作出四个图的图示，使第一个既是Euler图，又是Hamilton图；第二个是Euler图但不是Hamilton图；第三个是Hamilton图却不是Euler图；第四个既不是Euler图也不是Hamilton图。（8分）
（参，正确答案不唯一）
4． 设集合A={a,b,c}上的关系R的关系矩阵M (R )=
分别作出r (R )，sr(R )和tsr(R )的关系矩阵。（6分） r (R )=
五、 证明（共28分）
1． 用形式推理的标准格式证明：（6分）
1 1 0 0 1 0 1 1 1 1 1 1 sr(R )= 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 1 0 1 1 0 tsr(R )= ABCD,DEPAP
⑴ A P (附加前提) ⑵ A∨B
T⑴ I P
⑶ (A∨B)(C∧D)
⑷ C∧D T⑵⑶ I ⑸ D T⑷ I ⑹ D∨E
T⑸ I
⑺ (D∨E)P P
⑻ P T ⑹⑺ I ⑼ AP （格式不对酌情扣分）
CP
2． 判断x(P(x)Q(x))(xP(x)xQ(x))是否是重言式，并说明理由。（8分）
不是永真式，取解释如下
D= {1,2}
P(1) P(2) Q(1) Q(2)
F T F T
在该解释下xP(x) 为T，xQ(x)为F，所以xP(x) →xQ(x)为F；而(P(1) →Q(1))
为T， (P(2) →Q(2))为T，所以x(P(x) →Q(x))为T；综上该公式不是永真式
3． 已知R是A上的反自反的、传递的二元关系，证明R也是反对称的。（6分）
证明：假设R不是反对称的，即存在R，x≠y，R 因为R是传递的，由R，R得R，与R反自反矛盾 所以R是反对称的4． 设G是边数m小于30的简单无向平面图，试证明：G中必存在结点v，使得结点v的度数不大于4。（8分）
证明：假设G中有n个顶点，所有顶点的度数都大于等于5，则图中所有顶点度数之和∑deg(v)≥5n，又∑deg(v)=2m，显然2m≥5n，又因为G是平面图，所以m≤3n-6，即2*(3n-6)≥2m≥5n，这样必须2*(3n-6)≥5n，得n≥12 又因为m<30，所以n≤2m/5 < 2*30/5=12，和n≥12矛盾 命题得证
