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