第一篇:2009年4月離散數(shù)學(xué)試題(附答案)
全國(guó)2009年4月自學(xué)考試離散數(shù)學(xué)試題(附答案)
課程代碼:02324
一、單項(xiàng)選擇題(本大題共15小題,每小題1分,共15分)
在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的,請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。/S 1.下列為兩個(gè)命題變?cè)狿,Q的小項(xiàng)是()A.P∧Q∧? P B.? P∨Q C.? P∧Q
D.? P∨P∨Q 2.下列語(yǔ)句中是真命題的是()A.我正在說(shuō)謊
B.嚴(yán)禁吸煙
C.如果1+2=3,那么雪是黑的
D.如果1+2=5,那么雪是黑的 3.設(shè)P:我們劃船,Q:我們跑步。命題“我們不能既劃船又跑步”符號(hào)化為()A.? P∧? Q B.? P∨? Q C.?(P?Q)
D.?(? P∨? Q)
4.命題公式(P∧(P→Q))→Q是()A.矛盾式 B.蘊(yùn)含式 C.重言式
D.等價(jià)式
5.命題公式?(P∧Q)→R的成真指派是()A.000,001,110,B.001,011,101,110,111 C.全體指派
D.無(wú)
6.在公式(?x)F(x,y)→(? y)G(x,y)中變?cè)獂是()A.自由變?cè)?/p>
B.約束變?cè)?/p>
C.既是自由變?cè)质羌s束變?cè)?/p>
D.既不是自由變?cè)植皇羌s束變?cè)?/p>
7.集合A={1,2,?,10}上的關(guān)系R={
C.傳遞的、對(duì)稱的
D.反自反的、傳遞的
8.若R和S是集合A上的兩個(gè)關(guān)系,則下述結(jié)論正確的是()A.若R和S是自反的,則R∩S是自反的 B.若R和S是對(duì)稱的,則R?S是對(duì)稱的 C.若R和S是反對(duì)稱的,則R?S是反對(duì)稱的 D.若R和S是傳遞的,則R∪S是傳遞的
全國(guó)2009年4月自學(xué)考試離散數(shù)學(xué)試題)
9.R={<1,4>,<2,3>,<3,1>,<4,3>},則下列不是..t(R)中元素的是()A.<1,1> C.<1,3>
B.<1,2> D.<1,4> 10.設(shè)A={{1,2,3},{4,5},{6,7,8}},下列選項(xiàng)正確的是()A.1∈A C.{{4,5}}?A
B.{1,2,3}?A D.?∈A 11.在自然數(shù)集N上,下列運(yùn)算是可結(jié)合的是()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=|a-b| 12.在代數(shù)系統(tǒng)中,整環(huán)和域的關(guān)系是()A.整環(huán)一定是域 C.域一定是整環(huán)
B.域不一定是整環(huán) D.域一定不是整環(huán)
13.下列所示的哈斯圖所對(duì)應(yīng)的偏序集中能構(gòu)成格的是()
A. B.
C. D.
14.設(shè)G為有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖,則有()A.Δ(G)<n C.Δ(G)>n
B.Δ(G)≤n D.Δ(G)≥n
15.具有4個(gè)結(jié)點(diǎn)的非同構(gòu)的無(wú)向樹(shù)的數(shù)目是()A.2 C.4
二、填空題(本大題共10小題,每小題2分,共20分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。
B.3 D.5 16.(?x)(?y)(P(x,y)Q(y,z))∧?xP(x,y)中?x的轄域?yàn)開(kāi)_______,?x的轄域?yàn)開(kāi)_______。17.兩個(gè)重言式的析取是________式,一個(gè)重言式與一個(gè)矛盾式的析取是________式。
18.設(shè)N是自然數(shù)集合,f和g是N到N的函數(shù),且f(n)=2n+1,g(n)=n,那么復(fù)合函數(shù)(f?f)(n)
全國(guó)2009年4月自學(xué)考試離散數(shù)學(xué)試題
2=________(g?f)(n)=________。
19.設(shè)復(fù)合函數(shù)g?f是從A到C的函數(shù),如果g?f是滿射,那么________必是滿射,如果g?f是入射,那么________必是入射。
20.設(shè)A={1,2},B={2,3},則A-A=________,A-B=________。
21.設(shè)S是非空有限集,代數(shù)系統(tǒng)
中,其中P(S)為集合S的冪集,則P(S)對(duì)∪運(yùn)算的單位元是________,零元是________。
+>中,2的階是________。22.在
?0125.設(shè)圖D=
三、計(jì)算題(本大題共5小題,第26、27小題各5分,第28、29小題各6分,第30小題8分,共30分)
+B,A的冪集P(A)26.已知A={{?},{?,1}},B={{?,1},{1}},計(jì)算A∪B,A○。
27.構(gòu)造命題公式((P∧Q)→P)∨R的真值表。
28.下圖給出了一個(gè)有向圖。(1)求出它的鄰接矩陣A;(2)求出A2,A3,A4及可達(dá)矩陣P。
29.求下列公式的主合取范式和主析取范式:P∨(? P→(Q∨(? Q→R)))
30.設(shè)A={1,2,3,4,6,8,12,24},R為A上的整除關(guān)系,試畫(huà)的哈斯圖,并求A中的最大元、最小元、極大元、極小元。
四、證明題(本大題共3小題,第31、32小題各6分,第33小題8分,共20分)31.在整數(shù)集Z上定義:a?b?a?b?2,?a,b?Z,證明:
全國(guó)2009年4月自學(xué)考試離散數(shù)學(xué)試題
33.證明:邊e是圖G的一條割邊,當(dāng)且僅當(dāng)圖G中不存在包含邊e的簡(jiǎn)單回路。
五、應(yīng)用題(本大題共2小題,第34小題6分,第35小題9分,共15分)34.構(gòu)造下面推理的證明。
如果小張和小王去看電影,則小李也去看電影。小趙不去看電影或小張去看電影。小王去看電影。所以,當(dāng)小趙去看電影時(shí),小李也去。
35.今有n個(gè)人,已知他們中任何2人的朋友合起來(lái)一定包含其余n-2人。試證明:
(1)當(dāng)n≥3時(shí),這n個(gè)人能排成一列,使得中間任何人是其兩旁的人的朋友,而兩頭的人是其左邊(或右邊)的人的朋友。
(2)當(dāng)n≥4時(shí),這n個(gè)人能排成一圓圈,使得每個(gè)人是其兩旁的人的朋友。
全國(guó)2009年4月自學(xué)考試離散數(shù)學(xué)試題
第二篇:離散數(shù)學(xué)試題+答案
www.tmdps.cn 專注于收集各類歷年試卷和答案
一、單項(xiàng)選擇題(本大題共15小題,每小題1分,共15分)在每小題列出的四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)是符合題目要求的,請(qǐng)將正確選項(xiàng)前的字母填在題后的括號(hào)內(nèi)。1.一個(gè)連通的無(wú)向圖G,如果它的所有結(jié)點(diǎn)的度數(shù)都是偶數(shù),那么它具有一條()A.漢密爾頓回路
B.歐拉回路 C.漢密爾頓通路
D.初級(jí)回路
2.設(shè)G是連通簡(jiǎn)單平面圖,G中有11個(gè)頂點(diǎn)5個(gè)面,則G中的邊是()A.10
B.12
C.16
D.14 3.在布爾代數(shù)L中,表達(dá)式(a∧b)∨(a∧b∧c)∨(b∧c)的等價(jià)式是()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ù)乘法運(yùn)算,則G=<{1,-1,i,-i},·>是群,下列是G的子群是()A.<{1},·>
B.〈{-1},·〉
C.〈{i},·〉
D.〈{-i},·〉
5.設(shè)Z為整數(shù)集,A為集合,A的冪集為P(A),+、-、/為數(shù)的加、減、除運(yùn)算,∩為集合的交運(yùn)算,下列系統(tǒng)中是代數(shù)系統(tǒng)的有()A.〈Z,+,/〉
B.〈Z,/〉 C.〈Z,-,/〉
D.〈P(A),∩〉 6.下列各代數(shù)系統(tǒng)中不含有零元素的是()A.〈Q,*〉Q是全體有理數(shù)集,*是數(shù)的乘法運(yùn)算
B.〈Mn(R),*〉,Mn(R)是全體n階實(shí)矩陣集合,*是矩陣乘法運(yùn)算 C.〈Z,?〉,Z是整數(shù)集,?定義為x?xy=xy,?x,y∈Z D.〈Z,+〉,Z是整數(shù)集,+是數(shù)的加法運(yùn)算
7.設(shè)A={1,2,3},A上二元關(guān)系R的關(guān)系圖如下: R具有的性質(zhì)是 A.自反性 B.對(duì)稱性 C.傳遞性 D.反自反性
8.設(shè)A={a,b,c},A上二元關(guān)系R={〈a,a〉,〈b,b〉〈,a,c〉},則關(guān)系R的對(duì)稱閉包S(R)是()A.R∪IA
B.R
C.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上的等價(jià)關(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í)數(shù)集,a=0,f(x,y)=x-y,A(x,y):x www.tmdps.cn 專注于收集各類歷年試卷和答案 D.(?x)(?y)(A(x,y)→A(f(x,a),a))12.設(shè)B是不含變?cè)獂的公式,謂詞公式(?x)(A(x)→B)等價(jià)于()A.(?x)A(x)→B B.(?x)A(x)→B C.A(x)→B D.(?x)A(x)→(?x)B 13.謂詞公式(?x)(P(x,y))→(?z)Q(x,z)∧(?y)R(x,y)中變?cè)獂()A.是自由變?cè)皇羌s束變?cè)?B.既不是自由變?cè)植皇羌s束變?cè)?C.既是自由變?cè)质羌s束變?cè)?D.是約束變?cè)皇亲杂勺冊(cè)?/p> 14.若P:他聰明;Q:他用功;則“他雖聰明,但不用功”,可符號(hào)化為()A.P∨Q B.P∧┐Q C.P→┐Q D.P∨┐Q 15.以下命題公式中,為永假式的是()A.p→(p∨q∨r) B.(p→┐p)→┐p C.┐(q→q)∧p D.┐(q∨┐p)→(p∧┐p) 二、填空題(每空1分,共20分)16.在一棵根樹(shù)中,僅有一個(gè)結(jié)點(diǎn)的入度為_(kāi)_____,稱為樹(shù)根,其余結(jié)點(diǎn)的入度均為_(kāi)_____。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,如果對(duì)X中的任意兩個(gè)不同的x1和x2,它們的象y1和y2也不同,我們說(shuō)f是______函數(shù),如果ranf=Y,則稱f是______函數(shù)。 21.設(shè)R為非空集合A上的等價(jià)關(guān)系,其等價(jià)類記為〔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是要死的,則命題“所有的人都是要死的”可符號(hào)化為(?x)______,其中量詞(?x)的轄域是______。24.若H1∧H2∧?∧Hn是______,則稱H1,H2,?Hn是相容的,若H1∧H2∧?∧Hn是______,則稱H1,H2,?Hn是不相容的。 25.判斷一個(gè)語(yǔ)句是否為命題,首先要看它是否為,然后再看它是否具有唯一的。 三、計(jì)算題(共30分)26.(4分)設(shè)有向圖G=(V,E)如下圖所示,試用鄰接矩陣方法求長(zhǎng)度為2的路的總數(shù)和回路總數(shù)。 27.(5)設(shè)A={a,b},P(A)是A的冪集,?是對(duì)稱差運(yùn)算,可以驗(yàn)證 是群。設(shè)n是正整數(shù),求({a}-1{b}{a})n?{a}-n{b}n{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; www.tmdps.cn 專注于收集各類歷年試卷和答案 (1)作出偏序關(guān)系R的哈斯圖 (2)令B={1,2,3,5},求B的最大,最小元,極大、極小元,上界,下確界,下界,下確界。29.(6分)求┐(P→Q)?(P→┐Q)的主合取范式并給出所有使命題為真的賦值。 30.(5分)設(shè)帶權(quán)無(wú)向圖G如下,求G的最小生成樹(shù)T及T的權(quán)總和,要求寫(xiě)出解的過(guò)程。 31.(4分)求公式┐((?x)F(x,y)→(?y)G(x,y))∨(?x)H(x)的前束范式。 四、證明題(共20分)32.(6分)設(shè)T是非平凡的無(wú)向樹(shù),T中度數(shù)最大的頂點(diǎn)有2個(gè),它們的度數(shù)為k(k≥2),證明T中至少有2k-2片樹(shù)葉。 33.(8分)設(shè)A是非空集合,F(xiàn)是所有從A到A的雙射函數(shù)的集合,?是函數(shù)復(fù)合運(yùn)算。 證明:〈F, ?〉是群。 34.(6分)在個(gè)體域D={a1,a2,?,an}中證明等價(jià)式: (?x)(A(x)→B(x))?(?x)A(x)→(?x)B(x) 五、應(yīng)用題(共15分)35.(9分)如果他是計(jì)算機(jī)系本科生或者是計(jì)算機(jī)系研究生,那么他一定學(xué)過(guò)DELPHI語(yǔ)言而且學(xué)過(guò)C++語(yǔ)言。只要他學(xué)過(guò)DELPHI語(yǔ)言或者C++語(yǔ)言,那么他就會(huì)編程序。因此如果他是計(jì)算機(jī)系本科生,那么他就會(huì)編程序。請(qǐng)用命題邏輯推理方法,證明該推理的有效結(jié)論。 36.(6分)一次學(xué)術(shù)會(huì)議的理事會(huì)共有20個(gè)人參加,他們之間有的相互認(rèn)識(shí)但有的相互不認(rèn)識(shí)。但對(duì)任意兩個(gè)人,他們各自認(rèn)識(shí)的人的數(shù)目之和不小于20。問(wèn)能否把這20個(gè)人排在圓桌旁,使得任意一個(gè)人認(rèn)識(shí)其旁邊的兩個(gè)人?根據(jù)是什么? 參考答案 一、單項(xiàng)選擇題(本大題共15小題,每小題1分,共15分) 1.B 2.D 3.A 4.A 5.D 6.D 7.D 8.C 9.D 10.B 11.A 12.A 13.C 14.B 15.C 二、填空題 16.0 17.1 0 18.單位元 19.x∩y x∪y 20.入射 滿射 21.[x]R=[y]R 22.A(x) B(y)23.(M(x)→D(x)) M(x)→D(x) www.tmdps.cn 專注于收集各類歷年試卷和答案 24.可滿足式 永假式(或矛盾式)25.陳述句 真值 三、計(jì)算題 ?1100??1010???26.M=?? 1011????0011???2?2?M=??2??1110?111??? 121?011??M2ij?18,ij?6 ?M2i?1??i?1j?144 G中長(zhǎng)度為2的路總數(shù)為18,長(zhǎng)度為2的回路總數(shù)為6。 27.當(dāng)n是偶數(shù)時(shí),?x∈P(A),xn=? 當(dāng)n是奇數(shù)時(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ù)時(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的最大元:無(wú),最小元:無(wú); 極大元:2,5,極小元:1,3 下界:4,下確界4; 上界:無(wú),上確界:無(wú) 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 www.tmdps.cn 專注于收集各類歷年試卷和答案 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=15 31.原式?┐(?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片樹(shù)葉,y個(gè)分支點(diǎn)。于是T中有x+y個(gè)頂點(diǎn),有x+y-1 條邊,由握手定理知T中所有頂點(diǎn)的度數(shù)之的 x?y ?d(vi)=2(x+y-1)。 i?又樹(shù)葉的度為1,任一分支點(diǎn)的度大于等于2 且度最大的頂點(diǎn)必是分支點(diǎn),于是 x?y ?d(vi)≥x·1+2(y-2)+k+k=x+2y+2K-4 i?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,因?yàn)閒和g都是A到A的雙射函數(shù),故f?g也是A到A的雙射函數(shù),從而集合F關(guān)于運(yùn)算?是封閉的。 (2)?f,g,h∈F,由函數(shù)復(fù)合運(yùn)算的結(jié)合律有f?(g?h)=(f?g)?h故運(yùn)算?是可結(jié)合的。 (3)A上的恒等函數(shù)IA也是A到A的雙射函數(shù)即IA∈F,且?f∈F有IA?f=f?IA=f,故IA是〈F,?〉中的幺元 (4)?f∈F,因?yàn)閒是雙射函數(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)) www.tmdps.cn 專注于收集各類歷年試卷和答案 ?(┐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:他是計(jì)算機(jī)系本科生 q:他是計(jì)算機(jī)系研究生 r:他學(xué)過(guò)DELPHI語(yǔ)言 s:他學(xué)過(guò)C++語(yǔ)言 t:他會(huì)編程序 前提:(p∨q)→(r∧s),(r∨s)→t 結(jié)論:p→t 證①p P(附加前提) ②p∨q T①I ③(p∨q)→(r∧s) P(前提引入) ④r∧s T②③I ⑤r T④I ⑥r(nóng)∨s T⑤I ⑦(r∨s)→t P(前提引入) ⑧t T⑤⑥I 36.可以把這20個(gè)人排在圓桌旁,使得任一人認(rèn)識(shí)其旁邊的兩個(gè)人。 根據(jù):構(gòu)造無(wú)向簡(jiǎn)單圖G= ?Vi∈V,d(vi)是與vi相互認(rèn)識(shí)的人的數(shù)目,由題意知?vi,vj∈V有d(vi)+d(vj)?20,于是G中存在漢密爾頓回路。 設(shè)C=Vi1Vi2?Vi20Vi1是G中一條漢密爾頓回路,按這條回路的順序按其排座位即符合要求。 《離散數(shù)學(xué)》試題及答案 一、選擇題:本題共5小題,每小題3分,共15分,在每小題給出的四個(gè)選項(xiàng)中,只有一項(xiàng)是符合題目要求的。 1.命題公式(P?Q)?Q為() (A)矛盾式(B)可滿足式(C)重言式(D)合取范式 2.設(shè)P表示“天下大雨”,Q表示“他在室內(nèi)運(yùn)動(dòng)”,則命題“除非天下大雨,否則他不在室內(nèi)運(yùn)動(dòng)”符號(hào)化為()。 (A). P?Q;(B).P?Q;(C).?P??Q;(D).?P?Q. 3.設(shè)集合A={{1,2,3}, {4,5}, {6,7,8}},則下式為真的是() (A)1?A(B){1,2, 3}?A (C){{4,5}}?A(D)??A 4.設(shè)A={1,2},B={a,b,c},C={c,d}, 則A×(B?C)=() (A){<1,c>,<2,c>}(B){ 5.設(shè)G如右圖:那么G不是().(A)哈密頓圖;(B)完全圖; (C)歐拉圖;(D)平面圖.二、填空題:本大題共5小題,每小題4分,共20 6.設(shè)集合A={?,{a}},則A的冪集P(A7.設(shè)集合A={1,2,3,4 }, B={6,8,12}, A到B的關(guān)系R={?x,y?y?2x,x?A,y?B},那么R1=- 8.在“同學(xué),老鄉(xiāng),親戚,朋友”四個(gè)關(guān)系中_______是等價(jià)關(guān)系.9.寫(xiě)出一個(gè)不含“?”的邏輯聯(lián)結(jié)詞的完備集.10.設(shè)X={a,b,c},R是X上的二元關(guān)系,其關(guān)系矩陣為 ?101??,那么R的關(guān)系圖為 MR=?100????100?? 三、證明題(共30分) 11.(10分)已知A、B、C是三個(gè)集合,證明A∩(B∪C)=(A∩B)∪(A∩C) 12.(10分)構(gòu)造證明:(P?(Q?S))∧(?R∨P)∧Q?R?S (0,1)13.(10分)證明與[0,1),[0,1)與[0,1]等勢(shì)。 四、解答題(共35分) 14.(7分)構(gòu)造三階幻方(以1為首項(xiàng)的9個(gè)連續(xù)自然數(shù)正好布滿一個(gè)3?3方陣,且方陣中的每一行, 每一列及主、副對(duì)角線上的各數(shù)之和都相等.) 15.(8分)求命題公式(P?Q)?(?P??Q)的真值表.16.(10分)設(shè)R1是A1={1,2}到A2=(a,b,c)的二元關(guān)系,R2是A2到A3={?,?}的二元關(guān)系,R1= {<1,a>,<1,b>,<2,c>}, R2={,} 畢節(jié)學(xué)院《離散數(shù)學(xué) 》課程試卷 求R1?R2的集合表達(dá)式.17.(10分)某項(xiàng)工作需要派A、B、C和D 4個(gè)人中的2個(gè)人去完成,按下面3個(gè)條件,有幾種派法?如何派? 三個(gè)條件:(1)若A去,則C和D中要去1個(gè)人;(2)B和C不能都去; (3)若C去,則D留下。 一、單項(xiàng)選擇題(每小題3分,共15分) 1.B2.C3.C4.A5.B 二、填空題(每小題4分,共20分) 6.{?,{?},{{a}},{?,{a}}} 7.{<6,3>,<8,4> }8.老鄉(xiāng) 9.{?,?}或{?,?} 或 {?}或 {?} 10.見(jiàn) f(0)?0??111?························································································ 10分 ,n?1,?A ·?f()?n?1n?n ??f(x)?x,x?[0,1)?A 14.85 1 2 7 6 填對(duì)每個(gè)格得1分。 15.表中最后一列的數(shù)中,每對(duì)1個(gè)數(shù)得2分.?110?16.MR1???,(2分)001?? MR2?01??(4分)??01????00?? ?01??01???01?(6分)???00?????00???110? MR1?R2????001? R1?R2?{?1,??}(10分) 17.解設(shè)A:A去工作;B:B去工作;C:C去工作;D:D去工作。則根據(jù)題意應(yīng)有:A?C?D,?(B∧C),C??D必須同時(shí)成立。······························································································ 2分 因此(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 ··································································································································· 8分 畢節(jié)學(xué)院《離散數(shù)學(xué) 》課程試卷 故有三種派法:B∧D,A∧C,A∧D。······································································· 10分 畢節(jié)學(xué)院《離散數(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ú)向樹(shù)T中有8個(gè)頂點(diǎn),4度、3度、2度的分支點(diǎn)各一個(gè),T的樹(shù)葉數(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ú)向樹(shù)T有5個(gè)結(jié)點(diǎn),則T的邊數(shù)為. 8.設(shè)正則m叉樹(shù)的樹(shù)葉數(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= (1)畫(huà)出G的圖形; (2)寫(xiě)出G的鄰接矩陣; (3)求出G權(quán)最小的生成樹(shù)及其權(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沒(méi)有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)最小的生成樹(shù)如圖二中的粗線所示: 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分)(( 全國(guó)2008年4月自考離散數(shù)學(xué)試題 課程代碼:02324 一、單項(xiàng)選擇題(本大題共15小題,每小題1分,共15分) 在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的,請(qǐng)將其代碼填寫(xiě)在題后的括號(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={, 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= 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è)命題,德摩根律可表示為_(kāi)____________,吸收律可表示為_(kāi)___________。 19.對(duì)于公式 x(P(x)∨Q(x)),其中P(x)∶x=1,Q(x)∶x=2,當(dāng)論域?yàn)閧1,2}時(shí),其真值為_(kāi)____________ ,當(dāng)論域?yàn)閧0,1,2}時(shí),其真值為_(kāi)____________。 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)=_____________。 23.設(shè)圖G 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={,, 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={,,, , , 30.給定圖G如圖所示,(1)G中長(zhǎng)度為4的路有幾條?其中有幾條回路?(2)寫(xiě)出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是A上的等價(jià)關(guān)系。 33.設(shè)有G= 五、應(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是完全二叉樹(shù),G有7個(gè)點(diǎn),其中4個(gè)葉點(diǎn),則G的總度數(shù)為_(kāi)_________,分枝點(diǎn)數(shù)為_(kāi)_______________.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以集合形式(列舉法)記為_(kāi)__________ _______________________________________________________.14.設(shè)一階邏輯公式G = xP(x)?xQ(x),則G的前束范式是__________________________ _____.15.設(shè)G是具有8個(gè)頂點(diǎn)的樹(shù),則G中增加_________條邊才能把G變成完全圖。 16.設(shè)謂詞的定義域?yàn)閧a, b},將表達(dá)式xR(x)→xS(x)中量詞消除,寫(xiě)成與之對(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)把門(mén)關(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)的度,能畫(huà)出圖的是().(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中刪去()條邊可以得到樹(shù).(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)畫(huà)出半序集(A,R)的哈斯圖; (2)寫(xiě)出A的子集B = {3,6,9,12}的上界,下界,最小上界,最大下界; (3)寫(xiě)出A的最大元,最小元,極大元,極小元。 2.設(shè)集合A={1, 2, 3, 4},A上的關(guān)系R={(x,y)| x, y?A 且 x ? y}, 求 (1)畫(huà)出R的關(guān)系圖; (2)寫(xiě)出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)畫(huà)出半序集(A,R)的哈斯圖; (2)寫(xiě)出A的最大元,最小元,極大元,極小元; (3)寫(xiě)出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)畫(huà)出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)試寫(xiě)出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.集合A={x|x是整數(shù),<30},B={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={a,b,c,d,e,f,g},A的一個(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的子集B={2,4,6},則在(S,≤)中,B的最大元是_____;B的最小元是_____;B的上確界是_____;B的下確界是_____。 (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ú)向連通圖是樹(shù)當(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是集合X上的等價(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)添加沒(méi)有出現(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è) 證明 因?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= 證明 設(shè)G*= 離散數(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?R,則對(duì)任意的x、y、z∈A,如果xRz且zRy,則 六、(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使 對(duì)任意的x∈A,若存在y1、y2∈C,使得 綜上可知,fog是A到C的函數(shù)。 (2)對(duì)任意的x∈A,由g:A→B是函數(shù),有 八、(15分)設(shè) 證明 對(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、在一棵樹(shù)中有7片樹(shù)葉,3個(gè)3度結(jié)點(diǎn),其余都是4度結(jié)點(diǎn)則該樹(shù)有()個(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都是群 3、G= 四、邏輯推演 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> }; 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)樹(shù)。算法略。結(jié)果如圖: 樹(shù)權(quán)C(T)=23+1+4+9+3+17=57即為總造價(jià)。第三篇:離散數(shù)學(xué)試題與答案
第四篇:離散數(shù)學(xué)試題
第五篇:全國(guó)2008年4月自考離散數(shù)學(xué)試題
是一個(gè)半群,如果S是有限集,則必存在a∈S,使得a*a=a。