离散数学复习题（期末测试卷）

复习题

一、填空题（请将每空的正确答案写在答题纸相应位置处，答在试卷上不得分。每小题2分，共16分。）

1．谓词公式?x?y(P(x,y)?Q(y,z))??xR(x,y)中?x的辖域是 。 2．命题公式　(　p??q)的成真赋值为 。

3．在1和1000之间（包括1和1000在内）不能被4和5整除的数有 个。

4．设R是定义在集合A?{1,2,3,4}上的二元关系R?{?1,1?,?1,2?,?2,3?,?1,4?}，则R的对称闭包s(R)? 。

5．A?{1,2,3,4},x?y?min{x,y},则代数系统?A,??中的零元是 。 6．具有10个结点的无向完全图的边数= 。 7．一次同余方程3x??1(mod5)的最小正整数解是 。 8．84与198的最大公约数是 。

二、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共16分。）

1. 设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)) 2. 设个体域是整数集，则下列命题的真值为真的是( )。

A．?y?x(x?y?1) B．?x?y(x?y?0)

C．?x?y(x?y?y2) D．?y?x(x?y?x2)

3. 集合A?{1,2,?,10}上的关系R?{?x,y?|x?y?10,?x,y?A}，则R的性质为( )。

A、自反的 B、传递的、对称的 C、对称的 D、反自反的、传递的

4．对自然数集合N，下列定义的运算中( )是不可结合的。 A. a?b?a?b?3 B. a?b?a?2b

C. a?b?a?b(mod 3) D. a?b?min{a,b}

5．下列各图中既是欧拉图，又是汉密尔顿图的是( )。

A． B． C． D．

6．对于下列度数序列，可画成简单无向图的是( )。

A．(1，1，1，2，3) B．(1，2，2，3，4，5) C．(1，2，3，4，5，5) D．(2，3，3，4，5，6) 7. 含有5个结点、3条边的不同构的简单图有( )个。

A. 2 B. 3 C. 4 D. 5

【第 1 页 共 2 页】

8．5的模6逆等于( )。

A．1 B．3

C．4 D．5

三、计算题（第1、2、3、4小题各7分，第5、6小题各8分共44分。） 1．求命题公式(p?q)?(p?r)的主析取范式和主合取范式。

2．设?A,R?为偏序集，其中A?{1,2,3,4,6,9,24,54}，R是A上的整除关系。（1）画出?A,R?的哈斯图；（2）求A中的极大元；（3）令B?{4,6,9}，求B的上确界和下确界。 3．求下图1中带权无向图的最小生成树，并求出该最小生成树的权值。 4．求解递推方程：an?7an?1?12an?2?0,a0?4,a1?6 。 5．有向图D如图2所示，求：（1）D中v1到v3长度为3的通路有几条？（2）D中v1到v1长度为3的回路有几条？（3）D是哪类连通图？

12124536344v1v4 3 图1 图2

v2v3

6．在通讯中要传输字母a,b,c,d,e,f,g，它们出现的频率为：

a:30%,b:20%,c:15%,d:10%,e:10%,f:9%,g:6%，设计传输上述字母的最佳二元前缀码，画出最优树，并求传输100个按上述频率出现的字母所需二进制字个数。

四、证明题（每小题8分，共16分。） 1．设R为自然数集N上的关系，定义N上的关系R如下：?x,y??R?x?y是偶数。 （1）证明R为等价关系； （2）求商集N/R。 2．设Z为整数集合，在Z上定义二元运算?如下：证明：?x,y?Z,x?y?x?y?2，?Z,??是群。

五、符号化下列命题，并在自然推理系统P中论证结论的有效性（8分。）

若小张喜欢数学，则小李或小赵也喜欢数学。若小李喜欢数学，则他也喜欢物理。小张确实喜欢数学，可小李不喜欢物理。所以，小赵喜欢数学。

【第 2 页 共 2 页】

参考答案

一、填空题 （请将每空的正确答案写在答题纸相应位置处，答在试卷上不得分。每小题2分，共16分。）

1．P(x,y)?Q(y,z) 2．10，11，00 3．600

4．{?1,1?,?1,2?,?2,3?,?1,4?,?2,1?,?3,2?,?4,1?} 5．1 6．45 7．3 8．6

二、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共16分。）

1．C 2．C 3．C 4．B 5．C 6．A 7．C 8．D 三、计算题（第1、2、3、4小题各7分，第5、6小题各8分共44分。）

1．解：主合取范式为： （5分）

(p?q)?(p?r)?(?p?q)?(?p?r)?((?p?q)?(r??r))?((?p?r)?(q??q)) ?(?p?q?r)?(?p?q?r)?(?p?q?r)?(?p??q?r)?(?p?q?r)?(?p?q?r)?(?p??q?r)?M4?M5?M6 主析取范式为： （2分）

(p?q)?(p?r)?m0?m1?m2?m3?m7?(?p??q??r)?(?p??q?r)?(?p?q??r)?(?p?q?r)?(p?q?r)2．解：（1）?A,R?的哈斯图如下图所示。 （3分）

2454

426329

1

（2）A中的极大元是：24，54； ( 2分)

（3）B的上确界：无；B的下确界：1。 ( 2分) 3．解：所求该图的最小生成树如下图所示。 （5分）

121234 【第 1 页 共 3 页】

该最小生成树的权值之和

W（t）=2+1+1+2+3+4=13 （2分）

4．解：其特征方程为：x2?7x?12?0，其特征根是：x1?3,x2?4 （2分）

通解为：an?c13n?c24n （2分）

代入初值得到：c1?c2?4,3c1?4c2?6

解得：c1?10,c2??6 （2分）

所以，原方程的解为：

an?10?3n?6?4n。 （1分）

5．解：先求图D的邻接矩阵A及A2、A3。

?1?1A???0??1110??2?2011?2?，（1分） A???1001???000??1122??5?4111?3?,（2分）A???1000???110??2233?232??（2分） 110??122?(1) D中v1到v3长度为3的通路有3条。 （1分） (2) D中v1到v1长度为3的回路有5条。 （1分） (3) D是强连通图。 （1分）

6．解：按字母顺序，令pi为传输第i个字母的频率，i?1,2,?,7，则传输100个字母，

各字母出现的频数为wi?100pi，得

w1?30,w2?20,w3?15,w4?10,w5?10,w6?9,w7?6。将它们按照从小到大顺序排列，得 6?9?10?10?15?20?30。 （2分） 以wi为权求最优2叉树如下图所示。

100603015150019000130011010020402011101016

0000 （4分）

传输的前缀码分别为：a?01,b?11,c?001,d?100,e?101,f?0001,g?0000。 传100个所需二进制数字个数为：

W(t)=15+30+60+100+40+20=265。 （2分）

四、证明题（每小题8分，共16分。） 1．（1）证明：

?x?N,因为x?x?2x，2x?N且是偶数，于是?x,x??R,

因此R在N上是自反的； （1分）

【第 2 页 共 3 页】

?x,y?N,若?x,y??R,则x?y是偶数，即y?x是偶数，于是?y,x??R, 因此R在N上是对称的； （1分）

?x,y,z?N,若?x,y??R且?y,z??R,则x?y?2k1?y?z?2k2,k1,k2?Z， 于是x?z?(x?y)?(y?z)?2y?2(k1?k2?y)，进而?x,z??R,

因此R在N上是传递的； （2分）

综上所述，R是N上的等价关系。 （1分）

（2）N关于等价关系R的所有等价类为[0]R?{0,2,4,6,???}和[1]R?{1,3,5,7,???}， 则N/R?{[0]R,[1]R}。 （3分）

2．证明：显然，Z关于?是封闭的。 （1分）

对于任意x,y,z?Z，由于

(x?y)?z?(x?y?2)?z?(x?y?2)?z?2?x?y?z?4， 而 x?(y?z)?x?(y?z?2)?x?(y?z?2)?2?x?y?z?4，于是

(x?y)?z?x?(y?z)，即?满足结合律。 （2分）

（2分） ?x?Z，因为x?2?x?2?2?x?2?x，因此2是Z关于?的单位元。

?x?Z，由于4?x?Z且x?(4?x)?x?(4?x)?2?2?(4?x)?x，于是

x关于?存在逆元4?x。 （2分） 所以，?Z,??是群。 （1分）

五、符号化下列命题，并在自然推理系统P中论证结论的有效性（8分。） 解：设简单命题

p：小张喜欢数学。 q：小李喜欢数学。

r：小赵喜欢数学。 s：小李喜欢物理。 （2分） 前提：p?(q?r),q?s,p,?s 结论：r

（或写为：推理形式为 p?(q?r),q?s,p,?s?r ） （1分） 证明：

(1)q?s 前提引入 (2)?s 前提引入

（2）拒取式 （2分） (3)?q （1）

(4)p?(q?r) 前提引入 (5)p 前提引入

（5）假言推理 （2分） (6)q?r （4）

（6）析取三段论 （1分） (7)r （3）

【第 3页 共 3 页】