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

1、離 散 數(shù) 學Discrete Mathematics計 算 機 科 學 與 工 程 學 院 金 忠智 能 樓 (3 3 7 幢 )3 0 5 室84317297-305, 13770713373 http:/ 計 算 機 科 學 離 散 數(shù) 學離 散 數(shù) 學 研 究 離 散 數(shù) 量 關 系 和 離 散 結(jié) 構(gòu) 數(shù)學 模 型 的 數(shù) 學 分 支 的 統(tǒng) 稱 。 古 代 數(shù) 學 整 數(shù) 、 整 數(shù) 的 比近 代 數(shù) 學 連 續(xù) 的 數(shù) 量 概 念 （ 實 數(shù) ） ， 處 理連 續(xù) 數(shù) 量 關 系 的 數(shù) 學 （ 微 積 分 ）如 何 對 離 散 結(jié) 構(gòu) 建 立 離 散 數(shù) 學 模 型 ? 離 散

2、 數(shù) 學 及 其 應 用數(shù) 理 邏 輯(1-5) 集 合 論 (6 -8 )圖 論(9-10) 代 數(shù)(11-12) 劉 嘉 憶 對 計 算 機 專 業(yè) 系 統(tǒng) 知 識 的 輻 射 作 用 數(shù) 理 邏 輯第 一 章 命 題 演 算 基 礎第 二 章 命 題 演 算 的 推 理 理 論第 三 章 謂 詞 演 算 基 礎第 四 章 謂 詞 演 算 的 推 理 理 論第 五 章 遞 歸 函 數(shù) 論 第 一 章 命 題 演 算 基 礎1.1 命 題 和 聯(lián) 結(jié) 詞1 .1 .1 命 題 (一 ) 命 題 定 義定 義 1 凡 是 可 以 判 斷 真 假 的 陳 述 句 稱 為 命 題 。命 題 的 值

3、 真 , 用 T(或 1)表 示假 , 用 F(或 0)表 示 例 ： 下 列 句 子 都 是 命 題 嗎 ？ 雪 是 白 的 。 雪 是 黑 的 。 好 大 的 雪 啊 ！ 8 大 于 1 2 。 1 +1 0 1 =1 1 0 。 例 ： 下 列 句 子 都 是 命 題 嗎 ？ 上 海 世 博 會 開 幕 時 天 晴 2 1 世 紀 末 ， 人 類 將 住 在 月 球 大 于 2 的 偶 數(shù) 可 表 示 成 兩 個 素 數(shù) 之 和 X0 ， 則 x2 0 。例 若 兩 圓 面 積 相 等 ， 則 它 們 的 半 徑 相 等 。 是 否 命 題 ？ 是 否 復 合 命 題 ？例 若 兩 圓

4、的 面 積 相 等 ， 則 它 們 的 半 徑 相 等 。例 若 兩 圓 A、 B的 面 積 相 等 ， 則 它 們 的 半 徑 相 等 。 例 吃 一 塹 ， 長 一 智 。 A B 真 值 函 項 的 定 義以 真 假 為 定 義 域 并 以 真 假 為 值 域 的 函 數(shù)T, F(T, T), (T,F), (F,T), (F,F) T, F一 元 真 值 函 項二 元 真 值 函 項 T, F 一 元 聯(lián) 結(jié) 詞 的 真 值 表一 個 命 題 變 項 P， 可 取 “ T” 和 “ F” 兩 種 值 ?？?定 義 四 個 一 元 真 值 函 項 f0 ， f1 ， f2 ， f3 。P

5、 f0(P) f1(P) f2(P) f3(P)T T T F FF T F T F永真 恒等 否定P 永假 二 元 聯(lián) 結(jié) 詞 P Q f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f1 0 f1 1 f1 2 f1 3 f1 4 f1 5T T T F T T T F F F T T T T F F F FT F T T F T T F T T F F T F T F F FF T T T T F T T F T F T F F F T F FF F T T T T F T T F T F F F F F T Ff4為析取f2為蘊含 f8為等價 f11為合取 三 元 聯(lián) 結(jié)

6、詞 共 有 多 少 個 ？f0 f1 f2 f?(0 ,0 ,0 ) 0 1 0 1(0 ,0 ,1 ) 0 0 1 1(0 ,1 ,0 ) 0 0 0 1(0 ,1 ,1 ) 0 0 0 1(1 ,0 ,0 ) 0 0 0 1(1 ,0 ,1 ) 0 0 0 1(1 ,1 ,0 ) 0 0 0 1(1 ,1 ,1 ) 0 0 0 1 28 1 .1 .3 合 式 公 式合 式 公 式 為 如 下 定 義 的 式 子 ， 簡 稱 為 公 式 ： 任 何 命 題 變 元 均 是 公 式 ； 如 果 P為 公 式 ， 則 P為 公 式 ； 如 果 P， Q為 公 式 ， 則 PQ, PQ, PQ,

7、 PQ 為 公 式 ； 當 且 僅 當 經(jīng) 過 有 限 次 使 用 、 、 所 組 成 的符 號 串 才 是 公 式 ， 否 則 不 為 公 式 。Well formed formulae n 元 公 式 若 公 式 中 有 n個 不 同 的 命 題 變 元 ，就 說 為 n 元 公 式 。3元 公 式 的 例 子 ： （ （ PQ） R） （ PQ）（ PQR） （ PQ） 優(yōu) 先 級 約 定 、 、 、 優(yōu) 先 級 相 同 比 其 它 聯(lián) 結(jié) 詞 有 更 高 的 優(yōu) 先 級 括 號 （ ） 內(nèi) 的 運 算 優(yōu) 先例 令 P： 北 京 比 天 津 人 口 多 。 Q： 2+2 4。 R： 烏

8、 鴉 是 白 色 的 。 求 下 列 公 式 的 真 值 ： (1) (Q R)(P R) (2) (P R) (P R) 命 題 符 號 化l 分 析 出 簡 單 命 題 ， 符 號 化l 用 聯(lián) 結(jié) 詞 聯(lián) 結(jié) 簡 單 命 題提 示 ： 根 據(jù) 命 題 的 實 際 含 義 ， 不 拘 泥 于 原 句 形 式 地 確定 原 子 命 題 和 選 用 聯(lián) 結(jié) 詞 。例 將 下 述 命 題 符 號 化 ， 并 指 出 真 值 : （ 1） 肉 包 子 是 由 面 粉 和 豬 肉 做 成 的 。 （ 2） 2是 質(zhì) 數(shù) 且 偶 數(shù) ， 3是 質(zhì) 數(shù) 或 偶 數(shù) 。 （ 3） 如 果 我 只 有 懂

9、得 希 臘 文 才 能 了 解 柏 拉 圖 ， 那么 我 不 了 解 柏 拉 圖 。 （ 4） 如 果 他 喜 歡 QQ， 他 就 喜 歡 微 信 ； 當 小 紅 心 情愉 快 時 ， 她 就 唱 歌 ； 反 之 ， 當 她 唱 歌 時 ， 一定 心 情 愉 快 。 例 4 (p5 )已 知 三 個 命 題 ： P： 今 晚 我 在 家 上 網(wǎng) ；Q： 今 晚 我 去 球 場 看 足 球 比 賽 ；R： 今 晚 我 在 家 上 網(wǎng) 或 去 球 場 看 足 球 比 賽 。試 問 PQ和 R是 否 表 達 同 一 命 題 ？請 用 真 值 表 說 明 之 。 R=(PQ)(PQ)P Q PQ R T T T F T F T T F T T T F F F F 不 可 兼 或