命题演算(推理理论)9.pptVIP

* * * * * * 第四讲 命题逻辑的推理理论 命题逻辑的推理理论也称为命题演算 主要内容 一、推理的形式结构 二、推理定律和推理规则 三、逻辑证明方法 * 数理逻辑的推理理论主要研究推理的“思维过程”，为推理提供一定的推理规则。它只关心从前提得到结论这种推理的正确有效性。无论前提是否真得正确，它总是假设其是成立的。所以推理的正确性和结论的正确性可能是不一致的。推理理论在应用上常常是将一些定理，定律，公理和条件作为前提，通过推理得到新的定理。 引言 * 一、推理的形式结构 定义1 设A1, A2, …, Ak, B为命题公式. 若对于每组赋值，A1?A2?…? Ak 为假，或当A1?A2?…?Ak为真时，B也为真，则称由前提A1, A2, …, Ak推出结论B的推理是有效的或正确的, 并称B是有效结论或称B可由A1, A2, …, Ak逻辑推出. 定理1 由命题公式A1, A2, …, Ak 推B的推理正确当且仅当A1?A2?…?Ak?B为重言式 * 推理的形式结构 2. A1?A2?…?Ak?B 若推理正确, 记为A1 ? A2 ? … ? Ak ? B 3. 前提： A1, A2, … , Ak 结论： B 推理的形式结构 1. {A1, A2, …, Ak} B 若推理正确, 记为{A1,A2,?,An} B * 二、推理定律——重言蕴涵式 1. A ? (A?B) 附加律 2. (A?B) ? A 化简律 3. (A?B)?A ? B 假言推理 4. (A?B)??B ? ?A 拒取式 5. (A?B)??B ? A 析取三段论 6. (A?B)?(B?C) ? (A?C) 假言三段论 7. (A?B)?(B?C) ? (A?C) 等价三段论 8. (A?B)?(C?D)?(A?C) ? (B?D) 构造性二难 (A?B)?(?A?B) ? B 构造性二难(特殊形式) 9. (A?B)?(C?D)?( ?B??D) ? (?A??C) 破坏性二难 每个等值式可产生两个推理定律 如, 由A???A可产生 A???A 和 ??A?A * 推理规则 (1) 前提引入规则(P) 在推理过程中，可以随时引入已知的前提。 (2) 结论引入规则(T) 在推理过程中，前面已推出的有效结论都可作为后续推理的前提引用。 (3) 置换规则(R) 在推理过程中，命题公式中的子公式都可以用与之等值的命题公式置换，得到证明的公式序列的另一公式。 (4) 代入规则(S) 在推理过程中，重言式中的任一命题变元都可以用一命题公式代入，得到的仍是重言式。 * 推理规则 (4) 假言推理规则 (6) 化简规则 (8) 假言三段论规则 A?B A ∴B A ∴A?B A?B ∴ A (5) 附加规则 (7) 拒取式规则 (9) 析取三段论规则 A?B ?B ∴?A A?B B?C ∴A?C A?B ?B ∴A * 推理规则 (10) 构造性二难推理规则 (12) 合取引入规则 A?B C?D A?C ∴B?D A?B C?D ?B??D ∴?A??C A B ∴A?B (11) 破坏性二难推理规则 * 三、逻辑证明方法 判断有效结论的过程就是论证过程。 基本方法： （1）真值表法 （2）直接证明法 （3）间接证明法（反证法） 具体：等值演算、 主析取范式、构造证明法等 * 例：判断下列推理是否正确。 今天杨尚树或去网吧或去教室。他没去教室，所以他去网吧了。 设 p：杨尚树去网吧。