离散数学命题逻辑的推理理论.ppt
1,1.6 命题逻辑的推理理论,推理的形式结构 判断推理是否正确的方法 推理定律与推理规则 构造证明法,2,推理的形式结构问题的引入,推理: 从前提出发推出结论的思维过程 前提是指已知的命题公式,结论是推出的命题公式 例 如果天气凉快,小王就不去游泳.天气凉快.所以小王 没有去游泳. p:天气凉快,q:小王去游泳 前提: (p® Ø q)Ùp 结论: Ø q 问题:如何判断推理的是否正确?,3,推理的形式结构,定义 “A1, A2, , Ak 推B” 的推理正确 当且仅当 A1ÙA2ÙÙAk®B为重言式. 若对于每组赋值,A1ÙA2ÙÙ Ak 为假,或 当A1ÙA2ÙÙAk为真时, B也为真, 则称由A1,A2, Ak 推B的推理正确 , 否则推理不正确(错误). 推理的形式结构: A1ÙA2ÙÙAk®B 或 前提: A1, A2, , Ak 结论: B 若推理正确,则记作:A1ÙA2ÙÙAkÞB.,4,判断推理是否正确的方法,真值表法 等值演算法 主析取范式法 构造证明法 说明:当命题变项比较少时,用前3个方法比较方 便, 此时采用形式结构“ A1ÙA2ÙÙAk®B” . 当命题变项比较多时,用构造证明法,采用“前提: A1, A2, , Ak, 结论: B”.,5,实例,例 判断下面推理是否正确 (1) 若今天是1号,则明天是5号. 今天是1号. 所 以明天是5号. 解 设 p:今天是1号,q:明天是5号. 证明的形式结构为: (p®q)Ùp®q 证明(用等值演算法) (p®q)Ùp®q Û Ø(ØpÚq)Ùp)Úq Û ØpÚØqÚq Û 1 得证推理正确,6,实例 (续),(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是成假赋值,所以推理不正确.,7,推理定律重言蕴涵式,重要的推理定律 A Þ (AÚB) 附加律 (AÙB) Þ A 化简律 (A®B)ÙA Þ B 假言推理 (A®B)ÙØB Þ ØA 拒取式 (AÚB)ÙØB Þ A 析取三段论 (A®B)Ù(B®C) Þ (A®C) 假言三段论 (A«B)Ù(B«C) Þ (A«C) 等价三段论 (A®B)Ù(C®D)Ù(AÚC) Þ (BÚD) 构造性二难,8,推理定律 (续),(A®B)Ù(ØA®B)Ù(AÚØA) Þ B 构造性二难(特殊形式) (A®B)Ù(C®D)Ù( ØBÚØD) Þ (ØAÚØC) 破坏性二难,说明: 若某推理符合某条推理定律,则它自然是正确的 AÛB产生两条推理定律: A Þ B, B Þ A,9,推理规则,10,推理规则(续),11,构造证明直接证明法,例 构造下面推理的证明: 若明天是星期一或星期三,我就有课. 若有课,今天必备课. 我今天下午没备课. 所以, 明天不是星期一和星期三. 解 设 p:明天是星期一,q:明天是星期三, r:我有课,s:我备课 形式结构为 前提:(pÚq)®r, r®s, Øs 结论:ØpÙØq,12,直接证明法 (续),证明 r®s 前提引入 Øs 前提引入 Ør 拒取式 (pÚq)®r 前提引入 Ø(pÚq) 拒取式 ØpÙØq 置换,13,构造证明附加前提证明法,欲证明 前提: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ÙA2ÙÙAkÙC)®B,14,附加前提证明法 (续),例 构造下面推理的证明: 2是素数或合数. 若2是素数,则 是无理数. 若 是无理数,则4不是素数. 所以,如果4是 素数,则2是合数. 用附加前提证明法构造证明 解 设 p:2是素数,q:2是合数, r: 是无理数,s:4是素数 形式结构 前提:pÚq, p®r, r®Øs 结论:s®q,15,附加前提证明法 (续),证明 s 附加前提引入 p®r 前提引入 r®Øs 前提引入 p®Øs 假言三段论 Øp 拒取式 pÚq 前提引入 q 析取三段论 请用直接证明法证明之,16,构造证明归谬法(反证法),欲证明 前提:A1, A2, , Ak 结论:B 将ØB加入前提,若推出矛盾,则得证推理正确. 理由: A1ÙA2ÙÙAk®B Û Ø(A1ÙA2ÙÙAk)ÚB Û Ø(A1ÙA2ÙÙAkÙØB) 括号内部为矛盾式当且仅当 (A1ÙA2ÙÙAk®B)为 重言式,17,归谬法 (续),例 构造下面推理的证明 前提:Ø(pÙq)Úr, r®s, Øs, p 结论:Øq 证明(用归缪法) q 结论否定引入 r®s 前提引入 Øs 前提引入 Ør 拒取式,18,归谬法 (续), Ø(pÙq)Úr 前提引入 Ø(pÙq) 析取三段论 ØpÚØq 置换 Øp 析取三段论 p 前提引入 ØpÙp 合取 请用直接证明法证明之,