第一章 命题逻辑-离散数学.pdf

离 散 数 学离 散 数 学 3 11 2009 4 25 PM 1 离散数学离散数学 Discrete MathematicsDiscrete Mathematics 中国民航大学计算机学院中国民航大学计算机学院 张敏张敏 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 2 先看著名物理学家爱因斯坦出过的一道题 先看著名物理学家爱因斯坦出过的一道题 一个土耳其商人想找一个十分聪明的助手协助他 经商 有两人前来应聘 这个商人为了试试哪个更聪 明些 就把两个人带进一间漆黑的屋子里 他打开灯 后说 一个土耳其商人想找一个十分聪明的助手协助他 经商 有两人前来应聘 这个商人为了试试哪个更聪 明些 就把两个人带进一间漆黑的屋子里 他打开灯 后说 这张桌子上有五顶帽子 两顶是红色的 三 顶是黑色的 现在 我把灯关掉 而且把帽子摆的位 置弄乱 然后我们三个人每人摸一顶帽子戴在自己头 上 在我开灯后 请你们尽快说出自己头上戴的帽子 是什么颜色的 这张桌子上有五顶帽子 两顶是红色的 三 顶是黑色的 现在 我把灯关掉 而且把帽子摆的位 置弄乱 然后我们三个人每人摸一顶帽子戴在自己头 上 在我开灯后 请你们尽快说出自己头上戴的帽子 是什么颜色的 说完后 商人将电灯关掉 然后三 人都摸了一顶帽子戴在头上 同时商人将余下的两顶 帽子藏了起来 接着把灯打开 这时 那两个应试者 看到商人头上戴的是一顶红帽子 其中一个人便喊 道 说完后 商人将电灯关掉 然后三 人都摸了一顶帽子戴在头上 同时商人将余下的两顶 帽子藏了起来 接着把灯打开 这时 那两个应试者 看到商人头上戴的是一顶红帽子 其中一个人便喊 道 我戴的是黑帽子 我戴的是黑帽子 请问这个人说得对吗 他是怎么推导出来的呢 请问这个人说得对吗 他是怎么推导出来的呢 第一篇第一篇第一篇第一篇数理逻辑数理逻辑数理逻辑数理逻辑 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 3 要回答这样的问题 实际上就是看由一些诸如要回答这样的问题 实际上就是看由一些诸如 商人戴的是红帽子商人戴的是红帽子 这样的前提能否推出这样的前提能否推出 猜出答 案的应试者戴的是黑帽子 猜出答 案的应试者戴的是黑帽子 这样的结论来 这又需 要经历如下过程 这样的结论来 这又需 要经历如下过程 1 什么是前提 有哪些前提 什么是前提 有哪些前提 2 结论是什么 结论是什么 3 根据什么进行推理 根据什么进行推理 4 怎么进行推理 怎么进行推理 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 4 数理逻辑是用数理逻辑是用数学的方法数学的方法研究推理的形式 结构规律的数学学科 所谓 研究推理的形式 结构规律的数学学科 所谓 数学方法数学方法 是建立一套有严格定 义的符号 其作用是为了避免用自然语言讨 论问题时所带来的歧义性 例如 是建立一套有严格定 义的符号 其作用是为了避免用自然语言讨 论问题时所带来的歧义性 例如 1 曹雪芹曹雪芹是是 红楼梦 的作者 红楼梦 的作者 2 曹雪芹曹雪芹是是小说家小说家 3 小说家小说家是是文学家文学家 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 5 第一章第一章第一章第一章 命题逻辑命题逻辑命题逻辑命题逻辑 命题逻辑研究对象 命题逻辑研究对象 命题命题 主要讨论 主要讨论 命题符号化及联结词命题符号化及联结词 命题公式及分类命题公式及分类 等值演算等值演算 对偶与范式对偶与范式 推理理论推理理论 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 6 1 1 1 1 1 1 1 1 命题符号化及联结词命题符号化及联结词命题符号化及联结词命题符号化及联结词 命题命题命题命题 有真假意义的陈述句 以句子为单位 有真假意义的陈述句 以句子为单位 例1 1 1 判定下面这些句子哪些是命题 例1 1 1 判定下面这些句子哪些是命题 2是个素数 2是个素数 雪是黑色的 雪是黑色的 2015年人类将到达火星 2015年人类将到达火星 如果 a b且b c 则a c 如果 a b且b c 则a c x y 5 x yb b c a c 构成的复合命题 构成的复合命题 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 11 联结词联结词联结词联结词 复合命题的构成 是用复合命题的构成 是用 联结词联结词 将原子 命题联结起来构成的 将原子 命题联结起来构成的 归纳自然语言中的联结词 定义了六个 逻 辑 联结词 分别是 归纳自然语言中的联结词 定义了六个 逻 辑 联结词 分别是 1 否定否定 2 合取合取 3 析取析取 4 异或异或 5 蕴涵蕴涵 6 等价等价 V 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 12 一一一一 否定否定否定否定 表示 表示 不成立不成立 不不 用于 对一个命题用于 对一个命题P的否定 写成 的否定 写成 P 并读成 并读成 非非P P的真值 与的真值 与P真值相反 真值相反 例例1 2 1 P 2是素数 是素数 P 2不是素数 不是素数 P P 01 10 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 13 二二二二 合取合取合取合取 表示 表示 并且并且 不但不但 而且而且 既既 又又 尽管尽管 还还 例例1 2 2 P 小王能唱歌 小王能唱歌 Q 小王能跳舞 小王能跳舞 P Q 小王能歌善舞 小王能歌善舞 P Q读成读成P合取合取Q P Q的真值为真 当且的真值为真 当且 仅当仅当P和和Q的真值均为真 的真值均为真 PQP Q 111 100 010 000 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 14 三三三三 析取析取析取析取 异或 异或 异或 异或 表示表示 或者或者 或者或者 有有二义性二义性 看下面两个例子 看下面两个例子 例例1 2 3 灯泡灯泡或者或者线路有故障 线路有故障 例例1 2 4 第一节课上数学第一节课上数学或者或者上英语 上英语 例例3中的中的或者或者是是可兼取的或可兼取的或 即 即析取析取 例例4中的中的或者或者是是不可兼取的或不可兼取的或 也称之为 也称之为 异或异或 排斥或排斥或 即 即 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 15 1 1 1 1 析取析取析取析取 P 灯泡有故障 灯泡有故障 Q 线路有故障 线路有故障 例例3中的复合命题可中的复合命题可 表示为 表示为 P Q 读 读 成成P析取析取Q P或者或者Q P Q的真值为的真值为0 当 当 且仅当且仅当P与与Q均为均为0 PQP Q 111 101 011 000 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 16 2 2 2 2 异或异或异或异或 PQP Q 110 101 011 000 P 第一节上数学 第一节上数学 Q 第一节上英语 第一节上英语 例例4中的复合命题 可写成 中的复合命题 可写成P Q 读 成 读 成P异或异或Q P Q的真值为的真值为0 当且仅当 当且仅当P与与Q的的真值相同真值相同 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 17 3 3 3 3 异或的另一种表示异或的另一种表示异或的另一种表示异或的另一种表示 异或是表示两个命题不可能同时都成立 异或是表示两个命题不可能同时都成立 命题命题 第一节课上数学或者上英语 第一节课上数学或者上英语 可以 解释为 可以 解释为 第一节课上数学而没有上英语或者第一 节课上英语而没有上数学 第一节课上数学而没有上英语或者第一 节课上英语而没有上数学 于是有于是有 P Q 与与 P Q Q P 是一样的 实际应用中必须注意 是一样的 实际应用中必须注意 或者或者 的二义性 的二义性 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 18 四四四四 蕴涵蕴涵蕴涵蕴涵 条件条件条件条件 表示表示 如果如果 则则 例例1 2 5 P表示 缺少水分 表示 缺少水分 Q表示 植物会死亡 表示 植物会死亡 P Q 如果缺少水分 植物就会死亡 如果缺少水分 植物就会死亡 P Q 也称之为蕴涵式 读成 也称之为蕴涵式 读成 P蕴涵蕴涵 Q 如果如果P则则 Q 也说成 也说成P是是P Q 的前 件 的前 件 Q是是P Q的后件 还可以说的后件 还可以说P是是Q的 充分条件 的 充分条件 Q是是P的必要条件 的必要条件 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 19 P P P P QQQQ的真值 的真值 的真值 的真值 P Q的真值为假 当且仅当的真值为假 当且仅当P为真 为真 Q为 假 注意 当前件 为 假 注意 当前件P为假时 为假时 P Q为为1 PQP Q 111 100 011 001 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 20 关于充分条件和必要条件的说明 关于充分条件和必要条件的说明 关于充分条件和必要条件的说明 关于充分条件和必要条件的说明 充分条件 就是只要条件成立 结论就成立 则该条件就是充分条件 充分条件 就是只要条件成立 结论就成立 则该条件就是充分条件 上例中 上例中 缺少水分缺少水分 就是就是 植物会死亡植物会死亡 的充分条件 在自然语言中表示充分条件的词 有 如果 的充分条件 在自然语言中表示充分条件的词 有 如果 则则 只要 只要 就就 若 若 则则 必要条件 就是如果该条件不成立 那么结论 就不成立 必要条件 就是如果该条件不成立 那么结论 就不成立 则该条件就是必要条件 则该条件就是必要条件 上例中 上例中 植物死亡植物死亡 就是就是 缺少水分缺少水分 的必要条 件 的必要条 件 植物未死亡 一定不缺少水分植物未死亡 一定不缺少水分 在自然语言中表示必要条件的词有 在自然语言中表示必要条件的词有 只有只有 才才 仅当 仅当 仅当仅当 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 21 举例 举例 举例 举例 令 令 P 天气好 天气好 Q 我去公园 我去公园 1 如果天气好 我就去公园 如果天气好 我就去公园 2 只要天气好 我就去公园 只要天气好 我就去公园 3 天气好 我就去公园 天气好 我就去公园 4 仅当天气好 我才去公园 仅当天气好 我才去公园 5 只有天气好 我才去公园 只有天气好 我才去公园 6 我去公园 仅当天气好 我去公园 仅当天气好 命题命题1 2 3 写成 写成 P Q 命题命题4 5 6 写成 写成 Q P 可见可见 既表示充分条件 即前件是后件的充分条件 既表示充分条件 即前件是后件的充分条件 也表示必要条件 即后件是前件的必要条件 这一点要也表示必要条件 即后件是前件的必要条件 这一点要 特别注意特别注意 它决定了哪个作为前件 哪个作为后件 它决定了哪个作为前件 哪个作为后件 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 22 五五五五 等价等价等价等价 双条件 双条件 双条件 双条件 表示表示 当且仅当当且仅当 充分且必要充分且必要 例例1 2 6 P ABC是等边三角形 是等边三角形 Q ABC是等角三角形 是等角三角形 P Q ABC是等边是等边 三角形当且仅当三角形当且仅当 它是等角三角形 它是等角三角形 P Q的真值为真 当且仅当的真值为真 当且仅当P与与Q的真值相 同 的真值相 同 PQ P Q 111 100 010 001 离 散 数 学离 散 数 学 命题符号化命题符号化命题符号化命题符号化 所谓命题符号化 就是用命题公式的符 号串来表示给定的命题 所谓命题符号化 就是用命题公式的符 号串来表示给定的命题 命题符号化的方法命题符号化的方法 1 首先要明确给定命题的含义 首先要明确给定命题的含义 2 对于复合命题 找联结词 用联结词 断句 分解出各个原子命题 对于复合命题 找联结词 用联结词 断句 分解出各个原子命题 3 设原子命题符号 并用逻辑联结词联 结原子命题符号 构成给定命题的符 号表达式 设原子命题符号 并用逻辑联结词联 结原子命题符号 构成给定命题的符 号表达式 3 11 2009 4 25 PM 23 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 24 例例1 试以符号形式写出命题 我们要做到身体好 学 习好 工作好 为祖国四化建设而奋斗 解 试以符号形式写出命题 我们要做到身体好 学 习好 工作好 为祖国四化建设而奋斗 解 A 我们要做到身体好 我们要做到身体好 B 我们要做到学习好 我们要做到学习好 C 我们要做到工作好 我们要做到工作好 P 我们要为祖国四化建设而奋斗 故命题可形式化为 我们要为祖国四化建设而奋斗 故命题可形式化为 A B C P 例例2 上海到北京的 上海到北京的14次列车是下午五点半或六点开 解 次列车是下午五点半或六点开 解 P 上海到北京的 上海到北京的14次列车是下午五点半开 次列车是下午五点半开 Q 上海到北京的 上海到北京的14次列车是下午六点开 故命题可形式化为 次列车是下午六点开 故命题可形式化为 P Q P Q 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 25 例例3 说离散数学无用且枯燥无味是不对的 说离散数学无用且枯燥无味是不对的 P 离散数学是有用的 离散数学是有用的 Q 离散数学是枯燥无味的 该命题可写成 离散数学是枯燥无味的 该命题可写成 P Q 例例4 如果小张与小王都不去 则小李去 如果小张与小王都不去 则小李去 P 小张去 小张去 Q 小王去 小王去 R 小李去 该命题可写成 小李去 该命题可写成 P Q R 如果小张与小王不都去 则小李去 该命题可写成 如果小张与小王不都去 则小李去 该命题可写成 P Q R 也可以写成 也可以写成 P Q R 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 26 例例5 仅当天不下雨且我有时间 才上街 仅当天不下雨且我有时间 才上街 P 天下雨 天下雨 Q 我有时间 我有时间 R 我上街 我上街 分析 由于分析 由于 仅当仅当 是表示是表示 必要条件必要条件 的 既的 既 天不下雨且我有时间天不下雨且我有时间 是 是 我上街我上街 的必要条件 所以的必要条件 所以 该命题可写成 该命题可写成 R P Q 例例6 人不犯我 我不犯人 人若犯我 我必 犯人 人不犯我 我不犯人 人若犯我 我必 犯人 P 人犯我 人犯我 Q 我犯人 我犯人 该命题可写成 该命题可写成 P Q P Q 或写成 或写成 P Q 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 27 例7 若天不下雨 我就上街 否则在家 例7 若天不下雨 我就上街 否则在家 P 天下雨 Q 我上街 R 我在家 P 天下雨 Q 我上街 R 我在家 该命题可写成 P Q P R 该命题可写成 P Q P R 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 28 本节小结 本节小结 本节小结 本节小结 会判断命题会判断命题 要熟练掌握这五个联结词在自然语言中所 表示 的含义以及它们的真值表的定义 要熟练掌握这五个联结词在自然语言中所 表示 的含义以及它们的真值表的定义 特别要注意特别要注意 或者或者 的二义性 即要区分给定的的二义性 即要区分给定的 或或 是是 可兼取的或可兼取的或 还是还是 不可兼取的或不可兼取的或 特别要注意特别要注意 的用法 它既表示 充分条 件 也表示 必要条件 即要弄清哪个作为 前件 哪个作为后件 的用法 它既表示 充分条 件 也表示 必要条件 即要弄清哪个作为 前件 哪个作为后件 会自然语言命题符号化会自然语言命题符号化 作业 P38 2作业 P38 2 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 29 练习 填空练习 填空练习 填空练习 填空 已知已知P Q为为1 则 则P为为 Q为为 已知已知P Q为为0 则 则P为为 Q为为 已知已知P为为0 则 则P Q为为 已知已知P为为1 则 则P Q为为 已知已知P Q为为1 且 且P为为0 则 则Q为为 已知已知P Q为为0 则 则P为为 Q为为 已知已知P为为0 则 则P Q为为 已知已知Q为为1 则 则P Q为为 已知 已知 P Q为为0 则 则P为为 Q为为 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 30 已知已知P为为1 P Q为为1 则 则Q为为 已知 已知 Q为为1 P Q为为1 则 则P为为 已知已知P Q为为1 P为为1 则则Q为为 已知已知P Q为为0 P为为1 则则Q为为 P P 的真值为的真值为 P P 的真值为的真值为 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 31 2 令令 p 北京比天津人口多 北京比天津人口多 q 2 2 4 r 乌鸦是白色的 乌鸦是白色的 求下列命题的真值 求下列命题的真值 1 p q p q r 2 q r p r 3 p r p r 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 32 3 判断下列陈述是否是命题 如果是命题 是否是复合命题 判断下列陈述是否是命题 如果是命题 是否是复合命题 1 是无理数 是无理数 2 7能被能被2整除整除 3 什么时候开会呀 什么时候开会呀 4 2x 310 5 苹果树和梨树都是落叶乔木 苹果树和梨树都是落叶乔木 6 2是质数或合数 是质数或合数 7 豆沙包是由面粉和红小豆做成的 豆沙包是由面粉和红小豆做成的 8 吃一堑 长一智 吃一堑 长一智 9 n是偶数当且仅当它能被是偶数当且仅当它能被3整除 整除 n为一 固定的自然数 为一 固定的自然数 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 34 一一一一 命题常元与命题变元命题常元与命题变元命题常元与命题变元命题常元与命题变元 命题常元 命题常元 命题常元 命题常元 即是我们前面所说的命题 它是有即是我们前面所说的命题 它是有即是我们前面所说的命题 它是有即是我们前面所说的命题 它是有 具体含义具体含义具体含义具体含义 真值真值真值真值 的 例如 的 例如 的 例如 的 例如 3 3是素数 是素数 是素数 是素数 命题变元 命题变元 命题变元 命题变元 用英字母如用英字母如用英字母如用英字母如P P QQ等表示任何命题 等表示任何命题 等表示任何命题 等表示任何命题 称这些字母为命题变元 称这些字母为命题变元 称这些字母为命题变元 称这些字母为命题变元 提问 提问 提问 提问 命题变元是否是命题 如何变成命题 命题变元是否是命题 如何变成命题 命题变元是否是命题 如何变成命题 命题变元是否是命题 如何变成命题 解释 解释 解释 解释 指定命题变元代表某个具体的命题 指定命题变元代表某个具体的命题 指定命题变元代表某个具体的命题 指定命题变元代表某个具体的命题 赋值赋值赋值赋值 真值指派真值指派真值指派真值指派 对命题变元指派确定的真对命题变元指派确定的真对命题变元指派确定的真对命题变元指派确定的真 值 值 值 值 命题公式 命题公式 命题公式 命题公式 由命题变元 常元 符 联结词和由命题变元 常元 符 联结词和由命题变元 常元 符 联结词和由命题变元 常元 符 联结词和 1 2 1 2 1 2 1 2 命题公式及分类命题公式及分类命题公式及分类命题公式及分类 圆括号按圆括号按一一定逻辑关系联结起来的字符串定逻辑关系联结起来的字符串圆括号按圆括号按一一定逻辑关系联结起来的字符串定逻辑关系联结起来的字符串 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 35 二二二二 合式公式合式公式合式公式合式公式 wff well formed formulas wff well formed formulas 1 定义 定义 单个命题变元本身是个合式公式 单个命题变元本身是个合式公式 如果 如果A是合式公式 那么 是合式公式 那么 A是合式公式 是合式公式 如果 如果A和和B是合式公式 则是合式公式 则 A B A B A B 和和 A B 都是合式公式 都是合式公式 当且仅当能够有限次地应用 所得 到的含有 当且仅当能够有限次地应用 所得 到的含有命题变元命题变元 联结词联结词和和括号括号的的符号串符号串是合式 公式 是合式 公式 注意这个定义是递归的 注意这个定义是递归的 1 是递归的基础 由是递归的基础 由 1 开始 使用开始 使用 2 3 规则 可以得到任意的合式公式 规则 可以得到任意的合式公式 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 36 请判断下面的式子哪些是合式公式 请判断下面的式子哪些是合式公式 P Q Q P R P Q R P Q P R P Q R 按照合式公式定义最外层括号必须写 按照合式公式定义最外层括号必须写 约定 为方便 最外层圆括号可以省略 上面的合式公式可以写成 为方便 最外层圆括号可以省略 上面的合式公式可以写成 P Q P R P Q R 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 37 三 真值表三 真值表三 真值表三 真值表 一个命题公式不是复合命题 所以它没 有真值 但是给其中的所有命题变元作指派 以后它就有了真值 可以以表的形式反应它 的真值情况 一个命题公式不是复合命题 所以它没 有真值 但是给其中的所有命题变元作指派 以后它就有了真值 可以以表的形式反应它 的真值情况 真值表的构造真值表的构造 例例1 构造 构造 P Q的真值表 的真值表 例例2 构造 构造 P Q P Q 的真值 表 的真值 表 例例3 构造 构造 P P Q Q的真值表 的真值表 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 38 由于对每个命题变元可以有两个真值由于对每个命题变元可以有两个真值 1 0 被指派 所以有被指派 所以有n个命题变元的命题公式个命题变元的命题公式 A P1 P2 Pn 的真值表有的真值表有2n行 行 为了有序地列出公式的真值表 在对命题 变元做指派时 可以按照二进制数的次序 列表 为了有序地列出公式的真值表 在对命题 变元做指派时 可以按照二进制数的次序 列表 P Q和和P Q及 及 Q P真值相同 真值相同 P Q P Q 与与P Q真值相同 真值相同 离 散 数 学离 散 数 学 四 命题公式的分类四 命题公式的分类四 命题公式的分类四 命题公式的分类 永真式永真式 重言式重言式 所有赋值均为成真的赋值的公式 所有赋值均为成真的赋值的公式 永假式永假式 矛盾式矛盾式 所有赋值均为成真的赋值的公式 所有赋值均为成真的赋值的公式 可满足式 可满足式 至少有一组赋值是成真赋值的公式 至少有一组赋值是成真赋值的公式 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 40 本节小结本节小结本节小结本节小结 1 掌握合式公式公式的定义 即会判 断哪些公式是合式公式 掌握合式公式公式的定义 即会判 断哪些公式是合式公式 2 会构造命题公式的真值表 会构造命题公式的真值表 作业 作业 P38 3 4 P38 4 4 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 41 1 3 1 3 1 3 1 3 等值演算等值演算等值演算等值演算 看下面三个公式的真值表看下面三个公式的真值表 P Q P Q P Q Q P 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 从真值表可以看出 不论对从真值表可以看出 不论对P Q作何指 派 都使得 作何指 派 都使得P Q P Q和 和 Q P的真 值相同 表明它们之间彼此等价 的真 值相同 表明它们之间彼此等价 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 42 1 定义 定义 A B是含有命题变元是含有命题变元P1 P2 Pn的命题 公式 如不论对 的命题 公式 如不论对P1 P2 Pn作任何指派 都使得作任何指派 都使得 A和和B的真值相同 则称之为的真值相同 则称之为A与与B等价 记作等价 记作 A B 显然显然P Q P Q Q P 2 重要的等价公式重要的等价公式 对合律 对合律 P P 幂等律 幂等律 P P P P P P 结合律 结合律 P Q R P Q R P Q R P Q R 交换律 交换律P Q Q P P Q Q P 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 43 分配律 分配律P Q R P Q P R P Q R P Q P R 吸收律 吸收律 P P Q P P P Q P 德 德 摩根定律 摩根定律 P Q P Q P Q P Q 同一律 同一律P 0 P P 1 P 零律 零律P 1 1 P 0 0 互补律 互补律P P 1P P 0 蕴含等值式 蕴含等值式 P Q P Q 假言易位 假言易位 P Q Q P 等价等值式 等价等值式P Q P Q Q P P Q P Q P Q P Q P Q P Q 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 44 为便于记忆 将等价公式为便于记忆 将等价公式 前前10个个 与集合论的公式比 较 请看集合公式 与集合论的公式比 较 请看集合公式 对合律 对合律 A A A表示表示A的绝对补集的绝对补集 幂等律 幂等律 A A A A A A 结合律 结合律 A B C A B C A B C A B C 交换律 交换律A B B A A B B A 分配律 分配律 A B C A B A C A B C A B A C 吸收律 吸收律 A A B A A A B A 德 德 摩根定律摩根定律 A B A B A B A B 同一律 同一律A A A E A E表示全集表示全集 零律 零律A E E A 否定律 否定律A A EA A 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 45 3 3 3 3 等价公式的证明方法等价公式的证明方法等价公式的证明方法等价公式的证明方法 方法方法1 列真值表 不再举例 列真值表 不再举例 方法方法2 公式的等价变换 公式的等价变换 用置换定律用置换定律 置换定律置换定律 A是一个命题公式 是一个命题公式 X是是A中 的 一部分且也是合式公式 如果 中 的 一部分且也是合式公式 如果X Y 用 用Y 代替代替A中的中的X得到公式得到公式B 则 则A B 应用置换定律以及前面列出的等价公式可 以对给定公式进行等价变换 应用置换定律以及前面列出的等价公式可 以对给定公式进行等价变换 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 46 例题例题例题例题1 1 1 1 求证吸收律求证吸收律求证吸收律求证吸收律 P P P P P P P P Q Q Q Q P P P P 证明 证明 P P Q P 0 P Q 同一律同一律 P 0 Q 分配律分配律 P 0 零律零律 P 同一律同一律 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 47 例题例题例题例题2 2 2 2 化简公式化简公式化简公式化简公式 P P P P Q Q Q Q P P P P Q Q Q Q 并 并 并 并 判断公式的类型 判断公式的类型 判断公式的类型 判断公式的类型 证明证明 P Q P Q P Q P Q 公式公式E16 P Q P Q 摩根定律摩根定律 P Q P Q 对合律对合律 P Q Q 分配律分配律 P 1 互补律互补律 P 同一律同一律 公式公式E16 P Q P Q 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 48 例题例题例题例题3 3 3 3 化简化简化简化简 P P P P Q Q Q Q P P P P P P P P Q Q Q Q 解解 原公式原公式 P Q P P Q E16 结合结合 P Q P Q 对合律 幂等律对合律 幂等律 P Q Q P 交换律交换律 P Q Q P 结合律结合律 Q P 吸收律吸收律 公式公式E16 P Q P Q 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 49 4 4 4 4 性质性质性质性质 1 有自反性 任何命题公式有自反性 任何命题公式A 有 有A A 2 有对称性 若有对称性 若A B 则 则B A 3 有传递性 若有传递性 若A B且且B C 则 则A C 4 如果如果A P1 P2 Pn B P1 P2 Pn 则 则 A P1 P2 Pn B P1 P2 Pn 例例 A P Q P Q B P Q P Q 有有 A P Q B P Q A P Q P Q B P Q P Q 可见可见A P Q B P Q 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 50 本节小结本节小结本节小结本节小结 1 掌握书掌握书P12页下面的所有等价公式 页下面的所有等价公式 2 掌握等价公式的证明方法 掌握等价公式的证明方法 3 掌握等价公式的性质 掌握等价公式的性质 作业 作业 P38 5 1 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 51 1 将下列命题符号化 并给出各命题的真值 将下列命题符号化 并给出各命题的真值 1 若 若3 2 4 则地球是静止不动的 则地球是静止不动的 2 若 若3 2 4 则地球是运动不止的 则地球是运动不止的 3 若地球上没有树木 则人类不能生存 若地球上没有树木 则人类不能生存 4 若地球上没有水 则 是无理数 若地球上没有水 则 是无理数 练习练习练习练习 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 52 2 设 设 p 2 3 5 q 大熊猫产在中国 大熊猫产在中国 r 复旦大学在广州 求下列复合命题的真值 复旦大学在广州 求下列复合命题的真值 1 p q r 2 r p q p 3 r p q r 4 p q r p q r 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 53 1 4 1 4 1 4 1 4 其他联结词 略 其他联结词 略 其他联结词 略 其他联结词 略 1 1 1 1 完备集完备集完备集完备集 设设设设Q Q Q Q是逻辑运算符号集合 是逻辑运算符号集合 是逻辑运算符号集合 是逻辑运算符号集合 若所有逻辑运算都能由若所有逻辑运算都能由若所有逻辑运算都能由若所有逻辑运算都能由Q Q Q Q中元素表示中元素表示中元素表示中元素表示 出来 而出来 而出来 而出来 而Q Q Q Q的任意真子集无此性质 的任意真子集无此性质 的任意真子集无此性质 的任意真子集无此性质 则称则称则称则称Q Q Q Q是一个完备集 是一个完备集 是一个完备集 是一个完备集 都是完备集 都是完备集 都是完备集 都是完备集 2 2 2 2 如果如果如果如果 则则则则 的否定的否定的否定的否定 联结词联结词联结词联结词 3 3 3 3 与非与非与非与非 联结词联结词联结词联结词 4 4 4 4 或非或非或非或非 联结词联结词联结词联结词 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 54 从前面列出的等价公式看出 有很多是成对出现 的 这就是等价公式的对偶性 从前面列出的等价公式看出 有很多是成对出现 的 这就是等价公式的对偶性 1 对偶式 在一个只含有联结词 的公式 对偶式 在一个只含有联结词 的公式A中 将 换成 换成 中 将 换成 换成 1换 成 换 成0 0换成换成1 其余部分不变 得到另一个公 式 其余部分不变 得到另一个公 式A 称 称A与与A 互为对偶式 例如 互为对偶式 例如 A A P P Q R Q R P 1 Q P 0 Q 一 等价公式的对偶性一 等价公式的对偶性一 等价公式的对偶性一 等价公式的对偶性 1 5 1 5 1 5 1 5 对偶与范式对偶与范式对偶与范式对偶与范式 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 55 2 2 2 2 用对偶式求公式的否定 用对偶式求公式的否定 用对偶式求公式的否定 用对偶式求公式的否定 定理定理1 7 1 令令A P1 P2 Pn 是一个只含有联 结词 的命题公式 则 是一个只含有联 结词 的命题公式 则 A P1 P2 Pn A P1 P2 Pn 此定理可以反复地使用德此定理可以反复地使用德 摩根定律得以证 明 下面我们验证一下 摩根定律得以证 明 下面我们验证一下 令令 A P Q P Q A P Q P Q A P Q P Q A P Q P Q 可见 可见 A P Q A P Q 推论推论 A P1 P2 Pn A P1 P2 Pn 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 56 例如 利用上述求公式的否定公式求例如 利用上述求公式的否定公式求 P Q P Q R P Q P Q R 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 57 3 3 3 3 对偶原理 对偶原理 对偶原理 对偶原理 定理定理定理定理1 1 1 1 7 2 7 2 7 2 7 2 令令A P1 P2 Pn B P1 P2 Pn 是只含有联 结词 的命题公式 则如果 是只含有联 结词 的命题公式 则如果 A P1 P2 Pn B P1 P2 Pn 则则 A P1 P2 Pn B P1 P2 Pn 证明 因为证明 因为 A P1 P2 Pn B P1 P2 Pn 故故 A P1 P2 Pn B P1 P2 Pn 而而 A P1 P2 Pn A P1 P2 Pn B P1 P2 Pn B P1 P2 Pn 故 故 A P1 P2 Pn B P1 P2 Pn 所以所以A P1 P2 Pn B P1 P2 Pn 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 58 下面我们验证一下对偶原理 下面我们验证一下对偶原理 下面我们验证一下对偶原理 下面我们验证一下对偶原理 P Q R P Q P R A B P Q R P Q P R A B P 1 1 A B P 0 0 A B 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 59 二 范二 范二 范二 范 式式式式 范式就是命题公式的规范形式 这里约定在范 式中只含有联结词 和 范式就是命题公式的规范形式 这里约定在范 式中只含有联结词 和 一 析取范式与合取范式 一 析取范式与合取范式 1 合取式与析取式合取式与析取式 合取式 是用合取式 是用 联结命题变元或变元的否定 构成的式子 联结命题变元或变元的否定 构成的式子 如如 P P P Q P Q R 析取式 是用析取式 是用 联结命题变元或变元的否 定构成的式子 联结命题变元或变元的否 定构成的式子 如如 P P P Q P Q R 注注 P P P P P P P是合是合 析析 取式取式 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 60 2 析取范式析取范式 公式公式A如果写成如下形式 如果写成如下形式 A1 A2 An n 1 其中每个其中每个Ai i 1 2 n 是合取式 称之为是合取式 称之为A的析取范式 的析取范式 3 合取范式合取范式 公式公式A如果写成如下形式 如果写成如下形式 A1 A2 An n 1 其中每个其中每个Ai i 1 2 n 是析取式 称之为是析取式 称之为A的合取范式 的合取范式 例如 例如 P Q 的析取范式与合取范式 的析取范式与合取范式 P Q P Q P Q 析取范式析取范式 P Q P Q P Q 合取范式合取范式 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 61 4 4 析取范式与合取范式的写法析取范式与合取范式的写法 先用相应的公式去掉 和 先用相应的公式去掉 和 公式公式E16 P Q P Q 公式公式E21 P Q P Q P Q 公式公式E20 P Q P Q Q P 再用再用E16 P Q P Q P Q 用公式的否定公式或摩根定律将 后移到命题 变元之前 用公式的否定公式或摩根定律将 后移到命题 变元之前 A P1 P2 Pn A P1 P2 Pn 德德 摩根定律 摩根定律 P Q P Q P Q P Q 用分配律 幂等律等公式进行整理 使之成 为所要求的形式 用分配律 幂等律等公式进行整理 使之成 为所要求的形式 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 62 例如求例如求例如求例如求 P P P P Q Q Q Q R RR R的的的的析取范式与合取范式析取范式与合取范式析取范式与合取范式析取范式与合取范式 P Q R P Q P Q R P Q P Q R 析取范式析取范式 P Q R P Q P Q R P Q P Q R P Q R P Q R 合取范式合取范式 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 63 一个公式的析取范式与合取范式的形式是 不唯一的 下面定义形式唯一的主析取范式 与主合取范式 一个公式的析取范式与合取范式的形式是 不唯一的 下面定义形式唯一的主析取范式 与主合取范式 1 主析取范式 主析取范式 1 小项 定义 在一个有 小项 定义 在一个有n个命题变元的合取 式中 每个变元必出现且仅出现一次 称这 个合取式是个小项 例如 有两个变元的小项 个命题变元的合取 式中 每个变元必出现且仅出现一次 称这 个合取式是个小项 例如 有两个变元的小项 P Q P Q P Q P Q 二 主析取范式与主 二 主析取范式与主 二 主析取范式与主 二 主析取范式与主合取范式合取范式合取范式合取范式 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 64 小项的性质小项的性质小项的性质小项的性质 m3 m2 m1 m0 P Q P Q P Q P Q P Q 00 0 0 0 0 0 1 01 0 1 0 0 10 10 1 0 0 10 0 11 1 1 10 0 0 a 有有n个变元 则有个变元 则有2n个小项 个小项 b 每一组指派有且只有一个小项为每一组指派有且只有一个小项为1 为了记忆方便 可将各组指派对应的为 为了记忆方便 可将各组指派对应的为1的小项 分别记作 的小项 分别记作m0 m1 m2 m2n 1 上例中上例中 m0 P Qm1 P Q m2 P Qm3 P Q 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 65 2 主析取范式定义 析取范式 主析取范式定义 析取范式 A1 A2 An 其中每个其中每个Ai i 1 2 n 都是小项 称之为主析取范式 都是小项 称之为主析取范式 3 主析取范式的写法 方法 列真值表 列出给定公式的真值表 找出真值表中每个 主析取范式的写法 方法 列真值表 列出给定公式的真值表 找出真值表中每个 1 对应的小项 对应的小项 如何根据一组指派写对应的为如何根据一组指派写对应的为 1 的项 如果变 元 的项 如果变 元P被指派为被指派为1 P在小项中以在小项中以P形式出现 如变 元 形式出现 如变 元P被指派为被指派为0 P在小项中以 在小项中以 P形式出现形式出现 因要保 证该小项为 因要保 证该小项为1 用 用 联结上述小项 即可 联结上述小项 即可 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 66 例如求例如求 P Q和和P Q的主析取范式的主析取范式 P Q P Q P Q 0 0 1 1 0 1 1 0 1 0 0 0 1 1 1 1 P Q m0 m1 m3 P Q P Q P Q P Q m0 m3 P Q P Q 思考题思考题 永真式的主析取范式是什么样 永真式的主析取范式是什么样 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 67 方法方法方法方法 用公式的等价变换 用公式的等价变换 用公式的等价变换 用公式的等价变换 先写出给定公式的析取范式 先写出给定公式的析取范式 A1 A2 An 为使每个 为使每个Ai都变成小项 对缺少变元的都变成小项 对缺少变元的Ai 补全变元 比如缺变元补全变元 比如缺变元R 就用 联结永真 式 就用 联结永真 式 R R 形式补形式补R 用分配律等公式加以整理 用分配律等公式加以整理 例 例 P Q P Q P Q Q P P Q P Q P Q P Q P Q P Q P Q P Q 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 68 2 2 2 2 主 主 主 主合取范式合取范式合取范式合取范式 1 1 大项 大项 大项 大项 定义 定义 在有在有n个命题变元的析取式中 每个变 元必出现且仅出现一次 个命题变元的析取式中 每个变 元必出现且仅出现一次 称之为大项 例如 有两个变元的大项及其真值表 称之为大项 例如 有两个变元的大项及其真值表 M0 M1 M2 M3 P Q P Q P Q P Q P Q 0 0 01 1 1 0 1 1 01 1 1 0 1 1 01 1 1 1 1 1 0 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 69 大项的性质大项的性质大项的性质大项的性质 a 有有n个变元 则有个变元 则有2n个大项 个大项 b 每一组指派有且只有一个大项为每一组指派有且只有一个大项为0 为了记忆方便 可将各组指派对应的为为了记忆方便 可将各组指派对应的为0 的大项分别记作的大项分别记作M0 M1 M2 M2n 1 上例中上例中 M0 P QM1 P Q M2 P Q M3 P Q 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 70 2 2 2 2 主合取范式定义主合取范式定义主合取范式定义主合取范式定义 合取范式合取范式 A1 A2 An 其中每个其中每个Ai i 1 2 n 都是大项 称之为主合取范式 都是大项 称之为主合取范式 3 主合取范式的写法 主合取范式的写法 方法 列真值表方法 列真值表 列出给定公式的真值表 列出给定公式的真值表 找出真值表中每个 找出真值表中每个 0 对应的大项 对应的大项 如何根据一组指派写对应的为如何根据一组指派写对应的为 0 的大项 的大项 如果变元如果变元P被指派为被指派为0 P在大项中以在大项中以P形式出现 形式出现 如变元如变元P被指派为被指派为1 P在大项中以在大项中以 P形式出现形式出现 确保该大项为确保该大项为0 用 用 联结上述大项 即可 联结上述大项 即可 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 71 例如求例如求例如求例如求 P P P P QQQQ和和和和P P P P QQQQ的的的的主合取范式主合取范式主合取范式主合取范式 P Q P Q P Q 0 0 1 1 0 1 1 0 1 0 0 0 1 1 1 1 P Q M2 P Q P Q M1 M2 P Q P Q 离 散 数 学离 散 数 学 3 11 2009 4 25 PM 72 课堂练习 课堂练习 课堂练习 课