chap5命题逻辑讲义.ppt

* 推论5.5.1 对于L的任意合式公式A,B,C有{(A?B),(B?C)}├(A?C) 证明：根据演绎定理，只需证明： {(A?B),(B?C),A}├ C (A?B) 假设 (B?C) 假设 A 假设 B 1),3),MP C 2),4),MP 以上结果称作“假言三段论”规则，简记为HS规则，对HS规则再次应用演绎定理，又可得以下结果：{(A?B)}├((B?C)?(A?C))以及 ├((A?B)?((B?C)?(A?C))) * 利用HS规则，可得如下定理： 定理5.5.2 对于L的任意合式公式A和B， 有： (a)├(?B?(B?A)) （b)├((?A?A)?A) 证明:（a)的证明序列如下： (?B?(?A??B)) (L1) ((?A??B)?(B?A)) (L3) (?B?(B?A)) 1),2),HS 此结果在例1中证过，应用HS规则后，证明减少了4步。 * 对(b)├((?A?A)?A),先证{(?A?A)}├A: (?A?A) 假设 (?A?(??(?A?A)??A)) (L1) (??(?A?A)??A)?(A??(?A?A))(L3) (?A?(A??(?A?A))) 2),3),HS (?A?(A??(?A?A)))? ((?A?A)?(?A??(?A?A))) (L2) (?A?A)?(?A??(?A?A)) 4),5),MP (?A??(?A?A)) 1),6),MP (?A??(?A?A))?((?A?A)?A) (L3) (?A?A)?A 7),8),MP A 1),9),MP 从而由演绎定理，得├((?A?A)?A)。 * 5.4 推理理论 本节知识点： 本节主要掌握判断推理是否正确的三种方法： 真值表法 等值演算法 构造证明法 * 推理理论 在数学中，要通过推理和证明来建立定理，定理证明中的每一步骤都是根据逻辑推理中的规则，从某些称之为前提的命题推出另一些称之为结论的命题。 数理逻辑以推理为研究对象，用数学的方法来研究推理的形式结构和推理规则，也即在研究推理时，并不考虑具体的前提和结论之间的推理关系，并不涉及前提和结论的涵义，而是研究前提和结论的逻辑形式之间的关系。 * 定义5.4.1 设G和H是两个命题公式。如果G?H是重言式，则称H是G的逻辑结果，或称G蕴涵H，记为G?H. 这里的符号“?”是一个关系词，而不是逻辑联结词。 由联结词“?”的定义知：G?H是重言式，当且仅当对G，H的任意解释I，若I满足G,则I也满足H，因此，G?H的充要条件是，满足G的解释均满足H. * 例如： P Q P ∧Q P ∨Q P∧Q→ P∨Q P∨Q → P∧Q 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 1 1 * 定义5.4.1的推广 定义5.4.2 设G1,…,Gn，H是命题公式，n?1，若 G1?…?Gn ?H 则称H是G1,…,Gn 的逻辑结果，或称G1,…,Gn 共同蕴涵H。记为 G1，…，Gn ?H 其中，G1，…，Gn称为前提，H称为结论．所谓推理正确，就是指由一组前提G1，…，Gn ，能逻辑地推出结论H。 * 下面举例说明用真值表法与等值演算两种方法来判断推理是否正确． 注意：对于一段用自然语言叙述推理的文字，将它抽象成命题逻辑的推理形式，要做这样一些形式化工作： 1、找出语句中的简单命题，再将其符号化； 2、使用逻辑联接词来构成复合命题； 3、分别找出前提和结论； 4、构成推理的形式结构。 此后，利用推理规则来判断推理的正确性。 * 判断推理的例子 例：如果我进城，我就去书店．我没有进城．所以我没有去书店． 解：Ｐ：我进城．　　Ｑ：我去书店． 　　前提：P?Q, ?P 结论：?Ｑ 推理的形式结构： （（P?Q）∧? P）??Q * 真值表法 Ｐ　Ｑ (P?Q)??Ｐ ?Q ０　０ 1 1 ０　１ 1 0 １　０ 0 1 １　１ 0