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

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

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

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

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

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

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

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

8、重言式或永真式；,（3）若不是矛盾式，則稱為可滿足式。,第二章命題邏輯等值演算,一、等值式,引例：,與,定義：設是兩個命題公式，若構成的等價式為重言式，則稱是等值的，記作。,練習：1）與,2）與,等值演算公式：,雙重否定律:AA等冪律：AAA,AAA交換律:ABBA,ABBA結合律:(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)結合律p(qr)蘊涵等值式p(qr)蘊涵等值式注:ABAB,練習：,例證明:p(qr)(pq)r用等值演算不能直接證明兩個公式不等值,證明兩個公式不等值的基本思想是找到一個賦值使一個成真,另一個成假.方法一真值表法（自己證）方法二觀察賦值法.容易看出000,010等是左邊的成真賦值，是右邊的成假賦值.方法三用等值演算先化簡兩個公式，再觀察,例用等值演算法判斷下列公式的類型(1)q(pq)解q(pq)q(p

10、q)（蘊涵等值式）q(pq)（德摩根律）p(qq)（交換律，結合律）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是它的成假賦值.,總結：A為矛盾式當且僅當A0A為重言式當且僅當A1說明：演算步驟不惟一,應盡量使演算短些,定義文字：命題變項及其否定統(tǒng)稱為文字。如：p

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

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

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

14、步驟：（1）消去對,,,來說冗余的聯(lián)結詞，即，。利用下列等值式：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三個命題變項形成的極小項與極大項,極小項與極大項關系設mi和Mi是命題變項p1，p2，pn形成的極小項和極大項，則miMi，Mimi定義設由n個命題變項構成的析（合）取范式中所有的簡單合（析）取式都是極?。ù螅╉?，則稱該析（合）取范式為主

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