逻辑学真值表及命题演算.ppt

第五章 真值表方法与命题演算 教学重点与要点 完全真值表法的判定功用 归谬赋值法的操作与判定 命题演算证明方法的应用与构 造 一、真值联结词 定义：真值联结词是指仅仅表示复合命 题与肢命题之间真假关系的联结词。 真值联结词主要有五个： （否定）、（合取）、 （析取）、（蕴涵）、 （等值） 二、真值形式 定义：真值形式是指由真值联结词和命题 变项所构成的形式结构。 五种基本的真值形式 否定式： p 合取式：pq 析取式：pq 蕴涵式：pq 等值式：pq 三、五种基本真值形式的真值表 定义，真值表是数理逻辑中用以定义命题 联结词并确定复合命题真或假的一种图表 。 T 表示“真”、F 表示“假” 1、p p p T F F T 2、 pq p q pq T T T T F F F T F F F F 3、pq p q p q T T T T F T F T T F F F 4、pq p q p q T T T T F F F T T F F T 5、pq p q p q T T T T F F F T F F F T 真值表判定程序的三个要求 （1）程序的每一步都是由事先给定的规则明 确规定好的； （2）对于所判定的对象是否具有某种性质， 该程序能够给出唯一确定的结果； （3）该程序能够在有穷步骤结束。 判定程序的特点： 机械的、能行的、可判定的。 完全真值表法 完全真值表的作法 三个步骤： 1、找出已给命题公式的所有变项，并竖行 列出这些变项的所有真值组合； 2、根据命题公式的结构，由繁到简的依次 横行列出，一次只引进一个连接词，直至列出 该公式本身； 3、依据基本真值表，有变项的真值逐步计 算出每个部分的真值，最后列出整个公式得真 值。 完全真值表法的判定功能 （1）命题公式的性质判定 （2）推理形式有效性的判定 （3）命题公式之间关系的判定 重言式、矛盾式、可满足式的判定 1、重言式（又叫永真式）是指在一个命题形 式中不论其中的变项取什么值，该命题形式的 值总是真的。 如： p p p p p p T F T F T T 2、矛盾式（又叫永假式）是指在一个命 题形式中不论其中的变项取什么值，该命 题形式的值总是假的。 如： p p p p p p T F F F T F 3、可满足式（协调式）是指在一个命题 形式中不论其中的变项取什么值，该命题 形式的值至少在一种情况下是真的。 如：p q p q p q T T T T F F F T F F F F 真值表判定任一命题形式是否是重言式。 例1、（pq）p）q p q p pq (pq） p （pq）p ） q T T F T F T T F F T F T F T T T T T F F T F F T 例2、（pq）p） q p q q p q (pq） p （pq）p ） q T T F T T F T F T T T T F T F T F T F F T F F T 真值表判定任意两个复合命题之 间是否具有等值关系 例1、（p q） p q 由真值表可知这两个命题之间具有等值关 系。 p q p q (pq ) (pq)pq T T FF T F F T F FT F T T F T TF F T T F F TT F T T 例2、 （p q）； p q p q p q (p q) (p q)pq T T FF T F F T F FT T F T F T TF T F T F F TT F T T 三、真值表帮助解决一些推理问题 例：列出A、B、C三命题的真值表，并回 答当A、B、C三命题恰有一个为真时，甲 是否是木工？ A、如果甲不是木工，则乙是泥工。 B、如果乙不是泥工，则甲不是木工。 C、甲不是木工，且乙不是泥工 。 解 设p表示“甲是木工”；q表示“乙是泥 工”。 A：pq B：qp C：pq p q p q p q qp pq T T FF T T F T F FT T F F F T TF T T F F F TT F T T 练习题 一、用真值表判定下列真值形式是否是 重言式 1、（Pq） p）q 2、（Pq） q）P 二、请用真值表判定下列各组命题形式之 间是否具有等值关系。 1、 （Pq） Pq 2、 （Pq） Pq 三、列出A、B两命题的真值表，并回答A 、B恰有一个为假时，王军是否考上了大 学？ A：如果王军考上了大学，那么李伟就没 有考上大学。 B：王军没有考上大学。 四、列出A、B、C三命题的真值表，并回答 当A、B、C三命题恰有一真时，是否甲村 所有人家都有彩电？ A、甲村所有人家都有彩电，并且乙村所 有人家都有彩电。 B、或者甲村所有人家都有彩电，或者乙 村所有人家都有彩电。 C、如果乙村所有人家都有彩电，那么甲 村有些人家没有彩电。 真值表法的局限性 1、完全真值表法的局限性 判定多变项命题公式过于繁琐。 2、归谬赋值法的局限性 仅能判定蕴涵式， 3、真值树法的局限性 判定结构复杂的公式时，树冠过大操作不便 。 4、问题： 是否有一种方法既能解决命题逻辑有效性 的判定问题又能解决有效性的推导问题？ 命题演算的证明方法 一、命题演算方法概述 1、命题演算方法在问题求解上的必要性认 知 2、命题演算与形式系统构造 3、公理系统与自然演绎系统 4、自然演绎法的基本思想 5、具体推证方法的认知 直接证明法 间接证明法 反证法 一、直接证明法 1、直接证明法的特点认知 勿需附加任何前提即可依规则从给定的前提推 导出结论。 2、直接证明法的操作步骤 （1）依序编号排列前提，将结论写在最后一 个前提的右侧并用“/”断开。 （2）依据已知前提结合相关规则推出新的命 题，依次编号写在下面。 （3）在推出的新命题右侧括号内注明前提依 据和规则依据。 （4）证明结束写上证毕字样。 推证实例分析 1.AB 2.CD 3.AC BD 直接证明法 1.AB 2.CD 3.AC BD 4.AC (3.等值) 5.AD (4.2.连锁) 6.BA (1.易位) 7.BD (6.4.连锁) 8.BD (7.等值) 证毕。 二、假设证明法 1、间接推证法的特点认知 给定前提不够，需要附加。 2、假设证明法的基本思路 附加假设，依据蕴涵引入的规则有条件 的推出相关结论。 3、假设证明法的模式构造 解法二：假设证法 1.AB 2.CD 3.AC BD 4. B (假设) 4. D (假设) 5. A (1.4.销去) 5. C (2.4.销 去) 6. C (3.5.销去) 6. A (4.5.销去 ) 7. D (2.6.销去) 7. B (1.6.销 去) 8.BD (47.引入) 8.DB (47.引入) 9.BD (8.等值) 9.DB (8.等值) 证毕。 10.BD (9.交换) 证毕。 三、反证法 1、反证法的特点认知 前提不够，需要附加。 附加与结论相矛盾的命题作为假设依 据规则进行推导寻求矛盾。找到矛盾后利 用否定引入或销去规则反证结论成立。 2、反证法的模式构造 解法三：反证法 1.AB 2.CD 3.AC BD 4. (BD) (反设) 5. BD (4.等值) 6. B (5.销去) 7. A (1.6.销去) 8. C (3.7.销去) 9. D (2.8.销去) 10. D (5.销去) 11. DD (9.10.引入) 12.BD (411.销去) 证毕。 假设证明法与反证法的区别与综合应用 一、假设证明法与反证法的区别 二、假设证明法与反证法的综合应用 1、在证明中的综合应用 【例析4301 】 2、在推理中的综合应用 【4302】 三、命题逻辑定理的证明 (pq) p) q p q pq (pq) p (pq) p) q T T T T T T F F F T F T T F T F F T F T 画一个完全真值表 实例分析2 p q pp q q pq T T T F T T F T F T F T T F T F F T F F 永真式 永假式 可真式 * 实例分析3：判断3pq；pq； p q的真假关系 p q pq pq pq T T T T F T F F F T F T T T F F F T T F 等值 矛盾 实例分析4：用归谬赋值法判定（pq ）q）P这个推理是否有效？ （pq）q）P F T F T T T F T T 由上表可知： q 的赋值出现矛盾，此命题形式是重言式 ，与之相对应的推理形式是有效式。 运用归谬赋值法要注意： 由于给变项赋值过程中有先后的不同 ，因而具体矛盾的出现可能不同。 只有当赋值过程中矛盾不可避免的出 现时，才能表明原公式是重言式，相 应的推理有效。 赋值过程中，变项的值有时候不能惟 一的确定，此时需要讨论。 *返回* 1. AB 2. BC 3. CD 4. D /A 5. C （3，4，销去） 6. B （2，5，销去） 7. A （1，6，销去） 证毕。 直接证明法（实例分析一） 直接证法（实例分析二） 1. (AB)C 2. CD 3. BD /A 4. D （2，销去） 5. C （2，销去） 6. B （3，4，销去） 7. (AB) （1，5，销去） 8. AB （7，等值） 9. A （6，8，销去） 证毕。 回溯思考方法 1. A(BC) 2. AD 3. C(EF) 4. DF /E (1)“回溯”思考，首先要考察待证结论与前提的关联性 ，待证结论处在命题的后件，要获证必须基于对前 件C的肯定。 (2) C与前提1关联，要获取必须基于主联结关系的销去 。 (3) 前提1的销去，取决于对前提2中条件A的否定。 (4) 要获取对A的否定，必须基于对后件D的否定，而后件 D的否定处在前提4之中，要获取 D必先分解前提4。 直接证明法：推导结论 1. (BD) 2. CD 3. AB 4. (EF)C 5. AF 6. A (5. 销去) 7. B (3.6.销去) 8. BD (1.7.等值) 9. D (7.8.销去) 10. C (2.9.销去) 11. (EF) (4.10.销去) 12. EF (11.等值) 13. F (5.销去) 14. E (12.13.销去) 直接证明法前提一致性判定 1.AB 2.BC 3.DC 4.AD 5.D 6.C 7.B 8.A 9.A 10.AA 直接证明法前提一致性判定之02 1.AB 2.BC 3.DC 4.AD 5.A 6.B 7. C 8. D 假设证明法的模式构造 1. 给定前提 2. 3. / pq 4. p (假设） : ： ： 10. q 11. pq (4-10 引入） 1. BA 2. B(AC) AC 3. A (假设) 4. B (1.3,销去) 5. AC (2.4.销去) 6. C (5.销去) 7. AC (3.6.引入) 证毕。 假设证明法（实例分析一） 1.AC 2.C(E(HI) 3.FI A(FE) 4. A (假设) 5. C (1.4.销去) 6. E(HI) (2.5.销去) 7. F (假设) 8. I (3.7.销去) 9. IH (8.引入) 10. HI (9.交换) 11. (HI) (10.等值) 12. E (6.11.销去) 13. FE (712.引入) 14. A(FE) (413.引入) 证毕。 假设证明法（实例分析二） 反证法的模式构造 1. 2. / p p (反设) : : : 9. q q 10. p (49. 销去) 证毕。 .1. 2. 3. / p 4. P (反设) : : : 9. q q 10. p (49. 引入) 证毕。 1.A B 2.C B 3. (A C) / A 4. A C (3.等值) 5. A (反设) 6. B (1.5.销去) 7. C (2.6.销去) 8. C (4.5.销去) 9. C C (7.8.引入) 10. A (59. 引入) 证毕。 反证法（实例分析一） 在证明中的综合应用 1. ABC 2. (AB)C BC 3. C (假设) 4. (AB) (2.3.销去) 5. AB (4.等值) 6. AB (1.3.销去) 7. B (反设) 8. A (5.7.销去) 9. A (6.7.销去) 10. AA (8.9.引入) 11. B (710.销去) 12. CB (311.引入) 13. CB