第2篇數(shù)理邏輯ch4謂詞邏輯

1、第 4 章 謂 詞 邏 輯,4-1 謂詞的概念與表示,4-2 命題函數(shù)與量詞,4-3 謂詞公式與翻譯,4-4 變?cè)募s束,第4章 謂詞演算,4-5 謂詞演算的等價(jià)式與蘊(yùn)涵式,4-6 前束范式,4-7 謂詞演算的演繹與推理理論,4-1 謂詞的概念與表示,命題邏輯是一完整的語句為單位的，謂詞邏輯將語句細(xì)分為“對(duì)象” 和“謂詞”。對(duì)象一般是語句的主語，謂詞一般是語句的謂語。 謂詞演算中把一切討

2、論對(duì)象都稱為個(gè)體，它們可以是客觀世界中的具體客體，也可以是抽象的客體，諸如數(shù)字、符號(hào)等。 確定的個(gè)體常用a，b，c等到小寫字母或字母串表示。a，b，c等稱為常元（constants）。,不確定的個(gè)體常用字母x，y，z，u，v，w等來表示。它們被稱為變?cè)╲ariables）。,謂詞演算中把討論對(duì)象——個(gè)體的全體稱為個(gè)體域（domain of individuals），常用字母D表示，并約定任何D都至少含有一個(gè)成員。,當(dāng)

3、討論對(duì)象遍及一切客體時(shí)，個(gè)體域特稱為全總域（universe），用字母U表示。,用來指明對(duì)象的性質(zhì)或?qū)ο箝g關(guān)系的語句成分稱為謂詞（），用大寫字母表示謂詞，用小寫字母表示變?cè)?，變?cè)g用“，”分割。,通常把謂詞所攜空位的數(shù)目稱為謂詞的元數(shù)。表示單個(gè)客體性質(zhì)的謂詞是一元謂詞，例如P（x）;表示兩個(gè)客體之間關(guān)系的謂詞是二元謂詞，例如Q（x,y）;依此類推。,含空位的寫法有一個(gè)明顯的缺點(diǎn)，可讀性差。因此常用變?cè)獊泶婵瘴?，它們被稱為謂詞命名式

4、，簡(jiǎn)稱謂詞。謂詞命名式不是命題。,當(dāng)謂詞的空位上填入個(gè)體后，便產(chǎn)生一個(gè)關(guān)于該個(gè)體的語句，這時(shí)它被稱為謂詞填式 。謂詞填式是命題。,4-2 命題函數(shù)與量詞,命題與謂詞的關(guān)系：當(dāng)謂詞中的客體變?cè)痪唧w客體常元確定下來（代入或賦值）以后，才成為命題，從而才有確定的真假值。,定義4-2.1 當(dāng)有一個(gè)謂詞，一些客體變?cè)M成的表達(dá)式稱謂簡(jiǎn)單命題函數(shù)。 據(jù)此定義，n元謂詞就是n個(gè)客體變?cè)拿}函數(shù)。 當(dāng)n=0時(shí)，稱為0元謂詞，

5、它本身就是一個(gè)命題。故命題就是n元謂詞的特殊情況。 由一個(gè)或n個(gè)簡(jiǎn)單命題函數(shù)，以及邏輯聯(lián)結(jié)詞組合而成的表達(dá)式稱謂復(fù)合命題函數(shù)。,量詞（quantifiers） 全稱量詞?：指數(shù)量詞“對(duì)所有的”、“每一個(gè)”、“對(duì)任意一個(gè)”等。 例如： ?xA(x), ?yP(y) 存在量詞 ?：指數(shù)量詞“存在一些”、“至少有一個(gè)”、“對(duì)于一些”等 。 例如： ?xA(x)、?yP(y)

6、 由量詞確定的表達(dá)式都與個(gè)體域有關(guān)，因此，在討論帶有量詞的命題函數(shù)時(shí)，必須確定其個(gè)體域。 在全總個(gè)體域中，對(duì)全稱量詞?xH(x)可以寫成?x（M(x)→H(x)）；對(duì)存在量詞? xH(x)可以寫成?x（M(x)∧H(x)）, M(x)為特性謂詞。,我們把 A(x1,x2,…,xn) 稱為謂詞演算的原子公式，其中x1,x2,…,xn是客體變?cè)?，原子公式包括下述形式?Q，A(x), A(x,y), A(f(

7、x),y), A(x,y,z), A(a,y)等。 定義4-3.1 以下條款規(guī)定的符號(hào)串稱為謂詞公式( predicate forrmula)，又稱合式公式(Wff): （1）謂詞填式是公式，命題常元是公式（看作零元謂詞）,原子謂詞公式是合式公式。 （2）如果A合式公式，那么 (┐A) 是合式公式。 （3）如果A，B是合式公式，x為任一變?cè)?那么 (?xA)，(?x A)， (A∧

8、B)，(A∨B)， (A→B)， (A?B)）都是合式公式。 （4）只有有限步使用（1）、（2）、 （3）條款所形成的符號(hào)串是合式公式。,4-3 謂詞公式與翻譯,在謂詞公式中， ?、?后面所跟的x叫做量詞的指導(dǎo)變?cè)蜃饔米冊(cè)??xA(x), ?xP(x)中的A(x)和P(x)分別叫做量詞?和?的作用域或轄域。即當(dāng)量詞用于一謂詞或復(fù)合謂詞表達(dá)式時(shí)，該謂詞或復(fù)合謂詞表達(dá)式稱為量詞的轄域(domains of quantifier

9、s)。 在作用域中x的一切出現(xiàn)稱為約束出現(xiàn)，即不可以取值代入的變?cè)Q為約束變?cè)? binding variables)。除去約束變?cè)酝馑霈F(xiàn)的變?cè)Q為自由變?cè)纯扇≈荡氲淖冊(cè)Q為自由變?cè)?free variables)。,4-4 變?cè)募s束,由前所述，P(x1,x2,…,xn) 稱為n元謂詞。他有n個(gè)相互獨(dú)立的客體變?cè)獂1,x2,…,xn，若對(duì)其中的個(gè) k個(gè)變?cè)M(jìn)行約束，則P(x1,x2,…,xn) 稱變成n

10、-k元謂詞。因此，謂詞公式中如果沒有自由變?cè)霈F(xiàn)，則該式就成為一個(gè)命題。 為了避免由于變?cè)募s束與自由同時(shí)出現(xiàn)，引起概念上的混亂，故可以對(duì)約束變?cè)M(jìn)行更名。使得一個(gè)變?cè)谝粋€(gè)公式中具有一種形式出現(xiàn)，即呈自由出現(xiàn)或約束出現(xiàn)。,約束變?cè)?guī)則： （1）對(duì)于約束變?cè)梢愿?，其更改的變?cè)Q范圍是量詞中的指導(dǎo)變?cè)?，以及該量詞作用域中所出現(xiàn)的該變?cè)?，在公式的其余部分不變?（2）更名時(shí)一定要更改為作用域中沒有出現(xiàn)過

11、的變?cè)Q。 自由變?cè)胍?guī)則： （1）對(duì)于謂詞公式中的自由變?cè)梢源?，代入時(shí)需要對(duì)公式中出現(xiàn)該自由變?cè)拿恳惶庍M(jìn)行代入。 （2）用以代入的變?cè)c原公式中所有變?cè)拿Q不能相同。,量詞作用域中的約束變?cè)?dāng)論域的元素是有限時(shí)，客體變?cè)乃锌赡艿娜〈强擅杜e的。 設(shè)論域元素為：a1 , a2 , … , an 。 則有如下等價(jià)式： ?xA(x) ? A(a1) ∧ A

12、(a2 ) ∧,…, ∧ A(an) ?xA(x) ? A(a1) ∨ A(a2 ) ∨,…, ∨ A(an) 量詞對(duì)變?cè)募s束，往往與量詞的出現(xiàn)順序有關(guān)，約定“量詞按從左到右的順序讀出”。,定義4-5.1 給定任何兩個(gè)謂詞公式Wff A和Wff B，設(shè)他們有共同的個(gè)體域E，若對(duì)A和B的任一組變?cè)M(jìn)行賦值，所得命題的真值都相同，則稱謂詞公式A和B在E上是等價(jià)的，并記作A ? B。,定義4-5.0 給定

13、個(gè)體域E及公式A中各謂詞符號(hào)的解釋I，如果A中個(gè)體變?cè)獂1 ,…,xn分別取值u1 ,…,un時(shí)A真，則稱A在u1 ,…,un處真；當(dāng)x1 ,…,xn無論取E中怎樣的個(gè)體u1 ,…,un, A在u1 ,…,un處均真，則稱A在解釋I下真。,4-5 謂詞演算的等價(jià)式和蘊(yùn)涵式,定義4-5.3 如果在某一個(gè)體域E、某一解釋I下，對(duì)于變?cè)乃腥≈禒顩r，A的取值都假，則稱公式A為不可滿足的。公式A不可滿足時(shí)也稱A為永假式。,定義4-5.2

14、 給定個(gè)體域E，若公式A在每一解釋I下均真，那么稱A在E上永真（ A在E上有效valid ）。若公式A對(duì)任何個(gè)體域E，均有E上永真，則稱A為永真式，或稱A永真。,定義4-5.4 如果對(duì)某一個(gè)體域E、某一解釋I和變?cè)哪骋蝗≈禒顩r，A在此處取值真，則稱公式A為可滿足的。,定義4-5.5 設(shè)謂詞公式A中含自由變?cè)獂，設(shè)t為一個(gè)體項(xiàng)，且t中無自由變?cè)獮锳中的約束變?cè)?，那么稱t是在A中對(duì)x可代入的。,代入原理: 若A是永真式，那么對(duì)A中變

15、元可代入的代入實(shí)例都是永真式。,替換原理: 設(shè)A，D為謂詞公式，C為A的子公式，且C ? D。若B為將A中子公式C的某些出現(xiàn)（未必全部）替換為D后所得的公式，那么A ? B。,改名原理: 若公式A中無自由變?cè)獃，那么， ?xA(x) ? ?yA(y),?xA(x) ? ?yA(y),（1）命題公式的推廣 根據(jù)代入原理，命題演算中的公式可以推廣到謂詞公式中。即命題演算中的等價(jià)公式表和蘊(yùn)涵公式表都可以推廣到謂詞

16、演算中使用。,（2）量詞轉(zhuǎn)化 設(shè)P (x)表示個(gè)體x具有性質(zhì)P。于是下面的語句表示的意義是等價(jià)的： “不是所有的 x 都具有性質(zhì)P。” “存在不具有性質(zhì)P的 x ?！庇谑堑玫剑?┐（?x）P(x) ?（?x） ┐P(x) 同樣， “不存在具有性質(zhì)P的 x ?！?“所有的 x 都不具有性質(zhì)P?！庇谑堑玫剑?┐ （?x）P(x) ?（?x） ┐P(x),（3）量詞作用域

17、的收縮與擴(kuò)張 如果量的詞作用域內(nèi)有命題（命題內(nèi)已經(jīng)無個(gè)體變?cè)?，真假值已?jīng)確定了），則該命題可以移到量詞作用域的外邊。稱之為量詞作用域的收縮。 (?x) ( A(x)∨B ) ? (?x)A(x) ∨ B (?x) ( A(x)∧B ) ? (?x)A(x) ∧ B (?x) ( A(x)∨B ) ? (?x)A(x) ∨ B (?x) ( A(x)∧B )

18、 ? (?x)A(x) ∧ B,量詞作用域的擴(kuò)張: ((?x) A(x) →B ) ? (?x) (A(x) →B ) ((?x) A(x) →B ) ? (?x) (A(x) →B ) (B → (?x)( A(x)) ? (?x) (B → A(x)) (B → (? x)( A(x)) ? (? x) (B → A(x)) 證明（略） （4）量詞與命題聯(lián)結(jié)詞之間的一

19、些等價(jià)式 (?x) ( A(x)∧B(x)) ? (?x)A(x)∧(?x)B(x) (? x) ( A(x)∨B(x)) ? (? x)A(x)∨(? x)B(x),（5）量詞與命題聯(lián)結(jié)詞之間的一些蘊(yùn)涵式 (?x)A(x)∨(?x)B(x) ? (?x) （A(x)∨B(x)） (? x) ( A(x)∧B(x)) ? (? x)A(x)∧(? x)B(x)

20、 (?x) ( A(x)→B(x)) ? (?x)A(x)→(?x)B(x)) (?x) ( A(x)? B(x)) ? (?x)A(x)?(?x)B(x)),定義4-7.1‘ 設(shè)A為僅含聯(lián)結(jié)詞 ┐，∨，∧的謂詞公式，A*為將A中符號(hào)∨，∧，t，f，? , ?分別換為∧，∨，f，t, ?，? 后所得的公式，那么稱A*為A的對(duì)偶式。,（6）多個(gè)量詞的使用 全稱量詞與存在量詞在公式中出現(xiàn)的次序不能隨意更換。具有

21、兩個(gè)量詞的謂詞公式有如下關(guān)系： (?x) (?y) A(x,y) ? (?y) (?x) A(x,y) (?x) (?y) A(x,y) ? (?y) (?x) A(x,y) (?x) (?y) A(x,y) ? (?y) (?x) A(x,y) (?y) (?x) A(x,y)

22、 ? (?x) (?y) A(x,y) (?y) (?x) A(x,y) ? (?x) (?y) A(x,y) (?x) (?y) A(x,y) ? (?y) (?x) A(x,y) (?x) (?y) A(x,y) ? (?y) (?x) A(x,y) (?y) (?x) A(x,y) ? (?x) (?y

23、) A(x,y),,等價(jià)式,,蘊(yùn)涵式,定義4-6.1 公式A’稱為公式A的前束范式(prenex normal forms)，如果A ? A’，且A’形如 Q1x1…QnxnB其中Q1，…，Qn為量詞 ? 或 ?，B中無量詞，且僅含聯(lián)結(jié)詞┐，∨，∧，B稱為母式。當(dāng)B為合取(析取)范式時(shí)，A’稱為A的前束合取(析取)范式。 注意：“一般的范式不要求只含┐，∨，∧”，此定義含蓋了定義3-6.2和定義3-6.3的內(nèi)容 。,4-6 前

24、束范式,定義4-7.1‘ 設(shè)A為僅含聯(lián)結(jié)詞 ┐，∨，∧的謂詞公式，A*為將A中符號(hào)∨，∧，t，f，? , ?分別換為∧，∨，f，t, ?，? 后所得的公式，那么稱A*為A的對(duì)偶式。,定理4-6.1 （前束范式定理） 對(duì)任意謂詞公式均可作出其前束范式，進(jìn)而作出其前束合取范式或前束析取范式。 證明方法給出了化某Wff為前束范式的步驟： （1）內(nèi)移 “┐”號(hào) 根據(jù)量詞轉(zhuǎn)化公式，

25、利用德摩 . 根定律將“┐”號(hào)內(nèi)移到命題變?cè)蛑^詞填式的前面。 （2）前移量詞 根據(jù)量詞轄域的收縮和擴(kuò)張公式，把量詞移到全式的最前面。,定義4-6.2 設(shè)x1,…,xn是公式A中的所有自由變?cè)?，那么公?x1…?xnA(或?x1…?xnA(x1,…,xn)稱為A的全稱封閉式（generalization clusure）。,（1）全稱指定規(guī)則US（ ?-消除規(guī)則 ） 全稱消除定理 對(duì)任意公

26、式A，變?cè)獂，若??xA，則?A 。記為：,命題演算中的推理規(guī)則，如P、T和CP規(guī)則等可以在謂詞推理理論中應(yīng)用，但在謂詞推理中，某些前提與結(jié)論可能是受量詞限制的，為了使用這些等價(jià)式和蘊(yùn)涵式，必須在推理過程中應(yīng)用“消去和添加量詞的規(guī)則”，以便使謂詞公式的推理過程可類似于命題演算中推理理論那樣進(jìn)行。常用的量詞推廣規(guī)則和量詞消去規(guī)則如下：,5-2 謂詞演算的推理理論,（2）全稱推廣規(guī)則UG（ ?-引入規(guī)則） 全稱引入定理 對(duì)任

27、意公式A，變?cè)獂，若? A，則? ?x A。記為：,全稱引入定理‘ 對(duì)任何公式集 ?，公式A和變?cè)獂，x不是 ? 中任一公式的自由變?cè)敲?，?? ? A，則? ? ?x A。,全稱推廣規(guī)則UG（ ?-引入規(guī)則）示例（略）,全稱指定規(guī)則US（ ?-消除規(guī)則 ）示例（略）,,（3）存在指定規(guī)則ES（ ?-消除規(guī)則 ）,存在消除定理’ 設(shè)A，B為任意公式，變?cè)獂是公式A、但不是公式B的自由變?cè)?，那么?dāng)，??x A(x), A(x)? B

28、同時(shí)成立時(shí)，應(yīng)有? B 。記為：,存在消除定理“ 設(shè) ? 為一公式集，A，B為任意公式，變?cè)獂是A的自由變?cè)?，但不?? 中任一公式的自由變?cè)敲串?dāng) ? ? ?x A(x) ，? ?? A(x) ? ? B同時(shí)成立時(shí)，應(yīng)有 ? ? B 。,存在消除定理 設(shè)A，變?cè)獂是公式A的自由變?cè)?，那么?dāng)，??xA成立時(shí)，應(yīng)有?A 。記為：,存在指定規(guī)則ES（ ?-消除規(guī)則 ）示例（略）,（4）存在推廣規(guī)則EG（ ?-引入規(guī)則 ）,存在推廣規(guī)則E