《離散數(shù)學(xué)》第一章1-3節(jié)

第一篇數(shù)理邏輯邏輯學(xué)：研究思維形式及思維規(guī)律的科學(xué)思維的形式結(jié)構(gòu)包括概念判斷推理先看下面一道推理題：

如果我學(xué)習(xí)，那么我的離散數(shù)學(xué)不會(huì)不及格。如果我不熱衷于玩撲克，那么我將學(xué)習(xí)。但我離散數(shù)學(xué)不及格。因此我熱衷于玩撲克。1整理ppt

請(qǐng)問(wèn)這個(gè)人說(shuō)得對(duì)嗎？他是怎么推導(dǎo)出來(lái)的呢？

要回答這樣的問(wèn)題，實(shí)際上就是看由一些諸如“離散數(shù)學(xué)不及格”這樣的前提能否推出“熱衷于玩撲克”這樣的結(jié)論來(lái)。這又需要經(jīng)歷如下過(guò)程：

(1)什么是前提？有哪些前提？

(2)結(jié)論是什么？

(3)根據(jù)什么進(jìn)行推理？

(4)怎么進(jìn)行推理？

2整理ppt數(shù)理邏輯用數(shù)學(xué)的方法來(lái)研究推理的規(guī)律統(tǒng)稱數(shù)理邏輯。為什么研究數(shù)理邏輯程序=算法+數(shù)據(jù)算法=邏輯+控制數(shù)理邏輯是用數(shù)學(xué)方法即通過(guò)引入表意符號(hào)研究推理的學(xué)問(wèn)。因此，數(shù)理邏輯又名為符號(hào)邏輯。3整理ppt第一章命題邏輯命題邏輯，也稱命題演算，記為L(zhǎng)s。研究由命題為基本單位構(gòu)成的前提和結(jié)論之間的可推導(dǎo)關(guān)系。它與謂詞邏輯構(gòu)成數(shù)理邏輯的基礎(chǔ)，而命題邏輯又是謂詞邏輯的基礎(chǔ)。4整理ppt本次課內(nèi)容：命題，邏輯聯(lián)結(jié)詞，命題符號(hào)化

(1)掌握命題概念

(2)掌握聯(lián)結(jié)詞含義及真值表

(3)掌握命題符號(hào)化方法

本次課重點(diǎn)：5整理ppt1-1命題及其表示方法內(nèi)容：命題重點(diǎn)：掌握命題概念

6整理ppt一.基本概念命題：具有確定真值的陳述句。

or

真值客觀存在且唯一

or

能區(qū)分真假可以看出：

（1）一個(gè)命題，總是具有一個(gè)“值”，稱為真值。命真真命題：真值為真(T，1)的命題。假命題：真值為假(F，0)的命題。7整理ppt（2）判斷命題規(guī)則：

只有具有確定真值的陳述句才是命題，感嘆句，疑問(wèn)句，祈使句等都不是命題。

真值必須唯一，與是否知道其真值無(wú)關(guān)。

（3）判斷命題的兩個(gè)步驟：

1、是否為陳述句；

2、是否有確定的、唯一的真值。8整理ppt

1、100是自然數(shù)。

2、這周四是否開會(huì)？

3、1＋101＝110

4、Howdoyoudo?

5、別的星球上有生物。6、2010年國(guó)慶是晴天。

7、x+3>9

8、我正在說(shuō)謊。

9、全體立正！10、離散數(shù)學(xué)是我們的基礎(chǔ)必修課。11、我學(xué)英語(yǔ)，或者我學(xué)日語(yǔ)。

12、只有天下大雨，他才乘車去上班。例：判斷下列句子是否為命題是不是不是不是是是9整理ppt（2）（4）（9）不是命題。（3）在十進(jìn)制中為假，二進(jìn)制中為真，不能確定其真值。不是命題。（7）根據(jù)x的值而定，無(wú)唯一真值，不是命題。（5）（6）目前無(wú)法確定，但從事物的本質(zhì)而言，它本身是有真假可言的，即客觀存在且唯一，為命題。無(wú)法確定真值；（8）是悖論。

所以，（1）（5）（6）（10）（11）（12）是命題。分析：10整理ppt

“悖論”這個(gè)詞的意義比較豐富，它包括一切與人們直覺和日常經(jīng)驗(yàn)相矛盾的數(shù)學(xué)結(jié)論。由真推出假，由假推出真。(1)說(shuō)謊者悖論我們陷入了著名的說(shuō)謊者悖論之中。下面是它的簡(jiǎn)單形式。

這句話是錯(cuò)的上面這個(gè)句子對(duì)嗎?如果是對(duì)的，這句話就是錯(cuò)的！如果這句話是錯(cuò)的，那這個(gè)句子就對(duì)了！像這樣矛盾的說(shuō)法比你所能想到的還要普遍得多。附錄(悖論):11整理ppt著名的理發(fā)師悖論是伯特納德·羅素提出的。

告示:城里所有不自己刮臉的男人都由我給他們刮臉，我也只給這些人刮臉。誰(shuí)給這位理發(fā)師刮臉呢？如果他自己刮臉，那他就屬于自己刮臉的那類人。但是，他的招牌說(shuō)明他不給這類人刮臉，因此他不能自己來(lái)刮。如果另外一個(gè)人來(lái)給他刮臉，那他就是不自己刮臉的人。但是，他的招牌說(shuō)他要給所有這類人刮臉。因此其他任何人也不能給他刮臉?？磥?lái)，沒有任何人能給這位理發(fā)師刮臉了！伯特納德·羅素提出這個(gè)悖論，為的是把他發(fā)現(xiàn)的關(guān)于集合的一個(gè)著名悖論用故事通俗地表述出來(lái)。(2)羅素悖論（理發(fā)師悖論）12整理ppt注意：1.命題的真值是具有客觀性質(zhì)的，而不是由人的主觀決定的。2.

在數(shù)理邏輯中，不要糾纏各種具體問(wèn)題的真假問(wèn)題，而把它看成抽象化的數(shù)學(xué)概念。13整理ppt簡(jiǎn)單/原子命題：由不能再分解為更簡(jiǎn)單的陳述句的陳述句構(gòu)成。(1)(5)(10)

復(fù)合命題：由簡(jiǎn)單命題通過(guò)聯(lián)結(jié)詞聯(lián)結(jié)而成的陳述句。它由原子命題、命題聯(lián)結(jié)詞和圓括號(hào)組成。(11)(12)命題的分類14整理ppt

常用大寫字母、帶下標(biāo)的大寫字母、數(shù)字表示命題，稱之為命題標(biāo)識(shí)符。

例如：P：北京是中國(guó)的首都。[2]：北京是中國(guó)的首都。命題常量：表示一個(gè)確定的命題的命題標(biāo)示符。命題變?cè)喝我饷}的位置標(biāo)志。命題變?cè)皇敲}（表示任意命題，不能確定真值）當(dāng)命題變?cè)狿用一個(gè)特定的命題取代時(shí)，P才能確定真值，也稱對(duì)P進(jìn)行指派。二、命題的表示法15整理ppt本節(jié)的主要內(nèi)容有:1.給出了命題的概念；2.命題的判斷結(jié)果稱為命題的真值；3.原子命題,復(fù)合命題。16整理ppt1-2聯(lián)結(jié)詞內(nèi)容：

否定聯(lián)結(jié)詞

合取聯(lián)結(jié)詞

析取聯(lián)結(jié)詞

條件聯(lián)結(jié)詞

雙條件聯(lián)結(jié)詞17整理ppt(1)否定聯(lián)結(jié)詞定義1-2.1

設(shè)P為命題，復(fù)合命題“非P”（或“P的否定”）稱為P的否定式，記作┐P，符號(hào)┐稱為否定聯(lián)結(jié)詞。運(yùn)算規(guī)則：屬于單目運(yùn)算符(一元運(yùn)算)例:P:上海是一個(gè)大城市。

┐P:上海并不是一個(gè)大城市。

┐P：上海是一個(gè)不大的城市。

P┐P

T

F

F

T18整理ppt(2)合取聯(lián)結(jié)詞∧

P

QP∧Q

T

T

T

T

F

F

F

T

F

F

F

F定義1-2.2

設(shè)P,Q為二命題，復(fù)合命題“P并且Q”或“P與Q”，稱為P與Q的合取式，記作P∧Q，符號(hào)∧稱為合取聯(lián)結(jié)詞。運(yùn)算規(guī)則：屬于二元運(yùn)算符合取運(yùn)算特點(diǎn)：只有參與運(yùn)算的二命題全為真時(shí)，運(yùn)算結(jié)果才為真，否則為假。19整理ppt例1P：今天下雨。Q：明天下雨。上述命題的合取為：

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

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

P∧Q：這兩天都下雨。例2P:地球在運(yùn)轉(zhuǎn)。Q：2＋2＝4

則P∧Q：地球在運(yùn)轉(zhuǎn)且2＋2＝4例題20整理ppt注意：（1）自然語(yǔ)言中的表示“并且”意思的聯(lián)結(jié)詞，如“既…又…”、“不但…而且…”、“雖然…但是…”、“一面…一面…”等都可以符號(hào)化為∧

。（2）合取的概念與自然語(yǔ)言中的“與”意義類似，但并不完全相同。尤其例2在自然語(yǔ)言中是沒有意義的，但在數(shù)理邏輯中仍能成為一個(gè)新的命題。（3）不要見到“與”或“和”就使用聯(lián)結(jié)詞∧

！例如：甲與乙是同學(xué)。這里的“與”不是合取。21整理ppt（3）析取聯(lián)結(jié)詞∨定義1-2.3

設(shè)P,Q為二命題，復(fù)合命題“P或Q”稱為P與Q的析取式，記作P∨Q，符號(hào)∨稱為析取聯(lián)結(jié)詞。運(yùn)算規(guī)則：屬于二元運(yùn)算符析取運(yùn)算特點(diǎn)：只有參與運(yùn)算的二命題全為假時(shí)，運(yùn)算結(jié)果才為假，否則為真。

22整理ppt

析取運(yùn)算只能表示自然語(yǔ)言中的“相容或”(亦稱“可兼或”，用它聯(lián)結(jié)的命題具有相容性)的意思不能表示自然語(yǔ)言里的“排斥或”還有一些漢語(yǔ)中的“或”不是命題聯(lián)結(jié)詞。注意:

23整理ppt例如：火車8：00或9：00到站。（排斥或）設(shè)P：火車8：00到站。Q：火車9：00到站。則上述命題就不可簡(jiǎn)單符號(hào)化為：P∨Q

而應(yīng)描述為(P∧┐Q)∨(┐P∧Q)或者

P

Q命題P

Q┐（P

Q）

T

T

F

T

F

T

F

T

F

T

F

T

T

F

T

F

F

F

T

F24整理ppt（1）小王愛打球或愛跑步。（可兼或）設(shè)P：小王愛打球。Q：小王愛跑步。則上述命題可符號(hào)化為：P∨Q（2）今晚我在家看電視或去影院看電影（排斥或）

(P∧┐Q)∨(┐P∧Q)（3）他昨天做了二十或三十道習(xí)題?！盎颉敝皇潜硎镜牧?xí)題的近似數(shù)目。原子命題例如：25整理ppt（4）條件聯(lián)結(jié)詞→定義1-2.4

設(shè)P,Q為二命題，復(fù)合命題“如果P，則Q”稱為P與Q的蘊(yùn)涵式，記作P

Q，即“如果P，則Q”，“若P則Q”。并稱P為前件，Q為后件，符號(hào)

稱為蘊(yùn)涵聯(lián)結(jié)詞。運(yùn)算規(guī)則：屬于二元運(yùn)算符

P

QP→Q

T

T

T

T

F

F

F

T

T

F

F

T只有當(dāng)P的真值為T，Q的真值為F時(shí)，P

Q的真值為F。否則均為T。26整理ppt例題：例1：如果某動(dòng)物為哺乳動(dòng)物，則它必胎生。例2：如果我得到這本小說(shuō)，那末我今夜就讀完它。例3：如果雪是黑的，那么太陽(yáng)從西方出。27整理ppt（1）自然語(yǔ)言中可用P

Q蘊(yùn)涵式表述命題格式有“只要P，就Q”“因?yàn)镻，所以Q”、“只有Q才P”、“P僅當(dāng)Q”（P成立，Q就成立）、“除非Q才P”、“除非Q，否則非P”、“Q是P的必要條件”等。（2）與自然語(yǔ)言的不同：前件與后件可以沒有任何內(nèi)在聯(lián)系?。?）在數(shù)學(xué)或其他自然科學(xué)中，往往是P為真Q也為真的推理關(guān)系。但在數(shù)理邏輯中，作為一種規(guī)定，當(dāng)P為假時(shí)，無(wú)論Q如何，P

Q均為真。（善意的推定）注意：28整理ppt

（5）雙條件聯(lián)結(jié)詞

定義1.5

設(shè)P,Q為二命題，復(fù)合命題“P當(dāng)且僅當(dāng)Q”稱為P與Q的等價(jià)式，記作P

Q，符號(hào)

稱為等價(jià)聯(lián)結(jié)詞。運(yùn)算規(guī)則：屬于二元運(yùn)算符

P

QP

Q

T

T

T

T

F

F

F

T

F

F

F

T當(dāng)P和Q的真值相同時(shí)，P

Q的真值為T；否則為F。29整理ppt說(shuō)明：雙條件命題也可以不顧因果關(guān)系，只根據(jù)聯(lián)結(jié)詞的定義確定真值。例1：兩個(gè)三角形全等，當(dāng)且僅當(dāng)它們的三組對(duì)應(yīng)邊相等。

例2：燕子飛回南方，當(dāng)且僅當(dāng)春天來(lái)了。

例3：2＋2=4當(dāng)且僅當(dāng)雪是白的。30整理ppt小結(jié)：以上5種最基本、最常用、最重要的聯(lián)結(jié)詞可以組成一個(gè)集合{┐，∧，∨，，}，成為一個(gè)聯(lián)結(jié)詞集。由后四種組成的命題是復(fù)合命題，亦可被多次使用，如 （P∧Q）

R；復(fù)合命題的真值，取決于原子命題的真值，與原子命題之間是否有關(guān)系無(wú)關(guān)，與復(fù)合命題本身內(nèi)容、含義無(wú)關(guān)；∧、∨、

具有對(duì)稱性，┐、→沒有；連接詞具有運(yùn)算和操作性，從已知命題得到新命題。31整理ppt

1-3命題公式與翻譯內(nèi)容：合式公式命題翻譯重點(diǎn)難點(diǎn)：命題翻譯32整理ppt合式公式wff命題公式：將命題變?cè)寐?lián)結(jié)詞和圓括號(hào)按一定的邏輯關(guān)系聯(lián)結(jié)起來(lái)的有意義的符號(hào)串。例如：

P∧Q，P

（Q∨┐P）說(shuō)明：命題公式是沒有真假值的。僅當(dāng)命題變?cè)么_定命題代入時(shí)，才得到一個(gè)命題。命題的真值依賴于代換變?cè)哪切┟}真值。33整理ppt定義1-2-1合式公式是由下列規(guī)則形成的字符串：

（1）單個(gè)命題變?cè)旧硎且粋€(gè)合式公式。（2）如果A是合式公式，那么┐A是合式公式。（3）如果A和B是合式公式。那么P∧Q，P∨Q，P→Q，P

Q都是合式公式。（4）當(dāng)且僅當(dāng)能夠有限次地應(yīng)用(1)(2)