离散数学-1-8推理理论.ppt

1 第一章命题逻辑 1 8推理理论授课人 李朔Email chn nj lS 2 在数学和其它自然科学中 经常要考虑从某些前提A1 A2 An出发 能推导出什么结论 数理逻辑的主要任务是用逻辑的方法研究数学中的推理 所谓推理是指从前提出发 应用推理规则推出结论的思维过程 任何一个推理都由前提和结论两部分组成 前提就是推理所根据的已知命题 结论则是从前提出发通过推理而得到的新命题 要研究推理 首先应该明确什么样的推理是有效的或正确的 3 一 有效推理 假设一些命题为 并使用一些公认的规则 得到另外的命题 形成结论 这种过程就是论证 定义1 8 1设A和C是2个命题公式 当且仅当A C为一重言式 即A C 则称C为A的有效结论 或C可由A逻辑的推出 A叫做C的前提 上述定义可以推广到n个前提的情况 设H1 H2 Hn C是n 1个命题公式 当且仅当H1 H2 Hn C 称C是一组前提H1 H2 Hn的有效结论 判断有效结论的过程就是论证过程 基本方法是真值表法 直接证法 间接证法 4 二 真值表法 由定义1 8 1可以看出 要证明C是一组前提H1 H2 Hn的有效结论 只需证明H1 H2 Hn C为重言式 而证明一个公式为重言式 可以用真值表 等值演算 主析 合 取范式或已知的蕴含式等方法进行 用等价演算和主析 合 取范式证明重言式的方法前面已经讨论过了 我们已经非常熟悉了 这里仅对真值表法作简单说明 1 真值表法设P1 P2 Pn出现于前提H1 H2 Hm和结论C的全部命题变元 假定对P1 P2 Pn作了全部的真值指派 这样就能对应地确定H1 H2 Hn和C的所有真值 列出这个真值表 即可看出H1 H2 Hm C是否成立即找出H1 H2 Hm均为 的行 对于每一个这样的行 若C也为 则上式成立 或C为 H1 H2 Hm中起码有一个为 5 二 真值表法 例 分析事实 如果我有时间 那么我就去上街 如果我上街 那么我就去书店买书 但我没有去书店买书 所以我没有时间 试指出这个推理前提和结论 并证明结论是前提的有效结论 解 令 我有时间 我去上街 我去书店买书 根据题意 前提为 结论为 以下证明 是一组前提 的有效结论 即证明 P Q Q R R P 6 二 真值表法 作公式P Q Q R R P的真值表从表中可以看出 P Q Q R R都为1的行 赋值000的行 P也为1 或 P为0的行 赋值100 101 110 111的行 P Q Q R R至少有一个为0 所以 P Q Q R R P 7 三 命题逻辑的推理理论 当推理中包含的命题变元较多时 真值表法或等值演算法 主析取范式法等方法的演算量太大 给推理带来了困难 为此引入命题逻辑的推理理论 命题逻辑的推理是一个描述推理过程的命题公式序列 其中的每个命题公式或者是已知前提 或者是由某些前提应用推理规则得到的结论 中间结论或推理中的结论 它有两种方法 直接证法 直接推理 和间接证法 间接推理 8 直接证法 直接推理 直接证法 直接推理 基本思想是 由一组前提出发 利用一些公认的规则 根据已知的等价式或蕴含式 推演得到有效结论 公认的推理规则有4条 P规则 前提在推导过程中的任何时候都可以引入使用 T规则 推导中 如果一个或多个公式蕴含着公式S 则公式S可以引入到以后的推理之中 置换规则 在推导过程的任何步骤上 命题公式中的子公式都可以用与之等价的公式置换 等价式表 合取引入规则 任意两个命题公式A B可以推出A B常用的蕴含式和等价式见P43表1 8 3表1 8 4 9 直接证法 直接推理 例题 用直接推理法证明 证法1 1 P P规则 引入前提 2 QT 1 E 对 1 式T规则 根据E16蕴含等值式 3 P P规则 引入前提 4 T 2 3 I 对 2 3 式 规则 根据I13假言三段论 5 S PT 4 E 对 式T规则 根据E16蕴含等值式 6 P P规则 引入前提 7 S RT 5 6 I 对 5 6 式 规则 根据I13假言三段论 8 T 7 E 对 7 式T规则 根据E16蕴含等值式 10 直接证法 直接推理 证法2 1 P 2 R T 1 I 3 P 4 R S RT 3 I 5 S RT 2 4 I 6 P 7 T 5 6 I 11 直接证法 直接推理 用直接推理法证明 P Q Q R P R证明 P QP PP QT I假言推理 I11 Q RP RT I假言推理 I11 12 间接证法 间接推理 定义1 8 2假设公式H1 H2 Hm中的命题变元P1 P2 Pn 对于P1 P2 Pn的一些真值指派 如果能使H1 H2 Hm的真值为 则称公式H1 H2 Hm是相容的 如果对于P1 P2 Pn的每一组真值指派 使H1 H2 Hm的真值均为 则称公式H1 H2 Hm是不相容的 13 间接证法 间接推理 将不相容的概念应用于命题公式的证明 归谬法 设有一组前提H1 H2 Hn 要推出结论C 即要证H1 H2 Hn C 令S H1 H2 Hn则上式可以简记为S C由永真蕴含的定义有1 S C S C两边否定0 S C H1 H2 Hn C即要证明C是前提H1 H2 Hn的有效结论 只须证明H1 H2 Hn C 0 即H1 H2 Hn与 C不相容 这种间接推理方法称为归谬法 14 间接证法 间接推理 例题 证明 C 可逻辑推出 证明 1 P 2 P 附加前提 3 C P 4 CT 3 E E9德摩根律 5 BT 1 2 I I11假言推理 6 T 4 I I1简化式 7 矛盾 T 5 6 I I1合取引入规则 15 间接证法 间接推理 CP规则间接证法的另一种情况 要证H1 H2 Hn 设S H1 H2 Hn 则上式可以简记为S A B 由永真蕴含的定义有1 S S S R C S R C S R C H1 H2 Hn R C即H1 H2 Hn R C所以 要证明H1 H2 Hn R C 只需证明H1 H2 Hn R C 其中R叫做附加前提 这种间接推理方法称为CP规则 16 间接证法 间接推理 例题 证明 B重言蕴含 证明 1 DP 附加前提 2 P 3 T 1 2 I析取三断论 4 P 5 T 3 4 I I11假言推理 6 P 7 T 5 6 I I11假言推理 8 D CP 17 间接证法 间接推理 例用CP规则证明 P Q R T P Q T R证明 TP 附加前提 T PP PT 析取三段论 P Q R P Q RT 假言推理 QP RT 假言推理 T RCP规则 18 间接证法 间接推理 例试构造下面推理的证明 如果小张和小王去看电影 则小李也去看电影 小赵不去看电影或小张去看电影 小王去看电影 所以 当小赵去看电影时 小李也去看电影 解 将简单命题符号化 设P 小张去看电影 Q 小王去看电影 R 小李去看电影 S 小赵去看电影 2 找出前题与结论 前提 P Q R S P Q 结论 S R 19 间接证法 间接推理 故本题即要证明 P Q R S P Q推出S R证明 用CP规则证明 1 SP 附加前提引入 2 S PP 3 PT 1 2 I 析取三段论 4 P Q RP 5 QP 6 P QT 3 5 I 合取引入规则 7 RT 4 6 I 假言推理 8 S RCP 20 间接证法 间接推理 例构造下面推理的证明 如果小张守第一垒并且小李向B队投球 则A队将取胜 或者A队未取胜 或者A队获得联赛第一名 A队没有获得联赛的第一名 小张守第一垒 因此 小李没有向B队投球 解 设P 小张守第一垒 Q 小李向B队投球 R A队取胜 S A队获得联赛第一名 21 间接证法 间接推理 前提 P Q R R S S P结论 Q证明 用归谬法 1 QP 附加前提 2 R S 3 S 4 RT 2 3 I 析取三段论 5 P Q RP 6 P Q T 4 5 I 拒取式 7 P QT 6 E 德摩根律 置换 8 PP 9 QT 7 8 I 析取三段论 10 Q Q 矛盾 1 9 I 合取引入规则 22 本课小结 有效推理真值表法论证命题逻辑的推理理论 直接证法 间接证法 归缪法 规则 23 课后作业 通读书本本节例题P47 2 a c e 3 a b补充 构造下面推理的证明以下前提已经成立 1 甲或乙作的案 2 如果甲作的案 作案时间应在午夜后 3 若乙证词正确 则午夜灯光未灭 4 若乙证词不正确 则作案时间不在午夜之后 5 午夜灯光灭了结论 乙作的案令A 甲做的案B 乙做的案C 作案时间在午夜前D 乙证词正确E 午夜灯光未灭