12.5 推理理论授课时间：2学时教学重点：掌握基本蕴涵式，会使用三个推理规则：规则P 、规则T 和规则CP 教学难点：形式证明授课内容：12.5.1 命题的蕴含关系推理是从前提推出结论的思维过程，前提是已知的命题公式，结论是从前提出发应用推理规则得到的命题公式。
从某些给定的前提出发，按照严格定义的形式规则，推出有效的结论，这样的过程称为形式证明或演绎证明。
定义12.5-1 设B A A A k ,,,,21 都是命题公式，若B A A A k →∧∧∧)(21 为重言式，记作B A A A k ⇒∧∧∧)(21 ，则称A 1，A 2，…，A k 能推出结论B ，或称B 是前提集合{A 1，A 2，…，A k }的逻辑结论(Logical consequence)或者有效结论。
同用“B A ⇔”表示“B A ↔”为重言式类似，“B A ⇒”当且仅当“B A →”是重言式。
于是，判断推理是否有效的方法就是判断重言蕴涵式的方法，比如我们前面所讲的真值表法、等值演算和主范式法等。
例12.5-1 判断如下推理是否有效。
如果天气凉快，小王就不去游泳。
天气凉快。
所以小王没有游泳。
解 命题符号化， p ：天气凉快，q ：小王去游泳，前提：p q p ,⌝→结论：q ⌝推理的形式结构：q p q p ⌝⇒∧⌝→))((，要判断其推理是否有效，就是判断q p q p ⌝→∧⌝→))((是否是重言式。
①真值表法：作出q p q p ⌝→∧⌝→))((的真值表如表12.5-1所示。
由其真值表可以看出，最后一列均为1，即q p q p ⌝→∧⌝→))((重言式，所以推理有效。
②等值演算法：q p q p ⌝→∧⌝→))((⇔q p q p ⌝∨∧⌝∨⌝⌝))((⇔q p q p ⌝∨∧∧⌝⌝))((⇔q p q p ⌝∨⌝∨∧))((⇔)()(q p q q p p ⌝∨⌝∨∧⌝∨⌝∨⇔1∧1⇔1。
即q p q p ⌝→∧⌝→))((为重言式。
故推理有效。
③主析取范式法：q p q p ⌝→∧⌝→))((⇔1⇔∑（0，1，2，3）为重言式，故推理是有效的。
在推理过程中，我们也可以应用已经得到的一些基本蕴含关系（或重言蕴涵式）。
8. B A A ∨⇒ 附加2. B A B ∨⇒ 附加3. A B A ⇒∧ 化简4. B B A ⇒∧ 化简5. B A A →⇒⌝6. B A B →⇒7. A B A ⇒→⌝)(8. B B A ⌝⇒→⌝)(9. B A B A ∧⇒, 合取10. B A B A ⇒∧→))(( 假言推理18. A B B A ⌝⇒⌝∧→))(( 拒取式12. B A B A ⇒⌝∧∨)( 析取三段论13. C A C B B A →⇒→∧→)()( 假言三段论14. D B C A D C B A ∨⇒∨∧→∧→)()()( 构造性二难推理12.5.2 形式证明在推理过程中，如果命题变元较多，采用真值表、等值演算和主范式方法有时不方便。
为此介绍形式证明的方法。
形式证明(Formal Proof)的推理过程是一个命题序列，其中每一个命题或者是已知命题，或者是由某些前提根据推理规则推出的结论，序列的最后一个命题是需要论证的结论。
要进行正确的推理，需要使用推理规则，下面给出形式证明中的推理规则：⑴前提引入规则P ：在证明的任何步骤中，都可以引入前提。
⑵结论引入规则T ：在证明的任何步骤中，在此之前证明得到的结论都可以作为后续证明的前提引入。
⑶置换规则：在证明任何步骤中，命题公式中的任何子公式都可以用与之等值的命题公式置换，如可以用q p ∨⌝置换q p →等。
⑷代入规则：在证明的任何步骤中，重言式的任何一个命题变元都可以用一个命题公式代入，得到的仍是重言式。
⑸附加规则： B A A ∨⇒⑹化简规则： A B A ⇒∧表8.6-1⑺假言推理规则： B A B A ⇒→,⑻拒取式规则： A B B A ⌝⇒⌝→,⑼析取三段论规则：B A B A ⇒⌝∨,⑽假言三段论规则：C A C B B A →⇒→→,⑾等价三段论规则：C A C B B A ↔⇒↔↔,⑿构造性二难规则：D B C A D C B A ∨⇒∨→→,,⒀合取引入规则： B A B A ∧⇒,下面我们通过例题来说明如何构造形式证明。
例12.5-2 给出下列的推理的形式证明：q p ∨，r p ⌝→，t s →，r s →⌝，t ⌝⇒q 。
前提：q p ∨，r p ⌝→，t s →，r s →⌝，t ⌝结论：q证明 ①t s → P②t ⌝ P③s ⌝ T ①②拒取式④r s →⌝ P⑤r T ③④假言推理⑥r p ⌝→ P⑦p ⌝ T ⑤⑥拒取式⑧q p ∨ P⑨q T ⑦⑧析取三段论在形式证明的实际应用中，有时候为了使证明过程给人以更清晰的认识，往往在证明后附上证明（推理）树。
例如本题的证明树如图12.5-1所示。
它的作法是，把证明（推理）过程中作为前提的标号作为树叶，每一步用线相连，得到的相应结论的标号作为相应的结点，直到最后一步的结论作为树根。
例12.5-3 写出下面推理的形式证明：如果今天是星期一，则要进行英语或离散数学考试。
如果今天英语老师有会，则不考英语。
今天是星期一，英语老师有会。
所以今天进行离散数学考试。
解 符号化题目中的命题，设p ：今天是星期一，q ：进行英语考试，r ：进行离散数学考试，s ：英语老师有会。
前提：)(r q p ∨→,q s ⌝→,p ,s结论：r证明：①)(r q p ∨→ P②p P③r q ∨ T ①②假言推理④q s ⌝→ P① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨① ② ⑤ ④ ③⑥ ⑦图8.6-1 图8.6-2⑤s P⑥q ⌝ T ④⑤假言推理⑦r T ③⑥析取三段论由有效推理可知，今天进行离散数学考试。
其证明树如图12.5-2所示。
在上面的例子中，采用前面的规则进行形式证明的方法，通常也称为直接证明法。
在形式证明中，有时可采用一定的技巧，使证明过程简化。
CP 规则：证明类似)()(21B A A A A k →⇒∧∧∧ 问题时，我们常采用这种方法。
方法是，将结论中蕴涵前件作为一个附加前提来证明结论中蕴涵式中的后件是有效逻辑结论。
这种方法是可以保证整个推理正确的。
)()(21B A A A A k →→∧∧∧⇔)()(21B A A A A k ∨⌝∨∧∧∧⌝⇔B A A A A k ∨∧∧∧∧⌝)(21⇔B A A A A k →∧∧∧∧)(21根据置换原则可知，上式最后一个式子为重言式与第一个式子为重言式是等价的。
通常我们把这个结论在运用于形式证明时称为CP 规则。
例12.5-4 用形式证明法证明：)(r q p →→，p s ∨⌝，q ⇒r s →前提：)(r q p →→，p s ∨⌝，q结论：r s →证明 ①s 附加前提引入②p s ∨⌝ 前提引入③p ①②析取三段论④)(r q p →→ 前提引入⑤r q → ③④假言推理⑥q 前提引入⑦r ⑤⑥假言推理⑧r s → ①⑦CP 规则间接证明法--归谬法。
归谬法是将结论的否定作为一前提引入，通过有效推理得到矛盾，以此说明推理正确。
先补充一个概念：设A 1，A 2，…，A k 是k 个命题公式，若A 1∧A 2∧…∧A k 是可满足式，则称A 1，A 2，…，A k 是相容的，否则，即A 1∧A 2∧…∧A k 为矛盾式则称A 1，A 2，…，A k 是不相容的。
因B A A A k →∧∧∧)(21⇔B A A A k ∨∧∧∧⌝)(21⇔)(21B A A A k ⌝∧∧∧∧⌝所以，若A 1，A 2，…，A k ，B ⌝不相容，则说明B A A A k →∧∧∧)(21 是重言式，即B 是公式A 1，A 2，…，A k 的逻辑结论，故应用这种方法推理构造有效。
例12.5-5 用间接证明法证明：))((q s r p ⌝→∧⌝→，p ，s ⌝⇒q ⌝前提：))((q s r p ⌝→∧⌝→，p ，s ⌝结论：q ⌝证明 ①))((q s r p ⌝→∧⌝→ P②p P③q s r ⌝→∧⌝)( T ①②假言推理④)(q ⌝⌝ P 否定结论引入⑤s r ∧ T ③④拒取式⑥s T ⑤化简⑦ s ⌝ P⑧s s ∧⌝ T ⑥⑦合取由⑧得到矛盾，根据归谬法可知推理正确。
作业：1. 形式证明给出下列推理的过程的形式证明。
⑴s p s q p ,,→→⇒q⑵s p q r q p →⌝→⌝→,,⇒s r →⑶s r r q q p ∧⌝→→,,⇒p ⌝⑷q r q p ⌝→∨⌝,⇒r p ⌝→⑸前提：)(,)(),(t s h t s r r q p ⌝∧→⌝→∧→→结论：)(h q p →→。
2.下面的推理过程是否正确，结论是否有效，并说明理由。
①r q p →∧ P 前提引入②r p → T ①化简③p P 前提引入④r T ②③假言推理3. 判断下面的推理证明过程是否正确，若不正确请指出错误所在位置及出错原因，若正确则请补足每一步所用的推理规则。
前提：r p s q r p ,),(∨⌝→→结论：q s →证明：①p s ∨⌝ ⑴②s ⑵③p ⑶④)(q r p →→ ⑷⑤q r → ⑸⑥r ⑹⑦q ⑺⑧q s → ⑻4. 用推理规则证明下列推理的正确性：如果张三努力工作，那么李四或王五感到高兴；如果李四感到高兴，那么张三不努力工作；如果刘强高兴，那么王五不高兴。
所以，如果张三努力工作，则刘强不高兴。
