离散数学(1.8推理理论)

1离散数学(DiscreteMathematics)2第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)1.8.1常用的证明方法1.8.2真值表法

(TruthTable)1.8.3直接证法

(DirectProof)1.8.4间接证法

(IndirectProof)3第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)

1.8.1常用的证明方法定义1.8.1

：设Ａ和Ｃ是两个命题公式,当且仅当ＡＣ为一重言式，即ＡＣ,称Ｃ是Ａ的有效结论;或称Ｃ可由Ａ逻辑推出.一般地,如果有n个前提H1,H2,H3,.…,Hn

,

若H1H2H3....HnC,则称C是一组前提H1,H2,…,Hn的有效结论。注意:在形式逻辑中,我们并不关心结论是否真实,而主要关心结论是否可以由给定的前提推出来,我们只注意推理的形式是否正确.因此,有效结论并不一定是正确的,只有正确的前提经过正确的推理得到的逻辑结论才是正确的.4第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)证明C是A的有效结论的方法就是判别重言蕴含的方法.前面我们介绍的论证方法有真值表法、等值演算法、主析（合）取范式法。论证方法千变万化，但最基本、最常用的方法有三种：推理证明的方法5第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)1.8.2真值表法

(TruthTable)构造命题公式H1∧

H2∧……∧

Hn→C的真值表，若为永真，H1∧

H2∧……∧

HnC推理正确。例：证明((P∨Q)∧┐Q)PPQP∨Q┐Q(P∨Q)∧┐Q((P∨Q)∧┐Q)P0001010110011011111110016第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)由上面真值表可知((P∨Q)∧┐Q)P。1.8.3直接证法

(DirectProof)直接证法：由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式推演得到有效结论。常用的推理规则P规则:（也称前提引入规则）前提在推导过程中的任何时候都可以引用。T规则:在推导过程中，所证明的结论、已知的等价或蕴含公式都可以作为后续证明的前提，命题公式中的任何子公式都可以用与之等价的命题公式置换。7第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)常用的蕴含式和等价式见课本P43表1-8.3、1-8.4例1.如果考试及格，那我高兴。若我高兴，那么我饭量增加。我的饭量没增加，所以我考试没有及格。试对上述论证构造证明。解：设P：我考试及格.Q：我高兴。R：我饭量增加。则此论证可表为(P→Q)(Q→R)┐R┐P

证:8第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)常用的蕴含式和等价式见课本P43表1-8.3、1-8.4例1.如果考试及格，那我高兴。若我高兴，那么我饭量增加。我的饭量没增加，所以我考试没有及格。试对上述论证构造证明。解：设P：我考试及格.Q：我高兴。R：我饭量增加。则此论证可表为(P→Q)(Q→R)┐R┐P

证:1P→Q P2Q→R P3┐R P4┐Q T，2，3I125┐P T，1，4I129第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)例2.证明RS是前提CD，C→R,D→S的有效结论。

证：10第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)例2.证明RS是前提CD，C→R,D→S的有效结论。

证：1.CDP2.C→RP 3.D→SP4.┐C→DT，1E5.┐R→┐CT，2E6.┐R→ST，5，4，3I13

7.RST，6E11第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)例3：证明:P∨Q,QR,PS,┐SR∧(Q∨P)

证：12第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)例3：P∨Q,QR,PS,┐SR∧(Q∨P)

证明：1.PSP(前提引入)2.┐SP(前提引入)3.┐PT1,2I114.P∨QP(前提引入)5.QT3,4I116.QRP(前提引入)7.RT5,6I118.R∧(Q∨P)T4,7I913第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)例4：证明(P（Q∨R))∧(┐S

┐Q)∧(P∧┐S)R.证：14第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)例4：证明(P（Q∨R))∧(┐S

┐Q)∧(P∧┐S)R.证：（1）P∧┐SP（2）PT（1）I1（3）┐ST（1）I1（4）P（Q∨R)

P（5）Q∨RT(2)，(4)I11（6）┐S

┐Q

P（7）┐Q

T(3)，(6)I11（8）RT(5)，(7)I1115第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)1.8.4间接证法

(IndirectProof)附加前提证明法适用于如下类型蕴含式的证明:

(A1∧A2∧…∧Ak)(AB)(*)

欲证明(*)式，只需证明

(A1∧A2∧…∧Ak∧A)B即可，因为16第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)(A1∧A2∧…∧Ak)(AB)┐(A1∧A2∧…∧Ak)∨

(AB)┐(A1∧A2∧…Ak)∨

(┐A∨B)

(┐A1∨┐A2∨…∨┐Ak)∨

(┐A∨B)

┐A1∨┐A2∨…∨┐Ak∨┐A∨B

(┐A1∨┐A2∨…∨┐Ak∨┐A)∨B

┐(A1∧A2∧…∧Ak∧A)∨B(A1∧A2∧…∧Ak∧A)

B这样一来,原来结论中的前件A就变成了前提,称A为附加前提.

17第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)由证(A1∧A2∧…∧Ak∧A)B永真而证得(A1∧A2∧…∧Ak)(AB)永真的证明方法,称为附加前提证明法或CP规则.18第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)例1:证明:(A→BC)(B→┐A)(D→┐C)(A→┐D)证： 19第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)例1:证明:(A→BC)(B→┐A)(D→┐C)(A→┐D)证：1.A→BCP2.B→┐AP3.D→┐CP4.AP(附加前提) 5.BCT1，4I11 6.A→┐BT2,E 7.C→┐DT3，E8.┐BT4，6I119.CT5，8I11 10.┐DT7，9I11 11.A→┐DＴ４，10CP 20第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)

例2：前提：P(QR),SP,Q结论：SR.证明：21第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)

例2：前提：P(QR),SP,Q结论：SR.证明：1.SPP2.SP（附加前提引入）3.PT（1,2）I114.P(QR)P5.QRT（3,4）I116.QP7.RT（5,6）I118.SRT（2,7）CP22第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)2.归谬法定义1.8.2：设命题公式集合为{H1,H2,H3,.…,Hn}，若H1H2H3....Hn为永假式，则称{H1,H2,H3,.…,Hn}是不相容的，否则称为相容的。由于(A1∧A2∧…∧Ak)B┐(A1∧A2∧…∧Ak)∨B┐(A1∧A2∧…Ak∧┐B)故要证(A1∧A2∧…∧Ak)B永真,只需证A1∧A2∧…Ak∧┐B永假.这种将┐B作为附加前提推出矛盾的证明方法称为归谬法.23第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)例1:证明(P┐Q)∧(┐R∨Q)∧(R∧┐S)┐P证：24第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)例1:证明(P┐Q)∧(┐R∨Q)∧(R∧┐S)┐P证：1.

PP(附加前提)2.P┐Q

P3.┐Q

T(1,2)I114.┐R∨Q

P5.┐RT(3,4)I116.R∧┐SP7.RT(6)I18.R∧┐R(矛盾）T(5,7)由8得出了矛盾,根据归谬法说明原推理正确.25第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)例2:从PQ→RS,(T→Q)(S→U),┐R,(W→P)(T→U)推出W→┐T证：26第一章命题逻辑（PropositionalLogic）

1.8推理理论(InferenceTheory)例2:从PQ→RS,(T→Q)(S→U),┐R,(W→P)(T→U)推出W→┐T证：1.PQ→RSP2.(T→Q)(S→U)P3.(W→P)(T→U)P4.┐RP5.WP(附加前提) 6.┐R∨┐S T4I

7.┐(RS)T6E8.┐(PQ)T1，7I11 9.(W→P)T3,I

10.PT5，9I11.┐P∨┐QT8,E12.┐QT10，11I11 13.T→QT2I1114.┐TT12，13I1115.W→┐TＴ５,15CP27第一章命题逻辑（PropositionalLogic）

1.8推理理论(Infe