3命题逻辑的推理理论.ppt

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

1、1 13 3.1 1 推理的形式结构推理的形式结构3 3.2 2 自然推理系统自然推理系统P P第三章第三章第三章第三章 命题逻辑的推理理论命题逻辑的推理理论命题逻辑的推理理论命题逻辑的推理理论2 2q数理逻辑的主要任务是数理逻辑的主要任务是用数学的方法来研究数学中的用数学的方法来研究数学中的推理推理。q推理推理是指从前提出发推出结论的思维过程。是指从前提出发推出结论的思维过程。q前提前提是已知命题公式集合。是已知命题公式集合。q结论结论是从前提出发应用推理规则推出的命题公式。是从前提出发应用推理规则推出的命题公式。q证明证明是描述推理正确或错误的过程。是描述推理正确或错误的过程。3.1 3.

2、1 3.1 3.1 推理的形式结构推理的形式结构推理的形式结构推理的形式结构3 3定义定义3.1 3.1 设设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 A Ak k为假为假;（2 2）或者当）或者当A A1 1AA2 2 A Ak k为真时，为真时，B B也为真也为真;则称由前提则称由前提A A1 1,A,A2 2,A Ak k推出推出B B的的推理是有效的或正确的推理是有效的或正确的，并称

3、，并称B B是是有效结论有效结论。研究推理，首先应该明确什么样的推理是有效的或正确的。研究推理，首先应该明确什么样的推理是有效的或正确的。研究推理，首先应该明确什么样的推理是有效的或正确的。研究推理，首先应该明确什么样的推理是有效的或正确的。4 4关于有效推理的说明关于有效推理的说明关于有效推理的说明关于有效推理的说明q A1，A2，Ak由由 推推B的推理记为的推理记为 B若推理是正确的，记为若推理是正确的，记为 B若推理是不正确的，记为若推理是不正确的，记为 Bq由前提由前提A1，A2，Ak推结论推结论B的推理是否正确与诸前提的推理是否正确与诸前提的排列次序无关。的排列次序无关。5 5关于有

4、效推理的说明关于有效推理的说明关于有效推理的说明关于有效推理的说明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,n),n)，前提和结论的前提和结论的取值情况有以下四种：取值情况有以下四种：(1)(1)A A1 1AA2 2 A Ak k为为0 0，B B为为0 0。(2)(2)A A1 1AA2 2 A Ak k为为0 0，B B为为1 1。(3)(3)A A1 1AA2 2 A Ak k为为1 1，B B为为0 0。(4)(4)A A

5、1 1AA2 2 A Ak k为为1 1，B B为为1 1。q只要不出现只要不出现(3)(3)中的情况，推理就是正确的，因而判断推理中的情况，推理就是正确的，因而判断推理是否正确，就是判断是否会出现是否正确，就是判断是否会出现(3)(3)中的情况。中的情况。q推理正确，并不能保证结论推理正确，并不能保证结论B B一定为真一定为真。6 6(1)(1)p,pq qp,pq q(2)p,qp q(2)p,qp q 例例3.13.1 判断下列推理是否正确。（真值表法）判断下列推理是否正确。（真值表法）pqp(pq)qp(qp)q000000010101100010111111正确正确不正确不正确7 7

6、定理定理3.13.1 命题公式命题公式A A1 1,A,A2 2,A Ak k推推B B的推理正确当且仅当的推理正确当且仅当 (A A1 1A A2 2A Ak k)B B 为为重言式重言式。q该定理是判断推理是否正确的另一种方法。该定理是判断推理是否正确的另一种方法。说说明明有效推理的等价定理有效推理的等价定理有效推理的等价定理有效推理的等价定理8 8定理定理定理定理3.13.13.13.1的证明的证明的证明的证明(1)(1)证明必要性。若证明必要性。若A A1 1,A,A2 2,A Ak k推推B B的推理正确，的推理正确，则对于则对于A A1 1,A,A2 2,A Ak k,B,B中所含

7、命题变项的任意一组赋值，不会出中所含命题变项的任意一组赋值，不会出现现A A1 1AA2 2A Ak k为真，而为真，而B B为假的情况，为假的情况，因而在任何赋值下，蕴涵式因而在任何赋值下，蕴涵式(A A1 1AA2 2A Ak k)B)B均为真，故它均为真，故它为重言式。为重言式。(2)(2)证明充分性。若蕴涵式证明充分性。若蕴涵式(A A1 1AA2 2A Ak k)B)B为重言式，为重言式，则对于任何赋值此蕴涵式均为真，因而不会出现前件为真后件则对于任何赋值此蕴涵式均为真，因而不会出现前件为真后件为假的情况，为假的情况，即在任何赋值下，或者即在任何赋值下，或者A A1 1AA2 2A

8、Ak k为假，为假，或者或者A A1 1AA2 2A Ak k和和B B同时为真，这正符合推理正确的定义。同时为真，这正符合推理正确的定义。9 9当推理正确时，当推理正确时，q形式（形式（1）记为）记为 B。q形式（形式（2）记为）记为A1 A2 AkB。表示蕴涵式为重言式。表示蕴涵式为重言式。(1)设设=A1,A2,Ak，记为记为 B。(2)A1 A2 AkB(3)前提：前提：A1,A2,Ak结论：结论：B说说明明推理的形式结构推理的形式结构推理的形式结构推理的形式结构1010q 真值表法真值表法 q 等值演算法等值演算法 q 主析取范式法主析取范式法判断推理是否正确的方法判断推理是否正确的

9、方法判断推理是否正确的方法判断推理是否正确的方法q当命题变项较少时当命题变项较少时,这三种方法比较方便这三种方法比较方便。说说明明1111（1 1）下午马芳或去看电影或去游泳。她没去看电影，所下午马芳或去看电影或去游泳。她没去看电影，所 以，她去游泳了。以，她去游泳了。例例3.23.2 判断下列推理是否正确。（等值演算法）判断下列推理是否正确。（等值演算法）解：设解：设p:p:马芳下午去看电影，马芳下午去看电影，q:q:马芳下午去游泳。马芳下午去游泳。前提：前提：p pq q，p p 结论：结论：q q 推理的形式结构：推理的形式结构：(p(pq)q)p)p)q q (p (pq)q)p)p)

10、q q (p(pq)q)p)p)q q (p pq)q)p p)q q (p pp p)(q qp)p)q q (q qp)p)q q 1 1由定理由定理 3.1 3.1可知，可知，推理正确。推理正确。1 1、从左到右、从左到右 设设(pq)ppq)p为为1,1,则则pqpq与与p p均为均为1,1,从而从而q q为为1.1.2 2、从右到左从右到左设设q q为为0 0，则，则pqpq与与p p等值，从而等值，从而(pq)ppq)p与与 pppp等值，即等值，即(pq)ppq)p为为0 0。1212(1)A(1)A (AB)(AB)附加律附加律(2)(2)(AB)AB)A A 化简律化简律(3

11、)(3)(AB)A AB)A B B 假言推理假言推理(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)构造构造性二难性二难 (AB)(AB)(AA)AB)(AB)(AA)B B 构造性二难构造性二难(9)(9)(AB)(CD)(BD)AB)(CD)(BD)(AC)(AC)破坏性二难破坏性二难推理

12、定律推理定律推理定律推理定律-重言蕴含式重言蕴含式重言蕴含式重言蕴含式1313关于推理定律的几点说明关于推理定律的几点说明关于推理定律的几点说明关于推理定律的几点说明q注意注意 与与 的区别。的区别。q若一个推理的形式结构与某条推理定律对应的蕴涵式一若一个推理的形式结构与某条推理定律对应的蕴涵式一致，则不用证明就可断定这个推理是正确的。致，则不用证明就可断定这个推理是正确的。q2.12.1节给出的节给出的2424个等值式中的每一个都派生出两条推理个等值式中的每一个都派生出两条推理定律。例如双重否定律定律。例如双重否定律A A A A产生两条推理定律产生两条推理定律A A A A和和 A AA

13、A。q由九条推理定律可以产生九条推理规则由九条推理定律可以产生九条推理规则,它们构成了推它们构成了推理系统中的推理规则理系统中的推理规则。1414q判断推理是否正确的三种方法：真值表法、等值演算法和判断推理是否正确的三种方法：真值表法、等值演算法和主析取范式法。主析取范式法。q当推理中包含的命题变项较多时，上述三种方法演算量太当推理中包含的命题变项较多时，上述三种方法演算量太大。因此，有必要构造较为简洁的推理系统。大。因此，有必要构造较为简洁的推理系统。3 3 3 3.2 2 2 2 自然推理系统自然推理系统自然推理系统自然推理系统P P P P定义定义3.33.3 自然推理系统自然推理系统P

14、 P定义如下：1字母表字母表（1）命题变项符号：命题变项符号：p，q，r，,pi，qi，ri，（2）联结词符号：联结词符号：,（3）括号和逗号：括号和逗号：()，15152 2合式公式合式公式 3 3推理规则推理规则（1 1）前提引入规则（前提引入规则（P P规则规则）：在证明的任何步骤上都）：在证明的任何步骤上都可以引入前提。可以引入前提。（2 2）结论引入规则（结论引入规则（T T规则规则）：在证明的任何步骤上所）：在证明的任何步骤上所得到的结论都可以作为后继证明的前提。得到的结论都可以作为后继证明的前提。（3 3）置换规则：在证明的任何步骤上，命题公式中的子置换规则：在证明的任何步骤上，

15、命题公式中的子公式都可以用与之等值的公式置换，得到公式序列中的又一公式都可以用与之等值的公式置换，得到公式序列中的又一个公式。个公式。1616（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）现在气温在冰点以下并且正）现在气温在

16、冰点以下并且正在下雨。因此，现在气温在冰在下雨。因此，现在气温在冰点以下。点以下。1717（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（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 A B B A A B B1818在

17、自然推理系统在自然推理系统在自然推理系统在自然推理系统P P P P中构造证明中构造证明中构造证明中构造证明qP P中构造证明就是由一组中构造证明就是由一组P P中公式作为前提，利用中公式作为前提，利用P P中的规中的规则，推出结论。则，推出结论。q构造形式结构构造形式结构A A1 1 A A2 2 A Ak k B B 的推理的的推理的书写方法：书写方法：前提：前提：A A1 1,A,A2 2,A Ak k 结论：结论：B Bq证明方法：证明方法：直接证明法直接证明法 附加前提法附加前提法归谬法（或称反证法）归谬法（或称反证法）1919证明：证明：pqpq P P 前提引入前提引入 pq p

18、q，T T 置换置换 rqrq P P 前提引入前提引入 qr qr，T T 置换置换 pr pr，T T 假言三段论假言三段论 r rs s P P 前提引入前提引入 p ps s，T T 假言三段论假言三段论 例例3.33.3 在自然推理系统在自然推理系统P P中构造下面推理的证明：中构造下面推理的证明：(1)(1)前提：前提：pqpq,rqrq,rsrs 结论：结论：psps 2020证明：证明：pp（qrqr）P P前提引入前提引入 p pq q P P前提引入前提引入 p p T T化简化简 q q T T化简化简 qrqr TT假言推理假言推理 r r T T假言推理假言推理 r

19、rs s TT附加附加 rsrsT T置换置换例例3.3.3 3 在自然推理系统在自然推理系统P P中构造下面推理的证明：中构造下面推理的证明：(2)(2)前提：前提：pp（qrqr）,p pq q 结论：结论：rsrs 2121 ps ps 前提引入前提引入 p p 化简化简 s s 化简化简 p(qr)p(qr)前提引入前提引入 qr qr 假言推理假言推理 sqsq 前提引入前提引入 q q 假言推理假言推理 r r 析取三段论析取三段论 例例3.3.4 4 在自然推理系统在自然推理系统P P中构造下面推理的证明：中构造下面推理的证明：前提：前提：p(qrp(qr),),sqsq,psp

20、s结论：结论：r r2222构造证明：构造证明：（1 1）将简单命题符号化：）将简单命题符号化：设设 p:p:小张去看电影。小张去看电影。q:q:小王去看电影。小王去看电影。r:r:小李去看电影。小李去看电影。s:s:小赵去看电影。小赵去看电影。例例3.53.5 在在自然推理系统自然推理系统P P中构造下面推理的证明。中构造下面推理的证明。如果小张和小王去看电影，则小李也去看电影；小赵不去如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵看电影或小张去看电影；小王去看电影。所以，当小赵去看电影时，小李也去看电影。去看电影时，小李也去看电影。232

21、3（2 2）形式结构：形式结构：前提：前提：(p pq)q)r,r,s sp,q p,q 结论：结论：s sr r（3 3）证明：）证明：用附加前提证明法用附加前提证明法 s s 附加前提引入附加前提引入 s sp p 前提引入前提引入 p p 析取三段论析取三段论 (p pq)q)r r 前提引入前提引入 q q 前提引入前提引入 p pq q 合取合取 r r 假言推理假言推理 2424构造证明：构造证明：（1 1）将简单命题符号化：）将简单命题符号化：设设 p:p:小张守第一垒。小张守第一垒。q:q:小李向小李向B B队投球。队投球。r:Ar:A队取胜。队取胜。s:As:A队获得联赛第一

22、名。队获得联赛第一名。（2 2）形式结构：）形式结构：前提：前提：(p pq)q)r,r,r rs,s,s,p s,p 结论：结论：q q 例例3.63.6 在在自然推理系统自然推理系统P P中构造下面推理的证明。中构造下面推理的证明。如果小张守第一垒并且小李向如果小张守第一垒并且小李向B B队投球，则队投球，则A A队将取胜；或队将取胜；或者者A A队未取胜，或者队未取胜，或者A A队获得联赛第一名；队获得联赛第一名；A A队没有获得联队没有获得联赛的第一名；小张守第一垒。因此，小李没有向赛的第一名；小张守第一垒。因此，小李没有向B B队投球。队投球。2525（3 3）证明：）证明：用归谬法

23、用归谬法 q q 结论的否定引入结论的否定引入 r rs s 前提引入前提引入 s s 前提引入前提引入 r r 析取三段论析取三段论 (p pq)q)r r 前提引人前提引人 (p pq)q)拒取式拒取式 p pq q 置换置换 p p 前提引入前提引入 q q 析取三段论析取三段论 q qq q 合取合取 由于最后一步由于最后一步为矛盾式为矛盾式，所以推理正确。，所以推理正确。2626本章主要内容本章主要内容本章主要内容本章主要内容q推理的形式结构：推理的形式结构：推理的前提推理的前提推理的结论推理的结论推理正确推理正确q判断推理是否正确的方法：判断推理是否正确的方法：真值表法真值表法等值

24、演算法等值演算法主析取范式法主析取范式法 q对于正确的推理，在自然推理系统对于正确的推理，在自然推理系统P P中构造证明中构造证明:自然推理系统自然推理系统P P的定义的定义自然推理系统自然推理系统P P的推理规则：的推理规则：附加前提证明法附加前提证明法归谬法归谬法2727本章学习要求本章学习要求本章学习要求本章学习要求q理解并记住推理的形式结构的三种等价形式，即理解并记住推理的形式结构的三种等价形式，即A1,A2,AkBA1A2AkB前提：前提：A1,A2,Ak结论：结论：B在判断推理是否正确时，用在判断推理是否正确时，用；在；在P系统中构造证明时用系统中构造证明时用。q熟练掌握判断推理是

25、否正确的三种方法（真值表法，等值演算熟练掌握判断推理是否正确的三种方法（真值表法，等值演算法，主析取范式法）。法，主析取范式法）。q牢记牢记P系统中的各条推理规则。系统中的各条推理规则。q对于给定的正确推理，要求在对于给定的正确推理，要求在P系统中给出严谨的证明序列。系统中给出严谨的证明序列。q会用附加前提证明法和归谬法。会用附加前提证明法和归谬法。2828习题习题习题习题1、用用不不同同的的方方法法验验证证下下面面推推理理是是否否正正确确。对对于于正正确确的的推推理理还还要在要在P系统中给出证明。系统中给出证明。（1）前提：前提：pq,q结论：结论：p（2）前提：前提：qr,pr结论：结论：

26、qp2929（1）不正确。）不正确。验证答案，只需证明验证答案，只需证明(pq)qp不是重言式。不是重言式。方法一方法一等值演算等值演算(pq)qp(p q)q)p(pq)qp(p q)(q q)p p q易易知知10是是成成假假赋赋值值，故故(pq)qp不不是是重重言言式式，所所以以推理不正确。推理不正确。3030方法二方法二主析取范式法主析取范式法经过演算后可知经过演算后可知(pq)qpm0 m1 m3未含未含m2,故故(pq)qp不是重言式。不是重言式。方法三方法三直接观察出直接观察出10是成假赋值。是成假赋值。3131方法四方法四真值表法真值表法(pq)qp的真值表为的真值表为pq(p

27、q)qp001101010111结论（不正确）是对的。结论（不正确）是对的。3232（2）推理正确）推理正确方法一方法一真值表法（自己做）真值表法（自己做）方法二方法二等值演算法（自己做）等值演算法（自己做）方法三方法三主析取范式法（自己做）主析取范式法（自己做）方法四方法四P系统中构造证明系统中构造证明证明：证明：（直接证明法）（直接证明法）pr（前提引入）前提引入）rp（置换）置换）qr（前提引入）前提引入）qp（假言三段论）假言三段论）33332、在、在P系统中构造下面推理的证明：系统中构造下面推理的证明：如果今天是周六，我们就到颐和园或圆明园玩。如果今天是周六，我们就到颐和园或圆明园玩

28、。如如果颐和园游人太多，就不去颐和园。果颐和园游人太多，就不去颐和园。今天是周六，并且今天是周六，并且颐和园游人太多。颐和园游人太多。所以我们去圆明园或动物园玩。所以我们去圆明园或动物园玩。构造证明：构造证明：（1）设设p：今天是周六。今天是周六。q：到颐和园玩。到颐和园玩。r：到圆明园玩。到圆明园玩。s：颐和园游人太多。颐和园游人太多。t：到动物园玩。到动物园玩。（2）前提：）前提：p(q r),sq,p,s结论：结论：r t3434（3）证明：证明：p(q r)前提引入前提引入p前提引入前提引入q r假言推理假言推理sq前提引入前提引入s前提引入前提引入 q假言推理假言推理r析取三段论析取三段论r t附加附加3535作作作作 业业业业习题三习题三：6（4）、）、14（1）、（）、（5）、）、15（1）、）、16（2）3636同学们学习愉快！同学们学习愉快！下次课再见！下次课再见！