命題邏輯及命題演算.ppt

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

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

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

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

4、取式：兩個(gè)命題P和Q的析取是一個(gè)復(fù)合命題，記作PQ。當(dāng)且僅當(dāng)P、Q同時(shí)為F時(shí)，PQ為F，其他情況下，PQ的真值都是T。析取聯(lián)結(jié)詞“”表示自然語言中的“或”（or）。,見真為真，全假為假。,pq讀作“p或者q”、“p或q”。,（4）蘊(yùn)涵式：給定兩個(gè)命題P和Q，其條件命題是一個(gè)復(fù)合命題，記作PQ。當(dāng)且僅當(dāng)P的真值為T，Q的真值為F時(shí)，PQ的真值為F，其他情況下，PQ的真值都是T。條件聯(lián)結(jié)詞“”表示自然語言中的“如果，那么”。,pq中的p稱為條件前件，q稱為條件后件,前真后假為假，其他為真。,（5）等價(jià)式：給定兩個(gè)命題P和Q，其復(fù)合命題PQ稱作雙條件命題。當(dāng)P和Q的真值相同時(shí)，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ù)合命題的符號(hào)化,復(fù)合命題的符號(hào)化的基本步驟1)找出各個(gè)原子命題，并逐個(gè)符號(hào)化；2)找出各個(gè)連接詞，符號(hào)成相應(yīng)聯(lián)結(jié)詞；3)用聯(lián)結(jié)詞將原子命題逐個(gè)聯(lián)結(jié)起來；,1-1.2復(fù)合命題的符號(hào)化,例將下列命題符號(hào)化(1)北京不是村莊P:表示“北京是村莊”P:北京不是村莊(2)小王是游泳冠軍和百米賽跑冠軍P：小王是游泳冠軍;Q：小王百米賽跑冠軍PQ:小王是游泳冠軍和百米賽跑冠軍,1-1.2復(fù)合命題的符號(hào)化,例將下列命題符號(hào)化(3)小明或者小華能解夠出這道題P：小

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

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

8、重言式或永真式；,（3）若不是矛盾式，則稱為可滿足式。,第二章命題邏輯等值演算,一、等值式,引例：,與,定義：設(shè)是兩個(gè)命題公式，若構(gòu)成的等價(jià)式為重言式，則稱是等值的，記作。,練習(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,蘊(yùn)涵等值式:ABAB等價(jià)等值式:AB(AB)(BA)假言易位:ABBA等價(jià)

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

10、q)（蘊(yùn)涵等值式）q(pq)（德摩根律）p(qq)（交換律，結(jié)合律）p0（矛盾律）0（零律）由最后一步可知，該式為矛盾式.,(2)(pq)(qp)解(pq)(qp)(pq)(qp)（蘊(yùn)涵等值式）(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)盡量使演算短些,定義文字：命題變項(xiàng)及其否定統(tǒng)稱為文字。如：p

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

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

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

14、步驟：（1）消去對(duì),,,來說冗余的聯(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個(gè)命題變項(xiàng)的簡(jiǎn)單合取式(簡(jiǎn)單析取式)中，若每個(gè)命題變項(xiàng)均以文字的形式在其中出現(xiàn)且僅出現(xiàn)一次，而且第i（1in）個(gè)文字出現(xiàn)在左起第i位上，稱這樣的簡(jiǎn)單合取式（簡(jiǎn)單析取式）為極小項(xiàng)（極大項(xiàng)）.,由p,q兩個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng),由p,q,r三個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng),極小項(xiàng)與極大項(xiàng)關(guān)系設(shè)mi和Mi是命題變項(xiàng)p1，p2，pn形成的極小項(xiàng)和極大項(xiàng)，則miMi，Mimi定義設(shè)由n個(gè)命題變項(xiàng)構(gòu)成的析（合）取范式中所有的簡(jiǎn)單合（析）取式都是極?。ù螅╉?xiàng)，則稱該析（合）取范式為主

16、析（合）取范式。,由不同最小項(xiàng)所組成的析取式稱為主析取范式由不同最大項(xiàng)所組成的合取式稱為主合取范式,求(pq)(pr)的主析取范式。(pq)(pr)(qp)(pr)(qr)(析取范式)((pr)(qq))((pq)(rr))((qr)(pp))(pqr)(pqr)(pqr)(pqr)(主析取范式)m2m3m5m7,用等值演算法求公式的主范式的步驟：(1)先求析取范式（合取范式）(2)將不是極小項(xiàng)（極大項(xiàng)）的簡(jiǎn)單合取式（簡(jiǎn)單析取式）化成與之等值的若干個(gè)極小項(xiàng)的析取（極大項(xiàng)的合?。枰猛宦桑懵桑⑴胖新桑苈桑?、分配律、冪等律等.(3)極小項(xiàng)（極大項(xiàng)）用名稱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,