離散數(shù)學屈婉玲版課件ch

《離散數(shù)學屈婉玲版課件ch》由會員分享，可在線閱讀，更多相關《離散數(shù)學屈婉玲版課件ch（33頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、1 2 主 要 內(nèi) 容l 命 題 邏 輯 基 本 概 念l 命 題 邏 輯 等 值 演 算l 命 題 邏 輯 推 理 理 論l 一 階 邏 輯 基 本 概 念l 一 階 邏 輯 等 值 演 算 與 推 理第 一 部 分 數(shù) 理 邏 輯 3 第 一 章 命 題 邏 輯 的 基 本 概 念主 要 內(nèi) 容l 命 題 與 聯(lián) 結 詞 命 題 及 其 分 類 聯(lián) 結 詞 與 復 合 命 題l 命 題 公 式 及 其 賦 值 4 命 題 與 真 值 命 題 ： 判 斷 結 果 惟 一 的 陳 述 句 命 題 的 真 值 ： 判 斷 的 結 果 真 值 的 取 值 ： 真 與 假 真 命 題 與 假 命 題

2、注 意 ：感 嘆 句 、 祈 使 句 、 疑 問 句 都 不 是 命 題陳 述 句 中 的 悖 論 ， 判 斷 結 果 不 惟 一 確 定 的 不 是 命 題 1.1 命 題 與 聯(lián) 結 詞 5 例 1 下 列 句 子 中 那 些 是 命 題 ？ (1) 是 有 理 數(shù) . (2) 2 + 5 = 7. (3) x + 5 3. (4) 你 去 教 室 嗎 ？ (5) 這 個 蘋 果 真 大 呀 ！ (6) 請 不 要 講 話 ！ (7) 2050年 元 旦 下 大 雪 . 2 假 命 題命 題 概 念 真 命 題不 是 命 題 不 是 命 題 不 是 命 題不 是 命 題命 題 ， 但 真

3、值 現(xiàn) 在 不 知 道 6 命 題 分 類 ： 簡 單 命 題 （ 也 稱 原 子 命 題 ） 與 復 合 命 題簡 單 命 題 符 號 化l 用 小 寫 英 文 字 母 p, q, r, , pi, qi, ri (i1)表 示 簡 單 命 題l 用 “ 1”表 示 真 ， 用 “ 0”表 示 假 例 如 ， 令 p： 是 有 理 數(shù) ， 則 p 的 真 值 為 0， q： 2 + 5 = 7， 則 q 的 真 值 為 1 2 命 題 分 類 7 否 定 、 合 取 、 析 取 聯(lián) 結 詞定 義 1.3 設 p, q為 兩 個 命 題 ， 復 合 命 題 “ p或 q”稱 作 p與 q的析

4、取 式 ， 記 作 p q， 稱 作 析 取 聯(lián) 結 詞 . 規(guī) 定 p q為 假 當且 僅 當 p與 q同 時 為 假 .定 義 1.1 設 p為 命 題 ， 復 合 命 題 “ 非 p”(或 “ p的 否 定 ” )稱為 p的 否 定 式 ， 記 作 p， 符 號 稱 作 否 定 聯(lián) 結 詞 . 規(guī) 定 p 為 真 當 且 僅 當 p為 假 .定 義 1.2 設 p,q為 兩 個 命 題 ， 復 合 命 題 “ p并 且 q”(或 “ p與 q”)稱 為 p與 q的 合 取 式 ， 記 作 p q， 稱 作 合 取 聯(lián) 結 詞 . 規(guī) 定 p q為 真 當 且 僅 當 p與 q同 時 為

5、真 . 8 例 2 將 下 列 命 題 符 號 化 . (1) 吳 穎 既 用 功 又 聰 明 . (2) 吳 穎 不 僅 用 功 而 且 聰 明 . (3) 吳 穎 雖 然 聰 明 ， 但 不 用 功 . (4) 張 輝 與 王 麗 都 是 三 好 生 . (5) 張 輝 與 王 麗 是 同 學 .合 取 聯(lián) 結 詞 的 實 例 9 解 令 p:吳 穎 用 功 , q:吳 穎 聰 明 (1) pq (2) pq (3) pq (4) 設 p:張 輝 是 三 好 生 , q:王 麗 是 三 好 生 pq (5) p:張 輝 與 王 麗 是 同 學(1)(3) 說 明 描 述 合 取 式 的 靈

6、 活 性 與 多 樣 性(4)(5) 要 求 分 清 “ 與 ” 所 聯(lián) 結 的 成 分合 取 聯(lián) 結 詞 的 實 例 10 例 3 將 下 列 命 題 符 號 化(1) 2 或 4 是 素 數(shù) .(2) 2 或 3 是 素 數(shù) .(3) 4 或 6 是 素 數(shù) .(4) 小 元 元 只 能 拿 一 個 蘋 果 或 一 個 梨 .(5) 王 小 紅 生 于 1975 年 或 1976 年 .析 取 聯(lián) 結 詞 的 實 例 11 解 (1) 令 p:2是 素 數(shù) , q:4是 素 數(shù) , pq(2) 令 p:2是 素 數(shù) , q:3是 素 數(shù) , pq(3) 令 p:4是 素 數(shù) , q:6是

7、素 數(shù) , pq(4) 令 p:小 元 元 拿 一 個 蘋 果 , q:小 元 元 拿 一 個 梨 (pq)(pq)(5) p:王 小 紅 生 于 1975 年 , q:王 小 紅 生 于 1976 年 , (pq)(pq) 或 pq(1)(3) 為 相 容 或(4)(5) 為 排 斥 或 , 符 號 化 時 (5)可 有 兩 種 形 式 ， 而 (4)則 不 能析 取 聯(lián) 結 詞 的 實 例 12 定 義 1.4 設 p, q為 兩 個 命 題 ， 復 合 命 題 “ 如 果 p, 則 q”稱 作 p與 q的蘊 涵 式 ， 記 作 pq， 并 稱 p是 蘊 涵 式 的 前 件 ， q為 蘊

8、涵 式 的 后 件 ，稱 作 蘊 涵 聯(lián) 結 詞 . 規(guī) 定 ： pq為 假 當 且 僅 當 p為 真 q為 假 .蘊 涵 聯(lián) 結 詞(1) pq 的 邏 輯 關 系 ： q為 p 的 必 要 條 件(2) “如 果 p, 則 q” 有 很 多 不 同 的 表 述 方 法 ： 若 p， 就 q 只 要 p， 就 q p僅 當 q 只 有 q 才 p 除 非 q, 才 p 或 除 非 q， 否 則 非 p， (3) 當 p 為 假 時 ， pq恒 為 真 ， 稱 為 空 證 明 (4) 常 出 現(xiàn) 的 錯 誤 ： 不 分 充 分 與 必 要 條 件 13 例 4 設 p： 天 冷 ， q： 小

9、王 穿 羽 絨 服 ， 將 下 列 命 題 符 號 化(1) 只 要 天 冷 ， 小 王 就 穿 羽 絨 服 .(2) 因 為 天 冷 ， 所 以 小 王 穿 羽 絨 服 .(3) 若 小 王 不 穿 羽 絨 服 ， 則 天 不 冷 .(4) 只 有 天 冷 ， 小 王 才 穿 羽 絨 服 .(5) 除 非 天 冷 ， 小 王 才 穿 羽 絨 服 .(6) 除 非 小 王 穿 羽 絨 服 ， 否 則 天 不 冷 .(7) 如 果 天 不 冷 ， 則 小 王 不 穿 羽 絨 服 .(8) 小 王 穿 羽 絨 服 僅 當 天 冷 的 時 候 .蘊 涵 聯(lián) 結 詞 的 實 例pq注 意 ： pq 與

10、 qp 等 值 （ 真 值 相 同 ） pqpqqpqppqqpqp 14 定 義 1.5 設 p, q為 兩 個 命 題 ， 復 合 命 題 “ p當 且 僅 當 q”稱 作 p與q的 等 價 式 ， 記 作 pq， 稱 作 等 價 聯(lián) 結 詞 . 規(guī) 定 pq為 真當 且 僅 當 p與 q同 時 為 真 或 同 時 為 假 .pq 的 邏 輯 關 系 ： p與 q互 為 充 分 必 要 條 件等 價 聯(lián) 結 詞例 5 求 下 列 復 合 命 題 的 真 值(1) 2 + 2 4 當 且 僅 當 3 + 3 6. (2) 2 + 2 4 當 且 僅 當 3 是 偶 數(shù) .(3) 2 + 2

11、4 當 且 僅 當 太 陽 從 東 方 升 起 .(4) 2 + 2 4 當 且 僅 當 美 國 位 于 非 洲 .(5) 函 數(shù) f (x) 在 x 0 可 導 的 充 要 條 件 是 它 在 x0 連 續(xù) . 10010 15 l 本 小 節(jié) 中 p, q, r, 均 表 示 命 題 .l 聯(lián) 結 詞 集 為 , , , , ， p, pq, pq, pq, pq為基 本 復 合 命 題 . 其 中 要 特 別 注 意 理 解 pq的 涵 義 . 反 復 使 用, , , , 中 的 聯(lián) 結 詞 組 成 更 為 復 雜 的 復 合 命 題 .設 p: 是 無 理 數(shù) ， q: 3是 奇 數(shù)

12、 ， r: 蘋 果 是 方 的 ， s: 太 陽 繞 地 球 轉 則 復 合 命 題 (pq) (rs) p) 是 假 命 題 . 2 小 結l 聯(lián) 結 詞 的 運 算 順 序 ： , , , , , 同 級 按 先 出 現(xiàn) 者 先 運 算 . 16 1.2 命 題 公 式 及 其 賦 值命 題 變 項 與 合 式 公 式l 命 題 變 項l 合 式 公 式l 合 式 公 式 的 層 次公 式 的 賦 值l 公 式 賦 值l 公 式 類 型l 真 值 表 17 命 題 變 項 與 合 式 公 式 命 題 常 項 命 題 變 項 （ 命 題 變 元 ） 常 項 與 變 項 均 用 p, q, r

13、, , pi, qi, ri, , 等 表 示 . 定 義 1.6 合 式 公 式 （ 簡 稱 公 式 ） 的 遞 歸 定 義 ： (1) 單 個 命 題 變 項 和 命 題 常 項 是 合 式 公 式 , 稱 作 原 子 命 題 公 式 (2) 若 A是 合 式 公 式 ， 則 (A)也 是 (3) 若 A, B是 合 式 公 式 ， 則 (AB), (AB), (AB), (AB)也 是 (4) 只 有 有 限 次 地 應 用 (1)(3) 形 成 的 符 號 串 才 是 合 式 公 式幾 點 說 明 ：歸 納 或 遞 歸 定 義 , 元 語 言 與 對 象 語 言 , 外 層 括 號 可

14、 以 省 去 18 合 式 公 式 的 層 次定 義 1.7(1) 若 公 式 A是 單 個 命 題 變 項 ， 則 稱 A為 0層 公 式 .(2) 稱 A 是 n+1(n0) 層 公 式 是 指 下 面 情 況 之 一 ： (a) A=B, B 是 n 層 公 式 ； (b) A=BC, 其 中 B,C 分 別 為 i 層 和 j 層 公 式 ， 且 n=max(i,j)； (c) A=BC, 其 中 B,C 的 層 次 及 n 同 (b)； (d) A=BC, 其 中 B,C 的 層 次 及 n 同 (b)； (e) A=BC, 其 中 B,C 的 層 次 及 n 同 (b). (3)

15、若 公 式 A的 層 次 為 k, 則 稱 A為 k層 公 式 .例 如 公 式 A=p, B=p, C=pq, D=(pq)r, E=(pq) r) (rs) 分 別 為 0層 ， 1層 ， 2層 ， 3層 ， 4層 公 式 . 19 定 義 1.8 設 p1, p2, , pn是 出 現(xiàn) 在 公 式 A中 的 全 部 命 題 變 項 , 給 p1, p2, , pn各 指 定 一 個 真 值 , 稱 為 對 A的 一 個 賦 值 或 解 釋 . 若 使 A為 1, 則 稱 這 組 值 為 A的 成 真 賦 值 ; 若 使 A為 0, 則 稱 這 組值 為 A的 成 假 賦 值 .幾 點 說

16、 明 ：l A中 僅 出 現(xiàn) p1, p2, , pn， 給 A賦 值 =12n是 指 p1=1, p2=2, , pn=n, i=0或 1, i之 間 不 加 標 點 符 號l A中 僅 出 現(xiàn) p, q, r, , 給 A賦 值 123是 指 p= 1, q=2 , r=3 l 含 n個 命 題 變 項 的 公 式 有 2n個 賦 值 . 如 000, 010, 101, 110是 (pq)r的 成 真 賦 值 001, 011, 100, 111是 成 假 賦 值 . 公 式 賦 值 20 定 義 1.9 將 命 題 公 式 A在 所 有 賦 值 下 取 值 的 情 況 列 成 表 ,

17、稱 作A的 真 值 表 .構 造 真 值 表 的 步 驟 :(1) 找 出 公 式 中 所 含 的 全 部 命 題 變 項 p1, p2, , pn(若 無 下 角 標 則 按 字 母 順 序 排 列 ), 列 出 2n個 全 部 賦 值 , 從 000開 始 , 按 二 進 制 加 法 , 每 次 加 1, 直 至 111為 止 . (2) 按 從 低 到 高 的 順 序 寫 出 公 式 的 各 個 層 次 .(3) 對 每 個 賦 值 依 次 計 算 各 層 次 的 真 值 , 直 到 最 后 計 算 出 公 式 的 真 值 為 止 . 真 值 表 21 例 6 寫 出 下 列 公 式 的

18、 真 值 表 , 并 求 它 們 的 成 真 賦 值 和 成 假 賦 值 : (1) (pq) r (2) (qp) qp (3) (pq) q 真 值 表 22 (1) A = (pq) r成 真 賦 值 :000,001,010,100,110; 成 假 賦 值 :011,101,111 p q r pq r (pq)r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 00111111 10101010 11101010 真 值 表 1 23 (2) B (qp)qp成 真 賦 值 :00,01,10,11; 無 成 假 賦 值p q qp (qp)q (q

19、p)qp0 00 11 01 1 1011 0001 1111真 值 表 2 24 (3) C (pq)q的 真 值 表成 假 賦 值 :00,01,10,11; 無 成 真 賦 值p q p pq (pq) (pq)q0 00 11 01 1 1100 1101 0010 0000真 值 表 3 25 公 式 的 類 型定 義 1.10 (1) 若 A在 它 的 任 何 賦 值 下 均 為 真 , 則 稱 A為 重 言 式 或 永 真 式 ;(2) 若 A在 它 的 任 何 賦 值 下 均 為 假 , 則 稱 A為 矛 盾 式 或 永 假 式 ;(3) 若 A不 是 矛 盾 式 , 則 稱

20、A是 可 滿 足 式 .由 例 1可 知 , (pq) r, (qp) qp, (pq) q 分 別 為 非 重 言 式 的 可 滿 足 式 , 重 言 式 , 矛 盾 式 .注 意 ： 重 言 式 是 可 滿 足 式 ， 但 反 之 不 真 .真 值 表 的 用 途 : 求 出 公 式 的 全 部 成 真 賦 值 與 成 假 賦 值 , 判 斷 公 式 的 類 型 26 第 一 章 習 題 課主 要 內(nèi) 容l 命 題 、 真 值 、 簡 單 命 題 與 復 合 命 題 、 命 題 符 號 化l 聯(lián) 結 詞 , , , , 及 復 合 命 題 符 號 化l 命 題 公 式 及 層 次l 公 式

21、 的 類 型l 真 值 表 及 應 用基 本 要 求l 深 刻 理 解 各 聯(lián) 結 詞 的 邏 輯 關 系 , 熟 練 地 將 命 題 符 號 化l 會 求 復 合 命 題 的 真 值l 深 刻 理 解 合 式 公 式 及 重 言 式 、 矛 盾 式 、 可 滿 足 式 等 概 念l 熟 練 地 求 公 式 的 真 值 表 ， 并 用 它 求 公 式 的 成 真 賦 值 與 成 假 賦 值 及 判 斷 公 式 類 型 27 1. 將 下 列 命 題 符 號 化 (1) 豆 沙 包 是 由 面 粉 和 紅 小 豆 做 成 的 . (2) 蘋 果 樹 和 梨 樹 都 是 落 葉 喬 木 . (3)

22、 王 小 紅 或 李 大 明 是 物 理 組 成 員 . (4) 王 小 紅 或 李 大 明 中 的 一 人 是 物 理 組 成 員 . (5) 由 于 交 通 阻 塞 ， 他 遲 到 了 . (6) 如 果 交 通 不 阻 塞 ， 他 就 不 會 遲 到 . (7) 他 沒 遲 到 ， 所 以 交 通 沒 阻 塞 . (8) 除 非 交 通 阻 塞 ， 否 則 他 不 會 遲 到 . (9) 他 遲 到 當 且 僅 當 交 通 阻 塞 .練 習 1 28 提 示 ：分 清 復 合 命 題 與 簡 單 命 題分 清 相 容 或 與 排 斥 或分 清 必 要 與 充 分 條 件 及 充 分 必

23、要 條 件答 案 : (1) 是 簡 單 命 題 (2) 是 合 取 式 (3) 是 析 取 式 （ 相 容 或 ） (4) 是 析 取 式 （ 排 斥 或 ）設 p: 交 通 阻 塞 ， q: 他 遲 到 (5) pq, (6) pq或 qp (7) qp 或 pq, (8) qp或 pq (9) pq 或 pq可 見 (5)與 (7)， (6)與 (8) 相 同 （ 等 值 ）練 習 1解 答 29 2. 設 p : 2是 素 數(shù) q : 北 京 比 天 津 人 口 多 r : 美 國 的 首 都 是 舊 金 山 求 下 面 命 題 的 真 值 (1) (pq)r (2) (qr)(pr)

24、 (3) (qr)(pr) (4) (qp)(pr)(rq) 0練 習 2 100 30 3. 用 真 值 表 判 斷 下 面 公 式 的 類 型 (1) pr(qp) (2) (pq) (qp) r (3) (pq) (pr) 練 習 3 31 練 習 3解 答(1) pr(qp) 矛 盾 式 p q r qp (qp) pr(qp)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 11001111 00110000 00000000 32 練 習 3解 答(2) (pq) (qp) r 永 真 式 11111111 11110011 11110011 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 (pq) (qp) rqp pq p q r 33 練 習 3解 答(3) (pq) (pr) 非 永 真 式 的 可 滿 足 式p q r pq pr (pq) (pr)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 11110011 11110101 11111001