離散數(shù)學(xué)講義
《離散數(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當(dāng) 且 僅 當(dāng) 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) 當(dāng) 且 僅 當(dāng) 能 夠 有 限 次 地 應(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, 當(dāng) 且 僅 當(dāng) 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, 當(dāng) 且 僅 當(dāng) 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的“ 與 非 ” , 當(dāng) 且 僅 當(dāng) 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的“ 或 非 ” , 當(dāng) 且 僅 當(dāng) 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ù) )定 義 : 一 個 命 題 稱 為 合 取 范 式 , 當(dāng) 且 僅 當(dāng) 它 具 有 如 下 的 形式 :A1A2 An, (n1)其 中 A1,A2,An都 是 由 命 題 變 元 或 其 否 定 所 組 成 的 析 取 式 。定 義 : 一 個 命 題 稱 為 析 取 范 式 , 當(dāng) 且 僅 當(dāng) 它 具 有 如 下 的 形式 :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) 每 一 個 小 項 當(dāng) 其 真 值 指 派 與 編 碼 相 同 時 , 其 真 值 為 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) 每 一 個 大 項 當(dāng) 其 真 值 指 派 與 編 碼 相 同 時 , 其 真 值 為 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 當(dāng) 且 僅 當(dāng) A B為 一 個 重 言 式 。 79 1-7 重 言 式 與 蘊 涵 式 定 義 : A、 B是 命 題 公 式 , 當(dāng) 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是 兩 個 命 題 公 式 , 當(dāng) 且 僅 當(dāng) A-C為 一 個 重 言式 , 即 A=C, 稱 C是 A的 有 效 結(jié) 論 。 或 C可 以 由 A邏輯 地 推 出 。推 廣 :定 義 : 設(shè) H1,H2,Hn,C是 命 題 公 式 , 當(dāng) 且 僅 當(dāng) 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
- 溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。