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

离散数学年月真题

02324201810

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

P→（P∨Q∨R）

(P→¬P)→¬Q

A:

¬（Q→R）∧R

B:

（P→Q）→(¬Q→¬P)

C:

答D:案：C

解析：本题考核命题公式及其赋值，按照矛盾式的定义，在各种赋值下均为假的命题公式

即为矛盾式，也叫做永假式。可以列出是真值表来判断，也可以运用逻辑思维来判断。利

用真值表即可以得出选择C。

2、【单选题】命题A中含有n个命题变项，A是重言式的条件是A的主析取范式含

2<>n个极大项

1个极大项

A:

2<>n个极小项

B:

1个极小项

C:

答D:案：C

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

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

3、【单选题】设R为集合A上的关系，则下列叙述不正确的是

R在A上自反当且仅当IA⊆R

R在A上反自反当且仅当IA∩R=ϕ

A:

R在A上对称当且仅当R=R-1

B:

R在A上反对称当且仅当R∩R-1=ϕ

C:

答D:案：D

解析：本题考核二元关系的五种性质的充分必要条件定理，根据这个定理判断可见，R在

A上反对称当且仅当R∩R-1=IA，故D错误。

4、【单选题】设F（x）:x是兔子，G（y）:y是乌龟，H（x,y）:x比y跑得快。命题“并

不是所有兔子都比乌龟跑得快”可符号化为

¬∃x(F(x)∧∀y(G(y)→H(x,y)))

¬∀x∀y(F(x)∧G(y)→H(x,y))

A:

¬∃x∃y(F(x)∧G(y)→H(x,y))

B:

¬∀x(F(x)∧∃y(G(y)→H(x,y)))

C:

答D:案：B

解析：本题考核一阶逻辑命题的符号化，其中“所有”对应着全称量词“∀”，“并不

是”表示逻辑非，“兔子都比乌龟跑得快”与“x比y跑得快”对应，是蕴含关系，且兔

子和乌龟是逻辑与的关系，因此组成答案B。

5、【单选题】设集合X={a,{a}}，则下列陈述不正确的是

{a}∈X

{a}⊆X

A:

{a,{a}}⊆X

B:

{a,{a}}∈X

C:

答D:案：D

解析：根据集合的运算，可以看出{a,{a}}是原集合的子集，不是元素，因此不是属于关

系，应该是包含关系，因此{a,{a}}⊆X才是正确的。注此题选项为不正确的选项为D

6、【单选题】对非空集合A和B，若A∩B=A，则有

A-B=ϕ

B-A=ϕ

A:

B=ϕ

B:

A=ϕ

C:

答D:案：A

解析：根据集合的运算，若A∩B=A，则A⊂B，因此必然有A-B=ϕ，BCD显然与非空集合要

求不相符。

7、【单选题】设A={1,{1},{1,{1}}}，则其幂集P（A）的元素总个数为

1

4

A:

8

B:

16

C:

答D:案：C

解析：根据，幂集是全体子集组成的集合，主要是要分清楚集合A有3个元素，则幂集个

数为2<>n=2<>3=8个。

8、【单选题】描述偏序集的是

哈密顿图

哈斯图

A:

欧拉图

B:

树

C:

答D:案：B

解析：画出偏序关系的关系图，即是哈斯图。ACD都是图论的理论，其中哈密顿图是有哈

密顿回路的图，欧拉图是具有欧拉回路的图，树是连通无回路的无向图。故选B。

9、【单选题】在整数集Z上，下列定义的运算能构成一个群的是

a*b=max{a,b}

a*b=|a-b|

A:

a*b=a+b+1

B:

a*b=ab

C:

答D:案：C

解析：按照群的定义，在整数集合上，运算是可结合的，存在单位元，每个元素都是逆

元，则是一个群。显然只有C选项满足以上要求，其单位元为-1，a的逆元是-2-a。因

此，选C。

10、【单选题】设f:X→Y，g:Y→Z是函数，则下列陈述不正确的是

若f和g都是单射的，这f°g也是单射的

若f和g都是双射的，这f°g也是双射的

A:

若g和f°g是满射的，这f也是满射的

B:

若f和g都是满射的，这f°g也是满射的

C:

答D:案：C

解析：根据函数复合的定理来判断即可，都是单射就保持单射，都是双射就保持双射，都

是满射就保持满射。

11、【单选题】由4阶3条边构成的无向简单图的结点最大度数为

1

2

A:

3

B:

C:

4

答D:案：C

解析：图的阶数是图的结点个数，也就是该图有4个结点，简单图是不存在平行边与环的

图，因此三条边与结点连接的最大可能就是集中一点，即是三边都与某一结点连接，这个

结点度数最大，为3。因此选C。

12、【单选题】下列为一颗6阶无向树的度数列，对应不止一颗同构树的是

1,1,1,1,2,4

1,1,1,2,2,3

A:

1,1,2,2,2,2

B:

1,1,1,1,3,3

C:

答D:案：B

解析：无向树是连通无回路的无向图，简称树，根据树的性质，6阶即6个结点，则树的

边数为6-1=5条，然后根据各个选项的度数列，画出树，即可发现B可以有两种画法：度

数为3的结点可以取在5个连接结点的第三个（五个并排结点的中间一个）位置，也可以

是第二或者四个（五个并排结点的中间一个的前一个或后一个）位置。因此选B。

13、【单选题】设有集合A、B、C，则下列描述不正确的是

(A∪B)∪C=A∪(B∪C)

A∪(B∩C)=(A∪B)∩(A∪C)

A:

A∩(B∪C)=(A∩B)∪(A∩C)

B:

A-(B∩C)=(A-B)∩(A-C)

C:

答D:案：D

解析：按照集合的基本运算规律，即可得出D是不正确的。

14、【单选题】下列关于整数集合上的小于关系性质描述不正确的是

反自反的

对称的

A:

反对称的

B:

传递的

C:

答D:案：B

解析：整数集合上的小于关系是二元关系，根据二元关系的性质及整数的排序性质，可以

得出其具有反自反性、反对称性和传递性，显然不正确的选择B.

15、【单选题】分别记Z、N、Q、R为整数、自然数、有理数、实数集合，下列关于普通加

法的代数系统不是群的是

​​<'Z，+><z，+></z，+><z，+></z，+><z，+></z，+><z，+><

/z，+><z，+></z，+><z，+></z，+><z,+></z,+>

A:

<'N，+><n，+></n，+><n，+></n，+><n,+></n,+>

<'Q，+><q，+></q，+><q，+></q，+><q,+></q,+>

B:

​<'R，+><r，+></r，+><r，+></r，+><r,+></r,+>

C:

答D:案：B

解析：按照，在整数集合上，运算是可结合的，存在单位元，每个元素都是逆元，则是一

个群。对上面选项进行验证，发现只有B不是群，因此选B。

16、【问答题】集合A={1,2,3,4,5}，集合B={a,b,c,d,e},现有从A到B的二元关系R={<

1,b>,<3,e>,<5,e>}，和从B到A的二元关系S={<b,4>,<a,5>,<e,2>}，则

R°S=__________，S°R=_______________。

答案：{<1,4>}，{<a,e>}

解析：根据二元关系复合的计算方法，<1,b>与<b,4>复合即得出{<1,4>}，<a,5>

与<5,e>的复合得出{<a,e>}。

17、【问答题】命题公式（¬P→Q）→（P∧¬Q）的成真指派为_________，成假指派为

______________。

答案：00、10；01、11

解析：根据命题公式中P，Q不同取值列出真值表，即可得出其成真指派和成假指派。

18、【问答题】公式（∃x）（（P（x,y）→Q（z））

R（z））的约束变元为

_______，自由变元为_______。

答案：x，y、z

解析：根据一阶逻辑符号化的概念及全称量词与存在量词，可以判断约束变元为x，而自

由取值没有被约束的为y、z。

19、【问答题】设A={a,b}，B={1,2,3,}，则|A×B|=_________，|A×P（B）

|=_________。

答案：6，16

解析：根据笛卡尔积的定义，笛卡尔积是指的二元有序对组成的集合，显然上述两个集合

构成的笛卡尔积共有元素为2×3=6个；P(B)表示B的幂集，是B的所有子集组成集合，

其元素有2n=2³=8个，于是A×P(B)的元素个数为2×8=16个。

20、【问答题】设实数集合上的函数f（x）=x²，g（x）=2x+1，那么复合函数fºg（x）

=______，反函数g-1（x）=_______。

答案：1+2x²；(x-1)/2

解析：根据函数的复合与反函数的定义即可得出。

21、【问答题】有理数Q中的运算*定义如下：a*b=a+b+ab，则运算*的单位元为

________；设a有逆元，则其逆元a-1为____________。

答案：0；-a/(a+1)

解析：根据二元运算及其性质计算。设运算*的单位元e，则有

a*e=a⇔a+e+ae=a⇔e(1+a)=0⇔e=0；运算*的逆元a<>-1，这有a*a<>-1=e⇔a+a<>-

1+aa<>-1=0⇔a<>-1=-a/(a+1)

22、【问答题】

答案：6；3

解析：

23、【问答题】设5阶简单连通图G所有结点的度数之和为18，则G的结点的最大度数为

_________，最小度数为_______。

答案：4，3

解析：根据简单连通图的性质，其度数之和恰等于边数之和的两倍，因此边数为9条，5

阶说明有5个顶点，这样在保证连通的要求下，可以画出图形结构，就会看到其结点的最

大度数为4，最小度数为3。

24、【问答题】下图的格中，b的补元是_________，c的补元是______________。

答案：a,cb,d

解析：由图可见该格L为有界格，1为其全上界，0为其全下界。如果<L,∧,∨,0,1>是有

界格,a∈L,若存在b∈L,使得a∧b=0和a∨b=1成立,则称b是a的补元。按照以上定

义，我们可以看到b的补元是a,c；c的补元是b,d。

25、【问答题】设二元关系A={<2,5>,<3,5>,<3,4>}，B={<1,3>,<2,5>,<

3,4>}，那么dom（A∩B）=_______，ran（A∪B）=________。

答案：{2,3}，{3,4,5}

解析：先计算出A∩B={<2,5>,<3,4>}，A∪B={<2,5>,<3,5>,<3,4>,<1,3>}，

然后再求定义域dom(A∩B)={2,3}，值域ran(A∪B)={3,4,5}。

26、【问答题】研究4阶完全图K4，判断其是否存在欧拉回路？是否存在哈密顿回路？如果

存在，共有多少个非同构的回路？

答案：对与4阶完全图K<>4，每个结点的度数均为3，为奇数，因而不存在欧拉回路。4

阶完全图K_4中存在哈密顿回路。而且存在3个不同构的哈密顿回路。

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

恰有4个结点。一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图

是连通图。从图中的任意一点出发，路途中经过图中每一个结点当且仅当一次，则成为哈

密顿回路。根据以上欧拉回路与哈密顿回路的定义与性质，则可以判断出解的结论。

27、【问答题】构造命题公式（P→¬Q）∧R的真值表。

答案：

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

28、【问答题】给出集合A={1,2,3}上所有等价关系的个数，并列出这些关系的集合表达

式。

答案：

解析：在集合A上建立的二元关系符合自反的、对称的、传递的，此关系是等价的。显然

恒等关系I<>A满足以上要求。再根据自反、对称和传递要求，我们可以得出其他组合，

这个组合与恒等关系I<>A取并集，即得到结论。

29、【问答题】求命题公式¬（P∨（Q∧R））的主析取范式和主合取范式

答案：

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

式，最后要把主析取范式转换成极小项形式。主合取范式可以借助极小项与极大项关系来

确定

30、【问答题】集合A={a,b,c,d,e}上有偏序关系R={<a,d>,<a,c>,<a,b>,<a,e>,<

b,e>,<c,e>,<d,e>}∪IA（1）画出偏序集<A,R>的哈斯图；（2）找出A的极大元、

极小元、最大元和最小元。

答案：

解析：按照哈斯图的作图规则：（1）以“圆圈”表示元素；（2）若x≤y,则y画在x的

上层；（3）若y覆盖x,则连线；（4）不可比的元素可画在同一层。即可做出哈斯图。再

根据极大元、极小元、最大元和最小元的定义就可以得出结论。

31、【问答题】设Z是整数集合，在Z上定义二元运算*如下：∀x,y∈Z,x*y=x+y-2证明Z

关于运算*构成群。

答案：证明：∀x,y∈Z,x*y=x+y-2∈Z，因而*运算是封闭的。显然，*运算可结合，且单

位元e=2。∀a∈Z,由（a*a<>-1）=a+a<>-1-2=e=2可得a<>-1=4-a即任一元素均存在逆

元。综上，Z关于运算*构成群。

解析：判断某集合和运算能不能构成群，主要是根据群的定义研究其封闭性、可结合性、

单位元、逆元，都满足要求即是群。

32、【问答题】设集合A={<a,b>|a,b为正整数}，在A上定义二元关系~如下：<a,b>~<c,d>

当且仅当a+d=b+c。证明~是一个等价关系。

答案：证明：（1）自反性对∀<a,b>∈A，有a+b=a+b，所以<a,b>~<a,b>。故~具有自反

性。（2）对称性设<a,b>~<c,d>，则有a+d=b+c，亦即c+b=d+a，所以<c,d>~<a,b>。故~

具有对称性。（3）传递性设<a,b>~<c,d>且<c,d>~<e,f>，则有a+d=b+c，c+f=e+d，上述

两式两边分别相加后消去c+d，从而a+f=b+e。所以<a,b>~<e,f>。故~具有传递性。综合

（1）（2）（3），~是一个等价关系。

解析：证明二元关系中的等价关系，主要是从定义出发，满足自反性、对称性和传递性。

33、【问答题】在9阶无向图G中，每个结点的度数不是5就是6，证明G中至少有5个6

度结点或至少有6个5度结点。

答案：证明：（1）假设G中至少有5个6度结点，则结论成立。（2）如果G中至多只

有4个6度结点，由于每个结点的度数不是5就是6，则至少有5个度数为5的结点，而

奇度数结点不能为奇数个，因而这时G中度数为5的结点应当有6个或者8个，即至少有

6个5度结点。综合（