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

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

1、命题逻辑的推理理论命题逻辑的推理理论第一页，讲稿共十三页哦第二章第二章 命题逻辑等值演算命题逻辑等值演算推理的形式结构推理的形式结构自然推理系统自然推理系统P知知 识识 点：推理的形式结构、推理理论、自然系统点：推理的形式结构、推理理论、自然系统P、推理规则、推理规则教学要求：深刻理解和掌握命题逻辑中的基本推理方法教学要求：深刻理解和掌握命题逻辑中的基本推理方法 教学重点：推理理论、推理规则教学重点：推理理论、推理规则学时学时:22022-9-5第二页，讲稿共十三页哦3.1 推理的形式结构推理的形式结构 论证是指由一些前提出发得到某个结论，在数理逻辑中论证是指由一些前提出发得到某个结论，在数理

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

3、证有效结论B一定为真一定为真 例如：设例如：设p为为“太阳从西边升起太阳从西边升起”,q为为”太阳从东边落下太阳从东边落下”pq为为“如果太如果太阳从西边升起则太阳从东边落下阳从西边升起则太阳从东边落下”推理推理 p,pq q是正确的是正确的,即即q是前提是前提的有效结论的有效结论,但但q是个假命题是个假命题2022-9-5第三页，讲稿共十三页哦3.1 推理的形式结构推理的形式结构推理的形式结构推理的形式结构:前提前提:A1,A2,An 结论结论:B重要的推理定律重要的推理定律nABA,ABB (化简律化简律)AAB,BAB(附加律附加律)n(A B)A B (假言推论假言推论)n(AB)B

4、A (拒取式拒取式)n(AB)B A (析取三段论析取三段论)n(AB)(B C)AC (假言三段论假言三段论)n(AB)(BC)AC (等价三段论等价三段论)n(AB)(CD)(AC)(BD)(构造性二难构造性二难)(AB)(AB)B 构造性二难构造性二难(特殊形式特殊形式)n(AB)(CD)(BD)(AC)破坏性二难破坏性二难2022-9-5第四页，讲稿共十三页哦3.1 推理的形式结构推理的形式结构论证的方法论证的方法n真值表法真值表法n等值演算法等值演算法n将推理过程形式化将推理过程形式化证明公式 A1A2An B 是重言式即 证明 (A1A2An B)1形式系统一般分为两类 一类是自然

5、推理系统，它的特点是从任意给定的前提出发，应用系统中的推理规则进行推理演算，得到的最后命题公式是推理的结论（有时称为有效的结论，它可能是重言式，也可能不是）一类是公理推理系统，它只能从若干给定的公理出发，应用系统中推理规则进行推理演算，得到的结论是系统中的重言式，称为系统中的定理。2022-9-5第五页，讲稿共十三页哦3.2 自然推理系统自然推理系统P定义定义3.2 一个一个形式系统形式系统I由下面四个部分组成：由下面四个部分组成：（1）非空的字符表集，记作非空的字符表集，记作A(I)（2）A(I)中符号构造的合式公式集，记作中符号构造的合式公式集，记作E(I)（3）E(I)中一些特殊的公式组

6、成的公理集，记作中一些特殊的公式组成的公理集，记作AX(I)（4）推理规则集，记作推理规则集，记作R(I)可以将可以将 I 记为记为 其中其中 是是I的的形式语言系统形式语言系统 为为I的的形式演算系统形式演算系统。定义定义3.3 自然推理系统自然推理系统P定义如下：定义如下：1字母表字母表 （1）命题变项符号：）命题变项符号：p，q，r，,pi，qi，ri，（2）联结词符号：）联结词符号：,（3）括号和逗号：）括号和逗号：(,)，2合式公式合式公式 同定义同定义1.6 3推理规则推理规则2022-9-5第六页，讲稿共十三页哦3.2 自然推理系统自然推理系统P定理定理3.1 A1,A2,An

7、Ai,i=1,2,n 证明证明 因为因为 A1 A2 An (A1 A2 Ai1 Ai+1 An)Ai Ai 所以所以 A1,A2,An Ai 定理定理3.2 若若A1,A2,An Bi,i=1,2,m 且且B1,B2,Bm C,则则 A1,A2,An C 证明证明 由重言蕴涵的性质和题设可知由重言蕴涵的性质和题设可知 A1 A2 An B1 B2 Bm 再由重言蕴涵的传递性可知再由重言蕴涵的传递性可知 A1 A2 An C,即即A1,A2,An C定理定理3.3 若若A1,A2,An,B C,则则A1,A2,An (BC)证明证明 因为因为A1,A2,An,B C,所以所以 1 A1 A2

8、An BC (A1 A2 An B)C (A1 A2 An)B C (A1 A2 An)(BC)(A1 A2 An)(BC)即即A1,A2,An BC 2022-9-5第七页，讲稿共十三页哦3.2 自然推理系统自然推理系统PP规则规则 在推演过程中可以随时引用前提在推演过程中可以随时引用前提 T规则规则 在推演过程中可以随时引用前面已经得到的结论在推演过程中可以随时引用前面已经得到的结论 CP规则规则 若若A1,A2,An,B C 则则A1,A2,An (BC)B称为附加前提称为附加前提 在推理过程中可以随时使用重言等价式在推理过程中可以随时使用重言等价式(E)在推理过程中可以随时使用重言蕴涵

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

10、入 r 假言推理假言推理 r(pq)合取合取 此证明的序列长为此证明的序列长为8，最后一步为推理的结论，所以推理正确，最后一步为推理的结论，所以推理正确，r(pq)是有效是有效结论。结论。2022-9-5第九页，讲稿共十三页哦3.2 自然推理系统自然推理系统P例例2:在自然推理系统在自然推理系统P中构造下面推理的证明：中构造下面推理的证明：若数若数a是实数，则它不是有理数就是无理数；若是实数，则它不是有理数就是无理数；若a不能表示成分数，则它不是不能表示成分数，则它不是有理数；有理数；a是实数且它不能表示成分数。所以是实数且它不能表示成分数。所以a是无理数。是无理数。解解 首先将简单命题符号化

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

12、规则得出矛盾式的论证方法。后一种情形又称为反规则得出矛盾式的论证方法。后一种情形又称为反证法证法 在构造形式结构为在构造形式结构为 (A1A2Ak)B的推理证明中，如果将的推理证明中，如果将B作为前提能作为前提能推出矛盾来，比如说得出推出矛盾来，比如说得出(AA)，则说明推理正确。其原因如下：，则说明推理正确。其原因如下：(A1A2Ak)B (A1A2Ak)B (A1A2AkB)若若(A1A2AkB)为矛盾式，正说明为矛盾式，正说明(A1A2Ak)B为重言式，为重言式，即即(A1A2Ak)B 原故推理是正确原故推理是正确2022-9-5第十一页，讲稿共十三页哦3.2 自然推理系统自然推理系统P

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

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