命题逻辑的推理理论.ppt

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