计算机数学基础4

1、5、间接证法1） CP规则：有时要证的结论以蕴含的形式出现。要证A1A2AmBC。如果把结论中的前件B作为附加条件加入前提集合中，即证出了A1A2AmBC，则原来要证的结论成立。称之为附加前提证明法。简称CP规则。证明：A1A2AmBC A1A2AmBC证明：A1A2AmBC A1A2Am (BC)( A1A2Am)(BC)( A1A2Am)B)C( A1A2Am B)C( A1A2Am B)CCP规则成立。例6：试证(P(QS)(RP)QRS前提公式集合P(QS), RP, Q, 结论RS将结论RS中的前项R引入前提集合，而去演绎出S。证明：(1)RP规则P(2)R规则P(附加前提)(3)P

2、规则T由(1) (2) (析取三段论)(4) P(QS) 规则P(5)QS规则T由(3) (4) (假言推理)(6)Q规则P(7)S规则T由(5) (6) (假言推理)(8) RS规则CP例：证明AB，BC，CD逻辑的推出AD证法1：用CP规则(1)AB规则P(2)A规则P(附加前提)(3)B规则T由(1) (2) (析取三段论)(4)BC 规则P(5)C规则T由(3) (4) (析取三段论)(6) CD规则P(7)D规则T由(5) (6) (假言推理)(8)AD规则CP证法2：不用CP规则(1)AB规则P(2)AB规则T由(1)(蕴含律)(3)BC 规则P(5)AC规则T由(2) (4) (

3、假言三段论)(4)BC 规则T由(3)(蕴含律)(6)CD规则P(7)AD规则T由(5) (6) (假言三段论)2)归谬法设A1，A2，Am是命题公式，如果A1A2Am是可满足的，称A1，A2，Am是相容的。如果A1A2Am是矛盾式，称A1，A2，Am是不相容的。理论根据A1A2AmC( A1A2Am)C( A1A2AmC)则A1A2AmC，即A1A2AmC为重言式，A1A2AmC是矛盾式。从而得到如A1，A2，Am，C不相容，则C是A1，A2，Am的有效结论。因此我们可以把C作为附加前提推出矛盾来，从而可以得到C是A1，A2，Am的有效结论。这种方法称为归谬法，也就是我们通常说的反证法。例7

4、：是证明(RQ)(RS)(SQ)(PQ)P证明：(1) PQ规则P(2)P规则P(附加前提)(3)Q规则T由(1) (2) (假言推理)(4) RQ 规则P(5)R规则T由(3) (4) (拒取式)(6) SQ规则P(7)S规则T由(3) (6) (拒取式)(8) RS规则T由(4) (7) (合取引入)(9)(RS)规则T由(8) (德.摩根律)(10) RS规则P(11) (RS)(RS)规则T由(9) (10) (合取引入)(12) (RS)(RS)是矛盾式，所以P为前提公式的有效结论1.7自我练习1：求命题公式(P(PQ)R的真值表自我练习2：求(PQR)(PQR)的主析取范式。解：原公式(P(QR)(P(QR)(PP)(PQR)(QRP)(QRQR)0(PQR) (PQR)00(PQR) (PQR)m0m7(0,7)自我练习3：(AB)C)(B(DC)(B(DA)C证明：左边(AB)C)(B(DC)(ABC)(BCD)右边(B(DA)C(B(DA)C (ABC)(BCD)所以左边右边自我练习4：构造下面推理证明前提：(PQ),QR,R结论：P证明：(1)QR 规则P(2)R规则P(3)Q规则T由(1)(2)(析取三段论)(4)(PQ)规则P(5)PQ规则T由(3)(德.