離散數(shù)學(xué)

研究對(duì)象離散數(shù)學(xué)數(shù)學(xué)的幾個(gè)分支的總稱，以研究離散量的結(jié)構(gòu)和相互間的關(guān)系為主要目標(biāo)，其研究對(duì)象一般是有限個(gè)或可數(shù)無(wú)窮個(gè)元素.離散量與連續(xù)量相對(duì)，離散量是指分散開(kāi)來(lái)的、不存在中間值的量.比如，開(kāi)關(guān)v.s.音量旋鈕.

內(nèi)容數(shù)理邏輯(MathematicalLogic)集合論(SetTheory)組合論(Combinatorics)圖論(GraphTheory)數(shù)論(NumberTheory)教材

(TextBook)

離散數(shù)學(xué)

左孝凌等編著（上海科學(xué)技術(shù)文獻(xiàn)出版社）第一篇數(shù)理邏輯計(jì)算機(jī)是數(shù)理邏輯和電子學(xué)相結(jié)合的產(chǎn)物第二篇集合論集合：一種重要的數(shù)據(jù)結(jié)構(gòu)關(guān)系：關(guān)系數(shù)據(jù)庫(kù)的理論基礎(chǔ)函數(shù)：所有計(jì)算機(jī)語(yǔ)言中不可缺少的一部分第三篇代數(shù)系統(tǒng)計(jì)算機(jī)編碼和糾錯(cuò)碼理論數(shù)字邏輯設(shè)計(jì)基礎(chǔ)計(jì)算機(jī)使用的各種運(yùn)算第四篇圖論數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、計(jì)算機(jī)網(wǎng)絡(luò)原理的基礎(chǔ)1.平時(shí)成績(jī)占10%出勤率課堂紀(jì)律課上回答問(wèn)題作業(yè)完成情況2.期中考試占20%3.期末考試占70%

考核方法郭蕓Email:guoyun@蘇州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一篇

數(shù)理邏輯

關(guān)于邏輯的故事（一）

一人在尋找真理，別人問(wèn)他：“你真的不知道真理是什么嗎？”那個(gè)人說(shuō)：“當(dāng)然！”

別人又問(wèn)：“你既然不知道真理是什么，當(dāng)你找到真理的時(shí)候，你又如何辨別出來(lái)呢？如果你辨別得出真理與否，那說(shuō)明你已經(jīng)知道了真理是什么，又何來(lái)尋找呢？”

上帝真的是萬(wàn)能的嗎?1

如果上帝創(chuàng)造出了一塊連他自己都舉不起來(lái)的石頭，

如果上帝不能創(chuàng)造出一塊連自己都舉不起來(lái)的石頭，

所以不管上帝是否能創(chuàng)造出這么一塊石頭，他都不是萬(wàn)能的.那么上帝就不是萬(wàn)能的，因?yàn)橛幸粔K石頭它舉不起來(lái).

讓我們來(lái)提出一個(gè)問(wèn)題：上帝是否能創(chuàng)造出一塊連自己都舉不起來(lái)的石頭？那么上帝也不是萬(wàn)能的，因?yàn)橛幸粔K石頭它創(chuàng)造不出來(lái).

1此問(wèn)題與宗教或信仰無(wú)關(guān).這里我們只談及邏輯.

關(guān)于邏輯的故事（二）

據(jù)傳，古希臘有一個(gè)叫歐提勒士的年輕人，向當(dāng)時(shí)著名的智者普羅達(dá)哥拉斯學(xué)習(xí)法律，雙方簽了一個(gè)合同，結(jié)束學(xué)業(yè)之后，學(xué)生付給老師一半學(xué)費(fèi)，另一半學(xué)費(fèi)則要等到學(xué)生第一次出庭打贏官司，再支付.

可是學(xué)生一直沒(méi)有打贏官司，剩下的一半學(xué)費(fèi)老師遲遲沒(méi)有拿到.老師終于等不及了，就向法庭起訴，要學(xué)生支付另一半學(xué)費(fèi).

老師說(shuō)：“如果你打贏這場(chǎng)官司，依照合同，你得把另一半學(xué)費(fèi)付給我；如果你打輸這場(chǎng)官司，那么根據(jù)法庭判決，你也得把另一半學(xué)費(fèi)付給我.所以，不管你這場(chǎng)官司是贏是輸，你都要把學(xué)費(fèi)給我.”

學(xué)生反駁道：“如果我打輸這場(chǎng)官司，依照合同，我不需要把另一半學(xué)費(fèi)付給你；如果我打贏這場(chǎng)官司，那么根據(jù)法庭判決，我也不需要把另一半學(xué)費(fèi)付給你.所以，不管我這場(chǎng)官司是輸是贏，我都不需要把學(xué)費(fèi)給你.”

關(guān)于邏輯的故事（三）

邏輯推理俱樂(lè)部大廳門(mén)口貼著一張布告：“歡迎你參加推理俱樂(lè)部！如果你愿意，并且通過(guò)推理取得一張申請(qǐng)表，就可以獲得會(huì)員資格了！”

走進(jìn)大廳，只見(jiàn)桌子上擺著兩個(gè)盒子：一個(gè)圓盒子，一個(gè)方盒子.

圓盒子上寫(xiě)著一句話：“申請(qǐng)表不在此盒中”.方盒子上寫(xiě)著一句話：“這兩句話中只有一句是真話”.

如果你想獲得會(huì)員的資格，那么你是從圓盒子中，還是從方盒子中去取申請(qǐng)表呢？設(shè)方盒子上寫(xiě)的話(“這兩句話中只有一句是真話”)是真的，

推出圓盒子上的話(“申請(qǐng)表不在此盒中”)是假的，推出申請(qǐng)表在圓盒子中.

推出圓盒子上的話(“申請(qǐng)表不在此盒中”)也是假的，

推出申請(qǐng)表在圓盒子中.設(shè)方盒子上寫(xiě)的話(“這兩句話中只有一句是真話”)是假的，或者方盒子上的話是真的，或者方盒子上的話是假的.總之，申請(qǐng)表在圓盒子中.

關(guān)于邏輯的故事（四）

邏輯學(xué)

研究人的思維形式和規(guī)律的科學(xué)稱為邏輯學(xué).由于研究的對(duì)象和方法各有側(cè)重而又分為辯證邏輯形式邏輯數(shù)理邏輯

數(shù)理邏輯簡(jiǎn)介數(shù)理邏輯是運(yùn)用數(shù)學(xué)方法研究推理的科學(xué).數(shù)理邏輯又叫符號(hào)邏輯，因?yàn)樗闹饕ぞ呤欠?hào)體系.數(shù)理邏輯的核心是把邏輯推理符號(hào)化，即變成像數(shù)學(xué)演算一樣的邏輯演算.

數(shù)理邏輯的簡(jiǎn)單歷史——三個(gè)階段Aristotle：形式邏輯(主詞和謂詞邏輯).0初始階段(1660s-19世紀(jì)末)：將數(shù)學(xué)應(yīng)用于邏輯(Leibniz,George,Boole,DeMorgan).1過(guò)渡階段(19世紀(jì)末-1940前后)：邏輯應(yīng)用于數(shù)學(xué).2成熟階段(1930s-1970s)：成為數(shù)學(xué)的獨(dú)立分支.3在本課程中主要介紹命題邏輯和謂詞邏輯.它們對(duì)電子元件設(shè)計(jì)和性質(zhì)分析，對(duì)邏輯程序設(shè)計(jì)語(yǔ)言的研制具有十分重要的意義。命題公式及分類公式的等價(jià)推理理論本章要點(diǎn)命題的概念及其符號(hào)化其它聯(lián)結(jié)詞對(duì)偶與范式

第一章命題邏輯公式的蘊(yùn)含關(guān)系

命題：具有確定真值的陳述句.真值只有兩個(gè)：真或假a

，記作True和False，分別用符號(hào)T和F表示(也可以分別用1和0表示).只有說(shuō)法“真值為真”或“真值為假”——沒(méi)有“假值”一說(shuō).一、命題的概念及其符號(hào)化(一)命題的概念例1.1.1

判斷下列句子中哪些是命題.解題思想：判斷一個(gè)句子是否為命題,一看它是否為陳述句；二看它的真值是否唯一.一、命題的概念及其符號(hào)化1.4是素?cái)?shù).2.是無(wú)理數(shù).3.x大于y.4.外太空有生命.5.明年元旦蘇州是晴天.7.大于嗎？8.請(qǐng)不要吸煙！9.這朵花真美麗！10.我正在說(shuō)謊.6.1+11=100.√√√√(悖論)××××××(二)命題的符號(hào)化可以用以下兩種形式將命題符號(hào)化：用大寫(xiě)字母例如，P:今天天氣晴好.用帶下標(biāo)的大寫(xiě)字母或用數(shù)字例如，A3(或[3]):今天天氣晴好.上述的P,

A3

和[3]稱為命題標(biāo)識(shí)符.一、命題的概念及其符號(hào)化(三)與命題相關(guān)的幾個(gè)概念原子命題：不能再細(xì)分的命題復(fù)合命題：由原子命題和命題聯(lián)結(jié)詞構(gòu)成.例1.1.2判斷下列命題哪些是原子命題，哪些是復(fù)合命題.明天下雪.4是素?cái)?shù)”.明天下雪或明天下雨.原子命題復(fù)合命題原子命題一、命題的概念及其符號(hào)化(三)與命題相關(guān)的幾個(gè)概念命題常量(propositionconstants)表示具體命題的命題標(biāo)識(shí)符；例如，P:今天天氣晴好.則P是命題常量.命題變?cè)?propositionvariable)未指定具體命題，可以代表任意命題的命題標(biāo)識(shí)符；比如討論運(yùn)算規(guī)律時(shí)使用的命題標(biāo)識(shí)符.命題變?cè)皇敲}.指派(assignments)命題變?cè)靡粋€(gè)特定命題取代，從而成為一個(gè)命題，這個(gè)過(guò)程稱為對(duì)命題變?cè)概?集合{T,F}是命題變?cè)闹涤?一、命題的概念及其符號(hào)化聯(lián)結(jié)詞是復(fù)合命題的重要組成部分，又稱為邏輯運(yùn)算符.常用的有五種：否定合取析取條件雙條件原子命題+聯(lián)結(jié)詞=復(fù)合命題(四)聯(lián)結(jié)詞一、命題的概念及其符號(hào)化否定(negation)設(shè)P為命題，則P的否定是一個(gè)新的命題，記為P，讀作“非P”.若P為T(mén)，則

P為F；若P為F,則

P為T(mén).P

PTFFT一、命題的概念及其符號(hào)化合取(conjunction)如果P和Q是命題，那么“P并且Q”

也是命題，記為PQ，稱為P與

Q的合取，讀作“P與

Q”或“P并且Q”.PQ真值為T(mén)，當(dāng)且僅當(dāng)P和Q真值都為T(mén).PQP

QTTTTFFFTFFFF一、命題的概念及其符號(hào)化例1.1.3設(shè)P:

這些都是男生，則

P:這些不都是男生.能寫(xiě)成“這些都不是男生”嗎？例1.1.4設(shè)P:

2是素?cái)?shù)，Q:2是偶數(shù)，則PQ

:2是素?cái)?shù)，并且是偶數(shù).No.一、命題的概念及其符號(hào)化析取(disjunction)如果P和Q是命題，那么“P或Q”

也是命題，記為PQ，稱為P與

Q的析取，讀作“P或

Q”.PQ真值為T(mén)，當(dāng)且僅當(dāng)P或Q至少有一個(gè)真值為T(mén).PQP

QTTTTFTFTTFFF析取指的是“可兼或”.“或”的語(yǔ)意：“可兼或”，“排斥或”(也稱“異或”，“不可兼或”)

，表示大概、大約.一、命題的概念及其符號(hào)化“可兼或”(inclusive-or)和“排斥或”(exclusive-or)例1.1.5將下列命題符號(hào)化：(1)張三愛(ài)唱歌或愛(ài)聽(tīng)音樂(lè).(2)張三只能挑202或203房間.解：(1)設(shè)P:張三愛(ài)唱歌，Q:張三愛(ài)聽(tīng)音樂(lè)，這里的“或”是“可兼或”，也稱“相容或”即兩者可以同時(shí)為真，因此可以符號(hào)化為PQ.(2)設(shè)U:張三挑202房間，V:張三挑203房間，這里的“或”是“排斥或”，因此可以符號(hào)化為

(UV)

(UV)一、命題的概念及其符號(hào)化例1.1.6將下列命題符號(hào)化：(1)小王是跳遠(yuǎn)冠軍或百米賽跑冠軍.(2)小王在宿舍或在圖書(shū)館.(3)選小王或小李中的一人當(dāng)班長(zhǎng).解：其中P:小王是跳遠(yuǎn)冠軍，Q:小王是百米賽跑冠軍.(1)PQ.(可兼或)

(2)(PQ)

(PQ)(排斥或)其中P:小王在宿舍，Q:小王在圖書(shū)館.

(3)(PQ)

(PQ)(排斥或)其中P:選小王當(dāng)班長(zhǎng)，Q:選小李當(dāng)班長(zhǎng).一、命題的概念及其符號(hào)化條件(implication)給定兩個(gè)命題P和Q，其條件命題是一個(gè)復(fù)合命題，記為PQ，讀作“如果P，那么Q”或“若P，則Q”.當(dāng)且僅當(dāng)P的真值為T(mén),Q的真值為F時(shí)，PQ真值為F.

稱P為前件(或前提)，Q為后件(或結(jié)論).PQP

QTTTTFFFTTFFT一、命題的概念及其符號(hào)化關(guān)于PQ真值表的注解在自然語(yǔ)言中，“如果P，那么Q”中的前件P與后件Q往往具有某種內(nèi)在聯(lián)系.而在數(shù)理邏輯中，P與Q可以無(wú)任何內(nèi)在聯(lián)系.例如：如果雪是黑的，那么太陽(yáng)從西方出來(lái).在數(shù)學(xué)或其它自然科學(xué)中，“如果P，那么Q”往往表達(dá)的是前件P為真，后件Q也為真的推理關(guān)系.

但在數(shù)理邏輯中，作為一種“善意推定”的規(guī)定，當(dāng)P為假時(shí)，無(wú)論Q是真是假，PQ均為真.

也就是說(shuō)，只有P為T(mén)并且Q為F這一情況，才能使得復(fù)合命題PQ為F.什么是“善意的推定”？一、命題的概念及其符號(hào)化善意的推定例1.1.7張三對(duì)李四說(shuō)：“我去圖書(shū)館，一定幫你借那本書(shū)”.

可以將這句話表示為命題PQ(P:張三去圖書(shū)館，Q:張三借那本書(shū)).

后來(lái)張三因有事未去圖書(shū)館，即P為F，此時(shí)按規(guī)定PQ為

我們可理解為張三講了真話，即他要是去圖書(shū)館，我們相信他一定會(huì)幫李四借書(shū).這就是所謂“善意的推定”.T.一、命題的概念及其符號(hào)化例1.1.8將下列命題符號(hào)化：(1)只要天不下雨，我就騎自行車上班.(2)只有天不下雨，我才騎自行車上班.解：設(shè)P:天下雨，Q:我騎車上班.

(1)(天不下雨是騎車上班的充分條件.)

(2)(如果騎車上班，一定天不下雨.)

PQ.

QP或PQ.一、命題的概念及其符號(hào)化例1.1.9將下列命題符號(hào)化：(1)除非天氣好，否則我不會(huì)去公園的.(2)我將去鎮(zhèn)上，僅當(dāng)我有時(shí)間時(shí).解：設(shè)P:今天天氣好，Q:我去公園.(1)含義：我去公園必定是天氣好，至于天氣好是否去公園，在命題中沒(méi)有涉及.

QP.PQ.(2)設(shè)P:我將去鎮(zhèn)上，Q:我有時(shí)間.一、命題的概念及其符號(hào)化注以下句式均可符號(hào)化PQ：“如P，則Q”；“因?yàn)镻，所以Q”；“只要P，就Q”；“P，僅當(dāng)Q”；“只有Q，才P”；“除非Q，才P”；“除非Q，否則非P”.(除非天氣好，否則我不會(huì)去公園的.)(我將去鎮(zhèn)上，僅當(dāng)我有時(shí)間時(shí).)(只有天不下雨，我才騎自行車上班.)一、命題的概念及其符號(hào)化雙條件

(two-way-implication)給定兩個(gè)命題P和Q，其復(fù)合命題PQ稱作雙條件命題，讀作“P當(dāng)且僅當(dāng)Q”.PQ真值為T(mén)，當(dāng)且僅當(dāng)P和Q同時(shí)為T(mén)，或同時(shí)為F.雙條件聯(lián)結(jié)詞也可以記作”iff”.PQP

QTTTTFFFTFFFT一、命題的概念及其符號(hào)化例1.1.10分析下列各命題的真值：(1)2+2=4，當(dāng)且僅當(dāng)3是奇數(shù).(2)2+2=4，當(dāng)且僅當(dāng)3不是奇數(shù).(3)2+24，當(dāng)且僅當(dāng)3是奇數(shù).(4)2+24，當(dāng)且僅當(dāng)3不是奇數(shù).解：設(shè)P:2+2=4，Q:3是奇數(shù).(1)

PQ，真值為T(mén)(因P,Q皆為真)；(2)

P

Q，真值為F(因P為真，Q為假)；(3)

PQ，真值為F(因

P為假,Q為真)；(4)

P

Q，真值為T(mén)(因

P,Q皆為假).一、命題的概念及其符號(hào)化例1.1.11設(shè)P:天下雨，Q:草木枯黃，則天不下雨；

P:PQ:

PQ:PQ:PQ:天不下雨并且草木枯黃；天不下雨或草木枯黃；如果天不下雨，那么草木枯黃；天不下雨當(dāng)且僅當(dāng)草木枯黃.一、命題的概念及其符號(hào)化張三不是不聰明，而是不用功.(2)李文與李武是兄弟.(3)只有睡好覺(jué)才能恢復(fù)疲勞.(4)除非你努力，否則你將失敗.(5)如果我上街，我就去書(shū)店看看，除非我很累.解：其中,P:張三聰明.Q:張三用功.(1)

(P)

Q,其中,P:李文與李武是兄弟.(原子命題)(2)

P,其中,P:睡好覺(jué).Q:恢復(fù)疲勞(P是Q的必要條件.)(3)

Q

P,其中,P:你努力.Q:你將失敗.(4)

QP,其中,P:我很累.Q:我上街.R:我去書(shū)店看看.