离散数学 期末考试卷 B卷

东莞理工学院城市学院（本科）试卷（B卷）

2013-2014学年第一学期

开课单位：计算机与信息科学系 ，考试形式： 闭 卷，允许带 入场

科目：离散数学，班级： 软工本2012-1、2、3 姓名： 学号：

题序 得分 评卷人 一 二 三 四 总 分 一、单项选择题（每小题2分，共20分）

在每小题列出的四个备选项中只有一个是符合题目要求的，错选、多选或未选均无分。 1．下列语句中不是命题的只有（

A．鸡毛也能飞上天？

）

B．或重于泰山，或轻于鸿毛。 D．牙好，胃口就好。

C．不经一事，不长一智。

2．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（ ）

A．?P∧Q

B．P∧?Q

C．P→?Q ）

D．P∨?Q

3．下列命题公式不是永真式的是（

A．Q→（P∨Q） B．（P∧Q）→P

C．?(P∧?Q) ∧（?P∨Q） D．（P→Q）?（?P∨Q） 4．给定命题公式：（?P? Q）?（P? R），与之逻辑等价的是 (

A．P?（? Q?R）

B．P?（Q?R） D． P?（Q?R）

)

C．?P?（Q?R）

5．设A（x）:x是人，B（x）：x犯错误，命题“没有不犯错误的人”符号化为（ ）

A． ?x(A(x))∧B(x) C． ??x( A(x)∧B(X))

6．命题“所有的马都比某些牛跑得快”的符号化公式为（

）

B． ??x( A(x) →?B(x) ) D． ??x( A(x) ∧?B(x) )

假设：H（x）：x是马，C（y）：y是牛，F（x，y）：x跑得比y快。

《离散数学》B卷 第1页 共6页

A．(?x) (H（x）? ( ?y)( (C（y）? F(x,,y))) B．(?x) (H（x）? ( ?y)( (C（y）? F(x,,y))) C．(?x) (H（x）? ( ?y)( (C（y）? F(x,,y))) 7．下列公式是前束范式的是（ A．(?x)(?y)(?F(z,x)?G(y)) C．(?x)F(x,y)?(?y)G(y)

）

B．(?(?x)F(x)?(?y)G(y))?H(z) D．(?x)(F(x,y)?(?y)G(x,y))

D．( ?y) (?x) (H（x）? ( (C（y）? F(x,,y)))

8．下面的图是A=｛1,2,3｝上关系R的关系图G(R), 从G(R)可判断R所具有的性质是(

A.自反，对称，传递

B.反自反，非对称

D.反自反，对称，反对称，传递

）

2。 3。 )

1。 C.反自反，对称，非传递

9.设集合A={1，2，3}，下列关系R中不是等价关系的是（

A.R={(1,1),(2,2),(3,3)}

B.R={(1,1),(2,2),(3,3),(3,2),(2,3)}

C.R={(1,1),(2,2),(3,3),(1,2)} D.R={(1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1),(2,3),(3,2)}

）

10．下面关于关系R的传递闭包t (R)的描述最确切的是（

A．t(R)是包含R的二元关系

B．t(R)是包含R的最小传递关系 D．t(R)是任何包含R的传递关系

C．t(R)是包含R的一个传递关系 二、填空题（每空2分，共20分）

请在每小题的空格中填上正确答案。错填、不填均无分。

1．设全集E??1,2,3,4,5,6,7,8,9,10?的子集为A??2,4,6,8,10?，B??1,3,5,7,9?， A?B? ，~A?~B?

2．设集合X??1,2,3?，设关系R为X上的小于关系，则R= 3．设A??a,b,c?上的二元关系R={，，，}，则关系R具备

性质。

4．设A?{1,2,3},B??a,b?,C?{x,y,z},f:A?B,g:A?C的函数，且有

f???1,a?,?2,b?,?3,b??,g???1,x?,?2,y?,?3,z??,则f是 《离散数学》B卷 第2页 共6页

函数，

g是 函数。

的集合。

。

5．一个无向图表示为G=，其中V是结点的集合，E是 6．一个连通无向图G是欧拉图，当且仅当G中所有结点的度数为 7．公式(p?q)?(r?s)的真值表中共有 种真值指派（赋值组合）。

8．给定命题公式：P ?（?P?（Q?(? Q?R)）则它的成假指派（成假赋值）为 。

三、计算题（每小题8分，共48分） 要求写出详细计算过程，按步给分。

1、求命题公式 ( P→ (Q∨R) ) → ?Q的主析取范式和主合取范式。。

2．设集合A??1,2,3,4?，R和S均为A上的二元关系，且R???1,2?,?3,4??,

S???2,3?,?4,1??，分别求关系的合成R○S，S○R，R○S○R，S○R○S

《离散数学》B卷 第3页 共6页

3．设A??a,b,c,d?上的二元关系R={，，，}，用集合形式求R的自反闭包、对称闭包和传递闭包，并用关系图的形式表示三个闭包。

4．设赋权无向连通图G如下，求G的最小生成树，并求该最小生成树的权总和。

V1

5 V2 5 3 6 4 2 5 3 V4 1 V3 V5

6 V6

《离散数学》B卷 第4页 共6页

5．用Huffman算法画出树叶权为3, 5, 8, 10, 12的最优二叉树（要求画出最优树的形成过程），计算出该最优树的权，并给出哈夫曼编码。

6．给定一棵树（如图），试分别用前序周游算法、中序周游算法和后序周游算法写出运算表达式。

+ * a b d e

《离散数学》B卷 第5页 共6页

* + / f c

四、证明题（共12分）

用命题逻辑推理方法证明下面推理的有效性：

如果我学习，那么我离散数学不会不及格。如果我不热衷于玩游戏，那么我将学习。但是我离散数学不及格。因此，我热衷于玩游戏。

《离散数学》B卷 第6页 共6页

本文来源：https://www.bwwdw.com/article/l3cv.html