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

1 离散数学云南大学软件学院任课教师 谢仲文2013年秋季学期 2 绪论课程介绍和要求 主要内容教材说明什么是离散数学 为什么要学习离散数学 怎样学习离散数学 课程要求与考试 3 教材 主教材 1 郝林等编著 离散数学 北京 科学出版社 2012年5月参考书目 2 屈婉玲等编著 离散数学 北京 高等教育出版社 2008年3月3 左孝凌等编著 离散数学 上海 上海科学技术文献出版社 2004年1月 4 问题什么是数理逻辑 符号化 推理规则 经典数理逻辑和现代数理逻辑主要内容命题逻辑谓词逻辑推理与证明技术 第一部分数理逻辑 5 第一讲命题逻辑的基本概念 主要内容命题与联结词命题及其分类联结词与复合命题命题公式及其赋值 6 命题与真值命题 判断结果惟一的陈述句命题的真值 判断的结果真值的取值范围 真与假真命题与假命题注意 感叹句 祈使句 疑问句都不是命题陈述句中的悖论 判断结果不惟一确定的不是命题 1 1命题与联结词 7 悖论 如果有一个句子B 如果承认B 则可以推出非B成立 反之 如果承认非B 又可推出B成立 例子 1 我正在说假话 2 罗素的理发师悖论 3 克里特人伊壁孟德 所有的克里特人都是撒谎者 悖论不是命题 悖论的共同特征 论断者属于论断主体集 8 例1下列句子中那些是命题 1 是有理数 2 2 5 7 3 x 5 3 4 你去教室吗 5 这个苹果真大呀 6 请不要讲话 7 2050年元旦下大雪 假命题 命题概念 真命题 不是命题 不是命题 不是命题 不是命题 命题 但真值现在不知道 判断给定句子是否为命题的方法和步骤 1 判断它是否为陈述句 2 判断它是否有唯一的真值 9 命题分类 简单命题 也称原子命题 与复合命题简单命题符号化 命题常量用小写英文字母p q r pi qi ri i 1 表示简单命题用 1 或 1 表示真 用 0 或 0 表示假例如 令p 是有理数 p的真值为0 q 2 5 7 q的真值为1 复合命题符号化 由常量和联结词组成的公式 命题分类 10 否定 合取 析取联结词 定义1 3设p q为两个命题 复合命题 p或q 称作p与q的析取式 记作p q 称作析取联结词 规定p q为假当且仅当p与q同时为假 定义1 1设p为命题 复合命题 非p 或 p的否定 称为p的否定式 记作 p 符号 称作否定联结词 规定 p为真当且仅当p为假 定义1 2设p q为两个命题 复合命题 p并且q 或 p与q 称为p与q的合取式 记作p q 称作合取联结词 规定p q为真当且仅当p与q同时为真 11 例2将下列命题符号化 1 吴颖既用功又聪明 2 吴颖不仅用功而且聪明 3 吴颖虽然聪明 但不用功 4 张辉与王丽都是三好生 5 张辉与王丽是同学 合取联结词的实例 12 解令p 吴颖用功 q 吴颖聪明 1 p q 2 p q 3 p q 4 设p 张辉是三好生 q 王丽是三好生p q 5 p 张辉与王丽是同学 1 3 说明描述合取式的灵活性与多样性 4 5 要求分清 与 所联结的成分 合取联结词的实例 13 例3将下列命题符号化 1 2或4是素数 2 2或3是素数 3 4或6是素数 4 小元元只能拿一个苹果或一个梨 5 王小红生于1975年或1976年 析取联结词的实例 14 解 1 令p 2是素数 q 4是素数 p q 2 令p 2是素数 q 3是素数 p q 3 令p 4是素数 q 6是素数 p q 4 令p 小元元拿一个苹果 q 小元元拿一个梨 p q p q 5 p 王小红生于1975年 q 王小红生于1976年 p q p q 1 3 为相容或 4 5 为排斥或合取和析取如何记忆 析取联结词的实例 15 定义1 4设p q为两个命题 复合命题 如果p 则q 称作p与q的条件式 记作p q 并称p是条件式的前件 q为条件式的后件 称作条件联结词 规定 p q为假当且仅当p为真q为假 蕴涵联结词 1 p q的逻辑关系 q为p的必要条件 2 如果p 则q 有很多不同的表述方法 若p 就q只要p 就qp仅当q只有q才p除非q 才p或除非q 否则非p 3 当p为假时 p q恒为真 4 常出现的错误 不分充分与必要条件 16 例4设p 天冷 q 小王穿羽绒服 将下列命题符号化 1 只要天冷 小王就穿羽绒服 2 因为天冷 所以小王穿羽绒服 3 若小王不穿羽绒服 则天不冷 4 只有天冷 小王才穿羽绒服 5 除非天冷 小王才穿羽绒服 6 除非小王穿羽绒服 否则天不冷 7 如果天不冷 则小王不穿羽绒服 8 小王穿羽绒服仅当天冷的时候 蕴涵联结词的实例 p q 注意 p q与 q p p q等值 真值相同 p q p q q p q p p q q p q p 17 定义1 5设p q为两个命题 复合命题 p当且仅当q 称作p与q的等价式 记作p q 称作等价 双条件 联结词 规定p q为真当且仅当p与q同时为真或同时为假 p q的逻辑关系 p与q互为充分必要条件 等价联结词 例5求下列复合命题的真值 1 2 2 4当且仅当3 3 6 2 2 2 4当且仅当3是偶数 3 2 2 4当且仅当太阳从东方升起 4 2 2 4当且仅当美国位于非洲 5 函数0 x 在x0可导的充要条件是它在x0连续 1 0 0 1 0 18 自学内容 课本P8 P9 四种次重要联结词 19 本小节中p q r 均表示命题 联结词集为 p p q p q p q p q为基本复合命题 其中要特别注意理解p q的涵义 反复使用 中的联结词组成更为复杂的复合命题 复合命题的各个原子命题之间可以无任何实际联系 设p 是无理数 q 3是奇数 r 苹果是方的 s 太阳绕地球转则复合命题 p q r s p 是假命题 小结 联结词的运算顺序 同级按先出现者先运算 联结词的对称性 20 1 2命题公式及其赋值 命题变项与合式公式命题变项合式公式合式公式的层次公式的赋值公式赋值公式类型真值表 21 命题变项与合式公式 命题常项 命题变项 命题变元 类比常量和变量 常项与变项均用p q r pi qi ri 等表示 定义1 6合式公式 简称公式 的递归定义 1 单个命题变项和命题常项是合式公式 称作原子命题公式 2 若A是合式公式 则 A 也是 3 若A B是合式公式 则 A B A B A B A B 也是 4 只有有限次地应用 1 3 形成的符号串才是合式公式 几点说明 1 命题公式可以是没有真假值的 2 并不是由命题常 变 元 联结词和一些括号组成的字符串都能成为命题公式 3 递归定义 由基础 归纳和界限组成 22 合式公式的层次 定义1 7 1 若公式A是单个命题变项 则称A为0层公式 2 称A是n 1 n 0 层公式是指下面情况之一 a A B B是n层公式 b A B C 其中B C分别为i层和j层公式 且n max i j c A B C 其中B C的层次及n同 b d A B C 其中B C的层次及n同 b e A B C 其中B C的层次及n同 b 3 若公式A的层次为k 则称A为k层公式 例如公式A p B p C p q D p q r E p q r r s 分别为0层 1层 2层 3层 4层公式 23 第二讲命题逻辑的等值演算 上一讲主要内容回顾 简单命题和复合命题 5个重要联结词 命题常项和命题变项 公式的递归定义 公式的层次 第二讲主要内容1 4真值表与等价公式1 5重言式与蕴含式 24 定义1 8设p1 p2 pn是出现在公式A中的全部命题变项 给p1 p2 pn各指定一个真值 称为对A的一个赋值或解释 若使A为1 则称这组值为A的成真赋值 若使A为0 则称这组值为A的成假赋值 例 如000 010 101 110是 p q r的成真赋值001 011 100 111是成假赋值 说明 A中仅出现p1 p2 pn 给A赋值 1 2 n是指p1 1 p2 2 pn n i 0或1 i之间不加标点符号A中仅出现p q r 给A赋值 1 2 3 是指p 1 q 2 r 3 思考 含n个命题变项的公式有多少个赋值 公式赋值 25 定义1 4 1将命题公式A在所有赋值下取值的情况列成表 称作A的真值表 构造真值表的步骤 1 找出公式中所含的全部命题变项p1 p2 pn 若无下角标则按字母顺序排列 列出2n个全部赋值 从00 0开始 按二进制加法 每次加1 直至11 1为止 2 按从低到高的顺序写出公式的各个层次 3 对每个赋值依次计算各层次的真值 直到最后计算出公式的真值为止 真值表 26 例6写出下列公式的真值表 并求它们的成真赋值和成假赋值 1 p q r 2 q p q p 3 p q q 真值表 27 1 A p q r 成真赋值 000 001 010 100 110 成假赋值 011 101 111 真值表1 28 2 B q p q p 成真赋值 00 01 10 11 无成假赋值 真值表2 29 3 C p q q的真值表 成假赋值 00 01 10 11 无成真赋值 真值表3 30 问题思考 1 回顾 含n个命题变元的公式共有多少个不同的赋值 2 含n个命题变元的真值表共有多少种不同的真值情况 3 真值表与公式之间的关系 31 公式的类型 定义1 10 1 若A在它的任何赋值下均为真 则称A为重言式或永真式 2 若A在它的任何赋值下均为假 则称A为矛盾式或永假式 3 若A不是矛盾式 则称A是可满足式 由例1可知 p q r q p q p p q q分别为非重言式的可满足式 重言式 矛盾式 思考 重言式与可满足式 矛盾式之间的关系 32 真值表的用途 真值表可用于求出公式的全部成真赋值与成假赋值 判断公式的类型注意 1 如果两个公式的真值表对所有赋值最后一列都相同 则称两个公式的真值表相同 2 真值表只考虑最后的结果 而不考虑构造真值表的中间过程 33 等价公式 概念 两种定义 1 给定两个命题公式A和B 设P1 P2 Pn为所有出现于A和B中的原子变元 若给P1 P2 Pn任一组真值指派 A和B的真值都相同 则称A和B是等价公式或逻辑相等 记作A B 2 若等价式A B是重言式 则称A与B等值 记作A B 并称A B是等值式 A和B是等价公式 说明 1 与 的区别 2 A或B中可能有哑元出现 例 p q p q r r r为左边公式的哑元 34 等值式例题 例1判断下列各组公式是否等值 1 p q r 与 p q r 结论 p q r p q r 35 等值式例题 2 p q r 与 p q r 结论 p q r 与 p q r不等值 36 基本等价公式 1 2 双重否定律 A A幂等律A A A A A A交换律A B B A A B B A结合律 A B C A B C A B C A B C 分配律A B C A B A C A B C A B A C 德摩根律 A B A B A B A B吸收律A A B A A A B A 37 基本等价公式 2 2 零律A 1 1 A 0 0同一律A 0 A A 1 A排中律A A 1矛盾律A A 0蕴涵等值式A B A B等价等值式A B A B B A 假言易位A B B A等价否定等值式A B A B归谬论 A B A B A特别提示 必须牢记这16组等值式 这是继续学习的基础 38 等价演算 1 等值演算 由已知的等值式推演出新的等值式的过程2 等值演算的基础 1 等值关系的性质 自反性 对称性 传递性 2 基本的等值式 3 置换规则 关于如何应用16组基本等价公式 39 置换规则 定义1 4 3如果A是合式公式 A 的一部分 且A本身也是一个合式公式 则称A为合式公式 A 的子公式 定理1 4 1 置换规则P17定理1 3 3 设 A 是含公式A的命题公式 A为 A 的子公式 B 是用公式B置换 A 中所有的A后得到的命题公式 若B A 则 B A 40 等值演算的应用举例 1 2 证明两个公式等值例2证明p q r p q r证p q r p q r 蕴涵等值式 置换规则 p q r 结合律 置换规则 p q r 德摩根律 置换规则 p q r 蕴涵等值式 置换规则 注 可在注明中省去置换规则思考 可否用等值演算直接证明两个公式不等值 41 证明两个公式不等值例3证明p q r 与 p q r不等值证方法一真值表法方法二观察法 观察到000 010是左边的成真赋值 是右边的成假赋值方法三先用等值演算化简公式 然后再观察p q r p q r p q r p q r p q r更容易看出前面的两个赋值分别是左边的成真赋值和右边的成假赋值 等值演算的应用举例 2 2 42 作业 复习本次课的内容作业本 P45的4 5 P45的7 P46 8的 4 6 预习下次课内容 蕴含式 43 第三讲蕴含式 上一讲主要内容回顾 赋值 解释 成真赋值 成假赋值 真值表 重言式 矛盾式 可满足式 等价公式 两种定义 16组基本等价关系 子公式 置换规则 第三讲主要内容1 5蕴含式 44 判断公式类型 A为矛盾式当且仅当A 0A为重言式当且仅当A 1例4用等值演算法判断下列公式的类型 1 q p q 2 p q q p 3 p q p q r 等值演算判断公式类型 1 2 解 1 q p q q p q 蕴涵等值式 q p q 德摩根律 p q q 交换律 结合律 p 0 矛盾律 0 零律 矛盾式 45 判断公式类型 2 2 2 p q q p p q q p 蕴涵等值式 p q p q 交换律 1重言式 3 p q p q r p q q r 分配律 p 1 r 排中律 p r 同一律 可满足式 存在哑元 101和111是成真赋值 其它都是成假赋值 46 重言式的性质 定理1 5 1任何两个重言式的合取或析取 仍然是一个重言式 定理1 5 2一个重言式 对同一分量 命题变量 都用任何的同一个合式公式置换 其结果仍为一重言式 代入规则 注意与置换规则的比较 思考 1 举出与定理对应的例子 2 矛盾式的情况 3 可满足式的情况 47 蕴含式 定义a设P Q是两个公式 称Q是P的逻辑结果 或称P蕴涵Q 当且仅当对P Q的任意解释I 如果I满足P 则I也满足Q 记作P Q 定义b当且仅当P Q是一个重言式时 我们称 P蕴含Q 并记作P Q 注意 1 P Q不是对称式2 和 的区别逆换式 Q P 反换式 P Q 逆反式 Q P由真值表可见 P Q Q PQ P P Q即 条件命题公式与其逆反式是等价的 48 蕴含式的证明方法 根据真值表 要证P Q 只需证对于任意的P的成真赋值I I也是Q的成真赋值 根据蕴含式定义 要证P Q 只需证P Q是重言式 对于P Q来说 只有P的真值取1 Q的真值取0这样一种指派时 P Q的真值为0 破坏该条件 证明P Q是重言式方法 证法一 假设前件P为1时 导出后件Q为1 前真看后真 证法二 假设后件Q为0时 前件P为0 后假看前假 49 练习 推证 Q P Q P 证法2 后假看前假 假定 P为F 则P为T a 若Q为F 则P Q为F Q P Q 为F b 若Q为T 则 Q为F Q P Q 为F 所以 Q P Q P成立 证法1 前真看后真 假定 Q P Q 为T 则 Q为T 且 P Q 为T 由Q为F 则必须P为F 故 P为T 50 多前提蕴含 设G1 Gn H是公式 称H是G1 Gn的逻辑结果 或称G1 Gn共同蕴涵H 当且仅当公式G1 Gn蕴涵H G1 Gn共同蕴涵H记为 G1 Gn H 显然 公式H是G1 Gn的逻辑结果的充要条件是 公式 G1 Gn H 是恒真的 例如 P P Q共同蕴涵Q 定理 如果H1 Hm P共同蕴涵公式Q 则H1 Hm共同蕴涵公式P Q 例如 因为公式P Q Q R P共同蕴涵R 所以P Q Q R共同蕴涵P R 51 证明 1 因为 H1 Hm P Q 所以公式 H1 Hm P Q是恒真的 2 利用下面的基本等价公式 P1 P2 P3 P1 P2 P3 3 于是 H1 Hm P Q H1 Hm P Q 故 H1 Hm P Q 是恒真的 4 结论 H1 Hm共同蕴涵P Q 定理证明 52 基本蕴含式 P Q PP Q QP P QQ P Q P P Q Q P Q P Q P P Q QP Q P Q P P Q QP P Q Q Q P Q PP Q Q R P RP Q P R Q R R 53 蕴含式 性质1 定理1 5 4设P Q为任意两个命题公式 P Q的充分必要条件是P Q且Q P 思考和总结 两个命题公式等价的证明方法有哪些 1 真值表法 2 对基本等价公式使用置换规则 3 从重言式出发使用代入规则 4 分别证明P Q且Q P 5 54 蕴含式 性质2 蕴含的常用性质 1 设A B C为合式公式 若A B且A是重言式 则B必是重言式 2 若A B B C 则A C 即蕴含关系是传递的 3 若A B 且A C 那末A B C 4 若A B C B 则 A C B 55 多前提蕴含的证明方法 若给出前提集合S G1 Gk 公式G 证明S G的方法如下 原理 根据一些基本等价式和基本蕴涵式 从S出发 演绎出G 在演绎过程中遵循以下三条规则 规则1 可随便使用前提 P规则 规则2 可随便使用前面演绎出的某些公式的逻辑结果 T规则 规则3 如果需要演绎出的公式是P Q的形式 则我们可将P做为附加前提使用 而力图去演绎出Q CP规则 56 多前提蕴含的证明例子 例 证明 P Q S R P Q R S R P规则1R规则3P规则2 由1 2根据10P Q S 规则1Q S规则2 由3 4根据11Q规则1S规则2 由5 6根据11R S规则3 根据2 7 57 回顾 1 6其他联结词回顾4种次重要联结词 58 真值函数 定义 0 1 上的n元函数0 0 1 n 0 1 称为n元真值函数 4个一元真值函数确定了4个不等价的命题公式 真值函数确定了所需的联结词的个数 一元真值函数确定了只需要一个一元算子 59 二元真值函数 由表可见只需要九个联结词 60 二元真值函数 2元真值函数按序排列 61 公式与真值函数 任何一个含n个命题变项的命题公式A都对应惟一的一个n元真值函数F F恰好为A的真值表 等值的公式对应的真值函数相同 例如 p q p q都对应 62 联结词完备集 定义设S是一个联结词集合 如果任何n n 1 元真值函数都可以由仅含S中的联结词构成的公式表示 则称S是联结词完备集 若S是联结词完备集 则任何命题公式都可由S中的联结词表示 63 极小联结词完备集 由 P Q P Q Q P 故可把包含 的公式等价变换为包含 和 的公式 由P Q P Q 说明包含 的公式可以变换为包含 和 的公式 由P Q P Q P Q P Q 故由 这五个联结词组成的命题公式 必可由 或 组成的命题公式等价置换 一个联结词完备集中 若不包含冗余的联结词 则称该集合为一个极小联结词完备集 64 其他联结词 对于其他联结词 有下列性质 PQ P Q PQ P Q P Q P Q P Q P Q 结论 S 是联结词完备集 65 联结词完备集 思考判断以下是否是联结词完备集 1 S1 2 S2 3 S3 4 S4 5 S5 证明 1 2 在联结词完备集中加入新的联结词后仍为完备集 3 A B A B 4 A B A B 5 A B A B 不是联结词完备集 0不能用它表示它的子集 等都不是 66 极小完备集 定理2 7 与 为联结词完备集 证明 为完备集 p p p p p p pp q p q p q p p q q p q p q p q p q p q 得证 为联结词完备集 对 类似可证结论 任意命题公式都可由仅包含 或 的命题公式等价代换 或 为极小完备集 极小完备集亦可为 或 67 第一章数理逻辑1 7对偶与范式 67 1 7对偶 命题公式中仅含有 中的联结词观察教材p16 表1 22等价公式联结词符号的特征 找出规律 如 分配律P Q R P Q P R P Q R P Q P R 68 对偶式 定义 1 7 1在给定的命题公式中 仅含有 三种联结词 将联结词 换成 将 换成 若有特殊变元0和1亦互相取代 所得公式A 称为A的对偶公式 显然 A也是A 的对偶式 求对偶式的方法 先化为仅含有 三种联结词的公式 按定义依次完全替换 69 第一章数理逻辑1 7对偶与范式 69 对偶 举例 例题 写出下列表达式的对偶式 P Q P Q S P Q R P Q 1P QP QP Q Q R P Q P Q 70 第一章数理逻辑1 7对偶与范式 70 对偶 德摩根律的普遍形式 定理1 7 1 设A和A 是对偶式 P1 P2 Pn是出现在A和A 中的原子变元 则 A P1 P2 Pn A P1 P2 Pn A P1 P2 Pn A P1 P2 Pn 3种关系 整个公式的否定式 对偶式 内否式 71 第一章数理逻辑1 7对偶与范式 71 德摩根律的普遍形式 验证 例题3设A S W R 是 S W R 验证A S W R A S W R 对偶式的重要应用 求公式的否定 思考 若A是重言式 A 72 第一章数理逻辑1 7对偶与范式 72 对偶定理 定理1 7 2设P1 P2 Pn是出现在公式A和B中的所有原子变元 如果A B 则A B 证明 因为A B 即A P1 P2 Pn B P1 P2 Pn 是一个重言式 故A P1 P2 Pn B P1 P2 Pn 也是一个重言式 即A P1 P2 Pn B P1 P2 Pn 由定理1 7 1得 A P1 P2 Pn B P1 P2 Pn 因此A B 再次观察教材p16 表1 22等价公式 73 相容概念 定义1 8 2假设公式H1 H2 Hm中的命题变元为P1 P2 Pn 对于P1 P2 Pn的一些真值指派 如果能使H1 H2 Hm的真值为T 则称公式H1 H2 Hm是相容的 如果对于P1 P2 Pn的每一组真值指派 H1 H2 Hm的真值均为F 则称公式H1 H2 Hm是不相容的 74 间接证法 反证法 要证H1 H2 Hm C 设H1 H2 Hm为S 即证S CS C为重言式 永真式 即证 C S永为真 即证C S为永真 C S C S 即证 C S为永假 因此要证明H1 H2 Hm C 只要证明H1 H2 Hm与 C是不相容的 例题3证明A B B C 可逻辑推出 A 75 作业 1 复习本章的内容 自学 范式 长假过后第一次单元考试 重点 真值表 等价公式 重言式 蕴含式 对偶 范式作为附加题 76 作业 2 为了顺序地促进云南省移动互联网协会的成立 请各位老师 通知一下你教的本科班学生 作为一个必教的课后作业 博士生 硕士生 每一个人提交一份作业 作业的内容是关于运行在手机上的一个应用的设想 这个手机平台上的应用 应该能够方便人们的生活 如交通路线查询 学校课程及上课教室查询等 不能是游戏 内容可以不要求很详细 A4一张纸就可以了 纸质和电子版各一份 77 第五讲范式 引子画出教材P23例1 4 5的真值表 并仔细研究其赋值情况 78 1 7析取范式与合取范式 基本概念 1 文字 命题变项及其否定的总称 2 简单析取式 析取项 有限个文字构成的析取式p q p q p q r 3 简单合取式 合取项 有限个文字构成的合取式p q p q p q r 4 析取范式 由有限个简单合取式组成的析取式p p q p q p q p q r q r 5 合取范式 由有限个简单析取式组成的合取式p p q p q p q p p q r 6 范式 NF 析取范式与合取范式的总称 79 范式概念 两类特殊情况说明 单个文字既是简单析取式 又是简单合取式形如p q r p q r的公式既是析取范式 又是合取范式 80 范式的性质 定理1 1 一个简单析取式是重言式当且仅当它同时含有某个命题变项和它的否定式 2 一个简单合取式是矛盾式当且仅当它同时含有某个命题变项和它的否定式 定理2 1 一个析取范式是矛盾式当且仅当它每个简单合取式都是矛盾式 2 一个合取范式是重言式当且仅当它的每个简单析取式都是重言式 81 命题公式的范式 定理3 范式存在定理 任何命题公式都存在与之等值的析取范式与合取范式 公式A的析取 合取 范式 与A等值的析取 合取 范式求公式A的范式的步骤 1 消去A中的 若存在 A B A BA B A B A B 2 否定联结词 的内移或消去 A A A B A B A B A B 82 命题公式的范式 3 使用分配律A B C A B A C 求合取范式A B C A B A C 求析取范式 83 求公式的范式 例求下列公式的析取范式与合取范式 1 p q r 2 p q r解 1 p q r p q r 消去 p q r 结合律 最后结果既是析取范式 由3个简单合取式组成的析取式 又是合取范式 由一个简单析取式组成的合取式 84 2 p q r p q r 消去第一个 p q r 消去第二个 p q r 否定号内移 德摩根律 析取范式 p r q r 对 分配律 合取范式例求公式的合取范式 p p q r 公式范式的不足 不惟一 不能直观反映真值表的情况解决方法 进一步规范化主范式 求公式的范式 85 极小项与极大项 定义在含有n个命题变项的简单合取式 简单析取式 中 若每个命题变项均以文字的形式在其中出现且仅出现一次 而且第i个文字出现在左起第i位上 1 i n 称这样的简单合取式 简单析取式 为极小项 极大项 几点说明 n个命题变项有2n个极小项和2n个极大项2n个极小项 极大项 均互不等值用mi表示第i个极小项 其中i是该极小项成真赋值的十进制表示 用Mi表示第i个极大项 其中i是该极大项成假赋值的十进制表示 mi Mi 称为极小项 极大项 的名称 86 观察 由两个命题变项p q形成的极小项与极大项 87 实例 由三个命题变项p q r形成的极小项与极大项 mi与Mi的关系 思考P29定理1 4 6 mi Mi Mi mi 88 主析取范式与主合取范式 主析取范式 由极小项构成的析取范式主合取范式 由极大项构成的合取范式例如 n 3 命题变项为p q r时 p q r p q r m1 m3 主析取范式 p q r p q r M1 M7 主合取范式公式A的主析取 合取 范式 与A等值的主析取 合取 范式定理 主范式的存在惟一定理 任何命题公式都存在与之等值的主析取范式和主合取范式 并且是惟一的 如果命题变元的顺序固定 89 求公式主范式的步骤 求公式主析取范式的步骤 设公式A含命题变项p1 p2 pn 1 求A的析取范式A B1 B2 Bs 其中Bj是简单合取式j 1 2 s 2 若某个Bj既不含pi 又不含 pi 则将Bj展开成Bj Bj pi pi Bj pi Bj pi 重复这个过程 直到所有简单合取式都是长度为n的极小项为止 3 消去重复出现的极小项 即用mi代替mi mi 4 将极小项按下标从小到大排列 90 求公式主范式的步骤 求公式的主合取范式的步骤 设公式A含命题变项p1 p2 pn 1 求A的合取范式A B1 B2 Bs 其中Bj是简单析取式j 1 2 s 2 若某个Bj既不含pi 又不含 pi 则将Bj展开成Bj Bj pi pi Bj pi Bj pi 重复这个过程 直到所有简单析取式都是长度为n的极大项为止 3 消去重复出现的极大项 即用Mi代替Mi Mi 4 将极大项按下标从小到大排列 91 实例 例6 1 求公式A p q r的主析取范式和主合取范式解 p q r p q r 析取范式 p q p q r r p q r p q r m6 m7 r p p q q r p q r p q r p q r p q r m1 m3 m5 m7 代入 并排序 得 p q r m1 m3 m5 m6 m7 主析取范式 92 实例 p q r p r q r 合取范式 p r p q q r p q r p q r M0 M2 q r p p q r p q r p q r M0 M4 代入 并排序 得 p q