离散数学3概要.ppt

Discrete Math. 离散数学 Discrete Mathematics 形式系统 定义3.2一个形式系统I由下面四个部分组成： (1)非空的字母表集，记作A(I). (2)A(I)中符号构造的合式公式集，记作E(I). (3) E(I)中一些特殊的公式组成的公理集，记作AX(I). (4)推理规则集，记作R(I). 这样可将I记为4元组A(I),E(I),AX(I),R(I).其中A(I),E(I)是I的形式语言系统,AX(I),R(I)为I的形式演算系统。 形式系统一般分为两类： 一是自然推理系统：它的特点是从任意给定的前提出发，应用系统中的推理规则进行推理演算，得到的最后命题公式是推理的结论。 另外的则是公理推理系统：它只能从若干给定的公理出发，应用系统的推理规则进行推理演算。得到的结论是系统中的重言式，称为系统中的定理。 推理规则 归谬法 * CHAPTER THREE * 第一章 命题逻辑的推理理论 3.1 推理的形式结构 3.2 自然推理系统P 推理是指从一些已知的命题公式（称为前提)应用推理规则推演出另一些命题公式（称为结论）的过程。 定义3.1 设A1, A2, …, Ak和B是命题公式，若对于A1, A2, …, Ak, B中出现的命题变项的任一组赋值，要么A1∧A2∧…∧Ak为假，要么A1∧A2∧…∧Ak为真且B也为真, 则称由前提A1, A2, …, Ak 推出B的推理是有效的（或正确的)，并称B是有效的结论。 §3.1 推理的形式结构 A1∧A2∧…∧Ak?B永真 注： 1、由前提A1,A2,…,Ak 推结论B的推理是否正确与诸前提的排列次序无关。 将一个推理诸前提的集合记为Г，则由Г推出结论B的推理记为Г├ B。若该推理是正确的，则记为Г╞ B (或Г?B), 否则记为Г? B (或Г?B)。称Г├ B 和 {A1,A2,…,Ak}├ B为推理的形式结构。 2、设命题公式A1, A2, …, Ak, B中共有n个命题变项。对于任一组赋值?1, ?2, …, ?n (?i 取0或1, i=1,2,…, n), 前提和结论的取值情况有如下四种： (1)? A1∧A2∧… ∧ Ak 为0，B为0 (2) A1∧A2∧… ∧ Ak 为0，B为1 (3) A1∧A2∧… ∧ Ak 为1，B为0 (4) A1∧A2∧… ∧ Ak 为1，B为1 按照定义，只要不出现(3)，推理就是正确的。因而判断一个推理正确与否，只需判断是否会出现情况(3)即可。 3、推理正确，并不能保证结论B一定为真。因为前提可能是假的(情况(1))。 例3.1 判断下列推理是否正确 (1)｛p, p→q}├ q； (2)｛p, q→p}├ q 解：用真值表法 1 1 1 0 0 1 0 0 p∧(q→p) q p∧(p→q) q p q (1) 从真值表可见，没有出现前提p∧(p→q)为真，结论q为假的情况，故｛p, p→q} ? q。 (2) 在赋值为10时，出现了前提p∧(q→p)为真而q为假的情况，故｛p,q→p} ? q。 0 0 0 1 0 0 0 1 0 0 1 0 1 1 1 1 定理3.1 命题公式 A1,A2,…,Ak推 B的推理正确, 即{A1,A2,…,Ak}╞ B当且仅当(A1∧A2∧…∧Ak)→B为重言式。 证明 见教材43页。 由该定理，推理的形式结构： {A1,A2,…,Ak}┣B （3.1） 可用 (A1∧A2∧…∧Ak)→B （3.2） 表示。 判断推理是否正确的三种直接方法： 1、真值表法 2、等值演算法 3 、主析取范式法 或写成 前提：A1,A2,…,Ak 结论：B （3.5） 然后论证推理是否正确！ 同时{A1,A2,…,Ak}╞ B 换成A1∧A2∧…∧Ak ?B (1)? 若a能被4整除，则a能被2整除。a 能被4整除，所以?a能被2整除。 (2) 下午马芳或去看电影或去游泳。她没去看电影，所以她去游泳了。 (3) 若下午气温超过30℃，则王小燕必去游泳。若她去游泳，她就不去看电影了。所以，若王小燕没去看电影，下午气温必超过了30℃。