離散數學 大連理工大學軟件學院 陳志奎 教授 辦公室 綜合樓411 Tel 87571525 實驗室 教學樓A318 A323 Tel 87571620 24 MobileEmail zkchen zkchen00 1 34 引言 離散數學是計算機專業的一門重要基礎課 它所研究的 對象是離散數量關系和離散結構數學結構模型 由于數 字電子計算機是一個離散結構 它只能處理離散的或離 散化了的數量關系 因此 無論計算機科學本身 還是 與計算機科學及其應用密切相關的現代科學研究領域 都面臨著如何對離散結構建立相應的數學模型 又如何 將已用連續數量關系建立起來的數學模型離散化 從而 可由計算機加以處理 離散數學課程主要介紹離散數學 的各個分支的基本概念 基本理論和基本方法 這些概 念 理論以及方法大量地應用在數字電路 編譯原理 數據結構 操作系統 數據庫系統 算法的分析與設計 人工智能 計算機網絡等專業課程中 同時 該課程所 提供的訓練十分有益于學生概括抽象能力 邏輯思維能 力 歸納構造能力的提高 十分有益于學生嚴謹 完整 規范的科學態度的培養 2 34 學習方法 精確嚴格地掌握好概念和術語 正確理解 它們的內涵和外延 獨立完成作業 自覺歸納基本解題方法 閱讀和復習時 隨時備好紙筆 以便進行 詳細的推導和計算 學習和理解術語 給術語賦予特殊的含 義 加深理解 多做習題 加深理解 3 34 第一章 命題邏輯 第一章 命題邏輯 數理邏輯是用數學方法研究思維規律的一門學 科 所謂數學方法是指 用一套數學的符號系統 來描述和處理思維的形式與規律 因此 數理 邏輯又稱為符號邏輯 數理邏輯和計算機的發展有著密切的聯系 它為 機器證明 自動程序設計 計算機輔助設計等計 算機應用和理論研究提供必要的理論基礎 古典數理邏輯 命題邏輯和謂詞邏輯 是計算機 科學很重要的數學基礎 現代數理邏輯 邏輯演算 證明論 公理集合論 遞歸論和模型論 本章介紹數理邏輯中最基本的內容命題邏輯 首 先引入命題 命題公式等概念 然后 在此基礎 上研究命題公式間的等值關系和蘊含關系 并給 出推理規則 進行命題演算 5 34 數理邏輯的創始人數理邏輯的創始人 萊布尼茨萊布尼茨 Leibniz Gottfried Wilhelm Leibniz Gottfried Wilhelm Leibniz Gottfried Wilhelm Leibniz Gottfried Wilhelm 1646 7 1 1716 11 141646 7 1 1716 11 141646 7 1 1716 11 141646 7 1 1716 11 14 德國數學家 物理學家 哲學家等 德國數學家 物理學家 哲學家等 一個舉世罕見的科學天才 研究領域涉一個舉世罕見的科學天才 研究領域涉 及到邏輯學 數學 力學 地質學 法及到邏輯學 數學 力學 地質學 法 學 歷史學 語言學 生物學以及外交 學 歷史學 語言學 生物學以及外交 神學等諸多方面神學等諸多方面 出生于德國東部萊比錫的一個書香之出生于德國東部萊比錫的一個書香之 家 父親是萊比錫大學的道德哲學教家 父親是萊比錫大學的道德哲學教 授 母親出生在一個教授家庭 萊布尼授 母親出生在一個教授家庭 萊布尼 茲的父親在他年僅茲的父親在他年僅6 6歲時便去世了 給歲時便去世了 給 他留下了豐富的藏書 他留下了豐富的藏書 6 34 15歲時 進了萊比錫大學學習法律 一進校便跟上了大學二年 級標準的人文學科的課程 還廣泛閱讀了培根 開普勒 伽利 略等人的著作 并對他們的著述進行深入的思考和評價 在聽 了教授講授歐幾里德的 幾何原本 的課程后 萊布尼茲對數 學產生了濃厚的興趣 17歲時他在耶拿大學學習了短時期的數 學 并獲得了哲學碩士學位 19歲設計出世界第一臺乘法器 被認為是現代機器數學的先驅 者 Leibniz 1646 1716年 之夢 有一天所有的知識 包括精 神和無形的真理 能夠通過通用的代數演算放入一個單一的演 繹系統 1693年 發現了機械能的能量守恒定律 與牛頓并稱為微積分的創立者 系統闡述了二進制記數法 并把它和中國的八卦聯系起來 7 34 主要內容 主要內容 命題 命題邏輯聯結詞 命題變元 合式公式 重言式 永真蘊含 恒等式 帶入規則 替換規則 對偶原理 范式及其判定問題 命題演算的推理 8 34 1 1概述 目標 探索出一套完整的邏輯規則 這些規則 給出數學語句的準確定義 按照這些規 則可以確定任何特定的論證是否有效 應用 計算機電路設計 計算機程序構造 程序正確性證明 9 34 1 2命題與命題邏輯聯結詞 一 命題 所謂命題 是指具有非真必假的陳述句 而疑問句 祈使句和感嘆句等因都不能判斷其真假 故都不是命 題 1 定義 一個具有真假意義真假意義的陳述句陳述句被稱為一 個命題 或真或假 不能既真又假 例1 判斷下面語句是否是命題 華盛頓是美國的首都 多倫多是加拿大的首都 1 101 110 幾點了 x 1 3 西安的小吃真多呀 10 34 1 2命題與命題邏輯聯結詞 理發師問題 理發師給所有不給自己理發的人理發 11 34 1 2命題與命題邏輯聯結詞 一 命題 2 命題的真值及表示 命題用大寫的英文字母 如 來表示 P 今天是星期二 命題僅有兩種可能的真值 真和假 且二者只能居其 一 如果一個命題的真值是真 則用1或 Ture 來表 示 如果一個命題的真值是假 則用0或 False 來 表示 由于命題只有兩種真值 所以稱這種邏輯為二 值邏輯 命題的真值是具有客觀性質的 而不是由人 的主觀決定的 原子命題 一個命題不能再分解為更簡單的命題 這個命題 稱為原子命題 P Q R 12 34 1 2命題與命題邏輯聯結詞 二 邏輯聯結詞 復合命題 分子命題 如果如果下周日下雪 那么那么我就去滑雪 如果下周日不不下雨并且并且沒有考試 那么我去海 邊玩 這次演講比賽 我們班將由趙明或者或者張強參加 13 34 5種邏輯聯結詞 否定詞 并非 合取詞 并且 析取詞 或者 蘊含詞 如果 那么 單向詞 雙向蘊含詞 當且僅當 雙向詞 14 34 否定 定義 設 是一個命題 則 的否定是一個新的命題 記作 讀作 非 例2 找出命題 所有的素數都是奇數 的否定 并非所有的素數都是奇數 所有的素數都不是奇數 否定詞 的意義如下表 P P P P PP TF FT PP 01 10 或 真值表 利用運算對象真值的 所有可能組合判斷命題的真假 15 合取 定義 表征意義 兩命題合取的真值表 PQ 在命題 和 均為真時為真 否則為假 PQPQPQ 設 和 是命題 則用表示命題 并且 PQPQ PQPQ FFF FTF TFF TTT 000 010 100 111 或 16 合取 P Q PQ 命題 今天是星期五 命題 今天下雨 找出命題 和 的合取 PQ 解 表示 今天是星期五并且下雨 這一命題在下雨的星期五成真 不下雨 的星期五和不是星期五的日子都為假 17 析取 定義 表征意義 兩命題析取的真值表 PQ 在命題 和 均為假時為假 否則為真 PQPQPQ 設 和 是命題 則用表示命題 或者 PQPQ PQPQ FFF FTT TFT TTT 000 011 101 111 或 18 析取 P Q PQ 例 命題 李明在教室 命題 張強是個好教練 找出命題 和 的析取 PQ 解 表示 李明在教室或張強是個好教練 P Q 例 命題 李明在教室 命題 李明在網球場 表示命題 李明在教室或在網球場 19 異或 定義 表征意義 雙條件 的真值表 PQ 在 和 中恰有一個為真時為真 否則為假 PQP QPQ 設 和 是命題 則用表示命題 異或 PQP Q PQP Q FFF FTT TFT TTF 000 101 011 110 P Q 或 20 單條件 定義 表征意義 蘊含 的真值表 PQ 在 為真而 為假時為假 否則為真 PQPQPQ 設 和是命題 則用表示命題 如果那么 PQPQ PQPQ FFT FTT TFF TTT 001 100 011 111 PQ 或 21 單條件 政治家競選時許諾 如果我當選了 那么我將會減稅 如果今天是星期五 那么2 2 4 與程序設計中if p then S語句的區別 22 單條件 在日常生活中 用條件式表示前提和結論之間的 因果或實質關系 這種條件式稱為形式條件命題 然而在命題邏輯中 一個條件式的前提并不要求 與結論有任何關系 這種條件式稱為實質條件命 題 采用實質條件式作定義 不單是出于 善意 推斷 主要是因為前提與結論間有無因果和實 質關系難以區分 而且實質條件式已包含了形式 條件式 更便于應用 23 34 單條件 注意 在使用聯結詞 時 要特別注意以下幾點 1 在自然語言里 特別是在數學中 q是p的必要條件 有許多不同的敘述方式 例如 只要p 就q 因為 p 所以q p僅當q 只有q才p 除非q才p 除 非q 否則非p 等等 以上各種敘述方式表面看來有所不 同 但都表達的是q是p的必要條件 因而所用聯結詞均 應符號化為 上述各種敘述方式都應符號化為p q 2 在自然語言中 如果p 則q 中的前件p與后件q往往 具有某種內在聯系 而在數理邏輯中 p與q可以無任何 內在聯系 3 在數學或其它自然科學中 如果p 則q 往往表達的 是前件p為真 后件q也為真的推理關系 但在數理邏輯 中 作為一種規定 當p為假時 無論q是真是假 p q 均為真 也就是說 只有p為真q為假這一種情況使得復 合命題p q為假 24 34 雙條件 定義 表征意義 雙條件 的真值表 PQ 在 和具有相同的真值時為真 否則為假 PQPQPQ 設 和 是命題 則用表示命題 等值于 PQPQ PQPQ FFT FTF TFF TTT 001 100 010 111 PQ 或 25 1 2命題與命題邏輯聯結詞 注意 由邏輯聯結詞聯結的命題之間不需要任何關 系 優先次序 PQR PQR 26 句子到邏輯表達式的翻譯 步驟 確定給定的句子是否為命題 找出各原子命題并確定句子中的連詞為 對應的聯結詞 用正確的語法把原命題表示成由原子命 題 聯結詞和圓括號組成的公式 27 34 句子到邏輯表達式的翻譯 翻譯下列命題 1 他既聰明又用功 2 他雖聰明但不用功 解 原子命題 P 他聰明 Q 他用功 則有 1 翻譯成 P Q 2 翻譯成 P Q 28 34 句子到邏輯表達式的翻譯 除非有時間 我才去看電影 A 我有時間 B 我去看電影 翻譯為 B A 我不承認你是對的 除非太陽從西邊出來 A 我不承認你是對的 B 太陽從西邊出來 翻譯為 B A 29 34 句子到邏輯表達式的翻譯 如果你和他都不固執己見的話 那么不愉 快的事情就不會發生了 P 你固執己見 Q 他固執己見 R 不愉快的事情不會發生 翻譯為 P Q R 如果你和他不都是固執己見的話 那么不 愉快的事情就不會發生了 P Q R 30 34 句子到邏輯表達式的翻譯 P 這個材料很有趣 Q 這個習題很難 R 這門課程使人喜歡 1 這個材料很有趣 而且這些習題很難 2 這個材料無趣 習題也不難 那么 這門課程 就不會使人喜歡 3 這個材料無趣 習題也不難 而且這門課程也 不使人喜歡 4 這個材料很有趣意味著這些習題很難 反之亦 然 5 或者這個材料很有趣 或者這些習題很難 而 且兩者恰具其一 31 34 句子到邏輯表達式的翻譯 除非你已滿16周歲 否則只要你的身高不 足4英尺就不能乘公園滑行鐵