離散數(shù)學王元元習題解答 (1)

1、1 命題演算及其形式系統(tǒng)1.1 命題與聯(lián)結(jié)詞 內(nèi)容提要1.1.1 命題 我們把對確定的對象作出判斷的陳述句稱作命題（propositions），當判斷正確或符合客觀實際時，稱該命題真（true），否則稱該命題假（false）?！罢?、假”常被稱為命題的真值。 自然語言中“并非、或者、并且、如果，那么、當且僅當 ” 這樣的聯(lián)結(jié)詞稱為邏輯聯(lián)結(jié)詞（logical connectives）。通常把不含有邏輯聯(lián)結(jié)詞的命題稱為原子命題或原子（atoms），而把由原子命題和邏輯聯(lián)結(jié)詞共同組成的命題稱為復合命題（compositive propositions）。1.1.2 聯(lián)結(jié)詞否定詞(negation)“并

2、非”（not），用符號表示。設p表示一命題，那么p表示命題p的否定。p真時p假，而p假時p真。p讀作“并非p”或“非p”。 合取詞(conjunction)“并且”（and），用符號表示。設p，q表示兩命題，那么pq表示合取p和q所得的命題，即p和q同時為真時pq真，否則pq為假。pq讀作“p并且q”或“p且q”。 析取詞(disjunction)“或”（or）用符號表示。設p，q表示兩命題，那么pq表示p和q的析取，即當p和q有一為真時，pq為真，只有當p和q均假時pq為假。pq讀作“p或者q”、“p或q”。 蘊涵詞(implication)“如果，那么”（ifthen），用符號表示。設p，

3、q表示兩命題，那么pq表示命題“如果p，那么q”。當p真而q假時，命題pq為假，否則均認為pq為真。pq中的p稱為蘊涵前件，q稱為蘊涵后件。pq的讀法較多，可讀作“如果p則q”，“p蘊涵q”，“p是q的充分條件”，“q是p的必要條件”，“q當p”，“p僅當q”等等。數(shù)學中還常把qp，pq，qp分別叫做pq的逆命題，否命題，逆否命題。 雙向蘊涵詞(two-way implication)“當且僅當”（if and only if），用符號«表示之。設p，q為兩命題，那么p«q表示命題“p當且僅當q”，“p與q等價”，即當p與q同真值時p«q為真，否則為假。p

4、1;q讀作“p雙向蘊涵q”，“p當且僅當q”，“p等價于q”。由于“當且僅當”“等價”常在其它地方使用，因而用第一種讀法更好些。1.1.3 命題公式及其真值表我們把表示具體命題及表示常命題的p，q，r，s與f，t統(tǒng)稱為命題常元（proposition constant）。深入的討論還需要引入命題變元（proposition variable）的概念，它們是以“真、假”或“1，0”為取值范圍的變元，為簡單計，命題變元仍用p，q，r，s等表示。 定義1.1 以下三條款規(guī)定了命題公式（proposition formula）的意義： （1）命題常元和命題變元是命題公式，也稱為原子公式或原子。 （2）

5、如果A，B是命題公式，那么（A），（AB），（AB），（AB），（A«B）也是命題公式。 （3）只有有限步引用條款（1），（2）所組成的符號串是命題公式。 如果公式A含有命題變元p1，p2，pn，記為A(p1,pn)，并把聯(lián)結(jié)詞看作真值運算符，那么公式A可以看作是p1,pn的真值函數(shù)。對任意給定的p1,pn的一種取值狀況，稱為指派（assignments），用希臘字母a，b等表示，A均有一個確定的真值。當A對取值狀況 a 為真時，稱指派a弄真A，或a是A的成真賦值，記為a (A) = 1；反之稱指派a弄假A，或a是A的成假賦值，記為a (A) = 0。對一切可能的指派,公式A的取值可

6、能可用一張表來描述,這個表稱為真值表（truth table）。當A(p1,pn)中有k個聯(lián)結(jié)詞時，公式A的真值表應為2n行、k+n列（不計表頭）。1.1.4 語句的形式化用我們已有的符號語言，可以將許多自然語言語句形式化。語句形式化要注意以下幾個方面。 要善于確定原子命題，不要把一個概念硬拆成幾個概念，例如“弟兄”是一個概念，不要拆成“弟”和“兄”、“我和他是弟兄”是一個原子命題。 要善于識別自然語言中的聯(lián)結(jié)詞（有時它們被省略）。例如“風雨無阻，我去上學”一句，可理解為“不管是否刮風、是否下雨我都去上學”。 否定詞的位置要放準確。需要的括號不能省略，而可以省略的括號，在需要提高公式可讀性時亦

7、可不省略。另外要注意的是,語句的形式化未必是唯一的。 習題解答練習1.1 1、判斷下列語句是否是命題，若是命題則請將其形式化： （1）a+b （2）x>0 （3）“請進！” （4）所有的人都是要死的，但有人不怕死。 （5）我明天或后天去蘇州。 （6）我明天或后天去蘇州的說法是謠傳。 （7）我明天或后天去北京或天津。 （8）如果買不到飛機票，我哪兒也不去。 （9）只要他出門，他必買書，不管他余款多不多。 （10）除非你陪伴我或代我雇輛車子，否則我不去。 （11）只要充分考慮一切論證，就可得到可靠見解；必須充分考慮一切論證，才能得到可靠見解。 （12）如果只有懂得希臘文才能了解柏拉圖，那么我

8、不了解柏拉圖。 （13）不管你和他去不去，我去。 （14）侈而惰者貧，而力而儉者富。（韓非：韓非子·顯學）（15）騏驥一躍，不能十步；駑馬十駕，功在不舍；鍥而舍之，朽木不折；鍥而不舍，金石可鏤。（荀況：荀子·勸學）解 （1）a+b 不是命題 （2）x>0 不是命題（x是變元） （3）“請進！” 不是命題 （4）所有的人都是要死的，但有人不怕死。 是命題 可表示為pq，其中p：所有的人都是要死的，q：所有的人都怕死 （5）我明天或后天去蘇州。 是命題 可表示為pq，其中p：我明天去蘇州；q：我后天去蘇州（6）我明天或后天去蘇州的說法是謠傳。 是命題 可表示為(pq)，其

9、中p、q同（5）（7）我明天或后天去北京或天津。 是命題 可表示為pqrs，其中p：我明天去北京，q：我明天去天津，r：我后天去北京，s：我后天去天津（8）如果買不到飛機票，我哪兒也不去。 是命題 可表示為pq，其中，p：我買到飛機票，q：我出去（9）只要他出門，他必買書，不管他余款多不多。 是命題 可表示為(pqr)(pqr)或qr，其中p：他余款多，q：他出門，r：他買書（10）除非你陪伴我或代我雇輛車子，否則我不去。 是命題 可表示為(pq) « r，其中p：你陪伴我，q：你代我雇車，r：我去（11）只要充分考慮一切論證，就可得到可靠見解；必須充分考慮一切論證，才能得到可靠見解

10、。 是命題 可表示為(pq) (qp )或p «q，其中p：你充分考慮了一切論證，q：你得到了可靠見解 （12）如果只有懂得希臘文才能了解柏拉圖，那么我不了解柏拉圖。 是命題 可表示為(qp ) q，其中p：我懂得希臘文，q：我了解柏拉圖 （13）不管你和他去不去，我去。 是命題可表示為(pr) (qr) ( pr) ( qr)或r，其中p：你去，q：他去，r：我去（14）侈而惰者貧，而力而儉者富。（韓非：韓非子·顯學） 是命題可表示為(pq)r) (pq)r)，其中p：你奢侈，q：你懶惰，r：你貧困（15）騏驥一躍，不能十步；駑馬十駕，功在不舍；鍥而舍之，朽木不折；鍥而不

11、舍，金石可鏤。（荀況：荀子·勸學） 是命題可表示為(pq) (sr) (mno) (mnv)，其中p：騏驥一躍，q：騏驥一躍十步，r：駑馬行千里，s：駑馬不斷奔跑，m：你雕刻，n：你放棄，o：將朽木折斷，v：金石可雕刻 2、判定下列符號串是否為公式，若是，請給出它的真值表，并請注意這些真值表的特點（公式中省略了可以省略的括號）： （1）(p)（p為原子命題） （2）(pqr)s （3）(pq)p （4）p(pq) （5）(pp) （6）p(pq)q （7）p(pq)(pq) （8）(pq) « (qp) （9）(pq) «qp （10）pq« (pq)

12、（11）(pq)(qr)(pr)（12）(pqr) « (pr)(qr)解 （1）(p) 不是公式 （2）(pqr)s 不是公式 （3）(pq)p 是公式 pqpq(pq)pp(pq)00011011011011111111 （4）p(pq) 是公式（真值表見上表，恒真）（5）(pp) 是公式（恒假）pppp(pp)01101010（6）p(pq)q 是公式（恒真）pqpqp(pq)p(pq)q00101011011000111111（7）p(pq)(pq) 是公式（恒假）pqqpqp(pq)pqp(pq)(pq)0011010010101010100101101100（8）(pq)

13、 « (qp) 是公式（恒真）pqpqpqqp(pq) « (qp)0011111011011110010011100111（9）(pq) «qp 是公式（恒真）pqpqpq(pq)qp(pq) «qp00110111011010011001100111001001（10）pq« (pq) 是公式（恒真）pqppqpqpq« (pq)001111011111100001110111（11）(pq)(qr)(pr) 是公式（恒真）pqrpqqrpr(pq)(qr)(pq)(qr)(pr)0001111100111111010101010

14、111111110001001101011011101000111111111（12）(pqr) « (pr)(qr) 是公式（恒真）pqrpqpqrprqr(pr)(qr)(pqr) « (pr)(qr)000011111001011111010101001011111111100100101101111111110101001111111111*3、A國的人只有兩種，一種永遠說真話，一種永遠說假話。你來到A國，并在一個二叉路口不知如何走才能到達首都。守衛(wèi)路口的士兵只準你問一個問題，而且他只答“是”或“不是”。你應該如何發(fā)問，才能從士兵處獲知去首都的道路。解 設p：你是說

15、真話的；q：我應當向右走去首都 你應當問：p«q ? 當回答“是 (真)”，你選擇向右走；當回答“不（假）”時，你選擇向左走。因為 p«q真，當且僅當p真且q真（士兵說真話且應當向右走）或p假且q假（士兵說假話且應當向左走） p«q假，當且僅當p真且q假（士兵說真話且應當向左走）或p假且q假（士兵說假話且應當向右走）1.2 重言式 內(nèi)容提要1.2.1 重言式概念定義1.2 命題公式A稱為重言式（tautology），如果對A中命題變元的一切指派均弄真A，因而重言式又稱永真式；A稱為可滿足式（satisfactable formula），如果至少有一個指派弄真A，否

16、則稱A為不可滿足式或永假式、矛盾式。1.2.2 邏輯等價式和邏輯蘊涵式 定義1.3 當命題公式A«B為永真式時，稱A邏輯等價于B，記為AB，它又稱為邏輯等價式(logically equivalent)。 以下是一些重要的邏輯等價式，其中A，B，C表示任意命題公式： E1 AA 雙重否定律E2 AAA 冪等律 E3 AAA 冪等律 E4 ABBA 交換律 E5 ABBA 交換律E6 (AB)CA(BC) 結(jié)合律 E7 (AB)CA(BC) 結(jié)合律 E8 A(BC)(AB)(AC) 分配律 E9 A(BC)(AB)(AC) 分配律 E10 (AB)AB 德摩根律 E11 (AB)AB

17、德摩根律 E12 A(AB)A 吸收律 E13 A(AB)A 吸收律E14 ABAB E15 A« B(AB)(BA)E16 AttE17 AtAE18 AfAE19 AffE20 AAtE21 AAfE22 tf, ftE23 ABCA(BC)E24 ABBAE25 (AB)(AB)A 定義1.4 當命題公式AB為永真式時，稱A邏輯蘊涵B，記為A B，它又稱為邏輯蘊涵式(logically implication)。 我們也列出一些十分重要的邏輯蘊涵式： I1 A AB，B AB I2 AB A，AB BI3 A(AB) BI4 (AB)B AI5 A(AB) B，B(AB) AI

18、6 (AB)(BC) ACI7 (AB)(CD) (AC)(BD)I8 (A«B)(B«C) A«C 邏輯等價式與邏輯蘊涵式有如下明顯性質(zhì)。 定理1.1 對任意命題公式A，B，C，A'，B'， （1）AB當且僅當 A«B （2）A B當且僅當 AB （3）若AB，則BA （4）若AB，BC，則AC （5）若A B，則B A （6）若A B，B C，則A C （7）若A B，AA'，BB'，則A' B' 定理1.2 設A為永真式，p為A中命題變元，A(B/p)表示將A中p的所有出現(xiàn)全部代換為公式B后所得的命題

19、公式（稱為A的一個代入實例），那么A(B/p)亦為永真式。 定理1.3 設A為一命題公式，C為A的子公式（A的一部分，且自身為一公式），且CD。若將A中子公式C的某些（未必全部）出現(xiàn)替換為D后得到公式B，那么AB。 定理1.2常被稱為代入原理（rule of substitution），簡記為RS。定理1.3常被稱為替換原理（rule of replacement）簡記為RR。1.2.3 對偶原理 定義1.5 設公式A僅含聯(lián)結(jié)詞 ，A*為將A中符號，t，f分別改換為，f，t后所得的公式，那么稱A*為A的對偶（dual）。 顯然A與A*互為對偶，即(A*)*=A 定理1.4 設公式A中僅含命題變

20、元p1,pn，及聯(lián)結(jié)詞，那么 AA*(p1/p1, pn/pn)這里A*(p1/p1, pn/pn)表示在A*中對p1,pn分別作代入p1, pn后所得的公式。定理1.5 設A，B為僅含聯(lián)結(jié)詞，和命題變元p1,pn的命題公式，且滿足AB，那么有B* A*。進而當AB時有A*B*。常把B* A*，A*B*稱為A B和AB的對偶式。 習題解答練習1.2 1、試判定以下各式是否為重言式： （1）(pq)(qp) （2）p(pq) （3）q(pq) （4）pq(p«q) （5）(pq)(rq)(pr)q)（6）(pq)(rs)(pr)(qs)解 （1）否 （2）是 （3）是 （4）是 （5）

21、否 （6）否2、試用真值表驗證E6，E8，E10，E11，E23。證 （1）E6 (AB)C «A(BC)ABCAB(AB)CBCA(BC)E60000000100101111010111110111111110011011101111111101111111111111 （2）E8 A(BC) «(AB)(AC)ABCBCA(BC)ABAC(AB)(AC)E8000000001001100001010100001011100001100000001101110111110111011111111111 （3）E10 (AB) «ABABAB(AB)ABABE10

22、 00011111011010011010010111100001 （4）E11 (AB) «AB ABABAB(AB)ABE1100110111011001111001011111001001 （5）E23 (ABC) « (A(BC)ABCABABCBCA(BC)E2300001111001011110100101101101111100011111010111111010001111111113、不用真值表，用代入、替換證明E12，E13，E24。證 （1）E12： A(AB) A A(AB) (At)(AB) 據(jù)E17用RR A (tB) 對E8用RS At 據(jù)E1

23、6用RR A 據(jù)E17 （2）E13： A(AB) A A(AB) (Af)(AB) 據(jù)E18用RR A(fB) 對E9用RS Af 據(jù)E19用RR A 據(jù)E18 （3）E24： AB BA BABA 對E14用RS BA 據(jù)E1用RR AB 對E4用RS AB 據(jù)E14 4、試用真值表驗證I3，I4，I5，I6。證 （1）I3 A(AB)BABABA(AB)A(AB)B00101011011000111111 （2）I4 (AB) BAABBAAB(AB) BI40011111010110110100011100101 （3）I5 A(AB)B B(AB)AABAABA(AB)A(AB)B0

24、01001011111100101110101ABBABB(AB)B(AB)A001001010101101111110101 （4）I6 (AB) (BC) (AC)ABCABBCAC(AB)(BC)I600011111001111110101010101111111100010011010110111010001111111115、不用真值表，用代入、替換證明I7，I8。證 （1）I7：(AB)(CD) (AC)(BD) (AB)(CD)(AB)(CD) (AC)(BD)(AC)(BD) (ACB)(ACD)由于(AB)(CD) (ACB)(ACD)故(AB)(CD) (AC)(BD)。

25、（2）I8：(A«B)(B«C) (A«C) (A«B)(B«C)(AB)(BA)(BC)(CB) (AB)(BC) (CB)(BA) (AC) (CA) (A«C) 6、用三種不同方法證明下列邏輯等價式： （1）A«B(AB)(AB) （2）A(BC)B(AC) （3）A(AB)AB（4）A(BC)(AB)(AC)證 （1）證法1：ABABABABA«B(AB)(AB)00011111010100001000100011100011 證法2：A«B(AB)(BA) (AB)(BA) (AB)(AA)(B

26、B)(BA) (AB)(AB) 證法3：先證A«B (AB)(AB) (a) 設a為任一指派，使a(A«B)=1，那么a(A)= a(B)=1或a(A)= a(B)=0，從而a(AB)=1或a(AB)=1，即a(AB)(AB)=1。(a)得證；再證(AB)(AB) A«B (b)設a為任一指派，使a(A«B)=0，那么a(A)=1，a(B)=0，或者a(A)=0，a(B)=1，從而a(AB)=0且a(AB)=0，即a(AB)(AB)=0。(b)得證。 （2）證法1：ABCBCACA(BC)B(AC)0001111001111101001110111111

27、1001011101111111000001111111 證法2：A(BC)A(BC) (AB)C (BA)C B(AC) B(AC) 證法3：先證A(BC) B(AC) (a) 設a為任一指派，使a(A(BC)=1，那么） a(A)= 0，則a( AC)=1，從而a( B(AC)=1） a(A)= 1，a(B)=0，則a( B(AC)=1） a(A)=a(B)=a(C)=1，則a( B(AC)=1綜上，(a)得證；同理可證B(AC) A(BC)。（3）證法1：ABABA(AB)(A(AB) « (AB)00111011111000111111 證法2：A(AB)A(AB) (AA)

28、B AB AB 證法3：先證A(AB) AB (a) 設a為任一指派，使a( AB)=0，那么a(A)=1，a(B)=0，從而a( A(AB)=0。(a)得證；再證AB A(AB) (b)設a為任一指派，使a(A(AB)=0，那么a(A)=1，a(AB)=0。(b)得證。（4）證法1：ABCBCABACA(BC)(AB)(AC)0001111100111111010011110111111110010011101101111100100011111111 證法2：(AB)(AC)(AB) (AC) (AB) (AC) ( (AB)A)C (AA)(BA) )C (t(AB) )C (AB)C

29、A(BC) A(BC) 證法3：先證A(BC) (AB)(AC) (a) 設a為任一指派，使a(AB)(AC)=0，那么a( AB)=1，a( AC)=0，即a(A)= a(B)=1，a(C)=0，從而a( BC)=0，a( A(BC)=0。(a)得證；再證(AB)(AC) A(BC) (b)設a為任一指派，使a( A(BC)=0，那么a(A)=1，a(BC)=0，即 a(B)=1，a(C)=0，從而a(AB)=1，a( AC)=0，a(AB)(AC)=0。(b)得證。 7、用三種不同方法證明下列邏輯蘊涵式： （1）AB A«B （2）(AB)A A （3）AB (A«B)

30、A)B（4）(AB)(AC)(BC) C證 （1）證法1：ABABA«B(AB) (A«B)00011010011000111111 證法2：AB (AB) (AB) A«B 證法3：設a為任一指派，使a(AB)=1，則a(A)= a(B)=1，從而a( A«B)=1。AB A«B得證。 （2）證法1：ABAB(AB)A(AB)A) A00101011011001111111 證法2：(AB)A (AB) A (AB) A (A A)(BA) A(BA) A 證法3：設a為任一指派，使a(A)=0，則a(AB)= 1，從而a(AB)A)=0。(

31、AB)A A得證。 （3）證法1：ABABA«B(A«B)A(A«B)A)B(AB)(A«B)A)B)0011011011011110001011111111 證法2：ABAB (A«B)A)B(A«B)A)B (A«B) A)B (AB)(AB)A)B (AB)B AB AB (A«B)A)B 證法3：設a為任一指派，使a( AB)=1，則（）a(A)= 0；（）a(B)= 1。對（）顯然有a( (A«B)A)B)=1；對（）則可令a(B)= 0（a(B)= 1的情況已證），于是a(A«B)=

32、1，a(A«B)A)=0，a(A«B)A)B) =1。 AB (A«B)A)B得證。 （4）證法1：ABCABACBC(AB)(AC)(BC)(AB)(AC)(BC)C0000110100101101010110010111111110010101101111111101000111111111 證法2：(AB)(AC)(BC)(AB)(AC)(BC) (ABC)(ABC)(ABC)(ABC)(ABC) (ABC)(ABC)(ABC)(ABC) (AC) (AC) C證法3：設a為任一指派，使a(AB)(AC)(BC)=1，則a(AB)= a( AC)= a( B

33、C)=1。由a(AB)=1有兩種情況：（）a(A)=1，由a( AC)=1得a(C)=1；（）a(B)= 1，由a( BC)=1得a(C)=1。 (AB)(AC)(BC) C得證。 8、驗證下列邏輯等價式和邏輯蘊涵式，并寫出它們的對偶式： （1）(AB)(AB)A （2）(AB)(AB)(AB)(AB) （3）B(AB)A)t （4）A(BC) (AB)(AC)（5）(AB)C A(BC)解 （1）(AB)(AB)(AB)(AB) A(BB) A對偶式 ：(AB)(AB)A （2）(AB)(AB)(AB)A(BB)(AB) A(AB) AB (AB)對偶式 ：(AB)(AB)(AB)(AB)

34、（3）B(AB)A)B(AB)A) B(BA) t對偶式 ：B(AB)A)f （4）A(BC) ABAC (AB)(AC)對偶式 ：(AB)(AC) A(BC) （5）(AB)C (AB)C (AC)(BC) BC A(BC)對偶式 ：A(BC) (AB)C1.3 范式 內(nèi)容提要1.3.1 析取范式和合取范式 文字(letters)：指命題常元、變元及它們的否定，前者又稱正文字，后者則稱負文字。析取子句(disjunctive clauses)：指文字或若干文字的析取。例如, p , pq , pqr .合取子句(conjunctive clauses)：指文字或若干文字的合取。例如, p ,

35、 pq , pqr . 互補文字對(complemental pairs of letters) ：指形如L，L（L為文字）的一對字符。 定義1.6 命題公式A'稱為公式A的析取范式（disjunctive normal form），如果 （1）A'A （2）A'為一合取子句或若干合取子句的析取。定義1.7 命題公式A'稱為公式A的合取范式（conjunctive normal form）如果 （1）A'A （2）A'為一析取子句或若干析取子句的合取。1.3.2 主析取范式與主合取范式 定義1.8 設A為恰含命題變元p1,pn的公式。公式A

36、9;稱為A的主析（合）取范式（majordisjunctive（conjunctive）normal form），如果A'是A的析（合）取范式，并且其每個合（析）取子句中p1,pn均恰出現(xiàn)一次。1.3.3 聯(lián)結(jié)詞的擴充與歸約n個變元的真值表可以有張，因而可以定義個n元的真值函數(shù)或聯(lián)結(jié)詞。這就是說，我們可以規(guī)定=4個一元聯(lián)結(jié)詞，=16個二元聯(lián)結(jié)詞。定義1.9 稱n元聯(lián)結(jié)詞h是用m 個聯(lián)結(jié)詞g1, g2, gm 可表示的，如果 h(p1, p2,. . ., pn ) A而A中所含聯(lián)結(jié)詞僅取自g1, g2,. . ., gm。 定義1.10 當聯(lián)結(jié)詞組g1, g2,. . ., gm可表示所有一元、二元聯(lián)結(jié)詞時，稱其為完備聯(lián)結(jié)詞組（complete group of connectives）。 習題解答練