《離散數(shù)學(xué)講義》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)講義（212頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 2 離 散 數(shù) 學(xué) （ 第 三 版 ） ， 耿 素 云 等 編 著 清 華 大 學(xué) 出 版 社 ， 2004年 3月（ 1） 離 散 數(shù) 學(xué) (第 二 版 ) 及 其 配 套 參 考 書 離 散 數(shù) 學(xué) 題 解 作 者 ： 屈 婉 玲 ， 耿 素 云 ， 張 立 昂 清 華 大 學(xué) 出 版 社（ 2） 離 散 數(shù) 學(xué) 焦 占 亞 主 編 電 子 工 業(yè) 出 版 社 2005年 1月 3 選 修 課 /必 修 課 ：周 學(xué) 時 ：上 課 周 ：總 學(xué) 時 ： 4 第 一 篇 數(shù) 理 邏 輯 （ 14學(xué) 時 ）第 一 章 命 題 邏 輯 （ 8）第 二 章 謂 詞 邏 輯 （ 6）第 二 篇 集

2、 合 論 （ 12學(xué) 時 ）第 三 章 集 合 （ 4）第 四 章 二 元 關(guān) 系 與 函 數(shù) （ 8）第 四 篇 圖 論 （ 14學(xué) 時 ）第 七 章 圖 論 （ 8）第 八 章 一 些 特 殊 圖 （ 4）第 九 章 樹 （ 2） 5考 核 方 式 ：閉 卷 筆 試 第 四 篇 代 數(shù) 系 統(tǒng) （ 8學(xué) 時 ）第 5、 6章 圖 論 （ 8） 6 （ 1） 上 課 認 真 聽 講（ 2） 課 后 及 時 復(fù) 習(xí)（ 3） 獨 立 、 認 真 地 完 成 作 業(yè)（ 4） 有 問 題 及 時 提 出 ， 不 要 積 累 問 題 7 是 研 究 離 散 對 象 和 它 們 之 間 的 關(guān) 系 的

3、現(xiàn) 代 數(shù) 學(xué) 。 它 為 計 算 機 科 學(xué) 中 的 數(shù) 據(jù) 結(jié) 構(gòu) 、 編 譯 理 論 、 操 作 系 統(tǒng) 、 算 法 分 析 、 人 工 智 能 等 提 供 了 必 要 的 數(shù) 學(xué) 知 識 。其 內(nèi) 容 較 廣 ， 主 要 包 括 數(shù) 理 邏 輯 、 集 合論 、 圖 論 、 代 數(shù) 結(jié) 構(gòu) 等 四 個 基 本 部 分 。 8 離 散 數(shù) 學(xué) 將 日 常 的 概 念 、 判 斷 、推 理 用 數(shù) 學(xué) 符 號 來 表 示 ， 用 數(shù) 學(xué) 方 法進 行 思 維 。 其 目 標 是 掌 握 嚴 密 的 思 維方 法 、 嚴 格 證 明 的 推 理 能 力 和 演 算 能力 ， 掌 握 處 理

4、各 種 具 有 離 散 結(jié) 構(gòu) 的 事物 的 描 述 工 具 與 方 法 ， 適 應(yīng) 學(xué) 習(xí) 其 他專 業(yè) 課 程 的 各 種 需 要 ， 為 學(xué) 習(xí) 其 它 計算 機 課 程 提 供 必 要 的 數(shù) 學(xué) 工 具 。 9 本 課 程 將 學(xué) 習(xí) 數(shù) 理 邏 輯 、 集 合 論 以及 圖 論 、 代 數(shù) 系 統(tǒng) 的 部 分 內(nèi) 容 。 數(shù) 理 邏 輯 的 重 點 是 公 式 演 算與 推 理 證 明 ； 集 合 論 的 重 點 是 關(guān) 系理 論 與 映 射 的 描 述 ； 圖 論 則 著 重 于討 論 結(jié) 點 之 間 的 關(guān) 系 以 及 圖 論 方 法的 各 種 實 際 應(yīng) 用 。 10 第 一

5、 篇 數(shù) 理 邏 輯 11 數(shù) 理 邏 輯 是 用 數(shù) 學(xué) 方 法 來 研 究 推 理過 程 的 科 學(xué) 。 主 要 是 指 引 進 一 套 符號 體 系 的 方 法 ， 因 此 數(shù) 理 邏 輯 一 般又 叫 符 號 邏 輯 ?；?本 內(nèi) 容 是 ： 命 題 邏 輯 （ 演 算 ） 和謂 詞 邏 輯 （ 演 算 ） 。 12 命 題 演 算 是 數(shù) 理 邏 輯 的 基 本 組 成 部 分 ， 是 謂 詞 演 算 的 基 礎(chǔ) 。 本 章 包 括 以 下 內(nèi) 容 ：1-1 命 題 及 其 表 示 法1-2 連 結(jié) 詞1-3 命 題 公 式 及 翻 譯1-4 真 值 表 與 等 價 公 式1-5 其

6、 它 連 結(jié) 詞1-6 對 偶 與 范 式1-7 重 言 式 與 蘊 涵 式1-8 推 理 理 論 1-9 應(yīng) 用 13 命 題 ： 能 夠 判 斷 真 假 的 陳 述 語 句 。8 例 ： 中 國 是 一 個 國 家 ，8 9為 素 數(shù) 。原 子 命 題 ： 不 能 分 解 成 更 簡 單 的 陳 述 語句 的 命 題 。復(fù) 合 命 題 ： 由 連 結(jié) 詞 、 標 點 符 號 和 原 子命 題 復(fù) 合 構(gòu) 成 的 命 題 。一 般 用 字 母 “ T” 表 示 “ 真 ” ， “ F” 表 示“ 假 ” 。 也 經(jīng) 常 用 “ 1” 表 示 “ 真 ” ，“ 0” 表 示 “ 假 ” 。1-

7、1 命 題 及 其 表 示 法 14 8習(xí) 慣 上 ， 命 題 用 小 寫 字 母 p， q， r， ，或 用 帶 下 標 小 寫 字 母 表 示 。例 如 ：命 題 p： 中 國 人 們 是 偉 大 的 。命 題 q： 別 的 星 球 上 有 生 物 。命 題 p1： 1+101=102（ 在 十 進 制 或 二 進 制 數(shù) 范 圍 內(nèi) ） 。命 題 P 2： 今 天 下 雨 。命 題 r： 我 去 看 電 影 。 1-1 命 題 及 其 表 示 法 （ 續(xù) ） 15 判 斷 下 列 句 子 哪 些 是 命 題 ？ 地 球 是 圓 的 。 2+3=5 2+3=6 你 會 講 英 語 嗎 ？

8、3-x=5 是 命 題 ， 真 值 為 T是 命 題 ， 真 值 為 T是 命 題 ， 真 值 為 F不 是 命 題 （ 疑 問 句 不 是 命 題 ） 。不 是 命 題 ， 它 的 真 值 不 確 定 。1-1 命 題 及 其 表 示 法 （ 續(xù) ） 16 判 斷 下 列 句 子 哪 些 是 命 題 （ 續(xù) ） ？ 請 關(guān) 上 門 ！ 除 地 球 外 的 星 球 有 生 物 。 太 陽 明 天 會 出 來 。 不 是 命 題 ， 祈 使 句 不 是 命 題 。是 命 題 ， 它 的 真 值 是 唯 一 確定 的 ， 只 是 目 前 人 們 不 知 道是 命 題 ， 它 的 真 值 是 唯 一

9、 確定 的 ， 到 明 天 就 知 道 了 。再 次 注 意 ： 命 題 是 具 有 唯 一 真 值 的 陳 述 句 。1-1 命 題 及 其 表 示 法 （ 續(xù) ） 17 我 正 在 說 謊悖 論 (paradox)是 一 種 矛 盾 命 題 。 悖 論 是 自 相 矛 盾 的 命 題 。即 如 果 承 認 這 個 命 題 成 立 ， 就 可 推 出 它 的 否 定 命 題 成 立 ；反 之 ， 如 果 承 認 這 個 命 題 的 否 定 命 題 成 立 ， 又 可 推 出 這 個命 題 成 立 。paradox來 自 希 臘 語 “ para+dokein”， 意 思 是 “ 多 想 一想

10、 ” 。悖 論 是 屬 于 領(lǐng) 域 廣 闊 、 定 義 嚴 格 的 數(shù) 學(xué) 分 支 的 一 個 組 成 部分 ， 這 一 分 支 以 “ 趣 味 數(shù) 學(xué) ” 知 名 于 世 。 這 就 是 說 它 帶 有強 烈 的 游 戲 色 彩 。 然 而 ， 切 莫 以 為 大 數(shù) 學(xué) 家 都 看 不 起 “ 趣味 數(shù) 學(xué) ” 問 題 。 歐 拉 就 是 通 過 對 bridge-crossing之 謎 的 分析 打 下 了 拓 撲 學(xué) 的 基 礎(chǔ) 。 萊 布 尼 茨 也 寫 到 過 他 在 獨 自 玩 插棍 游 戲 （ 一 種 在 小 方 格 中 插 小 木 條 的 游 戲 ） 時 分 析 問 題 的樂

11、 趣 。 18 希 爾 伯 特 證 明 了 切 割 幾 何 圖 形 中 的 許 多 重 要 定 理 。 馮 紐曼 奠 基 了 博 弈 論 。 最 受 大 眾 歡 迎 的 計 算 機 游 戲 生 命 是 英國 著 名 數(shù) 學(xué) 家 康 威 發(fā) 明 的 。 愛 因 斯 坦 也 收 藏 了 整 整 一 書 架關(guān) 于 數(shù) 學(xué) 游 戲 和 數(shù) 學(xué) 謎 的 書 。古 今 中 外 有 不 少 著 名 的 悖 論 ， 它 們 震 撼 了 邏 輯 和 數(shù) 學(xué) 的 基礎(chǔ) ， 激 發(fā) 了 人 們 求 知 和 精 密 的 思 考 ， 吸 引 了 古 往 今 來 許 多思 想 家 和 愛 好 者 的 注 意 力 。 解

12、決 悖 論 難 題 需 要 創(chuàng) 造 性 的 思考 ， 悖 論 的 解 決 又 往 往 可 以 給 人 帶 來 全 新 的 觀 念 。 19 例 如 比 較 有 名 的 理 發(fā) 師 悖 論 ： 某 鄉(xiāng) 村 有 一 位 理 發(fā) 師 ， 一 天他 宣 布 ： 只 給 不 自 己 刮 胡 子 的 人 刮 胡 子 。 這 里 就 產(chǎn) 生 了 問題 ： 理 發(fā) 師 給 不 給 自 己 刮 胡 子 ？ 如 果 他 給 自 己 刮 胡 子 ， 他就 是 自 己 刮 胡 子 的 人 ， 按 照 他 的 原 則 ， 他 不 能 給 自 己 刮 胡子 ； 如 果 他 不 給 自 己 刮 胡 子 ， 他 就 是 不

13、自 己 刮 胡 子 的 人 ，按 照 他 的 原 則 ， 他 就 應(yīng) 該 給 自 己 刮 胡 子 。 這 就 產(chǎn) 生 了 矛 盾歷 史 上 著 名 的 悖 論 NO.1說 謊 者 悖 論 (1iarparadoxorEpimenidesparadox)最 古 老 的 語 義 悖 論 。 公 元 前 6世 紀 古 希 臘 哲 學(xué) 家 伊 壁 孟 德 所 創(chuàng) 的 四 個 悖 論 之 一 。 是 關(guān) 于 “ 我 正 在 撒 謊 ” 的 悖 論 。 具體 為 ： 如 果 他 的 確 正 在 撒 謊 ， 那 么 這 句 話 是 真 的 ， 所 以 伊壁 孟 德 不 在 撤 謊 ， 如 果 他 不 在 撒

14、 謊 ， 那 么 這 句 話 是 假 的 ，因 而 伊 壁 孟 德 正 在 撒 謊 。 20 NO.2伊 勒 克 特 拉 悖 論 (Eletraparadox)邏 輯 史 上 最 早 的 內(nèi) 涵 悖論 。 由 古 希 臘 斯 多 亞 學(xué) 派 提 出 。 它 的 基 本 內(nèi) 容 是 ： 伊 勒 克特 拉 有 位 哥 哥 奧 列 斯 特 回 家 了 盡 管 伊 勒 支 持 拉 知 道 奧 列斯 特 是 她 的 哥 哥 但 她 并 不 認 識 站 在 她 面 前 的 這 個 男 人 。 寫 成 一 個 推 理 即 ： 伊 勒 克 持 拉 不 知 道 站 在 她 面 前 的 這 個 人 是 她 的 哥

15、 哥 。 伊 勒 克 持 拉 知 道 奧 列 期 特 是 她 的 哥 哥 。 站 在 她 面 前 的 人 是 奧 列 期 特 。 所 以 ， 伊 勒 克 持 拉 既 知 道 并 且 又 不 知 道 這 個 人 是 她 的 哥 哥 。 21 NO.3M： 著 名 的 理 發(fā) 師 悖 論 是 伯 特 納 德 羅 素 提 出 的 。 一 個 理 發(fā)師 的 招 牌 上 寫 著 ： 告 示 ： 城 里 所 有 不 自 己 刮 臉 的 男 人 都 由 我 給 他 們 刮 臉 ， 我也 只 給 這 些 人 刮 臉 。 M： 誰 給 這 位 理 發(fā) 師 刮 臉 呢 ？ M： 如 果 他 自 己 刮 臉 ， 那

16、 他 就 屬 于 自 己 刮 臉 的 那 類 人 。 但是 ， 他 的 招 牌 說 明 他 不 給 這 類 人 刮 臉 ， 因 此 他 不 能 自 己 來刮 。 M： 如 果 另 外 一 個 人 來 給 他 刮 臉 ， 那 他 就 是 不 自 己 刮 臉 的人 。 但 是 ， 他 的 招 牌 說 他 要 給 所 有 這 類 人 刮 臉 。 因 此 其 他任 何 人 也 不 能 給 他 刮 臉 。 看 來 ， 沒 有 任 何 人 能 給 這 位 理 發(fā)師 刮 臉 了 ！ 22 NO.4唐 吉 訶 德 悖 論 M： 小 說 唐 吉 訶 德 里 描 寫 過 一 個 國 家 它 有 一 條 奇 怪的

17、法 律 ： 每 一 個 旅 游 者 都 要 回 答 一 個 問 題 。 問 ， 你 來 這 里 做 什 么 ？ M： 如 果 旅 游 者 回 答 對 了 。 一 切 都 好 辦 。 如 果 回 答 錯 了 ，他 就 要 被 絞 死 。 M： 一 天 ， 有 個 旅 游 者 回 答 旅 游 者 ： 我 來 這 里 是 要 被 絞 死 。 M： 這 時 ， 衛(wèi) 兵 也 和 鱷 魚 一 樣 慌 了 神 ， 如 果 他 們 不 把 這 人絞 死 ， 他 就 說 錯 了 ， 就 得 受 絞 刑 。 可 是 ， 如 果 他 們 絞 死 他 ，他 就 說 對 了 ， 就 不 應(yīng) 該 絞 死 他 。 23 下

18、 一 句 話 是 真 的 ；上 一 句 話 是 假 的 。命 題 常 項 （ 常 元 ） ： 具 有 唯 一 真 值 的 命 題 ；命 題 變 項 （ 變 元 ） ： 泛 指 任 意 一 個 命 題 或 者 類 似 x+y5根 據(jù) 條 件 不 同 真 值 不 同 的 命 題 。注 意 ： 命 題 變 項 不 是 命 題 ， 它 不 具 有 唯 一 真 值 24 1-2 聯(lián) 結(jié) 詞1、 否 定設(shè) P為 一 命 題 ， 則 新 命 題 “ P是 不 對 的 ” 稱為 P的 否 定 。 記 作 ： P如 ： P： 2是 常 數(shù) 。 P： 2不 是 常 數(shù) 。Q： 今 天 是 星 期 四 。 Q： 今

19、 天 不 是 星 期 四 。 P與 P的 真 值 關(guān) 系 ： 10 P0 1 P 25 1-2 聯(lián) 結(jié) 詞 （ 續(xù) ）2、 合 取設(shè) P， Q是 兩 命 題 ， 新 命 題 “ P并 且 Q”稱 為 命 題 P，Q的 合 取 。 記 作 ： P Q如 ： P： 北 京 是 中 國 的 首 都 。 Q： 北 京 是 一 個 古 都 。 P Q： 北 京 是 中 國 的 首 都 并 且 是 一 個 古 都 。 0 0 0 0 0 1 0 1 P Q 1 0 1 1 P Q P Q的 真 值 關(guān) 系 ： 26 1-2 聯(lián) 結(jié) 詞 （ 續(xù) ）3、 析 取設(shè) P， Q為 兩 個 命 題 ， 則 新 命

20、題 “ P或 者 Q”稱 為 命 題 P，Q的 析 取 。 記 作 ： P Q如 ： P： 北 京 是 中 國 的 首 都 。 Q： 北 京 是 一 個 故 都 。 P Q： 北 京 是 中 國 的 首 都 或 者 是 一 個 故 都 。規(guī) 定 ： P Q的 真 值 為 1當 且 僅 當 P， Q中 至 少 有 一 個真 值 為 1。 P Q的 真 值 關(guān) 系 ： 0 0 0 1 0 1 1 1 P Q 1 0 1 1 P Q 27 1-2 聯(lián) 結(jié) 詞 （ 續(xù) ）注 意 ： 析 取 聯(lián) 結(jié) 詞 與 漢 語 中 的 “ 或 ” 的 意 義 不 完 全 相 同 。 漢 語 中 的 “ 或 ” 既

21、可 以 表 示 “ 排 斥 或 ” ， 也 可 以 表 示 “ 可 兼 或 ” 。例 如 ：P： 今 天 晚 上 我 在 家 看 電 視 或 去 劇 場 看 戲 。Q： 他 可 能 是 100米 或 400米 賽 跑 的 冠 軍 。 “排 斥 或 ” “可 兼 或 ” 28 1-2 聯(lián) 結(jié) 詞 （ 續(xù) ）4、 條 件設(shè) P， Q是 兩 命 題 ， 其 條 件 命 題 是 一 個 復(fù) 合 命 題 ， 記 做 PQ，讀 做 “ 如 果 P， 則 Q”。 1 1 0 1P Q 0 0 0 1 1 0 1 1 P Q真 值 關(guān) 系 ： “善 意 的 推 定 ” 29 1-2 聯(lián) 結(jié) 詞 （ 續(xù) ）5、

22、 雙 條 件設(shè) P， Q是 兩 命 題 ， 其 雙 條 件 命 題 是 一 個 復(fù) 合 命 題 ，記 做 PQ， 讀 做 “ 如 果 P， 則 Q”。真 值 關(guān) 系 ： 1 0 0 1 0 0 0 1 1 0 1 1 P Q PQ 30 1-2 聯(lián) 結(jié) 詞 （ 續(xù) ）在 命 題 演 算 中 ， 五 個 聯(lián) 結(jié) 詞 的 含 義 由 真 值 表 唯 一 確 定 。 T T F TP Q F F F T T F T T P Q F T T TP Q F F F T T F T T P Q F F F F F T F T P Q T F T T P Q T F PF T P T F F T F F F

23、 T T F T T P Q PQ 31 1-3 命 題 公 式 及 其 賦 值定 義 ： 合 式 公 式 （ 1） 單 個 命 題 變 元 本 身 是 一 個 合 式 公 式 。 （ 2） 如 果 A是 一 個 合 式 公 式 ， 那 么 A是 合 式 公 式 。 （ 3） 如 果 A、 B是 合 式 公 式 ， 那 么 （ AB） 、 （ AB） 、 （ AB） 、 （ AB） 都 是 合 式 公 式 。 （ 4） 當 且 僅 當 能 夠 有 限 次 地 應(yīng) 用 上 面 （ 1） 、 （ 2） 、 （ 3） 所 得 到 的 包 含 命 題 變 元 、 聯(lián) 結(jié) 詞 合 括 號 的 符 號 串

24、 是 合 式 公 式 。 遞 歸 定 義基 礎(chǔ)歸 納界 限 32 1-3 命 題 公 式 及 其 賦 值 （ 續(xù) ）例 如 ： 合 式 公 式 ：(PQ),(PQ)(P(PQ)(PQ)(QR)(ST)非 合 式 公 式 ：(PQ)(Q) (PQ (PQ)Q) 括 號 不 匹 配括 號 不 匹 配應(yīng) 是 雙 目 運 算 符 33 1-3 命 題 公 式 及 翻 譯聯(lián) 結(jié) 詞 的 運 算 優(yōu) 先 級 ：高 低 命 題 公 式 的 層 （ 描 述 公 式 的 復(fù) 雜 程 度 ） 命 題 公 式 的 賦 值 （ 解 釋 、 翻 譯 ） 真 值 表 34 1-3 命 題 公 式 及 翻 譯 （ 續(xù) ）請

25、 看 教 材 Page 10-11。例 題 1： 我 們 要 做 到 身 體 好 、 學(xué) 習(xí) 好 、 工 作 好 ， 為 祖 國 的 四 化 建 設(shè) 而 奮 斗 。解 找 出 原 子 命 題 ： A： 我 們 要 做 到 身 體 好 。 B： 我 們 要 做 到 學(xué) 習(xí) 好 。 C： 我 們 要 做 到 工 作 好 。 P； 我 們 要 為 祖 國 的 四 化 建 設(shè) 而 奮 斗 。命 題 的 形 式 化 描 述 ： (A B C) P。 35 1-3 命 題 公 式 及 翻 譯 （ 續(xù) ）例 題 2： 上 海 到 北 京 的 14次 列 車 是 下 午 五 點 半 或 六 點 開 。解 找

26、出 原 子 命 題 ： P： 上 海 到 北 京 的 14次 列 車 是 下 午 五 點 半 開 。 Q： 上 海 到 北 京 的 14次 列 車 是 下 午 六 點 開 。排 斥 或 ： （ P Q） （ P Q） P Q 原 命 題 P Q PQ (PQ)T T F T T FT F T T F TF T T T F TF F F F T F命 題 的 形 式 化 描 述 ： (PQ)。 36 1-3 命 題 公 式 及 翻 譯 （ 續(xù) ）例 題 3： （ 自 學(xué) ）例 題 4： （ 自 學(xué) ）例 題 5： （ 自 學(xué) ）例 題 6： （ 自 學(xué) ） 37 習(xí) 題 ： * 各 章 節(jié) 后

27、習(xí) 題 中 的 雙 號 大 題 中 的 雙號 小 題 。 38 1-4 真 值 表 與 等 價 公 式 定 義 ： 在 命 題 公 式 中 ， 對 于 分 量 指 派 真 值 的 各 種 可 能 組 合 ，就 確 定 了 這 個 命 題 公 式 的 各 種 真 值 情 況 ， 把 它 們 匯 列 成 表 ，就 是 命 題 公 式 的 真 值 表 。含 n個 命 題 變 元 的 命 題 公 式 ， 共 有 2n組 賦 值 。例 題 1： PQ的 真 值 表 。 P Q P PQ0 0 1 10 1 1 11 0 0 01 1 0 1 39 1-4 真 值 表 與 等 價 公 式 （ 續(xù) ）例 題

28、 2： (PQ) P的 真 值 表 。P Q PQ P (PQ) P0 0 0 1 00 1 0 1 01 0 0 0 01 1 1 0 0例 題 3： (PQ) v(PQ)的 真 值 表 。 P Q P Q PQ PQ (PQ)v(PQ)0 0 1 1 0 1 10 1 1 0 0 0 01 0 0 1 0 0 01 1 0 0 1 1 1 永 假公 式 40 1-4 真 值 表 與 等 價 公 式 （ 續(xù) ）例 題 4： (PQ)(PQ)的 真 值 表 。P Q PQ (PQ) P Q PvQ (PQ)(PvQ)0 0 0 1 1 1 1 10 1 0 1 1 0 1 11 0 0 1 0

29、 1 1 11 1 1 0 0 0 0 1 永 真公 式 41 1-4 真 值 表 與 等 價 公 式 （ 續(xù) ）定 義 ： 給 定 兩 個 命 題 公 式 A和 B， 設(shè) P1， P2， ， Pn， 為所 有 出 現(xiàn) 在 A和 B中 的 原 子 變 元 。 若 給 P1， P2， ， Pn任意 一 組 真 值 指 派 ， A和 B的 真 值 都 相 同 ， 則 稱 A和 B是 等 價（ 或 邏 輯 相 等 ） ， 記 做 AB。 例 題 5： 證 明 PQ (PQ)(QP) 。P Q PQ PQ QP (PQ)(QP) 0 0 1 1 1 10 1 0 1 0 01 0 0 0 1 01 1

30、 1 1 1 1 42 1-4 真 值 表 與 等 價 公 式 （ 續(xù) ）兩 個 公 式（ 1） P Q PQP Q P P Q PQ0 0 1 1 10 1 1 1 11 0 0 0 01 1 0 1 1（ 2） (P Q) (P Q) PQ P Q P Q P Q P Q (P Q) (P Q) PQ0 0 1 1 0 1 1 10 1 1 0 0 0 0 01 0 0 1 0 0 0 01 1 0 0 1 0 1 1 43 1-4 真 值 表 與 等 價 公 式 （ 續(xù) ）10個 命 題 定 律 ：序 號 定 律 表 達 式1 雙 重 否 定 律 P P2 冪 等 律 PP PPP P3

31、 結(jié) 合 律 (P Q) R P (Q R)(P Q) R P (Q R)4 交 換 律 P Q Q PP Q Q P5 分 配 律 P (Q R) (P Q) (P R) P (Q R) (P Q) (P R) 44 1-4 真 值 表 與 等 價 公 式 （ 續(xù) ）10個 命 題 定 律 ：序 號 定 律 表 達 式6 吸 收 律 P (P Q) PP (P Q) P7 德 .摩 根 律 (P Q) P Q(P Q) P Q8 同 一 律 P 0 PP 1 P9 零 律 P 1 1P 0 0 10 排 中 律矛 盾 律 P P 1P P 0 45 11 蘊 涵 等 值 式 A B A B1

32、2 等 價 等 值 式 A B (A B) (B A)13 假 言 易 位 A B B A14 等 價 否 定 等值 式 A B A B15 歸 謬 論 (A B) (A B) A1-4 真 值 表 與 等 價 公 式 （ 續(xù) ） 46 1-4 真 值 表 與 等 價 公 式 （ 續(xù) ）例 題 6 驗 證 吸 收 律 ：P (P Q) PP (P Q) PP Q (P Q) P (P Q） (P Q) P (P Q)T T T T T T T F F T T TF T F F T FF F T F F F驗 證 ： 列 出 真 值 表 47 1-4 真 值 表 與 等 價 公 式 定 義 ：

33、如 果 X是 合 式 公 式 A的 一 部 分 ， 且 X本 身 也 是 一 個 合 式公 式 ， 則 稱 X為 公 式 A的 一 個 子 公 式 。例 題 7： 證 明 Q (P (P Q) Q P 。證 明 ： 由 吸 收 律 ， (P (P Q) P 因 此 ， 根 據(jù) 上 面 的 定 理 ， 有Q (P (P Q) Q P 。證 畢 。 此 定 理 也 稱 為 置 換 定 理 定 理 ： 設(shè) X是 合 式 公 式 A的 子 公 式 ， 若 X Y， 如 果 將 A中 的X用 Y來 置 換 ， 則 所 得 到 的 公 式 B與 公 式 A等 價 ， 即 A B。 48 1-4 真 值 表

34、 與 等 價 公 式例 題 8 證 明 ： (P Q) (P Q) P 證 ： (P Q) (P Q) P (Q Q) 分 配 律 P 1 否 定 律 P 同 一 律 49 1-4 真 值 表 與 等 價 公 式例 題 9 證 明 ： P (Q R) Q (P R) R (Q P)證 ： P (Q R) P (Q R) 蘊 涵 等 值 式 Q (P R) 結(jié) 合 律 Q (P R) 蘊 涵 等 值 式（ 第 二 個 等 價 公 式 類 似 可 證 。 ） 50 1-5 其 它 連 結(jié) 詞 定 義 ： 設(shè) P和 Q是 兩 個 命 題 公 式 ， 復(fù) 合 命 題 P 、 Q恰 有 一 個 成立 稱

35、 為 P與 Q的 排 斥 或 或 異 或 。 P Q的 真 值 為 T， 當 且 僅 當 P與 Q的 真 值 不 相 同 時 為 T， 否 則 為 F。P Q P QT T FT F TF T TF F F 定 理 ： 設(shè) P,Q,R為 任 意 命 題 公 式 。 如 果 P Q R， 則 P R Q， Q R P,且 P Q R為 一 矛 盾 式 。 51 1-5 其 它 連 結(jié) 詞 定 義 ： 設(shè) P和 Q是 兩 個 命 題 公 式 ， 復(fù) 合 命 題 P Q稱 為 P和 Q的 條 件 否 定 ， P Q的 真 值 為 T， 當 且 僅 當 P的 真 值 為 T， Q的 真 值 為 F；

36、否 則 ， P Q的 真 值 為 為 F。P Q P QT T FT F TF T FF F F 52 1-5 其 它 連 結(jié) 詞 定 義 ： 設(shè) P和 Q是 兩 個 命 題 公 式 ， 復(fù) 合 命 題 PQ稱 為 P和 Q的“ 與 非 ” ， 當 且 僅 當 P和 Q的 真 值 都 為 T時 ， PQ 的 真 值 為F； 否 則 ， PQ的 真 值 為 為 T。P Q PQT T FT F TF T TF F T 53 1-5 其 它 連 結(jié) 詞 定 義 ： 設(shè) P和 Q是 兩 個 命 題 公 式 ， 復(fù) 合 命 題 PQ稱 為 P和 Q的“ 或 非 ” ， 當 且 僅 當 P和 Q的 真

37、值 都 為 T時 ， PQ 的 真 值 為F； 否 則 ， PQ的 真 值 為 為 T。P Q PQT T FT F FF T FF F T 54 1-5 其 它 連 結(jié) 詞 命 題 公 式 ：1 2 3 4 5 6 7 8P Q T F P Q P Q PQ PQT T T F T T F F T FT F T F T F F T F TF T T F F T T F F TF F T F F F T T F T9 10 11 12 13 14 15 16 P Q PQ PQ PQ P Q PQ P Q QP Q PT T T F T F T F T FT F T F F T F T T F

38、F T T F T F F T F TF F F T T F T F T F 55 1-5 其 它 連 結(jié) 詞等 價 公 式 ：1. PQ (PQ) (QP) 2. (PQ) P Q3. P Q (P Q)， P Q (P Q)4. P Q (P Q)5. P Q ( PQ)6. PQ (P Q)7. PQ (P Q)最 小 聯(lián) 結(jié) 詞 組 ： ， 或 ， 或 或 56 回 顧 表 1-4.8的 10個 命 題 定 律 ：序 號 定 律 表 達 式1 對 合 律 P P2 冪 等 律 PP PPP P3 集 合 律 (P Q) R P (Q R)(P Q) R P (Q R)4 交 換 律 P

39、 Q Q PP Q Q P5 分 配 律 P (Q R) (P Q) (P R)P (Q R) (P Q) (P R)1-6 對 偶 與 范 式 57 序 號 定 律 表 達 式6 吸 收 律 P (P Q) PP (P Q) P7 德 .摩 根 律 (P Q) P Q(P Q) P Q8 同 一 律 P F PP T P9 零 律 P T TP F F10 否 定 律 P P TP P F1-6 對 偶 與 范 式 （ 續(xù) ）回 顧 表 1-4.8的 10個 命 題 定 律 ： 58 1-6 對 偶 與 范 式 （ 續(xù) ） 定 義 ： 在 給 定 的 命 題 中 ， 將 聯(lián) 結(jié) 詞 換 成

40、， 將 換 成 ， 若有 特 殊 變 元 F和 T也 相 互 替 代 ， 所 得 公 式 A*稱 為 A的 對 偶 式 。 顯 然 ， A*與 A互 為 對 偶 式 。 例 題 1. 例 題 2. 定 理 ： 設(shè) A*為 A的 對 偶 式 ， P1,P2,Pn是 出 現(xiàn) 在 A和 A*中 的 原 子 變 元 ， 則 A(P1,P2, Pn) A*(P1,P2, Pn) A(P1,P2, Pn) A*(P1,P2, Pn) 59 1-6 對 偶 與 范 式 （ 續(xù) ） 例 題 4： p q 的 對 偶 式 是 p q ; p q 的 對 偶 式 是 p q 永 真 式 的 對 偶 式 是 永 假

41、 式 ， 反 之 亦 然 ；定 理 ： 設(shè) A*為 A的 對 偶 式 ， P1,P2,Pn是 出 現(xiàn) 在 公 式 A和 B中 的 原 子 變 元 ， 如 果 A B， 則 A* B*。 60 1-6 對 偶 與 范 式 （ 續(xù) ）定 義 ： 一 個 命 題 稱 為 合 取 范 式 ， 當 且 僅 當 它 具 有 如 下 的 形式 ：A1A2 An， (n1)其 中 A1,A2,An都 是 由 命 題 變 元 或 其 否 定 所 組 成 的 析 取 式 。定 義 ： 一 個 命 題 稱 為 析 取 范 式 ， 當 且 僅 當 它 具 有 如 下 的 形式 ：A 1A2 An， (n1)其 中 A

42、1,A2,An都 是 由 命 題 變 元 或 其 否 定 所 組 成 的 合 取 式 。注 意 ： 一 個 命 題 的 合 取 范 式 或 析 取 范 式 不 是 唯 一 的 。 61 1-6 對 偶 與 范 式 （ 續(xù) ）求 一 個 命 題 的 合 取 范 式 或 析 取 范 式 的 步 驟 ：(1) 將 公 式 中 的 聯(lián) 結(jié) 詞 化 歸 成 ， 及 。(2) 利 用 德 .摩 根 定 律 將 否 定 聯(lián) 結(jié) 詞 直 接 移 到 各 命 題 變 元之 前 。(3) 利 用 分 配 律 、 結(jié) 合 律 將 公 式 歸 約 為 合 取 范 式 或 析 取 范式 。 62 1-6 對 偶 與 范

43、 式 （ 續(xù) ）定 義 ： n個 命 題 變 元 的 合 取 式 稱 為 布 爾 合 取 （ 或 小 項 ） ， 其中 每 個 變 元 與 它 的 否 定 不 能 同 時 存 在 ， 但 兩 者 必 須 出現(xiàn) 且 僅 出 現(xiàn) 一 次 。例 如 ： 兩 個 變 元 P和 Q， 其 小 項 為 ： PQ， PQ， PQ，PQ。三 個 變 元 P， Q， R的 小 項 為 ： P Q R， P Q R， P Q R， P Q R ， P Q R ，P Q R ， P Q R ， P Q R 。 一 般 說 來 ， n個 命 題 變 元 共 有 2n個 小 項 。 63 1-6 對 偶 與 范 式 （

44、 續(xù) ）兩 個 變 元 P和 Q的 小 項 的 真 值 表 ：P Q PQ PQ PQ PQ1 1 1 0 0 01 0 0 1 0 00 1 0 0 1 00 0 0 0 0 1 64 1-6 對 偶 與 范 式 （ 續(xù) ）三 個 變 元 P， Q， R的 小 項 的 真 值 表 ：P Q R P Q R P Q R P Q R P Q R0 0 0 1 0 0 00 0 1 0 1 0 00 1 0 0 0 1 00 1 1 0 0 0 11 0 0 0 0 0 01 0 1 0 0 0 01 1 0 0 0 0 01 1 1 0 0 0 0 65 1-6 對 偶 與 范 式 （ 續(xù) ）三

45、 個 變 元 P， Q， R的 小 項 的 真 值 表 :P Q R P Q R P Q R P Q R P Q R0 0 0 0 0 0 00 0 1 0 0 0 00 1 0 0 0 0 00 1 1 0 0 0 01 0 0 1 0 0 01 0 1 0 1 0 01 1 0 0 0 1 01 1 1 0 0 0 1 66 1-6 對 偶 與 范 式 （ 續(xù) ）三 個 變 元 P， Q， R的 小 項 的 真 值 表 :P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R0 0 0 1 0 0 0 0 0 0 00 0 1 0 1 0

46、 0 0 0 0 00 1 0 0 0 1 0 0 0 0 00 1 1 0 0 0 1 0 0 0 01 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 01 1 0 0 0 0 0 0 0 1 01 1 1 0 0 0 0 0 0 0 1 67 1-6 對 偶 與 范 式 （ 續(xù) ）三 個 變 元 P， Q， R的 小 項 的 編 碼 表 :m000 P Q Rm001 P Q Rm010 P Q Rm011 P Q Rm100 P Q Rm 101 P Q Rm110 P Q Rm111 P Q R 68 1-6 對 偶 與 范 式 （ 續(xù) ）小 項 的

47、性 質(zhì) :（ 1） 每 一 個 小 項 當 其 真 值 指 派 與 編 碼 相 同 時 ， 其 真 值 為 T，在 其 余 2n-1中 指 派 情 況 下 均 為 F。（ 2） 任 意 兩 個 不 同 小 項 的 合 取 式 為 永 假 。（ 3） 全 體 小 項 的 析 取 式 為 永 真 ， 記 為 ： 2 1 0 1 2 10 .n nii m m m m T 69 1-6 對 偶 與 范 式 （ 續(xù) ）定 義 ： 對 于 給 定 的 命 題 公 式 ， 如 果 有 一 個 等 價 公 式 ， 它 僅由 小 項 的 析 取 所 組 成 ， 則 該 等 式 稱 為 原 式 的 主 析 取

48、范式 。定 理 ： 在 真 值 表 中 ， 一 個 公 式 的 真 值 為 T的 指 派 所 對 應(yīng) 的小 項 的 析 取 ， 即 為 此 公 式 的 主 析 取 范 式 。例 題 6： 給 定 P Q， P Q和 (P Q)， 求 這 些 公 式 的 主析 取 范 式 。例 題 7：例 題 8： 例 題 9： 70 1-6 對 偶 與 范 式 （ 續(xù) ） 對 于 給 定 命 題 公 式 的 主 析 取 范 式 ， 如 果 將 其命 題 變 元 的 個 數(shù) 和 出 現(xiàn) 自 許 固 定 后 ， 則 此 公 式 的主 析 取 范 式 就 是 唯 一 的 。定 義 ： n個 命 題 變 元 的 析

49、取 式 稱 為 布 爾 析 取 或 大 項 。其 中 每 個 變 元 與 它 的 否 定 不 能 同 時 存 在 ， 但兩 者 必 須 且 僅 出 現(xiàn) 一 次 。 71 1-6 對 偶 與 范 式 （ 續(xù) ）大 項 的 二 進 制 編 碼 ：n=2: M00 P QM01 P QM10 P QM 11 P Q 72 1-6 對 偶 與 范 式 （ 續(xù) ）大 項 的 二 進 制 編 碼 ：n=3: M000 P Q RM001 P Q RM010 P Q RM011 P Q RM100 P Q RM 101 P Q RM110 P Q RM111 P Q R 73 1-6 對 偶 與 范 式 （

50、 續(xù) ）大 項 的 性 質(zhì) :（ 1） 每 一 個 大 項 當 其 真 值 指 派 與 編 碼 相 同 時 ， 其 真 值 為 F，在 其 余 2n-1中 指 派 情 況 下 均 為 T。（ 2） 任 意 兩 個 不 同 大 項 的 析 取 式 為 永 真 。（ 3） 全 體 大 項 的 合 取 式 為 永 假 ， 記 為 ： 2 1 0 1 2 10 .n nii m m m m F 74 1-6 對 偶 與 范 式 （ 續(xù) ）定 義 ： 對 于 給 定 的 命 題 公 式 ， 如 果 有 一 個 等 價 公 式 ， 它 僅由 大 項 的 合 取 所 組 成 ， 則 該 等 式 稱 為 原

51、式 的 主 合 取 范式 。定 理 ： 在 真 值 表 中 ， 一 個 公 式 的 真 值 為 F的 指 派 所 對 應(yīng) 的大 項 的 合 取 ， 即 為 此 公 式 的 主 合 取 范 式 。 75 1-6 對 偶 與 范 式 （ 續(xù) ）例 題 10： 利 用 真 值 表 技 術(shù) 求 (PQ) (PR)的 主 析 取 范 式和 主 合 取 范 式 。解 ： 公 式 (PQ) (PR)的 真 值 表 如 下 ：P Q R P P Q P R (PQ) (PR)T T T F T F TT T F F T F TT F T F F F F T F F F F F FF T T T F T TF

52、T F T F F FF F T T F T TF F F T F F F主 和 取 范 式 ：主 析 取 范 式 ： 76 1-6 對 偶 與 范 式 （ 續(xù) ）P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R0 0 0 1 0 0 0 0 0 0 00 0 1 0 1 0 0 0 0 0 00 1 0 0 0 1 0 0 0 0 00 1 1 0 0 0 1 0 0 0 01 0 0 0 0 0 0 1 0 0 01 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 01 1 1 0 0 0 0 0 0

53、 0 1 77 1-6 對 偶 與 范 式 （ 續(xù) ）例 題 11： 將 (PQ) (PR)化 為 主 合 取 范 式 。 78 1-7 重 言 式 與 蘊 涵 式 定 義 ： 給 定 一 個 命 題 ， 若 無 論 對 分 量 作 怎 樣 的 指 派 ， 其 對 應(yīng)的 真 值 永 遠 為 T， 則 稱 該 命 題 公 式 為 重 言 式 或 永 真 公 式 。 定 義 ： 給 定 一 個 命 題 ， 若 無 論 對 分 量 作 怎 樣 的 指 派 ， 其 對 應(yīng)的 真 值 永 遠 為 F， 則 稱 該 命 題 公 式 為 矛 盾 式 或 永 假 公 式 。 定 理 ： 任 何 兩 個 重 言

54、 式 的 合 取 或 析 取 仍 然 是 一 個 重 言 式 。 定 理 ： 一 個 重 言 式 ， 對 同 一 分 量 都 用 任 何 公 式 置 換 ， 其 結(jié) 果仍 然 是 一 個 重 言 式 。 定 理 ： 設(shè) A， B為 兩 個 命 題 公 式 ， A B 當 且 僅 當 A B為 一 個 重 言 式 。 79 1-7 重 言 式 與 蘊 涵 式 定 義 ： A、 B是 命 題 公 式 ， 當 A B為 一 個 重 言 式 時 ， 我 們 稱“ A蘊 涵 B”， 并 且 記 做 A = B 。 注 ： P =Q 與 Q = P 是 不 等 價 的 。 對 P =Q 來 說 ： Q =

55、 P稱 為 它 的 逆 換 式 。 P = Q稱 為 它 的 反 換 式 。 Q = P稱 為 它 的 逆 反 式 。 P Q Q P Q P P Q 逆 反命 題 80 1-7 重 言 式 與 蘊 涵 式14個 常 用 蘊 涵 命 題 ：序 號 表 達 式1 P P P2 P P = P3 P = P Q*4 P = P Q*5 Q = P Q*6 (P Q) = P*7 (P Q) = Q8 P (P Q) = Q 9 Q (P Q) = P 81 1-7 重 言 式 與 蘊 涵 式14個 常 用 蘊 涵 命 題 （ 續(xù) ） ：序 號 表 達 式10 P (P Q) Q11 (P Q) (

56、Q R) = P R12 (P Q) (P R) (Q R) = R13 (P Q) (R S) = (P R) (Q S)14 (P Q) (Q R) = (P R) 82 1-7 重 言 式 與 蘊 涵 式 定 理 ： 設(shè) P， Q為 任 意 兩 個 命 題 公 式 ， P Q 的 充 分 必 要 條件 是 P =Q 且 Q = P 。 性 質(zhì) 1. 設(shè) A,B為 合 式 公 式 ， 若 A=B且 A是 重 言 式 ， 則 B也 是 重 言 式 。 性 質(zhì) 2. 若 A=B， B=C， 則 A=C。 性 質(zhì) 3. 若 A=B且 A=C， 則 A=(B C)。 性 質(zhì) 4. 若 A=B且 C

57、=B， 則 (A C)=B。 83 1-8 推 理 理 論定 義 ： 設(shè) A和 C是 兩 個 命 題 公 式 ， 當 且 僅 當 A-C為 一 個 重 言式 ， 即 A=C， 稱 C是 A的 有 效 結(jié) 論 。 或 C可 以 由 A邏輯 地 推 出 。推 廣 ：定 義 ： 設(shè) H1,H2,Hn,C是 命 題 公 式 ， 當 且 僅 當 H1 H2 Hn=C稱 C是 一 組 前 提 H 1,H2,Hn的 有 效 結(jié) 論 。 或 稱 C可 以由 H1,H2,Hn邏 輯 地 推 出 。判 斷 有 效 結(jié) 論 的 過 程 叫 做 論 證 過 程 。 84 1-8 推 理 理 論 （ 續(xù) ）三 種 基

58、本 論 證 過 程 方 法 ：真 值 表 法 、 直 接 證 法 、 間 接 證 法 。（ 1） 真 值 表 法例 題 1. 一 個 統(tǒng) 計 表 格 的 錯 誤 或 者 是 由 材 料 不 可 靠 ， 或 者 是由 于 計 算 有 錯 誤 。 這 份 統(tǒng) 計 表 格 的 錯 誤 不 是 由 于 材 料不 可 靠 ， 所 以 這 統(tǒng) 計 表 格 的 錯 誤 是 由 于 計 算 有 錯 誤 。解 ： 設(shè) P： 統(tǒng) 計 表 格 的 錯 誤 是 由 于 材 料 不 可 靠 。Q： 統(tǒng) 計 表 格 的 錯 誤 是 由 于 計 算 有 錯 誤 。前 提 ： P (P Q) 結(jié) 論 ： Q P (P Q)=

59、Q 85 1-8 推 理 理 論 （ 續(xù) ）解 ： 公 式 P (P Q)的 真 值 表 如 下 ：P Q P P Q P (P Q)T T F T FT F F T FF T T T TF F T F F所 以 有 P (P Q)=Q。 86 1-8 推 理 理 論 （ 續(xù) ）（ 2） 直 接 證 法P規(guī) 則 ： 前 提 在 推 導(dǎo) 過 程 中 的 任 何 時 候 都 可 以 引 入 使 用 。T規(guī) 則 ： 在 推 導(dǎo) 過 程 中 ， 如 果 有 一 個 或 多 個 公 式 重 言 蘊 涵 這公 式 S， 則 公 式 S可 以 引 入 推 導(dǎo) 之 中 。 87 蘊 涵 命 題序 號 表 達

60、式I1 P P PI2 P P = QI3 P = P QI4 P = P QI5 Q = P QI6 (P Q) = PI7 (P Q) = Q I8 P (P Q) = QI9 Q (P Q) = PI10 P (P Q) QI11 (P Q) (Q R) = P RI12 (P Q) (P R) (Q R) = RI13 (P Q) (R S) = (P R) (Q S)I14 (P Q) (Q R) = (P R) 88 等 價 定 律序 號 表 達 式E1 P PE2 PP P， PP PE3 (P Q) R P (Q R)， (P Q) R P (Q R)E4 P Q Q P， P

61、 Q Q PE5 P (Q R) (P Q) (P R)， P (Q R) (P Q) (P R) E6 P (P Q) P， P (P Q) PE7 (P Q) P Q， (P Q) P QE8 P F P， P T PE9 P T T， P F FE10 P P T， P P F 89 1-8 推 理 理 論 （ 續(xù) ）例 題 1. 證 明 (PQ)(PR)(QS)=SR證 法 1： （ 1） PQ P規(guī) 則（ 2） PQ T規(guī) 則 作 用 于 （ 1） ， E等 價 性（ 3） QS P規(guī) 則（ 4） PS T規(guī) 則 作 用 于 （ 2） 、 （ 3） ， I蘊 涵 關(guān) 系（ 5） S

62、P T（ 4） ， E（ 6） P R P（ 7） S R T（ 5） 、 （ 6） ， I（ 8） S R T（ 7） ， E 90 1-8 推 理 理 論 （ 續(xù) ）證 法 2： （ 1） P R P規(guī) 則（ 2） PQRQ T規(guī) 則 作 用 于 （ 1） ， I蘊 涵 關(guān) 系（ 3） QS P規(guī) 則（ 4） QRSR T規(guī) 則 作 用 于 （ 3） ， I蘊 涵 關(guān) 系（ 5） PQSR T(2)、 （ 4） ， I（ 6） PQ P（ 7） S R T（ 5） 、 （ 6） ， I 91 1-8 推 理 理 論 （ 續(xù) ）例 題 2. 證 明 (WR)V,VCS,SU, CU=W（ 請

63、 同 學(xué) 們 自 學(xué) ） 92 1-8 推 理 理 論 （ 續(xù) ）（ 3） 間 接 證 法定 義 ： 設(shè) H1,H2,Hm是 命 題 公 式 ， 其 中 的 命 題 變 元 是P1,P2,Pn， 對 于 P1,P2,Pn的 某 些 真 值 指 派 ， 如 果 能使 H1 H2 Hm的 真 值 為 T， 則 稱 公 式H1,H2,Hm 是 相 容 的 。 如 果 對 于 P1,P2,Pn的 每 一 組真 值 指 派 都 使 得 H1 H2 Hm的 真 值 為 F， 則 稱H 1,H2,Hm 是 不 相 容 的 。不 相 容 的 概 念 用 于 命 題 公 式 的 證 明 ： 要 證 明 H1 H

64、2 Hm =C， 只 需 證 明 H1,H2,Hm與 C是 不 相 容 的 。 93 1-8 推 理 理 論 （ 續(xù) ）例 題 3. 證 明 (AB)， (BC)=A證 明 ：（ 1） A B P規(guī) 則（ 2） A P規(guī) 則 （ 附 加 前 提 ）（ 3） (BC) P規(guī) 則（ 4） B C T規(guī) 則 作 用 于 （ 3）（ 5） B T（ 1） 、 （ 2） ,I （ 6） B T（ 4） ,I （ 7） B B（ 矛 盾 ！ ） T（ 5） 、 （ 6） ， I 94 1-8 推 理 理 論 （ 續(xù) ）例 題 4. 證 明 (PQ)(PR)(QS)=S R（ 請 同 學(xué) 們 自 學(xué) ） 9

65、5 1-8 推 理 理 論 （ 續(xù) ）間 接 證 明 方 法 的 另 外 一 種 情 況 （ CP規(guī) 則 ） ： 若 要 證 明 要 H1 H2 Hm =（ R C） ， 設(shè) H1 H2 Hm為 S， 即 要 證 明 S=（ R C） 或 證 明 S=（ R C） ， 也 即 證 明 S （ R C） 為 永 真 式 。因 為S （ R C） S （ R C） （ S R） C （ S R） C （ S R） C因 此 ， 若 將 R作 為 附 加 前 提 ， 如 果 有 （ S R） = C， 即 證明 了 S=（ R C） 。 96 1-8 推 理 理 論 （ 續(xù) ）例 題 5. 證 明

66、A（ BC） ， DA， B重 言 式 蘊 涵 DC。證 明 ：（ 1） D P規(guī) 則 （ 附 加 前 提 ）（ 2） DA P規(guī) 則（ 3） A T（ 1） 、 （ 2） ,I （ 4） A（ BC） P規(guī) 則（ 5） BC T（ 3） 、 （ 4） ,I （ 6） B P（ 7） C T（ 5） 、 （ 6） ， I（ 8） DC CP規(guī) 則 97 1-8 推 理 理 論 （ 續(xù) ）例 題 6. 設(shè) 有 下 列 情 況 ， 結(jié) 論 是 否 成 立 ？ (a)或 者 是 晴 天 。 或 者 是 下 雨 。(b)如 果 是 晴 天 ， 我 去 看 電 影 。(c)如 果 我 去 看 電 影 ， 我 就 不 看 書 。 我 看 書 了 ， 所 以 今 天 下 雨（ 請 同 學(xué) 們 自 學(xué) ） 98 謂 詞 演 算 (一 階 謂 詞 演 算 ） 是 命 題演 算 的 擴 充 和 發(fā) 展 ,其 本 質(zhì) 同 命 題 演 算 ,是 把 數(shù) 學(xué) 中 的 邏 輯 論 證 加 以 符 號 化 ,從而 推 動 了 這 個 數(shù) 學(xué) 分 支 的 發(fā) 展 . 99 2-1 謂 詞 的 概 念 與 表 示2-2