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

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

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

請問這個人說得對嗎？他是怎么推導(dǎo)出來的呢？

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

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

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

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

(4)怎么進行推理？

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

(1)掌握命題概念

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

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

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

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

or

真值客觀存在且唯一

or

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

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

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

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

（3）判斷命題的兩個步驟：

1、是否為陳述句；

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

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

2、這周四是否開會？

3、1＋101＝110

4、Howdoyoudo?

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

7、x+3>9

8、我正在說謊。

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

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

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

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

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

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

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

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

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

例如：P：北京是中國的首都。[2]：北京是中國的首都。命題常量：表示一個確定的命題的命題標示符。命題變元：任意命題的位置標志。命題變元不是命題（表示任意命題，不能確定真值）當命題變元P用一個特定的命題取代時，P才能確定真值，也稱對P進行指派。二、命題的表示法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，符號┐稱為否定聯(lián)結(jié)詞。運算規(guī)則：屬于單目運算符(一元運算)例:P:上海是一個大城市。

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

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

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，符號∧稱為合取聯(lián)結(jié)詞。運算規(guī)則：屬于二元運算符合取運算特點：只有參與運算的二命題全為真時，運算結(jié)果才為真，否則為假。19整理ppt例1P：今天下雨。Q：明天下雨。上述命題的合取為：

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

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

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

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

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

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

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

22整理ppt

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

23整理ppt例如：火車8：00或9：00到站。（排斥或）設(shè)P：火車8：00到站。Q：火車9：00到站。則上述命題就不可簡單符號化為：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：小王愛跑步。則上述命題可符號化為：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的蘊涵式，記作P

Q，即“如果P，則Q”，“若P則Q”。并稱P為前件，Q為后件，符號

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

P

QP→Q

T

T

T

T

F

F

F

T

T

F

F

T只有當P的真值為T，Q的真值為F時，P

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

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

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

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

定義1.5

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

Q，符號

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

P

QP

Q

T

T

T

T

F

F

F

T

F

F

F

T當P和Q的真值相同時，P

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

例2：燕子飛回南方，當且僅當春天來了。

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

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

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

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

P∧Q，P

（Q∨┐P）說明：命題公式是沒有真假值的。僅當命題變元用確定命題代入時，才得到一個命題。命題的真值依賴于代換變元的那些命題真值。33整理ppt定義1-2-1合式公式是由下列規(guī)則形成的字符串：

（1）單個命題變元本身是一個合式公式。（2）如果A是合式公式，那么┐A是合式公式。（3）如果A和B是合式公式。那么P∧Q，P∨Q，P→Q，P

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