1、前言課程性質(zhì)：計算機數(shù)學(xué)基礎(chǔ)課程安排：三個學(xué)期教授三個部分 第一部分：離散數(shù)學(xué) 第一篇：數(shù)理邏輯 第二篇：集合論 第三篇：圖論 代數(shù)系統(tǒng)第二部分：計算數(shù)學(xué)第三部分：組合數(shù)學(xué)學(xué)習(xí)目的：1、初步掌握現(xiàn)代數(shù)學(xué)的觀點和方法； 2、初步掌握處理離散結(jié)構(gòu)和方法，提高計算機系統(tǒng)設(shè)計和程序設(shè)計的邏輯數(shù)字的能力； 3、初步掌握計算機在進(jìn)行數(shù)的處理時的方法和計算； 4、培養(yǎng)學(xué)習(xí)抽象思維和縝密思考的能力；第一篇 數(shù)理邏輯第一章 命題邏輯§1.1 命題和命題聯(lián)結(jié)詞一. 命題：定義：具有確定真值的表達(dá)判斷的陳述句稱為命題。說明：命題的真值：作為命題所表達(dá)的判斷只有兩個結(jié)果：正確和錯誤，此結(jié)果稱為 命題的真值。

2、 命題是正確的，稱此命題的真值為真；命題是錯誤的，稱此命題的真值為假。 真值為真的命題稱為真命題 ；真值為假的命題稱為假命題。其它類型的句子，如疑問句、祈使句、感嘆句均沒有真假意義，因為均不是命 題。在數(shù)理邏輯中，命題的真值的真和假，有時分別用1和0來表達(dá)，也有時分別 用T和F來表達(dá)。命題的分類：原子命題：不能分解成更簡單的命題的命題。復(fù)合命題：由若干個原子命題用命題聯(lián)結(jié)詞、標(biāo)點符號聯(lián)結(jié)起來的命題。例：（1）10是整數(shù)。 真原子命題（2）北京是我們祖國的首都。 真 原子命題（3）雪是黑的。 假 原子命題（4）煤是白的。 假 原子命題（5）今天是7號。 在一定條件下是真命題（如果今天是7號）。（

3、6）1+11=100。 在一定條件下是真命題（在二進(jìn)制中）。（7）我學(xué)英語，或者學(xué)法文。 復(fù)合命題（8）如果 天氣好，我就去游泳。 復(fù)合命題（9）向右看齊！ 祈使句 非命題（10）請勿吸煙！ 祈使句 非命題（11）你吃飯了嗎？疑問句 非命題（12）你上網(wǎng)了嗎？疑問句 非命題（13）本命題是假的。悖論（14）我正在說謊。 悖論（15）我不給所有自己給自己理發(fā)的人理發(fā)，但是卻會給所有自己不給自己理發(fā)的人理發(fā)。悖論 命題標(biāo)識符：用大寫字母P、Q、R、P1、P2L來表示命題，這些大寫字母稱 為命題標(biāo)識符。命題常量：用命題標(biāo)識符表示的確定的命題稱為命題常量，它有確定的真值。命題變量：表示任何一個命題的標(biāo)

4、識符，稱為命題變量，它有不確定的真值。二命題聯(lián)結(jié)詞：常見聯(lián)結(jié)詞否定、合取、析取、蘊含、等價和異或1. 否定 符號：P是命題，P讀作“非P”。P真值表為 PP 0 1 1 0否定的性質(zhì) 雙重否定律 ： （P） P說明：1、P是一元聯(lián)結(jié)詞所謂一元聯(lián)結(jié)詞就是聯(lián)結(jié)一個命題的聯(lián)結(jié)詞。 2、念作“等值”，表示該符號兩邊的兩個命題在任何情況下真值相同。2. 合取 符號：P、Q是命題PQ 讀作“P且Q”，“P合取Q”。PQ 真值表 PQ PQ 0 0 0 0 1 0 1 0 0 1 1 1例：P：今天下雨。Q:今天刮風(fēng)。則PQ ：今天下雨且刮風(fēng)。合取的性質(zhì)1) 冪等律 PPP2) 交換律 PQQP3) 結(jié)合律

5、 (PQ)CP(QC) 4) 零一律P0 05) 同一律P1 P6) 否定律 PP 0 3. 析取 符號： P、Q是命題,記作PQ ，讀作“P或Q”，“P析取Q”。PQ 真值表 PQ PQ 0 0 0 0 11 1 01 1 1 1例：P：今天下雨。Q:今天刮風(fēng)。則 PQ ：今天下雨或刮風(fēng)。析取的性質(zhì)：1) 冪等律 PPP2) 交換律 PQQP3) 結(jié)合律 (PQ)CP(QC)4) 同一律 P0P5) 零一律 P116) 否定律 PP 07) 吸收律 P(PQ) P, P(PQ) P8) 分配律P(QC)(PQ)(PC)P (QC)(PQ) (PC)9) 德、摩根律 (PQ)PQ, (PQ)P

6、Q說明：（1）和混合運算只能用分配律，不能用結(jié)合律。例：P(PQ)與P (QC)不等值。（2）和的分配律：P (QC)(PQ) (PC)，形如乘與加的分配律P× (Q+C)。（3）可兼或與不可兼或 可兼或：明天下雨或刮風(fēng)。 不可兼或：今天晚上去電影院看電影，或在家看電視。 4.蘊含 符號： P、Q是命題PQ 讀作“P蘊含Q”，“如果P則Q”，“當(dāng)P，則Q”，“P是Q的充分條件”。 例：P:我去上海。 Q:我給你買衣服。PQ：如果我去上海，就給你買衣服。P假Q(mào)假 我沒去上海，也沒給你買衣服。 PQ真P假Q(mào)真 我沒去上海，但沒給你買衣服。 PQ真P真Q假 我去了上海，但沒給你買衣服。 P

7、Q假P真Q真 我沒去上海，也沒給你買衣服。 PQ真PQ 真值表 PQ PQ 0 01 0 11 1 00 1 1 1P也稱為前件；Q稱為后件。前件為假時，PQ必為真；后件為真時，PQ必為真。蘊含的性質(zhì)1) 歸化：PQPQ 所謂歸化就是用、表示其它聯(lián)結(jié)詞。2) PQQP證明：P QPQPPQ0 01110 11111 00001 1011在全部四種情況下，PQ與QP的真值表相同，所以PQQP3)（PQ）PQ例：將下列命題符號化1) 如果1+23,則太陽從東邊升起 PQ2) 如果1+23,則太陽從東邊升起 PQ3) 如果1+23,則太陽從東邊升起 PQ4) 如果1+23,則太陽從東邊升起 PQP:

8、1+2=3Q:表示太陽從東邊升起說明(1)蘊涵不存在交換律、結(jié)合律PQ與QP不等值 （PQ）R與P（QP）等值 (2)在數(shù)理邏輯中，即使 P、Q沒有內(nèi)在聯(lián)系 PQ仍有意義5. 等價 符號：P、Q是命題從 讀作“P等價于Q”，“P當(dāng)且僅當(dāng)Q”，“P是Q的充要條件”。PQ 真值表 PQ PQ 0 01 0 10 1 00 1 1 1等價的性質(zhì)PQ(PQ)(QP)從(PQ)(PQ)(PQ)(PQ1) 交換律：PQ QP2) 結(jié)合律：（PQ）R P(QR)3) PQ(PQ)(QP)4) 歸化：PQ(PQ)(PQ)(PQ)(PQ)證明結(jié)合律PQRPQ（PQ）RQRP(QR)00010100011101010010101100101000111101000011010001111111左右兩