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

离散数学年月真题

0232420174

1、【单选题】下列命题公式为重言式的是

(P→Q)∧Q∧R

(P→¬P)→¬Q

A:

¬(Q→R)∧R

B:

((P→Q)∧(Q→R))→(P→R)

C:

答D:案：D

解析：在各种赋值下均为真的命题公式为重言式，或者称为永真式。可以通过列出每个选

项的真值表来进行判断。也可以用否定法来判断，对A选项，只要Q与R有一个为假，命

题即是假，排除A；对B选项，P为假，Q为真，命题即为假，排除B；对C选项，R为假

时，命题即为假，排除C；所以选D。

2、【单选题】命题公式A中含n个命题变项，A为矛盾式的条件是A的主合取范式含

2n个极大项

1个极大项

A:

2n个极小项

B:

1个极小项

C:

答D:案：A

解析：矛盾式没有成真赋值。每个极大项有一种成假赋值组合，因为命题公式A中含n个

命题变项，当其主合取范式恰好拥有2n个极大项时，恰好穷尽了所有赋值组合，即对A

来说，所有赋值组合都是成假的，A即是矛盾式。

3、【单选题】下列关于整数集合上的整除关系描述不正确的是

自反的

对称的

A:

反对称的

B:

传递的

C:

答D:案：B

4、【单选题】设F(x)：x是在美国的留学生，G(y):y是亚洲人。命题“并不是所有在美国

的留学生都是亚洲人”可符号化为

¬∃x(F(x)→G(x))

A:

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

¬∃x(F(x)→∀yG(y))

B:

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

C:

答D:案：B

解析：先把“所有在美国的留学生都是亚洲人”符号化为∀x(F(x)→G(x))，然后再否定

即可。

5、【单选题】关于笛卡尔积，下列陈述不正确的是

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

A×(B∩C)=(A×B)∩(A×C)

A:

P(A)×P(A)=P(A×A)

B:

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

C:

答D:案：C

解析：A、B、D选项为笛卡尔积的分配律。C选项与笛卡儿积无关。

6、【单选题】设A-B=A,则有

A∩B=

B=A

A:

B⊆A

B:

A⊆B

C:

答D:案：A

解析：A-B表示元素x在A中同时在B中，但是运算之后还是A，说明B没有起到限制作

用，即A与B没有交集。

7、【单选题】对任意集合A、B关于其幂集的下列叙述不正确的是

|P(A)|=2|A|

|P(B)|=2|B|

A:

P(A)∩P(B)=P(A∩B)

B:

P(A)∪P(B)=P(A∪B)

C:

答D:案：D

解析：A、B都是集合的幂集元素个数的计算公式。集合幂集的交集等于交集的幂集，所以

C正确。D不正确，可以验证如下。设A=｛1｝，B=｛2，3｝，则A的幂集是｛Φ，

｛1｝｝，B的幂集是｛Φ，｛2｝，｛3｝，｛2，3｝｝，它们的并集为｛Φ，｛1｝，

｛2｝，｛3｝，｛2，3｝｝。A与B的并集为｛1，2，3｝，它的幂集为｛Φ，｛1｝，

｛2｝，｛3｝，｛1，2｝，｛1，3｝，｛2，3｝，｛1，2，3｝｝。明显两者不相等。

8、【单选题】下列一阶逻辑等效变换不正确的是

A:

B:

C:

答D:案：C

解析：A、B、D为量词辖域收缩与扩张等值式，C的正确形式应该为

∀x(A(x)→B)⇔∃xA(x)→B。

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

a*b=a+b-2

a*b=a-b

A:

a*b=min⁡{a,b}

B:

a*b=ab

C:

答D:案：A

解析：群的定义要求，必须存在单位元，同时每个元素都有逆元。A选项存在单位元为

2，a逆元为4-a。其他选项都不满足。

10、【单选题】设都是双射函数，则下列性质不正确的是

A:

B:

C:

答D:案：A

解析：

A选项考核函数复合原理：两个双射函数复合的反函数等于反函数反向复合，因此应为

.其他选项都是反函数基本运算。

11、【单选题】下列的度数列，可以简单图化的是

5,5,4,4,2,1

5,4,3,2,2

A:

3,3,3,1

B:

4,4,3,3,2,2

C:

答D:案：D

解析：可图化的度数列需要满足模除2为0，即能够整除2，故排除A。B选项最大度为

5，不满足最大度小于阶数n-1的要求，C不能构成简单图。因此只能选D。

12、【单选题】一颗无向树有5片树叶，有3个2度结点，其余都是3度结点，那么这颗树

的结点数是

10

11

A:

12

B:

13

C:

答D:案：B

解析：根据无向树的定义，3个2度结点可以写成三点连一线，组成小树A，5片叶子再

与A相连则需要3个3度点，这样需要11点即可完成。

13、【单选题】设R1，R2是A上的两个二元关系，则下列描述不正确的是

A:

B:

C:

答D:案：C

解析：根据二元关系闭包的运算性质可得C为错误。

14、【单选题】下列关于欧拉图的描述正确的是

K4是欧拉图

K5是欧拉图

A:

完全图都是欧拉图

B:

K6是欧拉图

C:

答D:案：B

解析：根据欧拉图判断方法即得K5是欧拉图，欧拉图需要每个结点度数都为偶数。

15、【单选题】设X={1,2,3,6}，D是X上的整除运算，下列关于代数系统<X，D>的描述

正确的是

格

群

A:

半群

B:

二元关系

C:

答D:案：A

解析：格首先需要具有偏序关系，在X上的整除只能是偏序。

16、【问答题】

答案：{〈1，2〉，〈3，1〉，〈2，1〉}，{〈4，5〉，〈5，4〉，〈2，5〉}

解析：

按照左右复合的定义进行计算。为S对R的右复合，为S对R的左复合。

17、【问答题】命题公式(p→(Q∧R))的成真指派为_____________，成假指派为

_______________。

答案：000，001，010，011，111；100，101，110

解析：列出真值表即可得到。

18、【问答题】公式的约束变元为

___________，自由变元为________________。

答案：x，z；y

解析：凡是受到∃和∀限制的叫做约束变元，其他的微自由变元。

19、【问答题】集合A={1，2，3}上的划分共有___________种,其中划分S={{1},{2，3}}中

有序对的个数为______________。

答案：5；5

解析：集合A共有5个非空子集，所以其划分为5种。有S中两个元素{1},{2，3}组成的

有序对个数为5个。

20、【问答题】完全图K4是平面图，其面数r为__________，记节点数为n,边数为m，则

n-m+r=______________________。

答案：4；2

解析：完全图K4共4个节点，两两相连，共分割成4个面，边数为6个，所以n-m+r=4-

6+4=2。

21、【问答题】实数集R中的运算*定义如下:a*b=a+b-5ab，则*运算的单位元为

________________，*运算的零元为________________。

答案：0；1/5

解析：设单位元为e，由a*e=a有，a+e-5ae=a，解得e=0；设零元为Ɵ，由a*Ɵ=Ɵ有，

a+Ɵ-5aƟ=Ɵ，即a=5aƟ，解得Ɵ=1/5。

22、【问答题】

中，1的阶为

____________，9阶为____________。

答案：10；10

解析：群中元素a满足ak=e的最小正整数k称为该元素的阶。<Z10,+>的单位元e=0，则

可以计算出1与10的阶都是10。

23、【问答题】一个简单无向连通图，有n个结点，m条边，则边数m的最大值为

____________，边数m的最小值为____________。

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

解析：确保n个结点相连，只要一条线即可，所以边数最少为n-1；当任意两个不同点之

间都有连通线时候，边数最多，这时候恰好是无向完全图，故边数为n(n-1)/2。

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

___________。

答案：a，c，d；b，d

解析：根据格的补元定义进行判断即可。

25、【问答题】一颗n阶(n＞2)无向树T，其最大度数的最小值为

____________，的最大值为____________。

答案：2；n-1

解析：因为n＞2，因此最大度数最小值为2。根据最大度数定义可以得出无向树的最大

度数最小值为n-1。

26、【问答题】1000以内既不能被5或6整除，也不能被8整除的正整数有多少个。

答案：【解】S={x|x∈Z∧1≤x≤1000}A={x|x∈Z∧x可被5整除}B={x|x∈Z∧x可被6整

除}C={x|x∈Z∧x可被8整除}(2分)易得|A|=200（1000/5=200），|B|=166

（1000/6=166.666…），|C|=125(1000/8=125)，且|A∩B|=33，|C∩B|=41，|C∩A|=25，

|C∩B∩A|=8(2分)则根据文氏图可得，不能被5、6和8整除的数有1000-[|A|+|B|

+|C|-|A∩B|-|C∩B|-|C∩A|+|C∩B∩A|]=1000-(200+166+125-33-41-25+8）=1000-

400=600个(2分)

解析：本题解决主要是转化为集合运算。

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

答案：

解：

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

28、【问答题】

答案：

解：(1)关系图:(2)关系矩阵为

（3）R具有反自反性和反对称性，但是不具有自反性和

对称性。

解析：掌握住图的基本表示方法和基本性质即可解决。

29、【问答题】求公式(P→Q)Λ(Q→R)的主析取范式和主合取范式。

答案：

解：（1）主析取范式（3分）

（2）主合取范式（3分）由主析取范式和主合取范式之间的关系可得

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

式，特别是要把主析取范式转换成极小项形式。再求主合取范式时候，直接利用极大项与

极小项的关系进行转换，比较方便。

30、【问答题】下面是某偏序集〈A，R〉的哈斯图写出集合A和偏序关系R的表达式。

答案：解：（1）由图得出A=｛1，2，3，4，5｝（2）根据偏序关系的自反性、反对称性

和传递性，可以得出R=｛<1，3>，<3，5>，<1，5>,<2，4>，<4，5>,<2，

5>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>｝=｛<1，3>，<3，5>，<

1，5>,<2，4>，<4，5>,<2，5>｝∪IA

解析：通过偏序关系的定义与哈斯图进行反推即可得到。

31、【问答题】设

证明G关于矩

阵乘法构成一个群。

答案：

证明：（1）对矩阵乘法来说，任意矩阵，因

此为单位元e。（2分）（2）剩下三个矩阵分别记作b，c，d，利用

矩阵乘法可以验证bb=cc=dd=e，bd=db=c，cd=dc=b，bc=cb=d，可见G对矩阵乘法是封闭

的。（2分）（3）由bb=cc=dd=e可得b，c，d有逆元，其逆元都是本身。（2分）综合

（1）（2）（3），得G关于矩阵乘法满足群定义，构成一个群。（1分）

解析：根据群的定义来判定。

32、【问答题】

答案：证明：（1）因为对∀x，y∈R，f（〈x，y〉）=〈（x+y）/2，（x-y）/2〉，设有

存在〈x1，y1〉也使得f（〈x1，y1〉）=〈（x+y）/2，（x-y）/2〉，而根据f计算公式

f（〈x1，y1〉）=〈（x1+y1）/2，（x1-y1）/2〉f（〈x，y〉），则有方程组：（x+y）

/2=（x1+y1）/2，（x-y）/2=（x1-y1）/2可解得，x1=x，y1=y。可见每个象具有唯一的

原象，f为单射。（3分）（2）对于R×R上的任意〈a，b〉，可设f（〈x，y〉）=〈a，

b〉，由定义f（〈x，y〉）=〈（x+y）/2，（x-y）/2〉有方程组：（x+y）/2=a，（x-

y）/2=b可解得，x=a+b，y=a-b。根据实数的封闭性，a+b∈R，a-b∈R。即可见，值域中

每个元素都有原象，f为满射。（3分）综合（1）、（2）得出，f是一个双射函数。（1

分）

解析：根据双射函数定义，要证明双射，必须先满射单射与满射。单射与满射都按照最基

本定义来证明。

33、【问答题】设图G有n个结点，n+1条边。证明：图G中至少有一个结点度数≥3。

答案：证明：由于图G有n+1条，故G的n个结点度数之和为2（n+1）条。2（n+1）

/n=2+2/n，所以G中至少有一个结点的度数不小于3。由此可见，图G中至少有一个结点

度数≥3。(基本正确5分，完整7分)

解析：主要是考虑图的边、点与度数的关系。

34、【问答题】有向图D如图所示。求2到5的长度为2

的通路数；