Email：fws365@scu.edu.cn 2017年3月18日星期六 离散　　数学 计算机学院 冯伟森 Email：fws365@scu.edu.cn 2017年3月18日星期六.

Presentation on theme: "Email：fws365@scu.edu.cn 2017年3月18日星期六 离散　　数学 计算机学院 冯伟森 Email：fws365@scu.edu.cn 2017年3月18日星期六."— Presentation transcript:

1 Email：fws365@scu.edu.cn 2017年3月18日星期六
离散　　数学 计算机学院 冯伟森 2017年3月18日星期六

2 主要内容 1、推理的基本概念和推理形式 2、推理规则 1）P规则 2）T规则 3）CP规则 2017/3/18 计算机学院

3 §1．7 命题逻辑的推理方法 命题演算的一个主要任务在于提供一种正确的思维规律，即推理规则，应用此规则从一些前提中推导出一个结论来，这种推导过程称为演绎或形式证明。 定义1.19 设A1,A2,…,An,B是公式,如果 A1,A2,…,AnB 则称B是 A1,A2,…,An 的逻辑结果（有效结论）。 也可以说由A1,A2,…,An推出结论B。 2017/3/18 计算机学院

4 定义1.20 设G是由一组命题公式组成的集合，如果存在命题公式的有限序列：
在更一般意义上，我们有下述定义 定义 设G是由一组命题公式组成的集合，如果存在命题公式的有限序列： A1，A2，……，An（=B） 其中，Ai（i<n-1）或者是G中的某个公式，或者是前面的某些Aj（j<i）的有效结论，并且An就是B，则称公式B是G的逻辑结果（有效结论），或者称由G演绎出结论B来。 2017/3/18 计算机学院

5 公式B是公式集合G＝{A1,A2,…,An}的逻辑结果当且仅当A1∧A2∧…∧An→B为永真公式。
我们有下述结论： 公式B是公式集合G＝{A1,A2,…,An}的逻辑结果当且仅当A1∧A2∧…∧An→B为永真公式。 2017/3/18 计算机学院

6 解释 1) 这里需要特别注意的是：推理的有效性和结论的真实性是不同的，有效的推理不一定产生真实的结论；而产生真实结论的推理过程未必是有效的，因为有效的推理中可能包含为“假”的前提，而无效的推理却可能包含为“真”的前提。 2017/3/18 计算机学院

7 2) 由此可见，推理的有效性是一回事，前提与结论的真实与否是另一回事。所谓推理有效，指的是它的结论是在它的前提下合乎逻辑的结果。也即，如果它的前提都为真，那么所得的结论也必然为真，而并不是要求前提或结论一定为真或为假，如果推理是有效的话，那么不可能它的前提都为真时，而它的结论为假。 2017/3/18 计算机学院

8 推理规则 在数理逻辑中，主要的推理规则有： ① P规则（称为前提引用规则）：在推导的过程中，可随时引入前提集合中的任意一个前提；
② Ｔ规则（逻辑结果引用规则）：在推导的过程中，利用基本等价式和蕴涵式，由证明过程中某些中间公式变换出新的公式，若依据的是等价式，规则标明为TE，若依据的是蕴涵式，规则标明为TI 。 2017/3/18 计算机学院

9 推理规则 ③ ＣＰ规则（附加前提规则）：如果能从给定的前提集合G与公式P推导出S，则能从此前提集合G推导出P→S。
即 G1,G2,…,Gn P→S 当且仅当 G1,G2,…,Gn，P S 2017/3/18 计算机学院

10 推理方法 1.真值表法 根据前提A1,A2,…,An和结论B,构造条件式（A1∧A2∧…∧An）→B的真值表,若它为永真式，则结论B是有效的。 真值表法原则上可以解决推理的有效性问题，但当出现在公式中的命题变元数目很大时，此法显得不切实用，且烦琐乏味，对培养逻辑推理能力及训练推理技巧毫无帮助。 2017/3/18 计算机学院

11 演绎法是从前提（假设）出发，依据公认的推理规则，推导出一个结论来。
2、演绎法 演绎法是从前提（假设）出发，依据公认的推理规则，推导出一个结论来。 1）直接法 2）利用CP规则 3、间接证明法（反证法） 2017/3/18 计算机学院

12 直接证明法 例1-7．1 求证S∨R是前提{P∨Q，P→R，Q→S}的有效结论。(构造性二难推论) 证：步骤 公式 依据（注释）
证：步骤 公式 依据（注释） ① P∨Q P ② ～P→Q T，①，E1，E2 ③ Q→S P ④ ～P→S T, ②, ③,I9 ⑤ ～S→P T，④，E14，E23 ⑥ P→R P ⑦ ～S→R T，⑤，⑥，I9 ⑧ S∨R T，⑦，E2，E1 故 {P∨Q，P→R，Q→S}  S∨R 2017/3/18 计算机学院

13 利用CP规则 例1-7．2 证明R→S可以从前提 {P→（Q→S），～R∨P，Q}推出 证：① R P（附加前提） ② ～R∨P P
③ P T，①，②，I8 ④ P→（Q→S） P ⑤ Q→S T，③，④，I5 ⑥ Q P ⑦ S T，⑥，⑤，I5 ⑧ R→S CP，①，⑦ 2017/3/18 计算机学院

14 间接证明法（反证法） 根据蕴涵关系的性质8， A  B iff A∧～B是矛盾式
将结论的否定加入到前提集合中构成一组新的前提，然后证明这组新的前提集合是不相容的，即蕴涵一个矛盾式。 即，若 A1,A2,…,An, ～B  R∧～R 则 A1,A2,…,An  B 2017/3/18 计算机学院

15 例1-7．3 证明：{R→～Q，R∨S，S→～Q，P→Q}～P 证：① ～（～ P） P（假设前提） ② P T，①，E1 ③ P→Q P
④ Q T, ②, ③,I5 ⑤ S→～Q P ⑥ ～S T，④，⑤，I23，E1 ，I5 ⑦ R∨S P ⑧ R T，⑥，⑦，I7 ⑨ R→～Q P ⑩ ～Q T，⑧，⑨，I5 ⑾ Q∧～Q F，④，⑩ Ｅ19 ∴ {R→～Q，R∨S，S→～Q，P→Q}～P 2017/3/18 计算机学院

16 例1-7．4 把命题“如果小王不去，小张或小李就要去；如果小李去，小王就一定要去；此外，如果小林也去，小张就不愿去；因此，如果小王不去，小林也不会去”翻译成命题逻辑形式并证明命题是真的。 解： 令 P：小王去；Q：小张去； R：小李去；S：小林去； 则命题翻译成如下推理问题： ～P→(Q∨R),R→P,S→～Q～P→～S。 2017/3/18 计算机学院

17 利用CP规则证明 证： ① ～P P（附加前提） ② ～P→(Q∨R) P ③ Q∨R T①，②I5 ④ ～Q→R T③E1，E2 ⑤ R→P P ⑥ ～Q→P T④，⑤I9 ⑦ S→～Q P ⑧ S→P T⑥，⑦I9 ⑨ ～S T①，⑧I9，E1 ⑩ ～P→～S CP①，⑨ 2017/3/18 计算机学院

18 消解法（原理）(归结推理法) 利用规则推理有很大的随意性，不易机械执行，归结推理法是仅有一条推理规则的机械推理法,容易以程序实现，是定理机器证明的重要方法。是反证法的特殊情况。 根据基本蕴涵式I8（析取三段论） 即 P，～P∨Q  Q 和基本蕴涵式I13（归结原理） （P∨Q ）∧（～P∨R） Q∨R 2017/3/18 计算机学院

19 消解规则（归结式定义） 设C1=L∨C1′, C2=～L∨C2′是两个子句，有互补对L和～L，则新子句 R（C1,C2)=C1′∨C2′
为了证明 A1,A2,…,An  B 根据反证法，即需证明 A1,A2,…,An,～B  R∧～R 利用消解规则进行推理，其过程为： 1）从{A1,A2,…,An,～B }出发。 2017/3/18 计算机学院

20 2） 将A1∧A2∧…∧An∧～B转化成合取范式，如 P∧（P∨R）∧（～P∨Q）∧（～P∨R）的形式
3） 将合取范式中的所有子句（析取式）构成子句集合S，如 S={P，P∨R，～P∨Q，～P∨R} 4） 对S使用消解规则 对S的子句作归结，即消除互补式（互反对），如子句P∨R与～P∨Q作归结，得归结式R∨Q并将这归结式仍放S中，重复这一过程。 5） 直至归结出矛盾式 (称为空子句，记为□) 2017/3/18 计算机学院

21 因此，其消解过程就是对S的子句求消解式的过程。 R（C1,C2)=C1′∨C2′仅三种情况: ① C1=A∨B，C2= ～A∨D，
则（（A∨B），（～A∨D）） B∨D ② C1=A，C2=～A∨B 则（A,～A∨B) B ③ C1=A，C2= ～A 则（A，～A） F (□) 消解方法的机械性是很明显的，其复杂性就是怎样寻找包含互反句节的子句。不同的寻找方式就产生了各种方式的消解算法。 2017/3/18 计算机学院

22 例1-7．5 如果公司的利润高，那么公司有个好经理或它是一个好企业及大体上是个好的经营年份。现在的情况是：公司的利润高,不是一个好的经营年份。要证明，公司有个好经理。 解：设A：公司的利润高 B：公司有个好经理 C：公司是个好企业 D：大体上是个好的经营年份 则原题可符号化为： （A(B∨（C∧D））∧A∧～D B 2017/3/18 计算机学院

23 S={～A∨B∨C，～A∨B∨D，A，～D，～B} 归结过程（消解步骤）
P1:A(B∨（C∧D））  ～A∨（B∨（C∧D）） ～A∨（（B∨C）∧（B∨D）） （～A∨B∨C）∧（～A∨B∨D） P2: A P3: ～D S={～A∨B∨C，～A∨B∨D，A，～D，～B} 归结过程（消解步骤） 2017/3/18 计算机学院

24 （1） ～A∨B∨C P 引用子句 （2） ～A∨B∨D P （3） A P （4） ～D P （5） ～B P
（8） FLASE □ 由（5）,（7）归结 导出空子句 2017/3/18 计算机学院

25 基本要求 深刻理解蕴涵的定义和基本性质 牢记基本蕴涵式的名称及它们的内容 深刻理解三条推理规则 熟练掌握几种常用的推理方法 1）直接法
2）利用CP规则 3）间接证明法（反证法） 2017/3/18 计算机学院

26 习题一 20（2）（4）、21（2）、 22、23（1） 2017/3/18 计算机学院