離散數(shù)學(xué)課件：1-1 命題的概念及其符號化

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

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

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

(TextBook)

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

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

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

數(shù)理邏輯

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

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

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

上帝真的是萬能的嗎?1

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

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

所以不管上帝是否能創(chuàng)造出這么一塊石頭，他都不是萬能的.那么上帝就不是萬能的，因為有一塊石頭它舉不起來.

讓我們來提出一個問題：上帝是否能創(chuàng)造出一塊連自己都舉不起來的石頭？那么上帝也不是萬能的，因為有一塊石頭它創(chuàng)造不出來.

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

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

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

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

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

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

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

邏輯推理俱樂部大廳門口貼著一張布告：“歡迎你參加推理俱樂部！如果你愿意，并且通過推理取得一張申請表，就可以獲得會員資格了！”

走進大廳，只見桌子上擺著兩個盒子：一個圓盒子，一個方盒子.

圓盒子上寫著一句話：“申請表不在此盒中”.方盒子上寫著一句話：“這兩句話中只有一句是真話”.

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

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

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

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

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

邏輯學(xué)

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

數(shù)理邏輯簡介數(shù)理邏輯是運用數(shù)學(xué)方法研究推理的科學(xué).數(shù)理邏輯又叫符號邏輯，因為它的主要工具是符號體系.數(shù)理邏輯的核心是把邏輯推理符號化，即變成像數(shù)學(xué)演算一樣的邏輯演算.

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

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

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

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

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

A3

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

P為F；若P為F,則

P為T.P

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

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

Q的合取，讀作“P與

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

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

這些都是男生，則

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

2是素數(shù)，Q:2是偶數(shù)，則PQ

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

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

Q的析取，讀作“P或

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

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

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

(UV)

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

(2)(PQ)

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

(3)(PQ)

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

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

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

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

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

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

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

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

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

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

PQ.

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

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

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

QTTTTFFFTFFFT一、命題的概念及其符號化例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(因P,Q皆為真)；(2)

P

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

PQ，真值為F(因

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

P

Q，真值為T(因

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

P:PQ:

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

(P)

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

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

Q

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

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