離散第9講命題與邏輯聯(lián)結(jié)詞new

1、 1 11 1級專業(yè)選修課程級專業(yè)選修課程 授課人：王薇授課人：王薇信息與計算教研室信息與計算教研室離散數(shù)學(xué)數(shù)理邏輯代數(shù)結(jié)構(gòu)圖 論集合代數(shù)命題邏輯謂詞邏輯集合與關(guān)系函數(shù)基本概念矩陣表示典型圖樹本教材離散數(shù)學(xué)知識結(jié)構(gòu)離散數(shù)學(xué)前言vPowerPoint Template_Sub 邏輯學(xué)是一門非常古老的學(xué)科，邏輯學(xué)是一門非常古老的學(xué)科，它是它是研究人類推理過程的研究人類推理過程的科學(xué)科學(xué)。到現(xiàn)在已經(jīng)有了兩千多年的歷史。古典邏輯學(xué)主要到現(xiàn)在已經(jīng)有了兩千多年的歷史。古典邏輯學(xué)主要起源于古希臘學(xué)者亞里士多德的邏輯學(xué)說，他創(chuàng)作的工起源于古希臘學(xué)者亞里士多德的邏輯學(xué)說，他創(chuàng)作的工具論一書是古代一部最完備的邏輯

2、學(xué)著作具論一書是古代一部最完備的邏輯學(xué)著作。古典邏輯學(xué)的基本特點是用自然語言描述對邏輯的研究，古典邏輯學(xué)的基本特點是用自然語言描述對邏輯的研究，而一旦超出這個范圍，引入數(shù)學(xué)的方法來研究邏輯，就產(chǎn)而一旦超出這個范圍，引入數(shù)學(xué)的方法來研究邏輯，就產(chǎn)生了遠(yuǎn)遠(yuǎn)優(yōu)于古典邏輯學(xué)的現(xiàn)代邏輯學(xué)生了遠(yuǎn)遠(yuǎn)優(yōu)于古典邏輯學(xué)的現(xiàn)代邏輯學(xué)。 數(shù)理邏輯也稱符號邏輯，是現(xiàn)代邏輯學(xué)研究的主體部分，數(shù)理邏輯也稱符號邏輯，是現(xiàn)代邏輯學(xué)研究的主體部分，是是一門運用數(shù)學(xué)方法研究思維規(guī)律的邊緣性學(xué)科一門運用數(shù)學(xué)方法研究思維規(guī)律的邊緣性學(xué)科。將推理將推理變成數(shù)學(xué)演算變成數(shù)學(xué)演算，這是數(shù)理邏輯的指導(dǎo)思想，并且已經(jīng)成為，這是數(shù)理邏輯的指導(dǎo)思想

3、，并且已經(jīng)成為這門學(xué)科的主要特征這門學(xué)科的主要特征 。數(shù)理邏輯是用形式化數(shù)理邏輯是用形式化(符號化符號化)方法來研究推理的科學(xué)方法來研究推理的科學(xué)。* *命題邏輯研究命題和命題連接詞的邏輯結(jié)構(gòu)以及命題之間的推理關(guān)系。命題邏輯:推理的基本要素是命題. 引言 先看著名物理學(xué)家愛因斯坦出過的一道題： 一個土耳其商人想找一個十分聰明的助手協(xié)助他經(jīng)商，有兩人前來應(yīng)聘，這個商人為了試試哪個人更聰明些，就把兩個人帶進(jìn)一間漆黑的屋子里，他打開燈后說：“這張桌子上有五頂帽子，兩頂是紅色的，三頂是黑色的，現(xiàn)在，我把燈關(guān)掉，而且把帽子擺的位置弄亂，然后我們?nèi)齻€人每人摸一頂帽子戴在自己頭上，在我開燈后，請你們盡快說出

4、自己頭上戴的帽子是什么顏色的?！闭f完后，商人將電燈關(guān)掉，然后三人都摸了一頂帽子戴在頭上，同時商人將余下的兩頂帽子藏了起來，接著把燈打開。這時，那兩個應(yīng)試者看到商人頭上戴的是一頂紅帽子，其中一個人便喊道：“我戴的是黑帽子?！?請問這個人說得對嗎？他是怎么推導(dǎo)出來的呢？請問這個人說得對嗎？他是怎么推導(dǎo)出來的呢？ 要回答這樣的問題，實際上就是看由一些諸如要回答這樣的問題，實際上就是看由一些諸如“商人戴的是紅帽子商人戴的是紅帽子”這樣的這樣的前提前提能否推出能否推出“猜出答猜出答案的應(yīng)試者戴的是黑帽子案的應(yīng)試者戴的是黑帽子”這樣的這樣的結(jié)論結(jié)論來。來。 這又需要經(jīng)歷如下過程：這又需要經(jīng)歷如下過程： (

5、1) 什么是前提？有哪些前提？什么是前提？有哪些前提？ (2) 結(jié)論是什么？結(jié)論是什么？ (3) 根據(jù)什么進(jìn)行推理？根據(jù)什么進(jìn)行推理？ (4) 怎么進(jìn)行推理？怎么進(jìn)行推理？ 學(xué)習(xí)命題邏輯學(xué)習(xí)命題邏輯將回答這幾個問題。將回答這幾個問題。-8-第第9講講 命題與邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞vPowerPoint Template_Sub 1命題與邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞2邏輯等價式和邏輯蘊涵式邏輯等價式和邏輯蘊涵式3范式范式4證明技術(shù)（補充）證明技術(shù)（補充）v命題與邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞離散數(shù)學(xué)離散數(shù)學(xué)第第9 9講講 Page Page 5656 to to 7878-10-第第9講講 命題與

6、邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞v內(nèi)容提要內(nèi)容提要命題的概念命題的概念命題、命題真值表示命題、命題真值表示原子命題和復(fù)合命題、命題常元、命題變元原子命題和復(fù)合命題、命題常元、命題變元邏輯聯(lián)結(jié)詞邏輯聯(lián)結(jié)詞 、 、 、 、 命題公式命題公式 公式的歸納定義公式的歸納定義指派指派自然語句的形式化自然語句的形式化-11-第第9講講 命題與邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞v命題命題 (proposition (proposition或或statement) statement) 命題：命題：是一句有確定真假值的是一句有確定真假值的陳述句。陳述句。命題只有兩個結(jié)果，或是真，或是假，但二者或是真，或是假，但二者不能得兼

7、（排中律），也不能不能得兼（排中律），也不能不真又不假。真、假常被稱為命題的真值真、假常被稱為命題的真值 。 命題的真值命題的真值作為命題的陳述句所表達(dá)的判斷結(jié)果稱為命題的作為命題的陳述句所表達(dá)的判斷結(jié)果稱為命題的真值真值, 真值只有真值只有2個個:真或假。用真或假。用T , F或或1 , 0表示。表示。當(dāng)判斷正確或符合客觀實際時，稱該命題當(dāng)判斷正確或符合客觀實際時，稱該命題真真(true)， 否則稱該命題否則稱該命題假假(false)。任何命題的真值都是唯一的任何命題的真值都是唯一的.判斷給定句子是否為命題的步驟判斷給定句子是否為命題的步驟:首先判定它是否為陳述句首先判定它是否為陳述句判斷它

8、是否有唯一的真值判斷它是否有唯一的真值.疑問句、祈使句、感嘆句和悖論等都不是命題。疑問句、祈使句、感嘆句和悖論等都不是命題。悖論悖論：由真推出假又由假推出真的陳述句稱為悖：由真推出假又由假推出真的陳述句稱為悖論。即自相矛盾的句子。論。即自相矛盾的句子。-14-第第9講講 命題與邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞v命題舉例命題舉例 雪是白的雪是白的 半徑為半徑為1的圓的的圓的周長周長為為2 2是偶數(shù)是偶數(shù)且且3也是偶數(shù)也是偶數(shù) 陳勝起義那天杭州下雨陳勝起義那天杭州下雨 大于大于2的偶數(shù)均可以分解為兩個質(zhì)數(shù)的和的偶數(shù)均可以分解為兩個質(zhì)數(shù)的和 數(shù)學(xué)多美啊數(shù)學(xué)多美啊! X+Y=4 “我正在說謊。我正在說謊?！?/p>

9、 我只給那些不給自己刮胡子的人刮胡子我只給那些不給自己刮胡子的人刮胡子TTFT-15-第第9講講 命題與邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞v原子命題和復(fù)合命題原子命題和復(fù)合命題原子命題：原子命題：一個不能再分解成更簡單語句的命題一個不能再分解成更簡單語句的命題原子命題是最簡單的陳述句原子命題是最簡單的陳述句 （1）雪是白的。(T)（2）2+2=5(F)（3）2是素數(shù)。(T)（4）北京是中國的首都。(T) 上述命題都是簡單陳述句，他們都不能分解為更上述命題都是簡單陳述句，他們都不能分解為更簡單的陳述句了，稱這樣的命題為簡單的陳述句了，稱這樣的命題為原子命題.-16-第第9講講 命題與邏輯聯(lián)結(jié)詞命題與邏輯

10、聯(lián)結(jié)詞v原子命題和復(fù)合命題原子命題和復(fù)合命題原子命題通常記為原子命題通常記為p、q、r等小寫字母，等小寫字母，f表示表示恒假命題，恒假命題，t表示恒真命題。表示恒真命題。例：例：p：2000年年4月月5日是星期一。日是星期一。 q: 星期二的前一天是星期一。星期二的前一天是星期一。 恒真恒真 -17-第第9講講 命題與邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞v原子命題和復(fù)合命題原子命題和復(fù)合命題命題常元和變元命題常元和變元原子命題原子命題有確定有確定的的真值，又真值，又稱為命題常元。稱為命題常元。命題變元是指一個命題變元是指一個未確定真值未確定真值的任意命題，其的任意命題，其值在值在0，1上變化上變化。例例

11、 p: x+y=5 不是命題，但不是命題，但x,y一旦確定，它一旦確定，它的真值就確定了。的真值就確定了。這種真值可以變化的簡單陳這種真值可以變化的簡單陳述句稱為命題變元。述句稱為命題變元。命題命題變元變元也用也用p、q、r等小寫字母等小寫字母表示表示。-18-第第9講講 命題與邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞v原子命題和復(fù)合命題原子命題和復(fù)合命題復(fù)合復(fù)合命題：命題： 相對于原子命題的是相對于原子命題的是復(fù)合命題復(fù)合命題，它是由原子命題，它是由原子命題通過通過邏輯聯(lián)結(jié)詞邏輯聯(lián)結(jié)詞進(jìn)行適當(dāng)?shù)慕M合而成的進(jìn)行適當(dāng)?shù)慕M合而成的 。復(fù)合命題的真值不僅依賴于這兩個組成它的命題，而且復(fù)合命題的真值不僅依賴于這兩個

12、組成它的命題，而且還依賴于這個還依賴于這個聯(lián)結(jié)詞聯(lián)結(jié)詞的意義的意義 。-19-第第9講講 命題與邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞v舉例舉例p：3是素數(shù)是素數(shù)；q：3是偶數(shù)是偶數(shù) 利用聯(lián)結(jié)詞利用聯(lián)結(jié)詞“不不”、“或或”、“且且”等可分別等可分別構(gòu)成新命題：構(gòu)成新命題： “非非p”：3不是素數(shù)不是素數(shù)“p或或q” ：3是素數(shù)或偶數(shù)是素數(shù)或偶數(shù)“p并且并且q”： 3是素數(shù)且是偶數(shù)是素數(shù)且是偶數(shù)帶連接詞的命題：帶連接詞的命題：1）并非并非2是無理數(shù)。是無理數(shù)。(T)2） 4是偶數(shù)是偶數(shù)且且4也是素數(shù)。也是素數(shù)。(F)3）2或或4是素數(shù)。是素數(shù)。(T)4）如果如果角角A和角和角B是對頂角，是對頂角，則則角角A

13、=角角B 。(T)5）兩個三角形全等兩個三角形全等當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)它們的它們的3組對應(yīng)邊相等。組對應(yīng)邊相等。 (T) 這幾個命題的真值不僅依賴于這兩個組成它的命題，而這幾個命題的真值不僅依賴于這兩個組成它的命題，而且還依賴于這些聯(lián)結(jié)詞的意義。像這樣的聯(lián)結(jié)詞稱為且還依賴于這些聯(lián)結(jié)詞的意義。像這樣的聯(lián)結(jié)詞稱為邏邏輯聯(lián)結(jié)詞輯聯(lián)結(jié)詞（logical connectives）。）。練習(xí)練習(xí) 所以所以復(fù)合命題復(fù)合命題是由若干個是由若干個簡單命題簡單命題和和若干個若干個連接詞連接詞構(gòu)成的。構(gòu)成的。 下面我們下面我們將將連接詞也符號化連接詞也符號化。-22-第第9講講 命題與邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞v常用常

14、用5 5個邏輯聯(lián)結(jié)詞個邏輯聯(lián)結(jié)詞 一一.否定詞否定詞(negation) ：“P 表示表示P不成立不成立”、“并并非非P” 否定詞是一元運算。否定詞是一元運算。否定的是整個命題否定的是整個命題，并不是否定命題中個別的詞。，并不是否定命題中個別的詞?！癆 A和和B B都大于都大于0 0”的否定：的否定：“A A和和B B都不大于都不大于0 0”“A A和和B B不都大于不都大于0 0”“A A和和B B至少有一個不大于至少有一個不大于0 0”“A A和和B B至少有一個小于等于至少有一個小于等于0 0”“A大于大于0”的否定：的否定： “A不大于不大于0” “A小于等于小于等于0”-23-第第9

15、講講 命題與邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞v常用常用的的5 5個邏輯聯(lián)結(jié)詞個邏輯聯(lián)結(jié)詞 真值表真值表將復(fù)合命題的所有變元的所將復(fù)合命題的所有變元的所有取值列成表，就構(gòu)成真值表有取值列成表，就構(gòu)成真值表PP0110真值表真值表* *練習(xí)練習(xí)1：設(shè)：設(shè) P:今天是周三。今天是周三。 則則 P表示什么？表示什么？練習(xí)練習(xí)2：設(shè)：設(shè) Q:所有的自然數(shù)都是偶數(shù)。所有的自然數(shù)都是偶數(shù)。 則則 Q表示什么？表示什么？-25-第第9講講 命題與邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞v常用常用5 5個邏輯聯(lián)結(jié)詞個邏輯聯(lián)結(jié)詞二二. 合取詞合取詞(conjunction) ： pq表示表示“p并且并且q”、“p和和q都成立都成立”

16、合取詞是二元運算合取詞是二元運算只有當(dāng)只有當(dāng)p和和q均為真時，均為真時，pq才是真才是真的，否則，的，否則，pq是假的是假的是可交換的是可交換的pqpq000010100111p:今天是星期四；今天是星期四；q:今天上離散數(shù)學(xué)課；今天上離散數(shù)學(xué)課；p q：今天是星期四并且上離散數(shù)學(xué)課；：今天是星期四并且上離散數(shù)學(xué)課；* *例例1.如果如果P表示命題表示命題“你去了學(xué)校你去了學(xué)校”,Q表示命題表示命題“我去了工廠我去了工廠”， 那么那么PQ表示命題表示命題”你去了學(xué)校并且我去了工廠你去了學(xué)校并且我去了工廠“。 PQ為真，當(dāng)且僅當(dāng)你、我分別去了學(xué)校和工廠。為真，當(dāng)且僅當(dāng)你、我分別去了學(xué)校和工廠。注

17、注:使用合取聯(lián)結(jié)詞時，不要求兩命題間一定有任何關(guān)系。使用合取聯(lián)結(jié)詞時，不要求兩命題間一定有任何關(guān)系。例例2：P :今天下雨了今天下雨了。Q :教室里有教室里有100把椅子。把椅子。 則則,PQ：今天下雨了且教室里有今天下雨了且教室里有100把椅子。把椅子。離散數(shù)學(xué)第一章：命題邏輯對的說明的說明是二元連接詞是二元連接詞PQ中的中的P，Q可以沒有內(nèi)在聯(lián)系（如例可以沒有內(nèi)在聯(lián)系（如例2）具有對稱性，具有對稱性， PQ 與與Q P 的真值相同的真值相同P P=F可以把若干個命題連接在一起可以把若干個命題連接在一起.如，如， P Q R S 補充練習(xí)補充練習(xí): 將下列命題符號化。將下列命題符號化。 (1

18、) 吳穎吳穎既既用功用功又又聰明。聰明。 (2) 吳穎吳穎不僅不僅用功用功而且而且聰明。聰明。 (3) 吳穎吳穎雖然雖然聰明，聰明，但但不用功。不用功。 (4) 張輝張輝和和王麗王麗都都是三好學(xué)生。是三好學(xué)生。 (5) 張輝與王麗是同學(xué)。張輝與王麗是同學(xué)。 步步驟驟： 先找原子命先找原子命題并題并符符號號化化 再找再找連連接接詞詞1.1. 將將原命原命題題符符號號化化解解 ：首先首先將將原子命原子命題題符符號號化：化： p p: : 吳穎吳穎用功。用功。, ,q q: : 吳穎聰吳穎聰明。明。 r r: : 張輝張輝是三好是三好學(xué)學(xué)生。生。 s s: : 王王麗麗是三好是三好學(xué)學(xué)生。生。 u

19、u : :張輝與張輝與王王麗麗是同是同學(xué)學(xué)。 則則(1)到到(4)分別符號化為分別符號化為 pq，pq，qp，rs. (5)(5)是原子命是原子命題題，符，符號號化化為為u u. .補充練習(xí)補充練習(xí):將下列命題符號化。將下列命題符號化。 (1) 吳穎吳穎既既用功用功又又聰明。聰明。 (2) 吳穎吳穎不僅不僅用功用功而且而且聰明。聰明。 (3) 吳穎吳穎雖然雖然聰明，聰明，但但不用功。不用功。 (4) 張輝張輝和和王麗王麗都都是三好學(xué)生。是三好學(xué)生。 (5) 張輝與王麗是同學(xué)。張輝與王麗是同學(xué)。 (1)(1)到到(4)(4)都是都是復(fù)合命題，它們使用的聯(lián)結(jié)詞表面看來各不相同，但都是合取聯(lián)結(jié)詞，都

20、應(yīng)符號化為，在(5)中，雖然也使用了聯(lián)結(jié)詞“與”，但這個聯(lián)結(jié)詞“與”是聯(lián)結(jié)該句主語的，而整個句子仍是簡單陳述句，所以(5)是原子命題，-30-第第9講講 命題與邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞v常用常用5 5個邏輯聯(lián)結(jié)詞個邏輯聯(lián)結(jié)詞析取詞析取詞(disjunction) ： pq，“p成立或者成立或者q成立成立”、“p或或q”析取詞是二元運算析取詞是二元運算只有當(dāng)只有當(dāng)p和和q的真值均為假時，的真值均為假時， pq才是假的，否則才是假的，否則, pq總是真的總是真的pqpq000011101111p:我上午上離散數(shù)學(xué)；我上午上離散數(shù)學(xué)；q:我上午上概率統(tǒng)計；我上午上概率統(tǒng)計；p q：我上午或者上離散

21、：我上午或者上離散數(shù)學(xué)，或者上數(shù)學(xué)，或者上概率統(tǒng)計；概率統(tǒng)計；p:我上午一二節(jié)課上離散數(shù)學(xué)；我上午一二節(jié)課上離散數(shù)學(xué)；q:我上午一二節(jié)課上我上午一二節(jié)課上概率統(tǒng)計；概率統(tǒng)計；p q：我上午一二節(jié)課要么上：我上午一二節(jié)課要么上離散數(shù)學(xué)，要么上離散數(shù)學(xué)，要么上概率統(tǒng)計概率統(tǒng)計(不不會上兩門會上兩門)；同或同或異或異或 總結(jié)總結(jié)：析取析取一般代表漢語中的一般代表漢語中的“或或”，但漢語中的，但漢語中的“或或”是多含是多含義的，見下表：義的，見下表：或的含義或的含義例子例子說明說明可兼或可兼或晚會上她唱歌或跳舞晚會上她唱歌或跳舞二者均發(fā)生或二者之一發(fā)生二者均發(fā)生或二者之一發(fā)生排斥或排斥或 他上他上“師

22、大師大”或或“南開南開”非此即彼，不可兼得非此即彼，不可兼得表示近似值的或表示近似值的或他休息他休息5或或10分鐘分鐘近似數(shù)，近似數(shù)，5至至10分鐘分鐘由析取的定由析取的定義義可知，可知， 表示可兼或。表示可兼或。例例1：如果如果p，q分別表示分別表示“今晚我看書今晚我看書”和和“今晚我看電視今晚我看電視”， 那么那么pq表示表示“今晚我看書或者看電視今晚我看書或者看電視”。 當(dāng)我今晚看了書，或者看了電視，或者既看了書又看了電視當(dāng)我今晚看了書，或者看了電視，或者既看了書又看了電視時，時，pq為真，只是在我既不看書也不看電視時為真，只是在我既不看書也不看電視時pq為假。為假。 值得注意的是值得注

23、意的是，這里的，這里的“或或”是所謂可兼的，即當(dāng)是所謂可兼的，即當(dāng)p和和q有一為有一為真時，確認(rèn)真時，確認(rèn)pq為真。為真。則則原原命題可表示為：命題可表示為：()()PQPQ 例例2.2.一晚上他在家看書或出去散步。一晚上他在家看書或出去散步。解：解：不可兼或不可兼或 P P：他一晚上在家看書。：他一晚上在家看書。 Q Q：他一晚上出去散步。：他一晚上出去散步。 不可兼或也稱排斥或，它表示這一新命題當(dāng)P為真且Q為假時成真，或反過來，當(dāng)P為假且Q為真時成真。 P和Q均為真或均為假時，這一命題為假。即當(dāng)P和Q中恰有一個為真時它成真，否則它為假。對對的說明的說明是二元連接詞是二元連接詞P Q中的中的

24、P，Q可以沒有內(nèi)在聯(lián)系（如例可以沒有內(nèi)在聯(lián)系（如例2）具有對稱性，具有對稱性， PQ 與與Q P 的真值相同的真值相同P P=T可以把若干個命題連接在一起可以把若干個命題連接在一起.如，如， P Q R S-35-第第9講講 命題與邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞v常用常用5 5個邏輯聯(lián)結(jié)詞個邏輯聯(lián)結(jié)詞蘊涵詞蘊涵詞(implication) ： pq，“如果如果p，那么，那么q”、“p蘊涵蘊涵q”、“p是是q的充分條件的充分條件” 從真值表可以看出，只有當(dāng)前提為從真值表可以看出，只有當(dāng)前提為真，而結(jié)論是假時，真，而結(jié)論是假時，pq才是假的才是假的 pqpq001011100111逆命題逆命題：qp；

25、否命題否命題：pq逆否命題逆否命題：qp命題和逆否命題有相同命題和逆否命題有相同的真值（的真值（驗證一下驗證一下）“如果今天是星期三，那么如果今天是星期三，那么2+3=62+3=6”：前提為假，蘊涵命題為真；前提為假，蘊涵命題為真；前提和結(jié)論之間可以沒有關(guān)系，前提和結(jié)論之間可以沒有關(guān)系，稱為實質(zhì)蘊涵稱為實質(zhì)蘊涵p:天晴；天晴； q:我爬山；我爬山；只要天晴，我就爬山：只要天晴，我就爬山： p q 只有天晴，我才爬山：只有天晴，我才爬山： q p 注意注意： 在使用聯(lián)結(jié)詞在使用聯(lián)結(jié)詞時，要特別注意以下幾點：時，要特別注意以下幾點： 1在自然語言中，在自然語言中，“如果如果p，則，則q”中的前件中

26、的前件p與后件與后件q往往往往具有某種內(nèi)在聯(lián)系。而具有某種內(nèi)在聯(lián)系。而在數(shù)理邏輯中，在數(shù)理邏輯中，p與與q可以無任何內(nèi)可以無任何內(nèi)在聯(lián)系。在聯(lián)系。 2在數(shù)學(xué)或其它自然科學(xué)中，在數(shù)學(xué)或其它自然科學(xué)中，“如果如果p，則，則q”往往表達(dá)的往往表達(dá)的是前件是前件p為真，后件為真，后件q也為真的推理關(guān)系。但在數(shù)理邏輯中，也為真的推理關(guān)系。但在數(shù)理邏輯中，作為一種規(guī)定，當(dāng)作為一種規(guī)定，當(dāng)p為假時，無論為假時，無論q是真是假，是真是假，pq均為真。均為真。也就是說，只有也就是說，只有p為真為真q為假這一種情況使得復(fù)合命題為假這一種情況使得復(fù)合命題pq為假。為假。 例例1 將命題將命題“如果天氣好，那么我去接

27、你。如果天氣好，那么我去接你?！狈柣７柣?。解：設(shè)解：設(shè)p表示表示“天氣好天氣好”，q表示表示“我去接你我去接你”， 那么，那么，pq表示原命題。表示原命題。當(dāng)天氣好時，當(dāng)天氣好時， 我去接了你，這時諾言我去接了你，這時諾言pq真；真； 我沒去接你，則諾言我沒去接你，則諾言pq假。假。 當(dāng)天氣不好時，當(dāng)天氣不好時，我無論去或不去接你均未食言，此我無論去或不去接你均未食言，此時認(rèn)定時認(rèn)定 pq為真是適當(dāng)?shù)?。為真是適當(dāng)?shù)摹?、 、注： 較較 三三個聯(lián)結(jié)詞難個聯(lián)結(jié)詞難理解，但若要理解，但若要對對命命題間題間因果因果關(guān)關(guān)系系進(jìn)進(jìn)行表行表達(dá)達(dá)，則則必必須須引用引用 。例例2 2：令：令P:P:天天氣

28、氣好好 ，Q:Q:我去公我去公園園試將試將下列命下列命題題符符號號化化1 1）若天）若天氣氣好，我就去公好，我就去公園園。 符符號號化化為為：2 2）僅當(dāng)僅當(dāng)天天氣氣好，我才去公好，我才去公園園。 符符號號化化為為：PQQP-39-第第9講講 命題與邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞v常用常用5 5個邏輯聯(lián)結(jié)詞個邏輯聯(lián)結(jié)詞雙向蘊涵詞雙向蘊涵詞(two-way implication) p q，“p當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)q”、 “如果如果p，那么，那么q；反之亦然；反之亦然”只有當(dāng)只有當(dāng)p和和q的真值相同時，的真值相同時，pq才取才取真的真值真的真值 pq與與(pq)(qp)有完全相同的有完全相同的真值真值。

29、（驗證一下驗證一下）pqpq001010100111“只有你健康，你才會感到快樂；只有你健康，你才會感到快樂；只有感覺快樂你才健康只有感覺快樂你才健康”* *例例1如果p表示命題“ABCABC”，q表示命題“ABC與ABC的三邊對應(yīng)相等”，那么pq表示平面幾何中的一個真命題，因為p真時q顯然真，p假時q亦必然假，故p與q同真值。若q表示命題“ABC與ABC的三內(nèi)角對應(yīng)相等”那么pq不再是恒真的了，因p假時q未必為假。離散數(shù)學(xué)第一章：命題邏輯練習(xí): 將將下列命下列命題題符符號號化，化，并討論它們并討論它們的的真值真值。 (1) (1) 根根號號5 5是無理是無理數(shù)當(dāng)數(shù)當(dāng)且且僅當(dāng)僅當(dāng)加拿大位于加拿

30、大位于亞亞洲。洲。 (2) 2+3(2) 2+35 5的充要的充要條條件是根件是根號號5 5是無理是無理數(shù)數(shù)。 (3) (3) 若若兩圓兩圓A A，B B的面的面積積相等，相等，則它們則它們的半的半徑徑相等；反之相等；反之亦然。亦然。 (4) (4) 當(dāng)當(dāng)王小王小紅紅心情愉快心情愉快時時，她她就唱歌；反之，就唱歌；反之，當(dāng)她當(dāng)她唱歌唱歌時時，一定心情愉快。一定心情愉快。 解解 (1)(1): : 令令p p： 根根號號5 5是無理是無理數(shù)數(shù)，真值為真值為1 1， q q：加拿大位于：加拿大位于亞亞洲，洲，真值為真值為0 0， 則將則將(1)(1)符符號號化化為為p p q q，其，其真值為真值

31、為0. 0. (2)(2): : 令令r r：2 23 35 5，其，其真值為真值為1 1， 則將則將(2)(2)符符號號化化為為r r p p，真值為真值為1. 1. (3)(3): : 令令s s：兩圓兩圓A A，B B面面積積相等，相等， t t：兩圓兩圓A A，B B的半的半徑徑相等，相等， 則將則將(3)(3)符符號號化化為為s s t t，雖雖然不知道然不知道s s，t t的的真值真值，但由，但由s s與與t t的的內(nèi)內(nèi)在在聯(lián)聯(lián)系可知，系可知，s s t t的的真值為真值為1. 1. (4)(4): : 令令u u：王?。和跣〖t紅心情愉快，心情愉快， v v：王小：王小紅紅唱歌，唱

32、歌， 則將則將(4)(4)符符號號化化為為u u v. v.其其真值真值要由具體情要由具體情況況而定。而定。 練習(xí)練習(xí)：填填空空PQPQPQPQ已知已知 為為T T，則則P P為為（ ），），Q Q為為（ ）。）。已知已知 為為F F，則則P P為為（ ），），Q Q為為（ ）。）。已知已知P P為為F F，則則 為為（ ）。）。已知已知P P為為T T，則則 為為（ ）。）。已知已知 為為T T，且，且P P為為F F，則則Q Q為為（ ）。）。已知已知 為為F F，則則P P為為（ ），），Q Q為為（ ）。）。已知已知P P為為F F，則則 為為（ ）。）。已知已知Q Q為為T T，則則

33、 為為（ ）。）。已知已知 為為F F，則則P P為為（ ），），Q Q為為（ ）。）。 已知已知P P為為T T， 為為T T，則則Q Q為為（ ）。）。PQPQPQPQPQ PQT TT TT TT TT TF FF FF FF FF FT TT TT TT T以上定義了五種最基本、最常用、也是最重要的聯(lián)結(jié)詞以上定義了五種最基本、最常用、也是最重要的聯(lián)結(jié)詞， ，將它們組成一個集合，將它們組成一個集合， ，稱為一個，稱為一個聯(lián)結(jié)詞集聯(lián)結(jié)詞集。其中。其中為一元聯(lián)結(jié)詞，其余的都為一元聯(lián)結(jié)詞，其余的都是二元聯(lián)結(jié)詞。是二元聯(lián)結(jié)詞。 使用這些聯(lián)結(jié)詞有什么好處呢？使用這些聯(lián)結(jié)詞有什么好處呢？ 可以將復(fù)雜

34、命題表示成簡單可以將復(fù)雜命題表示成簡單的符號公式。的符號公式。注意： 4 4個聯(lián)個聯(lián)接接詞構(gòu)詞構(gòu)成的成的復(fù)復(fù)合命合命題題均可不均可不顧顧及命及命題間題間是否有是否有內(nèi)內(nèi)在在聯(lián)聯(lián)系，而只是根據(jù)系，而只是根據(jù)聯(lián)聯(lián)接接詞詞和原子命和原子命題題的的真真值值確定確定它們它們的的真值真值。 、 、 、-45-第第9講講 命題與邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞v命題公式命題公式 (proposition formula) (proposition formula) 命題公式：命題公式：是一個表達(dá)式，它是由命題常元、命題是一個表達(dá)式，它是由命題常元、命題變元、聯(lián)結(jié)詞符號和圓括號所組成的一個字符串變元、聯(lián)結(jié)詞符號和圓

35、括號所組成的一個字符串 歸納定義：（歸納定義：（看看16頁歸納定義頁歸納定義）命題常元和命題變元是命題公式，也稱為原子公式或原子命題常元和命題變元是命題公式，也稱為原子公式或原子如果如果A，B是命題公式，那么（是命題公式，那么（A）、（）、（AB）、）、 （AB）、（）、（AB）、（）、（AB）也是命題公式）也是命題公式只有有限步引用條款（只有有限步引用條款（1）、（）、（2）所組成的符號串是命題）所組成的符號串是命題公式公式 -46-第第9講講 命題與邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞v簡寫約定簡寫約定為了減少圓括號的使用，我們約定：為了減少圓括號的使用，我們約定：省掉最外面的括號省掉最外面的括號聯(lián)

36、結(jié)詞的優(yōu)先級從高到低是聯(lián)結(jié)詞的優(yōu)先級從高到低是 、（、（、）、）、結(jié)合能力平等的聯(lián)結(jié)詞從左到右運算結(jié)合能力平等的聯(lián)結(jié)詞從左到右運算(p) (q (r q) s)p q (r q s)-47-第第9講講 命題與邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞v指派指派(assignment) (assignment) 設(shè)設(shè)公式公式A含有含有n個命題變元個命題變元p1， p2 ， pn記為記為A(p1, pn ) 給定這給定這n個變元任意一組確定的值個變元任意一組確定的值（每一變元都（每一變元都有取真或假兩種可能），公式有取真或假兩種可能），公式A得到一個確定的得到一個確定的值（值（1或或0），），我們稱這一組確定的值

37、為公式我們稱這一組確定的值為公式A的的一組完全指派一組完全指派 常用常用 表示指派，若在某一指派表示指派，若在某一指派 下下A取真的真值，取真的真值，則稱則稱 弄真弄真A，記為，記為 (A)=1, 反之稱反之稱 弄假弄假A，記，記為為 (A)=0 -48-第第9講講 命題與邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞v指派舉例指派舉例使公式使公式A: (pq)r)p為真的指派為真的指派 (A)=11. (pq)r)=1， (p)=1， 2. (pq)r)=0， (p)=0 (r)=0, ( (r r)=1)=11.1. (q)=11.1.1. (r)=01.1.2. (r)=1 1.2. (q q)=01.2.

38、1. (r)=02.1. (q)=02.2. (q)=1(1,1,0)(1,1,1)(1,0,0)(0,0,1)(0,1,1)-49-第第9講講 命題與邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞v復(fù)合命題公式的真值表復(fù)合命題公式的真值表 首先確定在公式中出現(xiàn)的首先確定在公式中出現(xiàn)的命題變元的個數(shù)。命題變元的個數(shù)。寫出公式寫出公式A的的所有指派所有指派，一個指派為一行，若有，一個指派為一行，若有n個命題變個命題變元，則有元，則有2n組指派，也就是說真值表有組指派，也就是說真值表有2n+1行。行。確定公式中確定公式中聯(lián)結(jié)詞的個數(shù)聯(lián)結(jié)詞的個數(shù)，寫出單個聯(lián)結(jié)詞的真值，一般講，寫出單個聯(lián)結(jié)詞的真值，一般講，一個聯(lián)結(jié)詞對

39、應(yīng)著一列。一個聯(lián)結(jié)詞對應(yīng)著一列。 (pq)r)p的真值表的真值表 pqrpqr(pq)r(pq)r)p00001100010001010011001100011000111101000011011111111011(PQ)0110原命原命題題Q QP PPQ（）P Q （）PQPQ （）（）0 01 11 11 11 11 11 10 00 00 00 00 00 00 00 00 00 00 00 00 01 11 11 11 1例例2 2：上海到北京的14次列車是下午五點半開或六點開。復(fù)合命題的真值表復(fù)合命題的真值表 -51-第第9講講 命題與邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞v語句形式化舉例語句

40、形式化舉例設(shè)設(shè)p：a是偶數(shù)是偶數(shù) q：a是奇數(shù)是奇數(shù) r：a是質(zhì)數(shù)是質(zhì)數(shù) s：a=2，如，如何理解下述命題公式何理解下述命題公式pq lpr s p （r s）rs q（qs）r r （q s）1.r q s-52-第第9講講 命題與邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞v語句形式化舉例語句形式化舉例 我和他既是兄弟又是同學(xué)我和他既是兄弟又是同學(xué) pq，其中：，其中：p：我和他是兄弟，：我和他是兄弟，q：我和他是同學(xué)：我和他是同學(xué) 我和他至少有一個要去外地我和他至少有一個要去外地pq，其中：，其中：p：我去外地，：我去外地，q：他去外地：他去外地 狗急跳墻狗急跳墻pq，其中：，其中： p：狗急了，：狗急了

41、，q：狗跳墻：狗跳墻 除非他來，否則我不同他和解除非他來，否則我不同他和解pq，(pq)(pq)，其中：，其中： p：他來，：他來，q：我同他和解：我同他和解-53-第第9講講 命題與邏輯聯(lián)結(jié)詞命題與邏輯聯(lián)結(jié)詞v語句形式化舉例語句形式化舉例 如果你和他不都是傻子，那么你們倆都不會如果你和他不都是傻子，那么你們倆都不會去自討沒趣去自討沒趣（pq）（rs），其中：），其中： p：你是傻子；：你是傻子；q：他是傻子：他是傻子r：你會去自討沒趣；：你會去自討沒趣；s：他會去自討沒趣：他會去自討沒趣 若天氣若天氣不不下雨或不起霧，則航行比賽將舉行下雨或不起霧，則航行比賽將舉行而且救生表演將進(jìn)行而且救生表演將進(jìn)行 如果他如果他沒來沒來見你，那么他或者是生病了，或見你，那么他或者是生病了，或者是者是不不在本地在本地vPowerPoint Template_Sub 偵探調(diào)查了罪案的四個證人。從證人的話偵探得出的結(jié)論偵探調(diào)查了罪案的四個證人。從證人的話偵探得出的結(jié)論是：是：如果男管家說的是真話，那么廚師說的也是真話；如