数理逻辑是以数学的方法研究推理的形式结构和规律的数学学科

第 1章 命 题 逻 辑数 理 逻 辑 是 以 数 学 的 方 法 研 究 推 理 的 形 式 结构 和 规 律 的 数 学 学 科数 学 方 法 ： 建 立 一 套 符 号 来 描 述 和 讨 论 问 题 ， 避免 歧 义 性推 理 ： 就 是 研 究 前 提 和 结 论 之 间 的 关 系 和 思 维 规律 ， 亦 即 符 号 之 间 的 关 系 第 1章 命 题 逻 辑 第 1章 命 题 逻 辑 1.1 命 题 符 号 化 及 联 结 词1.2 命 题 公 式 及 分 类 1.3 等 值 演 算 1.4 联 结 词 全 功 能 集 1.5 对 偶 与 范 式 1.6 推 理 理 论 *1.7 命 题 演 算 的 自 然 推 理 形 式 系 统 N 1.8 例 题 选 解 习 题 一 第 1章 命 题 逻 辑 1.1 命 题 符 号 化 及 联 结 词 任 何 基 于 命 题 分 析 的 逻 辑 称 为 命 题 逻 辑 。 命 题是 研 究 思 维 规 律 的 科 学 中 的 一 项 基 本 要 素 ， 它 是 一个 判 断 的 语 言 表 达 。命 题 : 能 唯 一 判 断 真 假 的 陈 述 句 。 第 1章 命 题 逻 辑 这 种 陈 述 句 的 判 断 只 有 两 种 可 能 ， 一 种是 正 确 的 判 断 ， 一 种 是 错 误 的 判 断 。 如 果 某个 陈 述 句 的 判 断 为 真 （ 与 人 们 公 认 的 客 观 事实 相 符 ） ， 则 我 们 称 其 为 一 真 命 题 ， 并 说 此命 题 的 ， 否 则 称 为 假 命 题 ， 并 说 此命 题 的 。 第 1章 命 题 逻 辑【 例 1.1.1】 下 述 各 句 均 为 命 题 ：（ 1） 4是 偶 数 。（ 2） 煤 是 白 色 的 。（ 3） 几 何 原 本 的 作 者 是 欧 几 里 德 。（ 4） 2190年 人 类 将 移 居 火 星 。（ 5） 地 球 外 也 有 生 命 存 在 。 第 1章 命 题 逻 辑 上 述 命 题 中 （ 1） 、 （ 3） 是 真 命 题 ， （ 2）是 假 命 题 ， 其 中 的 （ 3） 可 能 有 人 说 不 出 它 的真 假 ， 但 客 观 上 能 判 断 真 假 。 （ 4） 的 结 果 目前 谁 也 不 知 道 ， 但 到 了 时 候 则 真 假 可 辨 ， 即 其真 值 是 客 观 存 在 的 ， 因 而 是 命 题 。 同 样 ， （ 5）的 真 值 也 是 客 观 存 在 的 ， 只 是 我 们 地 球 人 尚 不知 道 而 已 ， 随 着 科 学 技 术 的 发 展 ， 其 真 值 是 可以 知 道 的 ， 因 而 也 是 命 题 。 第 1章 命 题 逻 辑 【 例 1.1.2】 下 列 语 句 不 是 命 题 ： （ 1） 你 好 吗 ？ （ 2） 好 棒 啊 ！ （ 3） 请 勿 吸 烟 。 （ 4） x 3。 （ 5） 我 正 在 说 谎 。 （ 1） 、 （ 2） 、 （ 3） 均 不 是 陈 述 句 ， 因 而 不 是命 题 。 （ 4） 是 陈 述 句 ， 但 它 的 真 假 取 决 于 变 量 x的取 值 ， 例 如 取 x为 4时 其 值 为 真 ， 取 x为 2时 其 值 为 假 ，即 其 真 值 不 唯 一 ， 因 此 不 是 命 题 。 （ 5） 也 是 陈 述 句 ，但 它 是 悖 论 ， 因 而 也 不 是 命 题 。 第 1章 命 题 逻 辑 从 上 面 讨 论 可 以 看 出 ， 判 断 一 个 语 句 是 否 是 命题 的 关 键 是 ： (1)语 句 必 须 是 陈 述 句 。 (2)陈 述 句 必 须 具 有 唯 一 的 真 值 。 要 注 意 两 点 ： 一 个 陈 述 句 在 客 观 上 能 判 断 真 假 ， 而 不 受 人的 知 识 范 围 的 限 制 。 一 个 陈 述 句 暂 时 不 能 确 定 真 值 ， 但 到 了 一 定时 候 就 可 以 确 定 ， 与 一 个 陈 述 句 的 真 值 不 能 唯 一 确 定是 不 同 的 。 第 1章 命 题 逻 辑 以 上 所 讨 论 的 命 题 均 是 一 些 简 单 陈 述 句 。 在语 言 学 中 称 为 简 单 句 ， 其 结 构 均 具 有 “ 主 语 +谓语 ” 的 形 式 ， 在 数 理 逻 辑 中 ， 我 们 将 这 种 由 简 单句 构 成 的 命 题 称 为 简 单 命 题 ， 或 称 为 原 子 命 题 ，用 p、 q、 r、 pi、 qi、 ri等 符 号 表 示 （ 亦 可 用 其 它小 写 的 英 文 字 母 表 示 ） 。 如 ： p： 4是 偶 数 。 q： 煤 是 白 的 。 r： 几 何 原 本 的 作 者 是 欧 几 里 德 。 第 1章 命 题 逻 辑【 例 1.1.3】 下 列 命 题 不 是 简 单 命 题 ：（ 1） 4是 偶 数 且 是 2的 倍 数 。（ 2） 北 京 不 是 个 小 城 市 。（ 3） 小 王 或 小 李 考 试 得 第 一 。（ 4） 如 果 你 努 力 ， 则 你 能 成 功 。（ 5） 三 角 形 是 等 边 三 角 形 ， 当 且 仅当 三 内 角 相 等 。 第 1章 命 题 逻 辑 上 面 的 命 题 除 （ 3） 的 真 假 需 由 具 体 情 况 客 观 判断 外 ， 余 者 的 真 值 均 为 1。 但 是 它 们 均 不 是 简 单 命 题 ，分 别 用 了 “ 且 ” 、 “ 非 ” 、 “ 或 ” 、 “ 如 果则”、“ 当 且 仅 当 ” 等 联 结 词 。 由 命 题 和 联 结 词 构 成 的 命 题 称 为 复 合命 题 。 构 成 复 合 命 题 的 可 以 是 原 子 命 题 ， 也 可 以 是另 一 个 复 合 命 题 。 一 个 复 合 命 题 的 真 值 不 仅 与 构 成 复合 命 题 的 命 题 的 真 值 有 关 ， 而 且 也 与 所 用 联 结 词 有 关 。下 面 我 们 给 出 几 个 基 本 的 联 结 词 。 第 1章 命 题 逻 辑 1.否 定 联 结 词 设 p为 任 一 命 题 ， 复 合 命 题 “ 非 p”（ p的 否 定 ）称 为 p的 否 定 式 ， 记 作 。 为 否 定 联 结 词 。 为 真 ， 当 且 仅 当 p为 假 。 的 真 值 亦 可 由 表 1.1.1所 示 的 称 为 “ 真 值 表 ”的 表 格 确 定 。 由 表 1.1.1可 知 ： 命 题 p为 真 ， 当 且 仅当 为 假 。 p ppp 表 1.1.1 p0 1 1 0p 第 1章 命 题 逻 辑【 例 1.1.4】 (1) p： 4是 偶 数 。 其 真 值 为 1。 ： 4不 是 偶 数 。 其 真 值 为 0。 (2) q： 这 些 都 是 学 生 。 ： 这 些 不 都 是 学 生 。pq 第 1章 命 题 逻 辑 注 ： 否 定 联 结 词 使 用 的 原 则 ： 将 真 命 题变 成 假 命 题 ， 将 假 命 题 变 成 真 命 题 。 但 这 并不 是 简 单 的 随 意 加 个 不 字 就 能 完 成 的 。 例 如上 例 中 的 （ 2） ， q的 否 定 式 就 不 能 写 成 “ 这些 都 不 是 学 生 ” 。 事 实 上 严 格 来 讲 ， “ 不 是 ”不 一 定 否 定 “ 是 ” 。 如 阿 契 贝 难 题 ： “ 本 句是 六 字 句 ” 与 “ 本 句 不 是 六 字 句 ” 均 是 真 命题 。 不 过 ， 一 般 地 ， 自 然 语 言 中 的 “ 不 ” 、“ 无 ” 、 “ 没 有 ” 、 “ 并 非 ” 等 词 均 可 符 号化 为 . 第 1章 命 题 逻 辑 2.合 取 联 结 词 “ ” 设 p、 q是 任 意 两 个 命 题 ， 复 合 命 题 “ p且 q”（ p与 q） 称 为 p与 q的 合 取 式 ， 记 作 ： p q。 “ ”是 合取 联 结 词 。 p q为 真 ， 当 且 仅 当 p、 q均 为 真 。 p q的 真 值 表 如 表 1.1.2所 示 。 表 1.1.2 p q p q0 0 00 1 0 1 0 01 1 1 第 1章 命 题 逻 辑【 例 1.1.5】 (1) p： 4是 偶 数 。 q： 3是 素 数 。 则 p q： 4是 偶 数 且 3是 素 数 。 其 真 值 为 1。 (2) r： 煤 是 白 的 。 则 p r： 4是 偶 数 且 煤 是 白 的 。 真 值 为 0。 第 1章 命 题 逻 辑 3.析 取 联 结 词 “ ” 设 p、 q是 任 意 两 个 命 题 ， 复 合 命 题 “ p或 q”称为 p、 q的 析 取 式 ， 记 作 ： p q。 “ ”称 为 析 取 联结 词 。 p q为 假 ， 当 且 仅 当 p、 q同 为 假 。 表 1.1.3 p q p q0 0 00 1 11 0 1 1 1 1 第 1章 命 题 逻 辑【 例 1.1.6】 (1) p： 小 王 喜 欢 唱 歌 。 q： 小 王 喜 欢 跳 舞 。 则 p q： 小 王 喜 欢 唱 歌 或 喜 欢 跳 舞 。 (2) p： 明 天 刮 风 。 q： 明 天 下 雨 。 则 p q： 明 天 刮 风 或 者 下 雨 。 第 1章 命 题 逻 辑 注 “ ”的 逻 辑 关 系 是 明 确 的 。 即 p、 q二 命 题 中 至少 有 一 个 为 真 则 析 取 式 为 真 。 因 而 ， 自 然 语 言 中 常 用的 联 结 词 诸 如 ： “ 或 者或 者”、 “ 可 能可 能”等 ， 都 可 以 符 号 化 为 “ ”。 但 日 常 语 言 中 的 “ 或 ” 是具 有 二 义 性 的 ， 用 “ 或 ” 联 结 的 命 题 有 时 是 具 有 相 容性 的 ， 如 例 1.1.6中 的 二 例 ， 我 们 称 之 为 可 兼 或 。 而 有时 又 具 有 排 斥 性 ， 称 为 不 可 兼 或 （ 异 或 ） ， 如 ：（ 1） 小 李 明 天 出 差 去 上 海 或 去 广 州 。（ 2） 刘 昕 这 次 考 试 可 能 是 全 班 第 一 也 可 能 是 全 班 第 二 。 第 1章 命 题 逻 辑 4.蕴 含 联 结 词 “ ” 设 p、 q是 任 意 两 个 命 题 ， 复 合 命 题 “ 如 果 p， 则q”称 为 p与 q的 蕴 含 式 ， 记 作 ： pq。 P称 为 蕴 含 式 的前 件 ， q称 为 蕴 含 式 的 后 件 ， 称 为 蕴 含 联 结 词 。pq为 假 ， 当 且 仅 当 p为 真 、 q为 假 。 表 1.1.4 p q p q0 0 10 1 11 0 01 1 1 第 1章 命 题 逻 辑【 例 1.1.7】 (1) p： 天 下 雨 了 。 q： 路 面 湿 了 。 则 pq： 如 果 天 下 雨 ， 则 路 面 湿 。 (2) r： 三 七 二 十 一 。 则 pr： 如 果 天 下 雨 ， 则 三 七 二 十 一 。 第 1章 命 题 逻 辑 注 (1)逻 辑 中 ， 前 件 p为 假 时 ， 无 论 后 件 q是 真 是 假 ， 蕴 含 式 pq的 真 值 均 为 1。 这 与 日常 语 言 中 的 ， 特 别 是 数 学 上 常 用 的 “ 真 蕴 含 真 ”不 太 一 样 。 事 实 上 并 不 矛 盾 ， 例 如 某 人 说 ：“ 如 果 张 三 能 及 格 ， 那 太 阳 从 西 边 升 起 。 ” 说话 者 当 然 知 道 “ 张 三 能 及 格 ” 与 “ 太 阳 从 西 边升 起 ” 风 马 牛 不 相 及 ， 而 一 般 人 此 时 并 没 有 说谎 的 必 要 ， 即 这 是 真 命 题 ， 它 所 要 明 确 的 是“ 张 三 能 及 格 ” 是 假 命 题 。 第 1章 命 题 逻 辑 （ 2） 正 如 前 面 所 说 ， 数 理 逻 辑 中 的 联 结 词 是对 日 常 语 言 中 的 联 结 词 的 一 种 逻 辑 抽 象 ， 日 常 语 言中 联 结 词 所 联 结 的 句 子 之 间 是 有 一 定 内 在 联 系 的 ，但 在 数 理 逻 辑 中 ， 联 结 词 所 联 结 的 命 题 可 以 毫 无 关系 。 如 在 日 常 语 言 中 “ 如 果则”所 联 结 的 句 子之 间 表 现 的 是 一 种 因 果 关 系 ， 如 例 1.1.7中 的 （ 1） 。但 在 数 理 逻 辑 中 ， 尽 管 说 前 件 蕴 涵 后 件 ， 但 两 个 命题 可 以 是 毫 不 相 关 的 ， 如 例 1.1.7中 的 （ 2） 。 第 1章 命 题 逻 辑 （ 3） pq的 逻 辑 关 系 是 ： p是 q的 充 分 条 件 ， q是 p的 必 要 条 件 。 在 日 常 语 言 中 ， 特 别 是 在 数 学语 言 中 ， q是 p的 必 要 条 件 还 有 许 多 不 同 的 叙 述 方式 ， 如 ： “ p仅 当 q（ 仅 当 q， 则 p） ” 、 “ 只 有 q才 p”、 “ 只 要 p就 q”、 “ 除 非 q， 否 则 非 p（ 非 p，除 非 q） ” 等 ， 均 可 符 号 化 成 pq的 形 式 。 第 1章 命 题 逻 辑【 例 1.1.8】 符 号 化 下 列 命 题 ： （ 1） 只 要 天 下 雨 ， 我 就 回 家 。 （ 2） 只 有 天 下 雨 ， 我 才 回 家 。 （ 3） 除 非 天 下 雨 ， 否 则 我 不 回 家 。 （ 4） 仅 当 天 下 雨 ， 我 才 回 家 。 解 ： 设 p： 天 下 雨 。 q： 我 回 家 。 则 （ 1）符 号 化 为 pq。 （ 2） 、 （ 3） 、 （ 4） 均 符 号化 为 qp（ 或 等 价 形 式 ： ). p q 第 1章 命 题 逻 辑 5.等 价 联 结 词 “ ” 设 p、 q是 任 意 两 个 命 题 ， 复 合 命 题 “ p当 且 当 q”称 为 p与 q的 等 价 式 ， 记 作 ： p q。 “ ” 称 为 等 价 联 结 词 。 p q为 真 ， 当 且 仅当 p、 q真 值 相 同 。 p q的 真 值 表 如 表 1.1.5所 示 表 1.1.5 p q p q0 0 10 1 01 0 01 1 1 第 1章 命 题 逻 辑 【 例 1.1.9】 (1)p： 2+2=4。 q： 5是 素 数 。 则 p q： 2+2=4当 且 仅 当 5是 素 数 。 (2)p： A= B。 q： 二 角 是 同 位 角 。 则 p q： A= B当 且 仅 当 二 角 是 同 位 角 。 在 （ 1） 中 的 p与 q并 无 内 在 关 系 ， 但 因 二 者 均 为 真 ， 所以 p q的 真 值 为 1。 在 （ 2） 中 由 于 相 等 的 两 角 不 一 定 是 同 位 角 ， 所 以 真 值为 0。 第 1章 命 题 逻 辑【 例 1.1.10】 将 下 列 自 然 语 言 形 式 化 :（ 1） 如 果 天 不 下 雨 并 且 不 刮 风 ， 我 就 去 书 店 。（ 2） 小 王 边 走 边 唱 。（ 3） 除 非 a能 被 2整 除 ， 否 则 a不 能 被 4整 除 。（ 4） 此 时 ， 小 纲 要 么 在 学 习 ， 要 么 在 玩 游 戏 。（ 5） 如 果 天 不 下 雨 ， 我 们 去 打 篮 球 ， 除 非 班 上 有 会 。 第 1章 命 题 逻 辑 解 （ 1） 设 p： 今 天 天 下 雨 ， q： 今 天 天 刮 风 ，r： 我 去 书 店 。 则 原 命 题 符 号 化 为 ： (2)设 p： 小 王 走 路 ， q： 小 王 唱 歌 。 则 原 命 题符 号 化 为 ： p q (3)设 p： a能 被 2整 除 ， q： a能 被 4整 除 。 则 原命 题 符 号 化 为 ： p q r p q q p或 第 1章 命 题 逻 辑 (4)设 p： 小 刚 在 学 习 ， q： 小 刚 在 玩 游 戏 。则 原 命 题 符 号 化 为 ：( ) ( ) ( ) ( ) p q p q p q p q或 (5)设 p： 今 天 天 下 雨 ， q： 我 们 去 打 篮 球 ，r： 今 天 班 上 有 会 。 则 原 命 题 符 号 化 为 ：( ) r p q 第 1章 命 题 逻 辑补 充 ：小 明 和 小 亮 既 是 兄 弟 又 是 同 学 。P Q如 果 你 和 他 不 都 是 白 痴 ， 则 你 俩 都 不 会 去 干 此 傻 事 。无 论 你 和 他 去 不 去 ， 我 去 。 )()( srqp )()()()( rqprqprqprqp 第 1章 命 题 逻 辑 1.2 命 题 公 式 及 分 类 为 了 用 数 学 的 方 法 研 究 命 题 ， 就 必 须 像 数学 处 理 问 题 那 样 将 命 题 公 式 化 ， 并 讨 论 对 于 这些 公 式 的 演 算 （ 推 理 ） 规 则 ， 以 期 由 给 定 的 公式 推 导 出 新 的 命 题 公 式 来 。 第 1章 命 题 逻 辑 前 面 我 们 用 p、 q、 r等 符 号 表 示 确 定 的 简 单 命 题 ，通 常 此 时 称 它 们 为 命 题 常 元 。 而 事 实 上 ， 这 些 常 元 无论 具 体 是 怎 样 的 简 单 命 题 ， 它 们 的 真 值 均 只 可 能 是“ 1”或 “ 0”。 为 了 更 广 泛 地 应 用 命 题 演 算 ， 在 研 究 时 ，我 们 只 考 虑 命 题 的 “ 真 ” 与 “ 假 ” ， 而 不 考 虑 它 的 具体 涵 义 （ 即 只 重 “ 外 延 ” ， 不 顾 “ 内 涵 ” ） 。 譬 如 ：当 p是 一 个 真 命 题 时 ， p就 是 一 个 假 命 题 ， 而 不 管此 时 p表 示 的 是 命 题 “ 三 七 二 十 一 ” ， 还 是 命 题 “ 今天 天 下 雨 ” 。 这 时 的 p实 际 上 就 是 一 个 简 单 命 题 的 抽象 ， 就 如 同 数 学 公 式 中 的 变 量 x一 样 ， 我 们 称 其 为 命题 变 元 。 第 1章 命 题 逻 辑命 题 常 元 一 个 真 值 确 定 的 命 题命 题 变 元 一 个 真 值 尚 未 确 定 的 命 题 ， 以 p、 q、r等 表 之 。注 意 ： 命 题 变 元 不 是 命 题 ， 没 有 确 定 的 真 值 ，只 有 代 以 确 定 的 命 题 ， 变 成 常 元 ， 才 有 真 值 第 1章 命 题 逻 辑 命 题 公 式 由 命 题 变 元 （ 常 元 ） 符 、 联 结 词 和 圆括 号 按 一 定 逻 辑 关 系 联 结 起 来 的 字 符 串 。 所 谓 按 一 定 的 逻 辑 关 系 ， 即 字 符 串 的 构 成要 求 合 理 ， 如 （ p） 是 个 合 理 的 构 成 ， 是 命题 ， （ p） 不 是 合 理 的 构 成 ， 就 不 是 命 题 公 式 ，同 样 （ pq） r） 也 不 是 合 理 的 构 成 （ 括 号 必须 成 对 出 现 ） ， 因 此 也 不 是 命 题 公 式 。 合 理 的 命题 公 式 叫 做 合 式 公 式 （ 亦 称 真 值 函 数 ） ， 记 作 ： wff（ wff=Well-Formed Formulas） 。 第 1章 命 题 逻 辑定 义 1.2.1 合 式 公 式 的 递 归 定 义 ： 1 单 个 的 命 题 变 元 （ 或 常 元 ） 是 合 式 公 式 。 2 如 果 A是 一 个 合 式 公 式 ， 则 （ A） 也 是 合式 公 式 。 3 如 果 A、 B均 是 合 式 公 式 ， 则 （ A B） 、（ A B） 、 （ AB） 、 （ A B） 也 都 是 合 式公 式 。 4 有 限 次 地 应 用 1 , 2 , 3 组 成 的 公 式 是合 式 公 式 。默 认 联 结 词 的 优 先 级 ： 、 、 、 、 第 1章 命 题 逻 辑 例 如 ： （ （ p q） r） 、 均 是 合 式 公 式 。第 3式 的 生 成 过 程 如 下 ： p 1 q 1 （ pq） 3 r 1 （ q r） 3 （ p） 2 ( p) r) 3 (pq) (q r) 3 3 )()()( rprqqp )()( rqp )()()( rprqqp 第 1章 命 题 逻 辑 定 义 1.2.2(1)若 A是 单 个 命 题 （ 变 元 或 常 元 ） ， 则 称 为 0层 公 式 。(2)称 A为 n+1（ n0） 层 公 式 是 指 A符 合 下 列 诸 情 况 之 一 A= B， B是 n层 公 式 ； A=B C， 其 中 B为 i层 公 式 、 C为 j层 公 式 ， max（ i， j） = n； A=B C， 其 中 B、 C的 层 次 同 ； A=BC， 其 中 B、 C的 层 次 同 ； A=B C， 其 中 B、 C的 层 次 同 。 第 1章 命 题 逻 辑解 释 ： 指 定 命 题 变 元 代 表 某 个 具 体 的 命 题【 例 1.2.1】 公 式 ： A=（ p q） r。 解 释 I1： 假 设 p： 现 在 是 白 天 ， q： 现 在 是 晴天 ， r： 我 们 能 看 见 太 阳 。 则 A： 如 果 现 在 是 白 天 且 是 晴 天 ， 则 我 们 能 看见 太 阳 。 其 真 值 为 1。 解 释 I 2： 假 设 p、 q如 上 ， r： 我 们 能 看 见 星 星 。则 A： 如 果 现 在 是 白 天 且 是 晴 天 ， 则 我 们 能 看 见星 星 。 其 真 值 为 0。 第 1章 命 题 逻 辑 由 此 可 见 ， 不 同 的 解 释 可 使 公 式 有 不 同 的真 值 。 事 实 上 ， 对 于 命 题 变 元 无 论 做 什 么 样 的解 释 ， 它 都 只 有 两 种 结 果 ： 或 者 是 “ 真 ” ， 或者 是 “ 假 ” 。 从 而 由 变 元 和 联 结 词 组 成 的 公 式所 表 示 的 复 合 命 题 ， 也 是 或 为 “ 真 ” ， 或 为“ 假 ” 。 如 前 所 述 这 才 是 我 们 所 需 要 的 。 因 此 ，欲 获 取 命 题 公 式 的 真 值 ， 并 非 只 有 “ 解 释 ” 一个 途 径 ， 还 可 以 通 过 “ 赋 值 ” 获 得 。 第 1章 命 题 逻 辑赋 值 （ 真 值 指 派 ） 对 命 题 变 元 指 派 确 定 的 真 值 。赋 值 是 一 组 由 0、 1构 成 的 数 串 ， 按 字 典 顺 序 （ 或 下 标 ）对 应 公 式 中 的 命 题 符 。如 例 1.2.1中 ， 对 公 式 A=(p q） r：解 释 I1 实 际 上 是 对 变 元 p、 q、 r赋 值 111， 得 A的 真 值为 1；解 释 I 2 实 际 上 是 对 变 元 p、 q、 r赋 值 110， 得 A的 真 值为 0；A的 真 值 是 在 对 p、 q、 r的 某 种 赋 值 下 所 得 的 真 值 。 第 1章 命 题 逻 辑 定 义 1.2.3 设 p1， p2， pn是 公 式 A中 所 包 含 的 所有 命 题 变 元 ， 给 p1， p2， pn各 赋 一 个 真 值 称 为对 A的 一 个 赋 值 ， 那 些 使 A的 真 值 为 1的 赋 值 称 为A的 成 真 赋 值 ， 使 A的 真 值 为 0的 赋 值 称 为 A的 成假 赋 值 。 如 例 1.2.1中 ， 111是 A=（ p q） r的 成 真 赋值 ， 110是 A的 成 假 赋 值 。 根 据 前 面 对 联 结 词 的 讨论 知 ： 001、 011、 101、 000、 010也 都 是 A的 成 真赋 值 。 第 1章 命 题 逻 辑 问 题 若 公 式 A含 有 n（ n1） 个 命 题 变元 ， 那 么 对 A共 有 多 少 种 不 同 的 赋 值 ？ 答 ：因 为 n个 变 元 赋 值 后 形 成 一 个 n位 的 二 进 制数 ， 所 以 共 有 2n个 。 将 公 式 A在 所 有 赋 值 情 况 下 的 取 值 列成 表 ， 称 为 A的 真 值 表 。 第 1章 命 题 逻 辑构 造 真 值 表 的 步 骤 如 下 ： （ 1） 找 出 命 题 公 式 中 所 含 的 所 有 命 题 变 元 并按 下 标 或 字 典 顺 序 给 出 ； （ 2） 按 从 低 到 高 的 顺 序 写 出 各 层 次 ； （ 3） 顺 序 列 出 所 有 的 赋 值 （ 2n个 ） ； 对 应 每个 赋 值 ， 计 算 命 题 公 式 各 层 次 的 真 值 ， 直 到 最 后 计算 出 命 题 公 式 的 真 值 。 第 1章 命 题 逻 辑 【 例 1.2.2】 求 下 列 命 题 公 式 的 真 值 表 ：(1) ( )(2) ( ) ( )(3) ( ) p q qp q p qp q r 第 1章 命 题 逻 辑 表 1.2.1公 式 的 真 值 表 如 表 1.2.1所 示 。 ( ) p q q 第 1章 命 题 逻 辑 表 1.2.2 公 式 的 真 值 表 )()( qpqp 第 1章 命 题 逻 辑 表 1.2.3 公 式 的 真 值 表 如 表 1.2.3所 示rqp )( 第 1章 命 题 逻 辑 由 上 可 知 ， 有 的 公 式 在 任 何 赋 值 情 况 下 真 值 恒 为 1， 如例 1.2.2（ 1） ； 有 的 公 式 在 任 何 赋 值 情 况 下 真 值 恒 为 0，如 例 1.2.2（ 2） ； 有 的 公 式 某 些 赋 值 使 其 真 值 为 1， 而另 一 些 赋 值 使 其 真 值 为 0， 因 此 可 将 公 式 分 为 如 下 三类 ： 永 真 式 （ 重 言 式 ） 所 有 赋 值 均 为 成 真 赋 值 的 公 式 。 永 假 式 （ 矛 盾 式 ） 所 有 赋 值 均 为 成 假 赋 值 的 公 式 。 可 满 足 式 至 少 有 一 组 赋 值 是 成 真 赋 值 的 公 式 。 由 定 义 可 知 ， 任 何 不 是 矛 盾 式 的 公 式 是 可 满 足 式 ， 其中 包 含 永 真 式 第 1章 命 题 逻 辑补 充 ： 写 出 下 列 公 式 的 真 值 表 ： )()()( )()( )()( )()()( )( rqprpqp srqprqp qsrp rqrprqp rqp 第 1章 命 题 逻 辑 1.3 等 值 演 算 【 例 1.3.1】 构 造 公 式 的 真 值 表 解 公 式 的 真 值 表 如 表 1.3.1所 示 。 qp )( qp qp pq qp )( qp qp pq 第 1章 命 题 逻 辑 表 1.3.1 第 1章 命 题 逻 辑 由 例 题 可 见 ， 的 真 值 表 是 完 全 相 同 的 ， 这 种 情 况 并 不 是 偶 然 的 。事 实 上 ， 给 定 n个 命 题 变 元 ， 按 照 公 式 的 生 成 规 则 ，我 们 可 以 得 到 无 穷 多 个 命 题 公 式 ， 但 这 无 穷 多 个命 题 公 式 的 真 值 表 却 只 有 有 限 个 。 如 例 1.3.1， 许多 公 式 在 变 元 的 各 种 赋 值 下 真 值 是 一 样 的 ， 我 们称 其 为 等 值 的 ， 那 么 如 何 判 断 两 个 公 式 等 值 呢 ？ qp )( qp qp pq 第 1章 命 题 逻 辑 定 义 1.3.1 设 A、 B是 任 意 两 个 命 题 公 式 若 等 价 式 A B为 重 言 式 ， 则 称 A与 B是 等 值 的 ， 记 作 :A B。 定 理 1.3.1 A B为 重 言 式 ， 当 且 仅 当 A、 B具 有 相 同的 真 值 表 。 注 (1)如 果 A B不 是 重 言 式 ， 则 称 A与 B不 等值 ， 可 记 作 ： A B。 (2)“ ”与 “ =”不 同 ， “ A=B”表 示 二 公 式 一 样 ，“ A B”表 示 二 公 式 真 值 一 样 ， 第 1章 命 题 逻 辑 (3)“ ”与 “ ” 是 两 个 完 全 不 同 的 符 号 。 “ ”是 联 结 词 ， A B是 一 个 公 式 。 “ ” 不 是 联 结 词 ，而 是 两 个 公 式 之 间 的 关 系 符 ， A B并 不 是 一 个 公式 ， 而 只 是 表 示 A与 B是 两 个 真 值 相 同 的 公 式 。 (4)“ ”的 性 质 ： A A（ 自 反 性 ） ； 若 A B， 则 B A（ 对 称 性 ） ； 若 A B， B C， 则 A C（ 传 递 性 ） 。 第 1章 命 题 逻 辑利 用 真 值 表 我 们 可 以 证 明 许 多 等 值 式 ：(1)双 重 否 定 律 (2)幂 等 律 A A A A A A(3)交 换 律 A B B A A B B A(4)结 合 律 (A B) C A (B C) (A B) C A (B C)(5)分 配 律 A (B C) (A B) (A C) A (B C) (A B) (A C)(6)德 摩 根 律 A A ( )( ) A B A BA B A B 第 1章 命 题 逻 辑(7)吸 收 律 (8)零 律(9)同 一 律 AA AAAA ABAA ABAA 10 00 11 )( )( 第 1章 命 题 逻 辑(10)排 中 律 (11)矛 盾 律 (12)蕴 涵 等 值 式 (13)等 价 等 值 式 (14)假 言 易 位 (15)等 价 否 定 等 值 式 (16)归 谬 论 ABABA BABA ABBA ABBABA BABA AA AA )()( )()(01 第 1章 命 题 逻 辑【 例 1.3.2】 证 明 等 价 等 值 式 ： A B (AB) (BA)。 解 作 如 表 1.3.2所 示 的 真 值 表 。 表 1.3.2 因 此 ， A B (AB) (BA)。 第 1章 命 题 逻 辑 【 例 1.3.3】 用 等 值 演 算 验 证 等 值 式 p（ qr） （ p q） r。 证 明 ( )( )( )( ) ( )( ) p q rp q rp q rp q rp q rp q r （ 蕴 涵 等 值 式 ） （ 蕴 涵 等 值 式 ） （ 结 合 律 ） （ 德 摩 根 律 ） （ 蕴 涵 等 值 式 ） 第 1章 命 题 逻 辑【 例 1.3.4】 化 简 公 式 并 判 断 公 式 的 类 型 。( ( ) ( ) ( ) p q r q r p r解 ( ( ) ( ) ( )( ) ( ) ( )( ) ( ) )( ) ) ( ) )( ) ( ) ) ( ( ) ( ) )1 p q r q r p rp q r q r p rp q r q p rp q r p q rp q p q rp q p q rrr （ 结 合 律 ） （ 分 配 律 ） （ 结 合 律 、 交 换 律 ）（ 分 配 律 ） （ 德 摩 根 律 ） （ 排 中 律 ） （ 同 一 律 ） 该 公 式 为 可 满 足 式 第 1章 命 题 逻 辑【 例 1.3.5】 判 断 下 列 公 式 的 类 型 。 ( ) ) p q q p解 （ 分 配 律 ） （ 矛 盾 律 ） （ 同 一 律 ） （ 蕴 涵 等 值 式 ） （ 德摩 根 律 、 双 重 否 定 律 ）（ 交 换 律 、 结 合 律 ） （ 排 中 律 ） （ 零 律 ） 11 )( )( )( )( )0)( )()( )( q qpp pqp pqp pqp pqp pqqqp pqqp 第 1章 命 题 逻 辑 因 此 ， 公 式 是一 个 重 言 式 。 等 值 演 算 在 计 算 机 硬 件 设 计 ， 开 关理 论 和 电 子 元 器 件 中 都 占 据 重 要 地 位 。( ) ) p q q p 第 1章 命 题 逻 辑 1.4 联 结 词 全 功 能 集 前 面 我 们 一 共 介 绍 了 五 个 联 结 词 ： 、 、 、 和 ， 并 用 它 们 构 成 了 一些 命 题 公 式 ， 且 看 到 了 有 些 公 式 书 写 形 式 尽 管不 同 ， 但 实 际 上 是 等 值 的 。 因 此 我 们 不 禁 要 问 ： （ 1） 总 共 有 多 少 个 命 题 公 式 ？ （ 2） 总 共 有 多 少 个 联 结 词 ？ 第 1章 命 题 逻 辑 对 于 含 有 两 个 命 题 变 元 的 公 式 ， 理 论 上 讲可 以 书 写 出 无 穷 多 个 公 式 ， 但 互 不 等 值 的 公 式恰 有 =24=16个 。 对 应 着 16个 不 同 的 真 值 表（ 真 值 表 共 有 22行 ， 行 上 的 每 个 记 入 值 又 可 在 0、1中 任 取 其 一 ， 因 此 构 成 个 不 同 的 真 值 表 ） ，亦 即 对 应 着 16个 真 值 函 数 Fi（ i=0， 1， 15） ，其 中 F i： 00， 01， 10， 110， 1， 如 表1.4.1所 示 。222 222 第 1章 命 题 逻 辑 表 1.4.1 第 1章 命 题 逻 辑 这 里 ， F0和 F15正 是 两 个 常 值 函 数 ： 永 假 式0和 永 真 式 1； F3和 F5分 别 是 命 题 变 元 p和 q； F1是 我 们 所 熟 知 的 二 元 真 值 函 数 p q； F7是 二 元 真 值 函 数 p q； F9是 二 元 真 值 函 数 p q； F 10和 F12分 别 是 一 元 真 值 函 数 q和 p； F11和 F13 分 别 是 二 元 真 值 函 数 qp和 pq。 第 1章 命 题 逻 辑 1.如 果则的 否 定 “ ” 设 p、 q为 任 意 两 个 命 题 ， 复 合 命 题 “ 如 果 p则 q的否 定 ” 称 为 p、 q蕴 含 的 否 定 ， 记 作 ： p q 。“ ” 称 为 蕴 含 的 否 定 联 结 词 。 p q为 真 ， 当且 仅 当 p为 真 ， q为 假 。 由 上 面 所 述 可 知 ， F2是 二 元 真 值 函 数 p q。)( qpqp 第 1章 命 题 逻 辑 2.异 或 （ 排 斥 或 ） “ ” 设 p、 q为 任 意 两 个 命 题 ， 复 合 命 题 “ p异 或 q”称 为 p、q的 异 或 （ 排 斥 或 ） ， 记 作 ： p q。 “ ” 称 为 异 或（ 排 斥 或 ） 联 结 词 。 p q为 真 ， 当 且 仅 当 p、 q中 恰 有 一个 为 真 。 由 表 1.4.1和 前 面 所 述 可 知 ， F6是 二 元 真 值 函 数 p q。 )()()()()( qpqpqpqpqpqp )()( )()( )()( )()( )()()( qpqp pqqp pqqp pqqp pqqpqp 证 ： 等 价 等 值 式德 摩 根 律蕴 含 等 值 式德 摩 根 律交 换 律 第 1章 命 题 逻 辑(1)(2) ( ) ( )(3) ( ) ( )(4) 0 (5) 0(6) 1 A B B AA B C A B CA B C A BA AA AA A (A C)【 例 1.4.1】 用 真 值 表 证 明 )()( CBACBA 联 结 词 “ ” 有 以 下 性 质 ： 第 1章 命 题 逻 辑【 例 1.4.2】 用 等 值 演 算 证 明 )()()( CABACBA )()( )()(0 )()()( )()( )()()()( )()( )()()( CBCBA CBCBA CBCBAACBA CBACBA CABACABA CABA CBCBACBA 真 值 函 数 F6真 值 函 数 F6分 配 、 德 摩 根分 配矛 盾 、 零 律同 一 律 第 1章 命 题 逻 辑 3.与 非 “ ” 设 p、 q为 任 意 两 个 命 题 ， 复 合 命 题 “ p与 q的 否 定 ” 称 为 p、 q的 与 非 ， 记 作 ： pq。 “ ”称 为 与 非 联 结 词 。 pq为 假 ， 当 且 仅 当 p、 q均为 真 。 由 定 义 可 知 ， F14是 二 元 真 值 函 数 pq。( ) p q p q性 质 ： （ pq） r p（ qr） 第 1章 命 题 逻 辑证 明 ： 因 为 ( ) ( ) p q r p q r所 以 )( )( )()( )( )( )()( rqp rqp rqprqp rqp rqp rqprqp ( ) ( ) p q r p q r 第 1章 命 题 逻 辑 【 例 1.4.3】 将 下 列 公 式 化 成 仅 含 联 结 词 “ ”的 公 式 。 (1)(2)(3) A pB p qC p q解 (1) ( )(2) ( ) ( ) ( ) ( ) (3) ( ) ( ) ( ) A p p q p pB p q p q p q p q p qC p q p q p q p q q q 第 1章 命 题 逻 辑 4.或 非 “ ” 设 p、 q为 任 意 两 个 命 题 ， 复 合 命 题 “ p或 q的否 定 ” 称 为 p、 q的 或 非 ， 记 作 ： pq。 “ ”称 为或 非 联 结 词 。 pq为 真 ， 当 且 仅 当 p、 q均 为 假 。 由 定 义 可 知 ， F8是 二 元 真 值 函 数 pq。 pq （ p q） 类 似 于 “ ”， “ ”同 样 不 满 足 结 合 律 ， 并 类似 可 将 例 1.4.3中 的 公 式 化 成 仅 含 联 结 词 “ ”的 公式 。 第 1章 命 题 逻 辑 【 例 1.4.4】 将 公 式 p （ q r） 化 成 仅 含联 结 词 、 的 公 式 形 式 。 （ 等 价 等 值 式 ）（ 蕴 涵 等 值 式 ） （ 德 摩 根 律 ） （ 双 重 否 定 律 ） )()( )()( )()( )()( )( qrrqp qrrqp qrrqp qrrqp rqp 第 1章 命 题 逻 辑 【 例 1.4.5】 将 公 式 pq化 成 仅 含 联 结 词 、 的 公 式 形 式 。解 )()( )()( )( )( )( )( qppqpp qpqp qp qp qpqp qqp qp qp qpqp 第 1章 命 题 逻 辑 1.5 对 偶 与 范 式 在 1.3节 中 介 绍 的 基 本 等 值 式 中 ， 多 数 公 式 是成 对 出 现 的 ， 这 些 成 对 出 现 的 公 式 是 对 偶 的 。 定 义 1.5.1 在 仅 含 联 结 词 、 、 的 命 题公 式 A中 ， 将 换 成 ， 将 换 成 ， 若 A中 含 有0或 1， 则 将 0换 成 1， 1换 成 0， 所 得 命 题 公 式 称 为A的 对 偶 式 ， 记 作 A*。由 定 义 易 知 ， 对 偶 式 是 相 互 的 ， (A*)*=A， 我 们 称 A与 A*是 对 偶 的 。 第 1章 命 题 逻 辑 例 如 ：(1) ( ) 1 ( ) 0(2) ( ) ( ) ( ) ( ) p q r p q rp q q r p q q r与 与 互 为 对 偶 式 。 是 对 偶 的 。 第 1章 命 题 逻 辑 定 理 1.5.1 设 A与 A*是 对 偶 的 ， p1,p2,， pn是出 现 在 A、 A*中 的 所 有 命 题 变 元 ， 则 A（ p1， p2， , pn） A*（ p1， p2， ， pn） （ 1） A（ p1， p2， ， pn） A*（ p1， p2， ， p n） （ 2） 第 1章 命 题 逻 辑 定 理 1.5.2 设 A*、 B*分 别 是 公 式 A、 B的 对偶 式 ， 如 果 A B， 则 A* B*。 -对 偶 定 理 证 明 设 A、 B中 所 有 不 同 的 变 元 为 p1， p2， ， pn， 则 由 A B知 ： A（ p1， p2， ， pn) B（ p1， p2， ， pn） 是 永 真 式 ， A（ p 1， p2， ， pn） B（ p1， p2， ， pn） 亦 是 永 真 式 。 所 以 ， 1 2 1 2( , , , ) ( , , , )n nA p p p B p p p 第 1章 命 题 逻 辑 定 义 1.5.2 将 命 题 变 元 及 其 否 定 统 称 为 文 字 。 简 单 析 取 式 （ 基 本 和 ） 仅 由 有 限 个 文 字 构成 的 析 取 式 。 简 单 合 取 式 （ 基 本 积 ） 仅 由 有 限个 文 字 构 成 的 合 取 式 。 例 如 ， p、 q既 是 一 个 文 字 的 简 单 析 取 式 ， 又 是 一 个 文 字 的 简 单 合 取 式 。 p q、 p r均 是 有 两 个 文 字 的 简 单 析 取 式 。 p q r、 p q q均 是 有 三 个 文 字 的 简 单 合取 式 。 第 1章 命 题 逻 辑性 质 (1) 一 个 文 字 既 是 简 单 析 取 式 又 是 简 单 合 取 式 。 (2) 一 个 简 单 析 取 式 是 重 言 式 ， 当 且 仅 当 它 同 时含 有 一 个 命 题 变 元 及 其 否 定 。 (3) 一 个 简 单 合 取 式 是 矛 盾 式 ， 当 且 仅 当 它 同 时含 有 一 个 命 题 变 元 及 其 否 定 。 例 如 ， p q p是 重 言 式 ， p q q是 矛 盾式 。 第 1章 命 题 逻 辑 定 义 1.5.3 析 取 范 式 由 有 限 个 简 单 合 取 式 构 成 的 析 取式 。 合 取 范 式 由 有 限 个 简 单 析 取 式 构 成 的 合 取式 。 第 1章 命 题 逻 辑【 例 1.5.1】 判 断 下 列 各 式 是 析 取 范 式 还 是 合 取 范式 。 （ 1） p（ 2） p q（ 3） p q r（ 4） p （ q r） r（ 5） p （ p q） （ p q r） q 第 1章 命 题 逻 辑 解 : （ 1） 既 是 一 个 简 单 析 取 式 又 是 一 个 简 单 合 取 式 ， 是只 有 一 个 简 单 析 取 式 的 合 取 范 式 ， 也 是 只 有 一 个 简 单合 取 式 的 析 取 范 式 。 （ 2） 是 有 两 个 简 单 合 取 式 的 析 取 范 式 ， 也 是 只 有 一 个简 单 析 取 式 的 合 取 范 式 。 （ 3） 是 有 三 个 简 单 析 取 式 的 合 取 范 式 ， 也 是 只 有 一 个简 单 合 取 式 的 析 取 范 式 。 （ 4） 是 有 三 个 简 单 合 取 式 的 析 取 范 式 。 （ 5） 是 有 四 个 简 单 析 取 式 的 合 取 范 式 。 第 1章 命 题 逻 辑 性 质 ： (1) 一 个 文 字 既 是 一 析 取 范 式 又 是 一 合 取 范 式 。 (2) 一 个 析 取 范 式 为 矛 盾 式 ， 当 且 仅 当 它 的 每 个 简 单合 取 式 是 矛 盾 式 。 (3) 一 个 合 取 范 式 为 重 言 式 ， 当 且 仅 当 它 的 每 个 简 单析 取 式 是 重 言 式 。 例 如 ： A=（ p p q） （ p q q） 是 矛 盾 式 。 A=（ p p q） （ p q q） （ q r r） 是 重 言 式 。 第 1章 命 题 逻 辑 定 理 1.5.3 任 一 命 题 公 式 都 存 在 着 与 之 等 值 的析 取 范 式 ， 任 一 命 题 公 式 都 存 在 着 与 之 等 值 的 合取 范 式 。 证 明 对 于 任 一 公 式 ， 可 用 下 面 的 方 法 构 造 出与 其 等 值 的 范 式 ： （ 1） 利 用 等 值 式 A B (AB） （ BA） AB A B使 公 式 中 仅 含 联 结 词 、 、 。 第 1章 命 题 逻 辑 （ 2） 利 用 德 摩 根 律 和 双 重 否 定 律 （ A B） A B （ A B） A B A A 将 否 定 符 移 至 命 题 变 元 符 前 ， 并 去 掉 多 余 的 否定 符 。 第 1章 命 题 逻 辑 （ 3） 利 用 分 配 律 A （ B C) （ A B） （ A C） A （ B C） （ A B） （ A C）将 公 式 化 成 析 取 范 式 或 合 取 范 式 。 所 得 即 与 原 公式 等 值 的 范 式 。 第 1章 命 题 逻 辑【 例 1.5.2】 求 公 式 （ （ p q） r） p的 析 取 范 式 。 解 ( ) )( ) ) ) ( ( ) )( ( ( ) ) ( ( ) )( ( ) ) ( ( ) )( ) ) ( )( ) ( ) ( ) ( ) ) ( ) ( )( ( ) ( )P q r pp q r p p p q rp q r p p p q rp q r p p p q rp q r p p rp r q r p p rp r p q r p rp q r p r （ 消 ）（ 消 ） （ 德 摩 根 律 ）（ 分 配 律 ） （ 交 换 律 ） （ 吸 收 律 ） （ 双 重 否 定 律 、 吸 收 律 ） 第 1章 命 题 逻 辑( ( ) ( ) ( )( ) ( ) ( ) ( )0 ( ) ( ) 0( ) ( )p p r q p rp r p r q r p q r rp r p q rp r p q r （ 分 配 律 ） （ 分 配 律 ）（ 矛 盾 式 ）（ 同 一 律 ） -析 取 范 式 事 实 上 ， 第 *步 已 经 是 析 取 范 式 了 ， 最 后 是 化 简 了的 结 果 。 这 说 明 一 个 公 式 的 析 取 范 式 不 是 唯 一 的 。 第 1章 命 题 逻 辑 【 例 1.5.3】 求 例 1.5.2中 公 式 的 合 取 范 式 。 解 由 例 1.5.2第 4步原 式 ( ) ) ) ( )( ) ( ) ( )( ) ( ) ( )p q r p p rp q p r p p rp q p r p r （ 分 配 律 ） -合 取 范 式 （ 幂 等 律 、 交 换 律 ） 第 1章 命 题 逻 辑 定 义 1.5.3 对 于 公 式 A： 极 小 项 包 含 A中 所 有 命 题 变 元 或 其 否 定 一次 且 仅 一 次 的 简 单 合 取 式 ； 极 大 项 包 含 A中 所 有 命 题 变 元 或 其 否 定 一次 且 仅 一 次 的 简 单 析 取 式 。 注 极 小 项 或 极 大 项 中 各 文 字 要 求 按 角 标 顺序 或 字 典 顺 序 排 列 。 第 1章 命 题 逻 辑 【 例 1.5.4】 求 公 式 A（ p， q） 的 极 小 项 和 极 大 项 。 解 极 小 项 ： p q、 p q、 p q、 p q 极 大 项 ： p q 、 p q、 p q、 p q 即 极 小 （ 大 ） 项 的 个 数 等 于 22个 。 （ n元 的 公 式 为2 n个