第一篇：離散數(shù)學(xué)試卷2

離散數(shù)學(xué)試題（2）

一、單項選擇題(本大題共15小題，每小題1分，共15分)在每小題列出的四個選項中只有一個選項是符合題目要求的，請將正確選項前的字母填在題后的括號內(nèi)。

1.一個連通的無向圖G，如果它的所有結(jié)點的度數(shù)都是偶數(shù)，那么它具有一條()

A.漢密爾頓回路B.歐拉回路

C.漢密爾頓通路D.初級回路

2.設(shè)G是連通簡單平面圖，G中有11個頂點5個面，則G中的邊是()

A.10B.12C.16D.1

43.在布爾代數(shù)L中，表達(dá)式(a∧b)∨(a∧b∧c)∨(b∧c)的等價式是()

A.b∧(a∨c)

B.(a∧b)∨(a’∧b)

C.(a∨b)∧(a∨b∨c)∧(b∨c)

D.(b∨c)∧(a∨c)

4.設(shè)i是虛數(shù)，·是復(fù)數(shù)乘法運算，則G=<{1,-1,i,-i},·>是群，下列是G的子群是()

A.<{1},·>B.〈{-1},·〉

C.〈{i},·〉D.〈{-i},·〉

5.設(shè)Z為整數(shù)集，A為集合，A的冪集為P(A),+、-、/為數(shù)的加、減、除運算，∩為集合的交

運算，下列系統(tǒng)中是代數(shù)系統(tǒng)的有()

A.〈Z，+，/〉B.〈Z，/〉

C.〈Z，-，/〉D.〈P(A)，∩〉

6.下列各代數(shù)系統(tǒng)中不含有零元素的是()

A.〈Q，*〉Q是全體有理數(shù)集，*是數(shù)的乘法運算

B.〈Mn(R),*〉,Mn(R)是全體n階實矩陣集合，*是矩陣乘法運算

C.〈Z，?〉，Z是整數(shù)集，?定義為x?xy=xy,?x,y∈Z

D.〈Z，+〉，Z是整數(shù)集，+是數(shù)的加法運算

7.設(shè)A={1,2,3}，A上二元關(guān)系R的關(guān)系圖如下：

R具有的性質(zhì)是

A.自反性

B.對稱性

C.傳遞性

D.反自反性

8.設(shè)A={a,b,c}，A上二元關(guān)系R={〈a,a〉，〈b,b〉〈,a,c〉}，則關(guān)系R的對稱閉包S(R)是()

A.R∪IAB.RC.R∪{〈c,a〉}D.R∩IA

9.設(shè)X={a,b,c},Ix是X上恒等關(guān)系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R為X上的等價關(guān)系，R應(yīng)取()

A.｛〈c,a〉，〈a,c〉｝B.{〈c,b〉，〈b,a〉}

C.{〈c,a〉，〈b,a〉}D.{〈a,c〉，〈c,b〉}

10.下列式子正確的是()

A.?∈?B.???C.{?}??D.{?}∈?

11.設(shè)解釋R如下：論域D為實數(shù)集，a=0,f(x,y)=x-y,A(x,y):x

()

A.(? x)(?y)(?z)(A(x,y))→A(f(x,z),f(y,z))

離散數(shù)學(xué)試題（2）

B.(?x)A(f(a,x),a)

C.(?x)(?y)（A(f(x,y),x))

D.(?x)(?y)(A(x,y)→A(f(x,a),a))

12.設(shè)B是不含變元x的公式，謂詞公式(?x)(A(x)→B)等價于()

A.(?x)A(x)→BB.(?x)A(x)→B

C.A(x)→BD.(?x)A(x)→(?x)B

13.謂詞公式(?x)(P(x,y))→(?z)Q(x,z)∧(?y)R(x,y)中變元x()

A.是自由變元但不是約束變元

B.既不是自由變元又不是約束變元

C.既是自由變元又是約束變元

D.是約束變元但不是自由變元

14.若P：他聰明；Q：他用功；則“他雖聰明，但不用功”，可符號化為()

A.P∨QB.P∧┐QC.P→┐QD.P∨┐Q

15.以下命題公式中，為永假式的是()

A.p→(p∨q∨r)B.(p→┐p)→┐p

C.┐(q→q)∧pD.┐(q∨┐p)→(p∧┐p)

二、填空題(每空1分，共20分)

16.在一棵根樹中，僅有一個結(jié)點的入度為______，稱為樹根，其余結(jié)點的入度均為______。

17.A={1,2,3,4}上二元關(guān)系R={〈2，4〉，〈3，3〉，〈4，2〉}，R的關(guān)系矩陣MR中

m24=______,m34=______。

18.設(shè)〈s,*〉是群，則那么s中除______外，不可能有別的冪等元；若〈s,*〉有零元，則|s|=______。

19.設(shè)A為集合，P(A)為A的冪集，則〈P(A)，是格，若x,y∈P(A),則x,y最大下界是______，?〉

最小上界是______。

20.設(shè)函數(shù)f:X→Y,如果對X中的任意兩個不同的x1和x2，它們的象y1和y2也不同，我們說f

是______函數(shù)，如果ranf=Y，則稱f是______函數(shù)。

21.設(shè)R為非空集合A上的等價關(guān)系，其等價類記為〔x〕R。?x,y∈A，若〈x,y〉∈R，則 〔x〕R與〔y〕R的關(guān)系是______，而若〈x,y〉?R，則〔x〕R∩〔y〕R=______。

22.使公式(?x)(?y)(A(x)∧B(y))?(?x)A(x)∧(?y)B(y)成立的條件是______不含有y，______不含有x。

23.設(shè)M(x):x是人，D(s):x是要死的，則命題“所有的人都是要死的”可符號化為(?x)______,其中量詞(?x)的轄域是______。

24.若H1∧H2∧?∧Hn是______，則稱H1,H2,?Hn是相容的，若H1∧H2∧?∧Hn是______，則稱H1,H2,?Hn是不相容的。

25.判斷一個語句是否為命題，首先要看它是否為，然后再看它是否具有唯一的。

三、計算題(共30分)

26.(4分)設(shè)有向圖G=(V,E)如下圖所示，試用鄰接矩陣方法求長度為2的路的總數(shù)和回路總數(shù)。

27.(5)設(shè)A={a,b},P(A)是A的冪集，?是對稱差

運算，可以驗證

是群。設(shè)n是正整數(shù)，求({a}-1{a})n?{a}-nn{a}n

28.(6分)設(shè)A={1,2,3,4,5},A上偏序關(guān)系

R={〈1，2〉，〈3，2〉，〈4，1〉，〈4，2〉，〈4，3〉，〈3，5〉，〈4，5〉}∪IA;

(1)作出偏序關(guān)系R的哈斯圖

(2)令B={1,2,3,5}，求B的最大，最小元，極大、極小元，上界，下確界，下界，下確界。

29.(6分)求┐(P→Q)?(P→┐Q)的主合取范式并給出所有使命題為真的賦值。

30.(5分)設(shè)帶權(quán)無向圖G如下，求G的最小生成樹T及T的權(quán)總和，要求寫出解的過程。

31.(4分)求公式┐((?x)F(x,y)→(?y)G(x,y))∨(?x)H(x)的前束范式。

四、證明題(共20分)

32.(6分)設(shè)T是非平凡的無向樹，T中度數(shù)最大的頂點有2個，它們的度數(shù)為k(k≥2),證明T

中至少有2k-2片樹葉。

33.(8分)設(shè)A是非空集合，F(xiàn)是所有從A到A的雙射函數(shù)的集合，?是函數(shù)復(fù)合運算。證明：〈F, ?〉是群。

34.(6分)在個體域D={a1,a2,?，an}中證明等價式：

(?x)(A(x)→B(x))?(?x)A(x)→(?x)B(x)

五、應(yīng)用題(共15分)

35.(9分)如果他是計算機系本科生或者是計算機系研究生，那么他一定學(xué)過DELPHI語言而

且學(xué)過C++語言。只要他學(xué)過DELPHI語言或者C++語言，那么他就會編程序。因此如果他是計算機系本科生，那么他就會編程序。請用命題邏輯推理方法，證明該推理的有效結(jié)論。

36.(6分)一次學(xué)術(shù)會議的理事會共有20個人參加，他們之間有的相互認(rèn)識但有的相互不認(rèn)識。但對任意兩個人，他們各自認(rèn)識的人的數(shù)目之和不小于20。問能否把這20個人排在圓桌旁，使得任意一個人認(rèn)識其旁邊的兩個人?根據(jù)是什么?

參考答案

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

1.B2.D3.A4.A5.D

6.D7.D8.C9.D10.B

11.A12.A13.C14.B15.C

二、填空題

16.0

117.10

18.單位元1

19.x∩yx∪y

20.入射滿射

21.［x］R=［y］R

22.A(x)B(y)

23.(M(x)→D(x))M(x)→D(x)

24.可滿足式永假式(或矛盾式)

25.陳述句真值

三、計算題

??1100?

26.M=??1010??

?1011?

??

?0011??

?2110?

M2?=??2111??

?2121?

??

?1011??

4?M2ij?18,i???4Mij2?6 1j?1i?

1G中長度為2的路總數(shù)為18，長度為2的回路總數(shù)為6。

27.當(dāng)n是偶數(shù)時，?x∈P(A),xn=?

當(dāng)n是奇數(shù)時，?x∈P(A),xn=x

于是：當(dāng)n是偶數(shù)，(｛a｝-1｛b｝｛a｝)n?｛a｝-n｛b｝n｛a｝n

=??(｛a｝-1)n｛b｝n｛a｝n=?????

當(dāng)n是奇數(shù)時，(｛a｝-1｛b｝｛a｝)n?｛a｝-n｛b｝n｛a｝n

=｛a｝-1｛b｝｛a｝?(｛a｝-1)n｛b｝n｛a｝n

=｛a｝-1｛b｝｛a｝?｛a｝-1｛b｝｛a｝=?

28.(1)偏序關(guān)系R的哈斯圖為

(2)B的最大元：無，最小元：無；

極大元：2，5，極小元：1，3下界：4，下確界4；

上界：無，上確界：無

29.原式?(┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(P→Q))

((P→Q)∨(P→┐Q))∧(┐(P→┐Q)∨┐(P→Q))

(┐P∨Q∨┐P∨┐Q)∧(┐(┐P∨┐Q)∨(P∧┐Q))

(┐(P∧┐Q)∨(P∧┐Q))

(P∧Q)∨(P∧┐Q)

P∧(Q∨┐Q)

P∨(Q∧┐

Q)

(P∨Q)∧(P∨┐Q)

命題為真的賦值是P=1,Q=0和P=1,Q=1

30.令e1=(v1,v3),e2=(v4,v6)

e3=(v2,v5),e4=(v3,v6)

e5=(v2,v3),e6=(v1,v2)

e7=(v1,v4),e8=(v4,v3)

e9=(v3,v5),e10=(v5,v6)

令ai為ei上的權(quán)，則

a1

取a1的e1∈T,a2的e2∈T,a3的e3∈T,a4的e4∈T,a5的e5∈T,即，T的總權(quán)和=1+2+3+4+5=1

531.原式?┐(?x1F(x1,y)→?y1G(x,y1))∨?x2H(x2)(換名)

?┐?x1?y1(F(x1,y)→G(x,y1))∨?x2H(x2)

??x1?y1┐(F(x1,y1)→G(x,y1))∨?x2H(x2)

??x1?y1?x2(┐(F(x1,y1)→G(x,y1))∨H(x2)

四、證明題

32.設(shè)T中有x片樹葉，y個分支點。于是T中有x+y個頂點，有x+y-1 條邊，由握手定理知

T中所有頂點的度數(shù)之的x?y

?d(vi)=2(x+y-1)。

i?

1又樹葉的度為1，任一分支點的度大于等于

2且度最大的頂點必是分支點，于是

x?y

?d(vi)≥x·1+2(y-2)+k+k=x+2y+2K-

4i?1

從而2(x+y-1)≥x+2y+2k-4

x≥2k-2

33.從定義出發(fā)證明：由于集合A是非空的，故顯然從A到A的雙射函數(shù)總是存在的，如A

上恒等函數(shù)，因此F非空

(1)?f,g∈F,因為f和g都是A到A的雙射函數(shù)，故f?g也是A到A的雙射函數(shù)，從而集

合F關(guān)于運算?是封閉的。

(2)?f,g,h∈F,由函數(shù)復(fù)合運算的結(jié)合律有f?(g?h)=(f?g)?h故運算?是可結(jié)合的。

(3)A上的恒等函數(shù)IA也是A到A的雙射函數(shù)即IA∈F,且?f∈F有IA?f=f?IA=f,故IA是〈F，?〉中的幺元

(4)?f∈F,因為f是雙射函數(shù)，故其逆函數(shù)是存在的，也是A到A的雙射函數(shù)，且有f?f-1=f-1

?f=IA,因此f-1是f的逆元

由此上知〈F，?〉是群

34.證明(?x)(A(x)→B(x))? ?x(┐A(x)∨B(x))

?(┐A(a1)∨B(a1))∨(┐A(a2)∨B(a2))∨?∨(┐A(an)∨B(an)))?(┐A(a1)∨A(a2)∨?∨┐A(an)∨(B(a1)∨B(a2)∨?∨(B(an))?┐(A(a1)∧A(a2)∧?∧A(an))∨(┐B(a1)∨B(a2)∨?∨(B(an))?┐(?x)A(x)∨(?x)B(x)?(?x)A(x)→(?x)B(x)

五、應(yīng)用題

35.令p：他是計算機系本科生

q：他是計算機系研究生

r：他學(xué)過DELPHI語言

s:他學(xué)過C++語言

t:他會編程序

前提：(p∨q)→(r∧s),(r∨s)→t

結(jié)論：p→t

證①pP(附加前提)

②p∨qT①I

③(p∨q)→(r∧s)P(前提引入)

④r∧sT②③I

⑤rT④I

⑥r(nóng)∨sT⑤I

⑦(r∨s)→tP(前提引入)

⑧tT⑤⑥I

36.可以把這20個人排在圓桌旁，使得任一人認(rèn)識其旁邊的兩個人。根據(jù)：構(gòu)造無向簡單圖G=,其中V={v1,v2,?，V20}是以20個人為頂點的集合，E中的邊是若任兩個人vi和vj相互認(rèn)識則在vi與vj之間連一條邊。?Vi∈V,d(vi)是與vi相互認(rèn)識的人的數(shù)目，由題意知?vi,vj∈V有d(vi)+d(vj)?20,于是G

中存在漢密爾頓回路。

設(shè)C=Vi1Vi2?Vi20Vi1是G中一條漢密爾頓回路，按這條回路的順序按其排座位即符合要求。

第二篇：離散數(shù)學(xué)試卷1（范文）

離散數(shù)學(xué)試題（1）

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

在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。

1．下列是兩個命題變元p，q的小項是（）

A．p∧┐p∧qB．┐p∨q

C．┐p∧qD．┐p∨p∨q

2．令p：今天下雪了，q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號化為（）

A．p→┐q

C．p∧q

B．p∨┐q D．p∧┐q B．x+y=10 D．x mod 3=2 3．下列語句中是命題的只有（）A．1+1=10C．sinx+siny<0

4．下列等值式不正確的是（）

A．┐(?x)A?(?x)┐A

B．(?x)(B→A(x))?B→(?x)A(x)

C．(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x)

D．(?x)(?y)(A(x)→B(y))?(?x)A(x)→(?y)B(y)

5．謂詞公式(?x)P(x,y)∧(?x)(Q(x,z)→(?x)(?y)R(x,y,z)中量詞?x的轄域是（）

A．(?x)Q(x,z)→(?x)(?y)R(x,y,z))

B．Q(x,z)→(?y)R(x,y,z)

C．Q(x,z)→(?x)(?y)R(x,y,z)

D．Q(x,z)

6．設(shè)R為實數(shù)集，函數(shù)f：R→R，f(x)=2x，則f是（）

A．滿射函數(shù)

C．雙射函數(shù)B．入射函數(shù) D．非入射非滿射

7．設(shè)A={a,b,c,d}，A上的等價關(guān)系R={,,,}∪IA，則對應(yīng)于R的A的劃

分是（）

A．{{a},{b,c},lhzhsse}B．{{a,b},{c},ubmd4an}

C．{{a},,{c},tq7arte}D．{{a,b},{c,d}}

8．設(shè)A={?}，B=P(P(A))，以下正確的式子是（）

A．{?,{?}}∈B

C．{{?},{{?}}}∈BB．{{?,?}}∈B D．{?,{{?}}}∈B

9．設(shè)X，Y，Z是集合，一是集合相對補運算，下列等式不正確的是（）

A．(X-Y)-Z=X-(Y∩Z)

B．(X-Y)-Z=(X-Z)-Y

C．(X-Y)-Z=(X-Z)-(Y-Z)

D．(X-Y)-Z=X-(Y∪Z)

10．設(shè)*是集合A上的二元運算，稱Z是A上關(guān)于運算*的零元，若（）

A．?x?A,有x*Z=Z*x=Z

B．Z?A，且?x?A有x*Z=Z*x=Z

C．Z?A，且?x?A有x*Z=Z*x=x

D．Z?A，且?x?A有x*Z=Z*x=Z

離散數(shù)學(xué)試題（1）

11．在自然數(shù)集N上，下列定義的運算中不可結(jié)合的只有（）

A．a(chǎn)*b=min(a,b)

B．a(chǎn)*b=a+b

C．a(chǎn)*b=GCD(a,b)(a,b的最大公約數(shù))

D．a(chǎn)*b=a(mod b)

12．設(shè)R為實數(shù)集，R={x|x∈R∧x>0}，*是數(shù)的乘法運算，是一個群，則下列集

合關(guān)于數(shù)的乘法運算構(gòu)成該群的子群的是（）

A．{R中的有理數(shù)}

+C．{R中的自然數(shù)}

A．是交換群 +++

B．{R中的無理數(shù)} D．{1，2，3} B．是加法群 D．*對?是可分配的 +13．設(shè)是環(huán)，則下列正確的是（）C．?對*是可分配的14．下列各圖不是歐拉圖的是（）

15．設(shè)G是連通平面圖，G中有6個頂點8條邊，則G的面的數(shù)目是（）

A．2個面B．3個面

C．4個面D．5個面

第二部分非選擇題（共85分）

二、填空題（本大題共10小題，每空1分，共20分）

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

16．一公式為之充分必要條件是其析取范式之每一析取項中均必同時包含一命題變元及其否定；一公式為之充分必要條件是其合取范式之每一合取項中均必同時包含 一命題變元及其否定。

17．前束范式具有形式(Q1V1)(Q2V2)?(QnVn)A，其中Qi(1≤i≤n)為，A為的謂詞公式。

18．設(shè)論域是{a,b,c}，則(?x)S(x)等價于命題公式；(?x)S(x)等價于命題公式。

19．設(shè)R為A上的關(guān)系，則R的自反閉包。

20．某集合A上的二元關(guān)系R具有對稱性，反對稱性，自反性和傳遞性，此關(guān)系R，其關(guān)系矩陣是。

21．設(shè)是一個偏序集，如果S中的任意兩個元素都有和，則稱S關(guān)于≤

構(gòu)成一個格。

22．設(shè)Z是整數(shù)集，在Z上定義二元運算*為a*b=a+b+a·b，其中+和·是數(shù)的加法和乘法，則代數(shù)系統(tǒng)的幺元是，零元是。

23．如下平面圖有2個面R1和R2，其中deg(R1)=，deg(R2)=。

24．無向圖G具有一條歐拉回路，當(dāng)且僅當(dāng)G是。

25．在下圖中，結(jié)點v2的度數(shù)是，結(jié)點v5的度數(shù)是。

三、計算題（本大題共6小題，第26—27小題每小題4分，第28、30小題每小題5分，第29、31小題每小題6分，共30分）

26．（4分）求出從A={1,2}到B={x,y}的所有函數(shù)，并指出哪些是雙射函數(shù)，哪些是滿射函

數(shù)。

27．（4分）如果論域是集合{a,b,c}，試消去給定公式中的量詞：(?y)(?x)(x?y?0)。

28．（5分）設(shè)A={a,b,c }，P（A）是A的冪集，?是集合對稱差運算。已知

是群。

在群

中，①找出其幺元。②找出任一元素的逆元。③求元素x使?jié)M足{a}?x=。

29．（6分）用等值演算法求公式┐(p→q)?

?(p→┐q)的主合取范式

30．（5分）畫出5個具有5個結(jié)點5條邊的非同構(gòu)的無向連通簡單圖。

31．（6分）在偏序集中，其中Z={1,2,3,4,6,8,12,14}，≤是Z中的整除關(guān)系，求集合D={2,3,4,6}的極大元，極小元，最大元，最小元，最小上界和最大下界。

四、證明題（本大題共3小題，第32~33小題每小題6分，第34小題8分，共20分）

32．（6分）用等值演算法證明((q∧s)→r)∧(s→(p∨r))?(s∧(p→q))→r

33．（6分）設(shè)n階無向樹G=中有m條邊，證明m=n-1。

34．（8分）設(shè)P={?,{1},{1,2},{1,2,3}}，?是集合P上的包含關(guān)系。

（1）證明：

是偏序集。

（2）在（1）的基礎(chǔ)上證明

是全序集

五、應(yīng)用題(15分）

35．（9分）在謂詞邏輯中構(gòu)造下面推理的證明：每個在學(xué)校讀書的人都獲得知識。所以如

果沒有人獲得知識就沒有人在學(xué)校讀書。（個體域：所有人的集合）

第三篇：離散數(shù)學(xué)試卷

誠信應(yīng)考,考試作弊將帶來嚴(yán)重后果！華南理工大學(xué)期末考試 《離散數(shù)學(xué)》試卷A 注意事項：1.考前請將密封線內(nèi)填寫清楚；2.所有答案請直接答在試卷上；3．考試形式：閉卷；4.本試卷共五大題，滿分100分，考試時間120分鐘

一、填空題(本大題共12小題，每小題2分，共24分)1．求合式公式?xP(x)→?xQ(x,y)的前束范式________________。2．設(shè)集合A={a, b, {a,b}, ?}, B = {{a,b}, ?}，求B-A=_____________． 3．設(shè)p與q的真值為0,r,s的真值為1則命題?(s?(q?(r??p)))?(r??p)的真值是__________.4．設(shè)R是在正整數(shù)集合Z?上如下定義的二元關(guān)系R???x,y(x,y??Z)?(x?y?1?，0)則它一共有個有序?qū)?，且有自反性、對稱性、傳遞性、反自反性和反對稱性各性質(zhì)中的性質(zhì)。5．公式?x(P(x)→Q(x,y))→S(x)中的自由變元為________________，約束變元為________________。6．設(shè)有命題T(x): x 是火車，C(x): x是汽車，Q(x, y): x跑得比y快，那么命題“有的汽車比一些火車跑得快”的邏輯表達(dá)式是______________________.7．設(shè)G是n階m條邊的無向圖，若G連通且m=__________則G是無向樹.8．設(shè)X={1，2，3}，f：X→X，g：X→X，f={<1, 2>,<2,3>,<3,1>},g={<1,2>,<2,3>,<3,3>}，則f-1?g=________________，g?f=________________。9.不能再分解的命題稱為________________，至少包含一個聯(lián)結(jié)詞的命題稱為《離散數(shù)學(xué)》試卷A

________________．

10.連通無向圖G含有歐拉回路的充分必要條件是 11．設(shè)集合A={?,{a}}，則A的冪集P(A，|P(A)|=_____________________________。

12.設(shè)G = , G’ = 為兩個圖(同為無向圖或有向圖), 若E’ ? E且_______________, 則稱G’是G的子圖, 若E’ ? E且_______________, 則稱G’是G的生成子圖。

二、單選題(本大題共12小題，每小題2分，共26分)

1．下列命題公式為重言式的是（）

A.(p∨┐p)→q．B．p→(p∨q)C．q∧┐qD．(p→?p)→?q

2．下列語句中為命題的是()

A．你好嗎？

B．人有6指.C．我所說的是假的.D．明天是晴天.3.設(shè)D=為有向圖，V={a, b, c, d, e, f}, E={, , , ,}是（）

A．強連通圖

C．弱連通圖 B．單向連通圖 D．不連通圖

4．集合A＝{a，b，c}上的下列關(guān)系矩陣中符合偏序關(guān)系條件的是()

?10

1?011A．?

?001

??1100??101??101??111??0? B．?010?C．?110?D．?010? ??????1??????101???001???011??1?

5．設(shè)A={1，2，3}，A上二元關(guān)系S={<1，1>，<1，2>，<3，2>，<3，3>}，則S是（）

A．自反關(guān)系 B．傳遞關(guān)系C．對稱關(guān)系D． 反自反關(guān)系

6.設(shè)A={a,b,c,d}，A上的等價關(guān)系R={, , , }∪IA，則對應(yīng)于R的A的劃分是（）

A．{{a},{b, c},csxdvpk}

C．{{a},,{c},mk2gzlo} B．{{a, b},{c}, 1dffmg2} D．{{a, b}, {c,d}}

7.以下非負(fù)整數(shù)列可簡單圖化為一個歐拉圖的是()

A.{2, 2, 2, 2, 0}B.{4, 2, 6, 2, 2}

C.{2, 2, 3, 4, 1}D.{4, 2, 2, 4, 2}

8.設(shè)論域D＝{a，b }，與公式?xA(x)等價的命題公式是()

A．A(a)∧A(b)B．A(a)→A(b)C．A(a)∨A(b)D．A(b)→A(a)

9.一棵樹有3個4度頂點，4個2度頂點其余都是樹葉，求這棵樹有多少個樹葉頂點()

A.12B.8C.10D.1

310.有ABC三個人猜測甲乙丙三個球隊中的冠軍.各人的猜測如下:

A: 冠軍不是甲,也不是乙.B: 冠軍不是甲,而是丙.C: 冠軍不是丙,而是甲.已知其中有一個人說的完全正確.一個人說的都不對,而另外一人恰有一半說對了.據(jù)此推算,冠軍應(yīng)該是()

A．甲B.乙C.丙D.不確定

11．如第11題圖所示各圖，其中存在哈密頓回路的圖是()

12．設(shè)C(x): x是國家級運動員，G(x): x是健壯的，則命題“沒有一個國家級運動員不是健壯的”可符號化為()

(A)??x(C(x)??G(x))(B)??x(C(x)??G(x))

(C)??x(C(x)??G(x))(D)??x(C(x)??G(x))

三．計算題(30分)

1．用等值演算法求取求下列公式：(?P?Q)?(P∨?Q)的合取范式（5分）

2．圖G如下圖所示，求圖G的最小生成樹.（5分）

3．有向圖D如圖所示，求D的關(guān)聯(lián)矩陣M(D)（5分）

4.化簡表達(dá)式(((A?(B?C))?

A)?(B?(B?A)))?(C?A)（7分）

5．設(shè)R={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)和s(R)，并作出它們及R的關(guān)系圖(8分)

五．證明題(22分)

1．構(gòu)造下面推理的證明(5分)

前提：p?q，p??r，s?t，?s?r，?t

結(jié)論：q

2．設(shè)A={1, 2, 3, 4}, 在A?A定義的二元關(guān)系R，??u,v?,?x,y??A?A, uRxuy +xv

證明R是A?A上的等價關(guān)系。(5分)

3．已知A、B、C是三個集合，證明A-(B∪C)=(A-B)∩(A-C)（6分）

4． 無向圖G = ，且|V|=n, |E|=m, 試證明以下兩個命題是等價命題

1）G中每對頂點間具有唯一的通路，2）G連通且n=m+1。（6分）

第四篇：離散 2

集合一、知識點（建議看書）

1、集合（類、族、搜集）的定義：能作為整體論述的事物的整體。

元素（成員）：組成集合的每個事物。

基數(shù)（勢）：有限集合的元素個數(shù)，記為A2、集合的表示方法：①列舉法A={1，2，3}、②描述法A={a|a?I?0?a?5}、③歸納定義法。

3、區(qū)別{A}與A、{空集}與空集。

4、集合間的包含關(guān)系。（P55-P56）

5、并、交和差運算的定義及運算律。（P59-P60）

6、補運算定義、性質(zhì)。德-摩根定律。（P61-P62）

7、并和交運算的擴展。（P63）

8、環(huán)和（對稱差）與環(huán)積的定義、性質(zhì)。（P64）

9、冪集合：A是一集合，A的冪集合p(A)，是A的所有子集的集合。

n個元素的集合A，其冪集的元素個數(shù)是2n。

10、集合的歸納定義：（1）基礎(chǔ)條款；（2）歸納條款；（3）極小性條款。

歸納證明的步驟：（1）基礎(chǔ)步驟；（2）歸納步驟。

數(shù)學(xué)歸納法第一原理（P74）；數(shù)學(xué)歸納法第二原理（P76）

11、自然數(shù)的歸納定義。（P72）

12、二重組（序偶）：兩個元素a1、a2組成的序列記作。a1、a2分別稱為二重組的第一分量和第二分量。

=當(dāng)且僅當(dāng)a=c,b=d;?。

n重組的定義（P84）

13、叉積（笛卡爾乘積）的定義、運算律。（P84）

二、練習(xí)題

1、列出下列每一集合的元素和全部子集。（知識點4）

{a,b,c}、{a,{b,c}}、{{a,{b,c}}}

2、證明下列各式。

（a）(A?B)?B?A?B

（b）C?(A?B)?(C?A)?(C?B)

（c）A?(A?B)?A?B3、證明如果C?A且C?B，那么C?A?B（也就是A?B是包含在A和B中的最大集合）

4、設(shè)A、B、C和D是任意集合，試證明：

(A?B)?(C?D)?(A?C)?(B?D)

5、設(shè)A={0,1}，構(gòu)成集合p(A)?A。

第五篇：離散數(shù)學(xué)試卷二十三試題與答案

試卷二十三試題與答案

一、單項選擇題：（每小題1分，本大題共10分）

1．命題公式P?(Q?P)是（）。

A、矛盾式；B、可滿足式；C、重言式；D、等價式。

2．下列各式中哪個不成立（）。

A、?x(P(x)?Q(x))??xP(x)??xQ(x)；

B、?x(P(x)?Q(x))??xP(x)??xQ(x)；

C、?x(P(x)?Q(x))??xP(x)??xQ(x)；

D、?x(P(x)?Q)??xP(x)?Q。

3．謂詞公式?x(P(x)??yR(y))?Q(x)中的 x是（）。

A、自由變元；B、約束變元；

C、既是自由變元又是約束變元；D、既不是自由變元又不是約束變元。

4．在0 ?之間應(yīng)填入（）符號。

A、=；B、?；C、?；D、?。

5．設(shè)< A，? > 是偏序集，B?A，下面結(jié)論正確的是（）。

A、B的極大元b?B且唯一；B、B的極大元b?A且不唯一；

C、B的上界b?B且不唯一；D、B的上確界b?A且唯一。

6．在自然數(shù)集N上，下列（）運算是可結(jié)合的。

（對任意a,b?N）

A、a?b?a?b；B、a?b?max(a,b)；

C、a?b?a?5b；D、a?b?a?b。

7．Q為有理數(shù)集N，Q上定義運算*為a*b = a + b – ab ,則的幺元為（A、a；B、b；C、1；D、0。

8．給定下列序列，（）可以構(gòu)成無向簡單圖的結(jié)點度數(shù)序列。

A、（1，1，2，2，3）；B、（1，1，2，2，2）；

C、（0，1，3，3，3）；D、（1，3，4，4，5）。

9．設(shè)G是簡單有向圖，可達(dá)矩陣P(G)刻劃下列（）關(guān)系。

A、點與邊；B、邊與點；C、點與點；D、邊與邊。

10．一顆樹有兩個2度結(jié)點，1個3度結(jié)點和3個4度結(jié)點，則1度結(jié)點數(shù)為（A、5；B、7；C、9；D、8。

。）。）

二、填空：（每空1分，本大題共15分）

1．在自然數(shù)集中，偶數(shù)集為N1、奇數(shù)集為N2，則N1?N2=；

N1?N2 =。

2．設(shè)X?{1,2,3,4},R?{?1,2?,?2,4?，?3,3?}，則

r(R)=；s(R)= ；t(R)=。

3．設(shè)R為集合A上的等價關(guān)系，對?a?A，集合[a]R=，稱

為

元

素

a

形

成的R

等

價

類，[a]R??，因

為。

4．任意兩個不同小項的合取為，全體小項的析取式為。

5．設(shè)Q(x):x為偶數(shù)，P(x):x為素數(shù)，則下列命題：（1）存在唯一偶素數(shù)；（2）至多有一個偶素數(shù)；分別形式化：（1）；

（2）。

6．設(shè)T為根樹，若，則稱T為m元樹；

若則稱T為完全m叉樹。

7．含5個結(jié)點，4條邊的無向連通圖（不同構(gòu)）有 個，它們是。

三、判斷改正題：（每小題2分，本大題共20分）

1．命題公式(A?(A?B))?B是一個矛盾式。（）2．任何循環(huán)群必定是阿貝爾群，反之亦真。（）3．根樹中最長路徑的端點都是葉子。（）4．若集合A上的關(guān)系R是對稱的，則R

?

1也是對稱的。（）

5．?dāng)?shù)集合上的不等關(guān)系（≠）可確定A的一個劃分。（）6．設(shè)集合A、B、C為任意集合，若A×B = A×C，則B = C。（）7．函數(shù)的復(fù)合運算“?！睗M足結(jié)合律。（）8．若G是歐拉圖，則其邊數(shù)e合結(jié)點數(shù)v的奇偶性不能相反。（）9．圖G為（n , m）圖，G的生成樹TG必有n個結(jié)點。（）10．使命題公式P?(Q?R)的真值為F的真值指派的P、Q、R值分別是T、F、F。（）

四、簡答題（每小題5分，本大題共25分）

1．設(shè)?H,??和?K,??都是群?G,??的子群，問?H?K,??和?H?K,??是否是

?G,??的子并說明理由。

3，4，9}，B?{2，4，7，10,12}，從A到B的關(guān)系 2．設(shè)A?{2，R?{?a,b?a?A,b?B,且a整除b}，試給出R的關(guān)系圖和關(guān)系矩陣，并說明此

關(guān)系是否為函數(shù)？為什么？

3．設(shè)?S,??是半群，OL是左零元，對任x?S,x?OL是否是左零元？為什么？

4．某次會議有20人參加，其中每人至少有10個朋友，這20人擬圍一桌入席，用圖論知識說明是否可能每人鄰做的都是朋友？（理由）

5．通過主合取范式，求出使公式?(?P?Q)?R的值為F的真值指派。

五、證明題：（共30分）

1．設(shè)R為集合A上的二元關(guān)系，如果R是反自反的和可傳遞的，則R一定是反對稱的。

2．試證明若?G,??是群，H?G，且任意的a?H，對每一個x?G，有a?x?x?a，則?H,??是?G,??的子群。

3．設(shè)G是每個面至少由k（k?3）條邊圍成的連通平面圖，試證明為結(jié)點數(shù)，e為邊數(shù)。

4．符號化下列各命題，并說明結(jié)論是否有效（用推理規(guī)則）。任何人如果他喜歡美術(shù)，他就不喜歡體育。每個人或喜歡體育，或喜歡音樂，有的人不喜歡音樂，因而有的人不喜歡美術(shù)。答案

e?

k(v?2)k?

2，其中v

一、單項選擇題：

1．N

2;

?。r(R)?{?1,2?,?2,4?,?3,3?,?1,1?,?2,2?,?4,4?}，2．

s(R)?{?1,2?,?2,4?,?3,3?,?2,1?,?4,2?}，R?R?R?{?1,4?,?3,3?}，R?R?R?{?3,3?}，R?R?R?{?3,3?}，所以，t(R)?{?1,2?,?2,4?,?3,3?,?1,4?}。

3．[a]R?{xx?A,aRx}；a?[a]R。4．永假式（矛盾式），永真式（重言式）。5．（1）?x((Q(x)?P(x))??y(Q(y)?P(y)?x?y))。（2）?x?y(Q(x)?P(x)?Q(y)?P(y)?x?y)。

6．每個結(jié)點的出度都小于等于m；除葉子外，每個結(jié)點的出度都等于m。7．3。

三、判斷改正題：

1．×命題公式(A?(A?B))?B是一個重言式。2．×任何循環(huán)群必定是阿貝爾群，但反之不真。3．×根樹中最長路徑的端點不都是葉子。

4．√5．×≠不能確定A的一個劃分。6．√7．√

8．×歐拉圖其邊數(shù)e和結(jié)點數(shù)v的奇偶性可以相反。9．√10．√

四、簡答題

1．解：?H?K,??是 ?G,??的子群，?H?K,??不一定是?G,??的子群。??a,b?H?K,則的子群，a,b?H,a,b?K,由

?H,??和?K,??都是?G,??

?

a?b

?

1?H且a?b

?1

?K,?a?b

?1

?H?K,??H?K,??是?G,??的子群。

如：G = {1，5，7，11}，?：模12乘，則?G,??為群。且H = {1，5}，K = {1，7}，?H,??和?K,??皆為?G,??的子群，但H?K?{1,5,7}，?H?K,??不是?G,??的子群。因為 5?7?11?H?K，即運算不封閉。

2．解：R?{?2,2?,?2,4?,?2,10?,?2,12?,?3,12?,?4,4?,?4,12?}則R的關(guān)系圖為： R的關(guān)系矩陣為

?1??0??

0??0?

1010

0000

1000

1??1?1??0??

M

R

關(guān)系R不是A到B的函數(shù)，因為

元素2，4的象不唯一（或元素9無象）

3．解：x?OL仍是左零元。因為?y?S，由于OL是左零元，所以，OL?y?OL，又?S,??為半群，所以*可結(jié)合。

所以，(x?OL)?y?x?(OL?y)?x?OL，所以，x?OL仍是左零元。

4．解：可能。將人用結(jié)點表示，當(dāng)兩人是朋友時相應(yīng)結(jié)點間連一條邊，則得一個無向圖

G??V,E?，20人圍一桌，使每人鄰做都是朋友，即要找一個過每個點一次且僅

一次得回路。由題已知，?u,v?V,deg(u)?10,deg(v)?10，?deg(u)?deg(v)?20，由判定定理，G中存在一條漢密爾頓回路。即所談情況可能。

5．解：

原式??(P?Q)?R?(?P??Q)?R?(?P?R)?(?Q?R)

?(?P?Q?R)?(?P??Q?R)?(P??Q?R)?(?P??Q?R)?M100?M110?M

010

∴使公式?(?P?Q)?R的值為F的真值指派為：

?P:1

?

?Q:0?R:0?；

?P:1

?

?Q:1?R:0?；

?P:0

?

?Q:1?R:0?。

五、證明題：

1．證明：假設(shè)R不是反對稱的，則 ??x,y??R,性，∴ ?x,x??R 此與R反自反矛盾，∴R反對稱。

?y,x??R,x?y 由R的傳遞

2．證明：（1）設(shè)群?G,??的幺元為e，則?x?G有 x?e?e?x，∴e?H即H非空。（2）?a,b?H，則 ?x?G 有 a?x?x?a,b?x?x?b，從而

(a?b

?1)?x?(a?b

?1

?1?1)?x?(b?b

?1)

?a?(b?b)?x?b

?1

?(a?x)?b

?1

?1

?x?(a?b),?a?b?H

故 ?H,??是?G,??的子群。

3．解：設(shè)連通平面圖G有t個面：r1,r2,?,rt則有 v?e?r?2，deg(ri)?k,2k

?

tt

又有題意，deg(ri)?kt

i?1

又

e?

?deg(r)?2e

i

i?1，∴2e?kt，t?ev?e?

2k

e?2

kk?2

(v?2)

。從而，∴。

4．解：設(shè)P(x)：x喜歡美術(shù)，Q(x)：x喜歡體育，R(x)：x喜歡音樂。論域：人。

命題形式化為：前提：?x(P(x)??Q(x))，?x(Q(x)?R(x))，?x?R(x)結(jié)論：?x?P(x)。證明：（1）?x?R(x)P(2)?R(a)ES(1)(3)?x(Q(x)?R(x))P(4)Q(a)?R(a)US(4)(5)Q(a)T(2)(4)I(6)?x(P(x)??Q(x))P(7)P(a)??Q(a)US(6)(8)?P(a)T(5)(7)I(9)?x?P(x)EG(8)∴ 結(jié)論有效。