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

离散数学年月真题

0232420234

1、【单选题】设p:今天晴天，q:我们去放风筝，命题“今天要是晴天，我们就去放风

筝。”的符号化为

p→q

p→¬q

A:

q→p

B:

¬q→p

C:

答D:案：A

2、【单选题】下列命题公式是矛盾式的是

pΛ(p→q)

¬(p→q)Λq

A:

pΛ(pq)

B:

pV(pq)

C:↔

↔

答D:案：B

3、【单选题】下列式子不正确的是

∀xA(x)V∀xB(x)⇒∀x(A(x)VB(x))

∃xA(x)⋀∃xB(x)⇒∃x(A(x)⋀B(x))

A:

∃x(A(x)⋀B(x))⇒∃xA(x)⋀∃xB(x)

B:

∃xA(x)→∀xB(x)⇒∀x(A(x)→B(x))

C:

答D:案：B

4、【单选题】设命题公式A含有2个命题变元，且已知A为矛盾式，则A的主合取范式含大

项的个数为

2

3

A:

4

B:

1

C:

答D:案：C

5、【单选题】设A={1,2,3},A上的二元关系R={<1,2>,<2,3>,<3,2>,则R具有

自反性

A:

反自反性

对称性

B:

反对称性

C:

答D:案：B

6、【单选题】设A={1,2,3},A上的二元关系

R={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<3,1>,<3,3>},则R是

相容关系

等价关系

A:

偏序关系

B:

全序关系

C:

答D:案：A

7、【单选题】设A={1,2,3,4},B={5,6,7},给定f={<1,6>,<2,7>,<3,5>,<4,6>},则下列选项

中，正确的是

f不是从A到B的函数

f是单射函数

A:

f是满射函数

B:

f是双射函数

C:

答D:案：C

8、【单选题】设集合A有2个元素，则A×A的所有不同的等价关系的个数是

4

8

A:

12

B:

15

C:

答D:案：D

9、【单选题】设是布尔代数，∀x∈B,x⋀x'=

Φ

B

A:

0

B:

1

C:

答D:案：C

10、【单选题】正整数集上二元运算*封闭的是

x*y=|x-y|

x*y=x-y

A:

x*y=x/y

B:

x*y=x+2y

C:

答D:案：D

11、【单选题】设S={0,1,2,5},则代数系统中∪运算的幺元是

0

1

A:

Φ

B:

S

C:

答D:案：C

12、【单选题】设是代数系统，*和°是二元运算，如果*和°满足交换律，结合律和吸收

律，则构成一个

环

域

A:

格

B:

布尔代数

C:

答D:案：C

13、【单选题】下列是自补图的是

A:

B:

C:

答D:案：C

14、【单选题】设一棵树的结点个数为2020，则此树中的割边数为

2018

2019

A:

2020

B:

2021

C:

答D:案：B

15、【单选题】在有6个顶点12条边的连通简单平面图中，所围成每个面的边数为

3

4

A:

5

B:

6

C:

答D:案：A

16、【填空题】两个不同大项的析取式的真值是（）。

答案：T

17、【填空题】设论域的元素为a和b,则由消去量词可得∀xA(x)⋀∃yB(y)⇔（）。

答案：(A(a)⋀A(b))⋀(B(a)⋁B(b))

18、【填空题】公式∀x(A(x)⋀∃yB(y))→C(x)中∃y的辖域是（）。

答案：B(y)

19、【填空题】设A={1,2,3},R={<1,2>,<2,2>,<3,2>},S={<2,1>},则(R°S)-1=（）。

答案：{<1,1>,<1,2>,<1,3>}

20、【填空题】设A={1,2,3},B={a,b},则从A到B的所有不同满射函数的个数有（）个。

答案：6

21、【填空题】设R是实数集，在R上定义二元运算*，∀x,y∈R,x*y=x+y+2xy,则的幺元为

（）。

答案：0

22、【填空题】设是一个格，则公式aVb≤b的对偶公式是（）。

答案：a⋀b≥b

23、【填空题】无向图G为欧拉图，当且仅当G是连通的，且G中无（）数度顶点。

答案：奇

24、【填空题】5阶非同构的树共有（）棵。

答案：3

25、【填空题】一棵高度为5的正则3叉树中叶结点的个数为（）。

答案：81

26、【简答题】用真值表法判定命题公式(pV¬q)→(q⋀r)是否为非重言式的可满足式。

答案：

27、【简答题】用等值演算法求命题公式(p→q)Λr的主析取范式。

答案：(p→q)⋀r⇔(¬p⋁q)⋀r⇔(¬p⋀r)⋁(q⋀r)

⇔(¬p⋀q⋀r)⋁(¬p⋀→q⋀r)⋁(p⋀q⋀r)⇔m⋁m⋁m₇由此可得(p→q)⋀r的主析

取范式为m⋁m⋁m₇

₁₃

₁₃

28、【简答题】设集合A={1,2,3}上的二元关系R={<1,3>,<3,2>,<2,1>},写出自反闭包r(R),

对称闭包s(R)和传递闭包t(R)的集合表达式。

答案：r(R)=R∪IA={<1,3>,<3,2>,<2,1>,<1,1>,<2,2>,<3,3>}s(R)=R∪R-

1={<1,3>,<3,1>,<3,2>,<2,3>,<2,1>,<1,2>}

t(R)=R∪R²∪R³={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}

29、【简答题】画出A={2,4,8,12,24}上整除关系的哈斯图，并求B={4,8,12}的极大元、极

小元。

答案：

30、【简答题】利用Kruskal算法求图示的连通带权图的最小生成树，请给出详细过程并画

出最小生成树，求出最小生成树的权。

答案：

31、【简答题】设A={1,2,3},R为A×A上的二元关系，∀,∈AxA,R⇔x+y=u+v(1)证明R

为等价关系；(2)求R导出的等价类。

答案：A×A={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}(1)因为

∀∈A×A,x+y=x+y,从而R,即R具有自反性;∀,∈A×A,R,则x+y=u+v,从而u+v=x+y,

故R,即R具有对称性;∀,,∈A×A,R,R,则x+y=u+v,u+v=m+n,从而x+y=m+n,故R,即

R具有传递性;综上,R是A×A上的等价关系。(2)R导出五个等价类

为:[<1,1>]R={<1,1>},[<1,2>]R={<1,2>,<2,1>}，

[<1,3>]R={<1,3>,<2,2>,<3,1>},[<2,3>]R={<2,3>,<3,2>},[<3,3>]R={<3,3>}

32、【简答题】设有向图D如题32图所示，

(1)写出图D的邻接矩阵MD;

(2)计算图D中长度为4的通路数；

(3)计算图D中长度小于或等于4的回路数。

答案：

33、【简答题】用二叉树表示算术表达式(a*(b+c))÷(g+(h-i)),并给出该树的先序、中

序、后序遍历序列。

答案：

34、【证明题】证明：正有理数集Q+,关于普通乘法运算构成交换群。

答案：(1)满足封闭性:Va,b∈Q+,则有a*b∈Q+(2)满足结合律:∀a,b,c∈Q+,则有

(a*b)*c=abc=a*(b*c)(3)存在幺元1:∀a∈Q+,有1*a=a*1=a(4)每个元素都存在逆

元:∀a∈Q+,有a*a-1=a-1*a=1,且a-1∈Q+,故a的逆元为a-1。(5)满足交换

律:∀a,b∈Q+,有a*b=ab=ba=b*a综上所述,正有理数集