离散数学逻辑推理.ppt

1离散数学 Discrete Mathematics 2.5 2.5 逻辑推理逻辑推理命题逻辑题逻辑 推理推理推理前提集推理规则有效论证结论有效结论推理的过程就是证明永真蕴含式的过程定义1：令H1，H2，…，Hn是已知的命题公式(前提)，若有 H1∧H2∧∧Hn  C ，则称C是H1，H2，…Hn的有效结论，简称结论³真值表法 依据A  B的概念和定理³直接证法 利用P、T规则³间接证法 CP规则、反证法判别有效结论的常用方法判别有效结论的常用方法论证步骤：论证步骤：自然语 言描述符号化前提 结论结论有效？结论成立结论不成立有效无效1. 用全真值表证明要证明C 为前提A1，A2，…，An 的有效结论，只需构造命 题公式A1∧A2∧…∧An→C的真值表，证明它是重言式2. 用部分真值表证明因为条件命题A1∧A2 ∧…∧An →C为假当且仅当它的前件 A1∧A2∧…∧An为真，后件C为假只要能排除前件为真， 后件为假的情况，A1∧A2 ∧…∧An →C就是重言式从而C 为一组前提A1，A2，…，An的有效结论于是就有了下面方法：真值表法真值表法构造A1，A2，…，An与C 的真值表，且作在一个表上。

①找出A1，A2，…，An 都为真的行，若C也为真，则A1∧A2∧…∧An C，即C为前提A1，A2，…，An的有效结论② 找出C 为假的行，若在每个这样的行中， A1，A2，…，An 的真值至少有一个为假，则A1∧A2 ∧…∧An C，即C为一组前提A1，A2，…，An的有效结论example】甲乙两队进行乒乓球比赛，小张上场则小李上场，小李上场则甲队取胜，小张或小李上场了，所以甲队取胜Solution：(1)命题符号化令 P:小张上场；Q:小李上场；R:甲队取胜本例符号化为:(P→Q)∧(Q→R) ∧(P∨Q)R (2)列真值表（见后页）（3）分析结论有效性：由第四行、第八行可知，当前件为真时，结论为真，所以蕴含式成立，结论有效PQRP→→RP∨Q FFFTTF FFTTTF FTFTFT FTTTTT TFFFTT TFTFTT TTFTFT TTTTTT直接证法直接证法Ø 规则P(引入前提规则)：在推理过程中，可以随时 引入前提 Ø 规则T(引入结论规则)：在推理过程中，如果前边 有一个或几个公式永真蕴涵公式S，则可将S纳入推 理过程中推理规则推理规则³³直接直接证证证证法就是由一法就是由一组组组组前提，利用一些公前提，利用一些公认认认认的的推理推理规则规则规则规则 ，根，根据已知的等价或据已知的等价或蕴蕴蕴蕴含公式，推演得到有效的含公式，推演得到有效的结论结论结论结论 。

P ∧ Q  PP,Q  P ∧ Q P ∧ Q  Q¬P, P ∨ Q  QP P ∨ Q P, P → Q   P ∨ Q ¬Q, P → Q  ¬P¬P P → QP → Q, Q → R P → RQ  P → Q P ∨ Q, P → R, Q → R R ¬(P → Q )  P A → B (A∨ C ) →(B ∨ C)¬(P → Q ) ¬QA → B (A ∧ C ) →(B ∧ C)常见的蕴涵规则表常见的蕴涵规则表推理过程中，要应用下面所列出的永真蕴涵式I1-I16和等价公式E1-E22 具体公式见下面请看一些例子¬ ¬P PR ∨ (P ∧ ¬ P) RP∧Q  Q∧PR ∧ (P ∨ ¬ P) RP∨QQ ∨PR ∨ (P ∨ ¬ P) T(P∧Q ) ∧R P ∧(Q ∧ R)R ∧ (P ∧ ¬ P) F(P ∨ Q ) ∨ R P ∨(Q ∨ R)P → Q  ¬ P ∨ Q P ∧(Q ∨ R) (P ∧ Q) ∨ (P ∧ R)¬(P → Q )  P ∧ ¬ Q P ∨(Q ∧ R) (P ∨ Q) ∧ (P ∨ R)P → Q  ¬ Q → ¬ P ¬(P∧Q )  ¬P ∨ ¬ Q P →(Q → R)  (P∧Q ) → R¬(P ∨ Q )  ¬P ∧ ¬ Q P↔Q  (P → Q ) ∧ (Q → P ) P∨P PP↔Q  (P∧Q ) ∨(¬P ∧ ¬ Q )P ∧ P P¬(P↔Q )  P↔¬Q 等价式规则表等价式规则表【example】求证 P→Q，Q→R，P  R ProofProof：：序号 前提或结论 所用规则 从哪几步得到 所用公式(1) P P(2) PQ P (3) Q T (1)(2) I11 (4) Q→R P (5) R T (3)(4) I11（注公式I11为： P,P→Q  Q ）【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)E【【exampleexample】】求证P→(Q→S),R∨P,Q R→S proof:proof: (1) P→(Q→S) P(2) P∨(Q∨S) T (1) E16(3) P∨(S∨Q) T (2) E3(4) (P∨S)∨Q T (3) E5 (5) Q P (6) P∨S T (4)(5) I10(7) P→S T (6) E16(8) R∨P P(9) R→P T (8) E16(10) R→S T (7)(9) I13间接证法间接证法³ 不仅使用P规则，T规则，还是用反证法或CP规则的推理方法 被称为间接证法。

³相容性定义：假设公式H1, H2，…, Hm 中的命题变元为P1, P2, …，Pn，对于P1, P2, …，Pn的一些真值指派，如果能使H1∧H2∧∧Hm的真值为T，则称公式 H1, H2, …，Hm 是相容的如果对于P1, P2, …，Pn的每一组真值指派使得H1∧H2∧∧Hm的真值均为F, 则称公式H1, H2，…, Hm是不相容的我们可把不相容的概念应用于命题公式的证明我们可把不相容的概念应用于命题公式的证明³ 设有一组前提H1, H2，…, Hm 要推出结论C,即证H1∧H2∧∧Hm C，记作SC，即 C → S为永真，或C ∨  S为永真，故 C ∧ S为永假因此要证明H1∧H2∧∧Hm C，只要证明H1, H2，…, Hm与 C 是不相容的³间接证法的另一种情况是：若要证H1∧H2∧∧Hm (R →C)设H1∧H2∧∧Hm为S ，即证S (R →C)或S (R ∨ C)，故S → (R ∨ C)为永真 式因为S → (R ∨ C)   S ∨ (R ∨ C)  (S ∨ R) ∨ C   (S∧R) ∨ C  (S∧R) → C ,所以若将R作附加前提，如有(S∧R)  C 即证得S (R → C).由(S∧R)  C ，证得S (R → C)称为CP规则。

CPCP规则规则注意：³CP规则适用于结论为条件式的有效推理³使用CP规则就是把结论中的浅见作为附加前提加入 前提集合，共同去推出结论的后件example】使用CP规则证法求证P→(Q→S),R∨P,Q R→SProof：(1) R P(附加前提)(2) R∨P P(3) P T (1)(2) I10(4) P→(Q→S) P(5) Q→S T (3)(4) I11(6) Q P(7) S T (5)(6) I11(8) R→S CP【example】用逻辑推理方法证明下面推理的有效性： 如果体育馆有球赛，青年大街交通就拥挤在这种情况下，如果小王不提前出发，就会迟到因此，小王没有提前出发也未迟到，则体育馆没有球赛 Proof： 先将命题符号化：设 P：体育馆有球赛Q：青年大街交通拥挤R：小王提前出发 S：小王迟到则要证：P→Q，(Q∧R)→S (R∧S)→P P→Q，(Q∧R)→S (R∧S)→P proofproof：：(1) R∧S P(附加前提)(2) R T (1) I1(3) S T (1) I2(4) (Q∧R)→S P(5) (Q∧Ｒ) T(3)(4) I12(6) Q∨R T (5) E8 (7) Q T (2)(6) I10(8) P→Q P(9) P T (7)(8) I12(10)(R∧S)→P CP【example】 A→ (B→C), D ∨ A, B  D → C。

Proof：(1) D P(2) D ∨ A P(3) A T(1),(2)I(4) A→ (B→C) P(5) B→C 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（永假式）example】 P→Q, (Q∨R)∧R, (P∧S)   S ProofProof：：(1)  S P(假设前提)(2) S 。