第三章命题逻辑的推理理论课件.ppt

1、2023-2-111第三章第三章 命题逻辑的推理理论命题逻辑的推理理论2023-2-1123.1 推理的形式结构推理的形式结构所谓所谓推理推理是指从前提出发推出结论的思维过程是指从前提出发推出结论的思维过程.本节所要研究的内容是以什么样的形式来进行本节所要研究的内容是以什么样的形式来进行推理推理,什么样的推理过程才是正确的推理过程什么样的推理过程才是正确的推理过程,也也就是说什么样的推理才是有效的推理就是说什么样的推理才是有效的推理.2023-2-1133.1 推理的形式结构推理的形式结构定义定义3.1 设设A1,A2,Ak,B都是命题公式，若对于都是命题公式，若对于A1,A2,Ak,B中出现

2、的命题变项的任意一组赋值，中出现的命题变项的任意一组赋值，或者或者A1A2 Ak为假，或者当为假，或者当A1A2 Ak为真时，为真时，B也为真，则称由前提也为真，则称由前提A1,A2,Ak推推出出B的推理是有效的或正确的，并称的推理是有效的或正确的，并称B是有效的结是有效的结论。论。2023-2-1143.1 推理的形式结构推理的形式结构关于定义关于定义3.1的说明：的说明：（1）由前提）由前提A1，A2，Ak 推推 B 的推理的推理 记作记作A1，A2，AkB,称为推理的形式结构。称为推理的形式结构。若推理正确，记作若推理正确，记作A1，A2，Ak|=B，否则：记作否则：记作A1，A2，Ak

3、|B。2023-2-1153.1 推理的形式结构推理的形式结构(2)对于任一组赋值，前提和结论的取值有以下四种情对于任一组赋值，前提和结论的取值有以下四种情况：况：A1，A2，Ak为为0，B为为0。A1，A2，Ak为为0，B为为1。A1，A2，Ak为为1，B为为0。A1，A2，Ak为为1，B为为1。结论结论:情况下的推理是正确的情况下的推理是正确的.情况下的推理是错误的情况下的推理是错误的.2023-2-1163.1 推理的形式结构推理的形式结构（3）推理正确）推理正确,并不能保证结论并不能保证结论B一定为真一定为真,这与数这与数学上的推理是不同的学上的推理是不同的.判断下列推理是否正确判断下

4、列推理是否正确(1)p,pqq(2)p,qpq2023-2-1173.1 推理的形式结构推理的形式结构p q 0 00 11 01 1p(pq)qp(qp)q0 00 10 01 10 00 11 01 1结论结论:(1)式正确式正确.(2)式推理不正确式推理不正确.2023-2-118 定理定理3.1 命题公式命题公式A1，A2，Ak 推推 B 的推理正确当的推理正确当且仅当且仅当(A1 A2 Ak)B为重言式。为重言式。（证明参见课本）（证明参见课本）本书中本书中,一般采用一般采用(A1 A2 Ak)B作为推作为推理的形式结构理的形式结构,并且把它写成下面的形式并且把它写成下面的形式.前提

5、：前提：p,p q 结论：结论：q推理的形式结构推理的形式结构：(p(p q)q2023-2-119 只要证明蕴涵式只要证明蕴涵式(p(p q)q为重言式即可。为重言式即可。三种方式证明：三种方式证明：真值表、真值表、等值演算、等值演算、主析取范式主析取范式。例：判断下列推理是否正确。例：判断下列推理是否正确。1、今天小李或去网吧或去教室。他没去教室，所以、今天小李或去网吧或去教室。他没去教室，所以他去网吧了。他去网吧了。设设 p：小李去网吧。：小李去网吧。q：小李去教室。则：小李去教室。则前提：前提：p q,q结论：结论：p推理的形式结构推理的形式结构：(p q)q)p2023-2-1110

6、pqpq q(pq)q(pq)q)p000101011001101111111001（1）真值表）真值表2023-2-1111（2）等值演算法：）等值演算法：(pq)q)p (p q)(q q)p(p q)p (p q)p pq p 1所以，推理正确，即所以，推理正确，即(pq)q)p2023-2-1112（3）主析取范式法：）主析取范式法：(p q)q)p (p q)q)p (p q)q p(p q)q p(p q)q(p p)p(q q)(p q)(qp)(q p)(pq)(p q)m0 m1 m2 m3 所以，推理正确，即所以，推理正确，即(pq)q)p2023-2-1113例：判断下列

7、推理是否正确。例：判断下列推理是否正确。2 2、若、若a a能被能被4 4整除，则天下雨。现在天下雨，所以整除，则天下雨。现在天下雨，所以a a能能被被4 4整除。整除。设设 p：a能被能被4整除。整除。q：天下雨。则，：天下雨。则，前提：前提：p q,q 结论：结论：p 推理的形式结构推理的形式结构：(p q)q)p答案：答案：此推理不正确此推理不正确 2023-2-11143、若下午气温超过、若下午气温超过30 C，则王小燕必去游泳。若她，则王小燕必去游泳。若她去游泳，她就不去看电影了。所以，若王小燕没去去游泳，她就不去看电影了。所以，若王小燕没去看电影，下午气温必超过了看电影，下午气温必

8、超过了30 C。p：下午气温超过：下午气温超过30 Cq：王小燕去游泳：王小燕去游泳r：王小燕去看电影：王小燕去看电影前提：前提：p q，q r结论：结论：r p形式结构：形式结构：(p q)(q r)(r p)2023-2-1115w推理定律推理定律1.附加律附加律 A (A B)2.化简律化简律 (A B)A3.假言推理假言推理 (AB)A B4.拒取式拒取式 (AB)B A5.析取三段论析取三段论 (A B)B A6.假言三段论假言三段论 (AB)(BC)(AC)7.等价三段论等价三段论 (A B)(B C)(A C)2023-2-11168.构造性二难构造性二难 (AB)(CD)(AC

9、)(BD)(特殊形式特殊形式)(AB)(AB)(A A)B 9.破坏性二难破坏性二难 (AB)(CD)(B D)(A C)判断推理是否正确，上述三种方法演算量太大，判断推理是否正确，上述三种方法演算量太大，故而应给出严谨的证明。证明是一个描述推理过程故而应给出严谨的证明。证明是一个描述推理过程的命题公式的序列，其中的每个公式或者是已知前的命题公式的序列，其中的每个公式或者是已知前提，或者由某些前提应用推理规则得到的结论提，或者由某些前提应用推理规则得到的结论.要构要构造出严谨的证明必须在形式系统中证明。造出严谨的证明必须在形式系统中证明。2023-2-11173.2 自然推理系统P定义定义3.

10、2 一个一个形式系统形式系统 I 由下列四个部分组成：由下列四个部分组成：（1）非空的字母表集，记作）非空的字母表集，记作A（I）。）。（2）A(I)符号构造的合式公式集，记作符号构造的合式公式集，记作E(I)。（3）E(I)中一些特殊的公式组成的公理集中一些特殊的公式组成的公理集,记作记作AX(I)。（4）推理规则集，记作）推理规则集，记作R(I)。可以将可以将I 记作为记作为4元组元组其中其中是是I 的形式语言系统的形式语言系统 为为I 的形式演算系统的形式演算系统2023-2-1118自然推理系统自然推理系统 P 定义如下：定义如下：1、字母表、字母表 （1）命题变项符号：）命题变项符号

11、：p,q,r,（2）联结词符号：）联结词符号：，（3）括号与逗号括号与逗号：(),(),2 2、合式公式、合式公式 定义同定义同1.61.63 3、推理规则、推理规则2023-2-1119推理规则推理规则 (1)前提引入规则前提引入规则(2)结论引入规则结论引入规则(3)置换规则置换规则(4)假言推理规则假言推理规则 AB A B(5)附加规则附加规则 A A B (6)化简规则化简规则 A B A(7)拒取式规则拒取式规则 AB B A(8)假言三段论规则假言三段论规则 AB BC AC 2023-2-1120推理规则推理规则(续续)(11)破坏性二难推理破坏性二难推理规则规则 AB CD

12、BD AC(12)合取引入规则合取引入规则 A B A B(9)析取三段论规则析取三段论规则 A B B A(10)构造性二难推理构造性二难推理规则规则 AB CD A C B D2023-2-1121推理的形式结构为：推理的形式结构为：A1A2AkB证明时，要求首先写出：证明时，要求首先写出：前提：前提：A1 A2 Ak结论：结论：例例1：在自然推理系统中构造下列推理的证明。：在自然推理系统中构造下列推理的证明。前提：前提：p q,q r,p s,s结论：结论：r(p q)2023-2-1122证明：证明：p s 前提引入前提引入 s 前提引入前提引入 p 拒取式拒取式 p q 前提引入前提

13、引入 q 析取三段论析取三段论 q r 前提引入前提引入 r 假言推理假言推理 r(p q)合取合取2023-2-1123例例2：在自然推理系统中构造下列推理的证明。：在自然推理系统中构造下列推理的证明。若若a是实数，则它不是有理数就是无理数。若是实数，则它不是有理数就是无理数。若a不能不能表示成分数，则它不是有理数。表示成分数，则它不是有理数。A是实数且它不能是实数且它不能表示成分数，所以表示成分数，所以a是无理数。是无理数。p：a是实数。是实数。q：a是有理数。是有理数。r：a是无理数。是无理数。s：a能表示成分数。能表示成分数。前提：前提：p(q r),s q,p s结论：结论：r202

14、3-2-1124两种特殊的证明方法两种特殊的证明方法附加前提证明法附加前提证明法适用于此类蕴涵式的证明适用于此类蕴涵式的证明 (A1 A2 Ak)(A B)(*)欲证明欲证明(*)式，只需证明式，只需证明 (A1 A2 Ak A)B 即可，因为即可，因为2023-2-1125(*)式式 (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 (A1 A2 Ak A)B2023-2-1126前提：前提：p(q r),s p,q结论：结论：s r证明：证明：s p 前提引入前提引入

15、s 附加附加前提引入前提引入 p 假言推理假言推理 p(q r)前提引入前提引入 q r 假言推理假言推理 q 前提引入前提引入 r 假言推理假言推理 2023-2-1127两种特殊的证明方法两种特殊的证明方法归谬法归谬法适用于此类蕴涵式的证明适用于此类蕴涵式的证明 (A1 A2 Ak)B将将 B加入前提，若推出矛盾，则得证推理正确加入前提，若推出矛盾，则得证推理正确.理由理由:(A1 A2 Ak)B (A1 A2 Ak B）若若 (A1 A2 Ak B）为矛盾式，）为矛盾式，则则 (A1 A2 Ak)B 为重言式为重言式 ，即即 (A1 A2 Ak)B2023-2-1128前提：前提：p q ,r q,r s结论：结论：p证明：证明：p 结论否定结论否定引入引入 p q 前提引入前提引入 q 假言推理假言推理 r q 前提引入前提引入 r 析取三段论析取三段论 r s 前提引入前提引入 r 化简规则化简规则 r r 合取合取2023-2-1129用归谬法证明：用归谬法证明：前提：前提：p q，pr结论：结论：r q2023-2-1130练练 习习 题题1.(1)(3)(5)2.(1)6.(4)(5)(6)7.(2)8.(2)10