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

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

1、漳州师范学院计算机科学与工程系漳州师范学院计算机科学与工程系第三章第三章命题逻辑的推理理论命题逻辑的推理理论第二章第二章命题逻辑等值演算命题逻辑等值演算推理的形式结构推理的形式结构自然推理系统自然推理系统P知知识识点：推理的形式结构、推理理论、自然系统点：推理的形式结构、推理理论、自然系统P、推理规则、推理规则教学要求：深刻理解和掌握命题逻辑中的基本推理方法教学要求：深刻理解和掌握命题逻辑中的基本推理方法教学重点：推理理论、推理规则教学重点：推理理论、推理规则学时学时:22022/12/293.1推理的形式结构推理的形式结构论证是指由一些前提出发得到某个结论，在数理逻辑中论证是指由一些前提出发

2、得到某个结论，在数理逻辑中n需要讨论论证的有效性需要讨论论证的有效性n提出正确的推理规则和可行的推理方法提出正确的推理规则和可行的推理方法A1,A2,An为前提为前提,B为结论为结论称称A1,A2,AnB为推理的形式结构为推理的形式结构定理定理3.1命题公式命题公式A1,A2,An推推B是正确的当且仅当是正确的当且仅当A1 A2 AnB为重言式为重言式,即即A1 A2 AnBn并称并称B为前提为前提A1,A2,An的的有效结论有效结论n或称或称B为前提为前提A1,A2,An的的逻辑结果逻辑结果当前提为真时结论也为真当前提为真时结论也为真,但推理正确并不能保证有效结论但推理正确并不能保证有效结论

3、B一定为真一定为真例如：设例如：设p为为“太阳从西边升起太阳从西边升起”,q为为”太阳从东边落下太阳从东边落下”pq为为“如果太如果太阳从西边升起则太阳从东边落下阳从西边升起则太阳从东边落下”推理推理p,pqq是正确的是正确的,即即q是前提是前提的有效结论的有效结论,但但q是个假命题是个假命题2022/12/293.1推理的形式结构推理的形式结构推理的形式结构推理的形式结构:前提前提:A1,A2,An结论结论:B重要的推理定律重要的推理定律nABA,A BB(化简律化简律)AA B,BA B(附加律附加律)n(AB)AB(假言推论假言推论)n(AB)BA(拒取式拒取式)n(A B)BA(析取三

4、段论析取三段论)n(AB)(BC)AC(假言三段论假言三段论)n(AB)(BC)AC(等价三段论等价三段论)n(AB)(CD)(A C)(B D)(构造性二难构造性二难)(AB)(AB)B构造性二难构造性二难(特殊形式特殊形式)n(AB)(CD)(B D)(A C)破坏性二难破坏性二难2022/12/293.1推理的形式结构推理的形式结构论证的方法论证的方法n真值表法真值表法n等值演算法等值演算法n将推理过程形式化将推理过程形式化证明公式证明公式A1 A2 AnB是重言式是重言式即即证明证明(A1 A2 AnB)1形式系统一般分为两类形式系统一般分为两类一类是一类是自然推理系统自然推理系统，它

5、的特点是从，它的特点是从任意给定的前提出发，应用系统中的推理任意给定的前提出发，应用系统中的推理规则进行推理演算，得到的最后命题公式规则进行推理演算，得到的最后命题公式是推理的结论（有时称为有效的结论，它是推理的结论（有时称为有效的结论，它可能是重言式，也可能不是）可能是重言式，也可能不是）一类是公理推理系统，它只能从若干一类是公理推理系统，它只能从若干给定的公理出发，应用系统中推理规则进给定的公理出发，应用系统中推理规则进行推理演算，得到的结论是系统中的行推理演算，得到的结论是系统中的重言重言式式，称为系统中的定理。，称为系统中的定理。2022/12/293.2自然推理系统自然推理系统P定定

6、义3.2一个一个形式系形式系统I由下面四个部分组成：由下面四个部分组成：（1）非空的字符表集，记作非空的字符表集，记作A(I)（2）A(I)中符号构造的合式公式集，记作中符号构造的合式公式集，记作E(I)（3）E(I)中一些特殊的公式组成的公理集，记作中一些特殊的公式组成的公理集，记作AX(I)（4）推理规则集，记作推理规则集，记作R(I)可以将可以将I记为记为其中其中是是I的的形式形式语言系言系统为为I的的形式演算系形式演算系统。定定义3.3自然推理系自然推理系统P定义如下：定义如下：1字母表字母表（1）命题变项符号：）命题变项符号：p，q，r，,pi，qi，ri，（2）联结词符号：）联结词

7、符号：,（3）括号和逗号：）括号和逗号：(,)，2合式公式合式公式同同定义定义1.63推理规则推理规则2022/12/293.2自然推理系统自然推理系统P定理定理3.1A1,A2,AnAi,i=1,2,n证明证明因为因为A1 A2 An(A1 A2 Ai1 Ai+1 An)AiAi所以所以A1,A2,AnAi定理定理3.2若若A1,A2,AnBi,i=1,2,m且且B1,B2,BmC,则则A1,A2,AnC证明证明由重言蕴涵的性质和题设可知由重言蕴涵的性质和题设可知A1 A2 AnB1 B2 Bm再由重言蕴涵的传递性可知再由重言蕴涵的传递性可知A1 A2 AnC,即即A1,A2,AnC定理定理

8、3.3若若A1,A2,An,BC,则则A1,A2,An(BC)证明证明因为因为A1,A2,An,BC,所以所以1A1 A2 An BC(A1 A2 An B)C(A1 A2 An)B C(A1 A2 An)(BC)(A1 A2 An)(BC)即即A1,A2,AnBC2022/12/293.2自然推理系统自然推理系统PP规则规则在推演过程中可以随时引用前提在推演过程中可以随时引用前提T规则规则在推演过程中可以随时引用前面已经得到的结论在推演过程中可以随时引用前面已经得到的结论CP规则规则若若A1,A2,An,BC则则A1,A2,An(BC)B称为附加前提称为附加前提在推理过程中可以随时使用重言等

9、价式在推理过程中可以随时使用重言等价式(E)在推理过程中可以随时使用重言蕴涵式在推理过程中可以随时使用重言蕴涵式(I)在推理过程中可以随时引用置换规则和代入替则在推理过程中可以随时引用置换规则和代入替则2022/12/293.2自然推理系统自然推理系统P直接证明法：由一组前提遵循直接证明法：由一组前提遵循P规则和规则和T规则规则,根据已知的重言等价式根据已知的重言等价式和重言蕴涵式推演出有效结论的论证方法和重言蕴涵式推演出有效结论的论证方法例例1前提：前提：p q,qr,ps,s结论：结论：r(p q)证明：证明：ps前提引入前提引入s前提引入前提引入p拒取式拒取式p q前提引入前提引入q析取

10、三段论析取三段论qr前提引入前提引入r假言推理假言推理r(p q)合取合取此证明的序列长为此证明的序列长为8，最后一步为推理的结论，所以推理正确，最后一步为推理的结论，所以推理正确，r(p q)是有效结论。是有效结论。2022/12/293.2自然推理系统自然推理系统P例例2:在自然推理系统在自然推理系统P中构造下面推理的证明：中构造下面推理的证明：若数若数a是实数，则它不是有理数就是无理数；若是实数，则它不是有理数就是无理数；若a不能表示成分数，不能表示成分数，则它不是有理数；则它不是有理数；a是实数且它不能表示成分数。所以是实数且它不能表示成分数。所以a是无理数。是无理数。解解首先将简单命

11、题符号化：首先将简单命题符号化：证明：证明：p s前提引入前提引入p化简律化简律s化简律化简律p(q r)前提引入前提引入q r假言推理假言推理sq前提引入前提引入q假言推理假言推理r假言推理假言推理设设p:a是实数是实数,q:a是有理数是有理数,r:a是无理数是无理数,s:a能表示成分数能表示成分数推理的形式结构为推理的形式结构为p(q r),sq,p sr2022/12/293.2自然推理系统自然推理系统P间接证明法：由一组前提遵循间接证明法：由一组前提遵循P规则、规则、T规则和规则和CP规则推演出有效结论规则推演出有效结论,或者将否定结论作为附加前提或者将否定结论作为附加前提,利用利用P

12、规则和规则和T规则得出矛盾式的论证规则得出矛盾式的论证方法。后一种情形又称为反证法方法。后一种情形又称为反证法在构造形式结构为在构造形式结构为(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原故推理是正确原故推理是正确2022/12/293.2自然推理系

13、统自然推理系统P例例3在在自然推理系统自然推理系统P中构造下面推理的证明。中构造下面推理的证明。如果小张和小王去看电影，则小李也去看电影；小赵不去看电影如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影时，小李也或小张去看电影；小王去看电影。所以，当小赵去看电影时，小李也去看电影。去看电影。解解将简单命题符号化：将简单命题符号化：前提：前提：(p q)r,s p,q结论：结论：sr证明：用附加前提证明法。证明：用附加前提证明法。s附加前提引入附加前提引入s p前提引入前提引入p析取三段论析取三段论(p q)r前提引入前提引入q前提引入前提

14、引入p q合取合取r假言推理假言推理设设p:小张去看电影小张去看电影,q:小王去看电影小王去看电影,r:小李去看电影小李去看电影,s:小赵去看电影小赵去看电影2022/12/293.2自然推理系统自然推理系统P例例4：在在自然推理系统自然推理系统A中构造下面推理的证明。中构造下面推理的证明。如果小张守第一垒并且小李向如果小张守第一垒并且小李向B队投球，则队投球，则A队将取胜；或者队将取胜；或者A队未取队未取胜，或者胜，或者A队获得联赛第一名；队获得联赛第一名；A队没有获得联赛的第一名；小张守第一垒。队没有获得联赛的第一名；小张守第一垒。因此，小李没有向因此，小李没有向B队投球。队投球。证明证明:q结论的否定引入结论的否定引入r s前提引入前提引入s前提引入前提引入r析取三段论析取三段论(p q)r前提引入前提引入(p q)假言推理假言推理p q置换置换p前提引入前提引入q析取三段论析取三段论q q合取合取由于最后一步由于最后一步q q0，即原推理正确，即原推理正确先将简单命题符号化先将简单命题符号化设设p:小张守第一垒小张守第一垒q:小李向小李向B队投球队投球r:A队取胜队取胜s:A队获得联赛第一名队获得联赛第一名推理的形式结构推理的形式结构(p q)r,r s,s,pq2022/12/29