2023年7月全國自考離散數(shù)學(xué)試題試卷真題及答案

2023年7月全國自考離散數(shù)學(xué)試題試卷真題

一、單項選擇題(本大題共15小題，每題1分，共15分)

1.下列語句中不是命題的只有()

A.雞毛也能飛上天？B.或重于泰山，或輕于鴻毛。

C.不經(jīng)一事，不長一智。D.牙好，胃口就好。

2.從真值角度看，命題公式的全部類型是()

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

3.設(shè)M(X)：x是人；F(x)：x要吃飯。用謂詞公式體現(xiàn)下述命題：全部的人都要吃飯，其中里送的體

現(xiàn)式是()

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.設(shè)論域為整數(shù)集，下列真值為真的公式是()

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.設(shè)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.非零整數(shù)集合Z*上的除法運算

B.全體nXn實可逆矩陣集合Mn(R)上的矩陣加法和乘法運算

C.全體nXn實矩陣集合M,、(R)上的矩陣加法和乘法運算

D.A={1,2,-,10},x*y=LCM(x,y),即x,y最小公倍數(shù)

10.設(shè)＜A,。，*＞是環(huán)，則下列說法不正確的是()

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

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

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

ABCD

13.下列各有向圖是強連通圖的是()

14.設(shè)G是具有n個結(jié)點的無向簡樸圖，若在G中存在一條漢密爾頓路，則G中每一對結(jié)點的度數(shù)之和與

n-1的關(guān)系為()

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

15.設(shè)連通平面圖G,共有n個結(jié)點，e條邊，r個面，則歐拉證明成立的公式是()

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

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

請在每題的空格中填上正確答案。錯填、不填均無分。

16.所謂—是指不能再分解的命題，而復(fù)合命題是由某些—經(jīng)過聯(lián)結(jié)詞復(fù)合而成的命題。

17.在命題演算中，兩個—的合取、析取、條件、雙條件均為一。

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

19.設(shè)人={1,2,3,4},R是A上的二元關(guān)系，R={<x,y>|x/y是素數(shù)},則domR=;

ranR=。

20.設(shè)無向圖G有n個結(jié)點m條邊，每個結(jié)點的度數(shù)為k或k+1,記Nk為度數(shù)等于k的結(jié)點數(shù)，則Nk=。

假如無向簡樸圖C的結(jié)點的度數(shù)均為相同的偶數(shù)，且m=7,則n=—。

21.設(shè)*={1,3,5,9,15,45),R是X上的整除關(guān)系，則R是X上的偏序，其最大元是—，極小元

是。

22.設(shè)<1、1,0,1>是有界格，a,beL,若avb=0,則a=b=；若a/\b=l,則a=b=。

23.設(shè)e是群G上的幺元，若aeG且a?=e，則,a"=。

24.代數(shù)系統(tǒng)<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.設(shè)A={a,b,c},A上二元關(guān)系R={<a,a>,<a,c>,vb,a>},用關(guān)系矩陣法求最小的自然數(shù)m,n,m<n使Rn'=Rno

29.根據(jù)下列條件假如能畫則請畫出一種歐拉圖，假如不能畫則請闡明理由。

(1)偶數(shù)個頂點，偶數(shù)條邊(2)奇數(shù)個頂點，奇數(shù)條邊

(3)偶數(shù)個頂點，奇數(shù)條邊(4)奇數(shù)個頂點，偶數(shù)條邊

30.下列各整數(shù)集合對于整除關(guān)系都構(gòu)成偏序集，判斷哪些偏序集能構(gòu)成格？并闡明理由。

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.設(shè)A={2,3,5,12,19},等價關(guān)系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.設(shè)A是一種集合，X=P(A),R是X上元素之間的涉及關(guān)系，試證明<X,R>是偏序集。(注：P(A)

為A的幕集)

五、應(yīng)用題(本大題共2小題，第35題6分，第36題9分，共15分)

35.設(shè)有n個村莊要修路，(1)若要使全部村莊之間都有通路，問需在兩村之間至少修幾條路？(2)若

要使任意兩村莊之間有一條直接的路，則至少修幾種路？(3)若修一條連接全部村莊的環(huán)路，問有多

少種修路方案？

36.設(shè)有推理：

⑶沒有不守信用的人是可信賴的；

(b)有些能夠信賴的人是受過教育的人；

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

試構(gòu)造推理的證明，要求把推理的前提，結(jié)論符號化為謂詞形式，并寫出推理過程。(個體域：人的集合)

提醒：設(shè)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分，結(jié)論正確給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）的條件不能畫歐拉圖，因為歐拉圖要求圖中結(jié)點的度數(shù)都是偶數(shù);而偶數(shù)個

結(jié)點且每個結(jié)點的度數(shù)都是偶數(shù)，則由結(jié)點所得到的總度數(shù)=偶數(shù)x偶數(shù);而

由邊數(shù)所得到的總度數(shù)=奇數(shù)x2,這樣便得到:偶數(shù)x偶數(shù)=奇數(shù)x2

消去2之后,得到：

偶數(shù)x（偶數(shù)，奇數(shù)）=奇數(shù)，矛盾（2分）

30.解答：2）,3）,4）這三個偏序集能構(gòu)成格。（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，應(yīng)是不連通的；

(2)由于無向圖G是歐拉圖，因此G中有一條歐拉回路，通過G中所有邊恰好

一次；

(3)因此無向圖G若是歐拉圖，在歐拉回路上刪去任何一條邊，得到的圖G，仍

是連通的。

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

34.證:只要證R是P(A)上的自反、反對稱和傳遞關(guān)系。(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)上的偏序關(guān)系。

五、應(yīng)用題(本大題共2小題，第35題6分，第36題9分，共15分)

35.解:以n個村莊作為圖中n個頂點。(1)要使所有村莊之間都有通路，即在n個