離散數(shù)學(xué)教程課件

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

第一部分?jǐn)?shù)理邏輯

數(shù)理邏輯又名符號(hào)邏輯，是一門(mén)用數(shù)學(xué)方法研究推理過(guò)程的科學(xué)。邏輯學(xué)主要是研究各種論證。它可以是有意義的一般論證，也可以是科學(xué)理論中的數(shù)學(xué)證明或結(jié)論。建立邏輯學(xué)的主要目的在于探索出一套完整的規(guī)則，按照這些規(guī)則，就可以確定任何特定論證是否有效。這些規(guī)則，通常稱(chēng)為推理規(guī)則。同其它科學(xué)理論一樣，也可以把推理理論公式化(由于自然語(yǔ)言易產(chǎn)生二義性,用它來(lái)表示嚴(yán)格的推理就不合適了)。由于在邏輯學(xué)中使用了符號(hào)，故數(shù)理邏輯也稱(chēng)為符號(hào)邏輯。

命題邏輯是數(shù)理邏輯的基本組成部分.本章重點(diǎn)：命題、命題的符號(hào)化、命題聯(lián)結(jié)詞及其真值、命題公式及其賦值本章難點(diǎn)：命題公式及其賦值

第一章命題邏輯1.1命題及命題聯(lián)結(jié)詞

一、命題及其表示法能夠判斷真假的陳述句稱(chēng)作命題。

1命題的概念真值：作為命題的陳述句所表達(dá)的判斷結(jié)果真值只能取兩個(gè)：真或假。因?yàn)橹挥袃煞N真值，所以這種邏輯有時(shí)稱(chēng)為二值邏輯。真值為真的命題稱(chēng)為真命題；真值為假的命題為假命題。判斷句子是否為命題的標(biāo)準(zhǔn)：(1)陳述句(2)有唯一的真值說(shuō)明：命題必須是陳述性語(yǔ)句，而不能是疑問(wèn)句、命令句、感嘆句等；2.命題語(yǔ)句或者為真或者為假，二者必取其一，即命題的真值是唯一的

例1判斷下列句子是不是命題:(1)4是素?cái)?shù)。(2)是無(wú)理數(shù)。(3)(4)火星上有水。(5)2005年元旦是晴天(6)(7)請(qǐng)不要吸煙！

(8）這朵花真美麗啊！(9）我正在說(shuō)假話(huà).假命題真命題命題命題由真推出假，又由假推出真的陳述句稱(chēng)為悖論，凡悖論都不是命題。2命題與真值的符號(hào)化

本書(shū)中命題用大寫(xiě)英文字母表示：用1和0分別表示“真”和“假”,于是命題的真值取值為1或0.3原子命題與復(fù)合命題

不能分解成更簡(jiǎn)單的語(yǔ)句的命題稱(chēng)為原子命題。

原子命題中的“原子”取原子的“不可再分”之意,它是最基本的命題,相當(dāng)于自然語(yǔ)言的簡(jiǎn)單陳述句。例２下面的命題由哪些原子命題組成:(1)只要明天天氣好,我就去春游。(2)如果10是一個(gè)大于１的整數(shù),則10的大于１的最小因數(shù)一定是素?cái)?shù)。

解(1)有兩個(gè)原子命題P和Q,其中

P:明天天氣好。

Q:我去春游。(2)有兩個(gè)原子命題R和S,其中

R:10是一個(gè)大于１的整數(shù)。

S:10的大于１的最小因數(shù)是素?cái)?shù)。

多個(gè)原子命題由聯(lián)結(jié)詞和圓括號(hào)聯(lián)結(jié)起來(lái)構(gòu)成的命題稱(chēng)為復(fù)

合命題。復(fù)合命題的真假值只與原子命題的真假值有關(guān)。

二、聯(lián)結(jié)詞定義1.1若P是一個(gè)命題,則由否定詞┐和命題P組成的復(fù)合命題┐P稱(chēng)為P的否定式,讀作“非P”。┐P的真值定義為

命題┐P和P的關(guān)系可以用下表表示。稱(chēng)為┐P的真值表。1否定聯(lián)結(jié)詞﹁┐P為真當(dāng)且僅當(dāng)P為假

P﹁P0110定義1.２若P,Q是兩個(gè)命題,則由合取詞∧和命題P,Q

組成的復(fù)合命題P∧Q稱(chēng)為P,Q的合取式,讀作“P且Q”。

P∧Q的真值定義為

P∧Q為真當(dāng)且僅當(dāng)P,Q都為真因此,P,Q同時(shí)為假或一真一假時(shí),P∧Q都為假。

2合取聯(lián)結(jié)詞∧復(fù)合命題P∧Q的真值表：

PQP∧Q000010100111例３設(shè)有命題P,Q為

P:吳穎用功。Q:吳穎聰明。

則P,Q的合取式P∧Q

為

P∧Q

:吳穎既用功又聰明?；騊∧Q

:吳穎不僅用功而且聰明。

合取詞∧是自然語(yǔ)言中的連接詞“并且”、“和”、“及”、“與”“既又”、“不但…，而且…”、“雖然…，但是…”、“一面…，一面…”等的邏輯抽象。

定義1.3若P,Q是兩個(gè)命題,則由析取詞∨和命題P,Q組成的復(fù)合命題

P∨Q稱(chēng)為P,Q的析取式,讀作“P或Q”。

P∨Q的真值定義為

P∨Q為真當(dāng)且僅當(dāng)P,Q

至少有一個(gè)為真

因此只有P,Q同時(shí)為假時(shí),P∨Q才為假。3析取聯(lián)結(jié)詞∨復(fù)合命題P∨Q

的真值表：

PQP∨Q000011101111例1.3將下列命題符號(hào)化。

(1)張曉靜愛(ài)唱歌或愛(ài)聽(tīng)音樂(lè)。

(2)張曉靜是江西人或安徽人。

(3)張曉靜只能挑選202或203房間。解在解題時(shí)，先將原子命題符號(hào)化。

(1)P：張曉靜愛(ài)唱歌。

Q：張曉靜愛(ài)聽(tīng)音樂(lè)。自然語(yǔ)言的或有二義性,用它聯(lián)結(jié)的命題有時(shí)是相容的,有時(shí)是排斥的,對(duì)應(yīng)稱(chēng)為相容或與排斥或顯然(1)中“或”為相容或，即P與Q可以同時(shí)為真，符號(hào)化為P∨Q.

(2)R：張曉靜是江西人。

S：張曉靜是安徽人。

易知，(2)中“或”應(yīng)為排斥或，但不可能同時(shí)為真，可符號(hào)化為R∨S.

(3)T：張曉靜挑選202房間。

U：張曉靜挑選203房間。

由題意可知，(3)中“或”應(yīng)為排斥或。T，U的聯(lián)合取值情況有四種：同真，同假，一真一假(兩種情況)。如果也符號(hào)化為T(mén)∨U，張曉靜就可能同時(shí)得到兩個(gè)房間，這違背題意。因而不能符號(hào)化為T(mén)∨U.如何達(dá)到只能挑一個(gè)房間的要求呢？可以使用多個(gè)聯(lián)結(jié)詞，符號(hào)化為(T∧┐U)∨(┐T∧U)定義1.4若P,Q是兩個(gè)命題,則由蘊(yùn)涵詞→和命題P,Q組成的復(fù)合命題P→Q

稱(chēng)為P,Q的蘊(yùn)涵式,讀作“如果P,則Q”。4蘊(yùn)涵聯(lián)結(jié)詞→

P→Q

為假當(dāng)且僅當(dāng)P為真而Q為假

因此,P為假時(shí),不管Q

為真還是為假,P→Q

都為真;而P,Q同時(shí)為真時(shí),P→Q

也為真。

復(fù)合命題P→Q

的真值表：

PQP→Q

001011100111P→Q

的真值定義為1．在自然語(yǔ)言里，特別是在數(shù)學(xué)中，Q是P的必要條件有許多不同的敘述方式。例如，“只要P，就Q”，“因?yàn)镻，所以Q”，“P僅當(dāng)Q”，“只有Q才P”，“除非Q才P”，“除非Q，否則非P”等等。以上各種敘述方式表面看來(lái)有所不同，但都表達(dá)的是Q是P的必要條件，因而所用聯(lián)結(jié)詞均應(yīng)符號(hào)化為→，上述各種敘述方式都應(yīng)符號(hào)化為P→Q.注意：在使用聯(lián)結(jié)詞→時(shí)，要特別注意以下幾點(diǎn)：

例5設(shè)有命題P,Q為

P:∠1和∠2是對(duì)頂角。Q:∠1＝∠2則蘊(yùn)涵式P→Q為

P→Q:若∠1和∠2是對(duì)頂角,則∠1＝∠2。這時(shí)我們也說(shuō)“P是Q的充分條件”,或“Q是P的必要條件”。

3．在數(shù)學(xué)或其它自然科學(xué)中，“如果P，則Q”往往表達(dá)的是前件P為真，后件Q也為真的推理關(guān)系。但在數(shù)理邏輯中，作為一種規(guī)定，當(dāng)P為假時(shí)，無(wú)論Q是真是假，P→Q均為真。也就是說(shuō)，只有P為真Q為假這一種情況使得復(fù)合命題P→Q為假。

2．在自然語(yǔ)言中，“如果P，則Q”中的前件P與后件Q往往具有某種內(nèi)在聯(lián)系。而在數(shù)理邏輯中，P與Q可以無(wú)任何內(nèi)在聯(lián)系。

解:令P:3+3=6,P的真值為1;Q:雪是白色的,Q的真值為1;R:a能被4整除;S:a能被2整除.則(1)-(4)分別符號(hào)化為(5)-(9)符號(hào)化為(10)符號(hào)化為復(fù)合命題P

Q的真值表：

定義1.5若P,Q是兩個(gè)命題,則由等值詞和命題P,Q

組成的復(fù)合命題P

Q

稱(chēng)為P,Q的等價(jià)式,讀作“P當(dāng)且僅當(dāng)Q”。P

Q為真當(dāng)且僅當(dāng)P,Q同真值因此,P,Q一真一假時(shí),P

Q為假。

PQPQ001010100111P

Q的真值定義為

5等值聯(lián)結(jié)詞等值詞

是自然語(yǔ)言中的連接詞“當(dāng)且僅當(dāng)”等的邏輯抽象。

以上定義了五種最基本、最常用、也是最重要的聯(lián)結(jié)詞┐，∧，∨，→，，將它們組成一個(gè)集合{┐，∧，∨，→，}，稱(chēng)為一個(gè)聯(lián)結(jié)詞集。其中┐為一元聯(lián)結(jié)詞，其余的都是二元聯(lián)結(jié)詞。

聯(lián)結(jié)詞可以嵌套使用，在嵌套使用時(shí)，規(guī)定如下優(yōu)先順序：()，┐，∧，∨，→，，對(duì)于同一優(yōu)先級(jí)的聯(lián)結(jié)詞，先出現(xiàn)者先運(yùn)算。

解P，Q，R的真值分別為1，1，0。容易算出(1)、(2)、(3)的真值分別為1，1，0。

可以把自然語(yǔ)言中的有些語(yǔ)句，轉(zhuǎn)變成數(shù)理邏輯中的符號(hào)形式，稱(chēng)為命題的翻譯。命題翻譯時(shí)應(yīng)注意下列事項(xiàng)：（1）確定所給句子是否為命題。（2）句子中聯(lián)結(jié)詞是否為命題聯(lián)結(jié)詞。（3）要正確的選擇原子命題和合適的命題聯(lián)結(jié)詞。

命題的翻譯(命題符號(hào)化)本例可表示為：（PQ）∧（P（R∨S））。

例7：假如上午不下雨，我去看電影，否則就在家里讀書(shū)或看報(bào)。

解：設(shè)P：上午下雨；Q：我去看電影；R：我在家里讀書(shū)；S：我在家里看報(bào)。例8設(shè)P:明天下雨，

Q:明天下雪，

R:我去學(xué)校。試把下列命題符號(hào)化:(1)如果明天不是雨夾雪,我就去學(xué)校。(2)如果明天既不下雨又不下雪,我就去學(xué)校。(3)明天下雨或者下雪,我就不去學(xué)校。

解(1)┐(P∧Q)→R(2)(┐P∧┐Q)→R(3)(P∨Q)→┐R例9設(shè)有命題P,Q,R為

P:雪是黑的。

Q:小李是共青團(tuán)員。

R:小王是大學(xué)生。請(qǐng)寫(xiě)出命題┐P,P∧Q,P∨Q和(P∧Q)→R的含義。

解┐P:雪不是黑的。

P∧Q:雪是黑的且小李是共青團(tuán)員。

P∨Q:雪是黑的或者小李是共青團(tuán)員。

P∧Q)→R:如果雪是黑的且小李是共青團(tuán)員,那么小王是大學(xué)生。