一（6%）选择填空题。

(1) 设S = {1，2，3}，R 为S 上的二元关系，其关系图如右图所示，则R 具有（ ）的性质。

A. 自反、对称、传递；
B. 反自反、反对称；
C. 自反、传递；
D. 自反。

123
(2) 设A = {1, 2, 3, 4}， A 上的等价关系 R = {<a, b >, <b, a >, <c, d >, <d, c > } A I , 则对应于R 的A 的划分是（ ）。

A. {{a }, {b , c }, {d }}；
B. {{a , b }, {c }, {d }}；
C. {{a }, {b }, {c }, {d }}；
D. {{a , b }, {c , d }}。

二（10%）计算题。

(1) 求包含35条边，顶点的最小度至少为3的图的最大顶点数。

(2) 求如下图所示的有向图中，长度为4的通路的数目，并指出这些通路中有几条回路，几条由3v 到4v 的通路。

v 1
v 2v 3v
4
三 (14%) (1) 求 )()(p r q p →→∨ 的主析取范式,主合取范式及真值表;
(2) 求 )()),(),((x xH y x yG y x xF ∃→∃→∀⌝的前束范式。

四 (8%) 将下列命题符号化：其中 (1), (2) 在命题逻辑中，(3), (4) 在一阶逻辑中。

(1) 除非天下雨，否则他不乘公共汽车上班；
(2) 我不能一边听课，一边看小说；
(3) 有些人喜欢所有的花；
厦门大学《离散数学》课程试卷
学院 系 年级 专业
主考教师： 张莲珠，杨维玲 试卷类型：（A 卷）
(4)没有不犯错的人。

五（10%） 在自然推理系统Ｐ中构造下面推理的证明：
如果他是计算机系本科生或者是计算机系研究生，则他一定学过DELPHI 语言且学过C++语言。

只要他学过DELPHI 语言或者Ｃ++语言，那么他就会编程序。

因此如果他是计算机系本科生，那么他就会编程序。

六（10%） 在自然推理系统中构造下面推理的证明（个体域：人类）：
每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车。

有的人不喜欢骑自行车，因而有的人不喜欢步行。

七（14%） 下图给出了一些偏序集的哈斯图，判断其是否为格，对于不是格的说明理由，对于是格的说明它们是否为分配格、有补格和布尔格（布尔代数）。

八（12%） 设S = {1, 2, 3, 4, 6, 8, 12, 24}，“ ”为S 上整除关系，
(1)画出偏序集>< ,S 的哈斯图；
(2)设B = { 2, 3, 4, 6, 12}，求B 的极小元、最小元、极大元、最大元，下界，上界。

九（8%） 画一个无向图，使它是：
(1)是欧拉图，不是哈密尔顿图；
(2)是哈密尔顿图，不是欧拉图；
(3)既不是欧拉图，也不是哈密尔顿图；
并且对欧拉图或哈密尔顿图，指出欧拉回路或哈密尔顿回路，对于即不是欧拉图也不是哈密尔顿图的说明理由。

十（8%）设6个字母在通信中出现的频率如下：
%45:a %13:b %12:c
%16:d %9:e %5:f
用Huffman 算法求传输它们的最佳前缀码。

要求画出最优树，指出每个字母对应的编码，并指出传输)2(10≥n n 个按上述频率出现的字母需要多少个二进制数字。