離散數(shù)學(xué)例題整理.doc

第一章定律證明:(1) AB=BA (交換律)證 x xAB xA 或 xB, 自然有 xB 或 xA xBA得證 ABBA.同理可證 BAAB.(2) A(BC)=(AB)(AC) (分配律)證 x xA(BC) xA或(xB且 xC ) (xA或xB)且(xA或xC) x(AB)(AC) 得證 A(BC)(AB)(AC).類似可證 (AB)(AC)A(BC).(3) AE=E (零律)證 根據(jù)并的定義, 有EAE.根據(jù)全集的定義, 又有A EE.(4) AE=A (同一律)證 根據(jù)交的定義, 有AEA.又, x xA,根據(jù)全集E的定義, xE, 從而 xA且xE, xAE得證 AAE. 例4 證明 A(AB)=A （吸收律）證 利用例3證明的4條等式證明 A(AB) = (AE)(AB) (同一律) = A(EB) (分配律) = A(BE) (交換律) = AE (零律) = A (同一律)例5 證明 (A-B)-C=(A-C)-(B-C)證 (A-C)-(B-C) = (A C) (B C) (補(bǔ)交轉(zhuǎn)換律) = (A C) (B C) (德摩根律) = (A C) (B C) (雙重否定律) = (A C B) (A C C) (分配律) = (A C B) (A ) (矛盾律) = A C B (零律,同一律) = (A B) C (交換律,結(jié)合律) = (A B) C (補(bǔ)交轉(zhuǎn)換律)例6 證明 (AB)(AC)= (BC) - A證 (AB)(AC) =(AB) - (AC)(AC) - (AB) =(AB)AC)(AC)AB) = (BAC)(CAB) =(BC)(CB)A =(B-C)(C-B)A = (BC) - A例7 設(shè)A,B為任意集合, 證明: 若AB, 則P(A)P(B)證 x xP(A) xA xB (已知AB) xP(B)例8 證明 AB=AB-AB.AB=(AB)(AB) =(AA)(AB)(BA)(BB) =(AB)(BA) =(AB)(AB) =AB-AB 直接法 若n是奇數(shù), 則n2也是奇數(shù).假設(shè)n是奇數(shù), 則存在kN, n=2k+1. 于是 n2 = (2k+1)2 = 2(2k2+2k)+1得證n2是奇數(shù).間接法 若n2是奇數(shù), 則n也是奇數(shù).只證:若n是偶數(shù), 則n2也是偶數(shù).假設(shè)n是偶數(shù), 則存在kN, n=2k. 于是 n2 = (2k)2= 2(2k2)得證n2是偶數(shù).歸謬法 若A-B=A, 則AB=證 用歸謬法, 假設(shè)AB, 則存在x,使得 xAB xA且xB xA-B且xB (A-B=A) (xA且xB)且xB xB且xB, 矛盾構(gòu)造性 對(duì)每正整數(shù)n, 存n個(gè)連的正合數(shù).證 令x=(n+1)! +1考慮如下n個(gè)連續(xù)正整數(shù)：x+1, x+2, x+n ，對(duì)于i（i=1,2,3,n），x+i=(n+1)! +(1+i), 此式含有因子1+i，而1+i不等于1也不等于x+i，因此x+i是合數(shù)。所以x+1, x+2, x+n 是n個(gè)連續(xù)的正合數(shù)。非構(gòu)造性對(duì)每個(gè)正整數(shù)n, 存在大于n的素?cái)?shù).令x等于所有小于等于n的素?cái)?shù)的乘積加1, 則 x不能被所有小于等于n的素?cái)?shù)整除. 于是, x或者是素?cái)?shù), 或者能被大于n的素?cái)?shù)整除.因此,存在大于n的素?cái)?shù).數(shù)學(xué)歸：對(duì)所有n1, 1+3+5+ +(2n-1)=n2 歸納基礎(chǔ). 當(dāng)n=1時(shí), 1=12, 結(jié)論成立.歸納步驟. 假設(shè)對(duì)n(n1)結(jié)論成立, 則考慮n+1的情況有1+3+5+ +(2n-1)+(2n+1)=n2 +(2n+1) = (n+1)2得證當(dāng)n+1時(shí)結(jié)論也成立.第二數(shù)學(xué)歸 任=2的整數(shù)均可表成素?cái)?shù)的乘積證 歸納基礎(chǔ). 對(duì)于2, 結(jié)論顯然成立.歸納步驟. 假設(shè)對(duì)所有的k(2kn)結(jié)論成立, 要證結(jié)論對(duì)n+1也成立. 若n+1是素?cái)?shù), 則結(jié)論成立; 否則n+1=ab,2a,b3，則3y, G(x,y): xy,符號(hào)化為 F(2,3)G(3,4)真值為1例3 在一階邏輯中將下面命題符號(hào)化: (1)人都愛(ài)美; (2) 有人用左手寫(xiě)字個(gè)體域分別取(a) 人類集合, (b) 全總個(gè)體域 .解: (a) (1) 設(shè)F(x): x愛(ài)美, 符號(hào)化為 x F(x)(2) 設(shè)G(x): x用左手寫(xiě)字, 符號(hào)化為 $x G(x)(b) 設(shè)M(x): x為人， F(x), G(x)同(a)中(1) x (M(x)F(x)(2) $ x (M(x)G(x)例4 將下列命題符號(hào)化, 并討論其真值:(1) 對(duì)任意的x, 均有x2-3x+2=(x-1)(x-2)(2) 存在x, 使得x+5=3分別取(a) 個(gè)體域D1=N, (b) 個(gè)體域D2=R解 記F(x): x2-3x+2=(x-1)(x-2), G(x): x+5=3(a) (1) x F(x) 真值為1 (2) $x G(x) 真值為0(b) (1) x F(x) 真值為1 (2) $x G(x) 真值為1例5 將下面命題符號(hào)化:(1) 兔子比烏龜跑得快(2) 有的兔子比所有的烏龜跑得快(3) 并不是所有的兔子都比烏龜跑得快(4) 不存在跑得一樣快的兔子和烏龜解 用全總個(gè)體域，令F(x): x是兔子, G(y): y是烏龜, H(x,y): x比y跑得快, L(x,y): x和y跑得一樣快(1) xy(F(x)G(y)H(x,y) (2) $x(F(x)(y (G(y)H(x,y)(3) xy(F(x)G(y)H(x,y) (4) $x$y(F(x)G(y)L(x,y)例6 公式 x(F(x,y)$yG(x,y,z) x的轄域:(F(x,y)$yG(x,y,z)， 指導(dǎo)變?cè)獮閤 $y的轄域:G(x,y,z)， 指導(dǎo)變?cè)獮閥 x的兩次出現(xiàn)均為約束出現(xiàn) y的第一次出現(xiàn)為自由出現(xiàn), 第二次出現(xiàn)為約束出現(xiàn)z為自由出現(xiàn). 例7 公式 x(F(x)$xG(x)x的轄域:(F(x)$xG(x)， 指導(dǎo)變?cè)獮閤$x的轄域:G(x)， 指導(dǎo)變?cè)獮閤x的兩次出現(xiàn)均為約束出現(xiàn). 但是, 第一次出現(xiàn)的x是x中的x, 第二次出現(xiàn)的x是$x中的x. 例1 消去公式中既約束出現(xiàn)、又自由出現(xiàn)的個(gè)體變項(xiàng)(1) xF(x,y,z) $yG(x,y,z) uF(u,y,z) $yG(x,y,z) 換名規(guī)則 uF(u,y,z) $vG(x,v,z) 換名規(guī)則(2) x(F(x,y) $yG(x,y,z) x(F(x,y) $tG(x,t,z) 換名規(guī)則例2 設(shè)個(gè)體域D=a,b,c, 消去下面公式中的量詞:(1) x(F(x)G(x) (F(a)G(a)(F(b)G(b)(F(c)G(c)(2) x(F(x)$yG(y) xF(x)$yG(y) 量詞轄域收縮(F(a)F(b)F(c)(G(a)G(b)G(c)(3) $xyF(x,y) $x(F(x,a)F(x,b)F(x,c) (F(a,a)F(a,b)F(a,c)(F(b,a)F(b,b)F(b,c) (F(c,a)F(c,b)F(c,c)例4 證明下列等值式: $x(M(x)F(x) x(M(x) F(x)證 左邊 x (M(x)F(x) 量詞否定等值式 x(M(x)F(x) x(M(x) F(x)例5 求公式的前束范式(1) xF(x)$xG(x)解1 xF(x)xG(x) 量詞否定等值式 x(F(x)G(x) 量詞分配等值式解2 xF(x)$yG(y) 換名規(guī)則 xF(x)yG(y) 量詞否定等值式 x(F(x)yG(y) 量詞轄域擴(kuò)張 xy(F(x)G(y) 量詞轄域擴(kuò)張第四章笛卡兒積A=0, 1, B=a, b, cAB=, BA =, (1) R= | x,yN, x+y3 =, , , , , (2) C= | x,yR, x2+y2=1，其中R代表實(shí)數(shù)集合， C是直角坐標(biāo)平面上點(diǎn)的橫、縱坐標(biāo)之間的關(guān)系， C中的所有的點(diǎn)恰好構(gòu)成坐標(biāo)平面上的單位圓. (3) R= | x,y,zR, x+2y+z=3， R代表了空間直角坐標(biāo)系中的一個(gè)平面. 例1 R=, 則domR = a, c, a, d ranR =b, d, dfldR = a, c, a, d, b, d 例2 R=, , , S=, , , , R-1=, RS = , , SR =, , , 第六章已知圖G有10條邊, 4個(gè)3度頂點(diǎn), 其余頂點(diǎn)的度數(shù)均小于等于2, 問(wèn)G至少有多少個(gè)頂點(diǎn)? 解 設(shè)G有n個(gè)頂點(diǎn). 由握手定理, 43+2(n-4)210解得 n8證明不存在具有奇數(shù)個(gè)面且每個(gè)面都具有奇數(shù)條棱的多面體.證 用反證法. 假設(shè)存在這樣的多面體, 作無(wú)向圖G=,其中 V=v | v為多面體的面, E=(u,v) | u,vV u與v有公共的棱 uv.根據(jù)假設(shè), |V|為奇數(shù)且vV, d(v)為奇數(shù). 這與握手定理的推論矛盾.設(shè)9階無(wú)向圖的每個(gè)頂點(diǎn)的度數(shù)為5或6, 證明它至少有5個(gè)6度頂點(diǎn)或者至少有6個(gè)5度頂點(diǎn).證 討論所有可能的情況. 設(shè)有a個(gè)5度頂點(diǎn)和b個(gè)6度頂點(diǎn)(1)a=0, b=9;(2)a=2, b=7;(3)a=4, b=5;(4)a=6, b=3;(5)a=8, b=1(1)(3) 至少5個(gè)6度頂點(diǎn), (4)和(5) 至少6個(gè)5度頂點(diǎn)子圖(1),(2),(3)是(1)的子圖, (2),(3)是真子圖, (1)是母圖.(1),(3)是(1)的生成子圖.(2)是d,e,f 的導(dǎo)出子圖, 也是e5, e6, e7導(dǎo)出子圖.(3)是e1, e3, e5, e7的導(dǎo)出子圖畫(huà)出4階3條邊的所有非同構(gòu)的無(wú)向簡(jiǎn)單圖解 總度數(shù)為6, 分配給4個(gè)頂點(diǎn), 最大度為3, 且奇度頂點(diǎn)數(shù)為偶數(shù), 有下述3個(gè)度數(shù)列: (1) 1,1,1,3;(2)1,1,2,2;(3)0,2,2,2.畫(huà)出3個(gè)以1,1,1,2,2,3為度數(shù)列的非同構(gòu)的無(wú)向簡(jiǎn)單圖(1) v1到v4,v4到v1長(zhǎng)為3的通路各有多少條?(2) v1到自身長(zhǎng)為1,2,3,4的回路各有多少條?(3) 長(zhǎng)為4的通路共有多少條?其中有多少條回路?(4) 長(zhǎng)度小于等于4的回路共有多少條?(5) 寫(xiě)出D的可達(dá)矩陣, 并問(wèn)D是強(qiáng)連通的嗎?解v1到v4長(zhǎng)為3的通路有3條,v4到v1長(zhǎng)為3的通路有0條v1到自身長(zhǎng)為1,2,3,4的回路各有1條長(zhǎng)為4的通路共有16條, 其中有3條回路長(zhǎng)度小于等于4的回路共有 8條例1 已知無(wú)向樹(shù)T中, 有1個(gè)3度頂點(diǎn), 2個(gè)2度頂點(diǎn), 其余頂點(diǎn)全是樹(shù)葉. 試求樹(shù)葉數(shù), 并畫(huà)出滿足要求的非同構(gòu)的無(wú)向樹(shù). 解 設(shè)有x片樹(shù)葉,2(2+x)=13+22+x解得x=3，故T有3片樹(shù)葉.T的度數(shù)列為1, 1, 1, 2, 2, 3例2 畫(huà)出所有6階非同構(gòu)的無(wú)向樹(shù)解 5條邊, 總度數(shù)等于10（同構(gòu)性質(zhì)：頂點(diǎn)數(shù)相等，邊數(shù)相等，通過(guò)調(diào)整頂點(diǎn)順序度數(shù)列相等）