离散数学课件-第1章-5(上)

1、1离散数学Discrete Mathematics 汪荣贵 教授合肥工业大学软件学院专用课件2010.06第一章 逻辑与证明 学习内容1.1 逻辑1.2 命题等价1.3 谓词和量词 1.4 对偶与范式1.5 推理规则1.6 证明导论1.7 证明的方法和策略1.8 数理逻辑的应用命题逻辑推理推理前提集推理规则有效论证结论有效结论推理的过程就是证明永真蕴含式的过程定义1：令H1，H2，Hn是已知的命题公式(前提)，若 有 H1H2.Hn C ，则称C是H1，H2，Hn 的有效结论，简称结论。真值表法 依据A B的概念和定理直接证法 利用P、T规则间接证法 CP规则、反证法判别有效结论的常用方法论证

2、步骤：自然语言描述符号化前提结论结论有效？结论成立结论不成立有效无效1. 用全真值表证明 要证明C 为前提A1，A2，An 的有效结论，只需构造命题公式A1A2AnC的真值表，证明它是重言式。2. 用部分真值表证明 因为条件命题A1A2 An C为假当且仅当它的前件A1A2An为真，后件C为假。只要能排除前件为真，后件为假的情况，A1A2 An C就是重言式。从而C为一组前提A1，A2，An的有效结论。 于是就有了下面方法：真值表法 构造A1，A2，An与C 的真值表，且作在一个表上。 找出A1，A2，An 都为真的行，若C也为真，则A1A2An C，即C为前提A1，A2，An的有效结论。 找

3、出C 为假的行，若在每个这样的行中， A1，A2，An的真值至少有一个为假，则A1A2 An C，即C为一组前提A1，A2，An的有效结论。【example】分析事实：“如果我有时间，那么我就去上街；如果我上街，那么我就去书店买书；但我没有去书店买书，所以我没有时间。”。试指出这个推理前提和结论，并证明结论是前提的有效结论。solution： 令 p：我有时间。 q：我去上街。r：我去书店买书。根据题意，前提为：pq，qr，r结论为：p 以下证明p是一组前提 p q，q r，r的有效结论。即证明：( p q )( q r ) r p 下面用部分真值表进行证明。 作公式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】甲乙两队进行乒乓球比赛，小张上场则小李上场，小李上场则甲队取胜，小张或小李上场了，所以甲队取胜。Solution： (1)命题符号化 令 P:小张上场；Q:小李上场；R:甲队取胜 本例符号化为:(PQ)(QR) (PQ)R (2)列真值表（见后页）（

5、3）分析结论有效性：由第四行、第八行可知，当前件为真时，结论为真，所以蕴含式成立，结论有效。PQRPQQRPQFFFTTFFFTTTFFTFTFTFTTTTTTFFFTTTFTFTTTTFTFTTTTTTT直接证法规则P(引入前提规则)：在推理过程中，可以随时引入前提。规则T(引入结论规则)：在推理过程中，如果前边有一个或几个公式永真蕴涵公式S，则可将S纳入推理过程中。推理规则直接证法就是由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式，推演得到有效的结论。推理过程中，要应用下面所列出的永真蕴涵式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)常见的蕴涵规则表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 等价式规则表【example】求证 PQ，QR，P RProof： 序号 前提或结论 所用规则 从哪几步得到 所用公式 (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】用逻辑推理方法证明推理的有效性：如果我学习

10、，那么我数学不会不及格。如果我不热衷于玩朴克，那么我将学习。但是我数学不及格。因此，我热衷于玩朴克。Proof： 设 P：我学习。 Q：我数学及格。 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规则，T规则，还是用反证法或CP规则的推理方法被称为间接证法。相容性定义：假设公式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是不相容的。我们可把不相容的概念应用于命题公式的证明。设有一组前提H1, H2，, Hm 要推出结论C,即证H1H2.Hm C，记作SC，即 C S为永真，或C S为永真，故 C S为永假。 因此要证明H1H2.Hm C，只要证明H1, H2，, Hm 与 C 是不相容的。间接证法的另一种情况是： 若要证H1H2.Hm (R C)。设H1H2.Hm为S，即证S (R C)或S (R C)，故S (R C)为永真式。 因为S (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规则。CP规则注意：CP规则适用于结论为条件式的有效推理。使用CP规则就是把结论中的浅见作为附加前提加入前提集合，共同去推出结论的后件。【example】使用CP规则证法求证 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】用逻辑推理方法证明下面推理的有效性： 如果体育馆有球赛，青年大街交通就拥挤。在这种情况下，如果小王不提前出发，就会迟

14、到。因此，小王没有提前出发也未迟到，则体育馆没有球赛。Proof： 先将命题符号化： 设 P：体育馆有球赛。 Q：青年大街交通拥挤。 R：小王提前出发。 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反证法反证法的主要思想是：假设结论不成立,可以推出矛盾式。下面先介绍有关概念和定理。反证法定义：设有前提集合H1，H2 ，.，Hn ，H1，H2 ，.，Hn是相容的，H1 H2 . Hn C ，当且仅当H1，H2 ，.，Hn， C是不相容的。 或说H1 H2 . Hn C F（永假式）。Proof： 将H1 H2 . Hn 记为S，只需证S C 当且仅当 S C F。必要性

16、：假定S C F，所以前件S C 必须为永假，因为H1 H2 . Hn 是相容的，所以S不是永假式，在所有使S为真的真值指派下，C 必须为假。 所以，S为真时必得C为真，故有S C 。 即H1 H2 . Hn C.充分性：假定S C ，因为S不是永假式，所以在所有使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 为永假式。【example】 PQ, (QR)R, (PS) S Proof： (1) S P(假设前提) (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合取引入【练习】用推理规则证明一下各式。 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. 仅用规则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. 用推理步骤法证明下列命题：一台电脑处于死机状态的原因，或是由于病毒或是由于非法操