命題邏輯及命題演算.ppt

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

1、第一章命題邏輯,一、緒言1、離散數(shù)學(xué)課程簡介:--研究離散結(jié)構(gòu)的數(shù)學(xué)分科。辭海79年版，P355,概述和計算機科學(xué)聯(lián)系,和計算機科學(xué)聯(lián)系緊密是計算機科學(xué)的支撐學(xué)科之一，也是信息科學(xué)的數(shù)學(xué)基礎(chǔ)。在計算機理論研究及軟硬件開發(fā)的各個領(lǐng)域都有廣泛的應(yīng)用。在計算機科學(xué)發(fā)展的過程中，各種理論問題的研究交錯地使用著近代數(shù)學(xué)中的不同論題，這些論題構(gòu)成了離散數(shù)學(xué)。,學(xué)習(xí)離散數(shù)學(xué)的重要性,一個土耳其商人想找一個十分聰明的助手協(xié)助他經(jīng)商，有兩人前來應(yīng)聘，這個商人為了試試哪個更聰明些，就把兩個人帶進一間漆黑的屋子里，他打開燈后說：“這張桌子上有五頂帽子，兩頂是紅色的，三頂是黑色的，現(xiàn)在，我把燈關(guān)掉，而且把帽子擺的位置

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

3、引例：,4是素數(shù)；,是無理數(shù)；,大于；,大于嗎？；,請不要吸煙！,定義：命題---具有唯一真值的陳述句。,例我正在說假話；2009年的元旦是晴天。,表示方法：命題（），真（1）假（0）。,否則，某命題是由簡單命題通過聯(lián)結(jié)詞連接在一起的命題，稱之為復(fù)合命題。,非；且；或；如果則；當(dāng)且僅當(dāng)。,“見假為真，見真為假”p讀作“并非p”或“非p”。,（2）合取式：（conjunction）兩個命題P和Q的合取是一個復(fù)合命題，記作PQ。當(dāng)且僅當(dāng)P、Q同時為T時，PQ為T，其他情況下，PQ的真值都是F。合取聯(lián)結(jié)詞“”表示自然語言中的“并且”。,pq讀作“p并且q”或“p且q”,見假為假，全真為真。,（3）析

4、取式：兩個命題P和Q的析取是一個復(fù)合命題，記作PQ。當(dāng)且僅當(dāng)P、Q同時為F時，PQ為F，其他情況下，PQ的真值都是T。析取聯(lián)結(jié)詞“”表示自然語言中的“或”（or）。,見真為真，全假為假。,pq讀作“p或者q”、“p或q”。,（4）蘊涵式：給定兩個命題P和Q，其條件命題是一個復(fù)合命題，記作PQ。當(dāng)且僅當(dāng)P的真值為T，Q的真值為F時，PQ的真值為F，其他情況下，PQ的真值都是T。條件聯(lián)結(jié)詞“”表示自然語言中的“如果，那么”。,pq中的p稱為條件前件，q稱為條件后件,前真后假為假，其他為真。,（5）等價式：給定兩個命題P和Q，其復(fù)合命題PQ稱作雙條件命題。當(dāng)P和Q的真值相同時，PQ的真值為T，否則，

5、PQ的真值都是F。雙條件聯(lián)結(jié)詞“”表示自然語言中的“當(dāng)且僅當(dāng)”。,,pq讀作“p與q互為條件”，“p當(dāng)且僅當(dāng)q”。,相同為真，相異為假。,1-1.2復(fù)合命題的符號化,復(fù)合命題的符號化的基本步驟1)找出各個原子命題，并逐個符號化；2)找出各個連接詞，符號成相應(yīng)聯(lián)結(jié)詞；3)用聯(lián)結(jié)詞將原子命題逐個聯(lián)結(jié)起來；,1-1.2復(fù)合命題的符號化,例將下列命題符號化(1)北京不是村莊P:表示“北京是村莊”P:北京不是村莊(2)小王是游泳冠軍和百米賽跑冠軍P：小王是游泳冠軍;Q：小王百米賽跑冠軍PQ:小王是游泳冠軍和百米賽跑冠軍,1-1.2復(fù)合命題的符號化,例將下列命題符號化(3)小明或者小華能解夠出這道題P：小

6、明能夠解出這道題;Q：小華能夠解出這道題PQ(4)小王或者小李中的一個能夠當(dāng)上班長P：小王能夠當(dāng)上班長;Q：小李能夠當(dāng)上班長,1-1.2復(fù)合命題的符號化,例將下列命題符號化(5)今夜你若敢去公墓，那么我就咬掉我的鼻子或咬掉我的耳朵P：今夜你敢去公墓。Q：咬掉我的鼻子。R:咬掉我的耳朵,P(QR),1-1.2復(fù)合命題的符號化,例將下列命題符號化(6)王樂是計算機系的學(xué)生，生于1980年或1981年,是三好學(xué)生。P：王樂是計算機系的學(xué)生。Q：生于1980年。R:生于1981年.S:是三好學(xué)生.,P(QR)S,四、命題公式及其賦值,2.命題變項（命題變元）,3.合式公式（命題公式）：將命題變元用聯(lián)結(jié)

7、詞或圓括號按一定的邏輯關(guān)系聯(lián)結(jié)起來的符號串稱為合式公式或命題公式。（A，B）,定義：（1）單個命題變項可被稱為合式公式；（2）若是合式公式，則也是合式公式；（3）若是合式公式，則也是合式公式；（4）將1-3有限次的聯(lián)結(jié)起來也是合式公式。,定義：設(shè)是出現(xiàn)在公式中的全部的命題變項，給各指定一個真值，稱為對的一個賦值或解釋。若指定的一組值使的真值為1，則稱這組值為的成真賦值，若使的真值為0，則稱這組值為的成假賦值。,例：利用真值表求的成真賦值和成假賦值,練習(xí)：（1）（2）（3）,（2）若在它的各種賦值下取值為假，則稱為矛盾式或永假式；,定義：設(shè)為任一命題公式.(1)若在它的各種賦值下取值為真，則稱為

8、重言式或永真式；,（3）若不是矛盾式，則稱為可滿足式。,第二章命題邏輯等值演算,一、等值式,引例：,與,定義：設(shè)是兩個命題公式，若構(gòu)成的等價式為重言式，則稱是等值的，記作。,練習(xí)：1）與,2）與,等值演算公式：,雙重否定律:AA等冪律：AAA,AAA交換律:ABBA,ABBA結(jié)合律:(AB)CA(BC)(AB)CA(BC)分配律:A(BC)(AB)(AC)A(BC)(AB)(AC),德摩根律:(AB)AB(AB)AB吸收律:A(AB)A,A(AB)A零律:A11,A00同一律:A0A,A1A排中律:AA1矛盾律:AA0,蘊涵等值式:ABAB等價等值式:AB(AB)(BA)假言易位:ABBA等價

9、否定等值式:ABAB歸謬論:(AB)(AB)A注意:A,B,C代表任意的命題公式,等值演算的用途一：證明等值式。例1.10驗證p(qr)(pq)r右(pq)r蘊涵等值式pqr德摩根律p(qr)結(jié)合律p(qr)蘊涵等值式p(qr)蘊涵等值式注:ABAB,練習(xí)：,例證明:p(qr)(pq)r用等值演算不能直接證明兩個公式不等值,證明兩個公式不等值的基本思想是找到一個賦值使一個成真,另一個成假.方法一真值表法（自己證）方法二觀察賦值法.容易看出000,010等是左邊的成真賦值，是右邊的成假賦值.方法三用等值演算先化簡兩個公式，再觀察,例用等值演算法判斷下列公式的類型(1)q(pq)解q(pq)q(p

10、q)（蘊涵等值式）q(pq)（德摩根律）p(qq)（交換律，結(jié)合律）p0（矛盾律）0（零律）由最后一步可知，該式為矛盾式.,(2)(pq)(qp)解(pq)(qp)(pq)(qp)（蘊涵等值式）(pq)(pq)（交換律）1由最后一步可知，該式為重言式.,(3)((pq)(pq))r)解((pq)(pq))r)(p(qq))r（分配律）p1r（排中律）pr（同一律）這不是矛盾式，也不是重言式，而是非重言式的可滿足式.如101是它的成真賦值,000是它的成假賦值.,總結(jié)：A為矛盾式當(dāng)且僅當(dāng)A0A為重言式當(dāng)且僅當(dāng)A1說明：演算步驟不惟一,應(yīng)盡量使演算短些,定義文字：命題變項及其否定統(tǒng)稱為文字。如：p

11、,q簡單析取式：僅有有限個文字組成的析取式。如：p,q,pq,pqr簡單合取式：僅有有限個文字組成的合取式。如：p,q,pq,pqr,二、析取范式與合取范式,命題公式是千變?nèi)f化的，這給研究命題演算帶來困難，這里我們研究如何由一個命題公式化歸為一個標(biāo)準(zhǔn)形式的問題，這樣命題演算的研究問題就歸結(jié)為對標(biāo)準(zhǔn)形式的研究問題，這種標(biāo)準(zhǔn)形式就叫范式。析取范式它是這樣一種標(biāo)準(zhǔn)形式，在此式內(nèi)不出現(xiàn)聯(lián)結(jié)詞及，否定符號只出現(xiàn)在命題變元前。它是一個析取式，式中的每個析取項是個合取式，每個合取式中只包含命題變元或命題變元的否定。例如p(pq)(qr)此式即具有析取范式之形式注意:一個公式的析取范式并不唯一，如p(rq),

12、可以寫成(pp)(rq),合取范式它是這樣一種標(biāo)準(zhǔn)形式，在此式內(nèi)不出現(xiàn)聯(lián)結(jié)詞及，否定符號只出現(xiàn)在命題變元前。它是一個合取式，式中的每個合取項是個析取式，每個析取式中只包含命題變元或命題變元的否定。例如p(pq)(qr)此式即具有合取范式之形式注意:一個公式的合取范式并不唯一，如p(rq)可以寫成(pp)(rq),定義：析取范式：由有限個簡單合取式構(gòu)成的析取式。如：pq,(pq)(pqr)合取范式：由有限個簡單析取式構(gòu)成的合取式。如：pq,（pq）（pqr）范式：析取范式與合取范式統(tǒng)稱為范式。,設(shè)Ai(i=1,2,3,n)為簡單合取式，則A=A1A2An就是析取范式，而B=A1A2An就是合取范

13、式。析取范式和合取范式有下列性質(zhì)：（1）一個析取范式是矛盾式它的每個簡單合取式都是矛盾式。（2）一個合取范式是重言式它的每個簡單析取式都是重言式。,例求下列公式的析取范式與合取范式(1)A=(pq)r解(pq)r(pq)r（消去）pqr（結(jié)合律）這既是A的析取范式（由3個簡單合取式組成的析取式），又是A的合取范式（由一個簡單析取式組成的合取式）,(2)B=(pq)r解(pq)r(pq)r（消去第一個）(pq)r（消去第二個）(pq)r（否定號內(nèi)移德摩根律）這一步已為析取范式（兩個簡單合取式構(gòu)成）繼續(xù)：(pq)r(pr)(qr)（對分配律）這一步得到合取范式（由兩個簡單析取式構(gòu)成）,求范式的具體

14、步驟：（1）消去對,,,來說冗余的聯(lián)結(jié)詞，即，。利用下列等值式：AB(AB)AB(AB)(AB),（2）否定詞的消去或內(nèi)移。利用下列等值式：AB(AB)(AB)AB(AB)AB（3）利用分配律：C(AB)（CA）（CB）C(AB)（CA）（CB）,(3)求(pq)(pr)的析取范式。解：(pq)(pr)(pq)(pr)((pq)p)((pq)r)((pp)(qp))((pr)(qr))(qp)(pr)(qr),(4)求(pq)(pr)的析取/合取范式。解:(1)求析取范式(pq)(pr)(pq)(pr)pq(pr),(4)求(pq)(pr)的析取/合取范式。解：(2)求合取取范式(pq)(pr

15、)(pq)(pr)(pr)(pq)((pr)p)q((pp)(pr))q(ppq)(prq)(合取范式),定義在含有n個命題變項的簡單合取式(簡單析取式)中，若每個命題變項均以文字的形式在其中出現(xiàn)且僅出現(xiàn)一次，而且第i（1in）個文字出現(xiàn)在左起第i位上，稱這樣的簡單合取式（簡單析取式）為極小項（極大項）.,由p,q兩個命題變項形成的極小項與極大項,由p,q,r三個命題變項形成的極小項與極大項,極小項與極大項關(guān)系設(shè)mi和Mi是命題變項p1，p2，pn形成的極小項和極大項，則miMi，Mimi定義設(shè)由n個命題變項構(gòu)成的析（合）取范式中所有的簡單合（析）取式都是極?。ù螅╉?，則稱該析（合）取范式為主

16、析（合）取范式。,由不同最小項所組成的析取式稱為主析取范式由不同最大項所組成的合取式稱為主合取范式,求(pq)(pr)的主析取范式。(pq)(pr)(qp)(pr)(qr)(析取范式)((pr)(qq))((pq)(rr))((qr)(pp))(pqr)(pqr)(pqr)(pqr)(主析取范式)m2m3m5m7,用等值演算法求公式的主范式的步驟：(1)先求析取范式（合取范式）(2)將不是極小項（極大項）的簡單合取式（簡單析取式）化成與之等值的若干個極小項的析取（極大項的合?。?，需要利用同一律（零律）、排中律（矛盾律）、分配律、冪等律等.(3)極小項（極大項）用名稱mi（Mi）表示，并按角標(biāo)從小到大順序排序.,例求(pq)(pr)的主合取范式。解法1：Pqrppqpr(pq)(pr)00010100011010010111101111111000100101011111001001110111,解法2：(pq)(pr)(pq)(pr)(合取范式)((pq)(rr))((pr)(qq))((pqr)(pqr))((pqr)(pqr))(pqr)(pqr)(pqr)(pqr)(主合取范式)M0M1M4M6,