离散数学方世昌第5节.ppt

1.5 推理规则和证明方法 1.推理和推理规则 什么是推理？ 推理的例子：设x属于实数, P: x是偶数, Q: x2是偶数。 例1. 如果x是偶数, 则x2是偶数。 x是偶数。 x2是偶数。 1、推理和推理规则 推理规则：正确推理的依据。 任何一条永真蕴含式都可以作为一条推理规则。 例：析取三段论： 如果，P：他在钓鱼，Q：他在下棋 前提：他在钓鱼或下棋； 他不在钓鱼 结论：所以他在下棋 定义1：若H1∧H2∧ …∧Hn ? C, 则称C是H1, H2, …, Hn的有效结论。 特别若A ? B, 则称B是A的有效结论，或从A推出B。 有效结论 如： Q是?P，(P úQ) 的有效结论。 即 ?Pù(P úQ) →Q 是一个永真式。 推理的形式结构 形式(1) H1ùH2ù…ùHn?C 形式(2) 前提: H1, H2, … , Hn 结论: C 推理正确记作 H1ùH2ù…ùHnTC 推理的形式结构 形式(1) H1ùH2ù…ùHn?C 形式(2) 前提: H1, H2, … , Hn 结论: C 推理正确记作 H1ùH2ù…ùHnTC 常用的推理规则 1) 恒等式(E1~E24) 2) 永真蕴含式(I1~I8,表1.5-1) 3) 替换规则，代入规则 4) P规则和T规则 P规则：(前提引入) 在推导的任何步骤上，都可以引入前提。 T规则：(结论引用) 在推导任何步骤上所得结论都可以作为后继证明的前提。 永真蕴含式 推理规则 运用推理规则形式化证明 例1：考虑下述论证: 1. 如果这里有球赛, 则通行是困难的。 2. 如果他们按时到达, 则通行是不困难的。 3. 他们按时到达了。 4. 所以这里没有球赛。 前 3 个断言是前提, 最后1个断言是结论, 要求我们从前提推出结论。 1.5.2 证明方法　　定理常见的形式是“P当且仅当Q”，“如果P，那么Q”。 而前者又相当于P→Q并且Q→P， 所以归根结底，定理的主要形式是P→Q。至于其它形式，诸如： 　 P形式，只需证明P是假; P∧Q形式，只需证明P、Q俱真; P∨Q形式，可转化为 P→Q形式。　　我们主要从策略意义上说明如何证明P→Q形式的命题，具体的技巧，仍需通过例题来学习。 3. 证明方法 1). 无义证明法 证明 P ? Q为真，只需证明P为假。 2). 平凡证明法 证明 P ? Q为真，只需证明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 ⑤置换 结论有效, 即明天不是星期一和星期三 3. 证明方法 4). 间接证明法-（对原命题的逆否命题进行证明） 证P ? Q只需证? Q ? ?P 因为P ? Q 也即 P→Q永真 ， ? Q → ?P永真 所以? Q ? ?P 　　(2) 一个完全数是一个整数，它等于它的所有因子(除本身外)的和。 如 6 是一个完全数，因为 6=1+2+3，同样 28 也是。定理: 一个完全数不是一个质数。　　证 其逆反如下: 一个质数不是一个完全数。 假设P是一质数，那么P≥2 并且P恰有两个因子 1 和P，所以小于P的所有因子的总和是 1。 这得出P不是一个完全数。　　这是间接证明法。 6. 证明方法 6. CP规则（演绎定理） P1∧P