2023年7月全国自考离散数学试题试卷真题及答案

2023年7月全国自考离散数学试题试卷真题

一、单项选择题(本大题共15小题，每题1分，共15分)

1.下列语句中不是命题的只有()

A.鸡毛也能飞上天？B.或重于泰山，或轻于鸿毛。

C.不经一事，不长一智。D.牙好，胃口就好。

2.从真值角度看，命题公式的全部类型是()

A.永真式B.永假式C.永真式，永假式D.永真式，永假式，可满足式

3.设M(X)：x是人；F(x)：x要吃饭。用谓词公式体现下述命题：全部的人都要吃饭，其中里送的体

现式是()

A.(Vx)(M(x)->F(x))B.-nC3x)(M(x)A-.F(x))

C.(3x)(M(x)vF(x))D.(Vx)(「M(x)vF(x))

4.下列公式是前束范式的是(

A.(Vx)(Vy)KF(z,x)vG(y))B.(T3x)F(x)v(Vy)G(y))AH(Z)

C.0x)F(x,y)f(XZy)G(y)D.(>x)(F(x,y)f(Vy)G(x,y))

5.设论域为整数集，下列真值为真的公式是()

A.(Vx)(3y)(x-y=0)B.(3y)(Vx)(x-y=0)

C.(Vx)(Vy)(x-y=0)D.-<3x)-<3y)(x-y=0)

6.下列是谓词演算中的合式公式的是()

A.(Vx)(p(x)—>3y)B.(3x)F(x)AG(X,y)C.(Vx)P(x,y)Q(y,z)D.(Vx)->xAP(X,y)

7.设A=|01,B=P(P(A)),以下正确的式子是()

A.IH0LH0III｝包含于B

B.|H,0｝包含于B

C.10,10,101｝｝包含于B

D.|0,f0,||0|||｝包含于B

8.下列式子正确的是()

A.(A-B)-C=A-(BUC)B.A-(BUC)=(A-B)UC

C.~(A-B)=~(B-A)D.~(AAB)cA

9.下列集合对所给的运算是封闭的只有()

A.非零整数集合Z*上的除法运算

B.全体nXn实可逆矩阵集合Mn(R)上的矩阵加法和乘法运算

C.全体nXn实矩阵集合M,、(R)上的矩阵加法和乘法运算

D.A={1,2,­,10},x*y=LCM(x,y),即x,y最小公倍数

10.设＜A,。，*＞是环，则下列说法不正确的是()

A.＜A,。＞是互换群B.＜A,*＞是半群

C.*对。是可分配的D.④对*是可分配的

11.下列四个格，是分配格的是()

ABCD

13.下列各有向图是强连通图的是()

14.设G是具有n个结点的无向简朴图，若在G中存在一条汉密尔顿路，则G中每一对结点的度数之和与

n-1的关系为()

A.不小于B.不小于等于C.等于D.不不小于

15.设连通平面图G,共有n个结点，e条边，r个面，则欧拉证明成立的公式是()

A.e-n+r=2B.n+r-e=2C.n-r+e=2D.n-e-r=2

二、填空题(本大题共10小题，每题2分，共20分)

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

16.所谓—是指不能再分解的命题，而复合命题是由某些—经过联结词复合而成的命题。

17.在命题演算中，两个—的合取、析取、条件、双条件均为一。

18.使公式Qx)0y)(A(x)AB(y))o0x)A(x)AGy)B(y)成立的条件是中不含y,__中不含x。

19.设人={1,2,3,4},R是A上的二元关系，R={<x,y>|x/y是素数},则domR=;

ranR=。

20.设无向图G有n个结点m条边，每个结点的度数为k或k+1,记Nk为度数等于k的结点数，则Nk=。

假如无向简朴图C的结点的度数均为相同的偶数，且m=7,则n=—。

21.设*={1,3,5,9,15,45),R是X上的整除关系，则R是X上的偏序，其最大元是—，极小元

是。

22.设<1、1,0,1>是有界格，a,beL,若avb=0,则a=b=；若a/\b=l,则a=b=。

23.设e是群G上的幺元，若aeG且a?=e，则,a"=。

24.代数系统<A,。>,其中A为命题公式集合,。为析取运算v,贝kA,。>中零元素是一，幺元是一。

25.树是不涉及的一图。

三、计算题(本大题共6小题，第26、27题各4分，第28、29题各5分，第30、31题各6分，共30分)

26.假如论域是集合{a,b,c},试消去下面公式中的量词：(Vx)0y)(x+y=O)

27.求公式(pvq)f(qAr)的主析取范式。

28.设A={a,b,c},A上二元关系R={<a,a>,<a,c>,vb,a>},用关系矩阵法求最小的自然数m,n,m<n使Rn'=Rno

29.根据下列条件假如能画则请画出一种欧拉图，假如不能画则请阐明理由。

(1)偶数个顶点，偶数条边(2)奇数个顶点，奇数条边

(3)偶数个顶点，奇数条边(4)奇数个顶点，偶数条边

30.下列各整数集合对于整除关系都构成偏序集，判断哪些偏序集能构成格？并阐明理由。

1)L={123,4,5)2)L={1,2,3,6,12}

3)L={1,2,3,4,6,9/2』8,36}4)L={1,2,22,23,-,2n)

31.设A={2,3,5,12,19},等价关系R={<x,y>|x,yeAAx三y(mod3)},写出各元素的等价类，并求

A/Ro

四、证明题(本大题共3小题，第32、33题各6分，第34题8分，共20分)

32.用等价变换法证明：(P-Q)f((RfQ)f((PvR)-Q))是永真式。

33.若无向图G是欧拉图，G中是否存在割边？为何？

34.设A是一种集合，X=P(A),R是X上元素之间的涉及关系，试证明<X,R>是偏序集。(注：P(A)

为A的幕集)

五、应用题(本大题共2小题，第35题6分，第36题9分，共15分)

35.设有n个村庄要修路，(1)若要使全部村庄之间都有通路，问需在两村之间至少修几条路？(2)若

要使任意两村庄之间有一条直接的路，则至少修几种路？(3)若修一条连接全部村庄的环路，问有多

少种修路方案？

36.设有推理：

⑶没有不守信用的人是可信赖的；

(b)有些能够信赖的人是受过教育的人；

⑹所以有些受过教育的人是守信用的。

试构造推理的证明，要求把推理的前提，结论符号化为谓词形式，并写出推理过程。(个体域：人的集合)

提醒：设F(x)表达x是守信用的人；G(x)表达x是可信赖的人；H(x)表达x是受过教育的人。

一、单项选择题(本大题共15小题,每小题1分，共15分)

1.A2.D3.C4.A5.A6.B7.C8.A9.C10.D

11.C12.C13.D14.B15.B

二、填空题(本大题共10小题,每小题2分，共20分)

16.原子命题原子命题17.永真式永真式

18.A(x)B(y)19.domR={2,3,4jranR=[1,2]

20.(k+1)n-2m721.451

22.0123.ae

24.永真式永假式25.回路连通

三、计算题(本大题共6小题，第26、27题各4分，第28、29题各5分，第30、31题各6分，共

30分)

26.解:原式o(3y)(a+y=0)A(3y)(b+y)=0A(3y)(c+y)=0)(2分)

«=>[(a+a=0)V(a+b=0)V(a+c=0)]A[(b+a=0)V(b+b=0)V(b+c=

0)]A[(c+a=0)V(c+b=0)V(c+c=0)](2分)

27.解:原式o](pVq)V(qAT)

<=>(lpAlq)V(qAr)(1分)

O((1pAlq)A(rVlr))V((pVlp)AqAr)(1分)

<=>(lpAlqAr)V(lpAlqAlr)V(pAqAr)V(lpAqAr)

0VmJVm3V叫(2分)

注:若用真值表法,真值表正确给2分，结论正确给2分。

_1or

28.解:100(1分)

00.

ri011ri0■10in

MR2-MR,MR0000101(i分)

Lo0OJLo00..00oj

ri011Ifl011rio

000101(1分)

Lo00JL000..000J

32

MR,=MR3R=R,

m=2,n=3（2分）

29.解：（1）（2）（4）可以画出欧拉图:

（3分）

（3）的条件不能画欧拉图，因为欧拉图要求图中结点的度数都是偶数;而偶数个

结点且每个结点的度数都是偶数，则由结点所得到的总度数=偶数x偶数;而

由边数所得到的总度数=奇数x2,这样便得到:偶数x偶数=奇数x2

消去2之后,得到：

偶数x（偶数，奇数）=奇数，矛盾（2分）

30.解答：2）,3）,4）这三个偏序集能构成格。（2分）

理由：由下图（2）（3）（4）中任二个元索之间有最小上界和最大下界。

36

（4分，每个图各1分）

31.解:R=|〈2,5〉，〈5,2〉，〈3,12〉，〈12,3〉[LHA（1分）

[2]R=[5JH=）2,5|（1分）

[3]R=[12]„={3,12|（1分）

[19]R=|19J（1分）

A/R=|[2]R,[3]R,[19]H|=||2,5|,|3,12|,|19||（2分）

四、证明题(本大题共3小题，第32、33题各6分，第34题8分，共20分);

32.原式O[(PTQ)V((R-Q)一((PVR)TQ))

O(PA1Q)V(1(R-Q)V((PVR)TQ))

B(PA1Q)V(](1RVQ)Vl(PVR)VQ)

«=>(PA1Q)V(RA1Q)V1((PVR)A1Q)

0((PVR)A1Q)V1((PVR)A〕Q)

评分标准:每步1分。

33.解:若无向图C是欧拉图，则G中不存在割边；(2分)

因为：

(1)若G中有一条边是割边,那么删去该割边后得到的图G，应是不连通的；

(2)由于无向图G是欧拉图，因此G中有一条欧拉回路，通过G中所有边恰好

一次；

(3)因此无向图G若是欧拉图，在欧拉回路上删去任何一条边，得到的图G，仍

是连通的。

(4)所以C中不存在割边。(4分)

34.证:只要证R是P(A)上的自反、反对称和传递关系。(I分)

(1)证R是自反的。

VBeP(A),显然〈B,B〉eR。(2分)

(2)证R是反对称的。

VB,CeP(A)

<B,C>eRA(C,B)eR<=^BCCACCB=5.B=C(2分)

(3)证R是传递的。

VB,C,DeP(A)

<B,C>eRA<C,D>eR<=>BCCACCD=>BCD<^(B,D)eR(3分)

故R是P(A)上的偏序关系。

五、应用题(本大题共2小题，第35题6分，第36题9分，共15分)

35.解:以n个村庄作为图中n个顶点。(1)要使所有村庄之间都有通路，即在n个