命题逻辑的推理理论.ppt

,漳州师范学院计算机科学与工程系,第三章命题逻辑的推理理论,2020年5月19日8时52分,第二章命题逻辑等值演算,推理的形式结构自然推理系统P知识点：推理的形式结构、推理理论、自然系统P、推理规则教学要求：深刻理解和掌握命题逻辑中的基本推理方法教学重点：推理理论、推理规则学时:2,2020年5月19日8时52分,3.1推理的形式结构,论证是指由一些前提出发得到某个结论，在数理逻辑中需要讨论论证的有效性提出正确的推理规则和可行的推理方法A1,A2,An为前提,B为结论称A1,A2,AnB为推理的形式结构定理3.1命题公式A1,A2,An推B是正确的当且仅当A1A2AnB为重言式,即A1A2AnB并称B为前提A1,A2,An的有效结论或称B为前提A1,A2,An的逻辑结果当前提为真时结论也为真,但推理正确并不能保证有效结论B一定为真例如：设p为“太阳从西边升起”,q为”太阳从东边落下”pq为“如果太阳从西边升起则太阳从东边落下”推理p,pqq是正确的,即q是前提的有效结论,但q是个假命题,2020年5月19日8时52分,3.1推理的形式结构,推理的形式结构:前提:A1,A2,An结论:B重要的推理定律ABA,ABB(化简律)AAB,BAB(附加律)(AB)AB(假言推论)(AB)BA(拒取式)(AB)BA(析取三段论)(AB)(BC)AC(假言三段论)(AB)(BC)AC(等价三段论)(AB)(CD)(AC)(BD)(构造性二难)(AB)(AB)B构造性二难(特殊形式)(AB)(CD)(BD)(AC)破坏性二难,2020年5月19日8时52分,3.1推理的形式结构,论证的方法真值表法等值演算法将推理过程形式化,证明公式A1A2AnB是重言式即证明(A1A2AnB)1,形式系统一般分为两类一类是自然推理系统，它的特点是从任意给定的前提出发，应用系统中的推理规则进行推理演算，得到的最后命题公式是推理的结论（有时称为有效的结论，它可能是重言式，也可能不是）一类是公理推理系统，它只能从若干给定的公理出发，应用系统中推理规则进行推理演算，得到的结论是系统中的重言式，称为系统中的定理。,2020年5月19日8时52分,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推理规则,2020年5月19日8时52分,3.2自然推理系统P,定理3.1A1,A2,AnAi,i=1,2,n证明因为A1A2An(A1A2Ai1Ai+1An)AiAi所以A1,A2,AnAi定理3.2若A1,A2,AnBi,i=1,2,m且B1,B2,BmC,则A1,A2,AnC证明由重言蕴涵的性质和题设可知A1A2AnB1B2Bm再由重言蕴涵的传递性可知A1A2AnC,即A1,A2,AnC定理3.3若A1,A2,An,BC,则A1,A2,An(BC)证明因为A1,A2,An,BC,所以1A1A2AnBC(A1A2AnB)C(A1A2An)BC(A1A2An)(BC)(A1A2An)(BC)即A1,A2,AnBC,2020年5月19日8时52分,3.2自然推理系统P,P规则在推演过程中可以随时引用前提T规则在推演过程中可以随时引用前面已经得到的结论CP规则若A1,A2,An,BC则A1,A2,An(BC)B称为附加前提在推理过程中可以随时使用重言等价式(E)在推理过程中可以随时使用重言蕴涵式(I)在推理过程中可以随时引用置换规则和代入替则,2020年5月19日8时52分,3.2自然推理系统P,直接证明法：由一组前提遵循P规则和T规则,根据已知的重言等价式和重言蕴涵式推演出有效结论的论证方法例1前提：pq,qr,ps,s结论：r(pq)证明：ps前提引入s前提引入p拒取式pq前提引入q析取三段论qr前提引入r假言推理r(pq)合取此证明的序列长为8，最后一步为推理的结论，所以推理正确，r(pq)是有效结论。,2020年5月19日8时52分,3.2自然推理系统P,例2:在自然推理系统P中构造下面推理的证明：若数a是实数，则它不是有理数就是无理数；若a不能表示成分数，则它不是有理数；a是实数且它不能表示成分数。所以a是无理数。解首先将简单命题符号化：证明：ps前提引入p化简律s化简律p(qr)前提引入qr假言推理sq前提引入q假言推理r假言推理,设p:a是实数,q:a是有理数,r:a是无理数,s:a能表示成分数推理的形式结构为p(qr),sq,psr,2020年5月19日8时52分,3.2自然推理系统P,间接证明法：由一组前提遵循P规则、T规则和CP规则推演出有效结论,或者将否定结论作为附加前提,利用P规则和T规则得出矛盾式的论证方法。后一种情形又称为反证法在构造形式结构为(A1A2Ak)B的推理证明中，如果将B作为前提能推出矛盾来，比如说得出(AA)，则说明推理正确。其原因如下：(A1A2Ak)B(A1A2Ak)B(A1A2AkB)若(A1A2AkB)为矛盾式，正说明(A1A2Ak)B为重言式，即(A1A2Ak)B原故推理是正确,2020年5月19日8时52分,3.2自然推理系统P,例3在自然推理系统P中构造下面推理的证明。如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影时，小李也去看电影。解将简单命题符号化：前提：(pq)r,sp,q结论：sr证明：用附加前提证明法。s附加前提引入sp前提引入p析取三段论(pq)r前提引入q前提引入pq合取r假言推理,设p:小张去看电影,q:小王去看电影,r:小李去看电影,s:小赵去看电影,2020年5月19日8时52分,3.2自然推理系统P,例4：在自然推理系统A中构造下面推理的证明。如果小张守第一垒并且小李向B队投球，则A队将取胜；或者A队未取胜，或者A队获得联赛第一名；A队没有获得联赛的第一名；小张守第一垒。因此，小李没有向B队投球。证明:q结论的否定引入rs前提引入s前提引入r析取三段论(pq)r前提引入(pq)假言推理pq置换p前提引入q析取三段论qq合取由于最后一步qq0，即原推理正确,先将简单命题符号化设p:小张守第一垒q:小李向B队投球r:A队取胜s:A队获得联赛第一名推理的形式结构(pq)r,rs,s,pq,