离散数学-屈婉玲.pptVIP

第三章 命题逻辑的推理理论 主要内容 推理的形式结构 推理的正确与错误 推理的形式结构 判断推理正确的方法 推理定律 自然推理系统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 3. 前提： 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) 破坏性二难 每个等值式可产生两个推理定律 如, 由A???A可产生 A???A 和 ??A?A 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),AX(I),R(I)是 I 的 形式语言系统, A(I),E(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 构造下面推理的证明： 若明天是星期一或星期三，我明天就