第一篇：全國(guó)2008年4月自考離散數(shù)學(xué)試題

全國(guó)2008年4月自考離散數(shù)學(xué)試題

課程代碼：02324

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

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

1.設(shè)P：天下大雨,Q：他在室內(nèi)運(yùn)動(dòng),命題“除非天下大雨，否則他不在室內(nèi)運(yùn)動(dòng)”可符合化為（）

A.?P∧QB.?P→Q C.?P→?QD.P→?Q

2.下列命題聯(lián)結(jié)詞集合中，是最小聯(lián)結(jié)詞組的是（）

A.{?，}B.{?，∨，∧} C.{?，∧}D.{∧，→}

3.下列命題為假命題的是（）

A.如果2是偶數(shù)，那么一個(gè)公式的析取范式惟一

B.如果2是偶數(shù)，那么一個(gè)公式的析取范式不惟一

C.如果2是奇數(shù)，那么一個(gè)公式的析取范式惟一

D.如果2是奇數(shù)，那么一個(gè)公式的析取范式不惟一

4.謂詞公式 x(P(x)∨yR(y))→Q(x))中變?cè)獂是（）

A.自由變?cè)狟.約束變?cè)?/p>

C.既不是自由變?cè)膊皇羌s束變?cè)狣.既是自由變?cè)彩羌s束變?cè)?/p>

5.若個(gè)體域?yàn)檎麛?shù)減，下列公式中值為真的是（）

A.xy(x+y=0)B.y x(x+y=0)C.x y(x+y=0)D.?xy(x+y=0)

6.下列命題中不正確的是（）

A.x∈{x}-{{x}}B.{x}?{x}-{{x}}

C.A={x}∪x,則x∈A且x?AD.A-B=??A=B

7.設(shè)P={x|(x+1)2≤4}，Q={x|x2+16≥5x},則下列選項(xiàng)正確的是（A.P?QB.P?Q C.Q?PD.Q=P

8.下列表達(dá)式中不成立的是（）

A.A∪(B?C)=(A∪B)?(A∪C)B.A∩(B?C)=(A∩B)?(A∩C)C.(A?B)×C=(A×C)?(B×C)D.(A-B)×C=(A×C)-(B×C)9.半群、群及獨(dú)異點(diǎn)的關(guān)系是（）

A.{群}?{獨(dú)異點(diǎn)}?{半群}B.{獨(dú)異點(diǎn)}?{半群}?{群} C.{獨(dú)異點(diǎn)}?{群}?{半群}D.{半群}?{群}?{獨(dú)異點(diǎn)} 10.下列集合對(duì)所給的二元運(yùn)算封閉的是（）

A.正整數(shù)集上的減法運(yùn)算

B.在正實(shí)數(shù)的集R+上規(guī)定為ab=ab-a-b a,b∈R+ C.正整數(shù)集Z+上的二元運(yùn)算為xy=min(x,y)x,y∈Z+ D.全體n×n實(shí)可逆矩陣集合Rn×n上的矩陣加法

11.設(shè)集合A={1，2，3}，下列關(guān)系R中不是等價(jià)關(guān)系的是（）A.R={<1,1>,<2,2>,<3,3>}

B.R={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>}）

C.R={<1,1>,<2,2>,<3,3>,<1,2>}

D.R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>} 12.下列函數(shù)中為雙射的是（）

A.f：Z→Z,f(j)=j(mod)B.f：N→N,f(j)= C.f：Z→N,f(j)=|2j|+1D.f：R→R,f(r)=2r-15

13.設(shè)集合A={a,b, c}上的關(guān)系如下，具有傳遞性的是（）

A.R={,,,}B.R={,} C.R={,,,}D.R={}

14.含有5個(gè)結(jié)點(diǎn)，3條邊的不同構(gòu)的簡(jiǎn)單圖有（）

A.2個(gè)B.3個(gè)

C.4個(gè)D.5個(gè)

15.設(shè)D的結(jié)點(diǎn)數(shù)大于1，D=是強(qiáng)連通圖，當(dāng)且僅當(dāng)（）

A.D中至少有一條通路B.D中至少有一條回路

C.D中有通過(guò)每個(gè)結(jié)點(diǎn)至少一次的通路D.D中有通過(guò)每個(gè)結(jié)點(diǎn)至少一次的回路

二、填空題(本大題共10小題，每小題2分，共20分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。

16.設(shè)A={1,2,3}，B={3,4,5}，則A?A=___________，A?B=___________。

17.設(shè)A={1,2,3,4,5}，R?A×A，R={<1,2>，<3,4>,<2,2>}，則R的自反閉包r(R)=__________。

對(duì)稱閉包t(R)=__________。

18.設(shè)P、Q為兩個(gè)命題，德摩根律可表示為_____________，吸收律可表示為____________。

19.對(duì)于公式 x(P(x)∨Q(x))，其中P(x)∶x=1,Q(x)∶x=2,當(dāng)論域?yàn)閧1,2}時(shí)，其真值為_____________ ,當(dāng)論域?yàn)閧0,1,2}時(shí)，其真值為_____________。

20.設(shè)f∶R→R,f(x)=x+3,g∶R→R,g(x)=2x+1,則復(fù)合函數(shù) ,。

21.3個(gè)結(jié)點(diǎn)可構(gòu)成_________個(gè)不同構(gòu)的簡(jiǎn)單無(wú)向圖，可構(gòu)成________個(gè)不同構(gòu)的簡(jiǎn)單有向圖。

22.無(wú)向圖G=如左所示，則G的最大度

Δ(G)=_____________，G的最小度δ(G)=_____________。

23.設(shè)圖G,V={v1,v2,v3,v4},若G的鄰接矩陣，則deg-(v1)=_ ________, deg+(v4)=____________。

24.格L是分配格，當(dāng)且僅當(dāng)L既不含有與_______同構(gòu)的子格，也不含有與______同格的子格。

25.給定集合A={1,2,3,4,5}，在集合A上定義兩種關(guān)系：R={<1,2>,<3,4>,<2,2>}, S={<4,2>,<2,5>,<3,1>,<1,3>}，則。

三、計(jì)算題（本大題共5小題，第26、27題各5分，第28、29題各6分，第30題8分，共30分）

26.設(shè)A={a,b,c,d}，A上的等價(jià)關(guān)系R={,,,}∪IA，畫出R的關(guān)系圖，并求出A中各元素的等價(jià)類。

27.構(gòu)造命題公式?（P∨Q）（?P∧Q）的真值表。

28.求下列公式的主析取范式和主合取范式：P→（（Q→P）∧（?P∧Q））

29.設(shè)A={a, b, c, d, e}，R為A上的關(guān)系，R={，，, , ,, }∪IA，試畫的哈斯圖，并求A中的最大元，最小元，極大元，極小元。

30.給定圖G如圖所示，（1）G中長(zhǎng)度為4的路有幾條？其中有幾條回路？（2）寫出G的可達(dá)矩陣。

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

31.設(shè)（L，≤）是格，試證明： a, b, c ∈L, 有a∧（b∨c）≥（a∧b）∨（a∧c）；

a∨（b∧c）≤（a∨b）∧（a∨c）。

32.設(shè)R是A上的自反和傳遞關(guān)系，如下定義A上的關(guān)系T，使得 x, y∈A，∈T ∈R∧(y, x)∈R。

證明T是A上的等價(jià)關(guān)系。

33.設(shè)有G=, V的結(jié)點(diǎn)數(shù)|V|=n，稱該圖為n階圖，若從結(jié)點(diǎn)vi到vj存在路，證明從vi到vj必存在長(zhǎng)度小于等于n-1的一條路。

五、應(yīng)用題（本大題共2小題，第34題7分，第35題8分，共15分）

34.構(gòu)造下面推理的證明。

每個(gè)喜歡步行的人都不喜歡坐汽車，每個(gè)人或者喜歡坐汽車或者喜歡騎自行車。有的人不喜歡騎自行車，因而有的人不喜歡步行。

35.今要將6人分成3組（每組2個(gè)人）去完成3項(xiàng)任務(wù)。已知每個(gè)人至少與其余5個(gè)人中的3個(gè)人能相互合作。

（1）能否使得每組的2個(gè)人都能相互合作？

（2）你能給出幾種不同的分組方案？

《離散數(shù)學(xué)》試題及答案3

一、填空題設(shè)集合A,B，其中A＝{1,2,3}, B= {1,2}, 則A?(B)＝ __________________________.2.設(shè)有限集合A, |A| = n, 則 |?(A×A)| = __________________________.3.設(shè)集合A = {a, b}, B = {1, 2}, 則從A到B的所有映射是__________________________ _____________, 其中雙射的是__________________________.4.已知命題公式G＝?(P?Q)∧R，則G的主析取范式是_______________________________

__________________________________________________________.5.設(shè)G是完全二叉樹，G有7個(gè)點(diǎn)，其中4個(gè)葉點(diǎn)，則G的總度數(shù)為__________，分枝點(diǎn)數(shù)為________________.6 設(shè)A、B為兩個(gè)集合, A= {1,2,4}, B = {3,4}, 則從A?B＝_________________________;A?B＝_________________________;A－B＝ _____________________.7.設(shè)R是集合A上的等價(jià)關(guān)系，則R所具有的關(guān)系的三個(gè)特性是______________________, ________________________, _______________________________.8.設(shè)命題公式G＝?(P?(Q?R))，則使公式G為真的解釋有__________________________，_____________________________, __________________________.9.設(shè)集合A＝{1,2,3,4}, A上的關(guān)系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 則R1?R2 = ________________________,R2?R1 =____________________________,R12 =________________________.10.設(shè)有限集A, B，|A| = m, |B| = n, 則| |?(A?B)| = _____________________________.11 設(shè)A,B,R是三個(gè)集合，其中R是實(shí)數(shù)集，A = {x |-1≤x≤1, x?R}, B = {x | 0≤x < 2, x?R},則A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ ,.13.設(shè)集合A＝{2, 3, 4, 5, 6}，R是A上的整除，則R以集合形式(列舉法)記為___________ _______________________________________________________.14.設(shè)一階邏輯公式G = xP(x)?xQ(x)，則G的前束范式是__________________________ _____.15.設(shè)G是具有8個(gè)頂點(diǎn)的樹，則G中增加_________條邊才能把G變成完全圖。

16.設(shè)謂詞的定義域?yàn)閧a, b},將表達(dá)式xR(x)→xS(x)中量詞消除，寫成與之對(duì)應(yīng)的命題公式是__________________________________________________________________________.17.設(shè)集合A＝{1, 2, 3, 4}，A上的二元關(guān)系R＝{(1,1),(1,2),(2,3)}, S＝{(1,3),(2,3),(3,2)}。則R?S＝_____________________________________________________, R2＝______________________________________________________.二、選擇題 設(shè)集合A={2,{a},3,4}，B = {{a},3,4,1}，E為全集，則下列命題正確的是()。

(A){2}?A(B){a}?A(C)??{{a}}?B?E(D){{a},1,3,4}?B.設(shè)集合A={1,2,3},A上的關(guān)系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，則R不具備().(A)自反性(B)傳遞性(C)對(duì)稱性(D)反對(duì)稱性 設(shè)半序集(A,≤)關(guān)系≤的哈斯圖如下所示，若A的子集B = {2,3,4,5},則元素6為B的()。

(A)下界(B)上界(C)最小上界(D)以上答案都不對(duì)下列語(yǔ)句中，()是命題。

(A)請(qǐng)把門關(guān)上(B)地球外的星球上也有人

(C)x + 5 > 6(D)下午有會(huì)嗎？ 設(shè)I是如下一個(gè)解釋：D＝{a,b}, 則在解釋I下取真值為1的公式是().(A)xyP(x,y)(B)xyP(x,y)(C)xP(x,x)(D)xyP(x,y).6.若供選擇答案中的數(shù)值表示一個(gè)簡(jiǎn)單圖中各個(gè)頂點(diǎn)的度，能畫出圖的是().(A)(1,2,2,3,4,5)(B)(1,2,3,4,5,5)(C)(1,1,1,2,3)(D)(2,3,3,4,5,6).7.設(shè)G、H是一階邏輯公式，P是一個(gè)謂詞，G＝xP(x), H＝xP(x),則一階邏輯公式G?H是().(A)恒真的(B)恒假的(C)可滿足的(D)前束范式.設(shè)命題公式G＝?(P?Q)，H＝P?(Q??P)，則G與H的關(guān)系是()。

(A)G?H(B)H?G(C)G＝H(D)以上都不是.9 設(shè)A, B為集合，當(dāng)()時(shí)A－B＝B.(A)A＝B(B)A?B(C)B?A(D)A＝B＝?.設(shè)集合A = {1,2,3,4}, A上的關(guān)系R＝{(1,1),(2,3),(2,4),(3,4)}, 則R具有()。

(A)自反性(B)傳遞性(C)對(duì)稱性(D)以上答案都不對(duì)下列關(guān)于集合的表示中正確的為()。

(A){a}?{a,b,c}(B){a}?{a,b,c}(C)??{a,b,c}(D){a,b}?{a,b,c} 12 命題xG(x)取真值1的充分必要條件是().(A)對(duì)任意x，G(x)都取真值1.(B)有一個(gè)x0，使G(x0)取真值1.(C)有某些x，使G(x0)取真值1.(D)以上答案都不對(duì).13.設(shè)G是連通平面圖，有5個(gè)頂點(diǎn)，6個(gè)面，則G的邊數(shù)是().(A)9條(B)5條(C)6條(D)11條.14.設(shè)G是5個(gè)頂點(diǎn)的完全圖，則從G中刪去()條邊可以得到樹.(A)6(B)5(C)10(D)4.15.設(shè)圖G的相鄰矩陣為，則G的頂點(diǎn)數(shù)與邊數(shù)分別為().(A)4, 5(B)5, 6(C)4, 10(D)5, 8.三、計(jì)算證明題

1.設(shè)集合A＝{1, 2, 3, 4, 6, 8, 9, 12}，R為整除關(guān)系。

(1)畫出半序集(A,R)的哈斯圖；

(2)寫出A的子集B = {3,6,9,12}的上界，下界，最小上界，最大下界；

(3)寫出A的最大元，最小元，極大元，極小元。

2.設(shè)集合A＝{1, 2, 3, 4}，A上的關(guān)系R＝{(x,y)| x, y?A 且 x ? y}, 求

(1)畫出R的關(guān)系圖；

(2)寫出R的關(guān)系矩陣.3.設(shè)R是實(shí)數(shù)集合，?,?,?是R上的三個(gè)映射，?(x)= x+3, ?(x)= 2x, ?(x)＝ x/4,試求復(fù)合映射???，???, ???, ???，?????.4.設(shè)I是如下一個(gè)解釋：D = {2, 3}, abf(2)f(3)P(2, 2)P(2, 3)P(3, 2)P(3, 3)32320011

試求(1)P(a, f(a))∧P(b, f(b));(2)xy P(y, x).5.設(shè)集合A＝{1, 2, 4, 6, 8, 12}，R為A上整除關(guān)系。

(1)畫出半序集(A,R)的哈斯圖；

(2)寫出A的最大元，最小元，極大元，極小元；

(3)寫出A的子集B = {4, 6, 8, 12}的上界，下界，最小上界，最大下界.6.設(shè)命題公式G = ?(P→Q)∨(Q∧(?P→R)), 求G的主析取范式。

7.(9分)設(shè)一階邏輯公式：G =(xP(x)∨yQ(y))→xR(x)，把G化成前束范式.9.設(shè)R是集合A = {a, b, c, d}.R是A上的二元關(guān)系, R = {(a,b),(b,a),(b,c),(c,d)},(1)求出r(R), s(R), t(R)；

(2)畫出r(R), s(R), t(R)的關(guān)系圖.11.通過(guò)求主析取范式判斷下列命題公式是否等價(jià)：

(1)G =(P∧Q)∨(?P∧Q∧R)

(2)H =(P∨(Q∧R))∧(Q∨(?P∧R))

13.設(shè)R和S是集合A＝{a, b, c, d}上的關(guān)系，其中R＝{(a, a),(a, c),(b, c),(c, d)}, S＝{(a, b),(b, c),(b, d),(d, d)}.(1)試寫出R和S的關(guān)系矩陣；

(2)計(jì)算R?S, R∪S, R－1, S－1?R－1.四、證明題

1.利用形式演繹法證明：{P→Q, R→S, P∨R}蘊(yùn)涵Q∨S。

2.設(shè)A,B為任意集合，證明：(A-B)-C = A-(B∪C).3.(本題10分)利用形式演繹法證明：{?A∨B, ?C→?B, C→D}蘊(yùn)涵A→D。

4.(本題10分)A, B為兩個(gè)任意集合，求證：

A－(A∩B)=(A∪B)－B.參考答案

一、填空題

1.{3};{{3},{1,3},{2,3},{1,2,3}}.2..3.?1= {(a,1),(b,1)}, ?2= {(a,2),(b,2)},?3= {(a,1),(b,2)}, ?4= {(a,2),(b,1)};?3, ?4.4.(P∧?Q∧R).5.12, 3.6.{4}, {1, 2, 3, 4}, {1, 2}.7.自反性；對(duì)稱性；傳遞性.8.(1, 0, 0),(1, 0, 1),(1, 1, 0).9.{(1,3),(2,2),(3,1)};{(2,4),(3,3),(4,2)};{(2,2),(3,3)}.10.2m?n.11.{x |-1≤x < 0, x?R};{x | 1 < x < 2, x?R};{x | 0≤x≤1, x?12.12;6.13.{(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)}.14.x(?P(x)∨Q(x)).15.21.16.(R(a)∧R(b))→(S(a)∨S(b)).17.{(1, 3),(2, 2)};{(1, 1),(1, 2),(1, 3)}.二、選擇題

1.C.2.D.3.B.4.B.5.D.6.C.7.C.8.A.9.D.10.B.11.B.13.A.14.A.15.D

三、計(jì)算證明題

1.(1)

(2)B無(wú)上界，也無(wú)最小上界。下界1, 3;最大下界是3.(3)A無(wú)最大元，最小元是1，極大元8, 12, 90+;極小元是1.2.R = {(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)}.(1)

(2)

3.(1)???＝?(?(x))＝?(x)+3＝2x+3＝2x+3.(2)???＝?(?(x))＝?(x)+3＝(x+3)+3＝x+6,(3)???＝?(?(x))＝?(x)+3＝x/4+3,(4)???＝?(?(x))＝?(x)/4＝2x/4 = x/2，(5)?????＝??(???)＝???+3＝2x/4+3＝x/2+3.4.(1)P(a, f(a))∧P(b, f(b))= P(3, f(3))∧P(2, f(2))= P(3, 2)∧P(2, 3)= 1∧0 = 0.(2)xy P(y, x)= x(P(2, x)∨P(3, x))

R}.6 =(P(2, 2)∨P(3, 2))∧(P(2, 3)∨P(3, 3))=(0∨1)∧(0∨1)= 1∧1 = 1.5.(1)

(2)無(wú)最大元，最小元1，極大元8, 12;極小元是1.(3)B無(wú)上界，無(wú)最小上界。下界1, 2;最大下界2.6.G = ?(P→Q)∨(Q∧(?P→R))= ?(?P∨Q)∨(Q∧(P∨R))=(P∧?Q)∨(Q∧(P∨R))=(P∧?Q)∨(Q∧P)∨(Q∧R)

=(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)∨(P∧Q∧?R)∨(P∧Q∧R)∨(?=(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)∨(P∧Q∧?R)∨(?P∧Q∧R)= m3∨m4∨m5∨m6∨m7 = ?(3, 4, 5, 6, 7).7.G =(xP(x)∨yQ(y))→xR(x)= ?(xP(x)∨yQ(y))∨xR(x)=(?xP(x)∧?yQ(y))∨xR(x)=(x?P(x)∧y?Q(y))∨zR(z)= xyz((?P(x)∧?Q(y))∨R(z))

9.(1)r(R)＝R∪IA＝{(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)}, s(R)＝R∪R－1＝{(a,b),(b,a),(b,c),(c,b)(c,d),(d,c)}，t(R)＝R∪R2∪R3∪R4＝{(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}；

(2)關(guān)系圖:

11.G＝(P∧Q)∨(?P∧Q∧R)

＝(P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R)＝m6∨m7∨m3 ＝?(3, 6, 7)

H =(P∨(Q∧R))∧(Q∨(?P∧R))＝(P∧Q)∨(Q∧R))∨(?P∧Q∧R)

＝(P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R)∨(P∧Q∧R)∨(?P∧Q∧R)＝(P∧Q∧?R)∨(?P∧Q∧R)∨(P∧Q∧R)＝m6∨m3∨m7 ＝?(3, 6, 7)

G,H的主析取范式相同，所以G = H.13.(1)

P∧Q∧R)7

(2)R?S＝{(a, b),(c, d)}，R∪S＝{(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)}, R－1＝{(a, a),(c, a),(c, b),(d, c)}, S－1?R－1＝{(b, a),(d, c)}.四 證明題

1.證明：{P→Q, R→S, P∨R}蘊(yùn)涵Q∨S(1)P∨RP

(2)?R→PQ(1)(3)P→QP

(4)?R→QQ(2)(3)(5)?Q→RQ(4)(6)R→SP

(7)?Q→SQ(5)(6)(8)Q∨SQ(7)

2.證明：(A-B)-C =(A∩~B)∩~C = A∩(~B∩~C)= A∩~(B∪C)= A-(B∪C)

3.證明：{?A∨B, ?C→?B, C→D}蘊(yùn)涵A→D(1)AD(附加)(2)?A∨BP(3)BQ(1)(2)(4)?C→?BP(5)B→CQ(4)(6)CQ(3)(5)(7)C→DP(8)DQ(6)(7)(9)A→DD(1)(8)

所以 {?A∨B, ?C→?B, C→D}蘊(yùn)涵A→D.4.證明：A－(A∩B)= A∩~(A∩B)＝A∩(~A∪~B)

＝(A∩~A)∪(A∩~B)＝?∪(A∩~B)＝(A∩~B)＝A－B

而(A∪B)－B =(A∪B)∩~B

=(A∩~B)∪(B∩~B)=(A∩~B)∪?

= A－B

所以：A－(A∩B)=(A∪B)－B.8

1.離散數(shù)學(xué)試題及答案2 離散數(shù)學(xué)試題

一.多重選擇填空題

(本題包括16個(gè)空格，每個(gè)空格3分，共48分。每道小題都可能有一個(gè)以上的正確選項(xiàng)，須選出所有的正確選項(xiàng)，不答不得分，多選、少選或選錯(cuò)都將按比例扣分。)1．命題公式(P∧(P→Q))→Q是_____式。

(1)重言(2)矛盾(3)可滿足(4)非永真的可滿足 2．給定解釋I=(D,)=(整數(shù)集，{f(x,y):f(x,y)=x-y；g(x,y):g(x,y)=x+y；P(x,y):x

(1)100(2)99(3)2048(4)1024(5)512 4．集合Ａ={x|x是整數(shù)，<30}，Ｂ={x|x是質(zhì)數(shù)，x<20}，C={1,3,5}，則① =_____;② =_____;③ =_____;④ =_____。(1){1,2,3,5}(2)(3){0}(4){1,3,5,7,11,13,17,19}(5){1,3,5,7}(6){7,11,13,17,19} 5．設(shè)A、B、C是集合，下列四個(gè)命題中，_____在任何情況下都是正確的。(1)若A B且B∈C，則A∈C(2)若A B且B∈C，則A C(3)若A∈B且B C，則A C(4)若A∈B且B C，則A∈C 6．設(shè)集合Ａ={a,b,c,d,e,f,g}，Ａ的一個(gè)劃分 ={{a,b},{c,d,e},{f,g}}，則 所對(duì)應(yīng)的等價(jià)關(guān)系有_____個(gè)二元組。

(1)14(2)15(3)16(4)17(5)8(6)49(7)512 7．S={1,2,3,4,5,6,7,8,9,10,11,12}，≤是S上的整除關(guān)系。S的子集Ｂ＝{2,4,6｝，則在(S，≤)中，Ｂ的最大元是_____；Ｂ的最小元是_____；Ｂ的上確界是_____；Ｂ的下確界是_____。

(1)不存在的(2)36(3)24(4)12(5)6(6)1(7)2 8．設(shè)有有限布爾代數(shù)(B,+,*,’,0,1)，則 =_____能成立。(1)1(2)2(3)3(4)4(5)5(6)8(7)9 9．G={0,1,2,?,n}，n∈N，定義 為模n加法，即x y=(x+y)mod n，則代數(shù)系統(tǒng)(G，)_____。

(1)是半群但不是群(2)是無(wú)限群(3)是循環(huán)群(4)是變換群(5)是交換群

10．n個(gè)結(jié)點(diǎn)、m條邊的無(wú)向連通圖是樹當(dāng)且僅當(dāng)m=_____。(1)n+1(2)n(3)n-1(4)2n-1 二請(qǐng)給出命題公式 的主析取范式。(10分)三假設(shè)下列陳述都是正確的：(1)學(xué)生會(huì)的每個(gè)成員都是學(xué)生并且是班干部；

(2)有些成員是女生。問(wèn)是否有成員是女班干部？請(qǐng)將上述陳述和你的結(jié)論符號(hào)化，并給出你的結(jié)論的形式證明。(10分)四設(shè)R和S是集合Ｘ上的等價(jià)關(guān)系,則S∩R必是等價(jià)關(guān)系。(10分)

參考答案

一、1.1、3 2.4 3.4 4.1；4；2；2 5.4 6.4 7.1；7；4；7 8.2、4、6 9.3、4 10.3

二、分析：求給定命題公式的主析取范式與主合取范式，通常有兩種方法——列表法和等值演算法。(1)列表法

列出給定公式的真值表，其真值為真的賦值所對(duì)應(yīng)的極小項(xiàng)的析取，即為此公式的主析取范式。(2)等值演算法 在等值演算中，首先將公式中的蘊(yùn)涵聯(lián)結(jié)詞和等價(jià)聯(lián)結(jié)詞化去，使整個(gè)公式化歸為析取范式，然后刪去其中所有的永假合取項(xiàng)，再將析取式中重復(fù)出現(xiàn)的合取項(xiàng)合并和合并合取項(xiàng)中相同的命題變?cè)詈髮?duì)合取項(xiàng)添加沒有出現(xiàn)的命題變?cè)?，就是合?,經(jīng)過(guò)化簡(jiǎn)整理，即可得到主析取范式。解：（1）列表法 設(shè)

000011111 001010100 010010100 011110100 100001000 101000010 110000010 111100111 根據(jù)真值表中 真值為1的賦值所對(duì)應(yīng)的極小項(xiàng)的析取，即為 的主析取范式。由表可知

（2）等值演算

三、解：有成員是女班干部。

將命題符號(hào)化，個(gè)體域?yàn)槿倐€(gè)體域。

：x是學(xué)生會(huì)的成員。：x是學(xué)生 ：x是班干部 ：x是女性 前提：，結(jié)論： 證明： ① P ② ES①，e為額外變?cè)?③ P ④ T③ ⑤ T② ⑥ T② ⑦ T④⑤⑥ ⑧ T② ⑨ T⑤⑦⑧ ⑩ EG⑨

離散數(shù)學(xué)試題及答案1

離散數(shù)學(xué)考試試題（A卷及答案）

一、（10分）某項(xiàng)工作需要派A、B、C和D 4個(gè)人中的2個(gè)人去完成，按下面3個(gè)條件，有幾種派法？如何派？

(1)若A去，則C和D中要去1個(gè)人；

(2)B和C不能都去；

(3)若C去，則D留下。

解 設(shè)A：A去工作；B：B去工作；C：C去工作；D：D去工作。則根據(jù)題意應(yīng)有：A?C?D，?(B∧C)，C??D必須同時(shí)成立。因此

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

?(?A∨(C∧? D)∨(?C∧D))∧(?B∨?C)∧(?C∨?D)

?(?A∨(C∧? D)∨(?C∧D))∧((?B∧?C)∨(?B∧?D)∨?C∨(?C∧?D))?(?A∧?B∧?C)∨(?A∧?B∧?D)∨(?A∧?C)∨(?A∧?C∧?D)

∨(C∧? D∧?B∧?C)∨(C∧? D∧?B∧?D)∨(C∧? D∧?C)∨(C∧? D∧?C∧?D)

∨(?C∧D∧?B∧?C)∨(?C∧D∧?B∧?D)∨(?C∧D∧?C)∨(?C∧D∧?C∧?D)

?F∨F∨(?A∧?C)∨F∨F∨(C∧? D∧?B)∨F∨F∨(?C∧D∧?B)∨F∨(?C∧D)∨F

?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D∧?B)∨(?C∧D)?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D)?T

故有三種派法：B∧D，A∧C，A∧D。

二、（15分）在謂詞邏輯中構(gòu)造下面推理的證明：某學(xué)術(shù)會(huì)議的每個(gè)成員都是專家并且是工人，有些成員是青年人，所以，有些成員是青年專家。

解：論域：所有人的集合。()： 是專家；()： 是工人；()： 是青年人；則推理化形式為：

(()∧())，()(()∧())下面給出證明：

(1)()P

(2)(c)T(1)，ES(3)(()∧())P

(4)(c)∧(c)T(3)，US(5)(c)T(4)，I

(6)(c)∧(c)T(2)(5)，I

11(7)(()∧())T(6)，EG

三、（10分）設(shè)A、B和C是三個(gè)集合，則A?B??(B?A)。

證明：A?B?x(x∈A→x∈B)∧x(x∈B∧x?A)?x(x?A∨x∈B)∧x(x∈B∧x?A)??x(x∈A∧x?B)∧?x(x?B∨x∈A)??x(x∈A∧x?B)∨?x(x∈A∨x?B)??(x(x∈A∧x?B)∧x(x∈A∨x?B))??(x(x∈A∧x?B)∧x(x∈B→x∈A))??(B?A)。

四、（15分）設(shè)A＝{1，2，3，4，5}，R是A上的二元關(guān)系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。

解 r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>}

s(R)＝R∪R－1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>}

R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>}

R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2

t(R)＝ Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，5>}。

五、（10分）R是非空集合A上的二元關(guān)系，若R是對(duì)稱的，則r(R)和t(R)是對(duì)稱的。

證明 對(duì)任意的x、y∈A，若xr(R)y，則由r(R)＝R∪IA得，xRy或xIAy。因R與IA對(duì)稱，所以有yRx或yIAx，于是yr(R)x。所以r(R)是對(duì)稱的。

下證對(duì)任意正整數(shù)n，Rn對(duì)稱。

因R對(duì)稱，則有xR2y?z(xRz∧zRy)?z(zRx∧yRz)?yR2x，所以R2對(duì)稱。若 對(duì)稱，則x y?z(x z∧zRy)?z(z x∧yRz)?y x，所以 對(duì)稱。因此，對(duì)任意正整數(shù)n，對(duì)稱。

對(duì)任意的x、y∈A，若xt(R)y，則存在m使得xRmy，于是有yRmx，即有yt(R)x。因此，t(R)是對(duì)稱的。

六、（10分）若f：A→B是雙射，則f－1：B→A是雙射。

證明 因?yàn)閒：A→B是雙射，則f－1是B到A的函數(shù)。下證f－1是雙射。

對(duì)任意x∈A，必存在y∈B使f(x)＝y(tǒng)，從而f－1(y)＝x，所以f－1是滿射。

對(duì)任意的y1、y2∈B，若f－1(y1)＝f－1(y2)＝x，則f(x)＝y(tǒng)1，f(x)＝y(tǒng)2。因?yàn)閒：A→B是函數(shù)，則y1＝y(tǒng)2。所以f－1是單射。

綜上可得，f－1：B→A是雙射。

七、（10分）設(shè)是一個(gè)半群，如果S是有限集，則必存在a∈S，使得a*a＝a。

證明 因?yàn)?S，*>是一個(gè)半群，對(duì)任意的b∈S，由*的封閉性可知，b2＝b*b∈S，b3＝b2*b∈S，?，bn∈S，?。

因?yàn)镾是有限集，所以必存在j＞i，使得 ＝。令p＝j(luò)－i，則 ＝ *。所以對(duì)q≥i，有 ＝ *。

因?yàn)閜≥1，所以總可找到k≥1，使得kp≥i。對(duì)于 ∈S，有 ＝ * ＝ *(*)＝?＝ *。

令a＝，則a∈S且a*a＝a。

八、（20分）（1）若G是連通的平面圖，且G的每個(gè)面的次數(shù)至少為l(l≥3)，則G的邊數(shù)m與結(jié)點(diǎn)數(shù)n有如下關(guān)系：

m≤(n－2)。

證明 設(shè)G有r個(gè)面，則2m＝ ≥lr。由歐拉公式得，n－m＋r＝2。于是，m≤(n－2)。

（2）設(shè)平面圖G＝是自對(duì)偶圖，則| E|＝2(|V|－1)。

證明 設(shè)G*＝是連通平面圖G＝的對(duì)偶圖，則G*? G，于是|F|＝|V*| 12 ＝|V|，將其代入歐拉公式|V|－|E|＋|F|＝2得，|E|＝2(|V|－1)。

離散數(shù)學(xué)考試試題（B卷及答案）

一、（10分）證明(P∨Q)∧(P?R)∧(Q?S)S∨R

證明 因?yàn)镾∨R??R?S，所以，即要證(P∨Q)∧(P?R)∧(Q?S)?R?S。

(1)?R 附加前提

(2)P?R P

(3)?P T(1)(2)，I(4)P∨Q P

(5)Q T(3)(4)，I(6)Q?S P(7)S T(5)(6)，I(8)?R?S CP(9)S∨R T(8)，E

二、（15分）根據(jù)推理理論證明：每個(gè)考生或者勤奮或者聰明，所有勤奮的人都將有所作為，但并非所有考生都將有所作為，所以，一定有些考生是聰明的。

設(shè)P(e)：e是考生，Q(e)：e將有所作為，A(e)：e是勤奮的，B(e)：e是聰明的，個(gè)體域：人的集合，則命題可符號(hào)化為：x(P(x)?(A(x)∨B(x)))，x(A(x)?Q(x))，?x(P(x)?Q(x))x(P(x)∧B(x))。

(1)?x(P(x)?Q(x))P

(2)?x(?P(x)∨Q(x))T(1)，E(3)x(P(x)∧?Q(x))T(2)，E(4)P(a)∧?Q(a)T(3)，ES(5)P(a)T(4)，I(6)?Q(a)T(4)，I

(7)x(P(x)?(A(x)∨B(x))P

(8)P(a)?(A(a)∨B(a))T(7)，US(9)A(a)∨B(a)T(8)(5)，I(10)x(A(x)?Q(x))P

(11)A(a)?Q(a)T(10)，US(12)?A(a)T(11)(6)，I(13)B(a)T(12)(9)，I

(14)P(a)∧B(a)T(5)(13)，I(15)x(P(x)∧B(x))T(14)，EG

三、（10分）某班有25名學(xué)生，其中14人會(huì)打籃球，12人會(huì)打排球，6人會(huì)打籃球和排球，5人會(huì)打籃球和網(wǎng)球，還有2人會(huì)打這三種球。而6個(gè)會(huì)打網(wǎng)球的人都會(huì)打另外一種球，求不會(huì)打這三種球的人數(shù)。

解 設(shè)A、B、C分別表示會(huì)打排球、網(wǎng)球和籃球的學(xué)生集合。則：

|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。

因?yàn)閨(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，＝25－20＝5。故，不會(huì) 13 打這三種球的共5人。

四、（10分）設(shè)A1、A2和A3是全集U的子集，則形如 Ai?(Ai?為Ai或)的集合稱為由A1、A2和A3產(chǎn)生的小項(xiàng)。試證由A1、A2和A3所產(chǎn)生的所有非空小項(xiàng)的集合構(gòu)成全集U的一個(gè)劃分。

證明 小項(xiàng)共8個(gè)，設(shè)有r個(gè)非空小項(xiàng)s1、s2、?、sr(r≤8)。

對(duì)任意的a∈U，則a∈Ai或a∈，兩者必有一個(gè)成立，取Ai?為包含元素a的Ai或，則a∈ Ai?，即有a∈ si，于是U? si。又顯然有 si?U，所以U＝ si。

任取兩個(gè)非空小項(xiàng)sp和sq，若sp≠sq，則必存在某個(gè)Ai和 分別出現(xiàn)在sp和sq中，于是sp∩sq＝?。

綜上可知，{s1，s2，?，sr}是U的一個(gè)劃分。

五、（15分）設(shè)R是A上的二元關(guān)系，則：R是傳遞的?R*R?R。

證明(5)若R是傳遞的，則∈R*R?z(xRz∧zSy)?xRc∧cSy，由R是傳遞的得xRy，即有∈R，所以R*R?R。

反之，若R*R?R，則對(duì)任意的x、y、z∈A，如果xRz且zRy，則∈R*R，于是有∈R，即有xRy，所以R是傳遞的。

六、（15分）若G為連通平面圖，則n－m＋r＝2，其中，n、m、r分別為G的結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)。

證明 對(duì)G的邊數(shù)m作歸納法。

當(dāng)m＝0時(shí)，由于G是連通圖，所以G為平凡圖，此時(shí)n＝1，r＝1，結(jié)論自然成立。

假設(shè)對(duì)邊數(shù)小于m的連通平面圖結(jié)論成立。下面考慮連通平面圖G的邊數(shù)為m的情況。

設(shè)e是G的一條邊，從G中刪去e后得到的圖記為G?，并設(shè)其結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)分別為n?、m?和r?。對(duì)e分為下列情況來(lái)討論：

若e為割邊，則G?有兩個(gè)連通分支G1和G2。Gi的結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)分別為ni、mi和ri。顯然n1＋n2＝n?＝n，m1＋m2＝m?＝m－1，r1＋r2＝r?＋1＝r＋1。由歸納假設(shè)有n1－m1＋r1＝2，n2－m2＋r2＝2，從而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。

若e不為割邊，則n?＝n，m?＝m－1，r?＝r－1，由歸納假設(shè)有n?－m?＋r?＝2，從而n－(m－1)＋r－1＝2，即n－m＋r＝2。

由數(shù)學(xué)歸納法知，結(jié)論成立。

七、（10分）設(shè)函數(shù)g：A→B，f：B→C，則：

(1)fog是A到C的函數(shù)；

(2)對(duì)任意的x∈A，有fog(x)＝f(g(x))。

證明(1)對(duì)任意的x∈A，因?yàn)間：A→B是函數(shù)，則存在y∈B使∈g。對(duì)于y∈B，因f：B→C是函數(shù)，則存在z∈C使∈f。根據(jù)復(fù)合關(guān)系的定義，由∈g和∈f得∈g*f，即∈fog。所以Dfog＝A。

對(duì)任意的x∈A，若存在y1、y2∈C，使得、∈fog＝g*f，則存在t1使得∈g且∈f，存在t2使得∈g且∈f。因?yàn)間：A→B是函數(shù)，則t1＝t2。又因f：B→C是函數(shù)，則y1＝y(tǒng)2。所以A中的每個(gè)元素對(duì)應(yīng)C中惟一的元素。

綜上可知，fog是A到C的函數(shù)。

(2)對(duì)任意的x∈A，由g：A→B是函數(shù)，有∈g且g(x)∈B，又由f：B→C是函數(shù)，得∈f，于是∈g*f＝fog。又因fog是A到C的函數(shù)，則可寫為fog(x)＝f(g(x))。

八、（15分）設(shè)是的子群，定義R＝{|a、b∈G且a－1*b∈H}，則R是G中的一個(gè)等價(jià)關(guān)系，且[a]R＝aH。

證明 對(duì)于任意a∈G，必有a－1∈G使得a－1*a＝e∈H，所以∈R。

若∈R，則a－1*b∈H。因?yàn)镠是G的子群，故(a－1*b)－1＝b－1*a∈H。所以∈R。

若∈R，∈R，則a－1*b∈H，b－1*c∈H。因?yàn)镠是G的子群，所以(a－1*b)*(b－1*c)＝a－1*c∈H，故∈R。

綜上可得，R是G中的一個(gè)等價(jià)關(guān)系。

對(duì)于任意的b∈[a]R，有∈R，a－1*b∈H，則存在h∈H使得a－1*b＝h，b＝a*h，于是b∈aH，[a]R?aH。對(duì)任意的b∈aH，存在h∈H使得b＝a*h，a－1*b＝h∈H，∈R，故aH?[a]R。所以，[a]R＝aH。

發(fā)到哪？給個(gè)郵箱啊~~~~~~~

一、填空 20%（每小題2分）

1．設(shè)（N：自然數(shù)集，E???+ 正偶數(shù)）則。

2．A，B，C表示三個(gè)集合，文圖中陰影部分的集合表達(dá)式為。

3．設(shè)P，Q 的真值為0，R，S的真值為1，則的真值=。

4．公式 的主合取范式為。

5．若解釋I的論域D僅包含一個(gè)元素，則 在I下真值為。

6．設(shè)A={1，2，3，4}，A上關(guān)系圖為

則 R2 =。

7．設(shè)A={a，b，c，d}，其上偏序關(guān)系R的哈斯圖為

則 R=。

8．圖 的補(bǔ)圖為。

9．設(shè)A={a，b，c，d}，A上二元運(yùn)算如下：

* a b c d a b c d a b c d b c d a c d a b d a b c

那么代數(shù)系統(tǒng)的幺元是，有逆元的元素為，它們的逆元分別為。

10．下圖所示的偏序集中，是格的為。

二、選擇 20%（每小題 2分）

1、下列是真命題的有（）

A． ； B． ；

C． ； D．。

2、下列集合中相等的有（）

A．{4，3} ；B．{，3，4}；C．{4，3，3}；D． {3，4}。

3、設(shè)A={1，2，3}，則A上的二元關(guān)系有（）個(gè)。

A． 23 ； B． 32 ； C． ； D．。

4、設(shè)R，S是集合A上的關(guān)系，則下列說(shuō)法正確的是（）

A．若R，S 是自反的，則 是自反的；

B．若R，S 是反自反的，則 是反自反的；

C．若R，S 是對(duì)稱的，則 是對(duì)稱的；

D．若R，S 是傳遞的，則 是傳遞的。

5、設(shè)A={1，2，3，4}，P（A）（A的冪集）上規(guī)定二元系如下

則P（A）/ R=（）

A．A ；B．P(A)；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；

D．{{ }，{2}，{2，3}，{{2，3，4}}，{A}}

6、設(shè)A={，{1}，{1，3}，{1，2，3}}則A上包含關(guān)系“ ”的哈斯圖為（）

7、下列函數(shù)是雙射的為（）

A．f : I E , f(x)= 2x ； B．f : N N N, f(n)= ；

C．f : R I , f(x)= [x] ； D．f :I N, f(x)= | x |。

（注：I—整數(shù)集，E—偶數(shù)集，N—自然數(shù)集，R—實(shí)數(shù)集）

8、圖 中 從v1到v3長(zhǎng)度為3 的通路有（）條。

A． 0； B． 1； C． 2； D． 3。

9、下圖中既不是Eular圖，也不是Hamilton圖的圖是（）

10、在一棵樹中有7片樹葉，3個(gè)3度結(jié)點(diǎn)，其余都是4度結(jié)點(diǎn)則該樹有（）個(gè)4度結(jié)點(diǎn)。

A．1； B．2； C．3； D．4。

三、證明 26%

1、R是集合X上的一個(gè)自反關(guān)系，求證：R是對(duì)稱和傳遞的，當(dāng)且僅當(dāng) < a, b> 和在R中有<.b , c>在R中。（8分）

2、f和g都是群到< G2, *>的同態(tài)映射，證明是的一個(gè)子群。其中C=(8分)

3、G=(|V| = v，|E|=e)是每一個(gè)面至少由k（k 3）條邊圍成的連通平面圖，則，由此證明彼得森圖（Peterson）圖是非平面圖。（11分）

四、邏輯推演 16%

用CP規(guī)則證明下題（每小題 8分）

1、2、五、計(jì)算 18%

1、設(shè)集合A={a，b，c，d}上的關(guān)系R={ ,< b , a > ,< b, c > , < c , d >}用矩陣運(yùn)算求出R的傳遞閉包t(R)。（9分）

2、如下圖所示的賦權(quán)圖表示某七個(gè)城市 及預(yù)先算出它們之間的一些直接通信線路造價(jià)，試給出一個(gè)設(shè)計(jì)方案，使得各城市之間能夠通信而且總造價(jià)最小。（9分）

試卷一答案：

一、填空 20%（每小題2分）

1、{0，1，2，3，4，6}；

2、；

3、1；

4、； 5、1；

6、{<1,1>, <1,3>, <2,2>, <2,4> }；

7、{,,,,} IA ；

8、9、a ；a , b , c ,d ；a , d , c , d ；

10、c;

二、選擇 20%（每小題 2分）

題目 1 2 3 4 5 6 7 8 9 10

答案 C D B、C C A D C A D B A

三、證明 26%

1、證：

“ ” 若 由R對(duì)稱性知，由R傳遞性得

“ ” 若，有 任意，因 若 所以R是對(duì)稱的。

若，則 即R是傳遞的。

2、證，有，又

★ ★

★ < C , ★> 是 < G1 , ★>的子群。

3、證：

①設(shè)G有r個(gè)面，則，即。而 故 即得。（8分）

②彼得森圖為，這樣 不成立，所以彼得森圖非平面圖。（3分）

二、邏輯推演 16%

1、證明：

① P（附加前提）

② T①I ③ P

④ T②③I ⑤ T④I ⑥ T⑤I ⑦ P

⑧ T⑥⑦I ⑨ CP

2、證明

① P（附加前提）

② US①

③ P ④ US③

⑤ T②④I ⑥ UG⑤

⑦ CP

三、計(jì)算 18%

1、解：，t(R)={ , , < a , c> , , , < b ,b > , < b , c.> , < b , d > , < c , d > }

2、解： 用庫(kù)斯克（Kruskal）算法求產(chǎn)生的最優(yōu)樹。算法略。結(jié)果如圖：

樹權(quán)C(T)=23+1+4+9+3+17=57即為總造價(jià)。

第二篇：全國(guó)2006年4月高等教育自學(xué)考試離散數(shù)學(xué)試題

全國(guó)2006年4月高等教育自學(xué)考試

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

課程代碼：02324

一、單項(xiàng)選擇題（本大題共15小題，每小題1分，共15分）

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

1．下列命題公式為重言式的是（）A．p→(p∨q)C．q∧┐q 2．下列語(yǔ)句中不是命題的只有（）．．A．這個(gè)語(yǔ)句是假的。C．飛碟來(lái)自地球外的星球。

B．1+1=1.0

D．凡石頭都可練成金。B．(p∨┐p)→q D．p→┐q 3．設(shè)p：我很累，q：我去學(xué)習(xí)，命題：“除非我很累，否則我就去學(xué)習(xí)”的符號(hào)化正確的是

（）

A．┐p∧q C．┐p→┐q 4．下列等價(jià)式正確的是（）A．┐(?x)A?(?x)┐A B．(?x)(?y)A?(?x)(?y)A C．┐(?x)A?(?x)┐A

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

5．在公式(?x)(?y)(P(x,y)?Q(z))?(?y)P(y,z)中變?cè)獃是（）A．自由變?cè)?B．約束變?cè)?/p>

C．既是自由變?cè)?，又是約束變?cè)?D．既不是自由變?cè)植皇羌s束變?cè)?/p>

6．設(shè)A={1，2，3}，A上二元關(guān)系S={<1，1>，<1，2>，<3，2>，<3，3>}，則S是（）A．自反關(guān)系 C．對(duì)稱關(guān)系

B．反自反關(guān)系 D．傳遞關(guān)系 B．┐p→q D．p→┐q 7．設(shè)集合X為人的全體，在X上定義關(guān)系R、S為R={|a，b∈X∧a是b的母親}，那么關(guān)系{|a，b∈x∧ a是b的祖母}的表達(dá)式為（）A．R?S C．S?R

B．R-1?S D．R?S-1

8．設(shè)A是正整數(shù)集，R={(x，y)|x，y∈A∧x+3y=12}，則R∩({2，3，4，6}×{2，3，4，6})=（）A． O /

B．{<3，3>} C．{<3，3>，<6，2>} D．{<3，3>，<6，2>，<9，1>} 9．下列式子不正確的是（）A．(A-B)-C=(A-C)-B C．(A-B)-C=(A-C)-(B-C)10．下列命題正確的是（）A．{l，2}?{{1，2}，{l，2，3}，1} B．{1，2}?{1，{l，2}，{l，2，3}，2} C．{1，2}?{{1}，{2}，{1，2}} D．{1，2}∈{1，2，{2}，{l，2，3}} 11．在下列代數(shù)系統(tǒng)中，不是環(huán)的只有（）

A．，其中R為實(shí)數(shù)集，+為實(shí)數(shù)加法，a*b=a+2b。

D．，其中Mn(R)為實(shí)數(shù)集n×n階矩陣結(jié)合，+，*是矩陣加法和乘法。12．下列整數(shù)集對(duì)于整除關(guān)系都構(gòu)成偏序集，而能構(gòu)成格的是（）A．{l，2，3，4，5} C．{2，3，7}

B．{1，2，3，6，12} D．{l，2，3，7}

B．(A-B)-C=A-(B∪C)D．A-(B∪C)=(A-B)∪ C

13．結(jié)點(diǎn)數(shù)為奇數(shù)且所有結(jié)點(diǎn)的度數(shù)也為奇數(shù)的連通圖必定是（）A．歐拉圖 C．非平面圖

B．漢密爾頓圖 D．不存在的

14．無(wú)向圖G是歐拉圖當(dāng)且僅當(dāng)G是連通的且（）A．G中各頂點(diǎn)的度數(shù)均相等 B．G中各頂點(diǎn)的度數(shù)之和為偶數(shù) C．G中各頂點(diǎn)的度數(shù)均為偶數(shù) D．G中各頂點(diǎn)的度數(shù)均為奇數(shù)

15．平面圖(如下)的三個(gè)面的次數(shù)分別是（）

A．11，3，4 C．12，3，6

B．11，3，5 D．10，4，3

二、填空題（本大題共10小題，每小題2分，共20分）請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。

16．求一個(gè)公式的主析取或主合取范式的方法，有______________法和______________法。

17．給定謂詞合式公式A，其中一部分公式形式為(?x)B(x)或(?x)B(x)，則量詞?，?后面所跟的x稱為______________，而稱B為相應(yīng)量詞的______________。

18．設(shè)X，U，V，Y都是實(shí)數(shù)集，f1：X→U，且fl(x)→ex； f2：U→V，且f2(u)＝u(1+u)；f3：V→Y，且f3(v)=cosv。那么f3?f2?f1的定義域是______________，而復(fù)合函數(shù)(f3?f2?f1)(x)= ______________。

19．集合X={a，b，c，d}上二元關(guān)系R={，，，，，}，則R的自反閉包r(R)= ______________，對(duì)稱閉包s(R)= ______________。

20．已知G=<{l，-1，i，-i}，·>(其中i=?1，是數(shù)的乘法)是群，則-l的階是______________；i的階是______________。21．對(duì)代數(shù)系統(tǒng)，其中*是S上的二元運(yùn)算，若a，b∈S，且對(duì)任意的x∈S，都有a*x=x*a=x，b*x=x*b=b，則稱a為運(yùn)算“*”的______________，稱b為運(yùn)算“*”的______________。

22．設(shè)是群，則滿足結(jié)合律和______________；若｜S｜>l，S中不可能有______________。23．寫出如右有向圖的一條初級(jí)回路：______________，其長(zhǎng)度是______________。24．一個(gè)______________且______________的無(wú)向圖稱為樹。25．在簡(jiǎn)單無(wú)向圖G=中，如果V中的每個(gè)結(jié)點(diǎn)都與其稱為______________，如果V有n個(gè)結(jié)點(diǎn)，那么它還是

三、計(jì)算題(本大題共5小題，第26、27題各5分，第28、29題各6分，第30題8分，共30分)26．若集合A={a，{b，c}}的冪集為P(A)，集合B={ O /

，{ O / }}的冪集為P(B)，求P(A)∩P(B)。

27．構(gòu)造命題公式(p→(q∧ r))→┐p的真值表。

28．求圖G＝的可達(dá)矩陣，其中V＝｛v1,v2,v3,v4｝ E＝｛(v1,v2),(v2,v3),(v2,v4),(v3,v2),(v3,v4),(v3,v1),(v4,v1)｝

余的所有結(jié)點(diǎn)鄰接，則該圖______________度正則圖。

29．求下列公式的主析取范式和主合取范式：（P∧Q）∨（┐P∧R）

30．設(shè)A＝｛2，3，4，6，8，12，24｝，R為A上整除關(guān)系，試畫的哈斯圖，并求A中的最大元，最小元，極大元，極小元。

四、證明題（本大題共3小題，第31、32小題各6分，第33題8分，共20分）31．設(shè)M是偶數(shù)集，＋和·是數(shù)的加、乘運(yùn)算，證明是一個(gè)環(huán)。32．設(shè)R是集合X上的二元關(guān)系，證明R是X上傳遞關(guān)系當(dāng)且僅當(dāng)R?R?R。

33．設(shè)G是簡(jiǎn)單平面圖，G有n個(gè)頂點(diǎn)m條邊，且m<30，證明G中存在一項(xiàng)點(diǎn)v，d（v）≤4。

五、應(yīng)用題（本大題共2小題，第34題6分，第35題9分，共15分）34．判斷下面推理是否正確，并證明你的結(jié)論。如果小王今天家里有事，則他不會(huì)來(lái)開會(huì)。如果小張今天看到小王，則小王今天來(lái)開會(huì)了。小張今天看到小王。所以小王今天家里沒事。

35．有6個(gè)村莊Vi，i=l，2，…，6欲修建道路使村村可通。現(xiàn)已有修建方案如下帶權(quán)無(wú)向圖所示，其中邊表示道路，邊上的數(shù)字表示修建該道路所需費(fèi)用，問(wèn)應(yīng)選擇修建哪些道路可使得任二個(gè)村莊之間是可通的且總的修建費(fèi)用最低?要求寫出求解過(guò)程，畫出符合要求的最低費(fèi)用的道路網(wǎng)絡(luò)圖并計(jì)算其費(fèi)用。

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

中央電大離散數(shù)學(xué)試題

月

一、單項(xiàng)選擇題（每小題3分，本題共15分）

1．若集合A={1，{2}，{1，2}}，則下列表述正確的是()．

A．2?AB．{1}?A

C．1?AD．2 ? A

2．已知一棵無(wú)向樹T中有8個(gè)頂點(diǎn)，4度、3度、2度的分支點(diǎn)各一個(gè)，T的樹葉數(shù)為

()．

A．6B．4C．3D．

53．設(shè)無(wú)向圖G的鄰接矩陣為

?01111??10011????10000???11001????11010??

則G的邊數(shù)為()．

A．1B．7C．6D．14 4．設(shè)集合A={a}，則A的冪集為()．

A．{{a}}B．{a，{a}}

C．{?，{a}}D．{?，a}

5．下列公式中()為永真式．

A．?A??B ? ?A??BB．?A??B ? ?(A?B)

C．?A??B ? A?BD．?A??B ? ?(A?B)

二、填空題（每小題3分，本題共15分）

6．命題公式P??P的真值是

7．若無(wú)向樹T有5個(gè)結(jié)點(diǎn)，則T的邊數(shù)為．

8．設(shè)正則m叉樹的樹葉數(shù)為t，分支數(shù)為i，則(m-1)i

9．設(shè)集合A={1，2}上的關(guān)系R＝{<1, 1>,<1, 2>}，則在R中僅需加一個(gè)元素，就可使新得到的關(guān)系為對(duì)稱的．

10．(?x)(A(x)→B(x，z)∨C(y))中的自由變?cè)校?/p>

三、邏輯公式翻譯（每小題6分，本題共12分）

11．將語(yǔ)句“今天上課．”翻譯成命題公式．

12．將語(yǔ)句“他去操場(chǎng)鍛煉，僅當(dāng)他有時(shí)間．”翻譯成命題公式．

四、判斷說(shuō)明題（每小題7分，本題共14分）

判斷下列各題正誤，并說(shuō)明理由．

13．設(shè)集合A={1，2}，B={3，4}，從A到B的關(guān)系為f={<1, 3>}，則f是A到B的函數(shù)．

14．設(shè)G是一個(gè)有4個(gè)結(jié)點(diǎn)10條邊的連通圖，則G為平面圖．

五．計(jì)算題（每小題12分，本題共36分）

15．試求出（P∨Q）→（R∨Q）的析取范式．

16．設(shè)A={{1}, 1, 2}，B={ 1, {2}}，試計(jì)算

（1）（A∩B）（2）（A∪B）（3）A ?（A∩B）．

17．圖G=，其中V={ a, b, c, d }，E={(a, b),(a, c),(a, d),(b, c),(b, d),(c, d)}，對(duì)應(yīng)邊的權(quán)值依次為1、2、3、1、4及5，試

（1）畫出G的圖形；

（2）寫出G的鄰接矩陣；

（3）求出G權(quán)最小的生成樹及其權(quán)值．

六、證明題（本題共8分）

18．試證明：若R與S是集合A上的自反關(guān)系，則R∩S也是集合A上的自反關(guān)系．

中央電大2010年7月離散數(shù)學(xué)

試題解答

(供參考)

一、單項(xiàng)選擇題（每小題3分，本題共15分）

1．B2．D3．B4．C5．B

二、填空題（每小題3分，本題共15分）

6．假（或F，或0）

7．48．t-

19． <2, 1>

10．z，y

三、邏輯公式翻譯（每小題6分，本題共12分）

11．設(shè)P：今天上課，（2分）則命題公式為：P．（6分）

12．設(shè) P：他去操場(chǎng)鍛煉，Q：他有時(shí)間，（2分）則命題公式為：P ?Q．（6分）

四、判斷說(shuō)明題（每小題7分，本題共14分）

13．錯(cuò)誤．（3分）因?yàn)锳中元素2沒有B中元素與之對(duì)應(yīng)，故f不是A到B的函數(shù)．（7分）

14．錯(cuò)誤．（3分）不滿足“設(shè)G是一個(gè)有v個(gè)結(jié)點(diǎn)e條邊的連通簡(jiǎn)單平面圖，若v≥3，則e≤3v-6．”（7分）

五．計(jì)算題（每小題12分，本題共36分）

15．（P∨Q）→（R∨Q）? ┐(P∨Q)∨（R∨Q）（4分）

?(┐P∧┐Q)∨（R∨Q）（8分）

?(┐P∧┐Q)∨R∨Q（析取范式）（12分）

16．（1）（A∩B）={1}（4分）

（2）（A∪B）={1, 2, {1}, {2}}（8分）

（3）A?（A∩B）={{1}, 1, 2}（12分）

17．（1）G的圖形表示如圖一所示：ad1

5b c（3分）圖一

（2）鄰接矩陣：

?0?1?10111?1??（6分）??1101?

?1110??

（3）最小的生成樹如圖二中的粗線所示：

a 3d5

b圖二1c

權(quán)為：1+1+3=5

六、證明題（本題共8分）

18．證明：設(shè)?x?A，因?yàn)镽自反，所以x R x，即< x, x>?R；

又因?yàn)镾自反，所以x R x，即< x, x >?S．即< x, x>?R∩S故R∩S自反．

10分）12分）（4分）（6分）（8分）（（

第四篇：2010年7月自考離散數(shù)學(xué)試題及答案

全國(guó)2010年7月自學(xué)考試離散數(shù)學(xué)試題

課程代碼：02324

一、單項(xiàng)選擇題（本大題共15小題，每小題1分，共15分）

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

1．下列句子不是命題的是（D）．．A．中華人民共和國(guó)的首都是北京 C．雪是黑色的

B．張三是學(xué)生 D．太好了！

2．下列式子不是謂詞合式公式的是（B）．．A．（?x）P(x)→R(y)B．(?x)┐P（x）?(?x)(P(x)→Q(x))C．(?x)(?y)(P(x)∧Q(y))→(?x)R(x)D．(?x)(P(x,y)→Q(x,z))∨(?z)R(x,z)3．下列式子為重言式的是（）A．(┐P∧R)→Q C．P∨(P∧Q)

B．P∨Q∧R→┐R D．(┐P∨Q)?(P→Q)4．在指定的解釋下，下列公式為真的是（）A．(?x)(P(x)∨Q(x)),P(x):x=1,Q(x):x=2,論域:{1,2} B．(?x)(P(x)∧Q(x)),P(x):x=1,Q(x):x=2,論域: {1,2} C．(?x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,論域:{3,4} D．(?x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,論域:{3,4} 5．對(duì)于公式(?x)(?y)(P(x)∧Q(y))→(?x)R(x,y)，下列說(shuō)法正確的是（）A．y是自由變?cè)?C．(?x)的轄域是R(x, y)

B．y是約束變?cè)?/p>

D．(?x)的轄域是(?y)(P(x)∧Q(y))→(?x)R(x,y)6．設(shè)論域?yàn)閧1,2}，與公式(?x)A(x)等價(jià)的是（）A．A(1)∨A(2)C．A(1)∧A(2)

B．A(1)→A(2)D．A(2)→A(1)7．設(shè)Z+是正整數(shù)集，R是實(shí)數(shù)集，f:Z+→R, f(n)=log2n ,則f（）A．僅是入射 C．是雙射

B．僅是滿射 D．不是函數(shù)

8．下列關(guān)系矩陣所對(duì)應(yīng)的關(guān)系具有反對(duì)稱性的是（）

?1?A．?0??10101??1 ?0???1?B．?0??10100??1 ?1??

全國(guó)2010年7月自學(xué)考試離散數(shù)學(xué)試題

?0C．?0???10001??1 ?0???1D．?0???10101??0 ?0??9．設(shè)R1和R2是集合A上的相容關(guān)系，下列關(guān)于復(fù)合關(guān)系R1?R2的說(shuō)法正確的是（）A．一定是等價(jià)關(guān)系 C．一定不是相容關(guān)系

10．下列運(yùn)算不滿足交換律的是（）．．．A．a(chǎn)*b=a+2b C．a(chǎn)*b=|a-b|

B．a(chǎn)*b=min(a,b)D．a(chǎn)*b=2ab B．一定是相容關(guān)系

D．可能是也可能不是相容關(guān)系

11．設(shè)A是偶數(shù)集合，下列說(shuō)法正確的是（）A．是群 C．是群

B．是群

D．, ,都不是群

12．設(shè)*是集合A上的二元運(yùn)算，下列說(shuō)法正確的是（）A．在A中有關(guān)于運(yùn)算*的左幺元一定有右幺元 B．在A中有關(guān)于運(yùn)算*的左右幺元一定有幺元 C．在A中有關(guān)于運(yùn)算*的左右幺元，它們不一定相同 D．在A中有關(guān)于運(yùn)算*的幺元不一定有左右幺元 13．題13圖的最大出度是（）A．0 C．2 14．下列圖是歐拉圖的是（）

B．1 D．3

15．一棵樹的3個(gè)4度點(diǎn)，4個(gè)2度點(diǎn)，其它的都是1度，那么這棵樹的邊數(shù)是（）A．13 C．15

B．14 D．16

二、填空題（本大題共10小題，每小題2分，共20分）請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。

16．請(qǐng)寫出表示德摩根律的兩個(gè)命題公式等價(jià)定理___________，___________。

17．n個(gè)命題變?cè)腳__________稱為小項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)出現(xiàn)，但兩者必須___________。18．前提引入規(guī)則：在證明的任何步驟上都可以___________，簡(jiǎn)稱___________規(guī)則。

19．自由變?cè)胍?guī)則是指對(duì)某___________出現(xiàn)的個(gè)體變?cè)捎脗€(gè)體常元或用與原子公式中所有個(gè)體變?cè)煌膫€(gè)體變?cè)ゴ耄襙__________。20．設(shè)A=?,B={2,4}，則((A)=___________，A×B___________。

21．設(shè)A={1,2,3,4}, A上的二元關(guān)系R={<1,2>,<2,4>,<3,3>},S={<1,3>,<2,4>,<4,2>}，則R2?S=___________，全國(guó)2010年7月自學(xué)考試離散數(shù)學(xué)試題

(R)=___________。

22．設(shè)代數(shù)系統(tǒng)是環(huán)，則是___________，是___________。

23．在中，元素2的階為___________，它生成的子群為___________，其中?7為模7乘法。24．設(shè)是一個(gè)___________，如果A中任意兩個(gè)元素都有___________，則稱為格。25．若一條___________中，所有的___________均不相同，稱為跡。

三、計(jì)算題（本大題共6小題，每小題5分，共30分）

26．給定論域D={1,2}，f(1)=2, f(2)=1, S(1)=F, S(2)=T, G(1,2)=T, G(2,1)=T,在該賦值下，求式子?x(S(f(x))∧G(x, f(x)))的真值。

27．請(qǐng)通過(guò)等值演算法求┐(P∧Q)→(P∨Q)的主析取范式。

28．設(shè)A={1,2,3,4}，給定A上二元關(guān)系R={<1,1>,<1,2>,<2,4>,<4,2>}，求R的傳遞閉包。29．對(duì)題29圖所示格，找出它的所有的4元子格。

30．用矩陣的方法求題30圖中結(jié)點(diǎn)ui，u5之間長(zhǎng)度為2的路徑的數(shù)目。

31．求題31圖的最小生成樹。

四、證明題（本大題共3小題，第32小題8分，第33、34小題各6分，共20分）32．用推理方法證明(A∨B)→(C∧D),(D∨F)→E├A→E。

33．證明：設(shè)是一個(gè)群，則對(duì)于任意a,b∈G，必存在惟一的x∈G使得a·x=b。34．設(shè)圖G有n個(gè)結(jié)點(diǎn)，n+1條邊，證明：G中至少有一個(gè)結(jié)點(diǎn)度數(shù)≥3。

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

35．符合化下列命題，并構(gòu)造推理證明：三角函數(shù)都是周期函數(shù)，有些三角函數(shù)是連續(xù)函數(shù)，所以有些周期函數(shù)是連續(xù)函數(shù)。

36．兩個(gè)等價(jià)關(guān)系的并集不一定是等價(jià)關(guān)系，試舉例說(shuō)明。-12

全國(guó)2010年7月自學(xué)考試離散數(shù)學(xué)試題

2010年7月全國(guó)自考離散數(shù)學(xué)試題參考答案

全國(guó)2010年7月自學(xué)考試離散數(shù)學(xué)試題

全國(guó)2010年7月自學(xué)考試離散數(shù)學(xué)試題

全國(guó)2010年7月自學(xué)考試離散數(shù)學(xué)試題

全國(guó)2010年7月自學(xué)考試離散數(shù)學(xué)試題

第五篇：2010年7月自考離散數(shù)學(xué)試題及答案

一、單項(xiàng)選擇題（本大題共15小題，每小題1分，共15分）

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

1．下列句子不是命題的是（D）．．A．中華人民共和國(guó)的首都是北京 C．雪是黑色的

B．張三是學(xué)生 D．太好了！

2．下列式子不是謂詞合式公式的是（B）．．A．（?x）P(x)→R(y)B．(?x)┐P（x）?(?x)(P(x)→Q(x))C．(?x)(?y)(P(x)∧Q(y))→(?x)R(x)D．(?x)(P(x,y)→Q(x,z))∨(?z)R(x,z)3．下列式子為重言式的是（）A．(┐P∧R)→Q C．P∨(P∧Q)

B．P∨Q∧R→┐R D．(┐P∨Q)?(P→Q)4．在指定的解釋下，下列公式為真的是（）A．(?x)(P(x)∨Q(x)),P(x):x=1,Q(x):x=2,論域:{1,2} B．(?x)(P(x)∧Q(x)),P(x):x=1,Q(x):x=2,論域: {1,2} C．(?x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,論域:{3,4} D．(?x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,論域:{3,4} 5．對(duì)于公式(?x)(?y)(P(x)∧Q(y))→(?x)R(x,y)，下列說(shuō)法正確的是（）A．y是自由變?cè)?C．(?x)的轄域是R(x, y)

B．y是約束變?cè)?/p>

D．(?x)的轄域是(?y)(P(x)∧Q(y))→(?x)R(x,y)6．設(shè)論域?yàn)閧1,2}，與公式(?x)A(x)等價(jià)的是（）A．A(1)∨A(2)C．A(1)∧A(2)

B．A(1)→A(2)D．A(2)→A(1)7．設(shè)Z+是正整數(shù)集，R是實(shí)數(shù)集，f:Z+→R, f(n)=log2n ,則f（）A．僅是入射 C．是雙射

B．僅是滿射 D．不是函數(shù)

8．下列關(guān)系矩陣所對(duì)應(yīng)的關(guān)系具有反對(duì)稱性的是（）?101???A．?011?

??100???001???C．?001?

??100???100???B．?011?

??101???101???D．?010?

??100??9．設(shè)R1和R2是集合A上的相容關(guān)系，下列關(guān)于復(fù)合關(guān)系R1?R2的說(shuō)法正確的是（）A．一定是等價(jià)關(guān)系

B．一定是相容關(guān)系

全國(guó)2010年7月自學(xué)考試離散數(shù)學(xué)試題

C．一定不是相容關(guān)系

10．下列運(yùn)算不滿足交換律的是（）．．．A．a(chǎn)*b=a+2b C．a(chǎn)*b=|a-b|

D．可能是也可能不是相容關(guān)系

B．a(chǎn)*b=min(a,b)D．a(chǎn)*b=2ab

11．設(shè)A是偶數(shù)集合，下列說(shuō)法正確的是（）A．是群 C．是群

B．是群

D．, ,都不是群

12．設(shè)*是集合A上的二元運(yùn)算，下列說(shuō)法正確的是（）A．在A中有關(guān)于運(yùn)算*的左幺元一定有右幺元 B．在A中有關(guān)于運(yùn)算*的左右幺元一定有幺元 C．在A中有關(guān)于運(yùn)算*的左右幺元，它們不一定相同 D．在A中有關(guān)于運(yùn)算*的幺元不一定有左右幺元 13．題13圖的最大出度是（）A．0 C．2 14．下列圖是歐拉圖的是（）

B．1 D．3

15．一棵樹的3個(gè)4度點(diǎn)，4個(gè)2度點(diǎn)，其它的都是1度，那么這棵樹的邊數(shù)是（）A．13 C．15

B．14 D．16

二、填空題（本大題共10小題，每小題2分，共20分）請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。

16．請(qǐng)寫出表示德摩根律的兩個(gè)命題公式等價(jià)定理___________，___________。

17．n個(gè)命題變?cè)腳__________稱為小項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)出現(xiàn)，但兩者必須___________。18．前提引入規(guī)則：在證明的任何步驟上都可以___________，簡(jiǎn)稱___________規(guī)則。

19．自由變?cè)胍?guī)則是指對(duì)某___________出現(xiàn)的個(gè)體變?cè)捎脗€(gè)體常元或用與原子公式中所有個(gè)體變?cè)煌膫€(gè)體變?cè)ゴ耄襙__________。

20．設(shè)A=?,B={2,4}，則((A)=___________，A×B___________。

21．設(shè)A={1,2,3,4}, A上的二元關(guān)系R={<1,2>,<2,4>,<3,3>},S={<1,3>,<2,4>,<4,2>}，則R2?S=___________，(R-1)2=___________。

22．設(shè)代數(shù)系統(tǒng)是環(huán)，則是___________，是___________。

23．在中，元素2的階為___________，它生成的子群為___________，其中?7為模7乘法。24．設(shè)是一個(gè)___________，如果A中任意兩個(gè)元素都有___________，則稱為格。25．若一條___________中，所有的___________均不相同，稱為跡。

全國(guó)2010年7月自學(xué)考試離散數(shù)學(xué)試題

三、計(jì)算題（本大題共6小題，每小題5分，共30分）

26．給定論域D={1,2}，f(1)=2, f(2)=1, S(1)=F, S(2)=T, G(1,2)=T, G(2,1)=T,在該賦值下，求式子?x(S(f(x))∧G(x, f(x)))的真值。

27．請(qǐng)通過(guò)等值演算法求┐(P∧Q)→(P∨Q)的主析取范式。

28．設(shè)A={1,2,3,4}，給定A上二元關(guān)系R={<1,1>,<1,2>,<2,4>,<4,2>}，求R的傳遞閉包。29．對(duì)題29圖所示格，找出它的所有的4元子格。

30．用矩陣的方法求題30圖中結(jié)點(diǎn)ui，u5之間長(zhǎng)度為2的路徑的數(shù)目。

31．求題31圖的最小生成樹。

四、證明題（本大題共3小題，第32小題8分，第33、34小題各6分，共20分）32．用推理方法證明(A∨B)→(C∧D),(D∨F)→E├A→E。

33．證明：設(shè)是一個(gè)群，則對(duì)于任意a,b∈G，必存在惟一的x∈G使得a·x=b。34．設(shè)圖G有n個(gè)結(jié)點(diǎn)，n+1條邊，證明：G中至少有一個(gè)結(jié)點(diǎn)度數(shù)≥3。

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

35．符合化下列命題，并構(gòu)造推理證明：三角函數(shù)都是周期函數(shù)，有些三角函數(shù)是連續(xù)函數(shù)，所以有些周期函數(shù)是連續(xù)函數(shù)。

36．兩個(gè)等價(jià)關(guān)系的并集不一定是等價(jià)關(guān)系，試舉例說(shuō)明。

全國(guó)2010年7月自學(xué)考試離散數(shù)學(xué)試題

全國(guó)2010年7月自學(xué)考試離散數(shù)學(xué)試題

全國(guó)2010年7月自學(xué)考試離散數(shù)學(xué)試題

全國(guó)2010年7月自學(xué)考試離散數(shù)學(xué)試題

全國(guó)2010年7月自學(xué)考試離散數(shù)學(xué)試題