《离散数学-耿素云PPT(第5版)1.7》由会员分享，可在线阅读，更多相关《离散数学-耿素云PPT(第5版)1.7（18页珍藏版）》请在金锄头文库上搜索。
1、11.7 推理理论 推理的形式结构判断推理是否正确的方法推理定律与推理规则构造证明直接证明法, 附加前提证明法, 归缪法 2推理的形式结构问题的引入 推理举例:(1) 正项级数收敛当且仅当部分和有上界.(2) 若ACBD，则AB且CD.推理: 从前提出发推出结论的思维过程 上面(1)是正确的推理，而(2)是错误的推理. 证明: 描述推理正确的过程. 3推理的形式结构 定义 若对于每组赋值，或者A1A2 Ak 均为假， 或者当A1A2Ak为真时, B也为真, 则称由A1, A2, , Ak推B的推理正确, 否则推理不正确（错误）. “A1, A2, , Ak 推B” 的推理正确当且仅当 A1A2
2、AkB为重言式. 推理的形式结构: A1A2AkB 或前提： A1, A2, , Ak结论： B 若推理正确，则记作：A1A2AkB.4判断推理是否正确的方法真值表法 等值演算法 判断推理是否正确 主析取范式法 构造证明法 证明推理正确 说明：用前3个方法时采用形式结构 “ A1A2AkB” . 用构造证明时, 采用“前提: A1, A2, , Ak, 结论: B”. 5实例例 判断下面推理是否正确(1) 若今天是1号，则明天是5号. 今天是1号. 所 以明天是5号. 解 设 p：今天是1号，q：明天是5号. 推理的形式结构为: (pq)pq 证明（用等值演算法）(pq)pq (pq)p)q
3、pqq 1 得证推理正确 6实例 (续)(2) 若今天是1号，则明天是5号. 明天是5号. 所以今天是1号. 解 设p：今天是1号，q：明天是5号. 推理的形式结构为: (pq)qp证明（用主析取范式法）(pq)qp (pq)qp (pq)q)p qp (pq)(pq) (pq)(pq) m0m2m3 结果不含m1, 故01是成假赋值，所以推理不正确. 7推理定律重言蕴涵式 重要的推理定律A (AB) 附加律 (AB) A 化简律(AB)A B 假言推理(AB)B A 拒取式(AB)B A 析取三段论(AB)(BC) (AC) 假言三段论(AB)(BC) (AC) 等价三段论(AB)(CD)(
4、AC) (BD) 构造性二难 8推理定律 (续)(AB)(AB) B 构造性二难（特殊形式）(AB)(CD)( BD) (AC)破坏性二难证明:描述推理过程的命题公式序列，其中每个命题公式或者是已知的前提，或者是由前面的命题公式应用推理规则得到的结论.9推理规则 10推理规则(续)(11) 破坏性二难推理 规则 ABCDBD AC (12) 合取引入规则ABAB (9) 析取三段论规则ABB A(10)构造性二难推理 规则ABCDAC BD11构造证明之一直接证明法例 构造下面推理的证明：若明天是星期一或星期三，我就有课. 若有课 ，今天必备课. 我今天下午没备课. 所以，明天不是星期一和星期
5、三. 解 设 p：明天是星期一，q：明天是星期三，r：我有课，s：我备课 推理的形式结构为前提：(pq)r, rs, s结论：pq 12直接证明法 (续)证明 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 拒取式 pq 置换 13构造证明之二附加前提证明法 欲证明前提：A1, A2, , Ak结论：CB等价地证明前提：A1, A2, , Ak, C结论：B 理由： (A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2AkC)B (A1A2AkC)B14附加前提证明法 (续)例 构造下面推理的证明: 2是素数或合数. 若2是素数，则 是无理数. 若 是无
6、理数，则4不是素数. 所以，如果4是素数，则2是合数. 用附加前提证明法构造证明 解 设 p：2是素数，q：2是合数，r： 是无理数，s：4是素数 推理的形式结构前提：pq, pr, rs结论：sq15附加前提证明法 (续)证明 s 附加前提引入 pr 前提引入 rs 前提引入 ps 假言三段论 p 拒取式 pq 前提引入 q 析取三段论 请用直接证明法证明之 16构造证明之三归谬法(反证法) 欲证明前提：A1, A2, , Ak 结论：B 将B加入前提，若推出矛盾，则得证推理正确. 理由:A1A2AkB (A1A2Ak)B (A1A2AkB) 括号内部为矛盾式当且仅当 (A1A2AkB)为 重言式 17归谬法 (续)例 构造下面推理的证明前提：(pq)r, rs, s, p结论：q证明（用归缪法） q 结论否定引入 rs 前提引入 s 前提引入 r 拒取式18归谬法 (续) (pq)r 前提引入 (pq) 析取三段论 pq 置换 p 析取三段论 p 前提引入 pp 合取 请用直接证明法证明之
