【正文】 1/73 離散數(shù)學 II 肖明軍 Web: Email: 2/73 引言 ?課程簡介 – 離散數(shù)學是現(xiàn)代數(shù)學的一個重要分支 ， 是計算機科學中基礎理論的核心課程 ， 它 研究的對象是有限個或可數(shù)的離散量 。 充分描述了計算機科學離散性的特征 。 – 離散數(shù)學是傳統(tǒng)的邏輯學、集合論、數(shù)論基礎、算法設計、組合分析、離散概率、關系理論、圖論與樹、抽象代數(shù)、布爾代數(shù)、計算模型等匯集起來的一門綜合學科。離散數(shù)學的應用遍及現(xiàn)代科學技術的諸多領域。 – 離散數(shù)學是隨著計算機科學的發(fā)展而逐步建立起來的一門新興的工具性學科 ， 形成于上上個世紀七十年代 。 3/73 引言 ?課程意義 – 離散數(shù)學是計算機科學的數(shù)學基礎 ， 其基本概念 、理論 、 方法大量地應用在數(shù)字電路 、 編譯原理 、 數(shù)據(jù)結構 、 操作系統(tǒng) 、 數(shù)據(jù)庫系統(tǒng) 、 算法設計 、 人工智能 、 計算機網(wǎng)絡等專業(yè)課程中 ， 是這些課程的基礎課程 。 – 離散數(shù)學學習十分有益于概括抽象能力 、 邏輯思維能力 、 歸納構造能力的提高 ， 能夠培養(yǎng)提高學生的數(shù)學思維能力和對實際問題的求解能力 。 ?教學內容 – 數(shù)理邏輯 、 集合論 、 代數(shù)結構 、 圖論 4/73 引言 ?教學內容 第一部分 數(shù)理邏輯 第一章 命題邏輯 第二章 謂詞邏輯 第二部分 集合論 第三章 集合代數(shù) 第四章 二元關系 5/73 引言 ?教學內容 第二部分 集合論 第五章 函數(shù) 第六章 集合的基數(shù) 第三部分 代數(shù)結構 第七章 代數(shù)系統(tǒng) 第八章 群論 6/73 引言 ?教學內容 第三部分 代數(shù)結構 第九章 環(huán)與域 第十章 格與布爾代數(shù) 7/73 第一部分 數(shù)理邏輯 ?邏輯學 –是一門研究思維形式和規(guī)律的科學。分為辯證邏輯和形式邏輯兩種。思維的形式結構包括了 概念﹑ 判斷 和 推理 之間的結構和聯(lián)系，其中 概念 是思維的基本單位，通過概念對事物是否具有某種屬性進行肯定或否定的回答，就是 判斷 。由一個或幾個判斷推出另一判斷的思維形式就是 推理 。 ?數(shù)理邏輯 –用數(shù)學方法研究推理的規(guī)律稱為數(shù)理邏輯。所謂數(shù)學方法就是引用一套符號體系的方法，所以數(shù)理邏輯又稱作符號邏輯。 8/73 第一部分 數(shù)理邏輯 ?現(xiàn)代數(shù)理邏輯 –邏輯演算、邏輯演繹、模型論、證明論、遞歸函數(shù)論、公理化集合論等。 –我們要介紹的是數(shù)理邏輯中最基本的內容：命題邏輯和謂詞邏輯。即一般所謂的古典邏輯。 –德國數(shù)學家萊布尼茨 Leibniz（現(xiàn)代邏輯的首席創(chuàng)始人）；布爾 Boole （奠基人，邏輯的數(shù)學分析）；弗雷格（數(shù)論的基礎） 9/73 第一章 命題邏輯 命題邏輯也稱命題演算或語句邏輯。它研究以 “ 命題 ” 為基本單位構成的前提和結論之間的可推導關系，研究什么是命題？如何表示命題？怎樣由一組前提推導一些結論。 概念 判斷 推理 10/73 命題與命題聯(lián)結詞 ?定義 ：具有 確切真值 的 陳述句 (或斷言 )稱為命題 (Proposition)。 ?命題的取值稱為真值。真值只有“真”和“假”兩種，分別用“ T”或“ 1”和“ F”或“ 0”表示。 ?注意：命題的真值非真即假，只有兩種取值，這樣的系統(tǒng)為二值邏輯系統(tǒng)。 11/73 命題與命題聯(lián)結詞 ?例 11：命題示例。 (a):今天下雪 (b):3+3=6 (c):2是偶數(shù)而 3是奇數(shù) (d):陳勝起義那天，合肥下雨 (e):較大的偶數(shù)都可表為兩個質數(shù)之和 (f):x+y4 (g):真好啊 ! (h):x=3 (i):你去哪里？ (j):我正在說謊。 ?注意： 由定義知，一切沒有判斷內容的句子如命令，感嘆句，疑問句，祈使句，二義性的陳述句等都不能作為命題。 12/73 命題與命題聯(lián)結詞 ?例 12：下列句子哪些是命題，判斷命題的真假。 (1):2是素數(shù) (2):北京是中國的首都 (3):這個語句是假的 (4):x+y0 (5):我喜歡踢足球 (6):地球外的星球上也有人 (7):明年國慶節(jié)是晴天 (8):把門關上 (9):你要出去嗎？ (10):今天天氣真好??！ 13/73 ?注意 –命題一定是通過陳述句來表達；反之，并非一切的陳述句都一定是命題。 –命題的真值有時可明確給出，有時還需要依靠環(huán)境條件，實際情況，時間才能確定其真值。但其真值一定是唯一確定的。 命題與命題聯(lián)結詞 14/73 命題與命題聯(lián)結詞 ?命題可分為兩種類型： –簡單命題： 若一個命題已不能分解成更簡單的命題 ， 則該命題叫原子命題或本原命題或簡單命題 （ Simple Proposition） –復合命題 （ Compound Proposition） ：可以分解為簡單命題的命題 ， 而且這些簡單命題之間是通過關聯(lián)詞 （ 如 “ 或者 ” ,“并且 ” ,“不 ” ，“ 如果 … 則 … ”,“當且僅當 ” 等 ） 和標點符號復合而構成一個復合命題 。 例 ， 合肥是安徽的省會當且僅當鳥會飛 。 ?注意： –命題通常用大寫英文字母 （ 可帶下標 ） 來表示 。 15/73 命題聯(lián)結詞 命題通常可以通過一些聯(lián)結詞復合而構成新的命題 ，這些聯(lián)結詞被稱為 邏輯聯(lián)結詞 。 用數(shù)學方法研究命題之間的邏輯關系時 （ 也就是在命題演算中 ） ， 這些聯(lián)結詞可以看作是運算符 ， 因此也叫作 邏輯運算符 。 常用的聯(lián)結詞有以下 5個： ?定義 ： 設 P是任一命題 ， 復合命題 “ 非 P”（ 或“ P的否定 ” ） 稱為 P的否定式 （ Negation） ， 記作172。P ， “ 172?！睘榉穸?lián)結詞 。 172。P 為真當且僅當 P為假 。 如： P： 2是素數(shù) ， 則 172。P ： 2不是素數(shù) 。 命題與命題聯(lián)結詞 16/73 命題與命題聯(lián)結詞 ?定義 ： 設 P ﹑ Q是任意兩個命題 ， 復合命題 “ P并且 Q”（ 或 “ P和 Q”） 稱為 P與 Q的合取式（ Conjunction） ， 記作 P ∧ Q， “ ∧ ” 為合取聯(lián)結詞 。 P ∧ Q為真當且僅當 P， Q同為真 。 例 ， P： 2是素數(shù) ， Q： 2是偶數(shù) 。 則 P ∧ Q： 2是素數(shù)并且是偶數(shù) 。 17/73 命題與命題聯(lián)結詞 ?定義 ： 設 P ﹑ Q是任意兩個命題 ， 復合命題 “ P或 Q” 稱為 P與 Q的析取式 （ Disjunction） ， 記作 P ∨ Q， “ ∨ ” 為析取聯(lián)結詞 。 P ∨ Q為真當且僅當 P， Q至少一個為真 。 例 ， P： 2是素數(shù) ， Q： 2是奇數(shù) 。 則 P ∨ Q： 2是素數(shù)或是奇數(shù) 。 18/73 命題與命題聯(lián)結詞 ?定義 ： 設 P ﹑ Q是任意兩個命題 ， 復合命題 “ 如果 P則 Q” 稱為 P與 Q的蘊含式 （ Implication） ， 記作 P→Q， “ →” 為 蘊含聯(lián)結詞 ， P稱為蘊含式的前提 ， 假設或前件 ， 而 Q稱為結論式后件 。 P→Q為假當且僅當 P為真 Q為假 。 例 ， P： G是正方形 ， Q： G的四邊相等 ， 則 P→Q：如果 G是正方形 ， 則 G的四邊相等 。 蘊含式 P→Q可以用多種方式陳述： “ 若 P， 則 Q”。 “P是 Q的充分條件 ” 。 “Q是 P的必要條件 ” 。 “Q每當 P”。 “P僅當 Q”等 。 19/73 命題與命題聯(lián)結詞 ?給定命題 P→Q， 我們把 Q→P， ﹁ P→﹁ Q， ﹁Q→﹁ P分別叫作命題 P→Q的逆命題 ， 反命題和逆反命題 。 ?定義 ： 設 P， Q是任意兩個命題 ， 復合命題 “ P當且僅當 Q”稱為 P與 Q的等價式 (Equivalence)， 記作 P?Q， “ ?” 為等價聯(lián)結詞 。 P?Q為真當且僅當 P， Q同為真假 。 例如 ， P：合肥是安徽省會 ， Q：鳥會飛 ， 則 P?Q：合肥是安徽省會當且僅當鳥會飛 。 如果 P?Q是真 ， 則 P→Q和 Q→P是真 ， 反之亦然 ，因此 P?Q也讀作 “ P是 Q的充要條件 ” 或 “ P當且僅當 Q”。 20/73 命題與命題聯(lián)結詞 ?五個聯(lián)結詞 聯(lián)結詞 記號 表達式 讀法 真值結果 否定 172。 172。P 非 P 172。P 為真當且僅當 P為假 合取 ∧ P ∧ Q P且 Q P ∧ Q為真當且僅當P， Q同為真 析取 ∨ P ∨ Q P或 Q P ∨ Q為真當且僅當P， Q至少一個為真 蘊含 → P→Q 若 P則 Q P→Q為假當且僅當 P為真 Q為假 等價 ? P?Q P當且僅當Q P?Q為真當且僅當 P，Q同為真假 21/73 命題與命題聯(lián)結詞 ?一般約定： a)：運算符 (聯(lián)結詞 )結合力強弱順序為： 172。 ； ∧ ，∨ ； →， ?；凡符合此順序的 ， 括號可省略 。 b)：相同的運算符 ， 從左到右次序計算時 ， 括號可省去 。 c)：最外層括號可省 。 如 ， (172。((P ∧ 172。Q) ∨ R) →((R ∨ P)∨ Q)) 172。(P ∧ 172。Q ∨ R) →R ∨ P∨ Q ?22/73 ?例 ：符號化下列命題。 a)：他既有理論知識又有實踐經(jīng)驗 b)： i. 如果明天不是雨夾雪則我去學校 ii. 如果明天不下雨并且不下雪 ， 則我去學校 iii. 如果明天下雨或下雪則我不去學校 iv. 明天我將風雨無阻一定去學校 v. 當且僅當明天不下雪并且不下雨時我才去 學校 命題與命題聯(lián)結詞 23/73 命題與命題聯(lián)結詞 c)：說小學生編不了程序 ， 或說小學生用不了個人計算機 ， 那是不對的 。 d)：若不是他生病了或出差了 ， 我是不會同意他不參加學習的 。 e)：如果我上街了 ， 我就去書店看看 ， 除非我很累 。 24/73 命題與命題聯(lián)結詞 ?注意： (1)172。是自然語言中的 “ 非 ” ﹑ “不 ” 和 “ 沒有 ” 等的邏輯抽象 (2)∧ 是自然語言中的 “ 并且 ” ﹑ “既 … 又 … ” ﹑ “且 ” ﹑ “和 ” 等的邏輯抽象