離散數學DiscreteMathematics

陳明

Mobilemail:mingchen_gang@163.com信息科學與工程學院，J13-108二零一三年九月離散數學課程簡介◆離散數學，是現代數學的一個重要分支，是計算機科學中基礎理論的核心課程，是整個計算機學科的專業基礎課。◆離散數學是以研究離散量的結構和相互間的關系為主要目標，其研究對象一般地是有限個或可數個元素，因此它充分描述了計算機科學離散性的特點。◆離散數學是隨著計算機科學的發展而逐步建立的，它形成于七十年代初期，是一門新興的工具性學科。離散數學離散數學的應用◆關系型數據庫的設計（關系代數）◆表達式解析（樹）◆編譯技術、程序設計語言（代數結構）◆人工智能、自動推理、機器證明（數理邏輯）◆網絡路由算法（圖論）◆游戲中的人工智能算法（圖論、樹、博弈論）◆專家系統（集合論、數理邏輯—知識和推理規則的計算機表達）◆軟件工程—團隊開發—時間和分工的優化（圖論—網絡、劃分）◆(各種)算法的構造、正確性的證明和效率的評估（離散數學的各分支）離散數學教材左孝凌，李為鑒，劉永才編著．離散數學．上海：上海科學技術文獻出版社,1982主要參考教材:孫吉貴，楊鳳杰，歐陽丹彤，李占山編著．離散數學．高等教育出版社，2002離散數學學習要求◆本課程特點

定義+定理+例題◆多做習題，認真獨立完成作業

離散數學本課程主要內容◆第一篇數理邏輯

命題邏輯、謂詞邏輯◆第二篇集合論

集合與關系、函數◆第三篇代數系統

代數結構、格和布爾代數◆第四篇圖論

圖論離散數學第一篇數理邏輯

離散數學◆思維的形式結構包括了概念，判斷和推理之間的結構和聯系，其中概念是思維的基本單位，通過概念對事物是否具有某種屬性進行肯定或否定的回答，這就是判斷；由一個或幾個判斷推出另一判斷的思維形式，就是推理。◆研究推理有很多方法，用數學方法來研究推理的規律稱為數理邏輯，即通過引入表意符號研究推理，因此，數理邏輯又名符號邏輯。現代數理邏輯可分為四論、兩演算：證明論、模型論、遞歸函數論、公理化集合論，以及命題演算和謂詞演算，這里介紹的是數理邏輯最基本的內容：命題邏輯和謂詞邏輯。離散數學設有下列情況，結論是否有效？

(a)或者是天晴，或者是下雨。

(b)如果是天晴，我去看電影。.(c)如果我去看電影，我就不看書。

結論：如果我在看書則天在下雨。

解若設M：天晴。Q：下雨。

S：我看電影。R：我看書。故本題即證：M∨Q，M→S，S→┐R，推出R→Q離散數學邏輯學中著名的三段論方法，是由一個大前提，一個小前提推出結論的方法。例如：

所有的人都是要死的。蘇格拉底是人。所以蘇格拉底是要死的。離散數學第一章命題邏輯目標語言：就是表達判斷的一些語言的匯集。目標語言和一些符號公式構成了數理邏輯的形式符號體系。離散數學一、命題1、定義能表達判斷的陳述句，稱作命題（Proposition）。例：判斷下列語句是否為命題:(1)地球外存在智慧生物。(2)1＋1=10。(3)今天下雨。(4)你今年暑假去旅行嗎？（疑問句）(5)克里特島人說：“克里特島人是說謊話者”。（悖論）陳述句：述說一件事情的句子，句末用句號。祈使句：要求或者希望別人做什么事或者不做什么事時用的句子，句末用句號或感嘆號。疑問句：提出問題的句子，句末用問號。感嘆句：帶有濃厚感情的句子，句末用感嘆號。悖：相反。悖論：自相矛盾的陳述。1-1命題及其表示法

離散數學命題所表達的判斷結果稱為命題的真值（值）。真值只有“真”和“假”兩種，記作True（真）和False（假），分別用符號T（1）和F（0）表示。由于命題只有兩種真值，所以稱這種邏輯為二值邏輯。命題的真值是具有客觀性質的，而不是由人的主觀決定的。

2、真值（truthvalue）離散數學

下面的語句中，哪些語句是命題，如果是命題，指出它的真值：

（1）能整除7的正整數只有1和7本身。

（2）對于每一個正整數n存在一個大于n的素數。

（3）煤是白的。

（4）雪是黑的。

（5）在宇宙中地球是唯一有生命的星球。

（6）1+101=110

（7）買兩張星期六的電影票。（祈使句）

（8）全體立正！（祈使句）

（9）明天是否開會？（疑問句）

（10）天氣多好啊！（感嘆句）

（11）我正在說謊。（悖論）

（3）和（4）是命題，真值為F。（1）、（2）是命題，真值為T。祈使句、疑問句、感嘆句等都不能作為命題，悖論無真值，也不能作為命題。語句（7）—（11）都不是命題。

（5）是命題，有確定真值，只是目前還不知道。

（6）不是命題，在二進制中為T，在十進制中為F，故需根據上下文才能確定其真假。

離散數學命題有兩種類型：原子命題和復合命題原子命題：不能分解為更簡單的陳述句。復合（分子）命題：由聯結詞、標點符號和原子命題復合構成的命題。前面例子中：（1～5）是原子命題；“我學英語，或者我學日語”是復合命題。

3、分類離散數學

練習：指出下列語句哪些是命題，哪些不是命題，如果是命題，指出它的真值。（見教材第8頁習題（1））

a）離散數學是計算機科學系的一門必修課。

b）小李有空嗎？

c）明天我去看電影。

d）請勿隨地吐痰！

e）不存在最大質數。

f）如果我掌握了英語、法語，那么學習其他歐洲語言就容易的多。

g）x=3

h）我們要努力學習。

離散數學解：

a）離散數學是計算機科學系的一門必修課。是命題，真值為T。

b）小李有空嗎？疑問句，不是命題。

c）明天我去看電影。是命題，真值要根據具體情況確定。

d）請勿隨地吐痰！祈使句，不是命題。

e）不存在最大質數。是命題，真值為T。

f）如果我掌握了英語、法語，那么學習其他歐洲語言就容易的多。是命題，真值為T。

g）x=3不是命題，x=3的真假由x確定，當x取3時句子為真，當x取其他值時句子為假。

h）我們要努力學習。祈使句，不是命題。

a），c），e）是原子命題，f）是復合命題。

離散數學1、命題標識符：表示命題的符號稱為命題標識符。在數理邏輯中，使用大寫字母，或帶下標的大寫字母，或用方括號括起的數字表示命題。

例：P：今天下雨。

“今天下雨”是一個命題，P是命題標識符。

A1：今天下雨。

[12]：今天下雨。

A1

、

[12]也是命題標識符。

2、命題常量：一個命題標識符如表示確定的命題，就稱為命題常量。

3、命題變元：如果命題標識符只表示任意命題的位置標志，就稱為命題變元。命題變元可以表示任意命題，所以它不能確定真值，故命題變元不是命題。當命題變元用一個特定命題取代時，才能確定真值，這稱為對命題變元進行指派。

4、原子變元：當命題變元表示原子命題時，該變元稱為原子變元。二、命題的表示法離散數學1-2聯結詞

在數理邏輯中，復合命題是由原子命題與邏輯聯結詞組合而成，命題的連接方式叫做命題聯結詞或命題運算符。聯結詞是復合命題中的重要組成部分，為了便于書寫和進行推演，必須對聯結詞作出明確規定并符號化。我們主要討論下述五種聯結詞（亦稱真值聯結詞，邏輯聯結詞或邏輯運算符），借助它們組成復合命題。

離散數學（1）否定（Negation）

（一元聯結詞）

1.定義定義1-2.1設P為一命題，P的否定是一個新的命題，記作┐P。若P為T，┐P為F；若P為F，┐P為T。聯結詞“┐”表示命題的否定，稱為否定聯結詞或否定詞，讀作“非”或“not”。否定聯結詞有時亦可記作“ˉ”。P┐PTFFT2.真值表（truthtable）表1-2.1

命題P與其否定┐P的關系如表1-2.1所示。1/2離散數學“否定”的意義僅是修改了命題的內容，它是一個一元運算，我們仍把它看作為聯結詞。自然語言中的“不”、“無”、“沒有”等詞在命題演算中常與“非”相當。例：P：今天下雨。

┐P：今天不下雨。

┐P：今天無雨。

┐P：今天沒有下雨。

P：上海是一個大城市。

┐P：上海不是一個大城市。

┐P：上海是一個不大的城市。練習：P：一個世紀是一百年。寫出┐P。2/2離散數學（2）合取（Conjunction）

（二元聯結詞）

1.定義定義1-2.2兩個命題P和Q的合取是一個復合命題，記作P∧Q。當且僅當P、Q同時為T時，P∧Q為T，在其他情況下，P∧Q的真值都是F。聯結詞“∧”稱為合取詞，讀作“和”或“and”。2.真值表聯結詞“∧”的定義如表1-2.2所示。PQP∧QTT

TTFFFTFFFF表1-2.2

表1-2.2中給出復合命題P∧Q為T當且僅當P、Q同時為T。

1/7離散數學與“和”有相同意義的漢字還有“與”、“以及”、“并且”、“而且”等。例：P：今天下雨。

Q：明天下雨。上述命題的合取為

P∧Q：今天下雨而且明天下雨。

P∧Q：今天與明天都下雨。

P∧Q：這兩天都下雨。顯然只有當“今天下雨”與“明天下雨”都是真時，“這兩天都下雨”才是真的。2/7離散數學

合取的概念與自然語言中的“與”意義相似，但并不完全相同。例如

P：我們去看電影。

Q：房間里有十張桌子。上述命題的合取為

P∧Q：我們去看電影與房間里有十張桌子。在自然語言中，上述命題是沒有意義的，因為P與Q沒有內在聯系，但作為數理邏輯中P和Q的合取P∧Q來說，它仍可成為一個新的命題，只要按照定義，在P、Q分別取真值后，P∧Q的真值也必確定。3/7離散數學

例如

①P：雪是白的

Q：地球是行星。

P∧Q：雪是白的與地球是行星。

P∧Q的真值為T。②P：雪是白的

Q：地球是恒星。

P∧Q：雪是白的與地球是恒星。

P∧Q的真值為F。4/7離散數學

③P：雪是黑的

Q：地球是行星。

P∧Q：雪是黑的與地球是行星。

P∧Q的真值為F。④P：雪是黑的

Q：地球是恒星。

P∧Q：雪是黑的與地球是恒星。

P∧Q的真值為F。5/7離散數學

命題聯結詞“合取”甚至可以將兩個互為否定的命題聯結在一起。這時，其真值永為F。

P：今天下雨。

Q：今天不下雨。（此時Q既是┐P）

P∧Q：今天下雨與今天不下雨。

P∧Q的真值為F。

命題聯結詞“合取”也可以將若干個命題聯結在一起。

“合取”是一個二元運算。

6/7離散數學

注意，并非所有的“和”、“與”、“并且”均可用“∧”表示。例如“李華和張南是表兄弟。”“王麗與王萍是堂姐妹”“他打開箱子并且取出一件衣服來。”這三句中的“和”、“與”、“并且”就不能用“∧”表示。

練習：1）P：一個世紀是一百年。

Q：4是偶數。寫出P∧Q并確定其真值。

2）P：5是一個整數，Q：5不是一個奇數P∧Q：5是一個整數且5不是一個奇數P∧Q：5是一個整數但5不是一個奇數7/7離散數學（3）析取（Disjunction）

（二元聯結詞）

1.定義定義1-2.3兩個命題P和Q的析取是一個復合命題，記作P∨Q。當且僅當P、Q同時為F時，P∨Q為F，否則P∨Q的真值為T。聯結詞“∨”稱為合取詞，讀作“或”或“or”。PQP∨QTTTTFTFTTFF

F2.真值表聯結詞∨的定義如表1-2.3所示。表1-2.3表1-2.3中給出復合命題P∨Q為F當且僅當P、Q同時為F。1/4離散數學

例：P：燈泡壞了。

Q：開關壞了。上述命題的析取為

P∨Q：燈泡壞了或開關壞了。2/4離散數學注意，并非所有的“或”可用“∨”表示。例如，“我向東行或向西行。”該語句中的“或”稱為“排斥或”，因為事實上一個人不會既向東行，又向西行。析取“∨”指的是“可兼或”。例如，他可能是100米或400米賽跑的冠軍。這里

P：他可能是100米賽跑的冠軍。

Q：他可能是400米賽跑的冠軍。

P∨Q：他可能是100米或400米賽跑的冠軍。3/4離散數學

還有一些漢語中的“或”字實際上不是命題聯結詞。例如，他昨天做了二十或三十道習題。這里的“或”字只表示了習題的近似數目，不能用聯結詞“∨”表達。

練習：P：雪是黑的。

Q：4是偶數。寫出P∨Q并確定其真值。4/4離散數學（4）條件（Condition）

（二元聯結詞）1.定義定義1-2.4給定兩個命題P和Q，其條件命題是一個復合命題，記作P→Q，讀作“如果P，那么Q”或“若P則Q”。當且僅當P的真值為T，Q的真值為為F時，P→Q的真值為F，否則P→Q的真值為T。我們稱P為前件，Q為后件。PQP→QTTTTFFFTTFFT2.真值表聯結詞→的定義如表1-2.4所示。

表1-2.41/4離散數學

例1如果我得到這本小說，那么我今夜就讀完它。例2如果雪是黑的，那么太陽從西方出。上述二個例子都可用條件命題P→Q表達。在例1中，P：我得到這本小說，Q：我今夜就讀完它。P的真值為T，Q的真值為T，P→Q的真值為T。如果P的真值為T，Q的真值為F，P→Q的真值為F。如果P的真值為F，Q的真值為T，P→Q的真值為T。如果P的真值為F，Q的真值為F，P→Q的真值為T

在例2中，P：雪是黑的，Q：太陽從西方出。P的真值為F，Q的真值為F，P→Q的真值為T。2/4離散數學在自然語言中，“如果…”與“那么…”之間常常是有因果聯系的，否則就沒有意義，但對條件命題P→Q來說，只要P、Q能夠分別確定真值，P→Q即成為命題。自然語言中對“如果…、則…”這樣的語句，當前提為假時，結論不管真假，這個語句的意義，往往無法判斷。而在條件命題中，規定為“善意的推定”，即前提為F時，條件命題的真值都取為T。注意：3/4離散數學在數學上和有些邏輯學的書籍中，“若P則Q”亦可叫作P蘊含Q，而本書在條件命題中將避免使用“蘊含”一詞，因為在以后將另外定義“蘊含”這個概念。4/4離散數學(5)雙條件（DoubleCondition）

（二元聯結詞）1.定義定義1-2.5給定兩個命題P和Q，其復合命題PQ稱作雙條件命題，讀作“P當且僅當Q”，當P和Q的真值相同時，PQ的真值為T，否則PQ的真值為F。

PQPQTTTTFFFTFFFT表1-2.52.真值表聯結詞“”的定義可如表1-2.5所示。

1/2離散數學

例1兩個三角形全等，當且僅當它們的三組對應邊相等。例22+2＝4當且僅當雪是白的。上面三個例子都可用雙條件命題PQ來表示。與前面的聯結詞一樣，雙條件命題也可以不顧其因果聯系，而只根據聯結詞定義確定真值。雙條件聯結詞亦可記作“”或“iff”。它亦是二元運算。應強調指出的是：復合命題的真值只取決于各原子命題的真值，而與它們的內容、含義無關，與原子命題之間是否有關系無關。理解和掌握這一點是至關重要的。

2/2離散數學

學習本節要掌握下列概念：

命題能表達判斷的語句，并具有確定真值的陳述句。

真值一個命題總具有一個“值”，稱為真值。真值只有真和假兩種，分別記為T和F。

原子命題不能分解為更簡單的陳述句，稱為原子命題。

復合命題由聯結詞、標點符號和原子命題復合構成的命題，稱為復合命題。復合命題亦稱分子命題。

命題標識符表示命題的符號。

命題常量一個命題標識符表示確定的命題，該標識符稱作命題常量。

命題變元命題標識符如僅是表示任意命題的位置標志，就成為命題變元。

原子變元當命題變元表示原子命題時，該變元稱原子變元。

小結離散數學本節給出了如下五種聯結詞的定義：

否定設P為一命題，P的否定是一個新的命題，記作┐P。若P為T，┐P為F；若P為F，┐P為T。

合取兩個命題P和Q的合取是一個復合命題，記作P∧Q。當且僅當P、Q同時為T時，P∧Q為T，在其他情況下，P∧Q的真值都是F。

析取兩個命題P和Q的析取是一個復合命題，記作P∨Q。當且僅當P、Q同時為F時，P∨Q為F，否則P∨Q的真值為T。

條件給定兩個命題P和Q，其條件命題是一個復合命題，記作P→Q，讀作“如果P，那么Q”或“若P則Q”。當且僅當P的真值為T，Q的真值為為F時，P→Q的真值為F，否則P→Q的真值為T。

雙條件給定兩個命題P和Q，其復合命題PQ稱作雙條件命題，讀作“P當且僅當Q”，當P和Q的真值相同時，PQ的真值為T，否則PQ的真值為F。小結離散數學作業P8:（3）

離散數學例：(a)P:今晚我寫字,Q:今晚我看書。

P∨Q:今晚我寫字或看書

“或”字常見的含義有兩種:

◆“可兼或”,如上例中它不排除今晚既看書又寫字這種情況。運算符∨表示可兼或。

◆“排斥或”，例如“人固有一死,或重于泰山,或輕于鴻毛”中的“或”,它表示非此即彼,不可兼得。再比如：張明正在睡覺或者游泳。此兩題的或者是“排斥或”，也就是如果睡覺就不能游泳，如果游泳就不能睡覺。

P：張明在睡覺Q：張明在游泳可以翻譯為：

（P∧┓Q）Ⅴ(┓P∧Q)(可以利用真值表證明其等價于原命題)“可兼或”與“排斥或”的區別離散數學思考下列命題用哪個聯結詞：只要P，就Q；因為P，所以Q；P僅當Q；只有Q才P；除非Q才P；Q：你努力，P：你成功離散數學練習8頁（2）--（6）

(2)舉例說明原子命題和復合命題。

(3)設P表示命題“天下雪

Q表示命題“我將去鎮上。

R表示命題“我有時間”以符號形式寫出下列命題。

a)如果天不下雪和我有時間，那么我將去鎮上。

b)我將去鎮上，僅當我有時間時。

c)天不下雪。

d)天下雪，那么我不去鎮上。離散數學

(4)用漢語寫出一句子，對應下列每一個命題。

a)Q(R∧┐P)b)R∧Qc)(Q→R)∧(R→Q)(5)將下列命題符號化。

a)王強身體很好，成績也很好。

b)小李一邊看書，一邊聽音樂。

c)氣候很好或很熱。

d)如果a和b是偶數，則a+b是偶數。

e)四邊形ABCD是平行四邊形，當且僅當它的對邊平行．

f)停機的原因在于語法錯誤或程序錯誤。離散數學(6)將下列復合命題分成若干原子命題，

a)天氣炎熱且正在下雨。

b)天氣炎熱但濕度較低。

c)天正在下雨或濕度很高。

d)劉英與李進上山。

e)老王或小李是革新者。

f)如果你不看電影，那么我也不看電影。

g)我既不看電視也不外出，我在睡覺。

h)控制臺打字機既可作輸入設備，又可作輸出設備。離散數學

解答

(2)舉例說明原子命題和復合命題。原子命題：北京是中國的首都。復合命題：李毅和王強都是優秀學生。離散數學

(3)設P表示命題“天下雪”

Q表示命題“我將去鎮上。

R表示命題“我有時間”以符號形式寫出下列命題。

a)如果天不下雪和我有時間，那么我將去鎮上。（┐P∧R）→Qb)我將去鎮上，僅當我有時間時。R→Qc)天不下雪。┐Pd)天下雪，那么我不去鎮上。P→┐Q離散數學(4)用漢語寫出一句子，對應下列每