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

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

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

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

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

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

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

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

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

9、s)。 在作用域中x的一切出現(xiàn)稱為約束出現(xiàn)，即不可以取值代入的變元稱為約束變元( binding variables)。除去約束變元以外所出現(xiàn)的變元稱為自由變元，即可取值代入的變元稱為自由變元(free variables)。,4-4 變元的約束,由前所述，P(x1,x2,…,xn) 稱為n元謂詞。他有n個相互獨立的客體變元x1,x2,…,xn，若對其中的個 k個變元進行約束，則P(x1,x2,…,xn) 稱變成n

10、-k元謂詞。因此，謂詞公式中如果沒有自由變元出現(xiàn)，則該式就成為一個命題。 為了避免由于變元的約束與自由同時出現(xiàn)，引起概念上的混亂，故可以對約束變元進行更名。使得一個變元在一個公式中具有一種形式出現(xiàn)，即呈自由出現(xiàn)或約束出現(xiàn)。,約束變元更名規(guī)則： （1）對于約束變元可以更名，其更改的變元名稱范圍是量詞中的指導(dǎo)變元，以及該量詞作用域中所出現(xiàn)的該變元，在公式的其余部分不變。 （2）更名時一定要更改為作用域中沒有出現(xiàn)過

11、的變元名稱。 自由變元代入規(guī)則： （1）對于謂詞公式中的自由變元可以代入，代入時需要對公式中出現(xiàn)該自由變元的每一處進行代入。 （2）用以代入的變元與原公式中所有變元的名稱不能相同。,量詞作用域中的約束變元，當(dāng)論域的元素是有限時，客體變元的所有可能的取代是可枚舉的。 設(shè)論域元素為：a1 , a2 , … , an 。 則有如下等價式： ?xA(x) ? A(a1) ∧ A

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

13、個體域E及公式A中各謂詞符號的解釋I，如果A中個體變元x1 ,…,xn分別取值u1 ,…,un時A真，則稱A在u1 ,…,un處真；當(dāng)x1 ,…,xn無論取E中怎樣的個體u1 ,…,un, A在u1 ,…,un處均真，則稱A在解釋I下真。,4-5 謂詞演算的等價式和蘊涵式,定義4-5.3 如果在某一個體域E、某一解釋I下，對于變元的所有取值狀況，A的取值都假，則稱公式A為不可滿足的。公式A不可滿足時也稱A為永假式。,定義4-5.2

14、 給定個體域E，若公式A在每一解釋I下均真，那么稱A在E上永真（ A在E上有效valid ）。若公式A對任何個體域E，均有E上永真，則稱A為永真式，或稱A永真。,定義4-5.4 如果對某一個體域E、某一解釋I和變元的某一取值狀況，A在此處取值真，則稱公式A為可滿足的。,定義4-5.5 設(shè)謂詞公式A中含自由變元x，設(shè)t為一個體項，且t中無自由變元為A中的約束變元，那么稱t是在A中對x可代入的。,代入原理: 若A是永真式，那么對A中變

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

16、演算中使用。,（2）量詞轉(zhuǎn)化 設(shè)P (x)表示個體x具有性質(zhì)P。于是下面的語句表示的意義是等價的： “不是所有的 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、的收縮與擴張 如果量的詞作用域內(nèi)有命題（命題內(nèi)已經(jīng)無個體變元，真假值已經(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,量詞作用域的擴張: ((?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、些等價式 (?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é)詞之間的一些蘊涵式 (?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中符號∨，∧，t，f，? , ?分別換為∧，∨，f，t, ?，? 后所得的公式，那么稱A*為A的對偶式。,（6）多個量詞的使用 全稱量詞與存在量詞在公式中出現(xiàn)的次序不能隨意更換。具有

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

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

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

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

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

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