給力離散小組傾血編制

1、第一章 命題邏輯1-1 命題及其表示法定義1：命題是一個具有確定真值的陳述語句。l 注：真值表示真假的性質(zhì)，其可能的取值只有“真”和“假”，通常用T或1表示真，F(xiàn)或0表示假。l 例：5是一個整數(shù)。 3是偶數(shù)。 x+y=4。 你吃過飯了嗎? 我正在說謊。 l 命題有兩種形式：原子命題和復(fù)合命題。定義2：原子命題是不能再分解為更簡單命題的命題。l 例：蘇格拉底是哲學(xué)家。 如果天氣好，那么我去散步。l 注：1 原子命題的界定不宜絕對化； 2 原子命題常用大寫字母A，B，P，Q，或帶下標(biāo)的大寫字母如P1來表示。定義3：由原子命題、聯(lián)結(jié)詞或標(biāo)點(diǎn)符號的復(fù)合構(gòu)成的命題稱復(fù)合命題。l 例： 昨天下雨，今天也在

2、下雨。定義4：表示命題的符號稱為命題標(biāo)識符。l 例：P:北京是中國的首都。定義5：一個命題標(biāo)識符如果表示確定的命題，稱為命題常元；如果命題標(biāo)識符可以表示某 類命題中的任何一個，稱為命題變元。l 思考：命題變元是命題嗎？定義6：將一個命題變元P用一特定命題或真值去代替，它就有確定的真值，這稱對P的指派，或解釋，記為S(P)或I(P)。l 顯然，指派或解釋是針對命題變元進(jìn)行的。命題的聯(lián)結(jié)詞定義1：設(shè)P為一命題，P的否定是一個新的命題，記為P。若P為T， P為F；若P為T，P為F。l 例：P：上海不是一個大城市。 P：？定義2：兩個命題P和Q的合取是一個復(fù)合命題，記作PQ。當(dāng)且僅當(dāng)P、Q同時為T時，

3、PQ為T，其他情況下PQ均為F。l 例：P：地球是球形的。 Q: 牛頓是物理學(xué)家。 PQ: 地球是球形的并且牛頓是物理學(xué)家。又如：P：拿破侖是科西嘉人。 Q: 拿破侖不是科西嘉人。 ( P) PQ:拿破侖是科西嘉人并且拿破侖不是科西嘉人。注：l 1.是漢語中“與”、“和”、“并”的翻譯，但不能絕對化。l 2.合取在一起的兩個命題不一定有實質(zhì)的聯(lián)系，也不一定是一致的，甚至可以將互為否定的命題合取在一起(該注釋對其他邏輯聯(lián)結(jié)詞也適用)。定義3：兩個命題P和Q的析取是一個復(fù)合命題，記作PQ。當(dāng)且僅當(dāng)P、Q同時為F時，PQ的真值為F；否則PQ的真值為T。l 例： P：機(jī)器有故障。 Q：開關(guān)有故障。 P

4、Q：機(jī)器有故障或開關(guān)有故障。l 注：是漢語中“或” 的翻譯，但不能絕對化。特別應(yīng)注意區(qū)分“可兼或”和“排斥或”。l 例：1.今晚我在家看電視或去同學(xué)家玩。 2.他可能是100米或400米賽跑的冠軍。 3.他昨晚做了二十或三十道習(xí)題。 其中，例1中的“或”為“排斥或”，例2中的“或”為“可兼或”，而例3中的“或”，不是聯(lián)結(jié)詞，只表示習(xí)題的近似數(shù)，因此3不是一個復(fù)合命題，而是一個原子命題。（排斥或與可兼或的命題符號表達(dá)形式見后文）定義4：給定兩個命題P和Q，其條件是一個復(fù)合命題，記作PQ，讀作“如果P，那么Q” 或“P條件Q”。當(dāng)且僅當(dāng)P的真值為T，Q的真值為F時，PQ的真值為F;否則PQ的真值為

5、T。稱P為前項，Q為后項。l 例：P： 月亮下山。 Q： 3+3=6。 PQ： 如果月亮下山,則3+3=6。注：1.雖然上例的P、Q之間并無實際聯(lián)系，但只要P、Q可分別確定真值，即可用“”聯(lián)結(jié)。 2.QP稱為PQ的逆命題； PQ稱為PQ的否命題； QP稱為PQ的逆否命題。 3.前項P為F時，無論后項Q取何真值,PQ的真值均為T，這是所謂的“善意推定”。定義5：給定兩個命題P和Q，復(fù)合命題PQ稱作雙條件命題，讀作“P當(dāng)且僅當(dāng)Q”，當(dāng)P和Q的真值相同時，PQ的真值為T，否則PQ的真值為F。l 注：雙條件的其他表示法。l 例： P： 1+1=3。 Q： 雪是白的。 PQ： 1+1=3當(dāng)且僅當(dāng)雪是白的

6、。1-3 命題公式與翻譯定義1：命題常元、命題變元統(tǒng)稱為原子命題公式，簡稱原子公式。定義2： 合式公式是由下列規(guī)則形成的字符串： 1)真值T和F是合式公式。 2)原子命題公式是一個合式公式。 3)如果A是合式公式，那么A是合式公式。 4)如果A和B是合式公式，那么(AB)、(AB)、 (AB)和(AB)都是合式公式。 5)經(jīng)過有限次地應(yīng)用2)、3)和4)所得到的包含命題變元，聯(lián)結(jié)詞和括號的符號串是合式公式。l 例：指出(P(PQ)中的哪些部分是命題公式，如果是，則具體說明它是如何生成的 解： P 由規(guī)則2) Q 由規(guī)則2) (PQ) 由規(guī)則4)和 (P(PQ) 由規(guī)則4)和l 當(dāng)合式公式中的原

7、子命題公式是命題變元時，合式公式是沒有真假值的，僅當(dāng)其中的命題變元用確定的命題代入時，才能得到一個命題。這時，這個命題的真值，依賴于代換命題變元的那個命題的真值。運(yùn)算次序優(yōu)先級：， 相同的運(yùn)算符按從左至右次序計算，否則要加上括號，最外層圓括號可省去 翻譯l 把一個用文字?jǐn)⑹龅拿}相應(yīng)地寫成由命題標(biāo)識符、聯(lián)結(jié)詞和圓括號表示的合式公式，或反之，均稱為翻譯。自然語句符號化的過程主要包括兩個步驟:l (1)分析出各簡單命題, 將它們符號化;l (2)根據(jù)自然語句中的邏輯關(guān)系,使用恰當(dāng)?shù)拿}聯(lián)結(jié)詞, 把簡單命題逐個聯(lián)結(jié)起來, 構(gòu)成復(fù)合命題的符號化表示。l 如何將語句形式化, 以及如何理解形式化了的語句。

8、語句形式化要注意:1.要善于確定簡單命題, 不要把一個概念硬拆成幾個概念。例 “我和他是同學(xué)”是一個簡單命題。2.要善于識別自然語言中的聯(lián)結(jié)詞(有時它們被省略)。例 狗急跳墻。解：應(yīng)理解為: P: 狗急了, Q: 狗才跳墻上述語句形式化成P®Q。3.否定詞的位置要放準(zhǔn)確。例 如果你和他不都是傻子, 那么你們倆都不會去自討沒趣。解：設(shè) A: 你是傻子, B: 他是傻子, C: 你會去自討沒趣, D: 他會去自討沒趣。上述語句形式化為: (AB) ® (CD)。例：符號化下列命題。1.張明正在睡覺或游泳。解：令P:張明在睡覺，Q:張明在游泳，則此命題符號化為：(PQ)(QP)。

9、2.他可能是100米或400米賽跑的冠軍。解：令P: 他可能是100米賽跑的冠軍，Q: 他可能是100米賽跑的冠軍 ，則此命題符號化為：PQ。3.除非你努力，否則你將失敗。解：這個命題的實際含義是，你沒有失敗必定是你努力，令P:你失敗，Q:你努力，則此命題符號化為PQ。4.除非天氣好，我才騎自行車上班。解：這個命題的實際含義是，我騎自行車上班必定是天氣好，令P:我騎自行車上班，Q:天氣好，則此命題符號化為PQ。5.只有睡覺才能恢復(fù)疲勞。解：這個命題的實際含義是，能恢復(fù)疲勞必定是睡覺了，令P:恢復(fù)疲勞，Q:睡覺，則此命題符號化為PQ。6.只要我還有口氣，我就要戰(zhàn)斗。解：令P:我還有口氣，Q:我要

10、戰(zhàn)斗，則此命題符號化為PQ。1-4真值表與等價公式定義1：在合式公式中，根據(jù)對每個命題變元指派真值的各種可能組合，求解合式公式的對應(yīng)真值，匯列成表，稱為真值表。l 定義2：對于命題公式A中每個命題變元Pi，任給一個指派S(Pi)或解釋I(Pi)，得到一種真值的組合S(P1) S(P2)S(Pn)或I(P1) I(P2)I(Pn) 稱為A的一個真值指派，或稱為A的一種解釋，記為S(A)或I(A)。若S(A)或I(A)為T，稱S(A)或I(A)為A的成真指派或說A的解釋為真。類似地定義A的成假指派。 例：構(gòu)造P(PQ)的真值表 解：PQP(PQ)00 1 1 101 1 1 110 0 1 011

11、 0 1 1步驟 一般說來，n個命題變元組成的命題公式共有2n種真值指派。定義3：一個命題公式如果對于其分量指派真值的各種可能組合，其真值恒為真(假)，稱該命題公式是永真(假)式，記為T(F)。若至少有一個組合,其真值為真,則稱該命題公式是可滿足式。 例：PP PP PQ 例：前面的二個真值表的例子都是永真式.注：重言式一定是可滿足式。l 永真式也稱重言式；永假式也稱矛盾式。 關(guān)于重言式，有如下性質(zhì)：定理1：任何兩個重言式的合取或析取，仍然是重言式。 證明：設(shè)A、B為兩個重言式，則AB和AB的真值分別等于TT和TT。定理2：對一個重言式的同一分量都用任何一個命題公式置換，所得命題公式仍為一個重

12、言式。（即代入規(guī)則） 證明：由于重言式的真值與分量的真值指派無關(guān)，故對同一分量以任何一個命題公式置換后，重言式的真值不變。定理3：設(shè)A、B是兩個命題公式，AÛB當(dāng)且僅當(dāng)AB是一個重言式。（前面已證） 證明：若AÛB，則對于A、B所包含的分量的任意指派，A、B均取相同的真值，即AB是一個重言式；若AB是一個重言式，即對于分量的任意指派，A、B均取相同的真值，即AÛB定義4：給定兩個命題公式A和B，如果A和B在其任意指派（或解釋）下，其真值都是相同的，即A(P1，P2.Pn)，B(P1，P2.Pn)若對于P1，Pn任一組真值指派，A，B真值相同，則稱A和B是等價的，或

13、邏輯相等，記為AÛB。讀作A等價B，稱AÛB為等價式。與Û的區(qū)別與聯(lián)系l 區(qū)別: 是邏輯聯(lián)結(jié)詞,它出現(xiàn)在命題公式中;Û不是邏輯聯(lián)結(jié)詞,它表示兩個命題公式之間的一種充分必要關(guān)系,它不屬于兩個公式中的任何一個中的符號。l 聯(lián)系: 定理: AÛB當(dāng)且僅當(dāng)AB是永真式. 證明：（略） 所以又稱AÛB是永真雙條件式.等價式的性質(zhì):l 自反性:對任意公式A,有AÛAl 對稱性:對任意公式A,B,若AÛB,則BÛAl 傳遞性:對任意公式A,B,C,若AÛB, BÛC,則AÛC基本等價式命題

14、定律 雙否律: P Û P 冪等律： PPÛP, PPÛP 結(jié)合律： (PQ)RÛP(QR) (PQ)RÛP(Q R) 交換律： PQÛ QP， PQÛQP 分配律： P(QR)Û(PQ)(PR), P(QR)Û(PQ)(PR) 吸收律： P(PQ)ÛP, P(PQ)ÛP 德摩根律： (PQ)ÛPQ (PQ)ÛPQ 同一律： PFÛP， PTÛP 零律： PTÛT， PFÛF 互補(bǔ)律： P PÛT(排中律)， P P

15、ÛF(矛盾律) 條件式轉(zhuǎn)化律： PQ Û PQ, PQ Û QP 雙條件式轉(zhuǎn)化律： PQÛ(PQ)(QP)Û(PQ)(QP),PQ Û (PQ) 輸出律： (PQ)RÛP(QR) 歸謬律： (PQ)(PQ) Û P定義5：如果X是命題公式A的一部分，且X也是命題公式，則稱X是A的子公式。定理1：設(shè)A1是命題公式A的子公式，若A1ÛB1，則若將A中的A1用B1來替換，得到公式B ，則B與A等價，即AÛB.(替換規(guī)則)。 證明： 因為對變元的任一組指派， A1與B1真值相同，故以B1取代A1后，公式

16、B與公式A相對于變元的任一指派的真值也必相同，所以AÛB。定義：稱滿足定理1的替換為等價替換。定理2： 在一個永真式A中,任何一個原子命題變元R出現(xiàn)的每一處,用另一個公式代入,所得公式B仍是永真式.(代入規(guī)則)。證明:因為永真式對任意解釋,其值都是真,與所給的某個命題變元指派的真值是真還是假無關(guān),因此,用一個命題公式代入到原子命題變元R出現(xiàn)的每一處后,所得命題公式的真值仍為真.代入與替換的區(qū)別:l 代入是對原子命題變元而言的，而替換通常是可對命題公式實行之。l 代入必須是處處代入，替換則可部分替換，也可全部替換。l 代入是對一個永真式進(jìn)行的，替換則是對一般公式進(jìn)行的。1-5 蘊(yùn)涵式定

17、義1：當(dāng)且僅當(dāng)PQ是一個重言式時，稱“P重言蘊(yùn)涵Q”，在不會引起歧義的情況下，簡稱為“蘊(yùn)涵”，記作PÞQ。l 注：重言蘊(yùn)涵“Þ”與條件（也叫實質(zhì)蘊(yùn)涵）“”的區(qū)別類似于Û 與的區(qū)別定理4：設(shè)P、Q為任意兩個命題公式，PÛQ的充分必要條件是PÞQ且QÞP。證明：若PÛQ，則PQ為重言式，即PQ和QP是重言式；若有PÞQ且QÞP，則PQ和QP是重言式，即PQ為重言式l 蘊(yùn)涵的性質(zhì)：設(shè)A、B、C和D為命題公式，則 1.若A是重言式，且有AÞB，則B是重言式 2.若有AÞB、BÞC，則

18、有AÞC，即蘊(yùn)涵關(guān)系是傳遞的 3.若有AÞB、AÞC，則有AÞ(BC) 4.如有AÞC、BÞC，則有ABÞC1-6其他聯(lián)結(jié)詞定義1：設(shè)P和Q是兩個命題公式， P和Q的合取非是一個新命題公式，記作PQ。當(dāng)且僅當(dāng)P和Q的真值都為T時，PQ為F ，其他情況下PQ的真值都是T ?！昂先》恰蓖ǔＲ卜Q“與非”。l 根據(jù)此定義，可知 PQ Û (PQ)l 的性質(zhì)： PQ Û QP PP Û P (PQ)(PQ) Û PQ (PP)(QQ) Û PQ定義2：設(shè)P和Q是兩個命題公式， P和Q的

19、析取非是一個新命題公式，記作PQ。當(dāng)且僅當(dāng)P和Q的真值都為F時，PQ為T ，其他情況下PQ的真值都是F 。“析取非”通常也稱“或非”。l 根據(jù)此定義，可知 PQ Û (PQ)l 的性質(zhì)： PQ Û QP PP Û P (PQ)(PQ) Û PQ (PP)(QQ) Û PQ定義3：設(shè)P和Q是兩個命題公式， P和Q的條件非是一個新命題公式，記作PQ。當(dāng)且僅當(dāng)P為T而Q為F時，PQ為T，其他情況下PQ的真值都是F。也用符號'表示。l 根據(jù)此定義，可知 PQ Û (PQ)定義4：設(shè)P和Q是兩個命題公式， P和Q的雙條件非是一個新命題公

20、式，記作PDQ。當(dāng)且僅當(dāng)P和Q的真值不同時，PDQ為T，其他情況下PDQ的真值都是F?！半p條件非”也常稱為“異或”。也常用 Å , D'表示l 根據(jù)此定義，可知 PDQ Û (PDQ)聯(lián)結(jié)詞定義3：可以表示所有可能的真值函數(shù)(即聯(lián)結(jié)詞)的聯(lián)結(jié)詞集合G，如果G滿足下列兩個條件：1. 由G中聯(lián)結(jié)詞構(gòu)成的公式能等價表示任意命題公式2. G中的任一聯(lián)結(jié)詞不能用其余下聯(lián)結(jié)詞等價表示則稱G為聯(lián)結(jié)詞功能完全組。， ， ， ，是聯(lián)結(jié)詞功能完全組。和也是聯(lián)結(jié)詞功能完全組。1-7對偶和范式對偶定義1：在只包含聯(lián)結(jié)詞， ，的命題公式A中，將聯(lián)結(jié)詞和互換，特殊變元F和T亦互換，所得公式A*

21、稱為A的對偶式。l 例：求(PQ)R的對偶式。 (PQ)R定理1：設(shè)A*是A的對偶式，P1，P2，P3，Pn是出現(xiàn)于A和A*中的原子命題變元，則有 1)A(P1，P2，P3 ， Pn) Û A*(P1，P2，P3 ， Pn) 2) A*(P1，P2，P3 ， Pn) Û A(P1，P2，P3 ， Pn)l 例：A(P1，P2，P3)=P1(P2P3)，驗證定理1。l 解：1) A(P1，P2，P3) Û(P1(P2P3) Û(P1)(P2P3) A*(P1，P2，P3) Û( P1)(P2P3)2) A(P1，P2，P3) ÛP1(P

22、2P3) A*(P1，P2，P3) Û (P1(P2P3) Û P1(P2P3)定理2：如果AÛB，則A* Û B*。 證明：設(shè)P1,P2,Pn是出現(xiàn)在命題公式A、B中的原子變元，因為AÛB，即：A(P1,P2,Pn)B(P1,P2,Pn)是一個重言式。故有： A(P1,P2,Pn)B(P1,P2,Pn)是一個重言式。即A(P1,P2,Pn)ÛB(P1,P2,Pn) 再由定理1， A* Û B* ，即A* Û B*1-7對偶和范式范式定義 命題變元和命題變元的否定,稱為文字.如果一個文字恰為另一個文字的否定,則稱它

23、們?yōu)橐粚ο喾次淖?例:P和P都是文字,并且是一對相反文字, P不是文字.P和Q都是文字,但不是一對相反文字定義 設(shè)L1,L2,Lk都是文字,稱L1L2 Lk為簡單析取式,并稱Li為析取項，即有限個文字的析取組成的公式稱為簡單析取式;稱L1L2 Lk為簡單合取式,并稱Li為合取項，即有限個文字的合取組成的公式稱為簡單合取式.其中1ik.例：P、PQ、PQP等都是簡單合取式. P、PQ、PQP、PQ等都是簡單析取式.單個的文字既是簡單合取式; 又是簡單析取式。定理 (1)一簡單合取式為永假式的充分必要條件是, 它至少含有一對相反文字，即至少同時包含某個命題變元P及其否定P。(2) 一簡單析取式為永

24、真式的充分必要條件是，它至少含有一對相反文字，即至少同時包含某個命題變元P及其否定P。例： PQP為永假式定義 ：一個命題公式稱為合取范式，當(dāng)且僅當(dāng)它具有形式：A1A2An，其中A1,A2,An都是簡單析取式，n1，即：有限個簡單析取式的合取組成的公式稱為合取范式。定義 ：一個命題公式稱為析取范式，當(dāng)且僅當(dāng)它具有形式：B1B2Bm，其中B1,B2,Bm都是簡單合取式，m1，即：有限個簡單合取式的析取組成的公式稱為析取范式。析取范式和合取范式僅含聯(lián)結(jié)詞、和。例 ：P(QR)(P R) 是析取范式嗎？P、QR、PQ、(PQ)(QR) 都是析取范式。P、QR、PQ、(PQ)(QR) 都是合取范式。單

25、個的文字、簡單合取式和簡單析取式既是析取范式; 又是合取范式。任何析取范式的對偶式為合取范式, 任何合取范式的對偶式為析取范式。定理 (范式存在定理) 對于任意公式, 都存在等價于它的析取范式和合取范式。l 求任意命題公式的合取(析取)范式的步驟 1)將公式中的聯(lián)結(jié)詞化成， ，如消除公式中的運(yùn)算符“®”和“«”?？捎玫葍r式將 P®Q替換為PQP«Q替換為(P®Q)(Q®P)即 (PQ)(PQ) (析取范式)或 (PQ)(PQ) (合取范式) 2)利用雙否律和德摩根律將否定符號直接移到各個命題變元之前，如將P替換成P (PQ)替換為 P

26、Q (PQ)替換為 PQ 3)利用分配律、結(jié)合律將公式化為合取范式(析取)范式，如P(QR)= (PQ)(PR) (析取范式) P(QR)= (PQ)(PR) (合取范式) 例 求公式(PQ)®R)®P的合取范式和析取范式。解 (1)求合取范式 (PQ)® R) ® P Û(Ø (PQ)R)® P (消去第一個) Û Ø (Ø(PQ)R)P (消去第二個) Û Ø(ØP ØQ)R)P (Ø內(nèi)移) Û(Ø ØP 

27、16; ØQ) ØR)P (Ø內(nèi)移) Û(PQ) ØR)P (Ø消去) Û(PQP)(ØRP) (對分配律) Û(PQ)(ØRP) (交換律和等冪律) 可見,(PQP)(ØRP),(PQ)(ØRP)都是原公式的合取范式,這說明與某個命題公式等值的合取范式是不唯一的.(2)求析取范式用對的分配律就可得到析取范式,即 (PQ) ® R) ® P Û Û(PQ)ØR)P Û(PØR)(QØR)P (對分

28、配律) ÛP(Q ØR) (交換律和吸收律) 可見, (PØR)(QØR)P, P(Q ØR)都為原公式的析取范式.即：與命題公式等值的析取范式也是不唯一的.范式的應(yīng)用定理 (1)公式A為重言式的充分必要條件是, A的合取范式中每一簡單析取式至少包含一對相反文字。 (2)公式A為矛盾式的充分必要條件是, A的析取范式中每一簡單合取式至少包含一對相反文字。例 (PR)(QR)P是否為重言式或矛盾式。解 (PR)(QR)PÛ (PR)QRP在析取范式中共有4個簡單合取式, 但任何一個都沒有一對相反文字出現(xiàn)。 原公式不是矛盾式。應(yīng)用對的分配

29、律有:Û (PQRP)(RQRP)第一個簡單析取式同時包含有P和P，第二個簡單析取式同時包含有R和R。原公式是重言式。定義 ：在含有n個命題變元的簡單合取式中，若每個命題變元與它的否定不同時存在，且兩者之一必須出現(xiàn)一次且僅出現(xiàn)一次，則稱此簡單合取式為小項,或布爾積。l 如：兩個命題變元P和Q構(gòu)成的小項有PQ，PQ，PQ，PQ 。注：n個命題變元的小項有2n個。3個命題變元，8個小項對應(yīng)情況如下： PQR 000 0, 記作m0； PQR 001 1, 記作m1； PQR 010 2, 記作m2； PQR 011 3, 記作m3； PQR 100 4, 記作m4； PQR 101 5,

30、 記作m5； PQR 110 6, 記作m6； PQR 111 7, 記作m7. 一般情況下,n個命題變元共產(chǎn)生2n個小項,分別記為m0,m1,.m2n-1.小項有如下性質(zhì)：1. 沒有兩個小項是等價的，即各小項的真值表都是不同的。2. 任意兩個不同的小項的合取式是永假的3. 所有小項的析取為永真的4. 每個小項只在一組真值指派下為T，且其真值1位于主對角線上。這表明每個小項與其成真指派之間建立了一一對應(yīng)關(guān)系。定義 ：在給定公式的析取范式中，若其簡單合取式都是小項，則稱該范式為主析取范式。定理：一個公式的主析取范式是唯一的。定理：在真值表中，一個命題公式A的真值為T的指派所對應(yīng)的小項的析取，即為

31、該命題公式的主析取范式。 證明：對A為真的某一解釋，除其對應(yīng)為真的小項外，而其余小項均為假，故所有這些小項的析取范式B為真；其次，對A為假的某一解釋，其對應(yīng)的小項不包含在B中，即這些小項均為假，故所有這些小項的析取范式B為假。因此A與B等價。并且B又是小項的析取式，故B是一個主析取范式定理 ：任意含n個命題變元的非永假命題公式A都存在與其等價的主析取范式。等價變換法求主析取范式的一般步驟 1)把給定公式化為析取范式 2)除去析取范式中所有永假的析取項 3)合并重復(fù)項 4)補(bǔ)入合取項中沒有出現(xiàn)的命題變元，例如添加(PP)等，再用分配律展開例：求下式給出的命題公式的主析取范式.(PQ) ®

32、; R) ® P.由前例可知, 原公式的析取范式為, P (Q ØR)用P(ØQQ)(ØRR)取代P.用(ØPP)(Q ØR)取代(Q ØR).然后展開得小項.(PQ) ® R) ® P Û P(Q ØR) (析取范式) Û P(ØQQ) (ØRR)(ØPP)(Q ØR) Û (PØQØR)(PØQR) (P Q ØR)(P Q R) (ØPQØR)(P Q 

33、6;R) Û m4 m5 m6m7m2m6 Û m2m4m5m6m7定義 ：在n個命題變元的簡單析取式中，若每個命題變元與它的否定不能同時存在，而兩者必須出現(xiàn)一次且僅出現(xiàn)一次，則稱此簡單析取式為大項，或布爾和。如：兩個命題變元P和Q構(gòu)成的大項有PQ，PQ，PQ，PQ 。注：n個命題變元的大項有2n個l 注：可以為大項指定一種編碼，如果將命題變元按字典序排列，并且把命題變元與0對應(yīng)，命題變元的否定與1對應(yīng)，則可對2n個大項依二進(jìn)制數(shù)編碼。例如：M00對應(yīng)PQ，M101對應(yīng)PQRl 注意:編碼正好與小項相反 大項具有如下性質(zhì)：（類似小項）1. 沒有兩個大項是等價的2. 任意兩個

34、不同大項的析取為T3. 全體大項的合取必為F4. 每個大項只有一個解釋為假，且其真值0位于主對角線上。這表明每個大項與其成假指派之間建立了一一對應(yīng)關(guān)系。定義 ：在給定公式的合取范式中，若所有簡單析取式都是大項，則稱該合取范式為主合取范式。定理：一個公式的主合取范式是唯一的。l 定理：在真值表中，一個命題公式的真值為的指派所對應(yīng)的大項的合取，即為該命題公式的主合取范式。l 定理 ：任意含n個命題變元的非永真命題公式A都存在與其等價的主合取范式。主合取范式亦可由等價變換求得，基本步驟如下 1)化為合取范式 2)除去合取范式中所有永真合取項 3)合并重復(fù)項 4)補(bǔ)入合取項中沒有出現(xiàn)的命題變元，例如添

35、加(PP)等，再用分配律展開例 求PQR的主合取范式. 解 (PQ) R Û(PR)(QR) (合取范式) Û(P(Q ØQ)R)(P ØP)QR) Û(PQR)(P ØQR) (PQR) (Ø PQR) Û(PQR)(P Ø QR)(ØPQR) Û M000M010M100 Û M0M2M4由于小項與大項之間有關(guān)系：mi ÛMi Mi Ûmi 因此，主析取范式和主合取范式有著“互補(bǔ)”的關(guān)系 ，即由給定公式的主析取范式可以求出其主合取范式。例：A中含3個命

36、題變元,主析取范式為 A Û m0m1m5m7則主合取范式為 A Û M2M3M4M6主范式的用途1.判斷兩命題公式是否等價.2.判斷命題公式的類型3.求命題公式的成真和成假賦值.1.判斷兩命題公式是否等價.由于任何命題公式的主范式都是唯一的,因而若A Û B,說明A與B有相同的主析?。ê先。┓妒?反之,若A,B有相同的主析取（合?。┓妒?必有A ÛB.2.判斷命題公式的類型設(shè)A是含n個命題變項的命題公式, A為重言式,當(dāng)且僅當(dāng)A的主析取范式中含全部2n個小項.A為矛盾式,當(dāng)且僅當(dāng)A的主合取范式中含全部2n個大項.若A不與T或者F等價，且又不含2n個小項

37、或者大項,則A是可滿足式.例 判斷下列命題公式的類型. (PQ)P)Q；Û Ø(ØPQ)P)Q （消去）Û Ø(ØPQ) ØPQ （ Ø內(nèi)移）Û (PØQ) ØPQ （得到析取范式） Û(PØQ)(ØP(ØQQ)(ØPP)Q)（加項）Û (ØPØQ)(Ø PQ)(P Ø Q)(PQ)Û m0m1m2m3由于主析取范式中含全部2n=4個小項,故原命題公式為永真式.3.求命題公式的

38、成真和成假賦值.1-8推理理論例 張三說李四在說謊, 李四說王五在說謊, 王五說張三、李四都在說謊。問誰說真話, 誰說假話？解 設(shè)A:張三說真話; B:李四說真話; C:王五說真話依題意有 AØÛB, BØÛC, CØÛAØB。(A « ØB)(B « ØC)(C « ØAØB)Û (AØ®B)(ØB®A)(BØ®C)(ØC® B) (C®(ØA&

39、#216;B)(ØAØB)®C)Û (ØABØC)(AB)C) (ØAØBØC)(AØC)(BØC)Û ØABØC即: 李四說真話, 張三和王五說假話。本章構(gòu)造推論參照證明題集錦第二章 謂詞邏輯（部分*內(nèi)容為了解）在謂詞邏輯中，為揭示命題內(nèi)部結(jié)構(gòu)及其不同命題的內(nèi)部結(jié)構(gòu)關(guān)系，就按照這兩部分對命題進(jìn)行分析，并且把主語稱為個體或客體，把謂語稱為謂詞。.個體、謂詞和命題的謂詞形式l 定義 在原子命題中，所描述的對象稱為個體；用以描述個體的性質(zhì)或個體間關(guān)系的部分，稱

40、為謂詞。 個體，是指可以獨(dú)立存在的事物，它可以是具體的，也可以是抽象的，如張明，計算機(jī)，精神等。表示特定的個體，稱為個體常元，以a，b，c或帶下標(biāo)的ai，bi，ci表示；表示不確定的個體，稱為個體變元，以x，y，z或xi，yi，zi表示。 謂詞，當(dāng)與一個個體相聯(lián)系時，它刻劃了個體性質(zhì)；當(dāng)與兩個或兩個以上個體相聯(lián)系時，它刻劃了個體之間的關(guān)系。表示特定謂詞，稱為謂詞常元，表示不確定的謂詞，稱為謂詞變元，都用大寫英文字母，如P，Q，R，或其帶上、下標(biāo)來表示。在教材中，不對謂詞變元作更多地討論。 對于給定的命題，當(dāng)用表示其個體的小寫字母和表示其謂詞的大寫字母來表示時，規(guī)定把小寫字母寫在大寫字母右側(cè)的圓

41、括號( )內(nèi)。 例如，在命題“張明是位大學(xué)生”中，“張明”是個體，“是位大學(xué)生”是謂詞，它刻劃了“張明”的性質(zhì)。設(shè)S：是位大學(xué)生，c：張明，則“張明是位大學(xué)生”可表示為S(c)，或者寫成S(c)：張明是位大學(xué)生。定義 一個原子命題用一個謂詞(如P)和n個有次序的個體常元(如a1，a2，an)表示成P(a1，a2，an)，稱它為該原子命題的謂詞形式或命題的謂詞形式。應(yīng)注意的是，命題的謂詞形式中的個體出現(xiàn)的次序影響命題的真值，不是隨意變動，否則真值會有變化。.原子謂詞原子命題的謂詞形式還可以進(jìn)一步加以抽象，比如在謂詞右側(cè)的圓括號內(nèi)的n個個體常元被替換成個體變元，如x1,x2,··

42、;·,xn，這樣便得了一種關(guān)于命題結(jié)構(gòu)的新表達(dá)形式，稱之為n元原子謂詞。定義 由一個謂詞(如P)和n個體變元(如x1，x2，xn)組成的P(x1，x2，xn)，稱它為n元原子謂詞或n元命題函數(shù)，簡稱n元謂詞。而個體變元的論述范圍，稱為個體域或論域。l 當(dāng)n=1時，稱一元謂詞，如S(x)l 當(dāng)n=2時，稱為二元謂詞，如P(x，y)l l 特別地，當(dāng)n=0，稱為零元謂詞。零元謂詞是簡單命題，這樣命題與謂詞就得到了統(tǒng)一。注意：1. n元謂詞不是命題，只有其中的個體變元用特定個體或個體常元替代時，才能成為一個命題。 例如，令S(x)：x是大學(xué)生,這是一元謂詞，不是命題； S(c)：張明是位大

43、學(xué)生，這就是一個命題。2. 個體變元在哪些論域取特定的值，對命題的真值有影響。 例如，令S(x)：x是大學(xué)生。若x的論域為某大學(xué)的計算機(jī)系中的全體同學(xué)，則S(x)是真的；若x的論域是某中學(xué)的全體學(xué)生，則S(x)是假的；若x的論域是某劇場中的觀眾，且觀眾中有大學(xué)生也有非大學(xué)生的其它觀眾，則S(x)是真值是不確定的。 通常，把一個n元謂詞中的每個個體的論域綜合在一起作為它的論域，稱為n元謂詞的全總論域。定義了全總論域，為深入研究命題提供了方便。 當(dāng)一個命題沒有指明論域時，一般都把全總論域作為其論域。而這時又常常要采用一個謂詞如P(x)來限制個體變元x的取值范圍，并把P(x)稱為特性謂詞。特性謂詞：

44、用來限制個體變元的取值范圍的謂詞P(x) 稱為特性謂詞。例如，在全總論域中，用M(x)表示x是人；用R(x)表示x是實數(shù)等。.量詞在命題中分析出個體和謂詞后, 仍不足以表達(dá)日常生活中的各種問題 ，例如S(x)表示x是大學(xué)生，x的個體域為某單位的職工S(x)可表示某單位職工都是大學(xué)生，也可表示某單位有一些職工是大學(xué)生。 為了避免理解上的歧義，在謂詞邏輯中，需要引入用以刻劃“所有的”、“存在一些”等表示不同數(shù)量的詞，即量詞，其定義如下：定義 l 符號"稱為全稱量詞符，用來表達(dá)“對所有的”、“每一個”、“對任何一個”、“一切”等詞語；"x稱為全稱量詞，x稱為指導(dǎo)變元。l 符號$稱

45、為存在量詞符，用來表達(dá)“存在一些”、“至少有一個”、“對于一些”、“某個”等詞語；$x稱為存在量詞，x稱為指導(dǎo)變元。l 符號$!稱為存在唯一量詞符，用來表達(dá)“恰有一個”、“存在唯一”等詞語；$!x稱為存在唯一量詞，稱x為指導(dǎo)變元。l 全稱量詞、存在量詞、存在唯一量詞統(tǒng)稱量詞。量詞記號是由邏輯學(xué)家Fray引入的，有了量詞之后，用邏輯符號表示命題的能力大大加強(qiáng)了。例 試用量詞、謂詞表示下列命題： 所有大學(xué)生都熱愛祖國； 每個自然數(shù)都是實數(shù)； 一些大學(xué)生有遠(yuǎn)大理想； 有的自然數(shù)是素數(shù)。解 令S(x)：x是大學(xué)生，L(x)：x熱愛祖國，則所有大學(xué)生都熱愛祖國 ("x)(S(x)L(x) 令N

46、(x)：x是自然數(shù)，R(x)：x是實數(shù)，則每個自然數(shù)都是實數(shù) ("x)(N(x)R(x) l 全稱量詞("x)后跟條件式。令S(x)：x是大學(xué)生， I(x)：x有遠(yuǎn)大理想，則一些大學(xué)生有遠(yuǎn)大理想 ($x)(S(x)I(x)令N(x)：x是自然數(shù)， P(x)：x是素數(shù)。則有的自然數(shù)是素數(shù) ($x)(N(x)P(x)l 存在量詞($x)后跟合取式。 如果在解答時，指明了個體域，便不用特性謂詞，例如在、中令個體域為全體大學(xué)生，和中的個體域為全部自然數(shù)，則可符號化為：("x)L(x) ("x)R(x)($x)I(x) ($x)P(x)謂詞前加上了量詞，稱為謂詞的

47、量化。若一個謂詞中所有個體變元都量化了，則該謂詞就變成了命題。這是因為在謂詞被量化后，可以在整個個體域中考慮命題的真值了。這如同數(shù)學(xué)中的函數(shù)f(x)， 的值是不確定的，但 可確定其值。2.2 謂詞公式與翻譯.謂詞公式為了方便處理數(shù)學(xué)和計算機(jī)科學(xué)的邏輯問題及謂詞表示的直覺清晰性，將引進(jìn)項的概念。定義 項由下列規(guī)則形成： 個體常元和個體變元是項； 若f是n元函數(shù)，且t1，t2，tn是項，則f(t1，t2，tn)是項； 所有項都由和生成。有了項的定義，函數(shù)的概念就可用來表示個體常元和個體變元。這里函數(shù)是就廣義而言的。 例如，令f(x,y)表示x+y，謂詞N(x)表示x是自然數(shù)，那么f(2,3)表示個

48、體自然數(shù)5，而N(f(2,3)表示5是自然數(shù)。定義 若P(x1，x2，xn)是n元謂詞，t1，t2，tn是項，則稱P(t1，t2，tn)為原子謂詞公式，簡稱原子公式。定義 合式謂詞公式當(dāng)且僅當(dāng)由下列規(guī)則形成的符號串l 原子公式是合式謂詞公式；l 若A是合式謂詞公式，則(A)是合式謂詞公式；l 若A，B是合式謂詞公式，則(AB)，(AB)，(AB)和(A«B)都是合式謂詞公式；l 若A是合式謂詞公式，x是個體變元，則("x)A、($x)A都是合式謂詞公式；l 僅有有限項次使用、和形成的才是合式謂詞公式。.謂詞邏輯的翻譯l 把一個文字?jǐn)⑹龅拿}，用謂詞公式表示出來，稱為謂詞邏輯

49、的翻譯或符號化；反之亦然。l 一般說來，符號化的步驟如下：l 正確理解給定命題。必要時把命題改敘，使其中每個原子命題、原子命題之間的關(guān)系能明顯表達(dá)出來。l 把每個原子命題分解成個體、謂詞和量詞；在全總論域討論時，要給出特性謂詞。l 找出恰當(dāng)量詞。應(yīng)注意全稱量詞("x)后跟條件式，存在量詞($x)后跟合取式。l 用恰當(dāng)?shù)穆?lián)結(jié)詞把給定命題表示出來。l 例 將命題“沒有最大的自然數(shù)”符號化。解 命題中“沒有最大的”顯然是對所有的自然數(shù)而言，所以可理解為“對所有的x，如果x是自然數(shù)，則一定還有比x大的自然數(shù)”，再具體點(diǎn)，即“對所有的x如果x是自然數(shù)，則一定存在y，y也是自然數(shù)，并且y比x大”

50、。令N(x):x是自然數(shù)，G(x,y):x大于y，則原命題表示為：("x)(N(x)($y)(N(y)G(y,x)。2.3 約束變元與自由變元定義 給定一個謂詞公式A，其中有一部分公式形如("x)B(x)或($x)B(x)，則稱它為A的x約束部分，稱B(x)為相應(yīng)量詞的作用域或轄域。在轄域中，x的所有出現(xiàn)稱為約束出現(xiàn)，x稱為約束變元； B(x)中不是約束出現(xiàn)的其它個體變元的出現(xiàn)稱為自由出現(xiàn)，這些個體變元稱為自由變元。l 對于給定的謂詞公式，能夠準(zhǔn)確地判定它的轄域、約束變元和自由變元是很重要的。l 通常，一個量詞的轄域B(x)是某公式A的一部分，稱此轄域為A的子公式。因此，確

51、定一個量詞的轄域即是找出位于該量詞之后的相鄰接的子公式，具體地講：若量詞后有括號，則括號內(nèi)的子公式就是該量詞的轄域；若量詞后無括號，則與量詞鄰接的子公式為該量詞的轄域。 判定給定公式A中個體變元是約束變元還是自由變元，關(guān)鍵是要看它在A中是約束出現(xiàn)，還是自由出現(xiàn)。例 指出下列各合式公式中的量詞轄域、個體變元的約束出現(xiàn)和自由出現(xiàn)。(1) ("x) (P(x)($y) Q(x,y),量詞("x)的轄域是P(x) ($y) Q(x,y),量詞($y)的轄域是Q(x,y),對于($y)的轄域而言，y為約束出現(xiàn)，x為自由出現(xiàn)。對于("x)的轄域而言，x和y均為約束出現(xiàn)，x約束

52、出現(xiàn)2次，y約束出現(xiàn)1次。(2) ($x) H(x)L(x,y),量詞($x)的轄域是H(x) ，x為約束出現(xiàn)，L(x,y)中的x和y都為自由出現(xiàn)。對于整個公式而言，x的約束出現(xiàn)1次，自由出現(xiàn)1次，y自由出現(xiàn)1次。(3) ("x) ("y) (P(x,y)Q(y,z)($x)R(x,y),在公式("x) ("y) (P(x,y)Q(y,z)中，量詞("x)的轄域是("y) (P(x,y)Q(y,z)，量詞("y)的轄域是(P(x,y)Q(y,z)，x和y為約束出現(xiàn)，z為自由出現(xiàn)；在公式($x)R(x,y)中,量詞("

53、;x)的轄域是R(x,y)，x為約束出現(xiàn)，y為自由出現(xiàn)。在整個公式中，x為約束出現(xiàn)，y為約束出現(xiàn)又為自由出現(xiàn)，z為自由出現(xiàn)。 今后常用元語言符號A(x)表示x是其中的一個個體變元自由出現(xiàn)的任意公式，一旦在A(x)前加上量詞("x)或($x)，即得公式("x)A(x),或($x)A(x)。這時，x即是約束出現(xiàn)了。 類似地，用A(x,y)表示x和y是自由出現(xiàn)的公式。定義 設(shè)A為任意一個公式，若A中無自由出現(xiàn)的個體變元，則稱A為封閉的合式公式，簡稱閉式。若A中沒有約束變元出現(xiàn)，則稱A為開放公式，簡稱開式。 由閉式定義可知，閉式中所有個體變元均為約束出現(xiàn)。同樣，開式中所有個體變元均

54、為自由出現(xiàn)。例如：("x)(P(x)Q(x)和($x)("y)(P(x)Q(x,y)是閉式("x)(P(x)Q(x,y)和($y)("z)L(x,y,z)不是閉式P(x)Q(x,y)和L(x,y,z)是開式("x)(P(x)Q(x,y)既不是閉式也不是開式l 從約束變元的概念可以看出, P(x1, x2, , xn)是n元謂詞, 它有n個相互獨(dú)立的自由變元, 若對其中k個變元進(jìn)行約束，則成為n k元謂詞。 當(dāng)多個量詞連續(xù)出現(xiàn), 它們之間無括號分隔時,我們約定從左到右的次序讀出。后面的量詞在前面量詞的轄域之中, 且量詞對變元的約束與量詞的次序有關(guān)。量詞的次序不能隨意顛倒, 否則將與原命題意義不符。例:令f(x,y):x小于y減2，謂詞公式("y)($x) f(x,y), x, y的個體域為實數(shù)集。 量詞"y的轄域為($x) f(x,y), 量詞$x的轄域為f(x,y), 公式表示“任何實數(shù)y均有實數(shù)x, x< y 2”，是真命題。 若將量詞次序改為($x)("y) f(x,y), 則公式表示“存在一個實數(shù)x, 對任何實數(shù)y均有x<y2”，是假命題。 從前面討論可以看出，在一公式中，有的個體變元既可以是約束出現(xiàn)，又可以是自由出現(xiàn)，這就容易產(chǎn)生混淆。為了避免混淆，采用下面