目录
主要内容
推理的形式结构推理的正确与错误推理的形式结构判断推理正确的方法推理定律
自然推理系统P
形式系统的定义与分类自然推理系统 P在 P 中构造证明 : 直接证明法、附加前提证明法、归谬法
定义3.1 设A1, A2, …, Ak, B为命题公式. 若对于每组赋值，A1∧A2∧…∧ Ak 为假，或当A1∧A2∧…∧Ak为真时，B也为真，则称由前提A1, A2, …, Ak推出结论B的推理是有效的或正确的, 并称B是有效结论
定理 3.1 由命题公式 A 1 , A 2 , …, A k 推 B 的推理正确当且仅当 A 1 ∧ A 2 ∧ … ∧ A k → B 为重言式注意 : 推理正确不能保证结论一定正确判断推理是否正确的方法 :真值表法等值演算法主析取范式法
?例1 判断下面推理是否正确
(1) 若今天是 1 号，则明天是 5 号 . 今天是 1 号 . 所以 , 明天是 5 号 .(2) 若今天是 1 号，则明天是 5 号 . 明天是 5 号 . 所以 , 今天是 1 号 .解设 p ：今天是 1 号， q ：明天是 5 号 .(1) 推理的形式结构 : ( p → q ) ∧ p → q用等值演算法( p → q ) ∧ p → q? ? (( ? p ∨ q ) ∧ p ) ∨ q? ? p ∨? q ∨ q ? 1由定理 3.1 可知推理正确(2) 推理的形式结构 : ( p → q ) ∧ q → p用主析取范式法( p → q ) ∧ q → p? ( ? p ∨ q ) ∧ q → p? ? (( ? p ∨ q ) ∧ q ) ∨ p? ? q ∨ p? ( ? p ∧? q ) ∨ ( p ∧? q ) ∨ ( p ∧? q ) ∨ ( p ∧ q )? m 0 ∨ m 2 ∨ m 3结果不含 m 1 , 故 01 是成假赋值，所以推理不正确
推理定律——重言蕴涵式?
附加律??????????A ? (A ∨ B )化简律??????????(A∧ B ) ? A假言推理??????????(A → B ) ∧ A ? B拒取式??????????(A → B ) ∧? B ? ? A析取三段论??????????(A ∨ B ) ∧? B ? A假言三段论??????????(A → B ) ∧ ( B → C ) ? ( A → C )等价三段论??????????(A ? B ) ∧ ( B ? C ) ? ( A ? C )构造性二难??????????(A → B ) ∧ ( C → D ) ∧ ( A ∨ C ) ? ( B ∨ D )构造性二难 ( 特殊形式 )??????????(A → B ) ∧ ( ? A → B ) ? B破坏性二难??????????(A → B ) ∧ ( C → D ) ∧ ( ? B ∨? D ) ? ( ? A ∨? C )每个等值式可产生两个推理定律如由 A ??? A 可产生 A ??? A 和 ?? A ? A
?定义3.2 一个形式系统 I 由下面四个部分组成：
(1) 非空的字母表，记作 A ( I ) .(2) A ( I ) 中符号构造的合式公式集，记作 E ( I )(3) E ( I ) 中一些特殊的公式组成的公理集，记作 A X ( I ) .(4) 推理规则集，记作 R ( I ) .记 I =< A ( I ), E ( I ), A X ( I ), R ( I )>, 其中 < A ( I ), E ( I ), A X ( I ), R ( I )> 是 I 的形式语言系统 , < A ( I ), E ( I ), A X ( I ), R ( I )> 是 I 的 形式演算系统 .自然推理系统 : 无公理 , 即 A X ( I )= ?公理推理系统 推出的结论是系统中的重言式 , 称作 定理我认为这里不是很重要
定义 3.3 自然推理系统P 定义如下 :1. 字母表(1) 命题变项符号： p , q , r , …, p i , q i , r i , …(2) 联结词符号： ? , ∧ , ∨ , → , ?(3) 括号与逗号： (, ), ，2. 合式公式推理规则(与推理定律差不多)
(1) 前提引入规则(2) 结论引入规则(3) 置换规则(4) 假言推理规则
????????A→ B????????A?——————????????∴B(5) 附加规则????????A——————? ? ?∴A ∨ B(6) 化简规则????????A∧ B——————????????∴ A(7) 拒取式规则????????A→ B?????????B——————????????∴? A(8) 假言三段论规则????????A→B????????????????B→ C——————???? ?∴A → C(9) 析取三段论规则????????A∨ B?????????B——————????????∴A(10) 构造性二难推理规则????????A→ B????????C→ D????????A∨ C——————??????∴B ∨ D(11) 破坏性二难推理规则????????A→ B????????C→ D??????B ∨? D——————?????∴? A ∨? C(12) 合取引入规则????????A????????B——————????∴A ∧ C
例2 构造下面推理的证明：
若明天是星期一或星期三，我明天就有课 . 若我明天有课，今天必备课 . 我今天没备课 . 所以，明天不是星期一、也不是星期三 .解(1) 设命题并符号化设 p ：明天是星期一， q ：明天是星期三，r ：我明天有课， s ：我今天备课(2) 写出证明的形式结构前提： ( p ∨ q ) → r , r → s , ? s结论： ? p ∧? q(3) 证明① r →s????????前提引入② ?s????????前提引入③ ? r ????????①②拒取式④ ( p ∨ q ) →r???????? 前提引入⑤ ? ( p ∨ q)???????? ③④拒取式⑥ ? p ∧?q ????????⑤置换规则
附加前提证明法 适用于结论为蕴涵式
欲证前提： A 1 , A 2 , …, A k结论： C → B等价地证明前提： A 1 , A 2 , …, A k , C结论：B将C也当作条件理由：( A 1 ∧ A 2 ∧ … ∧ A k ) → ( C → B )? ? ( A 1 ∧ A 2 ∧ … ∧ A k ) ∨ ( ? C ∨ B )? ? ( A 1 ∧ A 2 ∧ … ∧ A k ∧ C ) ∨ B? ( A 1 ∧ A 2 ∧ … ∧ A k ∧ C ) → B
例3 构造下面推理的证明
2 是素数或合数 . 若 2 是素数，则 是无理数 . 若 是无理数，则 4 不是素数 . 所以，如果 4 是素数，则 2 是合数 .解 用附加前提证明法构造证明(1) 设 p ： 2 是素数， q ： 2 是合数，r ： 是无理数， s ： 4 是素数(2) 推理的形式结构前提： p ∨ q , p → r , r →? s结论： s → q(3) 证明① s??????????附加前提引入② p →r??????????前提引入③ r →? s?? 前提引入④ p→?s????????②③假言三段论⑤ ?p??????????①④拒取式⑥ p ∨q??????????前提引入⑦ q??????????⑤⑥析取三段论
归谬法 (反证法)?
欲证前提： A 1 , A 2 , … , A k结论： B做法在前提中加入 ? B ，推出矛盾理由：A 1 ∧ A 2 ∧ … ∧ A k → B? ? ( A 1 ∧ A 2 ∧ … ∧ A k ) ∨ B? ? ( A 1 ∧ A 2 ∧ … ∧ A k ∧? B )? ? ( A 1 ∧ A 2 ∧ … ∧ A k ∧? B ) ∨ 0? A 1 ∧ A 2 ∧ … ∧ A k ∧? B → 0
?例4 前提：?(p∧q)∨r, r→s, ?s, p
结论： ? q证明 用归缪法① q ????????结论否定引入② r → s ????????前提引入③ ? s ????????前提引入④ ? r ????????②③拒取式⑤ ? ( p ∧ q ) ∨ r ????????前提引入⑥ ? ( p ∧ q) ????????④⑤析取三段论⑦ ? p ∨? q ????????⑥置换⑧ ? p ????????①⑦析取三段论⑨ p ????????前提引入⑩? p ∧ p ????????⑧⑨合取