离散数学教学课件01-命题逻辑-1.8.pptVIP

第一章 命题逻辑Propositional Logic 第七节 命题逻辑的推理理论 第七节 命题逻辑的推理理论 数理逻辑的主要任务是提供一套推理规则（与这些推理规则有关的理论叫做推理理论），按照这种公认的推理规则，从给定的前提集合出发，推导出一个结论来。 这样的推导过程，通常称为有效推理（或演绎、形式证明） 得到的结论叫作有效结论。 命题逻辑的推理理论 在这里，我们关心的是推理的有效性，而不是结论的真实性。 前提的实际真值并不作为确定推理有效性的依据。 所谓推理有效，是指它的结论是其前提的合乎逻辑的结果。 推理 一、推理的基本概念和推理形式 定义1 推理（Proof），也叫论证，指由已知命题得到新的命题的思维过程 其中， 已知命题称为推理的前提或假设 推出的新命题成为推理的结论 推理 定义2 数理逻辑中，前提（Hypothesis） H是一个或几个命题公式H1, H2, … Hn，结论是一个命题公式C 由前提得到结论的推理形式可表示为 H1, H2, …, Hn ? C 推理形式是命题公式的一个有限序列 H1, H2, … Hn, C 推理 定义3 若存在H1, H2, … , Hn, C的一个指派，使得每个Hi为真，而C为假，则推理形式H1, H2, …, Hn ? C是无效的。 否则，推理是有效的此时称C为H1, H2, …, Hn 的有效结论 推理 定理 推理形式H1, H2, …, Hn ? C是有效的，当且仅当命题公式(H1 ∧ H2 ∧ … ∧ Hn) ? C 是永真式，即(H1 ∧ H2 ∧ … ∧ Hn) ? C 。 推理规则 二、推理规则 P规则（前提引入规则） 在推导过程中，前提可视需要引入 T规则（结论引入规则） 在推导过程中，前面已经导出的有效结论都可以作为后续推导的前提引入 CP规则 若推出有效结论为条件式R ? C时，只需要将其前件R加入到前提中作为附加前提，再去推出后件C即可。 推理规则 定理： 若 H1, H2, …, Hn, R ? C 则H1, H2, …, Hn? R ? C 证明：若H1, H2, …, Hn, R ? C 则(H1 ∧ H2 ∧ … ∧ Hn ∧ R ) ? C 为永真式， 即? (H1 ∧ H2 ∧ … ∧ Hn ∧ R ) ∨ C为永真式 则? (H1 ∧ H2 ∧ … ∧ Hn) ∨ ? R ∨ C为永真式 则? (H1 ∧ H2 ∧ … ∧ Hn ) ∨ (R ? C)为永真式 即(H1 ∧ H2 ∧ … ∧ Hn) ? (R ? C) 为永真式 因此，可得H1, H2, …, Hn? R ? C 推理定律 三、推理定律 P24由P14基本蕴涵公式得出P10的基本等价式也可以得到相应的推理定律，请自己补齐。 推理常用的方法 四、推理常用的方法 真值表法 演绎法 间接证明法 对于结论形式为R ? C的证明方法 真值表法 真值表法 根据给定前提H1, H2, …, Hn和结论C 构造条件式(H1 ∧ H2 ∧ … ∧ Hn) ? C 的真值表 若该条件式为永真式，则结论C是有效的，即H1, H2, …, Hn ? C是有效的 真值表法 例1.50已知 H1：P ? Q， H2：P，是否能推出结论 C：Q 解：构造真值表： 真值表法 为了简便起见，提供两种方法： 方法1:在真值表中，先找出前提H1, H2, …, Hn的真值均为真的行，若相应行中结论C的真值也为真，则H1, H2, …, Hn ? C为有效结论 真值表法 在例1.50中：已知H1：P ? Q， H2：P，是否能推出结论C：Q 可以仅这样构造真值表： 真值表法 方法2:在真值表中，先找出结论C为假的行，若这些行中，前提H1, H2, …, Hn的真值至少有一个为假，则H1, H2, …, Hn ? C为有效结论 真值表法 在例1.50中：已知H1：P ? Q， H2：P，是否能推出结论C：Q 可以仅这样构造真值表： 演绎法 演绎法 定义：从前提H推出结论C的一个演绎(Deduction)，是构造命题公式的一个序列 A1, A2, …, An ，其中Ai是前提H中的某个前提Hi，或者从Hi或Aj(ji)得到的有效结论，且 An就是C，则称公式C是该演绎的有效结论，或者称从H演绎出C 演绎法 例1.51 考虑下述论证 如果这里有球赛，则通行是困难的 如果他们按时到达，则通行是不困难的 他们按时到达了 所以这里没有球赛 设：设P：这里有球赛，Q：通行是困难的，R：他们按时到达 因此：前提是：P ? Q， R ?? Q，R 结论是： ? P 演绎法 设P：这里有球赛，Q：通行是困难的，R：他们按时到达 前提：P ? Q， R ??