命题逻辑的推理理论 (2).ppt
命题逻辑的推理理论命题逻辑的推理理论现在学习的是第1页，共13页第二章第二章命题逻辑等值演算命题逻辑等值演算推理的形式结构推理的形式结构自然推理系统自然推理系统P知知识识点：推理的形式结构、推理理论、自然系统点：推理的形式结构、推理理论、自然系统P、推理规则、推理规则教学要求：深刻理解和掌握命题逻辑中的基本推理方法教学要求：深刻理解和掌握命题逻辑中的基本推理方法教学重点：推理理论、推理规则教学重点：推理理论、推理规则学时学时:22023/3/31现在学习的是第2页，共13页3.1推理的形式结构推理的形式结构论证是指由一些前提出发得到某个结论，在数理逻辑中论证是指由一些前提出发得到某个结论，在数理逻辑中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的的逻辑结果逻辑结果当前提为真时结论也为真当前提为真时结论也为真,但推理正确并不能保证有效结论但推理正确并不能保证有效结论B一定为真一定为真例如：设例如：设p为为“太阳从西边升起太阳从西边升起”,q为为”太阳从东边落下太阳从东边落下”pq为为“如果太如果太阳从西边升起则太阳从东边落下阳从西边升起则太阳从东边落下”推理推理p,pqq是正确的是正确的,即即q是前提是前提的有效结论的有效结论,但但q是个假命题是个假命题2023/3/31现在学习的是第3页，共13页3.1推理的形式结构推理的形式结构推理的形式结构推理的形式结构:前提前提:A1,A2,An结论结论:B重要的推理定律重要的推理定律nABA,A BB(化简律化简律)AA B,BA B(附加律附加律)n(AB)AB(假言推论假言推论)n(AB)BA(拒取式拒取式)n(A B)BA(析取三段论析取三段论)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)破坏性二难破坏性二难2023/3/31现在学习的是第4页，共13页3.1推理的形式结构推理的形式结构论证的方法论证的方法n真值表法真值表法n等值演算法等值演算法n将推理过程形式化将推理过程形式化证明公式证明公式A1 A2 AnB是重言式是重言式即即证明证明(A1 A2 AnB)1形式系统一般分为两类形式系统一般分为两类一类是自然推理系统，它的特点是从任意一类是自然推理系统，它的特点是从任意给定的前提出发，应用系统中的推理规则进行给定的前提出发，应用系统中的推理规则进行推理演算，得到的最后命题公式是推理的结论推理演算，得到的最后命题公式是推理的结论（有时称为有效的结论，它可能是重言式，也（有时称为有效的结论，它可能是重言式，也可能不是）可能不是）一类是公理推理系统，它只能从若干给定一类是公理推理系统，它只能从若干给定的公理出发，应用系统中推理规则进行推理演的公理出发，应用系统中推理规则进行推理演算，得到的结论是系统中的重言式，称为系统算，得到的结论是系统中的重言式，称为系统中的定理。中的定理。2023/3/31现在学习的是第5页，共13页3.2自然推理系统自然推理系统P定定义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）联结词符号：）联结词符号：,（3）括号和逗号：）括号和逗号：(,)，2合式公式合式公式同定义同定义1.63推理规则推理规则2023/3/31现在学习的是第6页，共13页3.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定理定理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,AnBC2023/3/31现在学习的是第7页，共13页3.2自然推理系统自然推理系统PP规则规则在推演过程中可以随时引用前提在推演过程中可以随时引用前提T规则规则在推演过程中可以随时引用前面已经得到的结论在推演过程中可以随时引用前面已经得到的结论CP规则规则若若A1,A2,An,BC则则A1,A2,An(BC)B称为附加前提称为附加前提在推理过程中可以随时使用重言等价式在推理过程中可以随时使用重言等价式(E)在推理过程中可以随时使用重言蕴涵式在推理过程中可以随时使用重言蕴涵式(I)在推理过程中可以随时引用置换规则和代入替则在推理过程中可以随时引用置换规则和代入替则2023/3/31现在学习的是第8页，共13页3.2自然推理系统自然推理系统P直接证明法：由一组前提遵循直接证明法：由一组前提遵循P规则和规则和T规则规则,根据已知的重言等价式和重言蕴涵式根据已知的重言等价式和重言蕴涵式推演出有效结论的论证方法推演出有效结论的论证方法例例1前提：前提：p q,qr,ps,s结论：结论：r(p q)证明：证明：ps前提引入前提引入s前提引入前提引入p拒取式拒取式p q前提引入前提引入q析取三段论析取三段论qr前提引入前提引入r假言推理假言推理r(p q)合取合取此证明的序列长为此证明的序列长为8，最后一步为推理的结论，所以推理正确，最后一步为推理的结论，所以推理正确，r(p q)是有效结论。是有效结论。2023/3/31现在学习的是第9页，共13页3.2自然推理系统自然推理系统P例例2:在自然推理系统在自然推理系统P中构造下面推理的证明：中构造下面推理的证明：若数若数a是实数，则它不是有理数就是无理数；若是实数，则它不是有理数就是无理数；若a不能表示成分数，则它不能表示成分数，则它不是有理数；不是有理数；a是实数且它不能表示成分数。所以是实数且它不能表示成分数。所以a是无理数。是无理数。解解首先将简单命题符号化：首先将简单命题符号化：证明：证明：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 sr2023/3/31现在学习的是第10页，共13页3.2自然推理系统自然推理系统P间接证明法：由一组前提遵循间接证明法：由一组前提遵循P规则、规则、T规则和规则和CP规则推演出有效结论规则推演出有效结论,或者或者将否定结论作为附加前提将否定结论作为附加前提,利用利用P规则和规则和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原故推理是正确原故推理是正确2023/3/31现在学习的是第11页，共13页3.2自然推理系统自然推理系统P例例3在自然推理系统在自然推理系统P中构造下面推理的证明。中构造下面推理的证明。如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影时，小李也去看电影。小王去看电影。所以，当小赵去看电影时，小李也去看电影。解解将简单命题符号化：将简单命题符号化：前提：前提：(p q)r,s p,q结论：结论：sr证明：用附加前提证明法。证明：用附加前提证明法。s附加前提引入附加前提引入s p前提引入前提引入p析取三段论析取三段论(p q)r前提引入前提引入q前提引入前提引入p q合取合取r假言推理假言推理设设p:小张去看电影小张去看电影,q:小王去看电影小王去看电影,r:小李去看电影小李去看电影,s:小赵去看电影小赵去看电影2023/3/31现在学习的是第12页，共13页3.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,pq2023/3/31现在学习的是第13页，共13页
