離散數(shù)學例題整理.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) (補交轉換律) = (A C) (B C) (德摩根律) = (A C) (B C) (雙重否定律) = (A C B) (A C C) (分配律) = (A C B) (A ) (矛盾律) = A C B (零律,同一律) = (A B) C (交換律,結合律) = (A B) C (補交轉換律)例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 設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ù).假設n是奇數(shù), 則存在kN, n=2k+1. 于是 n2 = (2k+1)2 = 2(2k2+2k)+1得證n2是奇數(shù).間接法 若n2是奇數(shù), 則n也是奇數(shù).只證:若n是偶數(shù), 則n2也是偶數(shù).假設n是偶數(shù), 則存在kN, n=2k. 于是 n2 = (2k)2= 2(2k2)得證n2是偶數(shù).歸謬法 若A-B=A, 則AB=證 用歸謬法, 假設AB, 則存在x,使得 xAB xA且xB xA-B且xB (A-B=A) (xA且xB)且xB xB且xB, 矛盾構造性 對每正整數(shù)n, 存n個連的正合數(shù).證 令x=(n+1)! +1考慮如下n個連續(xù)正整數(shù)：x+1, x+2, x+n ，對于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個連續(xù)的正合數(shù)。非構造性對每個正整數(shù)n, 存在大于n的素數(shù).令x等于所有小于等于n的素數(shù)的乘積加1, 則 x不能被所有小于等于n的素數(shù)整除. 于是, x或者是素數(shù), 或者能被大于n的素數(shù)整除.因此,存在大于n的素數(shù).數(shù)學歸：對所有n1, 1+3+5+ +(2n-1)=n2 歸納基礎. 當n=1時, 1=12, 結論成立.歸納步驟. 假設對n(n1)結論成立, 則考慮n+1的情況有1+3+5+ +(2n-1)+(2n+1)=n2 +(2n+1) = (n+1)2得證當n+1時結論也成立.第二數(shù)學歸 任=2的整數(shù)均可表成素數(shù)的乘積證 歸納基礎. 對于2, 結論顯然成立.歸納步驟. 假設對所有的k(2kn)結論成立, 要證結論對n+1也成立. 若n+1是素數(shù), 則結論成立; 否則n+1=ab,2a,b3，則3y, G(x,y): xy,符號化為 F(2,3)G(3,4)真值為1例3 在一階邏輯中將下面命題符號化: (1)人都愛美; (2) 有人用左手寫字個體域分別取(a) 人類集合, (b) 全總個體域 .解: (a) (1) 設F(x): x愛美, 符號化為 x F(x)(2) 設G(x): x用左手寫字, 符號化為 $x G(x)(b) 設M(x): x為人， F(x), G(x)同(a)中(1) x (M(x)F(x)(2) $ x (M(x)G(x)例4 將下列命題符號化, 并討論其真值:(1) 對任意的x, 均有x2-3x+2=(x-1)(x-2)(2) 存在x, 使得x+5=3分別取(a) 個體域D1=N, (b) 個體域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 將下面命題符號化:(1) 兔子比烏龜跑得快(2) 有的兔子比所有的烏龜跑得快(3) 并不是所有的兔子都比烏龜跑得快(4) 不存在跑得一樣快的兔子和烏龜解 用全總個體域，令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)， 指導變元為x $y的轄域:G(x,y,z)， 指導變元為y 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)， 指導變元為x$x的轄域:G(x)， 指導變元為xx的兩次出現(xiàn)均為約束出現(xiàn). 但是, 第一次出現(xiàn)的x是x中的x, 第二次出現(xiàn)的x是$x中的x. 例1 消去公式中既約束出現(xiàn)、又自由出現(xiàn)的個體變項(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 設個體域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) 量詞轄域擴張 xy(F(x)G(y) 量詞轄域擴張第四章笛卡兒積A=0, 1, B=a, b, cAB=, BA =, (1) R= | x,yN, x+y3 =, , , , , (2) C= | x,yR, x2+y2=1，其中R代表實數(shù)集合， C是直角坐標平面上點的橫、縱坐標之間的關系， C中的所有的點恰好構成坐標平面上的單位圓. (3) R= | x,y,zR, x+2y+z=3， R代表了空間直角坐標系中的一個平面. 例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個3度頂點, 其余頂點的度數(shù)均小于等于2, 問G至少有多少個頂點? 解 設G有n個頂點. 由握手定理, 43+2(n-4)210解得 n8證明不存在具有奇數(shù)個面且每個面都具有奇數(shù)條棱的多面體.證 用反證法. 假設存在這樣的多面體, 作無向圖G=,其中 V=v | v為多面體的面, E=(u,v) | u,vV u與v有公共的棱 uv.根據(jù)假設, |V|為奇數(shù)且vV, d(v)為奇數(shù). 這與握手定理的推論矛盾.設9階無向圖的每個頂點的度數(shù)為5或6, 證明它至少有5個6度頂點或者至少有6個5度頂點.證 討論所有可能的情況. 設有a個5度頂點和b個6度頂點(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個6度頂點, (4)和(5) 至少6個5度頂點子圖(1),(2),(3)是(1)的子圖, (2),(3)是真子圖, (1)是母圖.(1),(3)是(1)的生成子圖.(2)是d,e,f 的導出子圖, 也是e5, e6, e7導出子圖.(3)是e1, e3, e5, e7的導出子圖畫出4階3條邊的所有非同構的無向簡單圖解 總度數(shù)為6, 分配給4個頂點, 最大度為3, 且奇度頂點數(shù)為偶數(shù), 有下述3個度數(shù)列: (1) 1,1,1,3;(2)1,1,2,2;(3)0,2,2,2.畫出3個以1,1,1,2,2,3為度數(shù)列的非同構的無向簡單圖(1) v1到v4,v4到v1長為3的通路各有多少條?(2) v1到自身長為1,2,3,4的回路各有多少條?(3) 長為4的通路共有多少條?其中有多少條回路?(4) 長度小于等于4的回路共有多少條?(5) 寫出D的可達矩陣, 并問D是強連通的嗎?解v1到v4長為3的通路有3條,v4到v1長為3的通路有0條v1到自身長為1,2,3,4的回路各有1條長為4的通路共有16條, 其中有3條回路長度小于等于4的回路共有 8條例1 已知無向樹T中, 有1個3度頂點, 2個2度頂點, 其余頂點全是樹葉. 試求樹葉數(shù), 并畫出滿足要求的非同構的無向樹. 解 設有x片樹葉,2(2+x)=13+22+x解得x=3，故T有3片樹葉.T的度數(shù)列為1, 1, 1, 2, 2, 3例2 畫出所有6階非同構的無向樹解 5條邊, 總度數(shù)等于10（同構性質(zhì)：頂點數(shù)相等，邊數(shù)相等，通過調(diào)整頂點順序度數(shù)列相等）