命题逻辑及命题演算.ppt

第一章命题逻辑 一 绪言1 离散数学课程简介 研究离散结构的数学分科 辞海 79年版 P355 概述和计算机科学联系 和计算机科学联系紧密是计算机科学的支撑学科之一 也是信息科学的数学基础 在计算机理论研究及软硬件开发的各个领域都有广泛的应用 在计算机科学发展的过程中 各种理论问题的研究交错地使用着近代数学中的不同论题 这些论题构成了离散数学 学习离散数学的重要性 一个土耳其商人想找一个十分聪明的助手协助他经商 有两人前来应聘 这个商人为了试试哪个更聪明些 就把两个人带进一间漆黑的屋子里 他打开灯后说 这张桌子上有五顶帽子 两顶是红色的 三顶是黑色的 现在 我把灯关掉 而且把帽子摆的位置弄乱 然后我们三个人每人摸一顶帽子戴在自己头上 在我开灯后 请你们尽快说出自己头上戴的帽子是什么颜色的 说完后 商人将电灯关掉 然后三人都摸了一顶帽子戴在头上 同时商人将余下的两顶帽子藏了起来 接着把灯打开 这时 那两个应试者看到商人头上戴的是一顶红帽子 其中一个人便喊道 我戴的是黑帽子 请问这个人说得对吗 他是怎么推导出来的呢 要回答这样的问题 实际上就是看由一些诸如 商人戴的是红帽子 这样的前提能否推出 猜出答案的应试者戴的是黑帽子 这样的结论来 这又需要经历如下过程 1 什么是前提 有哪些前提 2 结论是什么 3 根据什么进行推理 4 怎么进行推理 二 命题与联结词 1引例 4是素数 是无理数 大于 大于吗 请不要吸烟 定义 命题 具有唯一真值的陈述句 例我正在说假话 2009年的元旦是晴天 表示方法 命题 真 1 假 0 否则 某命题是由简单命题通过联结词连接在一起的命题 称之为复合命题 非 且 或 如果则 当且仅当 见假为真 见真为假 p读作 并非p 或 非p 2 合取式 conjunction 两个命题P和Q的合取是一个复合命题 记作P Q 当且仅当P Q同时为T时 P Q为T 其他情况下 P Q的真值都是F 合取联结词 表示自然语言中的 并且 p q读作 p并且q 或 p且q 见假为假 全真为真 3 析取式 两个命题P和Q的析取是一个复合命题 记作P Q 当且仅当P Q同时为F时 P Q为F 其他情况下 P Q的真值都是T 析取联结词 表示自然语言中的 或 or 见真为真 全假为假 p q读作 p或者q p或q 4 蕴涵式 给定两个命题P和Q 其条件命题是一个复合命题 记作P Q 当且仅当P的真值为T Q的真值为F时 P Q的真值为F 其他情况下 P Q的真值都是T 条件联结词 表示自然语言中的 如果 那么 p q中的p称为条件前件 q称为条件后件 前真后假为假 其他为真 5 等价式 给定两个命题P和Q 其复合命题P Q称作双条件命题 当P和Q的真值相同时 P Q的真值为T 否则 P Q的真值都是F 双条件联结词 表示自然语言中的 当且仅当 p q读作 p与q互为条件 p当且仅当q 相同为真 相异为假 1 1 2复合命题的符号化 复合命题的符号化的基本步骤1 找出各个原子命题 并逐个符号化 2 找出各个连接词 符号成相应联结词 3 用联结词将原子命题逐个联结起来 1 1 2复合命题的符号化 例将下列命题符号化 1 北京不是村庄P 表示 北京是村庄 P 北京不是村庄 2 小王是游泳冠军和百米赛跑冠军P 小王是游泳冠军 Q 小王百米赛跑冠军P Q 小王是游泳冠军和百米赛跑冠军 1 1 2复合命题的符号化 例将下列命题符号化 3 小明或者小华能解够出这道题P 小明能够解出这道题 Q 小华能够解出这道题P Q 4 小王或者小李中的一个能够当上班长P 小王能够当上班长 Q 小李能够当上班长 1 1 2复合命题的符号化 例将下列命题符号化 5 今夜你若敢去公墓 那么我就咬掉我的鼻子或咬掉我的耳朵P 今夜你敢去公墓 Q 咬掉我的鼻子 R 咬掉我的耳朵 P Q R 1 1 2复合命题的符号化 例将下列命题符号化 6 王乐是计算机系的学生 生于1980年或1981年 是三好学生 P 王乐是计算机系的学生 Q 生于1980年 R 生于1981年 S 是三好学生 P Q R S 四 命题公式及其赋值 2 命题变项 命题变元 3 合式公式 命题公式 将命题变元用联结词或圆括号按一定的逻辑关系联结起来的符号串称为合式公式或命题公式 A B 定义 1 单个命题变项可被称为合式公式 2 若是合式公式 则也是合式公式 3 若是合式公式 则也是合式公式 4 将1 3有限次的联结起来也是合式公式 定义 设是出现在公式中的全部的命题变项 给各指定一个真值 称为对的一个赋值或解释 若指定的一组值使的真值为1 则称这组值为的成真赋值 若使的真值为0 则称这组值为的成假赋值 例 利用真值表求的成真赋值和成假赋值 练习 1 2 3 2 若在它的各种赋值下取值为假 则称为矛盾式或永假式 定义 设为任一命题公式 1 若在它的各种赋值下取值为真 则称为重言式或永真式 3 若不是矛盾式 则称为可满足式 第二章命题逻辑等值演算 一 等值式 引例 与 定义 设是两个命题公式 若构成的等价式为重言式 则称是等值的 记作 练习 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零律 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注意 A B C代表任意的命题公式 等值演算的用途一 证明等值式 例1 10验证p q r p q r右 p q r蕴涵等值式 p q r德摩根律 p q r 结合律 p q r 蕴涵等值式 p q r 蕴涵等值式注 A B A B 练习 例证明 p q r p q r用等值演算不能直接证明两个公式不等值 证明两个公式不等值的基本思想是找到一个赋值使一个成真 另一个成假 方法一真值表法 自己证 方法二观察赋值法 容易看出000 010等是左边的成真赋值 是右边的成假赋值 方法三用等值演算先化简两个公式 再观察 例用等值演算法判断下列公式的类型 1 q p q 解q p q q p q 蕴涵等值式 q p q 德摩根律 p q q 交换律 结合律 p 0 矛盾律 0 零律 由最后一步可知 该式为矛盾式 2 p q q p 解 p q q p p q q p 蕴涵等值式 p q p q 交换律 1由最后一步可知 该式为重言式 3 p q p q r 解 p q p q r p q q r 分配律 p 1 r 排中律 p r 同一律 这不是矛盾式 也不是重言式 而是非重言式的可满足式 如101是它的成真赋值 000是它的成假赋值 总结 A为矛盾式当且仅当A 0A为重言式当且仅当A 1说明 演算步骤不惟一 应尽量使演算短些 定义文字 命题变项及其否定统称为文字 如 p q简单析取式 仅有有限个文字组成的析取式 如 p q p q p q r简单合取式 仅有有限个文字组成的合取式 如 p q p q p q r 二 析取范式与合取范式 命题公式是千变万化的 这给研究命题演算带来困难 这里我们研究如何由一个命题公式化归为一个标准形式的问题 这样命题演算的研究问题就归结为对标准形式的研究问题 这种标准形式就叫范式 析取范式它是这样一种标准形式 在此式内不出现联结词 及 否定符号只出现在命题变元前 它是一个析取式 式中的每个析取项是个合取式 每个合取式中只包含命题变元或命题变元的否定 例如 p p q q r 此式即具有析取范式之形式注意 一个公式的析取范式并不唯一 如p r q 可以写成 p p r q 合取范式它是这样一种标准形式 在此式内不出现联结词 及 否定符号只出现在命题变元前 它是一个合取式 式中的每个合取项是个析取式 每个析取式中只包含命题变元或命题变元的否定 例如 p p q q r 此式即具有合取范式之形式注意 一个公式的合取范式并不唯一 如p r q 可以写成 p p r q 定义 析取范式 由有限个简单合取式构成的析取式 如 p q p q p q r 合取范式 由有限个简单析取式构成的合取式 如 p q p q p q r 范式 析取范式与合取范式统称为范式 设Ai i 1 2 3 n 为简单合取式 则A A1 A2 An就是析取范式 而B A1 A2 An就是合取范式 析取范式和合取范式有下列性质 1 一个析取范式是矛盾式 它的每个简单合取式都是矛盾式 2 一个合取范式是重言式 它的每个简单析取式都是重言式 例求下列公式的析取范式与合取范式 1 A p q r解 p q r p q r 消去 p q r 结合律 这既是A的析取范式 由3个简单合取式组成的析取式 又是A的合取范式 由一个简单析取式组成的合取式 2 B p q r解 p q r p q r 消去第一个 p q r 消去第二个 p q r 否定号内移 德摩根律 这一步已为析取范式 两个简单合取式构成 继续 p q r p r q r 对 分配律 这一步得到合取范式 由两个简单析取式构成 求范式的具体步骤 1 消去对 来说冗余的联结词 即 利用下列等值式 A B A B A B A B A B 2 否定词的消去或内移 利用下列等值式 A B A B A B A B A B A B 3 利用分配律 C A B C A C B C A B C A C B 3 求 p q p r 的析取范式 解 p q p r p q p r p q p p q r p p q p p r q r q p p r q r 4 求 p q p r 的析取 合取范式 解 1 求析取范式 p q p r p q p r p q p r 4 求 p q p r 的析取 合取范式 解 2 求合取取范式 p q p r p q p r p r p q p r p q p p p r q p p q p r q 合取范式 定义在含有n个命题变项的简单合取式 简单析取式 中 若每个命题变项均以文字的形式在其中出现且仅出现一次 而且第i 1 i n 个文字出现在左起第i位上 称这样的简单合取式 简单析取式 为极小项 极大项 由p q两个命题变项形成的极小项与极大项 由p q r三个命题变项形成的极小项与极大项 极小项与极大项关系设mi和Mi是命题变项p1 p2 pn形成的极小项和极大项 则 mi Mi Mi mi定义设由n个命题变项构成的析 合 取范式中所有的简单合 析 取式都是极小 大 项 则称该析 合 取范式为主析 合 取范式 由不同最小项所组成的析取式称为主析取范式由不同最大项所组成的合取式称为主合取范式 求 p q p r 的主析取范式 p q p r q p p r q r 析取范式 p r q q p q r r q r p p p q r p q r p q r p q r 主析取范式 m2 m3 m5 m7 用等值演算法求公式的主范式的步骤 1 先求析取范式 合取范式 2 将不是极小项 极大项 的简单合取式 简单析取式 化成与之等值的若干个极小项的析取 极大项的合取 需要利用同一律 零律 排中律 矛盾律