命题逻辑的推理证明课程.ppt

第三章 命题逻辑的推理理论 主要内容 第一节 推理的形式结构 推理的正确与错误 推理的形式结构 判断推理正确的方法 推理定律 第二节 自然推理系统P 形式系统的定义与分类 自然推理系统P 在P中构造证明:直接证明法、附加前提证明法、归谬法 3.1 推理的形式结构 定义3.1 设A1, A2, …, Ak, B为命题公式. 若对于每组赋值， A1?A2?…? Ak 为假，或当A1?A2?…?Ak为真时，B也为真， 则称由前提A1, A2, …, Ak推出结论B的推理是有效的或正确 的, 并称B是有效结论. 推理的形式结构 2. A1?A2?…?Ak?B 若推理正确, 记为A1 ? A2 ? … ? Ak ? B 推理实例 例1 判断下面推理是否正确 (1) 若今天是1号，则明天是5号. 今天是1号. 所以, 明天是5号. (2) 若今天是1号，则明天是5号. 明天是5号. 所以, 今天是1号. 推理实例 (2) 推理的形式结构: 推理定律——重言蕴涵式 一些重要的重言蕴含式，称为推理定律。 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) 破坏性二难 3.2 自然推理系统P 定义3.2 一个形式系统 I 由下面四个部分组成： (1) 非空的字母表，记作 A(I). (2) A(I) 中符号构造的合式公式集，记作 E(I). (3) E(I) 中一些特殊的公式组成的公理集，记作 AX(I). (4) 推理规则集，记作 R(I). 记I=A(I),E(I),AX(I),R(I), 其中A(I),E(I)是 I 的 形式语言系统, AX(I),R(I) 是 I 的形式演算系统. 形式系统分为： 自然推理系统: 无公理, 即AX(I)=? 公理推理系统 推出的结论是系统中的重言式, 称作定理 自然推理系统P 定义3.3 自然推理系统 P 定义如下: 1. 字母表 (1) 命题变项符号：p, q, r, …, pi, qi, ri, … (2) 联结词符号：?, ?, ?, ?, ? (3) 括号与逗号：(, ), ， 2. 合式公式（同定义1.6） 3. 推理规则 (1) 前提引入规则：在证明的任何步骤都可以引入前提。 (2) 结论引入规则：在证明的任何步骤所得到的结论都可以作为后继证明的前提。 (3) 置换规则：在证明的任何步骤，命题公式中的子公式都可以用等值的公式置换，得到公式序列中又一个公式。 推理规则 (4) 假言推理规则 (6) 化简规则 (8) 假言三段论规则 推理规则 (10) 构造性二难推理规则 (11) 破坏性二难推理规则 (12) 合取引入规则 在自然推理系统P中构造证明 设前提A1, A2,?, Ak,结论B及公式序列C1, C2,?, Cl. 如果每 一个Ci(1?i?l)是某个Aj, 或者可由序列中前面的公式应用推理 规则得到, 并且Cl =B, 则称这个公式序列是由A1, A2,?, Ak推 出B的证明 例2 构造下面推理的证明： 若明天是星期一或星期三，我明天就有课. 若我明天有 课，今