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

1、第1章 命題邏輯數(shù)理邏輯：是用數(shù)學(xué)方法來(lái)研究推理的形式結(jié)構(gòu)和推理規(guī)律 的數(shù)學(xué)學(xué)科。 數(shù)理邏輯近年來(lái)發(fā)展特別迅速，主要原因是這門學(xué)科對(duì)于數(shù)學(xué)其它分支如集合論、數(shù)論、代數(shù)、拓?fù)鋵W(xué)等的發(fā)展有重大的影響，特別是對(duì)新近形成的計(jì)算機(jī)科學(xué)的發(fā)展起了推動(dòng)作用。反過(guò)來(lái)，其他學(xué)科的發(fā)展也推動(dòng)了數(shù)理邏輯的發(fā)展。本書介紹了數(shù)理邏輯的兩個(gè)最基本、也是最重要的部分：命題邏輯和謂詞邏輯。本章首先介紹命題邏輯。 命題邏輯是研究命題如何通過(guò)一些邏輯連接詞構(gòu)成更復(fù)雜的命題以及邏輯推理的方法。1.1 命題符號(hào)化與聯(lián)結(jié)詞數(shù)理邏輯研究的中心問(wèn)題是推理。推理的前提和結(jié)論都是表達(dá)判斷的陳述句。表達(dá)判斷的陳述句構(gòu)成了推理的基本單位。稱能判斷

2、真假的陳述句為命題。(判斷結(jié)果惟一的陳述句)作為命題的陳述句所表達(dá)得的判斷結(jié)果稱為命題的真值。真值只取兩個(gè)：真與假。真值為真的命題稱為真命題。真值為假的命題稱為假命題。命題又稱為具有唯一真值的陳述句。注意: 感嘆句、祈使句、疑問(wèn)句都不是命題陳述句中的悖論以及判斷結(jié)果不惟一確定的也不是命題 說(shuō)明一、命題的概念2是素?cái)?shù)。雪是黑色的。2+3=5 。明年10月1日是晴天。3能被2整除。這朵花多好看??！明天下午有會(huì)嗎？請(qǐng)關(guān)上門！x+y5。 地球外的星球上也有人 我正在說(shuō)謊話.例1.1 判斷下列句子是否為命題。 是，真命題是，假命題是，真命題是，真值客觀存在是，假命題不是，感嘆句不是，疑問(wèn)句不是，祈使句不

3、是，真值不唯一是，真值客觀存在 悖論二、命題的符號(hào)化用小寫英文字母 p , q , r , pi , qi ,ri 表示命題用“1”表示真，用“0”表示假 命題符號(hào)化：用表示命題的符號(hào)放在該命題的前面。r：充分大的偶數(shù)等于兩個(gè)素?cái)?shù)之和。s：今天是星期二。p：4是素?cái)?shù)。q：不能被分解成更簡(jiǎn)單句子的命題為簡(jiǎn)單命題或原子命題。（一）、簡(jiǎn)單命題簡(jiǎn)單命題的真值是唯一確定的，所以也稱簡(jiǎn)單命題為命題常項(xiàng)或命題常元。稱真值可以變化的簡(jiǎn)單陳述句為命題變項(xiàng)或命題變?cè)?也用p,q,r,表示命題變項(xiàng)。當(dāng)p,q,r,表示命題變項(xiàng)時(shí)，它們就成了取值0或1的變項(xiàng)，因而命題變項(xiàng)已不是命題。這樣一來(lái)，p,q,r,既可以表示命題

4、常項(xiàng)，也可以表示命題變項(xiàng)。在使用中，需要由上下文確定它們表示的是常項(xiàng)還是變項(xiàng)。 由簡(jiǎn)單命題通過(guò)聯(lián)結(jié)詞聯(lián)結(jié)而成的命題，稱這樣的命題為復(fù)合命題。 （二）、復(fù)合命題例1.2 （1）3不是偶數(shù)；（2）2是素?cái)?shù)和偶數(shù)；（3）林芳學(xué)過(guò)英語(yǔ)或日語(yǔ)；（4）如果角A和角B是對(duì)頂角，則角A等于角B ；定義1.1（否定聯(lián)結(jié)詞） 設(shè)p為命題，復(fù)合命題“非p”(或“p的否定”)稱為p的否定式,記作p，符號(hào)稱作否定聯(lián)結(jié)詞，并規(guī)定p為真當(dāng)且僅當(dāng)p為假。 例如：p： 3是偶數(shù)。 p： 3不是偶數(shù)。（三）、聯(lián)結(jié)詞pp1001定義1.2（合取聯(lián)結(jié)詞） 設(shè)p ,q為二命題，復(fù)合命題“p并且q”(或“p與q”)稱為p與q的合取式，記

5、作pq，稱作合取聯(lián)結(jié)詞，并規(guī)定pq為真當(dāng)且僅當(dāng)p與q同時(shí)為真。使用合取聯(lián)結(jié)詞時(shí)要注意的兩點(diǎn)：1）描述合取式的靈活性與多樣性。自然語(yǔ)言中的“既又”、“不但而且”、“雖然但是”、“一面一面”等聯(lián)結(jié)詞都可以符號(hào)化為。2）分清簡(jiǎn)單命題與復(fù)合命題。不要見(jiàn)到“與”或“和”就使用聯(lián)結(jié)詞。 pqpq111100010000例1.3 將下列命題符號(hào)化李平既聰明又用功。李平雖然聰明，但不用功。李平不僅用功而且聰明。李平不是不聰明，而是不用功。p: 李平聰明。q:李平用功。(1)pq(2)pq(3)qp(4) （p） q解題要點(diǎn)：正確理解命題含義。找出原子命題并符號(hào)化。選擇恰當(dāng)?shù)穆?lián)結(jié)詞。 定義1.3（析取聯(lián)結(jié)詞）

6、設(shè)p，q為二命題，復(fù)合命題“p或q”稱作p與q的析取式，記作pq，稱作析取聯(lián)結(jié)詞，并規(guī)定pq為真當(dāng)且僅當(dāng)p與q中至少一個(gè)為真。 自然語(yǔ)言中的“或”具有二義性，用它聯(lián)結(jié)的命題有時(shí)具有相容性，有時(shí)具有排斥性，對(duì)應(yīng)的聯(lián)結(jié)詞分別稱為相容或和排斥或(排異或)。 說(shuō)明pqpq111101011000數(shù)理邏輯中，pq表示相容或，即允許p與q同時(shí)為真。說(shuō)明例如：王燕學(xué)過(guò)英語(yǔ)或法語(yǔ)。 pq派小王或小李中的一人去開會(huì)。 (rs)(rs)自然語(yǔ)言中的“或”具有二義性，用它聯(lián)結(jié)的命題有時(shí)具有相容性，有時(shí)具有排斥性，對(duì)應(yīng)的聯(lián)結(jié)詞分別稱為相容或和排斥或(排異或)。 例如 將下列命題符號(hào)化 張曉靜愛(ài)唱歌或愛(ài)聽(tīng)音樂(lè)。張曉靜只

7、能挑選202或203房間。張曉靜是江西人或安徽人。設(shè) p：張曉靜愛(ài)唱歌，q：張曉靜愛(ài)聽(tīng)音樂(lè)。相容或，符號(hào)化為 pq設(shè)t：張曉靜挑選202房間，u：張曉靜挑選203房間。排斥或，符號(hào)化為：(tu)(tu)設(shè)r：張曉靜是江西人，s：張曉靜是安徽人。排斥或，符號(hào)化為：(rs)(rs)定義1.4（蘊(yùn)涵聯(lián)結(jié)詞） 設(shè)p，q為二命題，復(fù)合命題“如果p，則q”稱作p與q的蘊(yùn)涵式，記作pq，并稱p是蘊(yùn)涵式的前件，q為蘊(yùn)涵式的后件，稱作蘊(yùn)涵聯(lián)結(jié)詞,并規(guī)定pq為假當(dāng)且僅當(dāng)p為真q為假。 說(shuō)明pq的邏輯關(guān)系表示q是p的必要條件。 q是p的必要條件有許多不同的敘述方式 只要p，就q 因?yàn)閜，所以qp僅當(dāng)q只有q才p除非

8、q才p除非q，否則非p pqp q111100011001例1.4 將下列命題符號(hào)化，并指出其真值 只要不下雨，我就騎自行車上班。只有不下雨，我才騎自行車上班。如果3+3=6，則太陽(yáng)從東方升起。如果3+36，則太陽(yáng)從東方升起。如果3+3=6，則太陽(yáng)從西方升起。如果3+36，則太陽(yáng)從西方升起。解：令p：天下雨。q：我騎自行車上班。 r: 3+3=6 。s：太陽(yáng)從東方升起。t：太陽(yáng)從西方升起。(1)pq ; (2)q p; (3) rs ; (4) rs ; (5) rt;定義1.5（等價(jià)聯(lián)結(jié)詞） 設(shè)p，q為二命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”稱作p與q的等價(jià)式，記作pq， 稱作等價(jià)聯(lián)結(jié)詞，并規(guī)定pq

9、為真當(dāng)且僅當(dāng)p與q同時(shí)為真或同時(shí)為假。pqp q111100010001例1.5 將下列命題符號(hào)化2+35當(dāng)且僅當(dāng)3是奇數(shù)。2+35當(dāng)且僅當(dāng)3不是奇數(shù)。2+35當(dāng)且僅當(dāng)3是奇數(shù)。2+35當(dāng)且僅當(dāng)3不是奇數(shù)。兩圓A，B的面積相等當(dāng)且僅當(dāng)它們的半徑相等。設(shè) p ：2+35 ，q： 3是奇數(shù)。符號(hào)化為 pq，pq， pq，pq，設(shè) p：兩圓A，B的面積相等， q：兩圓A，B的半徑相等。符號(hào)化為 pq，真值為1。關(guān)于聯(lián)結(jié)詞的說(shuō)明多次使用聯(lián)結(jié)詞集中的聯(lián)結(jié)詞，可以組成更為復(fù)雜的復(fù)合命題。 本書規(guī)定的聯(lián)結(jié)詞優(yōu)先順序?yàn)椋? )， ，對(duì)于同一優(yōu)先級(jí)的聯(lián)結(jié)詞，先出現(xiàn)者先運(yùn)算。 習(xí)題：命題符號(hào)化(1)我和他既是兄弟

10、又是同學(xué) p：我和他是兄弟，q：我和他是同學(xué)。故命題可符號(hào)化為： pq。(2)張三或李四都可以做這件事。 p：張三可以做這件事。 q：李四可以做這件事。故命題可符號(hào)化為：pq。 (3)僅當(dāng)我有時(shí)間且天不下雨，我將去鎮(zhèn)上。對(duì)于“僅當(dāng)”，實(shí)質(zhì)上是“當(dāng)”的逆命題?！爱?dāng)A則B”是AB，而“僅當(dāng)A則B”是BA。 p：我有時(shí)間。 q：天不下雨。 r：我將去鎮(zhèn)上。故命題可符號(hào)化為：r(pq)。 (4)張剛總是在圖書館看書，除非圖書館不開門或張剛生病。 對(duì)于“除非”，只要記住，“除非”是條件。p：張剛在圖書館看書，q：圖書館不開門，r：張剛生病。 故命題可符號(hào)化為：(qr)p。 (5)風(fēng)雨無(wú)阻，我去上學(xué)?？衫斫鉃椤安还苁欠窆物L(fēng)、是否下雨，我都去上學(xué)”。 p：天刮風(fēng)，q：天下雨，r：我去上學(xué)。故命題可符號(hào)化為：(pqr)(pqr)(pqr)(pqr)或(pqr)(pqr)(pqr)(pqr) 理解為“四種情況必居其一,而每種情況下我都去上學(xué)” 命題符號(hào)化的要點(diǎn)要準(zhǔn)確確定原子命題，并將其形式化。要選用恰當(dāng)?shù)穆?lián)結(jié)詞，尤其要善于識(shí)別自然語(yǔ)言中的聯(lián)結(jié)詞（有時(shí)