命题逻辑II 范式与推理理论.ppt

* * * * * 实例 (续) (2) 若今天是1号，则明天是5号. 明天是5号. 所以今天是1号. 解 设p：今天是1号，q：明天是5号. 推理的形式结构为: (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) ? m0úm2úm3 结果不含m1, 故01是成假赋值，所以推理不正确. * 推理正确性的证明：推理定律 重要的推理定律重言蕴涵式 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) 破坏性二难 证明:描述推理过程的命题公式序列，其中每个命题公式或者是已知的前提，或者是由前面的命题公式应用推理规则得到的结论. * 推理规则 * 推理规则(续) (11) 破坏性二难推理规则 A?B C?D ?Bú?D \?Aú?C (12) 合取引入规则 A B \AùB (9) 析取三段论规则 AúB ?B \A (10)构造性二难推理规则 A?B C?D AúC \BúD * 构造证明之一——直接证明法 例 构造下面推理的证明： 若明天是星期一或星期三，我就有课. 若有课，今天必备课. 我今天没备课. 所以， 明天不是星期一和星期三. 解 ?设 p：明天是星期一，q：明天是星期三， r：我明天有课，s：我今天备课 推理的形式结构为 前提：(púq)?r, r?s, ?s 结论：?pù?q 证明： ① 如果我明天有课，今天一定备课 ② 今天我没有备课 ③ 我明天没课 ④ 若明天是星期一或星期三，我就有课 ⑤ 并非明天是星期一或星期三 ⑥ 明天不是周一，明天也不是周三 推理过程及其符号化：自然语言推理过程 * 推理过程及其符号化：形式证明 证明 ① r?s 前提引入 ② ?s 前提引入 ③ ?r ①②拒取式 ④ (púq)?r 前提引入 ⑤ ?(púq) ③④拒取式 ⑥ ?pù?q ⑤置换 * 构造证明之二——附加前提证明法 欲证明 前提：A1, A2, …, Ak 结论：C?B 等价地证明 前提：A1, A2, …, Ak, C 结论：B? 理由： (A1ùA2ù…ùAk)?(C?B) ? ?( A1ùA2ù…ùAk)ú(?CúB) ? ?( A1ùA2ù…ùAkùC)úB ? (A1