離散數(shù)學例題整理

1、第一章定律證明:(1) AÈB=BÈA (交換律)證 "x xÎAÈB Þ xÎA 或 xÎB, 自然有 xÎB 或 xÎAÞ xÎBÈA得證 AÈBÍBÈA.同理可證 BÈAÍAÈB.(2) AÈ(BÇC)=(AÈB)Ç(AÈC) (分配律)證 "x xÎAÈ(BÇC) Þ xÎA或(xÎ

2、;B且 xÎC ) Þ(xÎA或xÎB)且(xÎA或xÎC) ÞxÎ(AÈB)Ç(AÈC) 得證 AÈ(BÇC)Í(AÈB)Ç(AÈC).類似可證 (AÈB)Ç(AÈC)ÍAÈ(BÇC).(3) AÈE=E (零律)證 根據(jù)并的定義, 有EÍAÈE.根據(jù)全集的定義, 又有AÈ EÍE.(4) AÇE=A (同

3、一律)證 根據(jù)交的定義, 有AÇEÍA.又, "x xÎA,根據(jù)全集E的定義, xÎE, 從而 xÎA且xÎE, Þ xÎAÇE得證 AÍAÇE. 例4 證明 AÈ(AÇB)=A （吸收律）證 利用例3證明的4條等式證明 AÈ(AÇB) = (AÇE)È(AÇB) (同一律) = AÇ(EÈB) (分配律) = AÇ(BÈE) (交換律) = AÇE (零律

4、) = A (同一律)例5 證明 (A-B)-C=(A-C)-(B-C)證 (A-C)-(B-C) = (A Ç C) Ç (B Ç C) (補交轉(zhuǎn)換律) = (A Ç C) Ç (B È C) (德摩根律) = (A Ç C) Ç (B È C) (雙重否定律) = (A Ç C Ç B) È(A Ç C Ç C) (分配律) = (A Ç C Ç B) È(A Ç Æ) (矛盾律) = A Ç

5、 C Ç B (零律,同一律) = (A Ç B) Ç C (交換律,結(jié)合律) = (A B) C (補交轉(zhuǎn)換律)例6 證明 (AÈB)Å(AÈC)= (BÅC) - A證 (AÈB)Å(AÈC) =(AÈB) - (AÈC)È(AÈC) - (AÈB) =(AÈB)ÇAÇC)È(AÈC)ÇAÇB) = (BÇAÇC)È(CÇAÇ

6、;B) =(BÇC)È(CÇB)ÇA =(B-C)È(C-B)ÇA = (BÅC) - A例7 設(shè)A,B為任意集合, 證明: 若AÍB, 則P(A)ÍP(B)證 "x xÎP(A) Û xÍA Þ xÍB (已知AÍB) Û xÎP(B)例8 證明 AÅB=AÈB-AÇB.AÅB=(AÇB)È(AÇB) =(AÈA)Ç(A

7、00;B)Ç(BÈA)Ç(BÈB) =(AÈB)Ç(BÈA) =(AÈB)Ç(AÇB) =AÈB-AÇB 直接法 若n是奇數(shù), 則n2也是奇數(shù).假設(shè)n是奇數(shù), 則存在kÎN, n=2k+1. 于是 n2 = (2k+1)2 = 2(2k2+2k)+1得證n2是奇數(shù).間接法 若n2是奇數(shù), 則n也是奇數(shù).只證:若n是偶數(shù), 則n2也是偶數(shù).假設(shè)n是偶數(shù), 則存在kÎN, n=2k. 于是 n2 = (2k)2= 2(2k2)得證n2是偶數(shù).歸謬法 若A-B=

8、A, 則AÇB=Æ證 用歸謬法, 假設(shè)AÇB¹Æ, 則存在x,使得 xÎAÇB Û xÎA且xÎB Þ xÎA-B且xÎB (A-B=A) Û (xÎA且xÏB)且xÎB Þ xÏB且xÎB, 矛盾構(gòu)造性 對每正整數(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), 此式含有因

9、子1+i，而1+i不等于1也不等于x+i，因此x+i是合數(shù)。所以x+1, x+2, x+n 是n個連續(xù)的正合數(shù)。非構(gòu)造性對每個正整數(shù)n, 存在大于n的素數(shù).令x等于所有小于等于n的素數(shù)的乘積加1, 則 x不能被所有小于等于n的素數(shù)整除. 于是, x或者是素數(shù), 或者能被大于n的素數(shù)整除.因此,存在大于n的素數(shù).數(shù)學歸：對所有n³1, 1+3+5+ +(2n-1)=n2 歸納基礎(chǔ). 當n=1時, 1=12, 結(jié)論成立.歸納步驟. 假設(shè)對n(n³1)結(jié)論成立, 則考慮n+1的情況有1+3+5+ +(2n-1)+(2n+1)=n2 +(2n+1) = (n+1)2得證當n+1時結(jié)

10、論也成立.第二數(shù)學歸 任>=2的整數(shù)均可表成素數(shù)的乘積證 歸納基礎(chǔ). 對于2, 結(jié)論顯然成立.歸納步驟. 假設(shè)對所有的k(2£k£n)結(jié)論成立, 要證結(jié)論對n+1也成立. 若n+1是素數(shù), 則結(jié)論成立; 否則n+1=ab,2£a,b<n. 由歸納假設(shè), a,b均可表成素數(shù)的乘積, 從而n+1也可表成素數(shù)的乘積. 得證結(jié)論對n+1成立.命題為假的證明舉反例例11 證明下述命題不成立: 若AÇB=AÇC, 則B=C. 證明 反例: 取A=a,b, B=a,b,c, C=a,b,d, 有 AÇB=AÇC = a,b但

11、B¹C, 故命題不成立.第二章例3 證明 p®(q®r) Û (pÙq)®r證 p®(q®r) Û ØpÚ(ØqÚr) （蘊涵等值式） Û (ØpÚØq)Úr （結(jié)合律） Û Ø(pÙq)Úr （德摩根律） Û (pÙq) ®r （蘊涵等值式） (1) qÙØ(p®q) 解 qÙØ(p®q

12、) Û qÙØ(ØpÚq) （蘊涵等值式） Û qÙ(pÙØq) （德摩根律） Û pÙ(qÙØq) （交換律，結(jié)合律） Û pÙ0 （矛盾律） Û 0 （零律）該式為矛盾式.(2) (p®q)«(Øq®Øp) 解 (p®q)«(Øq®Øp) Û (ØpÚq)«(qÚØp) （蘊

13、涵等值式） Û (ØpÚq)«(ØpÚq) （交換律） Û 1該式為重言式.Ø(p®q)ÚØr 的析取范式與合取范式解 Ø(p®q)ÚØr Û Ø(ØpÚq)ÚØr Û (pÙØq)ÚØr 析取范式 Û (pÚØr)Ù(ØqÚØr) 合取范式 Ø(p®

14、;q)ÚØr 的主析取范式主合取范式解 (1) Ø(p®q)ÚØr Û (pÙØq)ÚØr pÙØq Û (pÙØq)Ù1 同一律 Û (pÙØq)Ù(ØrÚr) 排中律 Û (pÙØqÙØr)Ú(pÙØqÙr) 分配律 Û m4Úm5 Ør 

15、19; (ØpÚp)Ù(ØqÚq)ÙØr 同一律, 排中律 Û (ØpÙØqÙØr)Ú(ØpÙqÙØr)Ú(pÙØqÙØr)Ú(pÙqÙØr) Û m0Ú m2Ú m4Ú m6 分配律得 Ø(p®q)ÚØr Û m0Ú m2

16、18; m4 Úm5 Ú m6可記作 Û S(0,2,4,5,6)(2) Ø(p®q)ÚØr Û (pÚØr)Ù(ØqÚØr) pÚØr Û pÚ0ÚØr 同一律 Û pÚ(qÙØq)ÚØr 矛盾律 Û (pÚqÚØr)Ù(pÚØqÚØr) 分配律

17、Û M1ÙM3 ØqÚØr Û (pÙØp)ÚØqÚØr 同一律, 矛盾律 Û (pÚØqÚØr)Ù(ØpÚØqÚØr) 分配律 Û M3ÙM7得 Ø(p®q)ÚØr Û M1ÙM3ÙM7可記作 Û P(1,3,7)快速求 A Û (ØpÙ

18、q)Ú(ØpÙØqÙr)Úr的主析取范式(1) ØpÙq Û (ØpÙqÙØr)Ú(ØpÙqÙr) Û m2Ú m3 ØpÙØqÙr Û m1 r Û(ØpÙØqÙr)Ú(ØpÙqÙr)Ú(pÙØqÙr)Ú(pÙ

19、;qÙr) Û m1Ú m3Ú m5Ú m7得 AÛ m1Ú m2Ú m3Ú m5Ú m7 Û S(1,2,3,5,7)(2) 求 BÛ ØpÙ(pÚqÚØr)的主合取范式解 Øp Û (ØpÚqÚr)Ù(ØpÚqÚØr)Ù(ØpÚØqÚr)Ù(ØpÚ

20、;ØqÚØr) Û M4ÙM5ÙM6ÙM7pÚqÚØr Û M1得BÛ M1ÙM4ÙM5ÙM6ÙM7 Û P(1,4,5,6,7)例3 用主析取范式判斷公式的類型:(1) AÛ Ø(p®q)Ùq (3) CÛ (pÚq)®r A Û Ø(Ø pÚq)Ùq Û ( pÙØq)

21、17;q Û 0 矛盾式(2) BÛ p®(pÚq) B Û Ø pÚ(pÚq) Û 1 Û m0Úm1Úm2Úm3 重言式 (3) CÛ (pÚq)®r C Û Ø(pÚq)Úr Û (ØpÙØq)Úr Û (ØpÙØqÙr)Ú(ØpÙØqÙ

22、16;r)Ú(ØpÙØqÙr) Ú(ØpÙqÙr)Ú(pÙØqÙr)Ú(pÙqÙr) Û m0Úm1Úm3Ú m5Úm7 非重言式的可滿足式用主析取范式判斷下面2組公式是否等值:(1) p與(ØpÚq)®(pÙq)解 p Û pÙ(ØqÚq) Û (pÙØq)Ú(p&#

23、217;q) Û m2Úm3 (ØpÚq)®(pÙq) Û Ø(ØpÚq)Ú(pÙq) Û (pÙØq)Ú(pÙq) Û m2Úm3故 p Û (ØpÚq)®(pÙq)(2) (pÙq)Úr 與 pÙ(qÚr)解 (pÙq)Úr Û (pÙqÙØr)Ú

24、;(pÙqÙr) Ú(ØpÙØqÙr)Ú (ØpÙqÙr)Ú(pÙØqÙr)Ú(pÙqÙr) Û m1Úm3Úm5Ú m6Úm7 pÙ(qÚr) Û (pÙq)Ú(pÙ r) Û(pÙqÙØr)Ú(pÙqÙr)Ú(pÙ&

25、#216;qÙr)Ú(pÙqÙr) Û m5Ú m6Úm7故 (pÙq)Úr 不等于 pÙ(qÚr)例5 某單位要從A,B,C三人中選派若干人出國考察, 需滿足下述條件:(1) 若A去, 則C必須去;(2) 若B去, 則C不能去;(3) A和B必須去一人且只能去一人.問有幾種可能的選派方案?解 記p:派A去, q:派B去, r:派C去(1) p®r, (2) q®Ør, (3) (pÙØq)Ú(ØpÙq)求

26、下式的成真賦值 A=(p®r)Ù(q®Ør)Ù(pÙØq)Ú(ØpÙq)求A的主析取范式 A=(p®r)Ù(q®Ør)Ù(pÙØq)Ú(ØpÙq) Û (ØpÚr)Ù(ØqÚØr)Ù(pÙØq)Ú(ØpÙq) Û (ØpÙØq)&

27、#218;(ØpÙØr)Ú(rÙØq)Ú(rÙØr) Ù(pÙØq)Ú(ØpÙq) Û (ØpÙØq)Ù(pÙØq)Ú(ØpÙØr)Ù(pÙØq) Ú(rÙØq)Ù(pÙØq)Ú(ØpÙØq)Ù(&#

28、216;pÙq) Ú(ØpÙØr)Ù(ØpÙq)Ú(rÙØq)Ù(ØpÙq) Û (pÙØqÙr)Ú(ØpÙqÙØr)成真賦值:101,010結(jié)論: 方案1 派A與C去 方案2派B去A=(ØpÙØqÙr)Ú(ØpÙqÙr)Ú(pÙqÙr)的主合取范式解 A &

29、#219; m1Úm3Úm7 Û M0ÙM2ÙM4ÙM5ÙM6第二章判斷若今天是1號, 則明天是5號.今天是1號. 所以, 明天是5號. 解 設(shè) p: 今天是1號, q: 明天是5號 推理的形式結(jié)構(gòu)為 (p®q)Ùp®q證明 用等值演算法 (p®q)Ùp®q Û Ø(ØpÚq)Ùp)Úq Û (pÙØq)ÚØp)Úq Û Øp&

30、#218;ØqÚq Û 1得證推理正確判斷若下午氣溫超過30度, 則小燕必去游泳，若她去游泳她就不去看電影了. 所以若小燕沒去看電影, 下午氣溫必定超過了30度. m1解 設(shè)p: 下午氣溫超過30度, q: 小燕去游泳，r: 小燕去看電影. 推理的形式結(jié)構(gòu)為 (p®q)Ù(q®Ø r) )®(Ø r®p)證明 主析取范式法(p®q)Ù(q®Ø r) )®(Ø r®p)ÛpÚ rÛm1Ú

31、m3Ú m4 Ú m5Ú m6 Ú m7主析取范式中缺少m0， m2，不是重言式，不正確。前提: pÚq, q®r, p®s, Øs結(jié)論: rÙ(pÚq)直接證明法證明 p®s 前提引入 Ø s 前提引入 Ø p 拒取式 pÚq 前提引入 q 析取三段論 q®r 前提引入 r 假言推理 rÙ(pÚq) 合取推理正確, rÙ(pÚq)是有效結(jié)論構(gòu)造推理的證明: 若明天是星期一或星期三, 我就有課. 若有課,

32、今天必需備課. 我今天下午沒備課. 所以, 明天不是星期一和星期三. 解 設(shè) p:明天是星期一, q:明天是星期三， r:我有課， s:我備課前提: (pÚq)®r, r®s, Øs結(jié)論: ØpÙØq 前提: (pÚq)®r, r®s, Øs結(jié)論: ØpÙØq 證明 r®s 前提引入 Øs 前提引入 Ør 拒取式 (pÚq)®r 前提引入 Ø(pÚq) 拒取式 ØpÙ

33、Øq 置換結(jié)論有效, 即明天不是星期一和星期三例4 前提: ØpÚq, ØqÚr, r®s結(jié)論: p®s證明 p 附加前提引入 ØpÚq 前提引入 q 析取三段論 ØqÚr 前提引入 r 析取三段論 r®s 前提引入 s 假言推理推理正確, p®s是有效結(jié)論例5 前提: Ø(pÙq)Úr, r®s, Øs, p結(jié)論: Øq證明 用歸繆法 q 結(jié)論否定引入 r®s 前提引入 Øs 前提引入

34、 Ør 拒取式 Ø(pÙq)Úr 前提引入 Ø(pÙq) 析取三段論 ØpÚØq 置換 Øp 析取三段論 p 前提引入 ØpÙp 合取推理正確, Øq是有效結(jié)論例6 前提: (p®q)®r, r®s, Øs結(jié)論: pÙØq歸結(jié)證明法解 (p®q)®r Û Ø(ØpÚq)Úr Û (pÙØq)Úr &

35、#219; (pÚr)Ù(ØqÚr) r®s Û ØrÚs Ø(pÙØq) Û ØpÚq把推理的前提改寫成前提: pÚr, ØqÚr, ØrÚs, Øs, ØpÚq(結(jié)論均為0, 不必寫出)前提: pÚr, ØqÚr, ØrÚs, Øs , ØpÚq證明 pÚr 前提引入 Øp&

36、#218;q 前提引入 qÚr 歸結(jié) ØqÚr 前提引入 r 歸結(jié) ØrÚs 前提引入 s 歸結(jié) Øs 前提引入 0 合取第三章將下述命題用0元謂詞符號化, 并討論它們的真值:(1) 根2是無理數(shù), 而根3是有理數(shù)(2) 如果2>3，則3<4解 (1) 設(shè)F(x): x是無理數(shù), G(x): x是有理數(shù)符號化為真值為0(2) 設(shè) F(x,y): x>y, G(x,y): x<y,符號化為 F(2,3)®G(3,4)真值為1例3 在一階邏輯中將下面命題符號化: (1) 人都愛美; (2) 有人

37、用左手寫字個體域分別取(a) 人類集合, (b) 全總個體域 .解: (a) (1) 設(shè)F(x): x愛美, 符號化為 "x F(x)(2) 設(shè)G(x): x用左手寫字, 符號化為 $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 將下列命題符號化, 并討論其真值:(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)

38、(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) "x"y(F(x)ÙG(y)®H(x,y) (2) $x(F

39、(x)Ù("y (G(y)®H(x,y)(3) Ø "x"y(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)

40、4;$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,

41、z)Û "x(F(x,y) ® $tG(x,t,z) 換名規(guī)則例2 設(shè)個體域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) $x&quo

42、t;yF(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(&#

43、216;M(x)ÚØF(x)Û "x(M(x)® ØF(x)例5 求公式的前束范式(1) "xF(x)ÙØ$xG(x)解1 Û "xF(x)Ù"xØG(x) 量詞否定等值式Û "x(F(x)ÙØG(x) 量詞分配等值式解2 Û "xF(x)ÙØ$yG(y) 換名規(guī)則Û "xF(x)Ù"yØG(y) 量詞否定等值式Û &

44、quot;x(F(x)Ù"yØG(y) 量詞轄域擴張Û "x"y(F(x)ÙØG(y) 量詞轄域擴張第四章笛卡兒積A=0, 1, B=a, b, cA´B=<0,a>,<0,b>,<0,c>,<1,a>,<1,b>,<1,c> B´A =<a,0>,<b,0>,<c,0>,<a,1>,<b,1>,<c,1> (1) R=<x,y> | x,y

45、ÎN, x+y<3 =<0,0>, <0,1>, <0,2>, <1,0>, <1,1>, <2,0> (2) C=<x,y> | x,yÎR, x2+y2=1，其中R代表實數(shù)集合， C是直角坐標平面上點的橫、縱坐標之間的關(guān)系， C中的所有的點恰好構(gòu)成坐標平面上的單位圓. (3) R=<x,y,z> | x,y,zÎR, x+2y+z=3， R代表了空間直角坐標系中的一個平面. 例1 R=<a,b>,<c,d>,<a,d>,<d,d>, 則domR = a, c, a, d ranR =b, d, dfldR = a, c, a, d, b, d 例2 R=<1,2>, <2,3>, <1,4>, <2,2> S=<1,1>, <1,3>, <2,3>, <3,2>, <3,3>