华中科技大学年《离散数学》期末考试试题及答案

1、判断（10）（ F ）1 是合适公式。（ T ）2 矛盾式的代入实例必为矛盾式。（ F ）3 设和是两个命题公式，若=B且B是重言式，则A是重言式。（ T ）4 (A) (B) A是B的子集。（ F ）5 设A、B和C是集合，且，则。（ F ）6 若R和S是对称的，则是对称的。（ T ）7 是良序集，则A的任何非空子集必有唯一极小元。（ T ）8 每一个良序关系必是全序关系。（ T ）9 连通的4度正则图一定没有桥。（ F ）10P阶连通图至少有 P条边。单项选择（20）（ A ）1设P：我将去镇上 Q：我有时间。命题“我将去镇上，仅当我有时间”符号化为下列表达式中的哪个。A. PQ B. Q

2、P C. PQ D. QP（ A ）2. 下列各式中不正确的是：A. x(P(x)Q(x) xP(x)xQ(x)B. x(P(x)Q(x) xP(x)xQ(x)C. 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=, , 是A. 入射B. 满射 C. 双射 D. 以上答案都不对（ A ）5 若f、g是

3、A上的双射，则A. 是双射 B. -1=f-1g-1C. 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. 若是满射，下列结论正确的是 A. f必是满射 B. f必是单射 C. g必是满射 D. g必是单射（ C ）9. 若简单连通平面图G有4个结点，3个面，则G有多少条边 A.

4、3 B. 4 C. 5 D. 2（ B ）10. 给定下列序列，可构成无向简单图的结点度序列的是 A.（1，1，2，2，3） B.（1，1，2，2，2） C.（0，1，3，3，3） D.（1，3，4，4，5）填空（14）集合A=1,2,3,4,5上的等价关系R将导致集合A的一个划分，即商集A/R=1,2,3,4,5，则R=,。一棵树有两个2度顶点，一个3 度顶点，三个4 度顶点，则该树有_9_片树叶若用谓词R(x)表示“x是实数”，L(x, y)表示“xy”，那么命题“对于任意实数x和y，若xy，则必存在实数z使得xz且z0），则有_2n_个不同的A上的即对称又反对称的关系。设集合A=a,b,

5、c,d,e,f,g,h,i上的偏序关系R的哈斯图如下图所示，abcdefghi则集合a,b,c的上界有_c, e, f, h, i ，上确界是_c_。计算与作图（共28分）设=3,6,9,15,54,90,135,180，为自然数的整除关系。画出的asse图，并求6,15,90的上、下确界。（6分）3691554901351806,15,90的上确界：90 下确界：3（上下确界各1分）（绘图4分）设A=a,b，B=1,2,3,4，f=,是A到B的函数，试找出f的所有左逆和右逆（如果存在的话）。（8分）解：是单射，非满射，有4个左逆，无右逆 g1=,g2=,g3=,g4=,试作出四个图的图示，使

6、第一个既是Euler图，又是Hamilton图；第二个是Euler图但不是Hamilton图；第三个是Hamilton图却不是Euler图；第四个既不是Euler图也不是Hamilton图。（8分）（参考答案，正确答案不唯一）0 1 00 1 01 1 0设集合A=a,b,c上的关系R的关系矩阵M (R )= 分别作出r (R )，sr(R )和tsr(R )的关系矩阵。（6分）1 1 11 1 11 1 11 1 11 1 11 1 11 1 00 1 01 1 1r (R )=sr(R )= tsr(R )=证明（共28分）用形式推理的标准格式证明：（6分）,A P (附加前提) AB T

7、 I (AB)(CD) P CD T I D T I DE T I (DE)P P P T I AP CP（格式不对酌情扣分）判断是否是重言式，并说明理由。（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；综上该公式不是永真式已知R是A上的反自反的、传递的二元关系，证明R也是反对称的。（6分）证明：假设R不是反对称的，即存在R，xy，R因为R是传递的，由R，R得R，与R反自反矛盾所以R是反对称的设G是边数m小于30的简单无向平面图，试证明：G中必存在结点v，使得结点v的度数不大于4。（8分）证明：假设G中有n个顶点，所有顶点的度数都大于等于5，则图中所有顶点度