第三章 3.3 3.4 3.5 条件、间接、重言证明规则.ppt

3.3 条件证明规则,3.3.1 什么是条件证明规则,¬R∨S∴ R→R∧S,该论证是有效的（用真值表可以证明）遗憾的是，只用目前为止的18条规则，并不能构造该论证的有效性证明 为了使命题逻辑的证明系统完全，需要增加“条件证明规则”没有这条规则，我们将不能构造许多有效论证的证明而且它也极大地简化了许多证明，这些证明原则上如果没有条件证明是不能实现的¬R∨S∴ R→R∧S,（1）该推论是有效的，当且仅当，它的前提真时，结论不可能为假2）而结论是一个蕴涵式——一个蕴涵式不可能为假，即前件真时，后件不可能为假3）那么，现在就将前件R当成一个假设，如果能够由前提和这个添加的假设有效地推出结论的后件R∧S，即是说明： 在原来的前提下，当R真时， R∧S不可能假 也即是说明： 当原有前提¬R∨S真时，原结论R→R∧S不可能是假的符合有效性的概念）——有效性由此得到证明基本思路,如果从前提集合a和非前提命题b出发，能够推导出命题c，则可从a推导出b →c如果结论是一个蕴涵式，就将此式的前件作为假设，看是否能依据规则推出后件P1 P2 P3 Pr (前提) … Pn ∴ p →q （结论）,,Pr p∴ q 结论,,前提,（Pr→（p →q）） ↔ （Pr ∧p →q）,,Pr p . . . q ∴ p → q,,,P1 P2 P3 … Pn ∴ p →q,,,,,假设域,,框起来表示引入假设，又撤销假设。

框住的部分仅仅表示在p为真的假设下q是真的所以：在Pr为真的前提下，p →q不可能假该论证有效Pr,,¬R∨S∴ R→R∧S,(1) ¬R∨S ∴ R→R∧S (2) R 条件证明假设（条假） (3) ¬ ¬R （2）双否 (4) S （1）（3）否析 (5) R∧S （2）（4）合取 (6) R→R∧S （2）--（5）条件证明,,,,(1) C∨ (A∨B) (2) C∨K→D ∴ ¬A→(¬B→C∧D),(3) ¬A 条假 (4) ¬B 条假 (5) ¬A ∧¬B (3)(4)合取 (6) ¬ (A∨B) (5)德摩根 (7) C (1)(6)否析 (8) C∨K (7)附加 (9) D (2)(8)肯前 (10) C∧D (7)(8)合取 (11) ¬B→C∧D (4)--(10)条证 (12) ¬A→(¬B→C∧D) (3)--(11)条证,,,,,,,(1) C∨ (A∨B) (2) C∨K→D ∴ ¬A→(¬B→C∧D),(1) (T ∧H) ∨R (2) T→F (3) R→(F→(¬ F∧ ¬ R)) ∴ ¬ F ↔ R,(4) ¬ F 条假 (5) ¬T (2)否后 (6) ¬T ∨ ¬H (5)(6)合取 (7) ¬ (T∧H) (6)德摩根 (8) R (1)(7)否析 (9) ¬ F → R (4)--(8)条证 (10) R 条假 (11) F→(¬ F∧ ¬ R) (3)肯前 (12) ¬ F∨(¬ F∧ ¬ R) (11)蕴涵 (13) (¬ F∨¬ F) ∧(¬ F∨ ¬ R) (12)分配 (14) ¬ F∨¬ F (13)化简 (15) ¬ F (14)重言 (16) R → ¬ F (10)--(15)条证 (17) (¬ F → R)∧(R → ¬ F) (9)(16)合取 (18) ¬ F ↔ R (17)等值,,,,(1) (T ∧H) ∨R (2) T→F (3) R→(F→(¬ F∧ ¬ R)) ∴ ¬ F ↔ R,,,,(1) S ∨P (2) S→O∧R (3) P→(¬ P∨T) ∴ O∨T,(4) ¬ O 条假 (5) ¬O ∨ ¬R (4)附加 (6) ¬ (O∧R) (5)德摩根 (7) ¬ S (2)(6)否后 (8) P (1)(8)否析 (9) ¬ P ∨ T (3)(8)肯前 (10) ¬ ¬ P (8)双否 (11) T (9) (10)否析 (12) ¬ O → T (4) --(11)条证 (13) ¬ ¬ O ∨T (12)蕴涵 (14) O∨T (13)双否,,,(1) S ∨P (2) S→O∧R (3) P→(¬ P∨T) ∴ O∨T,,,3.4 间接证明规则,证明p，就假定¬p，从¬p推出矛盾的结果。

Pr ¬ p . . . q ∧¬q ∴ p,,,,,间接假设：归谬法和排中律注意：间接证明规则和条件证明规则不同在于它不是必须的，其作用仅在于简化证明过程 详见P93,（1）R→¬S∧T（2）T∨(R∧¬S) ∴ T,（1）P ∨ Q→R（2）¬(R∧¬S) (3) ¬P →T ∴ T ∨S,（1） P ∨ Q→R（2） ¬(R∧¬S) (3) ¬P →T ∴ T ∨S,(4) ¬ (T ∨S) 间假 (5) ¬ T ∧ ¬ S (4)德摩根 (6) ¬ T (5)化简 (7) ¬ ¬ P (3)(6)否后 (8) P (7)双否 (9) P ∨ Q (8)附加 (10) R (1)(9)肯前 (11) ¬ S (5)化简 (12) R ∧ ¬ S (10)(11)合取 (13) (R ∧ ¬ S) ∧ ¬(R∧¬S) (12)(2)合取 (14) T ∨S (4)-(13)间证,,,,(1) (M→R)→(K→¬B) (2) ¬(¬K∨I)→R (3) ¬ K →I ∴ B →I,(4) B 条假 (5) ¬I 间假 (6) ¬¬K (3)(5)否后 (7) ¬ ¬K ∧ ¬I (5) (6)合取 (8) ¬(¬K ∨I ) (7)德摩根 (9) R (2)(8)肯前 (10) ¬ M∨ R (9)附加 (11) M→R (10)蕴涵 (12) K→¬B (1) (11)肯前 (13) K (6)双否 (14) ¬ B (12)(13)肯前 (15) B∧¬ B (4)(14)合取 (16) I (5) -(15)间证 (17) B → I (4)-(16)条证,。