主析取范式的求法.ppt

第一章 命题逻辑 第七讲 定义 对于给定的命题公式，如果有一个等价公式 仅由小项的析取所组成，则该等价式称为原式的主析 取范式。 内容回顾 小项 定义 n个命题变元的合取式，称为布尔合 取或小项，其中每个变元与它的否定不能同时 存在，但两者必须出现且仅出现一次。 每个小项可用n位二进制编码表示。以变元自身出 现的用1 表示，以其否定出现的用0表示： 小项的性质如下： （1）每一个小项当其真值指派与编码相同时，其真值为 1，其余的2n1种均为0; （2）任意两个不同小项的合取式永假： （3）全体小项的析取式永为真，记为： 主析取范式的求法 真值表法 等值演算法 趣味推理题 A、B、C三人去餐馆吃饭，他们每人要的不是 火腿就是猪排。 （1）如果A要的是火腿，那么B要的就是猪排 。 （2）A或C要的是火腿，但是不会两人都要火 腿。 （3）B和C不会两人都要猪排。 谁昨天要的是火腿，今天要的是猪排？ 只有B才能昨天要火腿，今天要猪排。 154 主合取范式 定义1- n个命题变元的析取式，称为布尔析取或 极大项，其中每个变元与它的否定不能同时存 在，但两者必须出现且仅出现一次。 例如，2个命题变元p和Q 的大项为： 3个命题变元p、Q、R的大项为： n个命题变元共有2n个大项，每个大项可表示为 n位二进制编码，以变元自身出现的用0表示，以变元的 否定出现的用1表示；且对应十进制编码。这一点与小 项的表示刚好相反。 若n= 2，则有 若n= 3，则有: 大项的性质如下： (1)每一个大项当其真值指派与编码相同时，其真值为0， 其余的2n1种赋值均为1; (2)任意两个不同大项的析取式永真： (3)全体大项的合取式必为假，记为： 定义1- 对于给定的命题公式，如果有一个等价公式仅由极 大项的合取所组成，则该等价式称为原式的主合取范式 。 定理1- （主合取范式存在惟一定理） 任何命题公式的主 合取范式一定存在，并且惟一。 由真值表方法可知：一个公式的真值为0的真值指派 所对应的大项的合取，即为此公式的主合取范式。 例1- 用真值表方法求 的主合取范式 解: 公式的真值表如下 P Q R PQ R(pQ)R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 所以公式 的主合取范式为: 用等值演算方法构成主合取范式的主要步骤如下 ： （1）将原命题公式化归为合取范式； （2）除去合取范式中所有永真的合取项； （3）合并相同的析取项和相同的变元； （4）对合取项补入没有出现的命题变元，即添加 如(pp) 的式子，再按分配律进行演算； （5）将大项按下标由小到大的顺序排列。 例1- 用等值演算方法求 的主合取范式。 解： 【说明】 (1)主析取范式的析取项为小项，用小m加下标表示 。如m010，其中0表示对应的命题变元的否定出现 在析取项中,1表示对应的命题变元出现在析取项 中。 (2)主合取范式的合取项为大项,用大M加下标表示,如 M010,其中0表示对应的命题变元出现在合取项中,1 表示对应命题变元的否定出现在合取项中。 (3)在真值表中,一个公式的主析取范式由其真值为1 的真值指派所在对应的小项的析取组成。 (4)在真值表中,一个公式的主合取范式由其真值为0 的真值指派所对应的大项的合取所组成。 极小项与极大项 由p, q两个命题变项形成的极小项与极大项 公式 成真赋值赋值 名称 公式 成假赋赋 值值 名称 p q p q p q p q 0 0 0 1 1 0 1 1 m0 m1 m2 m3 p q p q p q p q 0 0 0 1 1 0 1 1 M0 M1 M2 M3 极小项项 极大项项 由p, q, r三个命题变项形成的极小项与极大项 极小项项 极大项项 公式 成真 赋值赋值 名称 公式 成假 赋值赋值 名称 p q r p q r p q r p q r p q r p q r p q r p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 m0 m1 m2 m3 m4 m5 m6 m7 p q r p q r p q r p q r p q r p q r p q r p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 M0 M1 M2 M3 M4 M5 M6 M7 1.6 蕴含公式 如果双条件命题AB 为重言式，则A B 。而 条件命题AB 是不对称的，如果AB为真，B不一 定能推出A 。那么A和B究竟存在什么关系呢？ 161 蕴含公式 定义1-26 设A，B是命题公式, 若AB是重言式, 则 称AB是蕴含重言式，记为AB ，读作“A永真蕴 含B”。简称A蕴含B 即 AB iff AB 1 注意: 与 是意义不同的符号。 证明： 所以P(pQ)Q 下面介绍几种证明A永真蕴含B的方法。 方法一：用真值表法或等价变换(推导)法证明AB 1 。 例1-24 证明 。 P Q PQ P(PQ) (P(PQ) )Q 0 0 0 1 1 0 1 1 1 1 0 1 0 0 0 1 1 1 1 1 方法二：通过分析的方法来证明一个条件命题是蕴含 式。由于原命题等于其逆反命题，即 ABBA ，所以用分析法证明AB ， 有 如下两种方法: (1) 假设前件A为真时, 推出后件B也为真, 则AB ; (2) 假设后件B为假时, 推出前件A也为假, 则AB 。 例1-25 证法1： 证法2： 例1-26 如果我认真学习，我的“离散数学”不会不及格， 如果我不热衷于玩电子游戏，我将认真学习， 但我的“离散数学”不及格。 结论：我热衷于玩电子游戏。 证明： 设P：我认真学习。 Q：我的“离散数学”及格。 R：我热衷于玩电子游戏。 常见的蕴含重言式 析取三段论 假言推论 拒取式 假言三段论 二难推论 化简式一 附加式 化简式二 例1-27 分析证明 。 证明：假设后件 为0，则P为1，R 为 0。 (a)若Q为1，则 为0，所以 为0； (b)若Q为0，则 为0，所以 为0。 故此： 成立。 162 蕴含公式的性质 （1）设A、B是命题公式，若AB 且A为重言式，则 B必是重言式。 证明: 因为AB ，所以 AB 为1，又因为A为1，所以B 为1，即B为重言式。 （2）蕴含关系是传递的，即AB 且BC ， 则AC 。 1.8 推理理论 逻辑学的主要任务是提出一套推理规则，按照公认的 推理规则从前提集合中推导出一个结论来，这个推理过程 称为演绎或形式证明。 在一般的论证中，主要是根据实践经验。如果确认前 提为真，并遵守恰当的推理规则，则可期望所得的结论也 是真的。倘若认定前提是真的，从前提推导出结论的论证 是遵守逻辑推理规则，且公认此结论是真实的，则这个论 证称为合法论证。一般论证中必须特别注意论证的合法性 。 所谓合法是指前提和结论都符合客观实际情况，大家 公认是真实的。即合情、合理、合法，令人信服。 在数理逻辑中情况稍有不同，它把注意力 集中在推理规则的研究上，如果依据这些推理 规则，从前提推导出来的任何结论都称为有效 结论，这种论证称为有效论证。在确认论证有 效性时，前提与结论的真实性不起任何作用， 也就是说，在数理逻辑中，只关心论证的有效 性，而不大关心论证的合法性。 前提：如果马会飞或羊吃草，则母鸡就会是飞鸟 ；如果母鸡是飞鸟，那么烤熟的鸭子还会跑； 烤熟的鸭子不会跑。 结论：羊不吃草。 蕴含式的定义是：给定两个命题公式A和B，当且仅当 AB 是一个重言式，则称A蕴含B，记为 AB ，又称 B是A的有效结论或B由A逻辑推出。这个定义可以推广到 有n个前提的情况。 定义1-27 设 是命题公式，当且仅当 则称C是前提集合 的有效结论。 判别有效结论的过程就是论证的过程，论证方法千变万化 ，但基本方法是真值表法、直接证法和间接证法。 （一）真值表法 设 是出现的前提集合 和C中的所有命题分量，假定对 作全 部的真值指派就能确定 和C的 真值，那么通过真值表就可以确定结论C是否是前提集 合的有效论证，这个方法称为真值表法。 利用真值表判别一个有效论证的方法： 方法一： 在真值表上，若前提 H1,H2,H3,Hn 均为真的所有行 ，结论C也为真，则论证有效。 方法二： 在真值表上，若结论C为假的每一行，其前提 H1,H2,H3,Hn 中至少有一个为假，则论证有效。 例1-28 如果我认真学习，我的“离散数学”不会不及格， 如果我不热衷于玩电子游戏，我将认真学习， 但我的“离散数学”不及格。 结论：我热衷于玩电子游戏。 P:我认真学习， Q:我的“离散数学”及格， R:我热衷于玩电子游戏。 符号化为： 其真值表如下： 解： 判断法一：真值表中，只有第2行的前提都为1，其结论 也为1，所以论证有效。 判断法二：真值表中，第1、3、5、7行为0，每行的前 提至少有一个为0，所以论证有效。 P Q RRpQRpQ R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 1 1 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 0 1 pqpqpq 00111 01110 10001 11100 （二）构造证明法 (1)推理规则 常用的推理规则有： P规则： 在推导的任意一步都可以引入一个前提。 T规则： 如果公式S等价于或被重言蕴含在一个或多个前提或中 间结果命题中，则推导中可以引入S。 CP规则： 如果能从R及一组前提推导出C，则可从这组前提推导出 RC。 设设前提 若 则则 (2)推理定律 在推导过程除推理规则外,还需要推理定律,这些推理定 律就是前面所讲的常用的蕴含