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

命题逻辑的推理理论命题逻辑的推理理论第一页，讲稿共七十一页哦上一节的复习上一节的复习范式的定义范式的定义n定义定义2.3（1）由有限个）由有限个简单合取式简单合取式构成的析取式称构成的析取式称为为析取范式析取范式。（2）由有限个）由有限个简单析取式简单析取式构成的合取式称构成的合取式称为为合取范式合取范式。（3）析取范式与合取范式统称为）析取范式与合取范式统称为范式范式。第二页，讲稿共七十一页哦上一节的复习上一节的复习求范式的步骤（用等值演算）求范式的步骤（用等值演算）n消去联结词消去联结词,蕴涵等值式蕴涵等值式:AB A B 等价等值式等价等值式:A B (AB)(BA)n否定号的消去（利用双重否定律）否定号的消去（利用双重否定律）A An内移否定号（利用德摩根律）内移否定号（利用德摩根律）(A B)A B (A B)A Bn利用利用对对的分配律求析取范式，的分配律求析取范式，对对的分配的分配律求合取范式。律求合取范式。第三页，讲稿共七十一页哦上一节的复习（续）上一节的复习（续）n定义定义2.5（主范式）（主范式）设由设由n个命题变项构成的析取范式（合取个命题变项构成的析取范式（合取范式）中所有的简单合取式（简单析取范式）中所有的简单合取式（简单析取式）都是式）都是极小项（极大项）极小项（极大项），则称该析，则称该析取范式（合取范式）为主析取范式（主取范式（合取范式）为主析取范式（主合取范式）。合取范式）。第四页，讲稿共七十一页哦上一节的复习（续）上一节的复习（续）n求主范式的步骤求主范式的步骤 （存在性证明过程存在性证明过程）(1)补充命题变项；补充命题变项；(2)消去重复出现的极小（大）项和矛消去重复出现的极小（大）项和矛盾式（重言式）。盾式（重言式）。第五页，讲稿共七十一页哦引言引言n“命题命题”的形式的形式 前两章介绍了前两章介绍了“命题命题”的形式。的形式。n“推理推理”的形式的形式 本章介绍本章介绍“推理推理”的形式。的形式。推理是逻辑的研究对象。推理是逻辑的研究对象。第六页，讲稿共七十一页哦3.1.推理的形式结构推理的形式结构n有效推理有效推理n有效推理的等价定理有效推理的等价定理n重言蕴涵式重言蕴涵式第七页，讲稿共七十一页哦有效推理有效推理n数理逻辑的主要任务是用数学的方法来研究数学中数理逻辑的主要任务是用数学的方法来研究数学中的的推理推理。n所谓推理是指从前提出发推出结论的思维过程，所谓推理是指从前提出发推出结论的思维过程，而前提是已知而前提是已知命题公式集合命题公式集合，结论是从前提出发应，结论是从前提出发应用推理规则推出的用推理规则推出的命题公式命题公式。n要研究推理就应该给出推理的形式结构，为此，要研究推理就应该给出推理的形式结构，为此，首先应该明确什么样的推理是有效的或正确的。首先应该明确什么样的推理是有效的或正确的。第八页，讲稿共七十一页哦有效推理（续）有效推理（续）n定义定义3.1 设设A1,A2,Ak和和B都是命题公式，若对于都是命题公式，若对于A1,A2,Ak和和B中出现的命题变项的任意一组赋中出现的命题变项的任意一组赋值，值，或者或者A1 A2 Ak为假，为假，或者或者当当A1 A2 Ak为真时，为真时，B也为真，也为真，则称由前提则称由前提A1,A2,Ak推出推出B的推理是的推理是有效的有效的或或正正确的确的，并称，并称B是有效结论。是有效结论。第九页，讲稿共七十一页哦定义定义3.1有关说明有关说明n由前提由前提A1,A2,Ak推结论推结论B的推理是否正确与诸前的推理是否正确与诸前提的排列次序无关。提的排列次序无关。因而前提的公式不一定是序列，而是一个有限的公式因而前提的公式不一定是序列，而是一个有限的公式集合，若将这个集合记为集合，若将这个集合记为，可将由，可将由推推B的推理记为的推理记为 B。若推理是正确的，则记为。若推理是正确的，则记为 B，否则记为，否则记为 B。这里，可以称这里，可以称B和和A1,A2,Ak B 为为推理的形推理的形式结构式结构。第十页，讲稿共七十一页哦定义定义3.1有关说明（续）有关说明（续）n设设A1,A2,Ak，B中共出现中共出现n个命题变项，对于任何一组赋值个命题变项，对于任何一组赋值1,2,n(i=0或者或者1，i=1,2,n)，前提和结论的取值情况有以下四种：，前提和结论的取值情况有以下四种：(1)A1 A2 Ak为为0，B为为0.(2)A1 A2 Ak为为0，B为为1.(3)A1 A2 Ak为为1，B为为0.(4)A1 A2 Ak为为1，B为为1.由定义由定义3.1可知，只要不出现可知，只要不出现(3)中的情况，推理就是正确的，因而判断推理是中的情况，推理就是正确的，因而判断推理是否正确，就是判断是否会出现否正确，就是判断是否会出现(3)中的情况。中的情况。第十一页，讲稿共七十一页哦定义定义3.1有关说明（续）有关说明（续）n由以上的讨论可知，推理正确，并不能由以上的讨论可知，推理正确，并不能保证结论保证结论B一定为真，这与数学中的推理一定为真，这与数学中的推理是不同的。是不同的。n这个与前面我们所介绍的哪个内容非常这个与前面我们所介绍的哪个内容非常相关？相关？蕴涵联结词蕴涵联结词!第十二页，讲稿共七十一页哦例例3.1.判断推理是否正确判断推理是否正确(1)p,pq q分析：分析：定义定义3.1;真值表真值表;1 0?第十三页，讲稿共七十一页哦例例3.1（续）（续）(1)p,pq q解题：解题：p (pq),q的真值表的真值表第十四页，讲稿共七十一页哦有效推理的等价定理有效推理的等价定理n定理定理3.1 命题公式命题公式A1,A2,Ak推推B的推理正确的推理正确当且仅当当且仅当(A1 A2 Ak)B 为为重言式重言式。n证明（证明（课后练习课后练习）必要性（必要性（仅当仅当）；）；充分性（充分性（当当）。）。第十五页，讲稿共七十一页哦推理的形式结构推理的形式结构n由定理由定理3.1知，推理形式：知，推理形式：前提：前提：A1,A2,Ak结论：结论：B 是有效的当且仅当是有效的当且仅当(A1 A2 Ak)B为重言式。为重言式。(A1 A2 Ak)B称为上述推理的称为上述推理的形形式结构式结构。第十六页，讲稿共七十一页哦推理的有效性推理的有效性n推理的有效性等价于它的推理的有效性等价于它的形式结构为永形式结构为永真式真式。n即推理正确即推理正确 A1 A2 Ak B 可记为可记为 A1 A2 Ak B 其中其中 同同 一样是一种元语言符号，用一样是一种元语言符号，用来表示蕴涵式为重言式。来表示蕴涵式为重言式。第十七页，讲稿共七十一页哦推理有效性的判断方法推理有效性的判断方法n分析分析 (1)A1 A2 Ak B (2)形式结构为永真式形式结构为永真式(重言式重言式)(A1 A2 Ak)B (3)判断命题公式永真性的方法判断命题公式永真性的方法 真值表法；真值表法；等值演算法；等值演算法；主析（合）取范式法主析（合）取范式法.第十八页，讲稿共七十一页哦例例3.2.判断下面推理是否正确判断下面推理是否正确(1)若若a能被能被4整除，则整除，则a能被能被2整除；整除；a能被能被4整除。整除。所以所以a能被能被2整除整除。简单命题符号化简单命题符号化:p:a能被能被4整除整除.q:a能被能被2整除整除.前提前提:pq,p结论结论:q推理的形式结构推理的形式结构:(pq)p q 第十九页，讲稿共七十一页哦例例3.2（续）（续）可以可以真值表法真值表法或或等值演算等值演算或或主析取范式方法主析取范式方法来计算推理的形式结构是否为重言式。来计算推理的形式结构是否为重言式。p q pq(pq)p(pq)p q0 00 11 01 1110100011111第二十页，讲稿共七十一页哦例例3.2（续）（续）（练习练习）(2)下午马芳或去看电影或去游泳；她没有看电影。下午马芳或去看电影或去游泳；她没有看电影。所以，她去游泳了。所以，她去游泳了。（要求用命题等值演算法解题要求用命题等值演算法解题）(3)若下午气温超过若下午气温超过30，则王小燕必去游泳；若，则王小燕必去游泳；若她去游泳，她就不去看电影了。她去游泳，她就不去看电影了。所以王小燕没有所以王小燕没有去看电影，下午气温必超过了去看电影，下午气温必超过了30。（要求用主析取范式法解题要求用主析取范式法解题）第二十一页，讲稿共七十一页哦例例3.2（续）（续）(2)下午马芳或去下午马芳或去看电影或去游泳；看电影或去游泳；她没有看电影。她没有看电影。所以，她去游所以，她去游泳了。泳了。第二十二页，讲稿共七十一页哦例例3.2（续）（续）若下午气温超过若下午气温超过30，则王小燕必去游泳；，则王小燕必去游泳；若她去游泳，她就不去看电影了。若她去游泳，她就不去看电影了。所以王小燕没有去看电影，下午气温必超过了所以王小燕没有去看电影，下午气温必超过了30。第二十三页，讲稿共七十一页哦重言蕴涵式重言蕴涵式 n形如形如AB的重言式在推理中十分重要的重言式在推理中十分重要n若若AB为重言式，则称为重言式，则称B为为A的推论，的推论，记为记为A B n九个九个重要重要的重言蕴涵式的重言蕴涵式 推理定律。推理定律。第二十四页，讲稿共七十一页哦重言蕴涵式重言蕴涵式(1)n附加律附加律 A (A B)第二十五页，讲稿共七十一页哦重言蕴涵式重言蕴涵式(2)n化简律化简律 (A B)A第二十六页，讲稿共七十一页哦重言蕴涵式重言蕴涵式(3)n假言推理假言推理 (AB)A B 第二十七页，讲稿共七十一页哦重言蕴涵式重言蕴涵式(4)n拒取式拒取式 (AB)B A 第二十八页，讲稿共七十一页哦重言蕴涵式重言蕴涵式(5)n析取三段论析取三段论 (A B)B A 第二十九页，讲稿共七十一页哦重言蕴涵式重言蕴涵式(6)n假言三段论假言三段论 (AB)(BC)(AC)第三十页，讲稿共七十一页哦重言蕴涵式重言蕴涵式(7)n等价三段论等价三段论 (A B)(B C)(A C)第三十一页，讲稿共七十一页哦重言蕴涵式重言蕴涵式(8)n构造性二难构造性二难 (AB)(CD)(A C)(B D)n构造性二难构造性二难(特殊形式特殊形式)(AB)(AB)(A A)B 第三十二页，讲稿共七十一页哦重言蕴涵式重言蕴涵式(9)n破坏性二难破坏性二难 (AB)(CD)(B D)(A C)第三十三页，讲稿共七十一页哦24个等值式派生的推理定律个等值式派生的推理定律n2.1中的中的24个等值式中的每一个都派生个等值式中的每一个都派生出两条推理定律出两条推理定律 第三十四页，讲稿共七十一页哦16组（组（24个）重要的等值式个）重要的等值式n1.双重否定律双重否定律 A A （2.1）A A A A第三十五页，讲稿共七十一页哦课后作业课后作业(1)默写默写9个重要的重言蕴涵式；个重要的重言蕴涵式；(2)复习复习16组（组（24个）重要的等值式。个）重要的等值式。第三十六页，讲稿共七十一页哦上一节课的复习上一节课的复习n推理的形式结构推理的形式结构 (1)A1,A2,Ak B (2)(A1 A2 Ak)Bn有效推理有效推理 命题公式命题公式A1,A2,Ak推推B的推理正确的推理正确当且仅当当且仅当(A1 A2 Ak)B 为为重言式重言式。第三十七页，讲稿共七十一页哦上一节课的复习（续）上一节课的复习（续）推理形式：推理形式：前提：前提：A1,A2,Ak结论：结论：B 是有效的当且仅当是有效的当且仅当(A1 A2 Ak)B 为重言式。为重言式。第三十八页，讲稿共七十一页哦3.2.自然推理系统自然推理系统Pn判断推理是否正确的三种方法：判断推理是否正确的三种方法：真值表法真值表法;等值演算法等值演算法;主析取范式法主析取范式法.演算量大，比较繁琐演算量大，比较繁琐.n用更严谨的形式推理系统描述推理用更严谨的形式推理系统描述推理第三十九页，讲稿共七十一页哦形式推理系统形式推理系统 n定义定义3.2 一个形式系统一个形式系统I由下面四个部分组成：由下面四个部分组成：（1）非空的字符表集，记作非空的字符表集，记作A(I)。（2）A(I)中符号构造的合式公式集，记作中符号构造的合式公式集，记作E(I)。（3）E(I)中一些特殊的公式组成的公理集，记作中一些特殊的公式组成的公理集，记作 AX(I)。（4）推理规则集，记作推理规则集，记作R(I)。可以将可以将I记为记为.其中其中是是I的形式语言系的形式语言系统，统，为为I的形式演算系统。的形式演算系统。第四十页，讲稿共七十一页哦形式系统的种类形式系统的种类n自然推理系统自然推理系统 它的特点是从它的特点是从任意给定的前提任意给定的前提出发，应用系统中的出发，应用系统中的推理规则进行推理演算，得到的最后命题公式是推理推理规则进行推理演算，得到的最后命题公式是推理的结论。的结论。n公理推理系统公理推理系统 它只能从它只能从若干给定的公理若干给定的公理出发，应用系统中推理出发，应用系统中推理规则进行推理演算，得到的结论是系统中的重言规则进行推理演算，得到的结论是系统中的重言式，称为系统中的式，称为系统中的定理定理。第四十一页，讲稿共七十一页哦自然推理系统自然推理系统 PnP是一个自然推理系统，因而没有公理。是一个自然推理系统，因而没有公理。故故P只有三个部分。只有三个部分。第四十二页，讲稿共七十一页哦自然推理系统自然推理系统 P（续）（续）n定义定义3.3 自然推理系统自然推理系统P定义如下：定义如下：1字母表字母表（1）命题变项符号：命题变项符号：p，q，r，,pi，qi，ri，（2）联结词符号：联结词符号：,（3）括号和逗号：括号和逗号：(,)，2合式公式合式公式 同定义同定义1.6 第四十三页，讲稿共七十一页哦自然推理系统自然推理系统 P（续）（续）3推理规则推理规则 （1）前提引入规则前提引入规则：在证明的任何步骤上都可以：在证明的任何步骤上都可以引入前提。引入前提。（2）结论引入规则结论引入规则：在证明的任何步骤上所得到：在证明的任何步骤上所得到的结论都可以作为后继证明的前提。的结论都可以作为后继证明的前提。（3）置换规则置换规则：在证明的任何步骤上，命题公：在证明的任何步骤上，命题公式中的子公式都可以用与之等值的公式置换，得式中的子公式都可以用与之等值的公式置换，得到公式序列中的又一个公式。到公式序列中的又一个公式。第四十四页，讲稿共七十一页哦自然推理系统自然推理系统 P（续）（续）3推理规则（续）推理规则（续）由由九条推理定律九条推理定律和和结论引入规则结论引入规则还可以还可以导出以下各条推理规则。导出以下各条推理规则。第四十五页，讲稿共七十一页哦（4）假言推理规则假言推理规则（或称分离规则）（或称分离规则）n若证明的公式序列中已出现过若证明的公式序列中已出现过AB和和A，则由假言推理定律，则由假言推理定律(AB)A B可知，可知，B是是AB和和A的有效结论。的有效结论。由结论引入规则可知，可将由结论引入规则可知，可将B引入到命题引入到命题序列中来。用图式表示为如下形式：序列中来。用图式表示为如下形式：第四十六页，讲稿共七十一页哦（5）附加规则附加规则 第四十七页，讲稿共七十一页哦（6）化简规则化简规则 第四十八页，讲稿共七十一页哦（7）拒取式规则拒取式规则 第四十九页，讲稿共七十一页哦（8）假言三段论规则假言三段论规则 第五十页，讲稿共七十一页哦（9）析取三段论规则析取三段论规则 第五十一页，讲稿共七十一页哦（10）构造性二难推理构造性二难推理 第五十二页，讲稿共七十一页哦（11）破坏性二难推理规则破坏性二难推理规则 第五十三页，讲稿共七十一页哦（12）合取引入规则合取引入规则 n本条规则说明，若证明的公式序列中已本条规则说明，若证明的公式序列中已出现出现A和和B，则可将，则可将A B引入序列中。引入序列中。第五十四页，讲稿共七十一页哦自然推理系统自然推理系统P中的证明中的证明nP中的证明就是由一组中的证明就是由一组P中公式作为中公式作为前提前提，利用利用P中的规则，推出中的规则，推出结论结论。当然此结论也为当然此结论也为P中公式。中公式。构造证明构造证明。第五十五页，讲稿共七十一页哦例例3.3.在自然推理系统在自然推理系统P中构造下面推理的证明中构造下面推理的证明(1)前提：前提：p q,qr,ps,s 结论：结论：r(p q)证明证明:ps 前提引入前提引入 s 前提引入前提引入 p 拒取式拒取式 p q 前提引入前提引入 q 析取三段论析取三段论 qr 前提引入前提引入 r 假言推理假言推理 r(p q)合取合取 得证得证r(p q)为有效结论为有效结论.第五十六页，讲稿共七十一页哦例例3.3（续，（续，练习练习）(2)前提：前提：p q,r q,rs 结论：结论：ps 第五十七页，讲稿共七十一页哦P的简单实际应用的简单实际应用n可以在自然推理系统可以在自然推理系统P中构造中构造数学数学和和日常日常生活生活中的一些推理，所得结论都是有效中的一些推理，所得结论都是有效的，即当各前提的合取式为真时，结论的，即当各前提的合取式为真时，结论必为真。必为真。第五十八页，讲稿共七十一页哦例例3.4 在自然推理系统在自然推理系统P中构造下面推理的证明中构造下面推理的证明 n若数若数a是实数，则它不是有理数就是无理数；若是实数，则它不是有理数就是无理数；若a不能表示成不能表示成分数，则它不是有理数；分数，则它不是有理数；a是实数且它不能表示成分数。所以是实数且它不能表示成分数。所以a是无理数。是无理数。解解 首先将简单命题符号化：首先将简单命题符号化：设设 p：a是实数。是实数。q：a是有理数。是有理数。r：a是无理数。是无理数。s：a能表示成分数。能表示成分数。前提前提：p(q r),sq,p s 结论结论：r 第五十九页，讲稿共七十一页哦例例3.4（续，（续，课后练习课后练习）前提前提：p(q r),sq,p s 结论结论：r 第六十页，讲稿共七十一页哦P中常用证明方法中常用证明方法n附加前提证明法附加前提证明法 n归谬法归谬法 第六十一页，讲稿共七十一页哦附加前提证明法附加前提证明法 有时推理的形式结构具有如下形式有时推理的形式结构具有如下形式（A1 A2 Ak)(AB)（3.5）（3.5）式中结论也为蕴涵式。此时可将结论中的前）式中结论也为蕴涵式。此时可将结论中的前件也作为推理的前提，使结论只为件也作为推理的前提，使结论只为B。即，将（。即，将（3.5）化为下述形式）化为下述形式 (A1 A2 Ak A)B（3.6）第六十二页，讲稿共七十一页哦附加前提证明法（续）附加前提证明法（续）(A1 A2 Ak)(AB)(A1 A2 Ak)(A B）(A1 A2 Ak A)B (A1 A2 Ak A)B (A1 A2 Ak A)B 因为（因为（3.5）式与（）式与（3.6）式是等值的，因而若能证明）式是等值的，因而若能证明（3.6）式是正确的，则（）式是正确的，则（3.5）式也是正确的。）式也是正确的。用形式结构（用形式结构（3.6）式证明，将）式证明，将A称为附加前提，并称此证称为附加前提，并称此证明法为明法为附加前提证明法附加前提证明法。第六十三页，讲稿共七十一页哦例例3.5 在在P中构造中构造下面推理的证明下面推理的证明 n如果小张和小王去看电影，则小李也去看电影；小赵不去看如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影时，小李也去看电影。电影时，小李也去看电影。解解 将简单命题符号化：将简单命题符号化：设设 p:小张去看电影。小张去看电影。q:小王去看电影。小王去看电影。r:小李去看电影。小李去看电影。s:小赵去看电影。小赵去看电影。前提前提：(p q)r,s p,q 结论结论：sr 证明：证明：用附加前提证明法用附加前提证明法。第六十四页，讲稿共七十一页哦例例3.5（续）（续）前提前提：(p q)r,s p,q 结论结论：sr 证明：证明：用附加前提证明法用附加前提证明法。第六十五页，讲稿共七十一页哦归谬法归谬法n在构造形式结构为在构造形式结构为(A1 A2 Ak)B 的推理证明中，如果将的推理证明中，如果将B作为前提能推作为前提能推出矛盾来，比如说得出出矛盾来，比如说得出(A A)，则说明，则说明推理正确。推理正确。第六十六页，讲稿共七十一页哦归谬法（续）归谬法（续）(A1 A2 Ak)B (A1 A2 Ak)B (A1 A2 Ak B)若若(A1 A2 Ak B)为矛盾式，正说明为矛盾式，正说明(A1 A2 Ak)B为重言式，即为重言式，即(A1 A2 Ak)B,故推理正确。故推理正确。这种将这种将结论的否定式结论的否定式作为作为附加前提引入附加前提引入并推出并推出矛矛盾式盾式的证明方法称为的证明方法称为归谬法归谬法。第六十七页，讲稿共七十一页哦例例3.6.在在P中构造中构造下面推理的证明（下面推理的证明（练习练习）n如果小张守第一垒并且小李向如果小张守第一垒并且小李向B队投球，队投球，则则A队将取胜；或者队将取胜；或者A队未取胜，或者队未取胜，或者A队获得联赛第一名；队获得联赛第一名；A队没有获得联赛的队没有获得联赛的第一名；小张守第一垒。因此，小李没第一名；小张守第一垒。因此，小李没有向有向B队投球。队投球。（1）用归谬法证明；用归谬法证明；（2）不用归谬法证明。）不用归谬法证明。第六十八页，讲稿共七十一页哦例例3.6（续）（续）第六十九页，讲稿共七十一页哦课后作业课后作业习题三习题三 第第14(-1,-3,-4,-6),15,16,18题题 （第（第53,54页）页）.第七十页，讲稿共七十一页哦谢谢 谢谢 !第七十一页，讲稿共七十一页哦