离散数学课件1-命题逻辑.ppt

* 主要内容： 推理的基本概念和形式结构：①推理的前提②推理的结论③推理正确④有效结论? 判断推理是否正确的方法：①真值表法②等值演算法③主析取范式法 推理规则1）P规则2）T规则3）CP规则 消解原理 本节小结： * 学习要求： 熟练掌握判断推理是否正确的三种方法（真值表法，等值演算法，主析取范式法）。 牢记P系统中的各条推理规则。 对于给定的正确推理，要求在P系统中给出严谨的证明序列。? 会用附加前提证明法和反证法。作业：习题1.7 1(4)(5)，2(2), 4(3) * * * * * * * * * * * * * * * * 作业 习题一：5（1）（3）、68(1)（3）、9、10 第六节 命题公式的蕴含 一、定义：设A和B是两个WFF，如果在任何解释下，当A取值1 时，B也取值1，就说A蕴含B。A 蕴含 B记为 A?B。 定理：设A和B是两个WFF， A?B当且仅当 A?B是永真式。 证明要点： 当A?B时，A取值1，B必取值1；A取值0， A?B自然取值1，因而A?B恒取值1，即A?B 是永真式；反过来，当 A?B是永真式时，A取值1时，必然B取值1，从而A?B。 A ? B当且仅当A?B且B?A。 命题公式的蕴涵 注：蕴涵和条件联结词→是完全不同的。→是逻辑联结词，A→B是一个命题公式；?是公式间关系符，A?B不是一个命题公式，仅表示A，B间的蕴涵关系。 三、几个基本蕴含式 P ?Q ?P， P ?Q ?Q～(P ? Q) ? P, ～(P ? Q) ? ～ Q（简化法则） P ? P?Q，Q ? P?Q～P ? P? Q, Q ? P ? Q（扩充法则） P ?（P ? Q） ?Q（假言推理） ～Q∧（P→Q）? ～P （拒取式（否定式假言推论）） * （P∨Q）∧（P→R）∧（Q→R）? R（P→Q）∧（R→S）?（P∧R）→（Q∧S）（二难推论） （P?Q）∧（Q?R）? P?R （等价三段论） （P∨Q）∧（～P∨R）? Q∨R （归结原理） ～P∧（P∨Q）? Q , P∧（ ～ P∨Q）? Q（析取三段论） （P→Q）∧（Q→R）? P→R （假言三段论） 四、蕴含的基本性质 1. A ? A (自反性) 2. 如果A? B且B? A, 则A ? B (反对称性) 3. 如果A? B且A是永真式，则B必是永真式 4. 如果A? B且B? C, 则A? C (传递性) 证明：由已知条件A ? B，且 B ? C，(A→B）∧（B→C） 是永真式；再由假言三段论，应有（A→B）∧（B→C）? A→C ； 再根据性质3， A→C也必是永真式，即A ? C 。 * 5. 如果A? B且A? C, 则A? B ? C证明： 由 A?B 且 A?C得到A?B和A?C都是永真式，于是（A?B）∧（A?C）也是永真式； 而，（A?B）∧（A?C）（～A∨B）∧(～A∨C)～A∨(B∧C)?A→(B∧C)，所以A?(B∧C)是永真式，即A?B∧C。 注：由证明过程可知，A?B∧C可以得到A?B 且 A?C 。 * * 6. 如果 A?C 且 B?C, 则 A? B? C 注：由简化法则和扩充法则，也可导得A ? B? C。 7. A ? B ? C当且仅当 A? B?C 注：这个性质很重要，是CP规则的依据。使我们能把证明 A? B?C 转化为证明 A ? B ? C。 8. A ? B当且仅当 A ? ?B是矛盾式注：这个性质为反证法提供了依据。 定理：A ? B当且仅当 ?BA注：这个性质表达了逆向思维原理，是另一种反证法形式。 二、判定A?B的常用方法 方法一：按照定义，考察对任何使 A取值1的解释是否都能使 B也取值1 。 例：检查（P?Q）? ?R?R?Q 是否成立？ 解: P Q R （P?Q）? ?RR?Q0 0 0110 1 0111 0 0111 1 0111 1 111 由此可见，蕴含式成立。 方法二：考察对任何使B取值0的解释是否都能使A也取值0。 我们只需要考虑： P Q RR?Q（P?Q）? ?R 0 0 100 1 0 100 下面的解释在判别中可以不考虑： 0 1 110 由以上可见，蕴含式成立。 * 例：考虑以下语句，并将其前提和结论符号化。 1)、前提： 　1. 如果明天天晴，我们准备外出旅游。P→Q 　2．明天的确天晴。P 　　结论：我们外出旅游。Q 　上述例子可描述为：P→Q，P?Q　(假言推论) 2)、前提： 　1.　如果一个人是单身汉，则他不幸福。P→Q 　2.　如果一个人不幸福，则他死得早。 Q→R 　　结论：单身汉死得早。 P→R 　上述例