第1章命题逻辑.ppt

例1-5-3.2学院安排课表，教语言课的教师希望将课程安排在第一或第三节；教数学课的教师希望将课程安排在第二或第三节；教物理课的教师希望将课程安排在第一或第二节。如何安排课表，使得三位教师都满意。 解：令L1、L2、L3分别表示语言课排在第一、第二、第三节。 M1、M2、M3分别表示数学课排在第一、第二、第三节。 P1、P2、P3分别表示物理课排在第一、第二、第三节。 三位教师都满意的条件是：A?(L1?L3)?(M2?M3)?(P1?P2 ) 为真。 (L1?L3)?(M2?M3)?(P1?P2 ) ? ((L1?M2)?(L1?M3)?(L3?M2)?(L3?M3))?(P1?P2) ?(L1?M2?P1)?(L1?M3?P1)?(L3?M2?P1)?(L3?M3?P1)?(L1?M2?P2)?(L1?M3?P2)?(L3?M2?P2)?(L3?M3?P2) 因为同一时间只能安排一门课程，因此只有两种排法可以满足条件并且是合理的：L3 ?M2?P1和L1?M3?P2，暨语言课排在第三节、数学课排在第二节、物理课排在第一节或者语言课排在第一节、数学课排在第三节、物理课排在第二节。 §1-6命题逻辑的蕴含关系§1-6-1 蕴含 定义1-6-1.1设A和B是两个命题公式，若A→B是永真式，则称A蕴涵B，记作A?B，称A?B为蕴涵式或永真条件式，并称A为蕴含式的前件或前提，B为蕴含式的后件或结论。 等价式与蕴涵式之间的关系：设A和B是两命题公式，A?B的充要条件是A?B且B?A。 §1-6-2 证明蕴含关系的方法 （1）真值表证明A→B是重言式。 （2）逻辑推演证明：可以使用如下任何一种方法 ① 前件真推导后件真方法 设条件式的前件指派为真，若能推导出后件真值也为真，则条件式是永真式，故蕴涵式成立。 ② 后件假推导前件假方法 设条件式的后件指派为假，若能推导出前件真值也为假，则条件式是永真式，即蕴涵式成立。 例1-6-2.1求证?Q?(P?Q)? ?P。 证明 ①前件真推导后件真方法：设?Q?(P?Q)为T，则?Q，(P?Q)皆为T，于是Q为F，P?Q为T，则必须P为F，故?P为T。 ②后件假推导前件假方法：假定?P为F，若Q为F，则P?Q为F，?Q?(P?Q)为F；若Q为T，则?Q为F，?Q?(P?Q)为F，故?Q?(P?Q)? ?P。 §1-6-3 基本蕴涵式 由以上方法可证明得到常用的蕴涵式如下： 1. A ? (A?B) 附加律 2. (A?B) ? A 化简律 3. (A?B)?A ? B 假言推理 4. (A?B) ?? B ? ?A 拒取式 5. (A?B) ?? B ? A 析取三段论 §1-6-3 基本蕴涵式 6. (A?B)?(B?C) ? (A?C) 假言三段论 7. (A?B)?(B?C) ? (A?C) 等价三段论 8. (A?B)?(C?D)?(A?C) ? (B?D) 构造性二难推理 (A?B)?(C?D)?( ?B??D) ? (?A??C) 破坏性二难推理 §1-7命题逻辑的推理理论§1-7-1 论证的有效性 定义1-7-1.1设A1, A2, …, Ak, B为命题公式. 若对于每组赋值，A1?A2?…? Ak 为假，或当A1?A2?…?Ak为真时，B也为真，则称由前提A1, A2, …, Ak推出结论B的推理是有效的, 并称B是有效结论。 实际上，有效推理的过程就是证明永真蕴含式的过程，即令A1?A2?…? Ak是已知的命题公式(前提)，若有A1?A2?…?Ak ? B 则称B是A1, A2, …, Ak的有效结论。 可见无效论证为：若前提皆是真命题而结论是假命题。 在命题逻辑推理中应注意区分“有效“和“真“是截然不同的概念：有效的推理不一定产生真实的结论；产生真实结论的推理过程未必是有效的；有效的推理中可能包含假的前提；而无效的推理却可能包含真的前提；如果前提全是真，则有效结论也应该真而绝非假。 §1-7-2 有效论证的判断方法 判断推理是否有效的方法： （1）真值表法 （2）等值演算法 （3）主析取范式法 （4）逻辑推演法 例1-7-2.1判断下面推理是否正确。 (1) 若今天是1号，则明天是5号。 今天是1号，所以明天是5号。 (2) 若今天是1号，则明天是5号。 明天是5号， 所以今天是1号。 (3) 若今天是1号，则明天是5号。 明天不是5号， 所以今天不是1号。 解: 令 p：今天是1号。q：明天是5号。