《命題邏輯基本概念.ppt》由會員分享，可在線閱讀，更多相關(guān)《命題邏輯基本概念.ppt（57頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第一部分數(shù)理邏輯,傳統(tǒng)邏輯與數(shù)理邏輯：邏輯一詞源于希臘文，意思指：詞、思想、理性、規(guī)律等。邏輯學(xué)研究的是：判別一個推理過程是否正確的標準。數(shù)理邏輯也叫符號邏輯，即用人工符號來書寫邏輯法則，它是一門涉及數(shù)學(xué)、邏輯學(xué)、哲學(xué)等幾門學(xué)科的橫向交叉學(xué)科。,傳統(tǒng)邏輯用以表示命題形式和推理形式的是自然語言的某些詞語，而自然語言是多義的，不適于用以精確地表示各種命題形式和推理形式。數(shù)理邏輯克服了這方面的局限性，以其特有的人工符號來書寫邏輯法則，突出體現(xiàn)了方便、精確的優(yōu)勢。,數(shù)理邏輯是用數(shù)學(xué)方法來研究推理的形式結(jié)構(gòu)和推理規(guī)律的數(shù)學(xué)學(xué)科，它與數(shù)學(xué)的其它分支、計算機科學(xué)、人工智能、語言學(xué)等學(xué)科均有密切的聯(lián)系。命題邏輯和一階謂詞邏輯是數(shù)理邏輯中最成熟的部分，在計算機科學(xué)中應(yīng)用最為廣泛，其中命題邏輯是數(shù)理邏輯的最基礎(chǔ)部分，謂詞邏輯是在它的基礎(chǔ)上發(fā)展起來的。,一、主要內(nèi)容,命題邏輯基本概念命題邏輯等值演算命題邏輯推理理論一階邏輯基本概念一階邏輯等值演算與推理理論,二、學(xué)習(xí)要求,深刻理解命題、聯(lián)結(jié)詞、復(fù)合命題、命題公式、等值式、等值演算、推理及證明等概念熟練進行等值演算與構(gòu)造證明,第一章命題邏輯基本概念,本章的主要內(nèi)容：命題、聯(lián)結(jié)詞、復(fù)合命題命題公式、賦值、命題公式的分類本章與后續(xù)各章的關(guān)系本章是后續(xù)各章的準備或前提,1.1命題與聯(lián)結(jié)詞,一、命題及其分類1．命題與真值,命題：能判斷真假的陳述句。,感嘆句、疑問句、祁使句都不是命題,真值：用真值來描述命題是“真”還是“假”。分別用“1”和“0”或“T”和“F”表示。,模糊的陳述句不是命題例如：他很高?自相矛盾的句子不是命題例如：我正在說謊（悖論）,命題是陳述句，但陳述句不一定都是命題,悖論就是自相矛盾的句子，如果承認它是正確的，則可以推出它是錯誤的。而如果承認它是錯誤的，又能推出它是正確的。,關(guān)于悖論,如果理發(fā)師的頭由別人給他理,也就是說理發(fā)師自己不替自己理發(fā),那么按照規(guī)定,這位理發(fā)師應(yīng)該給自己理發(fā)。另一方面,如果理發(fā)師的頭由自己理,那么按照規(guī)定,理發(fā)師不能給自己理發(fā)。,例：一個村上，有一個理發(fā)師公開宣布他給而且只給村子中所有自己不替自己理發(fā)的人理發(fā)?，F(xiàn)在要問：誰給這個理發(fā)師理發(fā)？,這就是由19世紀數(shù)學(xué)家希爾伯特提出的著名的“理發(fā)師悖論”。這一悖論的提出，指出康托爾集合論的理論基礎(chǔ)的不足之處，促進了集合論的發(fā)展。所以悖論的提出并不可怕，它只是表明數(shù)學(xué)理論的基礎(chǔ)缺乏完備性。只要完善理論基礎(chǔ)，就可以避免悖論的產(chǎn)生。,(1）是有理數(shù).（2）2+5＝7.（3）x+5＞3.（4）你去教室嗎？（5）這個蘋果真大呀?。?）請不要講話！（7）明年元旦下雪.,解：（1）是假命題，（2）是真命題.（7）是命題，它的真值現(xiàn)在不知道，到明年元旦就知道了。可見命題的真值是客觀存在的，不以我們是否知道而改變。,例：下列句子中哪些是命題？,（1）判斷一個語句是否為命題，首先看是否為陳述句，再看其真值是否唯一。（2）“能判斷真假”并不同于“已知真假”。,注意：,2.命題的分類,（1）簡單命題（也稱原子命題）由簡單句形成的命題。（2）復(fù)合命題：由一個或幾個簡單命題通過聯(lián)結(jié)詞的聯(lián)接而構(gòu)成的命題。,例：李明既是三好學(xué)生又是足球隊員。張平或者正在釣魚或者正在睡覺。如果明天天氣晴朗，那么我們舉行運動會。,3.簡單命題符號化（1）用小寫英文字母p，q，r，…，pi，qi，ri…（i≥1）表示簡單命題。（2）用“1”表示真，用“0”表示假,例如：令p：是有理數(shù)，則p的真值為0。q：2+5=7，則q的真值為1。,二、聯(lián)結(jié)詞與復(fù)合命題,1．否定式與否定聯(lián)結(jié)詞“?”定義1.1：設(shè)p為命題，復(fù)合命題“非p”（或“p的否定”）稱為p的否定式，記作?p，符號?稱作否定聯(lián)結(jié)詞，并規(guī)定?p為真當且僅當p為假。,2．合取式與合取聯(lián)結(jié)詞“∧”,定義1.2：設(shè)p，q為二命題，復(fù)合命題“p并且q”（或“p與q”）稱為p與q的合取式，記作p∧q，∧稱作合取聯(lián)結(jié)詞，并規(guī)定p∧q為真當且僅當p與q同時為真。,例將下列命題符號化：（1）吳穎既用功又聰明。（2）吳穎不僅用功而且聰明。（3）吳穎雖然聰明，但不用功。（4）張輝與王麗都是三好生。（5）張輝與王麗是同學(xué)。,（1）-（3）說明描述合取式的靈活性與多樣性（4）-（5）要求分清聯(lián)結(jié)詞“與”聯(lián)結(jié)的復(fù)合命題與簡單命題,3.析取式與析取聯(lián)結(jié)詞“∨”,定義1.3：設(shè)p,q為二命題，復(fù)合命題“p或q”稱作p與q的析取式，記作p∨q，∨稱作析取聯(lián)結(jié)詞，并規(guī)定p∨q為假當且僅當p與q同時為假。,例：將命題“他可能是100米或400米賽跑的冠軍?！狈柣?。,解：令p：他可能是100米賽跑冠軍；q：他可能是400米賽跑冠軍。,則命題可表示為p∨q。,,,,設(shè)p、q是兩個命題，p排斥或（不可兼或）q是一個復(fù)合命題，記作p∨q。,,令p：今天晚上我在家看電視。q：今天晚上我去劇場看戲。命題可表示為p∨q，或者表示為（p∧q∨(p∧q)。,例：今天晚上我在家看電視或去劇場看戲。,,例將下列命題符號化：（1）2或4是素數(shù)。（2）2或3是素數(shù)。（3）4或6是素數(shù)。（4）小元元只能拿一個蘋果或一個梨。（5）王小紅生于1975年或1976年。,（1）-（3）為相容或（4）-（5）為排斥或,4.蘊涵式與蘊涵聯(lián)結(jié)詞“?”,定義1.4：設(shè)p,q為二命題，復(fù)合命題“如果p,則q”稱作p與q的蘊涵式，記作p?q，并稱p是蘊涵式的前件，q為蘊涵式的后件，?稱作蘊涵聯(lián)結(jié)詞，并規(guī)定，p?q為假當且僅當p為真q為假。,（1）p?q的邏輯關(guān)系：p為q的充分條件，q為p的必要條件（2）“如果p,則q的不同表述法很多：若p，則q；只要p，就q；p僅當q；只有q才p；除非q,才p;除非q，否則非p；…．,說明：,下例有助于理解蘊涵式真值表：,例：一位父親對兒子說：“如果我去書店，就一定給你買本《兒童畫報》。”問：什么情況下父親食言？,解：可能情況有四種：(1)父親去了書店，給兒子買了《兒童畫報》。(2)父親去了書店，卻沒給兒子買《兒童畫報》。(3)父親沒去書店，卻給兒子買了《兒童畫報》。(4)父親沒去書店，也沒給兒子買《兒童畫報》。顯然，(1)、(4)父親沒有食言，(3)與父親的許諾沒有抵觸，當然也沒有食言，只有(2)算食言，而這種情況正好對應(yīng)蘊涵式為假的“前件真后件假”的條件。,例：用符號形式表示下列命題。(1)如果明天早上下雨或下雪,那么我不去學(xué)校。(2)如果明天早上不下雨且不下雪,那么我去學(xué)校。(3)如果明天早上不是下雨又下雪，那么我去學(xué)校。(4)只有當明天早上不下雨且不下雪時,我才去學(xué)校。,解:令p：明天早上下雨；q：明天早上下雪；r：我去學(xué)校。(1)（p∨q）→r；(2)（p∧q）→r；(3)(p∧q）→r；(4)r→（p∧q）,練習(xí)：令p,q,r,s代表以下命題：p：我在午飯前寫完了計算機程序；q：我要在下午打網(wǎng)球；r：陽光明媚；s：濕度很低。給出以下句子的符號化形式：(a)如果陽光明媚，那么我要在下午打網(wǎng)球；(b)在午飯前寫完了計算機程序是我在下午打網(wǎng)球的必要條件；(c)濕度很低和陽光明媚是我在下午打網(wǎng)球的充分條件。,例：設(shè)p：天冷，q：小王穿羽絨服，將下列命題符號化：（1）只要天冷，小王就穿羽絨服。（2）因為天冷，所以小王穿羽絨服。（3）若小王不穿羽絨服，則天不冷。（4）只有天冷，小王才穿羽絨服。（5）除非天冷，小王才穿羽絨服。（6）除非小王穿羽絨服，否則天不冷。（7）如果天不冷，則小王不穿羽絨服。（8）小王穿羽絨服僅當天冷的時候。,解：（1）,（2）,（3）,（6）符號化為p?q其余的符號化為q?p。,5.等價式與等價聯(lián)結(jié)詞,定義1.5：設(shè)p,q為二命題，復(fù)合命題“p當且僅當q”稱作p與q的等價式，記作p?q，?稱作等價聯(lián)結(jié)詞，并規(guī)定，p?q為真當且僅當p與q同時為真或同時為假.,說明：p?q的邏輯關(guān)系為p與q互為充分必要條件。,例：非本倉庫工作人員，一律不得入內(nèi)。,解：令p：某人是倉庫工作人員；q：某人可以進入倉庫。則上述命題可表示為p?q。,6.邏輯聯(lián)結(jié)詞與自然語言中聯(lián)結(jié)詞的關(guān)系：,否定?：不是，沒有，非，不。合取?：并且，同時，和，既…又…，不但…而且…，雖然…但是…。析取?：或者，或許，可能。蘊涵?：若…則…，假如…那么…，既然…那就…，倘若…就…，只要…就，只有…才，…。等價?：當且僅當，充分必要，相同，一樣，…。,?,?,?,?,?,同級按先出現(xiàn)者先運算。若有括號時，先進行括號內(nèi)運算。,7.聯(lián)結(jié)詞的運算順序：,例：(q?p)?q?p?p,8.復(fù)合命題符號化,（1）從語句中分析出各簡單命題，將它們符號化；（2）使用合適的命題聯(lián)結(jié)詞，把簡單命題逐個聯(lián)結(jié)起來，組成復(fù)合命題的符號化表示。,例：將下列命題符號化：（1）派小王或小李出差。（2）我們不能既劃船又跑步。（3）如果你來了，那么他唱不唱歌將看你是否伴奏而定。（4）如果李明是體育愛好者，但不是文藝愛好者，那么李明不是文體愛好者。（5）假如上午不下雨，我去看電影，否則就在家里看書。,解（1）令p：派小王出差；q：派小李出差。命題符號化為p∨q。,（2）令p：我們劃船；q：我們跑步。則命題可表示為(p∧q）。,（3）令p：你來了；q：他唱歌；r：你伴奏。則命題可表示為p→（q?r）,（4）令p：李明是體育愛好者；q：李明是文藝愛好者。則命題可表示為（p∧q）→（p∧q）,（5）令p：上午下雨；q：我去看電影；r：我在家看書。則命題可表示為（p→q）∧（p→r）。,練習(xí)1.判斷下列語句哪些是命題，若是命題，則指出其真值。（1）只有小孩才愛哭。（2）X+6=Y（3）銀是白的。（4）起來吧，我的朋友。,(是假),(不是),(是真),(不是),2．將下列命題符號化（1）我看見的既不是小張也不是老李。,解令p：我看見的是小張；q：我看見的是老李。,則該命題可表示為p∧q,（2）如果晚上做完了作業(yè)并且沒有其它的事，他就會看電視或聽音樂。,解令p：他晚上做完了作業(yè)；q：他晚上有其它的事；r：他看電視；s：他聽音樂。則該命題可表示為（p∧q）→（r∨s）,1.2命題公式及其賦值,一、命題變項與合式公式1．命題變項（或命題變元）（1）命題常項真值惟一確定的簡單命題（2）命題變項真值可以變化的陳述句（3）常項與變項均用p,q,r,…,pi,qi,ri,…,等表示.,2．合式公式（簡稱公式）,定義1.6合式公式的遞歸定義：（1）原子合式公式（單個命題變項）（2）若A是合式公式，則(?A)也是合式公式（3）若A,B是合式，則(A?B),(A?B),(A?B),(A?B)也是合式公式（4）只有有限次地應(yīng)用（1）-（3）形成的符號串才是合式公式,例：下列符號串是否為命題公式。（1）p→(q∧pr）；（2）（p∨q）→（（q∧r））,解：（1）不是命題公式。（2）是命題公式。,３．合式公式的層次,定義1.7（1）若公式A是單個的命題變項，則稱A為0層合式.（2）稱A是n+1(n≥0)層公式是指下面情況之一：(a)A=?B,B是n層公式；(b)A=B?C,其中B,C分別為i層和j層公式，且n=max(i,j)；(c)A=B?C,其中B,C的層次及n同(b)；(d)A=B?C,其中B,C的層次及n同(b)；(e)A=B?C,其中B,C的層次及n同(b).（3）若公式A的層次為k,則稱A為k層公式.,例如：公式A=p,B=?p,C=?p?q,D=?(p?q)?r,E=((?p?q)?r)?(?r?s),分別為0層，1層，2層，3層，4層公式.,二、公式的賦值（或解釋）與真值表,1.公式的賦值定義1.8（1）賦值（解釋）設(shè)p1,p2,…,pn是出現(xiàn)在公式A中的全部的命題變項，給p1,p2,…,pn各指定一個真值，稱為對A的一個賦值或解釋。,（2）成真賦值若指定的一組值使A的真值為1，則稱這組值為A的成真賦值。（3）成假賦值若使A的真值為0，則稱這組值為A的成假賦值。,例如，000,010,101,110是?(p?q)?r的成真賦值，而001,011,100,111是成假賦值.,2.公式的類型,定義1.9：（1）重言式（也稱永真式）在各種賦值下取值均為真。（2）矛盾式（也稱為永假式）在各種賦值下取值均為假。（3）可滿足式（不是矛盾式的公式）。,判斷(p??p)?q,(p??p)??q,p??q的類型？,問：（1）如何判斷公式的類型？（2）如何求出公式A的全部成真與成假賦值？,答案：重言式、矛盾式、可滿足式.,3．真值表,定義1.10：A的真值表?A的取值情況列成的表。,例：寫出下列公式的真值表A=(p?q)??rB=(q?p)?q?pC=?(?p?q)?q,A的真值表,從上表看出A的成真與成假賦值及它的類型,B的真值表,從表看出B是哪種類型公式？,C的真值表,C是哪種類型?,第一章小結(jié),1．主要內(nèi)容命題、真值、命題的分類、命題符號化聯(lián)結(jié)詞?,?,?,?,?及復(fù)合命題符號化命題公式及層次公式的類型真值表及應(yīng)用,深刻理解各聯(lián)結(jié)詞的邏輯關(guān)系會求復(fù)合命題的真值熟練地將復(fù)合命題符號化準確地求公式的真值表，并用它求公式成真與成假賦值及判斷公式類型,2．要求,練習(xí)：1．將下列命題符號化（1）豆沙包是由面粉和紅小豆做成的.（2）蘋果樹和梨樹都是落葉喬木.（3）王小紅或李大明是物理組成員.（4）王小紅或李大明中的一人是物理組成員.（5）由于交通阻塞，他遲到了.（6）如果交通不阻塞，他就不會遲到.（7）他沒遲到，所以交通沒阻塞.（8）除非交通阻塞，否則他不會遲到.（9）他遲到當且僅當交通阻塞.,提示：(1)分清復(fù)合命題與簡單命題；(2)分清相容或與排斥或；(3)分清充分與必要條件及充分必要條件。,答案：（1）是簡單命題（2）是合取式（3）是析取式（相容或）（4）排斥或設(shè)p:交通阻塞，q:他遲到（5）p?q,（6）?p??q或q?p（7）?q??p或p?q,（8）q?p或?p??q（9）p?q或?p??q可見（5）與（7），（6）與（8）等值,2．p:2是素數(shù)；q:北京比天津人口多；r:美國的首都是舊金山。求下面命題的真值（1）(p?q)?r（2）(q?r)?(p??r)（3）(q?r)?(p??r)（4）(q?p)?((p??r)?(?r??q)),答案：真值分別為0，1，0，0,3．用真值表判斷下面公式的類型（1）p?r??(q?p)（2）((p?q)?(?q??p))?r（3）(p?q)?(p?r),提示：按層次寫真值表，由最后一列判類型。,答案：（1）為矛盾式，（2）為重言式，（3）為可滿足式,作業(yè)：,習(xí)題一1，4，8，11，12，14，15，19（1，2，3，6），20（1，3）21（2），24，25,