工科离散数学课件 第一章 1_7_推理理论(2) - 自然推理系统(1) - 直接推理.pptx

1.7.2 自然推理系统1.7 推理理论-自然推理系统——严格的形式论证有两类不同的系统：自然推理系统和公理推理系统。——形式逻辑推理的本质是说明一个蕴含关系，或者说，总是假定前提为真，再利用约定的规则，说明结论为真的过程。[自然推理系统]指不引入公理，仅确定一些推理规则，从前提出发，利用推理规则构造出严格的命题序列，推导出最终的结论。自然推理=构造证明法=演绎法=形式证明。——这种推理就是“因为+所以”组成的步骤，只是每次的“所以”都要由推理规则（原因）来保证。——证明跳步大了？没有直接规则做保证——公理逻辑（推理）系统：基于公理，如欧氏几何，5条公理 1. 第一类规则：基本等价式和蕴含式 ——1/3类1.7 推理理论-自然推理系统——将基本等价关系和蕴含关系称为推理规则或推理定律，或称前者为推理定律，后者为推理规则。基本推理规则的形成： 因为：如果你有口令(p)，那么，就能登录网络(q)。 你有了口令(p) 。 所以：你能登录网络(q) 。? p?q p? q——得到一条规则（定律）： p→q, p ? q 或 (p→q)?p ? q 1.7 推理理论-自然推理系统序号蕴含关系含 义I1p ? q ? p?化简律（联言推理，分解式）I2p ? q ?q?I3p ? p ? q附加律I4q ? p ? qI5┐p ? p → qI6q ? p → qI7┐(p → q) ? pI8?┐(p → q) ? ┐qI9p, q ? p ? q?合取引入（联言推理，合成式）I10┐p, p ? q ? q析取三段论（选言推理）基本规则： 1.7 推理理论-自然推理系统(1)等价定律来自1.5节；(2)肯定形式与否定形式同样有效!序号蕴含关系含义I11p, p→q ? q?假言推理I12┐q, p→q ? ┐p ?拒取式I13p→q, q→r ? p→r假言三段论I14p?q, q?r ? p?r等价三段论I15p→r, q→s, p?q ? r?s构造性二难I16p→r,q→s, ┐r?┐s ? ┐p?┐q破坏性二难I17p→q ? (p?r)→(q?r)I18p→q ? (p?r)→(q?r)I19p→q, p→r ? p→(q?r)I20p→q, p→r ? p→(q?r)I21(┐p?q)?(p?r) ? q?r消解律——补充视频 2. 第二类规则：前提与基本定律的引用规则1.7 推理理论-自然推理系统[P 规则]前提引入规则，指在证明的任何步骤都可引入前提。 ——p ? q [T 规则]推理定律引用规则，指在证明中，如一个或几个公式满足推理定律，则其结论或等价公式可引入。 ——p ? p ? q；┐q, p→q ? ┐p[置换规则]若 A可引入，X 是 A 的子公式，且X?Y。如果在 A 中用 Y 部分或全部替换 X 得到 B，则B可引入。 ——∵p?(q?r) ，∴ p?(┐ q?r)置换规则=子公式（等价）代换。——部分书籍中不允许使用置换规则，少用置换规则 使用 P规则、 T规则和置换规则实现的证明方法。[直接证法] 1.7 推理理论-自然推理系统示例：若 n 是偶数，则 n2 也是偶数。证明：(1) ∵n=2m 前提（m是一个整数） P(2)∴n2=(2m)2 由推理规则：x=y?x2=y2 , (1)?(2) T(1) E(3)∴ n2=4m2 由推理规则： x2=x*x，乘法交换律和结合律, (2)?(3) 置换规则(2)(4)∴ n2=2(2m2) 由推理规则：乘法结合律 , (3)?(4) 置换规则 (3)(5)∴n2是偶数 由推理规则：若x是整数则2x是偶数(偶数定义) , (4)?(5) T (4) E∵∵ 例-34：证明 (p?q)?(p→r)?(q→s) ? s?r。1.7 推理理论-自然推理系统证明：