命題邏輯及命題演算.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)聘，這個商人為了試試哪個更聰明些，就把兩個人帶進(jìn)一間漆黑的屋子里，他打開燈后說：“這張桌子上有五頂帽子，兩頂是紅色的，三頂是黑色的，現(xiàn)在，我把燈關(guān)掉，而且把帽子擺的位置弄

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

5、真值都是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(pq)（蘊

10、涵等值式）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,q簡單析取式：僅

11、有有限個文字組成的析取式。如：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),可以寫成(pp)(

12、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)成）,求范式的具體步驟：（1）消去對

14、,來說冗余的聯(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)(pq)(pr)(pr)(pq)

15、(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,