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

1,2.4 命题逻辑推理理论,2.4.1 推理的形式结构 推理的前提与结论,正确推理 推理定律 2.4.2 自然推理系统P 推理规则 直接证明法, 附加前提证明法, 归谬法(反证法), 归结证明法,2,有效推理,定义2.20 若对于每组赋值, A1A2 Ak 为假, 或者 当A1A2Ak为真时, B也为真, 则称由前提A1,A2, Ak 推B的推理有效或推理正确, 并称B是有效的结论 定理2.8 由前提A1, A2, , Ak 推出B 的推理正确当且仅当 A1A2AkB 为重言式.,3,推理的形式结构,形式(1) A1A2AkB 形式(2) 前提: A1, A2, , Ak 结论: B 推理正确记作 A1A2AkB 判断推理是否正确的方法: 真值表法 等值演算法 主析取范式法 构造证明法,4,实例,例1 判断下面推理是否正确: (1) 若今天是1号, 则明天是5号. 今天是1号. 所以, 明天是5号. 解 设 p: 今天是1号, q: 明天是5号 推理的形式结构为 (pq)pq 证明 用等值演算法 (pq)pq (pq)p)q (pq)p)q pqq 1 得证推理正确,5,实例(续),(2) 若今天天冷，小王就穿羽绒服。小王就穿羽绒服。 所以,今天天冷。 解 设p:今天天冷, q:小王穿羽绒服. 推理的形式结构为 (pq)qp 证明 用主析取范式法 (pq)qp (pq)qp (pq)q)p qp (pq)(pq) (pq)(pq) m0m2m3 01是成假赋值, 所以推理不正确.,6,推理定律重言蕴涵式,A (AB) 附加律 (AB) A 化简律 (AB)A B 假言推理 (AB)B A 拒取式 (AB)B A 析取三段论 (AB)(BC) (AC) 假言三段论 (AB)(BC) (AC) 等价三段论 (AB)(CD)(AC) (BD) 构造性二难 (AB)(AB) B 构造性二难(特殊形式) (AB)(CD)( BD) (AC) 破坏性二难,7,自然推理系统P,自然推理系统P由下述3部分组成: 1. 字母表 (1) 命题变项符号: p,q,r, pi,qi,ri, (2) 联结词: , , , , (3) 括号与逗号: ( ), , 2. 合式公式 3. 推理规则 (1) 前提引入规则 (2) 结论引入规则 (3) 置换规则,8,自然推理系统P(续),9,自然推理系统P(续),10,直接证明法,例2 在自然推理系统P中构造下面推理的证明: 前提: pq, qr, ps, s 结论: r(pq) 证明 ps 前提引入 s 前提引入 p 拒取式 pq 前提引入 q 析取三段论 qr 前提引入 r 假言推理 r(pq) 合取 推理正确, r(pq)是有效结论,11,实例,例3 构造推理的证明: 若明天是星期一或星期三, 我就有 课. 若有课, 今天必需备课. 我今天下午没备课. 所以, 明天 不是星期一和星期三. 解 设 p:明天是星期一, q:明天是星期三， r:我有课， s:我备课 前提: (pq)r, rs, s 结论: pq,12,实例(续),前提: (pq)r, rs, s 结论: pq 证明 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 拒取式 pq 置换 结论有效, 即明天不是星期一和星期三,13,附加前提证明法,欲证明 等价地证明 前提: A1, A2, , Ak 前提: A1, A2, , Ak, C 结论: CB 结论: B,理由: (A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2AkC)B (A1A2AkC)B,14,实例,例4 构造下面推理的证明: 前提: pq, qr, rs 结论: ps 证明 p 附加前提引入 pq 前提引入 q 析取三段论 qr 前提引入 r 析取三段论 rs 前提引入 s 假言推理 推理正确, ps是有效结论,15,归谬法(反证法),欲证明 前提：A1, A2, , Ak 结论：B 将B加入前提, 若推出矛盾, 则得证推理正确.,理由: A1A2AkB (A1A2Ak)B (A1A2AkB) 括号内部为矛盾式当且仅当 (A1A2AkB)为重言式,16,实例,例5 构造下面推理的证明 前提: (pq)r, rs, s, p 结论: q 证明 用归缪法 q 结论否定引入 rs 前提引入 s 前提引入 r 拒取式,17,实例(续), (pq)r 前提引入 (pq) 析取三段论 pq 置换 p 析取三段论 p 前提引入 pp 合取 推理正确, q是有效结论,18,归结证明法,理由 (pq)(pr)(qr) (pq)(pr)(qr) (pq)(pr)qr (pq)q)(pr)r) (pq)(pr) 1,19,归结证明法(续),在自然推理系统P中只需下述推理规则: (1) 前提引入规则 (2) 结论引入规则 (3) 置换规则 (4) 化简规则 (5) 合取引入规则 (6) 归结规则,20,归结证明法的基本步骤,1. 将每一个前提化成等值的合取范式, 设所有合取范式的 全部简单析取式为A1, A2, At 2. 将结论化成等值的合取范式B1B2Bs, 其中每个Bj 是简单析取式 3. 以A1,A2,At为前提, 使用归结规则推出每一个Bj, 1js 4. 由合取引入规则得到结论B1B2Bs,21,实例,例6 用归结证明法构造下面推理的证明: 前提: (pq)r, rs, s 结论: (pq)(ps) 解 (pq)r (pq)r (pq)r (pr)(qr) rs rs (pq)(ps) (pq)(ps) (pq)(ps) p(qs) 推理可表成 前提: pr, qr, rs,