離散數(shù)學(xué)練習(xí)部分解答

1、離散數(shù)學(xué)練習(xí)（部分）解答離散數(shù)學(xué)練習(xí)解答福建農(nóng)林大學(xué)東方學(xué)院2009 2010學(xué)年第二學(xué)期第一篇數(shù)理邏輯二、解答題：1、將下列命題符號化：(1 )明天不下雨又有空的話，我就會去 打球。(2)只要她生病了，我都會去看她(只有她生病了，我才會去看她)。(3)每個旅客或坐頭等艙或坐二等艙。(4)有些汽車比任何火車都慢，但并非 所有的汽車都比火車慢。解(1)設(shè)P：明天不下南；Q：明天我有空；R：明天我去打球。則該命題可符號化為P Q R o(2)設(shè)P :她生?。籕：我去看她。則該命 題可符號化為 P Q (Q P)。(3)設(shè) M:LL 是旅客；F:LL 坐 LL； G:LL 是頭等艙位；H：LL是二等

2、艙位。則該命題可符號化為x(M(x) ( y(G(y) F(x,y) y(H(y) F(x,y)。(4)設(shè)M:LL是汽車；W:LL是火車；F:LL比L L慢。則該命題可符號化為x(M(x) ( y(W(y) F(x,y)( x(M(x) ( y(W(y) F(x, y)2、求公式G (P (Q R) Q的主合取范式和主 析取范式，并求使G取值為真的所有指派。解：G的主析取范式：G (P (Q R) Q(P (Q R) Q ( P Q) (Q Q) (R Q)(PQ) (R Q) P Q (R R) (R Q) (P P)( PQ R) ( P QR) (R Q P) (RQ P)(P Q R)

3、 ( P Q R) ( P Q R)Q G (P Q R) (P Q R) (PQ R) ( P Q R) ( P QR)練習(xí)解答第1頁(共9頁)所以G ( G)的主合取范式為G ( P Q R) ( P Q R) ( P Q R) (P Q R) (P Q R)使G取值為真的所有指派為：(1,0,1).(0,0,1),(0,0,0)注意：若沒有要求用等值演算，也可采用真值表求。三、邏輯推理題1、用演繹法證明：P-( CHR), S P,Q,R卜S.(應(yīng)注明每一步推理所采用的推理規(guī)則)。證明：(1) ( S)(假設(shè)，否定結(jié)論引入)(2) s(1)置換，T規(guī)則)(前提，P規(guī)則)則)p析取三段論，

4、p析取三段論，T規(guī)則)P ( Q R)Q R言推理，T規(guī)則) Q規(guī)則)R假言推理，T規(guī)則)R規(guī)則)R R 取，T規(guī)則)(，(3)(前提，P規(guī)則)(4), (5)假(前提，P(，(6)(前提，P(8), (9)合所以所以P ( Q R), S P, Q, R S2P ( Q R), S P, Q, R S2、找出下列推導(dǎo)過程中的錯誤，并問結(jié)論 是否有效？如果是，寫出正確的推導(dǎo)過 程。(1) x(P(x) Q(x) P(y) Q(y)(3) xP(x)(4 ) P(y)規(guī)則P (前提引入)(1)規(guī)則P (前提引入)(3) Q(y) Q(y)(6) xQ(x)(2),(4)假言推理(5)練習(xí)解答第2

5、頁(共9頁)解該推導(dǎo)過程中由(3)推出結(jié)論(4)是 錯誤的。這是因為第(2)步中已有變元y出現(xiàn)， 囚此由第(3)步中應(yīng)用規(guī)則時，不能再引入變 元y。 3 分結(jié)論xQ(x)結(jié)論xQ(x)是有效的(1 ) xP(x) P(y)(3 ) x(P(x) Q(x)(4 ) P(y) Q(y),其正確推導(dǎo)過程為: 規(guī)則P(1)規(guī)則P(3)Q(y)(2),(4) 假言推理xQ(x)(5)3、有紅、黃、綠、白四隊參加足球聯(lián)賽，如 果紅隊第三，則當(dāng)黃隊不是第二時，綠隊第四。 或者白隊不是第一，或者紅隊第三。已知綠隊不 是第四。試證明：如果白隊第一，那么黃隊第二。(要求：設(shè)p:白隊第一；Q：黃隊第二；R： 紅隊第

6、三；S：綠隊第四。并寫出前提和結(jié)論的 符號化及推理過程。)解 前提：R ( Q S), p r, S結(jié)論：p Q TOC o 1-5 h z 證明：(1) P附加前提引入P R前提引入3)R(1), (2)析取三段論R ( Q S)前提引入 TOC o 1-5 h z q s(3)(4)假言推理s前提引入(7)Q(6), (5)拒取第二篇集合論二、答題1、設(shè)集合A 1,2, ,12, R為A上的整除關(guān)系)試 (1)畫出偏序集(a,r)的HassefS; 一(2)，出a市的最大元、最小元、極大元、極小啟、，一一 一，一 一一一，(3)與出A的子集B 1,3, 6,9的上界、下界及上、 下確界。練

7、習(xí)解答第3頁(共9頁)解：(1)(a,r)的Hasse圖如下:1A中沒有最大元；最小元是1；極小元 也是1;極大元有7, 8, 9, 10, 11, 12。B 1,3, 6, 9沒有上界 也就沒有上確界； 下鼻是1 ；下確界也是1。2、(自然映射問題)習(xí)題八(P162)第16題。 (屈婉玲離散數(shù)學(xué)，下同)設(shè)A a,b,c, R為A上的等價關(guān)系,且R a,b , b,a UIa求自然映射g： A AIR。解：因為 A/R a,b,c,所以g： A A/R, g(a) g(b) a,b, g(c) c3、(計數(shù)問題)習(xí)題六(P99)第21上23題。 (1)埔旺有25個學(xué)生，其中14人會打籃球，12

8、人會打排琰乙.64會打篇球和我琰“一. 睛T6嗯!丁跳贏得儲溫Bfc種呈不 會上丁球的人數(shù)。一解:尊2為該理W生第a小AB. C9到 表示會打籃球、排球和網(wǎng)球的學(xué)生集合，則據(jù)題|S 25)|A 14)|B 12)|C| 6)AB 6)| AC 5)ABC 2因為會打網(wǎng)球的人都會打藍(lán)球或排球，因此有C ACUBC于是由包含排斥原理知、C AC BC ABC或BC C ABC AC從而不會打球的人數(shù)為ABC| |S (A B |C) (AB AC BC) | ABC一一，SAJB) ,ab 5,一 一(2)使用包含排斥原理求不超過 120的素 數(shù)個數(shù)。解：因為112=121,故不超過120的合數(shù)至

9、少 含有2、3、5或7這些素因數(shù)之一。為此，設(shè)S xx Z,1 x 120A1 xx S,2xA2 xx S,3 xA x x S,5 xA x x S,7|x練習(xí)解答第4頁(共9頁)現(xiàn)在鬼要求出不能被這4個素數(shù)整除的數(shù)的個數(shù)。 TOC o 1-5 h z 由于，且A 60A2 40 A 24A4 17Ai A?胃20 Al A 畀10120120A1 1 A4 -Z_ 8A21Asi 82 73 5A A4 / 5A3 1A4 * 33 75 7AlAJAs 4 Al A2 1A 2 |AI A3I A4 1AJ A3I A 1A1I A2I A3I A4 0因此，不能被2、3、5及7整除的

10、整數(shù)有A I A2 I A, I A4120 (60 40 24 17) (20 12 8 8 5 3) (4 2 1 1) 0120 141 56 8 27又因為2、3、5及7不滿足上述條件，被 篩 掉工但它們是素數(shù)，而數(shù)1則相反。故不超過120的素數(shù)有27 4 1 30個*4、(特征函數(shù)問題)習(xí)題八(P162)第14 題。設(shè)S為集合，A, B是S的子集，t表示 T的特征函數(shù)。若a ( a,1 , b,1 , c,0 , d,0 b a,0 , b,1 , c,0 , d,1 )求 AIB。*5、設(shè) A 0,1)S Aa,則 a a ) cardA 20A上可定義2n 16 (n cardA

11、 2)個二兀關(guān) 系。其中4 個自反關(guān)系, 4個反自反關(guān)系，8個對稱關(guān)系.12個反對稱關(guān)系,2個等價關(guān) 系, 3個偏序關(guān)系。練習(xí)解答第5頁(共9頁)注意：A上的二元關(guān)系是A A的一個子集， 若n cardA 2,則A A的子集有2n個。空關(guān)系即空集 既是反自反的，也是對稱的，還是反對稱的。應(yīng)掌握本例中每一類關(guān)系具 體的有哪些。AS中有2n 4個函數(shù)，其中一2_個是雙射。 *6、(哈斯圖問題)(P127例7.19)設(shè)集合A a,b,c , _R為募集P(A)上的包含關(guān)系)試求： (1)畫出偏序集 P(A),R w Hasse圖；一 (2)3出P(A)中的最大元、最小元、極大元、 極小元；(3)寫出

12、P(A)的子集B a, b)的上界、下界及 上、下確界。*7、(哈斯圖問題)(P127例7.20)已知偏序集A,R的哈斯 圖如下，求關(guān)系 R 的集合表示三、證明題1、設(shè)R是非空集合A上的等價關(guān)系，試證R的 逆關(guān)系R1也是A上的等價關(guān)系。證明1) R1具有自反性：x A,因為R是A上 的等價關(guān)系，具有自反性，有(x,x) R)從而(x,x) R1,即R1具有自反性。R1具有對稱性：x,y A,若(x,y) R1,則(y, x) R o因為R具有對稱”因此(x,y) R,從而(y,x) R1,即R1具有對稱性。R1具有傳遞性：x,y,z A,若(x, y),(y,z) R 1 ,貝U (z,y),

13、(y,x) Ro因為R具有傳遞性，因此(z,x) R,從而(x,z) R1,即 R1具有傳遞性。所以R1是A上的等價關(guān)系2、設(shè)R是非空集合A上的偏序關(guān)系，試證R的 逆關(guān)系R1也是A上的偏序關(guān)系。練習(xí)解答第6頁(共9頁)證明1) R1具有自反性：x A,因為R是A上的 等價關(guān)系，具有自反性，有(x,x) R,從而(x,x) R1,即R1具有自反性。) R1具有反對稱性：x,y A ,若 (x. y),( y,x) R1,貝(y,x),(x, y) R。因為R具有反對稱性，因此x y,即R1也具有反對 稱性。) R1具有傳遞性：x,y,z A,若(x, y),(y,z) R 1 ,則(z,y),(

14、y,x) R o因為R具有傳遞性，因此(z,x) R,從而(x,z) R1,即R1具有傳遞性。所以R1是A上的偏序關(guān)系。3、設(shè)(0, 1)和0, 1為實數(shù)區(qū)間，證明：(0,1) 0,1 提示：參考課本第148頁例8.9 (5)的解答。第四篇圖論三、應(yīng)用及證明題：1、(哈米爾頓回路問題)習(xí)題十五(P306)第15題某工廠生產(chǎn)由6種顏色的紗織成的雙色布。已知在一批雙色布中，每種顏色至少與其他3種顏色相搭配。證明可以從這批雙色布中挑出3種，它們由不同顏色的紗織成。解：構(gòu)造無向簡單圖G V,E ,使V Vi,V2,L ,V6）其中Vi（i 12L表示6種顏色之一）而E v，Vj v，Vj V,i j

15、,且v與vj在布中有搭配由已知條件可知，Vi,Vj V（i j）, 有 d（vi） d（Vj） 3 3 6 V于是根據(jù)無向簡單圖有哈密頓回路的判定定理，G為哈密頓圖。設(shè)C Vi,vJ vm為G中的一條哈密頓 回路，任何兩個頂點若在C中相鄰，則在這批布 中有這兩個頂點代表的顏色搭配成的雙色布。于 是，在這批布中有Vi1與Vi2, 也與環(huán).以及也與”搭配成 的3種雙色布，它們使用了全部6種顏色。練習(xí)解答第7頁（共9頁）*2、（最短路問題）習(xí)題十五（P307）第22 題。某工廠使用一臺設(shè)備，每年年初要決定是繼 續(xù)使用，還是購買新的。預(yù)計該設(shè)備第一年的價 格為11萬元，以后每年漲1萬元。使用的第1 年

16、，第2年，第5年的維修費分別為5, 6,8, 11, 18萬元。使用1年后的殘值為4萬元） 以后每使用1年殘值減少1萬元。試制定購買維 修該設(shè)備的5年計劃，使總支出最小。解：第i年初購買使用到第j年初（或第j 1年 末）所需的總費用（購買費+維修費殘值）如下根據(jù)上表構(gòu)造有向帶權(quán)圖 G,其中頂點,表 示第i年初（或第i 1年末），1到Vj（i j）的邊表示在 第i年初購買設(shè)備使用到第j 1年末，其權(quán)為所需 的總費用。練習(xí)解答第8頁（共9頁）應(yīng)用Dijkstra標(biāo)號法計算結(jié)果如下表:Vi(Vi, 0) *(Vi, oo)(Vi, 12) *(Vi, oo)(Vi, 19)(Vi, 19)V2V2V3V4(Vi, oo) (Vi, 28)(Vi, 28)*(Vi, oo) (Vi, 40)(Vi, 40)(Vi, 40) *(Vi, oo) (Vi, 59)(V2, 53)(V3, 49)(V3, 49) *6從頂點1到6的最短路徑Vi V3 V