給力離散小組傾血編制

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

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

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

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

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

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

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

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

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

10、戰(zhàn)斗，則此命題符號(hào)化為PQ。1-4真值表與等價(jià)公式定義1：在合式公式中，根據(jù)對(duì)每個(gè)命題變?cè)概烧嬷档母鞣N可能組合，求解合式公式的對(duì)應(yīng)真值，匯列成表，稱(chēng)為真值表。l 定義2：對(duì)于命題公式A中每個(gè)命題變?cè)狿i，任給一個(gè)指派S(Pi)或解釋I(Pi)，得到一種真值的組合S(P1) S(P2)S(Pn)或I(P1) I(P2)I(Pn) 稱(chēng)為A的一個(gè)真值指派，或稱(chēng)為A的一種解釋?zhuān)洖镾(A)或I(A)。若S(A)或I(A)為T(mén)，稱(chēng)S(A)或I(A)為A的成真指派或說(shuō)A的解釋為真。類(lèi)似地定義A的成假指派。 例：構(gòu)造P(PQ)的真值表 解：PQP(PQ)00 1 1 101 1 1 110 0 1 011

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

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

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

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也是命題公式，則稱(chēng)X是A的子公式。定理1：設(shè)A1是命題公式A的子公式，若A1ÛB1，則若將A中的A1用B1來(lái)替換，得到公式B ，則B與A等價(jià)，即AÛB.(替換規(guī)則)。 證明： 因?yàn)閷?duì)變?cè)娜我唤M指派， A1與B1真值相同，故以B1取代A1后，公式

16、B與公式A相對(duì)于變?cè)娜我恢概傻恼嬷狄脖叵嗤?，所以AÛB。定義：稱(chēng)滿(mǎn)足定理1的替換為等價(jià)替換。定理2： 在一個(gè)永真式A中,任何一個(gè)原子命題變?cè)猂出現(xiàn)的每一處,用另一個(gè)公式代入,所得公式B仍是永真式.(代入規(guī)則)。證明:因?yàn)橛勒媸綄?duì)任意解釋,其值都是真,與所給的某個(gè)命題變?cè)概傻恼嬷凳钦孢€是假無(wú)關(guān),因此,用一個(gè)命題公式代入到原子命題變?cè)猂出現(xiàn)的每一處后,所得命題公式的真值仍為真.代入與替換的區(qū)別:l 代入是對(duì)原子命題變?cè)缘?，而替換通常是可對(duì)命題公式實(shí)行之。l 代入必須是處處代入，替換則可部分替換，也可全部替換。l 代入是對(duì)一個(gè)永真式進(jìn)行的，替換則是對(duì)一般公式進(jìn)行的。1-5 蘊(yùn)涵式定

17、義1：當(dāng)且僅當(dāng)PQ是一個(gè)重言式時(shí)，稱(chēng)“P重言蘊(yùn)涵Q”，在不會(huì)引起歧義的情況下，簡(jiǎn)稱(chēng)為“蘊(yùn)涵”，記作PÞQ。l 注：重言蘊(yùn)涵“Þ”與條件（也叫實(shí)質(zhì)蘊(yùn)涵）“”的區(qū)別類(lèi)似于Û 與的區(qū)別定理4：設(shè)P、Q為任意兩個(gè)命題公式，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是兩個(gè)命題公式， P和Q的合取非是一個(gè)新命題公式，記作PQ。當(dāng)且僅當(dāng)P和Q的真值都為T(mén)時(shí)，PQ為F ，其他情況下PQ的真值都是T ?！昂先》恰蓖ǔＲ卜Q(chēng)“與非”。l 根據(jù)此定義，可知 PQ Û (PQ)l 的性質(zhì)： PQ Û QP PP Û P (PQ)(PQ) Û PQ (PP)(QQ) Û PQ定義2：設(shè)P和Q是兩個(gè)命題公式， P和Q的

19、析取非是一個(gè)新命題公式，記作PQ。當(dāng)且僅當(dāng)P和Q的真值都為F時(shí)，PQ為T(mén) ，其他情況下PQ的真值都是F ?！拔鋈》恰蓖ǔＲ卜Q(chēng)“或非”。l 根據(jù)此定義，可知 PQ Û (PQ)l 的性質(zhì)： PQ Û QP PP Û P (PQ)(PQ) Û PQ (PP)(QQ) Û PQ定義3：設(shè)P和Q是兩個(gè)命題公式， P和Q的條件非是一個(gè)新命題公式，記作PQ。當(dāng)且僅當(dāng)P為T(mén)而Q為F時(shí)，PQ為T(mén)，其他情況下PQ的真值都是F。也用符號(hào)'表示。l 根據(jù)此定義，可知 PQ Û (PQ)定義4：設(shè)P和Q是兩個(gè)命題公式， P和Q的雙條件非是一個(gè)新命題公

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

21、稱(chēng)為A的對(duì)偶式。l 例：求(PQ)R的對(duì)偶式。 (PQ)R定理1：設(shè)A*是A的對(duì)偶式，P1，P2，P3，Pn是出現(xiàn)于A和A*中的原子命題變?cè)?，則有 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)，驗(yàn)證定理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中的原子變?cè)?，因?yàn)锳ÛB，即：A(P1,P2,Pn)B(P1,P2,Pn)是一個(gè)重言式。故有： A(P1,P2,Pn)B(P1,P2,Pn)是一個(gè)重言式。即A(P1,P2,Pn)ÛB(P1,P2,Pn) 再由定理1， A* Û B* ，即A* Û B*1-7對(duì)偶和范式范式定義 命題變?cè)兔}變?cè)姆穸?稱(chēng)為文字.如果一個(gè)文字恰為另一個(gè)文字的否定,則稱(chēng)它

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

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

25、個(gè)的文字、簡(jiǎn)單合取式和簡(jiǎn)單析取式既是析取范式; 又是合取范式。任何析取范式的對(duì)偶式為合取范式, 任何合取范式的對(duì)偶式為析取范式。定理 (范式存在定理) 對(duì)于任意公式, 都存在等價(jià)于它的析取范式和合取范式。l 求任意命題公式的合取(析取)范式的步驟 1)將公式中的聯(lián)結(jié)詞化成， ，如消除公式中的運(yùn)算符“®”和“«”。可用等價(jià)式將 P®Q替換為PQP«Q替換為(P®Q)(Q®P)即 (PQ)(PQ) (析取范式)或 (PQ)(PQ) (合取范式) 2)利用雙否律和德摩根律將否定符號(hào)直接移到各個(gè)命題變?cè)?，如將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 (消去第一個(gè)) Û Ø (Ø(PQ)R)P (消去第二個(gè)) Û Ø(ØP ØQ)R)P (Ø內(nèi)移) Û(Ø ØP 

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

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

29、律有:Û (PQRP)(RQRP)第一個(gè)簡(jiǎn)單析取式同時(shí)包含有P和P，第二個(gè)簡(jiǎn)單析取式同時(shí)包含有R和R。原公式是重言式。定義 ：在含有n個(gè)命題變?cè)暮?jiǎn)單合取式中，若每個(gè)命題變?cè)c它的否定不同時(shí)存在，且兩者之一必須出現(xiàn)一次且僅出現(xiàn)一次，則稱(chēng)此簡(jiǎn)單合取式為小項(xiàng),或布爾積。l 如：兩個(gè)命題變?cè)狿和Q構(gòu)成的小項(xiàng)有PQ，PQ，PQ，PQ 。注：n個(gè)命題變?cè)男№?xiàng)有2n個(gè)。3個(gè)命題變?cè)?個(gè)小項(xiàng)對(duì)應(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個(gè)命題變?cè)伯a(chǎn)生2n個(gè)小項(xiàng),分別記為m0,m1,.m2n-1.小項(xiàng)有如下性質(zhì)：1. 沒(méi)有兩個(gè)小項(xiàng)是等價(jià)的，即各小項(xiàng)的真值表都是不同的。2. 任意兩個(gè)不同的小項(xiàng)的合取式是永假的3. 所有小項(xiàng)的析取為永真的4. 每個(gè)小項(xiàng)只在一組真值指派下為T(mén)，且其真值1位于主對(duì)角線上。這表明每個(gè)小項(xiàng)與其成真指派之間建立了一一對(duì)應(yīng)關(guān)系。定義 ：在給定公式的析取范式中，若其簡(jiǎn)單合取式都是小項(xiàng)，則稱(chēng)該范式為主析取范式。定理：一個(gè)公式的主析取范式是唯一的。定理：在真值表中，一個(gè)命題公式A的真值為T(mén)的指派所對(duì)應(yīng)的小項(xiàng)的析取，即為

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

32、; R) ® P.由前例可知, 原公式的析取范式為, P (Q ØR)用P(ØQQ)(ØRR)取代P.用(ØPP)(Q ØR)取代(Q ØR).然后展開(kāi)得小項(xiàng).(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個(gè)命題變?cè)暮?jiǎn)單析取式中，若每個(gè)命題變?cè)c它的否定不能同時(shí)存在，而兩者必須出現(xiàn)一次且僅出現(xiàn)一次，則稱(chēng)此簡(jiǎn)單析取式為大項(xiàng)，或布爾和。如：兩個(gè)命題變?cè)狿和Q構(gòu)成的大項(xiàng)有PQ，PQ，PQ，PQ 。注：n個(gè)命題變?cè)拇箜?xiàng)有2n個(gè)l 注：可以為大項(xiàng)指定一種編碼，如果將命題變?cè)醋值湫蚺帕?，并且把命題變?cè)c0對(duì)應(yīng)，命題變?cè)姆穸ㄅc1對(duì)應(yīng)，則可對(duì)2n個(gè)大項(xiàng)依二進(jìn)制數(shù)編碼。例如：M00對(duì)應(yīng)PQ，M101對(duì)應(yīng)PQRl 注意:編碼正好與小項(xiàng)相反 大項(xiàng)具有如下性質(zhì)：（類(lèi)似小項(xiàng)）1. 沒(méi)有兩個(gè)大項(xiàng)是等價(jià)的2. 任意兩個(gè)

34、不同大項(xiàng)的析取為T(mén)3. 全體大項(xiàng)的合取必為F4. 每個(gè)大項(xiàng)只有一個(gè)解釋為假，且其真值0位于主對(duì)角線上。這表明每個(gè)大項(xiàng)與其成假指派之間建立了一一對(duì)應(yīng)關(guān)系。定義 ：在給定公式的合取范式中，若所有簡(jiǎn)單析取式都是大項(xiàng)，則稱(chēng)該合取范式為主合取范式。定理：一個(gè)公式的主合取范式是唯一的。l 定理：在真值表中，一個(gè)命題公式的真值為的指派所對(duì)應(yīng)的大項(xiàng)的合取，即為該命題公式的主合取范式。l 定理 ：任意含n個(gè)命題變?cè)姆怯勒婷}公式A都存在與其等價(jià)的主合取范式。主合取范式亦可由等價(jià)變換求得，基本步驟如下 1)化為合取范式 2)除去合取范式中所有永真合取項(xiàng) 3)合并重復(fù)項(xiàng) 4)補(bǔ)入合取項(xiàng)中沒(méi)有出現(xiàn)的命題變?cè)缣?/p>

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

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

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

38、成真和成假賦值.1-8推理理論例 張三說(shuō)李四在說(shuō)謊, 李四說(shuō)王五在說(shuō)謊, 王五說(shuō)張三、李四都在說(shuō)謊。問(wèn)誰(shuí)說(shuō)真話, 誰(shuí)說(shuō)假話？解 設(shè)A:張三說(shuō)真話; B:李四說(shuō)真話; C:王五說(shuō)真話依題意有 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即: 李四說(shuō)真話, 張三和王五說(shuō)假話。本章構(gòu)造推論參照證明題集錦第二章 謂詞邏輯（部分*內(nèi)容為了解）在謂詞邏輯中，為揭示命題內(nèi)部結(jié)構(gòu)及其不同命題的內(nèi)部結(jié)構(gòu)關(guān)系，就按照這兩部分對(duì)命題進(jìn)行分析，并且把主語(yǔ)稱(chēng)為個(gè)體或客體，把謂語(yǔ)稱(chēng)為謂詞。.個(gè)體、謂詞和命題的謂詞形式l 定義 在原子命題中，所描述的對(duì)象稱(chēng)為個(gè)體；用以描述個(gè)體的性質(zhì)或個(gè)體間關(guān)系的部分，稱(chēng)

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

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

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

43、學(xué)生，這就是一個(gè)命題。2. 個(gè)體變?cè)谀男┱撚蛉√囟ǖ闹?，?duì)命題的真值有影響。 例如，令S(x)：x是大學(xué)生。若x的論域?yàn)槟炒髮W(xué)的計(jì)算機(jī)系中的全體同學(xué)，則S(x)是真的；若x的論域是某中學(xué)的全體學(xué)生，則S(x)是假的；若x的論域是某劇場(chǎng)中的觀眾，且觀眾中有大學(xué)生也有非大學(xué)生的其它觀眾，則S(x)是真值是不確定的。 通常，把一個(gè)n元謂詞中的每個(gè)個(gè)體的論域綜合在一起作為它的論域，稱(chēng)為n元謂詞的全總論域。定義了全總論域，為深入研究命題提供了方便。 當(dāng)一個(gè)命題沒(méi)有指明論域時(shí)，一般都把全總論域作為其論域。而這時(shí)又常常要采用一個(gè)謂詞如P(x)來(lái)限制個(gè)體變?cè)獂的取值范圍，并把P(x)稱(chēng)為特性謂詞。特性謂詞：

44、用來(lái)限制個(gè)體變?cè)娜≈捣秶闹^詞P(x) 稱(chēng)為特性謂詞。例如，在全總論域中，用M(x)表示x是人；用R(x)表示x是實(shí)數(shù)等。.量詞在命題中分析出個(gè)體和謂詞后, 仍不足以表達(dá)日常生活中的各種問(wèn)題 ，例如S(x)表示x是大學(xué)生，x的個(gè)體域?yàn)槟硢挝坏穆毠(x)可表示某單位職工都是大學(xué)生，也可表示某單位有一些職工是大學(xué)生。 為了避免理解上的歧義，在謂詞邏輯中，需要引入用以刻劃“所有的”、“存在一些”等表示不同數(shù)量的詞，即量詞，其定義如下：定義 l 符號(hào)"稱(chēng)為全稱(chēng)量詞符，用來(lái)表達(dá)“對(duì)所有的”、“每一個(gè)”、“對(duì)任何一個(gè)”、“一切”等詞語(yǔ)；"x稱(chēng)為全稱(chēng)量詞，x稱(chēng)為指導(dǎo)變?cè)?。l 符號(hào)$稱(chēng)

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

46、(x)：x是自然數(shù)，R(x)：x是實(shí)數(shù)，則每個(gè)自然數(shù)都是實(shí)數(shù) ("x)(N(x)R(x) l 全稱(chēng)量詞("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是素?cái)?shù)。則有的自然數(shù)是素?cái)?shù) ($x)(N(x)P(x)l 存在量詞($x)后跟合取式。 如果在解答時(shí)，指明了個(gè)體域，便不用特性謂詞，例如在、中令個(gè)體域?yàn)槿w大學(xué)生，和中的個(gè)體域?yàn)槿孔匀粩?shù)，則可符號(hào)化為：("x)L(x) ("x)R(x)($x)I(x) ($x)P(x)謂詞前加上了量詞，稱(chēng)為謂詞的

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

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

49、的翻譯或符號(hào)化；反之亦然。l 一般說(shuō)來(lái)，符號(hào)化的步驟如下：l 正確理解給定命題。必要時(shí)把命題改敘，使其中每個(gè)原子命題、原子命題之間的關(guān)系能明顯表達(dá)出來(lái)。l 把每個(gè)原子命題分解成個(gè)體、謂詞和量詞；在全總論域討論時(shí)，要給出特性謂詞。l 找出恰當(dāng)量詞。應(yīng)注意全稱(chēng)量詞("x)后跟條件式，存在量詞($x)后跟合取式。l 用恰當(dāng)?shù)穆?lián)結(jié)詞把給定命題表示出來(lái)。l 例 將命題“沒(méi)有最大的自然數(shù)”符號(hào)化。解 命題中“沒(méi)有最大的”顯然是對(duì)所有的自然數(shù)而言，所以可理解為“對(duì)所有的x，如果x是自然數(shù)，則一定還有比x大的自然數(shù)”，再具體點(diǎn)，即“對(duì)所有的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 約束變?cè)c自由變?cè)x 給定一個(gè)謂詞公式A，其中有一部分公式形如("x)B(x)或($x)B(x)，則稱(chēng)它為A的x約束部分，稱(chēng)B(x)為相應(yīng)量詞的作用域或轄域。在轄域中，x的所有出現(xiàn)稱(chēng)為約束出現(xiàn)，x稱(chēng)為約束變?cè)?B(x)中不是約束出現(xiàn)的其它個(gè)體變?cè)某霈F(xiàn)稱(chēng)為自由出現(xiàn)，這些個(gè)體變?cè)Q(chēng)為自由變?cè)?。l 對(duì)于給定的謂詞公式，能夠準(zhǔn)確地判定它的轄域、約束變?cè)妥杂勺冊(cè)呛苤匾?。l 通常，一個(gè)量詞的轄域B(x)是某公式A的一部分，稱(chēng)此轄域?yàn)锳的子公式。因此，確

51、定一個(gè)量詞的轄域即是找出位于該量詞之后的相鄰接的子公式，具體地講：若量詞后有括號(hào)，則括號(hào)內(nèi)的子公式就是該量詞的轄域；若量詞后無(wú)括號(hào)，則與量詞鄰接的子公式為該量詞的轄域。 判定給定公式A中個(gè)體變?cè)羌s束變?cè)€是自由變?cè)P(guān)鍵是要看它在A中是約束出現(xiàn)，還是自由出現(xiàn)。例 指出下列各合式公式中的量詞轄域、個(gè)體變?cè)募s束出現(xiàn)和自由出現(xiàn)。(1) ("x) (P(x)($y) Q(x,y),量詞("x)的轄域是P(x) ($y) Q(x,y),量詞($y)的轄域是Q(x,y),對(duì)于($y)的轄域而言，y為約束出現(xiàn)，x為自由出現(xiàn)。對(duì)于("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)。對(duì)于整個(gè)公式而言，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)。在整個(gè)公式中，x為約束出現(xiàn)，y為約束出現(xiàn)又為自由出現(xiàn)，z為自由出現(xiàn)。 今后常用元語(yǔ)言符號(hào)A(x)表示x是其中的一個(gè)個(gè)體變?cè)杂沙霈F(xiàn)的任意公式，一旦在A(x)前加上量詞("x)或($x)，即得公式("x)A(x),或($x)A(x)。這時(shí)，x即是約束出現(xiàn)了。 類(lèi)似地，用A(x,y)表示x和y是自由出現(xiàn)的公式。定義 設(shè)A為任意一個(gè)公式，若A中無(wú)自由出現(xiàn)的個(gè)體變?cè)瑒t稱(chēng)A為封閉的合式公式，簡(jiǎn)稱(chēng)閉式。若A中沒(méi)有約束變?cè)霈F(xiàn)，則稱(chēng)A為開(kāi)放公式，簡(jiǎn)稱(chēng)開(kāi)式。 由閉式定義可知，閉式中所有個(gè)體變?cè)鶠榧s束出現(xiàn)。同樣，開(kāi)式中所有個(gè)體變?cè)?/p>

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)是開(kāi)式("x)(P(x)Q(x,y)既不是閉式也不是開(kāi)式l 從約束變?cè)母拍羁梢钥闯? P(x1, x2, , xn)是n元謂詞, 它有n個(gè)相互獨(dú)立的自由變?cè)? 若對(duì)其中k個(gè)變?cè)M(jìn)行約束，則成為n k元謂詞。 當(dāng)多個(gè)量詞連續(xù)出現(xiàn), 它們之間無(wú)括號(hào)分隔時(shí),我們約定從左到右的次序讀出。后面的量詞在前面量詞的轄域之中, 且量詞對(duì)變?cè)募s束與量詞的次序有關(guān)。量詞的次序不能隨意顛倒, 否則將與原命題意義不符。例:令f(x,y):x小于y減2，謂詞公式("y)($x) f(x,y), x, y的個(gè)體域?yàn)閷?shí)數(shù)集。 量詞"y的轄域?yàn)?$x) f(x,y), 量詞$x的轄域?yàn)閒(x,y), 公式表示“任何實(shí)數(shù)y均有實(shí)數(shù)x, x< y 2”，是真命題。 若將量詞次序改為($x)("y) f(x,y), 則公式表示“存在一個(gè)實(shí)數(shù)x, 對(duì)任何實(shí)數(shù)y均有x<y2”，是假命題。 從前面討論可以看出，在一公式中，有的個(gè)體變?cè)瓤梢允羌s束出現(xiàn)，又可以是自由出現(xiàn)，這就容易產(chǎn)生混淆。為了避免混淆，采用下面