离散数学03.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《离散数学03.ppt》由会员分享,可在线阅读,更多相关《离散数学03.ppt(45页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、 1第第3 3章章 命题逻辑的推理理论命题逻辑的推理理论聊城大学重点课程聊城大学重点课程离散数学离散数学 2本章说明本章说明本章说明本章说明q本章的主要内容本章的主要内容推理的形式结构推理的形式结构自然推理系统自然推理系统P Pq本章与后续各章的关系本章与后续各章的关系本章是第五章的特殊情况和先行准备本章是第五章的特殊情况和先行准备 3q3.1 3.1 推理的形式结构推理的形式结构q3.2 3.2 自然推理系统自然推理系统P Pq 本章小结本章小结q 习题习题q 作业作业 43.1 3.1 推理的形式结构推理的形式结构推理的形式结构推理的形式结构q数理逻辑的主要任务是数理逻辑的主要任务是用数学
2、的方法来研究数学中的用数学的方法来研究数学中的推理推理。q推理推理是指从前提出发推出结论的思维过程。是指从前提出发推出结论的思维过程。q前提前提是已知命题公式集合。是已知命题公式集合。q结论结论是从前提出发应用推理规则推出的命题公式。是从前提出发应用推理规则推出的命题公式。q证明证明是描述推理正确或错误的过程。是描述推理正确或错误的过程。q要研究推理,首先应该明确什么样的推理是有效的或要研究推理,首先应该明确什么样的推理是有效的或正确的。正确的。5定义定义3.1 3.1 设设A A1 1,A,A2 2,A Ak k和和B B都是命题公式,若对于都是命题公式,若对于A A1 1,A,A2 2,A
3、 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的的推理是有效的或正确推理是有效的或正确的的,并称,并称B B是是有效结论有效结论。有效推理的定义有效推理的定义有效推理的定义有效推理的定义 6关于有效推理的说明关于有效推理的说明q A1,A2,Ak由由 推推B的推理记为的推理记为B若推理是正确的,记为若推理是正确的,记为 B若
4、推理是不正确的,记为若推理是不正确的,记为 Bq由前提由前提A1,A2,Ak推结论推结论B的推理是否正确的推理是否正确与诸前提的排列次序无关。与诸前提的排列次序无关。7关于有效推理的说明关于有效推理的说明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
5、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 A1 1AA2 2 A Ak k为为1 1,B B为为1 1。q只要不出现只要不出现(3)(3)中的情况,推理就是正确的,因而判断中的情况,推理就是正确的,因而判断推理是否正确,就是判断是否会出现推理是否正确,就是判断是否会出现(3)(3)中的情况。中的情况。q推理正确,并不能保证结论推理正确,并不能保证结论B B一定为真一定为真。8(1)(1)p,pq qp,pq q(2)p,qp q(2)p,qp q 例例3.13.1 判断下列推理是否正确。(真值表法)判
6、断下列推理是否正确。(真值表法)pqp(pq)qp(qp)q000000010101100010111111例题例题例题例题正确正确不正确不正确 9定理定理3.13.1 命题公式命题公式A A1 1,A,A2 2,A Ak k推推B B的推理正确当且仅当的推理正确当且仅当 (A A1 1A A2 2A Ak k)B B 为为重言式重言式。q该定理是判断推理是否正确的另一种方法。该定理是判断推理是否正确的另一种方法。说说明明有效推理的等价定理有效推理的等价定理有效推理的等价定理有效推理的等价定理 10定理定理3.13.1的证明的证明(1)(1)证明必要性。若证明必要性。若A A1 1,A,A2
7、2,A Ak k推推B B的推理正确,的推理正确,则对于则对于A A1 1,A,A2 2,A Ak k,B,B中所含命题变项的任意一组赋值,不会出中所含命题变项的任意一组赋值,不会出现现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为重言式,为重言式,则对于任何赋值此蕴涵式均为真,因而不会出现前件为真后件则对于任何赋值此蕴涵式均为真
8、,因而不会出现前件为真后件为假的情况,为假的情况,即在任何赋值下,或者即在任何赋值下,或者A A1 1AA2 2A Ak k为假,为假,或者或者A A1 1AA2 2A Ak k和和B B同时为真,这正符合推理正确的定义。同时为真,这正符合推理正确的定义。11当推理正确时,当推理正确时,q形式(形式(1)记为)记为 B。q形式(形式(2)记为)记为A1 A2 AkB。表示蕴涵式为重言式。表示蕴涵式为重言式。(1)设设=A1,A2,Ak,记为记为 B。(2)A1 A2 AkB(3)前提:前提:A1,A2,Ak结论:结论:B说说明明推理的形式结构推理的形式结构推理的形式结构推理的形式结构 12q
9、真值表法真值表法 q 等值演算法等值演算法 q 主析取范式法主析取范式法判断推理是否正确的方法判断推理是否正确的方法q是否有其他的证明方法?是否有其他的证明方法?思思考考q当命题变项较少时当命题变项较少时,这三种方法比较方便这三种方法比较方便。说说明明 13(1 1)下午马芳或去看电影或去游泳。她没去看电影,所以,她下午马芳或去看电影或去游泳。她没去看电影,所以,她 去游泳了。去游泳了。例例3.23.2 判断下列推理是否正确。(等值演算法)判断下列推理是否正确。(等值演算法)解:设解:设p:p:马芳下午去看电影,马芳下午去看电影,q:q:马芳下午去游泳。马芳下午去游泳。前提:前提:p pq q
10、,p p 结论:结论:q q 推理的形式结构:推理的形式结构:(p(pq)q)p)p)q q (p (pq)q)p)p)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可知,可知,推理正确。推理正确。例题例题例题例题 14(2 2)若今天是若今天是1 1号,则明天是号,则明天是5 5号号。明天是明天是5 5号号,所以今天是所以今天是1 1号号。例例3.23.2 判断下列推理是否正确。(判断下列推理是否正确。(主析取范式法主析取范式法 )(pq)qp(p q)qp(p q)q
11、)p q p(pq)(pq)(pq)(p q)m0 m2 m3主主析析取取范范式式不不含含m m1 1,故故不不是是重重言言式式(0101是是成成假假赋赋值值),所所以以推推理理不正确。不正确。解:设解:设p p:今天是今天是1 1号,号,q q:明天是明天是5 5号。号。前提:前提:pq,q 结论:结论:p 推理的形式结构:推理的形式结构:(pq)qp 例题例题例题例题 15(1)A(1)A (AB)(AB)附加律附加律(2)(2)(AB)AB)A A 化简律化简律(3)(3)(AB)A AB)A B B 假言推理假言推理(4)(4)(AB)B AB)B A A 拒取拒取式式(5)(5)(A
12、B)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)破坏性二难破坏性二难推理定律推理定律推理定律推理定律-重言蕴含式重言蕴含式重言蕴含式重言蕴含式 16小节结束小节结束关于推理定
13、律的几点说明关于推理定律的几点说明关于推理定律的几点说明关于推理定律的几点说明qA,B,CA,B,C为元语言符号,代表任意的命题公式。为元语言符号,代表任意的命题公式。q若一个推理的形式结构与某条推理定律对应的蕴涵若一个推理的形式结构与某条推理定律对应的蕴涵式一致,则不用证明就可断定这个推理是正确的。式一致,则不用证明就可断定这个推理是正确的。q2.12.1节给出的节给出的2424个等值式中的每一个都派生出两条推个等值式中的每一个都派生出两条推理定律。例如双重否定律理定律。例如双重否定律A A A A产生两条推理定产生两条推理定律律A A A A和和 A AA A。q由九条推理定律可以产生九条
14、推理规则由九条推理定律可以产生九条推理规则,它们构成了它们构成了推理系统中的推理规则推理系统中的推理规则。173.2 3.2 自然推理系统自然推理系统P Pq判断推理是否正确的三种方法:真值表法、等值演判断推理是否正确的三种方法:真值表法、等值演算法和主析取范式法。算法和主析取范式法。q当推理中包含的命题变项较多时,上述三种方法演当推理中包含的命题变项较多时,上述三种方法演算量太大。算量太大。q对于由前提对于由前提A A1 1,A,A2 2,A Ak k推推B B的正确推理应该给出严谨的正确推理应该给出严谨的证明的证明。q证明是一个描述推理过程的命题公式序列,其中的证明是一个描述推理过程的命题
15、公式序列,其中的每个公式或者是前提,或者是由某些前提应用推理每个公式或者是前提,或者是由某些前提应用推理规则得到的结论(中间结论或推理中的结论)。规则得到的结论(中间结论或推理中的结论)。q要构造出严谨的证明就必须在形式系统中进行。要构造出严谨的证明就必须在形式系统中进行。18形式系统的定义形式系统的定义定义定义3.23.2 一个一个形式系统形式系统I由下面四个部分组成:由下面四个部分组成:(1 1)非空的字母表,记作)非空的字母表,记作A(I)。(2 2)A(I)中符号构造的合式公式集,记作中符号构造的合式公式集,记作E(I)。(3 3)E(I)中一些特殊的公式组成的公理集,记作中一些特殊的
16、公式组成的公理集,记作AX(I)。(4 4)推理规则集,记作推理规则集,记作R(I)。可以将可以将I记为记为4 4元组元组 是是I的的形式语言系统形式语言系统 是是I的的形式演算系统形式演算系统 19形式系统的分类形式系统的分类(1 1)自然推理系统自然推理系统从从任任意意给给定定的的前前提提出出发发,应应用用系系统统中中的的推推理理规规则则进进行行推推理理演演算算,得得到到的的最最后后命命题题公公式式是是推推理理的的结结论论(有时称为有效的结论)。(有时称为有效的结论)。(2 2)公理系统公理系统从从若若干干给给定定的的公公理理出出发发,应应用用系系统统中中推推理理规规则则进进行行推理演算,
17、得到的结论是系统中的定理。推理演算,得到的结论是系统中的定理。q本书只介绍自然推理系统本书只介绍自然推理系统P P。说说明明 20自然推理系统的定义自然推理系统的定义定义定义3.33.3 自然推理系统自然推理系统P P的定义的定义1.1.字母表字母表(1 1)命题变项符号:命题变项符号:p,q,r,pi,qi,ri,(2 2)联结词符号:联结词符号:,(3 3)括号与逗号:括号与逗号:(),2.2.合式公式(同定义合式公式(同定义1.61.6)21自然推理系统的定义自然推理系统的定义3.3.推理规则推理规则(1 1)前提引入规则)前提引入规则 在证明的任何步骤上都可以引入前提。在证明的任何步骤
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 03
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内