命题逻辑的推理理论PPT讲稿.ppt

《命题逻辑的推理理论PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《命题逻辑的推理理论PPT讲稿.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1页，共35页，编辑于2022年，星期六q数理逻辑的主要任务是数理逻辑的主要任务是用数学的方法来研究数学中的推理。用数学的方法来研究数学中的推理。q推理推理是指从前提出发推出结论的思维过程。是指从前提出发推出结论的思维过程。q前提前提是已知命题公式集合。是已知命题公式集合。q结论结论是从前提出发应用推理规则推出的命题公式。是从前提出发应用推理规则推出的命题公式。q证明证明是描述推理正确或错误的过程。是描述推理正确或错误的过程。q要研究推理，首先应该明确什么样的推理是有效的或正要研究推理，首先应该明确什么样的推理是有效的或正确的。确的。第2页，共35页，编辑于2022年，星期六定义定义1.24

2、1.24 设设A A1 1,A,A2 2,A,Ak k和和B B都是命题公式，若对于都是命题公式，若对于A A1 1,A,A2 2,A,Ak k和和B B中出现的命题变项的任意一组赋值，中出现的命题变项的任意一组赋值，（1 1）或者）或者A A1 1AA2 2 AAk k为假为假;（2 2）或者当）或者当A A1 1AA2 2 AAk k为真时，为真时，B B也为真也为真;则称由前提则称由前提A A1 1,A,A2 2,A,Ak k推出推出B B的的推理是有效的或正确的推理是有效的或正确的，并称并称B B是是有效结论有效结论。有效推理的定义有效推理的定义即：（即：（A1 A2 Ak）B为重言式

3、为重言式第3页，共35页，编辑于2022年，星期六关于有效推理的说明关于有效推理的说明q A1，A2，Ak由由 推推B的推理记为的推理记为B若推理是正确的，记为若推理是正确的，记为 B若推理是不正确的，记为若推理是不正确的，记为 Bq由前提由前提A1，A2，Ak推结论推结论B的推理是否正确与诸的推理是否正确与诸前提的排列次序无关。前提的排列次序无关。第4页，共35页，编辑于2022年，星期六q设设A A1 1，A A2 2，A Ak k，B B中共出现中共出现n n个命题变项，对于任何一组赋个命题变项，对于任何一组赋值值1 12 2n n(i i=0=0或者或者1 1，i=1,2,i=1,2,

4、n),n)，前提和结论的取，前提和结论的取值情况有以下四种：值情况有以下四种：(1)(1)A A1 1AA2 2 AAk k为为0 0，B B为为0 0。(2)(2)A A1 1AA2 2 AAk k为为0 0，B B为为1 1。(3)(3)A A1 1AA2 2 AAk k为为1 1，B B为为0 0。(4)(4)A A1 1AA2 2 AAk k为为1 1，B B为为1 1。q只要不出现只要不出现(3)(3)中的情况，推理就是正确的，因而判断推理是中的情况，推理就是正确的，因而判断推理是否正确，就是判断是否会出现否正确，就是判断是否会出现(3)(3)中的情况。中的情况。q推理正确，并不能保

5、证结论推理正确，并不能保证结论B B一定为真。一定为真。第5页，共35页，编辑于2022年，星期六(1)(1)p,pq qp,pq q(2)p,qp q(2)p,qp q 例例1 1 判断下列推理是否正确。（真值表法）判断下列推理是否正确。（真值表法）pqp(pq)qp(qp)q000000010101100010111111正确正确不正确不正确第6页，共35页，编辑于2022年，星期六当推理正确时，当推理正确时，q形式（形式（1）记为）记为 B。q形式（形式（2）记为）记为A1 A2 AkB。表示蕴涵式为重言式。表示蕴涵式为重言式。(1)=A1,A2,Ak，记为，记为 B。(2)A1 A2

6、AkB(3)前提：前提：A1,A2,Ak结论：结论：B说明说明推理的形式结构推理的形式结构第7页，共35页，编辑于2022年，星期六q 真值表法真值表法 q 等值演算法等值演算法 q 主析取范式法主析取范式法判断推理是否正确的方法判断推理是否正确的方法q是否有其他的证明方法？是否有其他的证明方法？思考思考q当命题变项较少时当命题变项较少时,这三种方法比较方便这三种方法比较方便。说明说明第8页，共35页，编辑于2022年，星期六 下午马芳或去看电影或去游泳。她没去看电影，所以，她下午马芳或去看电影或去游泳。她没去看电影，所以，她 去游泳了。去游泳了。例例2 2 判断下列推理是否正确。（等值演算法

7、）判断下列推理是否正确。（等值演算法）解：设解：设p:p:马芳下午去看电影，马芳下午去看电影，q:q:马芳下午去游泳。马芳下午去游泳。前提：前提：pqpq，p p 结论：结论：q q 推理的形式结构：推理的形式结构：(pq)(pq)p)p)q q (pq)(pq)p)p)q q (pq)(pq)p)qp)q (ppq)q)pp)q q (pppp )()(qp)qp)q q (q qp)p)q q 1 1例题例题第9页，共35页，编辑于2022年，星期六(1)A(1)A (AB)(AB)附加律附加律(2)(2)(AB)AB)A A 化简律化简律(3)(3)(AB)A AB)A B B 假言推理

8、假言推理(4)(4)(AB)B AB)B A A 拒取式拒取式(5)(5)(AB)B AB)B A A 析取三段论析取三段论 (6)(6)(AB)(BC)AB)(BC)(AC)(AC)假言三段论假言三段论(7)(7)(A AB)(BB)(BC)C)(A(A C)C)等价三段论等价三段论(8)(8)(AB)(CD)(AC)AB)(CD)(AC)(BD)(BD)构造构造性二难性二难 (9)(9)(AB)(CD)(BD)AB)(CD)(BD)(AC)(AC)破坏性二难破坏性二难推理定律推理定律-重言蕴含式重言蕴含式第10页，共35页，编辑于2022年，星期六关于推理定律的几点说明关于推理定律的几点说

9、明qA,B,CA,B,C为元语言符号，代表任意的命题公式。为元语言符号，代表任意的命题公式。q若一个推理的形式结构与某条推理定律对应的蕴涵式一致，若一个推理的形式结构与某条推理定律对应的蕴涵式一致，则不用证明就可断定这个推理是正确的。则不用证明就可断定这个推理是正确的。q1.31.3节给出的节给出的2424个等值式中的每一个都派生出两条推理个等值式中的每一个都派生出两条推理定律。例如双重否定律定律。例如双重否定律A A A A产生两条推理定律产生两条推理定律A A A A和和 A AA A。q由九条推理定律可以产生九条推理规则由九条推理定律可以产生九条推理规则,它们构成了推理系它们构成了推理系

10、统中的推理规则。统中的推理规则。第11页，共35页，编辑于2022年，星期六构造性证明方法构造性证明方法q判断推理是否正确的三种方法：真值表法、等值演算法和主判断推理是否正确的三种方法：真值表法、等值演算法和主析取范式法。析取范式法。q当推理中包含的命题变项较多时，上述三种方法演算量太当推理中包含的命题变项较多时，上述三种方法演算量太大。大。q对于由前提对于由前提A A1 1,A,A2 2,A,Ak k推推B B的正确推理应该给出严谨的的正确推理应该给出严谨的证明证明。q证明证明是一个描述推理过程的是一个描述推理过程的命题公式序列命题公式序列，其中的每个公，其中的每个公式或者是式或者是前提前提

11、，或者是由某些前提应用推理规则得到的，或者是由某些前提应用推理规则得到的结结论论（中间结论或推理中的结论）。（中间结论或推理中的结论）。第12页，共35页，编辑于2022年，星期六常用的推理规则常用的推理规则（1 1）前提引入规则前提引入规则：在证明的任何步骤上，：在证明的任何步骤上，都可以引入前提。都可以引入前提。（2 2）结论引入规则结论引入规则：在证明的任何步骤上，所证：在证明的任何步骤上，所证明的结论都可以作为后续证明的前提。明的结论都可以作为后续证明的前提。（3 3）置换规则置换规则：在证明的任何步骤上，命题公式：在证明的任何步骤上，命题公式中任何子命题公式都可以用与之等价的命题公式

12、中任何子命题公式都可以用与之等价的命题公式置换。置换。第13页，共35页，编辑于2022年，星期六（4 4）假言推理规则）假言推理规则 A AB B A A B B（5 5）附加规则）附加规则 A A A A B B（6 6）化简规则）化简规则 A A B B A A（4 4）若今天下雪）若今天下雪,则将去滑雪。则将去滑雪。今天下雪，所以去滑雪。今天下雪，所以去滑雪。（5 5）现在气温在冰点以下。因）现在气温在冰点以下。因此，要么现在气温在冰点以此，要么现在气温在冰点以下，要么现在下雨。下，要么现在下雨。（6 6）现在气温在冰点以下并且）现在气温在冰点以下并且正在下雨。因此，现在气温正在下雨。

13、因此，现在气温在冰点以下。在冰点以下。第14页，共35页，编辑于2022年，星期六（7 7）拒取式规则）拒取式规则 A AB B B B A A（8 8）假言三段论规则假言三段论规则 A AB B B BC C A AC C（9 9）析取三段论规则）析取三段论规则 A A B B B B A A第15页，共35页，编辑于2022年，星期六（1010）构造性二难推理规则）构造性二难推理规则 A AB B C CD D A A C C B B D D （1111）破坏性二难推理规则）破坏性二难推理规则 A AB B C CD D B BD D A AC C（1212）合取引入规则合取引入规则 A

14、A B B A A B B第16页，共35页，编辑于2022年，星期六构造证明构造证明q构造证明就是由一组公式作为前提，利用自然推理系构造证明就是由一组公式作为前提，利用自然推理系统中的规则，推出结论。统中的规则，推出结论。q构造形式结构构造形式结构A A1 1 A A2 2 A Ak k B B 的推理的书写方法：的推理的书写方法：前提：前提：A A1 1,A,A2 2,A,Ak k 结论：结论：B Bq证明方法：证明方法：直接证明法直接证明法 附加前提法附加前提法归谬法（或称反证法）归谬法（或称反证法）第17页，共35页，编辑于2022年，星期六例例3 3.1.1 构造下面推理的证明：构造

15、下面推理的证明：前提：前提：pq,rq,rs pq,rq,rs 结论：结论：ps ps pqpq 前提引入前提引入 pq pq 置换置换 rqrq 前提引入前提引入 qr qr 置换置换 pr pr 假言三段论假言三段论 rs rs 前提引入前提引入 ps ps 假言三段论假言三段论 第18页，共35页，编辑于2022年，星期六例题例题例例3 3.2.2 构造下面推理的证明：构造下面推理的证明：前提：前提：pp（qrqr）,pq,pq 结论：结论：rs rs pp（qrqr）前提引入前提引入 pqpq 前提引入前提引入 p p 化简化简 q q 化简化简 qrqr 假言推理假言推理 r r 假

16、言推理假言推理 rsrs 附加附加 rsrs置换置换第19页，共35页，编辑于2022年，星期六技巧一：附加前提证明法技巧一：附加前提证明法q(A(A1 1 AA2 2 A Ak k)(A B)(A B)等价于等价于 (A(A1 1 AA2 2 A Ak k A)BA)B 即原来结论中的前件变成前提了！即原来结论中的前件变成前提了！第20页，共35页，编辑于2022年，星期六例例4 4 构造下面推理的证明。构造下面推理的证明。如果小张和小王去看电影，则小李也去看电影；小赵不去如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影或小张去看电影

17、；小王去看电影。所以，当小赵去看电影时，小李也去看电影。看电影时，小李也去看电影。构造证明：构造证明：（1 1）将简单命题符号化：）将简单命题符号化：设设 p:p:小张去看电影。小张去看电影。q:q:小王去看电影。小王去看电影。r:r:小李去看电影。小李去看电影。s:s:小赵去看电影。小赵去看电影。第21页，共35页，编辑于2022年，星期六（2 2）形式结构：形式结构：前提：前提：(pq)r,sp,q pq)r,sp,q 结论：结论：sr sr（3 3）证明：用附加前提证明法）证明：用附加前提证明法 s s 附加前提引入附加前提引入 spsp 前提引入前提引入 p p 析取三段论析取三段论

18、(pq)r pq)r 前提引入前提引入 q q 前提引入前提引入 pqpq 合取合取 r r 假言推理假言推理 第22页，共35页，编辑于2022年，星期六技巧二：归谬法技巧二：归谬法q(A(A1 1 AA2 2 A Ak k)B)B 等价于等价于（A A1 1 AA2 2 A Ak k B B ）因此，若因此，若A A1 1 AA2 2 A Ak k 与与B B 不相容（即不相容（即A A1 1 AA2 2 A Ak k B B 为矛盾式为矛盾式，或，或（A A1 1 AA2 2 A Ak k B B ）为重言式），则说明为重言式），则说明B B是是A A1 1 AA2 2 A Ak k的逻

19、辑结论。的逻辑结论。这种将这种将B B 作为附加前提推出矛盾的证明方法成作为附加前提推出矛盾的证明方法成为归谬法。为归谬法。第23页，共35页，编辑于2022年，星期六例例5 5 构造下面推理的证明。构造下面推理的证明。如果小张守第一垒并且小李向如果小张守第一垒并且小李向B B队投球，则队投球，则A A队将取胜；或者队将取胜；或者A A队未取胜，队未取胜，或者或者A A队获得联赛第一名；队获得联赛第一名；A A队没有获得联赛的第一名；小张守第队没有获得联赛的第一名；小张守第一垒。因此，小李没有向一垒。因此，小李没有向B B队投球。队投球。构造证明：构造证明：（1 1）将简单命题符号化：）将简单

20、命题符号化：设设 p:p:小张守第一垒。小张守第一垒。q:q:小李向小李向B B队投球。队投球。r:Ar:A队取胜。队取胜。s:As:A队获得联赛第一名。队获得联赛第一名。（2 2）形式结构：）形式结构：前提：前提：(pq)r,rs,s,p pq)r,rs,s,p 结论：结论：q q 第24页，共35页，编辑于2022年，星期六例题例题（3 3）证明：用归谬法）证明：用归谬法 q q 结论的否定引入结论的否定引入 rs rs 前提引入前提引入 s s 前提引入前提引入 r r 析取三段论析取三段论 (pq)r pq)r 前提引人前提引人 (pq)pq)拒取式拒取式 pq pq 置换置换 p p

21、 前提引入前提引入 q q 析取三段论析取三段论 qqqq 合取合取 由于最后一步为矛盾式，所以推理正确。由于最后一步为矛盾式，所以推理正确。小节结束第25页，共35页，编辑于2022年，星期六本节主要内容本节主要内容q推理的形式结构：推理的形式结构：推理的前提推理的前提推理的结论推理的结论推理正确推理正确q判断推理是否正确的方法：判断推理是否正确的方法：真值表法真值表法等值演算法等值演算法主析取范式法主析取范式法 q对于正确的推理，给予构造证明对于正确的推理，给予构造证明:1.1.常用的推理规则：常用的推理规则：2.2.附加前提证明法附加前提证明法3.3.归谬法归谬法第26页，共35页，编辑

22、于2022年，星期六本章学习要求本章学习要求q理解并记住推理的形式结构的三种等价形式，即理解并记住推理的形式结构的三种等价形式，即A A1 1,A,A2 2,A,Ak kBBAA1 1AA2 2AAk kBB前提：前提：A A1 1,A,A2 2,A,Ak k 结论：结论：B B在判断推理是否正确时，用在判断推理是否正确时，用；在系统中构造证明时用；在系统中构造证明时用。q熟练掌握判断推理是否正确的三种方法（真值表法，等值演算熟练掌握判断推理是否正确的三种方法（真值表法，等值演算法，主析取范式法）。法，主析取范式法）。q牢记各条推理规则。牢记各条推理规则。q对于给定的正确推理，要求在系统中给出

23、严谨的证明序列。对于给定的正确推理，要求在系统中给出严谨的证明序列。q会用附加前提证明法和归谬法。会用附加前提证明法和归谬法。第27页，共35页，编辑于2022年，星期六典型例题典型例题1 1、用用不不同同的的方方法法验验证证下下面面推推理理是是否否正正确确。对对于于正正确确的的推推理理还还要要在在系统中给出证明。系统中给出证明。（1 1）前提：前提：p pq q,q q 结论：结论：p p（2 2）前提：前提：q qr r,p pr r 结论：结论：q qp p 第28页，共35页，编辑于2022年，星期六（1 1）不正确。）不正确。验证答案，只需证明验证答案，只需证明(p pq q)q q

24、 p p 不是重言式。不是重言式。方法一方法一 等值演算等值演算 (p pq q)q qp p (p p q q)q q)p p(p pq q)q qp p(p p q q)(q q q q)p p p p q q易易知知1010是是成成假假赋赋值值，故故(p pq q)q qp p不不是是重重言言式式，所所以以推理不正确。推理不正确。第29页，共35页，编辑于2022年，星期六方法二方法二 主析取范式法主析取范式法经过演算后可知经过演算后可知(p pq q)q qp p m m0 0 m m1 1 m m3 3 未含未含m m2 2,故故(p pq q)q qp p不是重言式。不是重言式。方

25、法三方法三 直接观察出直接观察出1010是成假赋值。是成假赋值。第30页，共35页，编辑于2022年，星期六方法四方法四 真值表法真值表法(p pq q)q qp p的真值表为的真值表为pq(pq)qp001101010111结论（不正确）是对的。结论（不正确）是对的。第31页，共35页，编辑于2022年，星期六（2）推理正确推理正确方法一方法一 真值表法（自己做）真值表法（自己做）方法二方法二 等值演算法（自己做）等值演算法（自己做）方法三方法三 主析取范式法（自己做）主析取范式法（自己做）方法四方法四 构造证明构造证明证明：证明：（直接证明法）（直接证明法）p pr r （前提引入）（前提

26、引入）r rp p （置换）置换）q qr r （前提引入）（前提引入）q qp p （假言三段论）假言三段论）第32页，共35页，编辑于2022年，星期六2 2、构造下面推理的证明：、构造下面推理的证明：如果今天是周六，我们就到颐和园或圆明园玩。如果今天是周六，我们就到颐和园或圆明园玩。如果颐如果颐和园游人太多，就不去颐和园。和园游人太多，就不去颐和园。今天是周六，并且颐和今天是周六，并且颐和园游人太多。园游人太多。所以我们去圆明园或动物园玩。所以我们去圆明园或动物园玩。构造证明：构造证明：（1 1）设设p p：今天是周六。：今天是周六。q q：到颐和园玩。：到颐和园玩。r r：到圆明园玩。

27、：到圆明园玩。s s：颐和园游人太多。：颐和园游人太多。t t：到动物园玩。：到动物园玩。（2 2）前提：）前提：p p(q q r r),),s sq q,p p,s s 结论：结论：r r t t第33页，共35页，编辑于2022年，星期六（3 3）证明：）证明：p p(q q r r)前提引入前提引入 p p 前提引入前提引入 q q r r 假言推理假言推理 s sq q 前提引入前提引入 s s 前提引入前提引入 q q 假言推理假言推理 r r 析取三段论析取三段论 r r t t 附加附加第34页，共35页，编辑于2022年，星期六习题习题qP.3P.34-354-35 1.1 1.18 8(1)(3)(1)(3)1.1 1.19 9(2)(4)(2)(4)1.1.2020第35页，共35页，编辑于2022年，星期六