第一章第7节 逻辑推论.pdf

1 第一章 命题逻辑第一章 命题逻辑 1 1 命题和联结词 命题和联结词 1 2 公式和真值赋值 公式和真值赋值 1 3 等值演算 等值演算 1 4 对偶定理 对偶定理 1 5 联结词的完全集 联结词的完全集 1 6 范式 范式 1 7 逻辑推论逻辑推论 1 7 逻辑推论逻辑推论 定义定义1 20 若真值赋值 v 满足公式集 中的每个公 式 则称 v 满足 若有真值赋值满足 则称 是可满足的 否则称 是不可满足的 有限公式集 A1 An 是可满足的当且仅当公 式 A1 An 是可满足式 因此 判断一个有限 公式集的不可满足性可归结为判断公式的永假性 任何真值赋值 v 都满足空集 对于每个公式 A 若 A 则 v A 1 例例 判断以下公式集是否可满足 p s r q s p q 解解 设 v 是真值赋值 若 v q v s p 1 则 v p 1 且 v s 0 因而 v s r 0 所以 v p s r q 0 这表明不存在使得 p s r q s p q 这三个公式同时为真的真值赋值 因此 p s r q s p q 是不可满足的 例例 判断以下公式集是否可满足 p q r r s s 解解 若真值赋值 v 满足该公式集 则 v p q r v r s v s 1 因而 v s 0 v r 0 v p q 0 所以 只要令 v p 0 q 0 r 0 s 0 v 就满足该公 式集 这表明公式集 p q r r s s 是可满足的 例例 判断公式集 p q r p q r 是否可满足 11010 01110 11001 01101 1 1 0 0 q 0111 1001 1110 1100 p q rp q rrp 可以看出 有四个真值赋值满足该公式集 要说明公式集 不可满足 需要证明每个真值赋 值都使得 中至少一个公式为假 要说明公式集 可满足 只需找出一个满足 的 具体真值赋值即可 对于有穷的公式集 可以通过真值表判断 是 否可满足 2 定义定义1 21 设 是公式集 A 是公式 若每个满足 的真值赋值都满足 A 则称 A 是 的逻辑推 论 记为 A 若 A 不是 的逻辑推论 记为 A 简记 A1 An A 为 A1 AnA 将 A 简记为A A 表示从前提集 推出结论 A 在逻辑上是正确 的 即只要前提 真 结论 A 就一定真 尽管A 是 的逻辑推论 但是对于每个真值赋值 v 可能 v A 1 也可能存在 B 使得 v B 0 但是不 可能发生 v A 0 且使得每个B 都有 v B 1 的 情况 A 当且仅当对于每个真值赋值 v min v B B v A 推理是从已知前提推出结论的思维过程 下面我们 看一个例子 如果 6 月 7 日是星期日 则 6 月 7 日颐和园里人 多 6 月 7 日是星期日 因此 6 月 7 日颐和园里 人多 这个推理里有两个前提 如果 6 月 7 日是星期 日 则 6 月 7 日颐和园里人多 和 6 月 7 日是星 期日 结论是 6 月 7 日颐和园里人多 这是 一个正确的推理 如果用 A 表示 6 月 7 日是星期 日 用 B 表示 6 月 7 日颐和园里人多 则上 述推理的前提表示为 A B 和 A 结论表示为 B 如果用 A 和 B 分别表示任意命题 也不会产生前 提 A B 和 A 都真 而结论 B 为假的情况 例 如 用 A 表示 路滑 用 B 表示 小孩会摔 倒 推理仍然是正确的 这表明 由 A B 和 A 推出 B 是正确的推理形式 研究哪些推理形式是正确的 哪些推理形式是不 正确的 是逻辑学的基本任务 A 正是 由 前提集 推出结论 A 是正确的推理形式 的精确 定义 定理定理1 11 设 A 是公式 则A 当且仅当 A 是永真 式 证明证明 设A 任取真值赋值 v v 满足空集 所以 v A 1 因此 A 是永真式 设 A 是永真式 任取满足空集 的真值赋值 v 则 v A 1 因此 A A B 当且仅当 A B 是永真式 A B 当且仅当 对于任意真值赋值v v A v B 定理定理1 12 A1 An B 当且仅当 A1 An B 是永真式 证明证明 设 A1 AnB 任取真值赋值 v 若 v A1 An 1 则 v A1 v An 1 v 满 足 A1 An 所以 v B 1 因此 v A1 An B 1 若 v A1 An 0 则 v A1 An B 1 因此 A1 An B 是永真式 设 A1 An B 是永真式 任取满足 A1 An 的真值赋值 v 则 v A1 v An 1 v A1 An 1 所以 v B 1 因此 A1 AnB 定理定理1 13 A B 当且仅当 A B 且 B A 证明证明A B 当且仅当A B 是永真式 当且仅当 A B B A 是永真式 当且仅当A B 和 B A 都是永真式 当且仅当A B 且 B A 例例1 14 证明 A A B B 证明证明 若真值赋值 v 使得 v A v A B 1 则 v B 1 所以 A A B B 3 定理定理1 14 设 是公式集合 A 和 B 是公式 则 A B 当且仅当 A B 证明证明 设 A B 任取满足 的真值赋值 v 1 v A 0 这时 v A B 1 2 v A 1 v 满足 A 由 A B 得 出 v B 1 v A B 1 设 A B 任取满足 A 的真值赋 值 v 则 v 也满足 并且 v A 1 由 A B 得出 v A B 1 所以 v B 1 例例1 15 证明 A B B CA C 证法证法1 设真值赋值 v 使 v A B v B C 1 1 若 v A 0 则 v A C 1 2 若 v A 1 则由 v A B 1 得出 v B 1 再由 v B C 1 得 v C 1 v A C 1 证法证法2 若真值赋值 v 使得 v A C 0 且 v A B 1 则 v A 1 且 v C 0 再由 v A B 1 得出 v B 1 v B C 0 证法证法3 A B B CA C 当且仅当 A B B C AC 若 v A B v B C v A 1 则 v C 1 例例1 17 证明 p q p q r 111010 110110 000001 101101 1 1 0 0 q 01011 11101 11110 11000 p q rp qq rrp 当 v p 1 q 1 r 1 时 v p q 1 而v p q r 0 要证明公式 A 是公式集 的逻辑推论 即 A 需要证明 对于每个真值赋值 v 如果 v 使得 中 每个公式都真 则 v A 1 或者证明 对于每个 真值赋值 v 如果 v A 0 则 v 使得 中至少一 个公式为假 要证明公式 A 不是公式集 的逻辑推论 即 A 只需找出一个具体的真值赋值 v v 使得 中每个公式都真 但 v A 0 要证明 A1 An B 只需证明 对于每个真值 赋值 v 如果 v B 0 且 v A1 v An 1 1 则 v An 0 定理定理1 15 设是正整数 公式集 A1 An 是可满 足的当且仅当A1 An是可满足式 定理定理1 16 设 是公式集合 是不可满足的当 且仅当每个公式都是 的逻辑推论 证明证明 设 是不可满足的 A 为任意公式 显然 每个满足 的真值赋值都满足 A 因为以下命题 为真 对于每个真值赋值 v 若 v 满足 则 v 满足 A 所以 A 是 的逻辑推论 设每个公式都是 的逻辑推论 则永假式 0 是 的逻辑推论 若真值赋值 v 满足 则 v 满 足 0 这是不可能的 所以 是不可满足的 4 例1证明下列推理关系 1 在大城市球赛中 如果北京队第三 那么如果上海 队第二 那么天津队第四 沈阳队不是第一或北京队 第三 上海队第二 从而可知 如果沈阳队第一 那 么天津队第四 解 令p 北京队第三 q 上海队第二 r 天津队第四 s 沈 阳队第一 即证 p q r s p q s r 练习2即是 例2证明下列推理关系 2 如果国家不对农产品给予补贴 那么国家就要对农产品进行控 制 如果对农产品进行控制 农产品就不会短缺 或者农产品短 缺或者农产品过剩 事实上农产品不过剩 从而国家对农产品给 予了补贴 解 令p 国家对农产品给予了补贴 q 国家就要对农产品进行控 制 r 农产品短缺 s 农产品过剩 即证 p q q r r s s p 由 p q q r 得 p r 其等价与r p 由r s 等价与 s r 结合r p 所以 s p 因为 s 为 真 所以p为真 例3 由所给前提写出你能够得出的结论 1 一份统计表格的失真是由于数据不可靠 或者是由于计 算出错误 这份统计表格的失真不是由于计算出错误 2 如果张老师来了 这个问题可以得到解答 如果李老师 来了 这个问题也可以得到解答 这个问题没有得到解 答 3 如果我爬山 那么我很疲劳 我不疲劳 4 如果我的程序通过 那么我去踢球 如果我去踢球 那 么晚餐我能吃很多 今天晚餐我不想吃 解 1 p q q p 2 p r q r r p q 3 p q q p 4 p q q r r p 练习 证明以下关系成立 1 p q q r r s p s 2 p q r s p q s r 3 p q r s s e u p u 4 r s s q q q r 5 q s e u s q e 6 如果合同是有效得 那么张三应受罚 如果张三 受罚 他将破产 如果银行给张三贷款 他就不 语法概念 原子公式 公式 公式的替换实例 公式的对偶 式 文字 简单析取式 简单合取式 析取范式 合取范式 极大项 极小项 主析取范式 主合取 范式 语义概念 真值赋值 真值赋值 v 满足公式 A 永真式 永假 式 可满足式 公式的等值 联结词的完全集 可 满足的公式集 公式 A 是公式集 的逻辑推论 与语法和语义都有关的概念 公式 A 的主析取范式 公式 A 的主合取范式 第一章练习 1 假定计算机专业二年级上学期开设的主修课程是 英语 每周4学时 数学分析每周4学时 汇编每周4学时 数据结构每周4学时 电路分析每周4学时 专业课教 学要求以上课程安排上午讲授 且每日一课4学时 各任课老师提出如下要求 外语老师要求周一或周三上 课 数学老师要求周三或周五上课 电路分析老师要 求周二或周四上课 汇编语言老师要求周一或周二上 课 数据结构老师要求周四或周五上课 按上述要求 安排课表 5 解 设p1 英语周一上 p2 英语周三上 q1 数学分析周三上 q2 数学分析周五上 r1 电路分析周二上 r2 电路分析周四上 s1 汇编周一上 s2 汇编周二上 w1 数据结构周四上 w2 数据结构周五上 所以各个老师的要求表示如下 注意是异或 p1 p2 p1 p2 q1 q2 q1 q2 r1 r2 r1 r2 s1 s2 s1 s2 w1 w2 w1 w2 解 显然如果要满足上述条件 必须是上述五个公式的合 取为真的情况 既G p1 p2 p1 p2 q1 q2 q1 q2 r1 r2 r1 r2 s1 s2 s1 s2 w1 w2 w1 w2 取值为真 即求它 的极小项和析取 此外因为p1 s1 0 p2 q1 0 q2