離散數(shù)學(xué)課件-第1章-5(上)

1、1離散數(shù)學(xué)Discrete Mathematics 汪榮貴 教授合肥工業(yè)大學(xué)軟件學(xué)院專用課件2010.06第一章 邏輯與證明 學(xué)習(xí)內(nèi)容1.1 邏輯1.2 命題等價1.3 謂詞和量詞 1.4 對偶與范式1.5 推理規(guī)則1.6 證明導(dǎo)論1.7 證明的方法和策略1.8 數(shù)理邏輯的應(yīng)用命題邏輯推理推理前提集推理規(guī)則有效論證結(jié)論有效結(jié)論推理的過程就是證明永真蘊(yùn)含式的過程定義1：令H1，H2，Hn是已知的命題公式(前提)，若 有 H1H2.Hn C ，則稱C是H1，H2，Hn 的有效結(jié)論，簡稱結(jié)論。真值表法 依據(jù)A B的概念和定理直接證法 利用P、T規(guī)則間接證法 CP規(guī)則、反證法判別有效結(jié)論的常用方法論證

2、步驟：自然語言描述符號化前提結(jié)論結(jié)論有效？結(jié)論成立結(jié)論不成立有效無效1. 用全真值表證明 要證明C 為前提A1，A2，An 的有效結(jié)論，只需構(gòu)造命題公式A1A2AnC的真值表，證明它是重言式。2. 用部分真值表證明 因?yàn)闂l件命題A1A2 An C為假當(dāng)且僅當(dāng)它的前件A1A2An為真，后件C為假。只要能排除前件為真，后件為假的情況，A1A2 An C就是重言式。從而C為一組前提A1，A2，An的有效結(jié)論。 于是就有了下面方法：真值表法 構(gòu)造A1，A2，An與C 的真值表，且作在一個表上。 找出A1，A2，An 都為真的行，若C也為真，則A1A2An C，即C為前提A1，A2，An的有效結(jié)論。 找

3、出C 為假的行，若在每個這樣的行中， A1，A2，An的真值至少有一個為假，則A1A2 An C，即C為一組前提A1，A2，An的有效結(jié)論。【example】分析事實(shí)：“如果我有時間，那么我就去上街；如果我上街，那么我就去書店買書；但我沒有去書店買書，所以我沒有時間。”。試指出這個推理前提和結(jié)論，并證明結(jié)論是前提的有效結(jié)論。solution： 令 p：我有時間。 q：我去上街。r：我去書店買書。根據(jù)題意，前提為：pq，qr，r結(jié)論為：p 以下證明p是一組前提 p q，q r，r的有效結(jié)論。即證明：( p q )( q r ) r p 下面用部分真值表進(jìn)行證明。 作公式pq，qr，r，p的真值表

4、，如表1所示。表1pqrpqqrrp00011110011101010101101111011000110101010011010101111100qr，r至少有一個為0，所以 (pq)(qr)rp從表中可以看出： pq，qr，r都為1的行(賦值000的行)，p也為1。 p為0的行(賦值100，101，110，111的行) pq，【example】甲乙兩隊進(jìn)行乒乓球比賽，小張上場則小李上場，小李上場則甲隊取勝，小張或小李上場了，所以甲隊取勝。Solution： (1)命題符號化 令 P:小張上場；Q:小李上場；R:甲隊取勝 本例符號化為:(PQ)(QR) (PQ)R (2)列真值表（見后頁）（

5、3）分析結(jié)論有效性：由第四行、第八行可知，當(dāng)前件為真時，結(jié)論為真，所以蘊(yùn)含式成立，結(jié)論有效。PQRPQQRPQFFFTTFFFTTTFFTFTFTFTTTTTTFFFTTTFTFTTTTFTFTTTTTTT直接證法規(guī)則P(引入前提規(guī)則)：在推理過程中，可以隨時引入前提。規(guī)則T(引入結(jié)論規(guī)則)：在推理過程中，如果前邊有一個或幾個公式永真蘊(yùn)涵公式S，則可將S納入推理過程中。推理規(guī)則直接證法就是由一組前提，利用一些公認(rèn)的推理規(guī)則，根據(jù)已知的等價或蘊(yùn)含公式，推演得到有效的結(jié)論。推理過程中，要應(yīng)用下面所列出的永真蘊(yùn)涵式I1-I16和等價公式E1-E22。具體公式見下表。下面請看一些例子。I1P Q PI

6、9P,Q P Q I2P Q QI10P, P Q QI3P P Q I11P, P Q QI4Q P Q I12Q, P Q PI5P P QI13P Q, Q R P RI6Q P Q I14P Q, P R, Q R R I7(P Q ) P I15A B (A C ) (B C)I8(P Q ) QI16A B (A C ) (B C)常見的蘊(yùn)涵規(guī)則表E1 P PE12R (P P) RE2PQ QPE13R (P P) RE3PQQ PE14R (P P) TE4(PQ ) R P (Q R)E15R (P P) FE5(P Q ) R P (Q R)E16P Q P Q E6P (

7、Q R) (P Q) (P R)E17(P Q ) P Q E7P (Q R) (P Q) (P R)E18P Q Q P E8(PQ ) P Q E19P (Q R) (PQ ) RE9(P Q ) P Q E20PQ (P Q ) (Q P ) E10PP PE21PQ (PQ ) (P Q )E11P P PE22(PQ ) PQ 等價式規(guī)則表【example】求證 PQ，QR，P RProof： 序號 前提或結(jié)論 所用規(guī)則 從哪幾步得到 所用公式 (1) P P (2) PQ P (3) Q T (1)(2) I11 (4) QR P (5) R T (3)(4) I11（注公式I11

8、為： P,PQ Q ）【example】證明(pq)(qr)pr 證明： pqP p P q T qr P r T【example】證明(P Q) (P R) (Q S) S R. Proof(1): (1) P Q P (2) P Q T(1) E (3) Q S P (4) P S T(2),(3) I (5) S P T(4) E (6) P R P (7) S R T(5),(6) I (8) S R T(7)EProof(2): (1) P R P (2) P Q R Q T(1) I (3) Q S P (4) QR S R T(3) I (5) P Q S R T(2),(4)

9、I (6) P Q P (7) S R T(5),(6) I 【example】證明 (W R) V, V C S, SU, CU WProof: (1) CU P (2) U T(1) I (3) SU P (4) S T(2),(3)I (5) C T(1)I (6) CS T(4),(5)I (7) (C S) T(6)E (8) (W R) V P (9) V C S P (10) (W R) (C S) T(8),(9)I (11) (W R) T(7),(10)I (12) W R T(11)E (13) W T(12)I【example】用邏輯推理方法證明推理的有效性：如果我學(xué)習(xí)

10、，那么我數(shù)學(xué)不會不及格。如果我不熱衷于玩樸克，那么我將學(xué)習(xí)。但是我數(shù)學(xué)不及格。因此，我熱衷于玩樸克。Proof： 設(shè) P：我學(xué)習(xí)。 Q：我數(shù)學(xué)及格。 R：我熱衷于玩樸克。 于是符號化為： PQ，RP，Q RPQ，RP，Q R(1) PQ P(2) Q P (3) P T (1)(2) I12 (4) RP P(5) R T (3)(4) I12 (6) R T (5) E1 注：公式I12為： Q，PQ P 公式E1 為： RR 【example】求證P(QS),RP,Q RS proof: (1) P(QS) P (2) P(QS) T (1) E16 (3) P(SQ) T (2) E3

11、(4) (PS)Q T (3) E5 (5) Q P (6) PS T (4)(5) I10 (7) PS T (6) E16 (8) RP P (9) RP T (8) E16 (10) RS T (7)(9) I13間接證法不僅使用P規(guī)則，T規(guī)則，還是用反證法或CP規(guī)則的推理方法被稱為間接證法。相容性定義：假設(shè)公式H1, H2，, Hm 中的命題變元為 P1, P2, ，Pn，對于P1, P2, ，Pn的一些真值指派，如果能使H1H2.Hm的真值為T，則稱公式 H1, H2, ，Hm 是相容的。如果對于P1, P2, ，Pn的每一組真值指派使得H1H2.Hm的真值均為F, 則稱公式H1,

12、H2，, Hm是不相容的。我們可把不相容的概念應(yīng)用于命題公式的證明。設(shè)有一組前提H1, H2，, Hm 要推出結(jié)論C,即證H1H2.Hm C，記作SC，即 C S為永真，或C S為永真，故 C S為永假。 因此要證明H1H2.Hm C，只要證明H1, H2，, Hm 與 C 是不相容的。間接證法的另一種情況是： 若要證H1H2.Hm (R C)。設(shè)H1H2.Hm為S，即證S (R C)或S (R C)，故S (R C)為永真式。 因?yàn)镾 (R C) S (R C) (S R) C (SR) C (SR) C , 所以若將R作附加前提，如有(SR) C 即證得S (R C). 由(SR) C ，

13、證得S (R C)稱為CP規(guī)則。CP規(guī)則注意：CP規(guī)則適用于結(jié)論為條件式的有效推理。使用CP規(guī)則就是把結(jié)論中的淺見作為附加前提加入前提集合，共同去推出結(jié)論的后件?！緀xample】使用CP規(guī)則證法求證 P(QS),RP,Q RS。Proof： (1) R P(附加前提) (2) RP P (3) P T (1)(2) I10 (4) P(QS) P (5) QS T (3)(4) I11 (6) Q P (7) S T (5)(6) I11 (8) RS CP 【example】用邏輯推理方法證明下面推理的有效性： 如果體育館有球賽，青年大街交通就擁擠。在這種情況下，如果小王不提前出發(fā)，就會遲

14、到。因此，小王沒有提前出發(fā)也未遲到，則體育館沒有球賽。Proof： 先將命題符號化： 設(shè) P：體育館有球賽。 Q：青年大街交通擁擠。 R：小王提前出發(fā)。 S：小王遲到。 則要證：PQ，(QR)S (RS)P PQ，(QR)S (RS)Pproof： (1) RS P(附加前提) (2) R T (1) I1 (3) S T (1) I2 (4) (QR)S P (5) (Q) T(3)(4) I12 (6) QR T (5) E8 (7) Q T (2)(6) I10 (8) PQ P (9) P T (7)(8) I12 (10)(RS)P CP【example】 A (BC), D A,

15、B D C。 Proof： (1) D P (2) D A P (3) A T(1),(2)I (4) A (BC) P (5) BC T(3),(4)I (6) B P (7) C T(5),(6)I (8) D C CP反證法反證法的主要思想是：假設(shè)結(jié)論不成立,可以推出矛盾式。下面先介紹有關(guān)概念和定理。反證法定義：設(shè)有前提集合H1，H2 ，.，Hn ，H1，H2 ，.，Hn是相容的，H1 H2 . Hn C ，當(dāng)且僅當(dāng)H1，H2 ，.，Hn， C是不相容的。 或說H1 H2 . Hn C F（永假式）。Proof： 將H1 H2 . Hn 記為S，只需證S C 當(dāng)且僅當(dāng) S C F。必要性

16、：假定S C F，所以前件S C 必須為永假，因?yàn)镠1 H2 . Hn 是相容的，所以S不是永假式，在所有使S為真的真值指派下，C 必須為假。 所以，S為真時必得C為真，故有S C 。 即H1 H2 . Hn C.充分性：假定S C ，因?yàn)镾不是永假式，所以在所有使S為真的真值指派下，C都為真，或C 都為假。 所以在任何真值指派下S C 為假， S C 為永假式。 即S C F。 【example】證明A B, (B C)可邏輯推出 A。 Proof： (1) A B P (2)A P(附加前提) /* A A (3) (B C) P (4) B C T(3)E (5)B T(1),(2)I

17、(6) B T(4)I (7) B B T(5),(6)I /* B B 為永假式?！緀xample】 PQ, (QR)R, (PS) S Proof： (1) S P(假設(shè)前提) (2) S T (1)E (3) (PS) P (4) PS T (3)E (5) P T (2)(4)I (6) PQ P (7) Q T (5)(6)I (8) (QR)R P (9) QR T (8)I (10) R T (8)I (11) R T (7)(9)I (12) RR T (10)(11）I【example】用反證法證明 (pq)r，rs，s，pq Proof： q P(附加前提) rs P s

18、P r T析取三段論 (pq)r P (pq) T拒取式 pq T德摩根律 p P q T析取三段論 qq(矛盾) T合取引入【練習(xí)】用推理規(guī)則證明一下各式。 a) (P Q), Q R, R P b) J (M N), (H G) J, H G M N c) P Q, ( Q R) R, ( P S) SProof： a） (P Q), Q R, R P (1) R P (2) Q R P (3) Q T(1)(2)I (4) (P Q) P (5) P Q T(4)E (6) P T(3)(5)Ib) J (M N), (H G) J, H G M NProof：(H G) J P(H G

19、) PJ T(1)(2)IJ (M N) PM N T(3)(4)Ic) P Q, ( Q R) R, ( P S) S( Q R) R P Q R T(1)I R T(1)I Q T(2)(3)IP Q P P T(4)(5)I( P S) PP S T(7)E S T(6)(8)I2. 僅用規(guī)則P和T，推證以下公式。 a) A B , C B A C b) A (B C),(CD) E, F (D E) A (B F) c) A B CD, D E F A F d) B D,(E F) D B EProof: a) A B , C B A C (1) (A C) P(附加前提) (2)A

20、T(1)I (3)C T(1)I (4) A B P (5)B T(2)(4)I (6) C B P (7) B T(3)(6)I (8) B B T(5)(7) 矛盾 b) A (B C),(CD) E, F (D E) A (B F)(A (B F) ) P(附加前提)A T(1)I (B F) T(1)IB T(3)IF T(3)IA (B C) PB C T(2)(6)IC T(4)(7)IF (D E) P(10) D E T(5)(9)I(11) D T(10)I(12) C D T(8)(11)I(13) (C D ) E P(14) E T(12)(13)I(15) E T(1

21、0)I(16) E E T(14)(15) 矛盾A B CD, D E F A F (1) (A F) P(附加前提) (2)A T(1)I (3) F T(1)I (4) A B T(2)I (5) A B CD P (6) CD T(4)(5)I (7)C T(6)I (8)D T(6)I (9) D E T(8)I (10) D E F P (11)F T(9)(10)I (12) F F T(3)(11)矛盾d) B D,(E F) D B E (1) (B E) P(附加前提) (2) B T(1)I (3) E T(1)I (4) B D P (5) D T(2)(4)I (6) (E F) D P (7) (E F) T(5)(6)I (8) E T(7)I (9) E E 矛盾 3. 用推理步驟法證明下列命題：一臺電腦處于死機(jī)狀態(tài)的原因，或是由于病毒或是由于非法操