命题逻辑推理理论--离散数学.ppt

. 武汉大学国际软件学院唐存琛 刘峰 2.4 命题逻辑推理理论 2.4.1 推理的形式结构 推理及其形式结构 推理定律 2.4.2 自然推理系统P 自然推理系统的定义 证明方法 2.4.1 推理的形式结构 一、什么是推理 二、推理的形式结构 例1 判断下面推理是否正确: (1) 若今天是1号, 则明天是5号. 今天是1号. 所以, 明天是5号. 例1 (2) 若今天是1号, 则明天是5号. 明天是5号. 所以, 今天是1号。 三、推理定律——重言蕴涵式 A T (AúB) 附加律 (AùB) T A 化简律 (A?B)ùA T B 假言推理 (A?B)ù?B T ?A 拒取式 (AúB)ù?B T A 析取三段论 (A?B)ù(B?C) T (A?C) 假言三段论 (A?B)ù(B?C) T (A?C) 等价三段论 (A?B)ù(C?D)ù(AúC) T (BúD) 构造性二难 (A?B)ù(?A?B) T B 构造性二难(特殊形式) (A?B)ù(C?D)ù( ?Bú?D) T (?Aú?C) 破坏性二难 注意： 2.4.2 自然推理系统P 自然推理系统P由下述3部分组成: 1. 字母表 (1) 命题变项符号: p,q,r,…, pi,qi,ri,… (2) 联结词: ? , ? , ? , ? , ? (3) 括号与逗号: ( ), , 2. 合式公式 3. 推理规则 (1) 前提引入规则 (2) 结论引入规则 (3) 置换规则 自然推理系统P(续) 自然推理系统P(续) 直接证明法 例2 在自然推理系统P中构造下面推理的证明: 前提: púq, q?r, p?s, ?s 结论: rù(púq) 证明 ① p?s 前提引入 ② ? s 前提引入 ③ ? p ①②拒取式 ④ púq 前提引入 ⑤ q ③④析取三段论 ⑥ q?r 前提引入 ⑦ r ⑤⑥假言推理 ⑧ rù(púq) ⑦④合取 推理正确, rù(púq)是有效结论 实例 例3 构造推理的证明: 若明天是星期一或星期三, 我就有 课. 若有课, 今天必需备课. 我今天下午没备课. 所以, 明天 不是星期一和星期三. 解 设 p:明天是星期一, q:明天是星期三， r:我有课， s:我备课 前提: (púq)?r, r?s, ?s 结论: ?pù?q 实例(续) 前提: (púq)?r, r?s, ?s 结论: ?pù?q 证明 ① r?s 前提引入 ② ?s 前提引入 ③ ?r ①②拒取式 ④ (púq)?r 前提引入 ⑤ ?(púq) ③④拒取式 ⑥ ?pù?q ⑤置换 结论有效, 即明天不是星期一和星期三 附加前提证明法 欲证明 等价地证明 前提: A1, A2, …, Ak 前提: A1, A2, …, Ak, C 结论: C?B 结论: