2018年4月自考02324离散数学试题及答案含解析

离散数学年月真题

0232420184

1、【单选题】令p：天下大雨，q：小王迟到。命题“除非天下大雨，否则小王不会迟到”

的符号化形式为

p→q

q→p

A:

¬p→q

B:

¬q→p

C:

答D:案：B

解析：本题考核的是自然语言的必要条件叙述方式，可以把代有连接副词的命题转化为普

通的“如果，则”结构的蕴涵式即可。“除非天下大雨，否则小王不会迟到”等价于“如

果小王迟到了，则天下大雨了”，即“q→p”，因此选择B。

2、【单选题】令F(x):x是实数，G(x):x是有理数。命题“实数不全是有理数”的符号化形

式为

∀x(F(x)→G(x))

∀x(F(x)∧G(x))

A:

¬∀x(F(x)→G(x))

B:

¬∀x(F(x)∧G(x))

C:

答D:案：C

解析：先把“所有实数都是有理数”符号化为∀x(F(x)→G(x))，然后再否定即可。

3、【单选题】设A是含n(n≥1)个命题变项的公式，若A是重言式，则A的主析取范式含极

小项个数为

0

1

A:

n

B:

2n

C:

答D:案：D

解析：根据极小项的定义，由于每个命题变项在极小项中以原形或者否定式形式出现且仅

出现一次，因而n个命题变项共可产生2n个不同的极小项。

4、【单选题】下列图中，是欧拉图的为

A:

B:

C:

答D:案：C

解析：根据欧拉图的定义及判定定理，欧拉图是通过所有边一次且仅有一次行遍所有顶点

的通路的图，其判定为当且仅当为连通图时，没有奇度顶点。因此只能选C。

5、【单选题】无向图G=<V，E>，在V上定义关系R：∀v、w∈V，如果存在一条v到w的路

径，则vRw。则关系R为

等价关系

偏序关系

A:

全序关系

B:

恒等关系

C:

答D:案：A

解析：根据二元关系中等价关系的定义与无向图的应用，即可知用无向图可以表示等价关

系，故选择A。

6、【单选题】简单无向图G有16条边，每个结点都是2度结点，则G的结点数为

8

14

A:

B:

16

18

C:

答D:案：C

解析：根据无向图的边与结点度数的握手定理：各顶点度数之和等于边数的两倍，即可以

得到：边数16×2倍=2度×m个，因此结点数m=16，选C。

7、【单选题】下列谓词恒等式，不正确的是

A:

B:

C:

答D:案：C

解析：

本题主要考察一阶逻辑等值式与置换规则等内容，选项C为量词辖域收缩与扩张等值式的

应用，正确的应该为。

8、【单选题】下列度数序列中，不能构成简单无向图的是

{1，1，1，2，3}

{1，3，3，3}

A:

{2，2，2，2，2}

B:

{3，3，3，3}

C:

答D:案：B

解析：如果构成的图是简单无向图，则满足：度数最大值≤n-1，即满足小于数量减一，

可见上述选项都满足。但是B中，设结点为v1，v2，v3，v4，其对应度数分别为1，3，

3，3；由于v1度数为1，则v1仅能其余三者之一相邻，那么v2，v3，v4就不可能都是3

度顶点，这是相互矛盾的，因此B选项不能构成简单无向图。

9、【单选题】对于完全图Kn(n≥3)，结点按字母标定，如果字母顺序不同即作为不同回

路，那么Kn中哈密顿回路个数为

n

n(n-1)

A:

B:

2n

(n-1)!

C:

答D:案：D

解析：完全图是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。n阶

完全图中哈密顿回路的条数为：（n-1)!/2，又字母顺序不同即作为不同回路，那么Kn中

哈密顿回路个数为（n-1)!。

10、【单选题】集合A上的对称关系R的关系矩阵为M，则M的元素必定

对角线上全是0

对角线上全是1

A:

关于对角线对称

B:

关于反对角线对称

C:

答D:案：C

解析：对称关系的关系矩阵表示恰好是对称矩阵。

11、【单选题】在自然数集合N上，可结合的运算是

a*b=a-b

a*b=max⁡(a,b)

A:

a*b=a+2b

B:

a*b=|a-b|

C:

答D:案：B

解析：可结合的运算即是满足结合律的运算，根据自然数计算性质，可以得出只有B满足

结合律。因此只能选B。

12、【单选题】要从完全图K5中得到一颗生成树，需要删除的边数为

5

6

A:

7

B:

10

C:

答D:案：B

解析：由完全图得到生成树的方法：n阶完全图，删去(n-1)(n-2)/2条边变树，即可得到

要删除的边数为6。

13、【单选题】设R、S是集合A上的两个偏序关系，则仍然是偏序关系的为

R-S

A:

B:

C:

答D:案：D

解析：首先明确偏序关系是自反性的、反对称性的和传递性的，然后按照二元关系的运算

分别讨论各个选项的性质，发现只有D选项为满足自反的、反对称的和传递的，故选D。

14、【单选题】下图中4个偏序集的图形，不能构成格的是

A:

B:

C:

答D:案：C

解析：格的定义：偏序集中任意两个元素组成的集合都有上确界和下确界。根据格定义即

可判断C不能构成格。

15、【单选题】设f是从实数集合R到R的函数，则不是双射函数f(x)的是

x3

x2

A:

2x+1

B:

xex

C:

答D:案：B

解析：既是满射函数又是单射函数才是双射函数，即一一映射，可见只有B不满足一一映

射。

16、【问答题】设R=｛<x,y>|x,y∈Z+∧gcd⁡(x,y)=2∧lcm(x,y)=12｝，其中Z+是正整数

集合，gcd⁡(x,y)表示x,y的最大公约数，lcm⁡(x,y)表示x、y的最小公倍数，则R的元素

_________。

答案：〈2，12〉，〈4，6〉

解析：按照二元关系的定义和正整数集合中最大公约数与最小公倍数定义进行计算。显

然，2和12满足要求，又有2=1×2，12=1×2×2×3，根据质因数组合，则可以得到4和

6也满足。

17、【问答题】

答案：A=B=D=F，C=E=G

解析：根据集合的定义、性质和交并补相等计算，特别还是元素的唯一性及无序性来判

断。

18、【问答题】

答案：

解析：

根据二元关系的计算规则，

19、【问答题】设有集合A和B，|A|=5，|B|=2，则从A到B不同的满射函数共有_________

个。

答案：30

解析：根据函数的定义及性质，满射是像集B都有用排列组合知识，从A到B的映射个数

为25=32个，其中不是满射的有2个，即所有A都映射为B中一个元素的情况共有2个。

因此，从A到B不同的满射函数共有30个。

20、【问答题】在正整数域中，命题公式∀x∃y(x∙y=0)的真值为，命题公式∃x∀y(x∙y=1)

的真值为_________。

答案：F，F

解析：命题公式∀x∃y(x∙y=0)表示在正整数域内，对任意一个x都有一个y使得x∙y=0，

显然这是不可能的，所以为F。命题公式∃x∀y(x∙y=1)表示对存在一个x使得任意一个y

满足x∙y=1，也是不可能的，故为F。

21、【问答题】无向图G有11条边，4个3度结点，其余均为5度结点，则G的阶数为，其

中5度结点有_______个。

答案：6，2

解析：无向图的握手原理：度数之和等于边数的两倍。因此，设5度结点有x个，那么

3×4+5x=11×2，解得x=2，故阶数是图的结点数为6，5度结点为2个。

22、【问答题】一颗无向树T，有40个1度结点，20个2度结点，31个3度结点，无6度

或以上结点，则T中有________个4度结点，__________个5度结点。

答案：2，1

解析：无向树的边数等于结点数-1，所以设有x个4度结点，y个5度结点，那么根据图

的握手定理：度数之和等于边数的两倍，可得方程：

40×1+20×2+31×3+4x+5y=(40+20+31+x+y-1)×2，解得2x+3y=7，则x=2，y=1即是。

23、【问答题】设A为非空有限集合，P(A)为A的幂集，∩为集合的交运算，则群<P(A)，

∩>的单位元是________，零元是________。

答案：

A，

解析：幂集是集合所有子集的集合，含有全集A和∅，根据单位元的定义：存在一个θ使

得∀x∈P(A)满足θ∩x=x，则满足要求的只有A。同理，按照零元的定义，则有零元为

∅。

24、【问答题】一个n阶(n>2)简单非连通图的边的最大个数是_________。

答案：(n-1)(n-2)/2

解析：可以借助完全图来进行解决。完全图是简单无向图，每对不同的顶点之间都恰连有

一条边相连，那么n阶完全图的边数为n(n-1)/2，要改造成为非连通图，则只需要至少制

造出一个孤立结点即可，即去掉n-1条边，于是可得n(n-1)/2-(n-1)=(n-1)(n-2)/2，故

一个n阶(n>2)简单非连通图的边的最大个数是(n-1)(n-2)/2。

25、【问答题】若含n(n≥2)个命题变项的命题公式A的主合取范式包括k个极大项，则A

的主析取范式必定包括_________个极小项。

答案：2n-K

解析：根据一个命题的主合取范式的极大项与其主析取范式的极小项之和为2n即可得。

26、【问答题】用列真值表的方法说明下列逻辑等价式成立

答案：

解：分别列出两个命题公式的真值表如下：

从真值

表可见，P→(Q→R)与(P→Q)→(P→R)的真值完全相同，因此有

.

解析：按照P、Q、R的赋值情况依次计算列表即可。

27、【问答题】求命题公式(Q∧(¬P→(Q∨¬(Q→R))))的主析取范式。

答案：

解析：主要利用蕴涵式向析取式和合取式的转化规则，把公式化成主析取范式和主合取范

式，最后要把主析取范式转换成极小项形式。

28、【问答题】根据关系的性质，填写下表（具备某项性质填写“√”，不具备填写

“×”）。请将下表绘制在答题卡中并作答。

答案：

解：根据所列关系性质，填表如下：

解析：参照二元关系中自反性、对称性、传递性的主要定义，根据恒等与小于关系的运算

性质即可。

29、【问答题】画出下列集合关于整除关系的哈斯图：{1,2,3,4,6,8,12,24}并指出它的

极小元，极大元，最小元，最大元。

答案：

解：根据整除关系及哈斯图规范，画出哈斯图如下图所示：由上图

所示的哈斯图可见，该整除关系偏序集的极小元是1，极大元是24。其最小元是1，最大

元是24。

解析：整除关系是典型的偏序关系，按照哈斯图的画法规则，把顶点排序，然后从最小的

1开始，y覆盖x就把y放在x上面并连接y与x，依次即可画出哈斯图。再根据极小元、

极大元、最小元和最大元的定义来判断各自的取值即可。

30、【问答题】30．有向图D如题30图所示，回答以下问题：（1）写出D的邻接矩阵

A；（2）D中长度为2、3、4的通路各有多少条？其中回路分别为多少条？

答案：

由此可知，D中长

度为1的通路有8条，长度为2的通路有11条，长度为3的通路有14条，长度为4的通

路有17条；D中长度为1的回路有1条，长度为2的回路有3条，长度为3的回路有1

条，长度为4的回路有3条。

解析：

根据图形写出邻接矩阵，然后利用邻接矩阵的幂次与通路、回路的数量关系进行计算即

可。邻接矩阵次幂得到的矩阵的所有元素之和为其所有通路的数量，对角线之和为

所有回路之和。

31、【问答题】设R、S都是A上的二元关系，证明：dom(R∪S)=dom(R)∪dom(S)。

答案：

解析：根据二元关系定义域的定义，讨论任意一个属于R∪S的元素，利用逻辑运算方法

得出R∪S的定义域等于各自定义域的并。

32、【问答题】证明下列谓词公式为永真式∀y(∀xA(x)→A(y))。

答案：

易见这是一个永真式。所

以，谓词公式∀y(∀xA(x)→A(y))为永真式。

解析：利用谓词等值式的一般形式展开即可看到前后项是相同的，因此是永真式。

3