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

2、是語句的謂語。謂詞一般是語句的謂語。 謂詞演算中把一切討論對象都稱為謂詞演算中把一切討論對象都稱為，它們它們可以是客觀世界中的具體客體，也可以是抽象的客體，可以是客觀世界中的具體客體，也可以是抽象的客體，諸如數(shù)字、符號等。諸如數(shù)字、符號等。 確定的個體常用確定的個體常用a，b，c等到小寫字母或字母串表示。等到小寫字母或字母串表示。a，b，c等稱為等稱為（constants）。）。 不確定的個體常用字母不確定的個體常用字母x，y，z，u，v，w等來表等來表示。它們被稱為示。它們被稱為（variables）。）。 謂詞演算中把討論對象謂詞演算中把討論對象個體的全體稱為個體的全體稱為（domain

3、of individuals），常用字常用字母母D表示，并約定任何表示，并約定任何D都至少含有一個成員都至少含有一個成員。 當討論對象遍及一切客體時，個體域特稱為當討論對象遍及一切客體時，個體域特稱為（universe），），用字母用字母U表示。表示。 用來指明對象的性質或對象間關系的語句成用來指明對象的性質或對象間關系的語句成分稱為分稱為（），），用大寫字母表示謂詞，用用大寫字母表示謂詞，用小寫字母表示變元，變元之間用小寫字母表示變元，變元之間用“，”分割。分割。 通常把謂詞所攜空位的數(shù)目稱為謂詞的通常把謂詞所攜空位的數(shù)目稱為謂詞的。表表示單個客體性質的謂詞是一元謂詞，例如示單個客體性質的謂

4、詞是一元謂詞，例如P（x）;表示兩表示兩個客體之間關系的謂詞是二元謂詞，例如個客體之間關系的謂詞是二元謂詞，例如Q（x,y）;依此依此類推。類推。 含空位的寫法有一個明顯的缺點，可讀性差。因此含空位的寫法有一個明顯的缺點，可讀性差。因此常用變元來代替空位，它們被稱為常用變元來代替空位，它們被稱為，簡稱簡稱。 當謂詞的空位上填入個體后，便產生一個關于該個當謂詞的空位上填入個體后，便產生一個關于該個體的語句，這時它被稱為體的語句，這時它被稱為 。 4-2 4-2 命題函數(shù)與量詞命題函數(shù)與量詞（quantifiers）指數(shù)量詞指數(shù)量詞“對所有的對所有的”、“每一每一個個”、“對任意一個對任意一個”等

5、。等。 例如：例如： xA(x), xA(x), yP(y)yP(y)指數(shù)量詞指數(shù)量詞“存在一些存在一些”、“至少至少有一個有一個”、“對于一些對于一些”等等 。 例如：例如： xA(x)xA(x)、 yP(y)yP(y) 由量詞確定的表達式都與個體域有關，因此，在由量詞確定的表達式都與個體域有關，因此，在討論帶有量詞的命題函數(shù)時，必須確定其個體域。討論帶有量詞的命題函數(shù)時，必須確定其個體域。 在全總個體域中，對全稱量詞在全總個體域中，對全稱量詞 xH(x)xH(x)可以寫成可以寫成 x x（M(x)M(x)H(x)H(x)）；對存在量詞）；對存在量詞 xH(x)xH(x)可以寫成可以寫成 x

6、 x（M(x)M(x)H(x)H(x)）, , M(x)M(x)為特性謂詞。為特性謂詞。 我們把我們把 A(x1,x2,xn) 稱為謂詞演算的原子公式，其稱為謂詞演算的原子公式，其中中x1,x2,xn是客體變元，原子公式包括下述形式：是客體變元，原子公式包括下述形式： Q，A(x), A(x,y), A(f(x),y), A(x,y,z), A(a,y)等。等。 定義定義4-3.1 以下條款規(guī)定的符號串稱為以下條款規(guī)定的符號串稱為 predicate forrmula)，又稱，又稱謂詞填式是公式，命題常元是公式（看作零元謂謂詞填式是公式，命題常元是公式（看作零元謂詞）詞）,原子謂詞公式是合式公

7、式。原子謂詞公式是合式公式。如果如果A合式公式，那么合式公式，那么 (A) 是合式公式。是合式公式。如果如果A，B是合式公式，是合式公式，x為任一變元，為任一變元， 那么那么 ( xA)，( x A)， (AB)，(AB)， (AB)， (AB)）都是合式公式。都是合式公式。只有有限步使用（只有有限步使用（1）、（）、（2）、）、 條款所形條款所形成的符號串是合式公式。成的符號串是合式公式。 4-3 4-3 謂詞公式與翻譯謂詞公式與翻譯 在謂詞公式中，在謂詞公式中， 、 后面所跟的后面所跟的x叫做量詞的叫做量詞的指導指導變元變元或或作用變元作用變元， xA(x), xA(x), xP(x)xP

8、(x)中的中的A(x)A(x)和和P(x)P(x)分別叫做量詞分別叫做量詞 和和 的的作用域作用域或或轄域轄域。即。即當量當量詞用于一謂詞或復合謂詞表達式時，該謂詞或復合謂詞詞用于一謂詞或復合謂詞表達式時，該謂詞或復合謂詞表達式稱為表達式稱為(domains of quantifiers)。 在作用域中在作用域中x x的一切出現(xiàn)稱為約束出現(xiàn)，即不可以取的一切出現(xiàn)稱為約束出現(xiàn)，即不可以取值代入的變元稱為值代入的變元稱為( binding variables)。除去約束變元以外所出現(xiàn)的變元稱為自由變元，即可取除去約束變元以外所出現(xiàn)的變元稱為自由變元，即可取值代入的變元稱為值代入的變元稱為(free

9、 variables)。 4-4 4-4 變元的約束變元的約束 由前所述，由前所述，P(x1,x2,xn) 稱為稱為n元謂詞元謂詞。他有。他有n個相互獨立的客體變元個相互獨立的客體變元x1,x2,xn，若對其中的個，若對其中的個 k個個變元進行約束，則變元進行約束，則P(x1,x2,xn) 稱變成稱變成n-k元謂詞元謂詞。因此，謂詞公式中如果沒有自由變元出現(xiàn)，則該式就成因此，謂詞公式中如果沒有自由變元出現(xiàn)，則該式就成為一個命題。為一個命題。 為了避免由于變元的約束與自由同時出現(xiàn)，引起概為了避免由于變元的約束與自由同時出現(xiàn)，引起概念上的混亂，故可以對約束變元進行更名。使得一個變念上的混亂，故可以

10、對約束變元進行更名。使得一個變元在一個公式中具有一種形式出現(xiàn)，即呈自由出現(xiàn)或約元在一個公式中具有一種形式出現(xiàn)，即呈自由出現(xiàn)或約束出現(xiàn)。束出現(xiàn)。 約束變元更名規(guī)則：約束變元更名規(guī)則： （1）對于約束變元可以更名，其更改的變元名稱范）對于約束變元可以更名，其更改的變元名稱范圍是量詞中的指導變元，以及該量詞作用域中所出現(xiàn)的圍是量詞中的指導變元，以及該量詞作用域中所出現(xiàn)的該變元，在公式的其余部分不變。該變元，在公式的其余部分不變。 （2）更名時一定要更改為作用域中沒有出現(xiàn)過的變）更名時一定要更改為作用域中沒有出現(xiàn)過的變元名稱。元名稱。 自由變元代入規(guī)則：自由變元代入規(guī)則： （1）對于謂詞公式中的自由變

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

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

13、的，并記作，并記作A A B B。 定義定義4-5.04-5.0 給定個體域給定個體域E E及公式及公式A A中各謂詞符號的解中各謂詞符號的解釋釋I I，如果，如果A A中個體變元中個體變元x x1 1 ,x ,xn n分別取值分別取值u u1 1 ,u ,un n時時A A真真，則稱，則稱；當；當x x1 1 ,x ,xn n無論取無論取E E中中怎樣的個體怎樣的個體u u1 1 ,u ,un n, , A A在在u u1 1 ,u ,un n處均真處均真，則稱，則稱。4-5 4-5 謂詞演算的等價式和蘊涵式謂詞演算的等價式和蘊涵式 定義定義4-5.34-5.3 如果在某一如果在某一個體域個

14、體域E、某一解釋、某一解釋I下，對下，對于變元的于變元的所有取值狀況所有取值狀況，A的取值的取值都假都假，則稱公式，則稱公式A為為不不的的。公式。公式A不可滿足時也稱不可滿足時也稱A為為。 定義定義4-5.24-5.2 給定個體域給定個體域E，若公式，若公式A在每一解釋在每一解釋I下下均真，那么稱均真，那么稱valid。若公式。若公式A對任何個體域對任何個體域E，均有均有E上永真上永真，則，則稱稱A為為，或稱，或稱A。 定義定義4-5.44-5.4 如果對某一如果對某一個體域個體域E、某一解釋、某一解釋I和變元和變元的的某一取值狀況某一取值狀況，A在在此處此處取值取值真真，則稱公式，則稱公式A

15、為為的的。 定義定義4-5.54-5.5 設謂詞公式設謂詞公式A A中含自由變元中含自由變元x x，設，設t t為一個為一個體項，且體項，且t t中無自由變元為中無自由變元為A A中的約束變元，那么稱中的約束變元，那么稱t t是是的的。 若若A是永真式，那么是永真式，那么對對A中變元可代入中變元可代入的代入實例都是永真的代入實例都是永真式。式。 設設A A，D D為謂詞公式，為謂詞公式，C C為為A A的子公式，且的子公式，且C C D D。若。若B B為將為將A A中子公式中子公式C C的某些出現(xiàn)（未必全部）替的某些出現(xiàn)（未必全部）替換為換為D D后所得的公式，那么后所得的公式，那么A A

16、B B。若公式若公式A A中無自由變元中無自由變元y y，那么，那么， xA(x) xA(x) yA(y),yA(y), xA(x) xA(x) yA(y)yA(y) （1）命題公式的推廣）命題公式的推廣 根據(jù)代入原理，命題演算中的公式可以推廣到謂詞根據(jù)代入原理，命題演算中的公式可以推廣到謂詞公式中。即命題演算中的等價公式表和蘊涵公式表都可公式中。即命題演算中的等價公式表和蘊涵公式表都可以推廣到謂詞演算中使用。以推廣到謂詞演算中使用。 （2）量詞轉化）量詞轉化 設設P (x)(x)表示個體表示個體x x具有性質具有性質P P。于是下面的語句表示。于是下面的語句表示的意義是等價的：的意義是等價的

17、： “ “不是所有的不是所有的 x x 都具有性質都具有性質P P。” “ “存在不具有性質存在不具有性質P P的的 x x 。”于是得到：于是得到： （ x x）P(x) P(x) （ x x） P(x) P(x) 同樣，同樣， “ “不存在具有性質不存在具有性質P P的的 x x 。” “ “所有的所有的 x x 都都不具有性質不具有性質P P。”于是得到：于是得到： （ x x）P(x) P(x) （ x x） P(x) P(x) （3）量詞作用域的收縮與擴張）量詞作用域的收縮與擴張 如果量的詞作用域內有命題（命題內已經無個體如果量的詞作用域內有命題（命題內已經無個體變元，真假值已經確定

18、了），則該命題可以移到量詞變元，真假值已經確定了），則該命題可以移到量詞作用域的外邊。稱之為作用域的外邊。稱之為量詞作用域的收縮。量詞作用域的收縮。 ( x)x) ( A(x)B )( A(x)B ) ( x)A(x)x)A(x) B B ( x)x) ( A(x)B )( A(x)B ) ( x)A(x)x)A(x) B B ( ( x)x) ( A(x)B )( A(x)B ) ( ( x)A(x)x)A(x) B B ( ( x)x) ( A(x)B )( A(x)B ) ( ( x)A(x)x)A(x) B B 量詞作用域的擴張量詞作用域的擴張: ( ( x) A(x) x) A(x)

19、 B B ) ) ( ( x)x) ( (A(x) A(x) B B ) ) ( ( ( x) A(x) x) A(x) B B ) ) ( x)x) ( (A(x) A(x) B B ) ) ( (B B ( x)( A(x)x)( A(x) ) ( x)x) ( (B B A(x)A(x) ) ( (B B ( x)( A(x)x)( A(x) ) ( x)x) ( (B B A(x)A(x) ) 證明（略）證明（略） （4 4）量詞與命題聯(lián)結詞之間的一些等價式）量詞與命題聯(lián)結詞之間的一些等價式 ( x)x) ( ( A(x)B(x) A(x)B(x) ) ( x)A(x)x)A(x)(

20、x)B(x)x)B(x) ( x)x) ( ( A(x)B(x) A(x)B(x) ) ( x)A(x)x)A(x)( x)B(x)x)B(x) （5 5）量詞與命題聯(lián)結詞之間的一些蘊涵式）量詞與命題聯(lián)結詞之間的一些蘊涵式 ( x)A(x)x)A(x)( x)B(x)x)B(x) ( x)x) （A(x)B(x)A(x)B(x)） ( x)x) ( ( A(x)B(x) A(x)B(x) ) ( x)A(x)x)A(x)( x)B(x)x)B(x) ( x) x) ( ( A(x) A(x)B(x)B(x) ) ( ( x)A(x)x)A(x)( ( x)B(x)x)B(x) ) ( x) x

21、) ( ( A(x) A(x) B(x)B(x) ) ( ( x)A(x)x)A(x)( ( x)B(x)x)B(x) ) 定義定義4-7.1 設設A A為為聯(lián)結詞聯(lián)結詞 ，的謂詞公的謂詞公式，式，A A* *為將為將A A中符號中符號，t t，f f， , , 分別換為分別換為，f f，t, t, ， 后所得的公式，那么稱后所得的公式，那么稱A A* *為為A A的的。（6 6）多個量詞的使用）多個量詞的使用 全稱量詞與存在量詞在公式中出現(xiàn)的次序不能隨全稱量詞與存在量詞在公式中出現(xiàn)的次序不能隨意更換。具有兩個量詞的謂詞公式有如下關系：意更換。具有兩個量詞的謂詞公式有如下關系： ( x) x)

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

23、) ( x) A(x,y)x) A(x,y) ( x) x) ( y) A(x,y) A(x,y) ( y) ) ( x) A(x,y)x) A(x,y) ( y) ) ( x) A(x,y)x) A(x,y) ( x) x) ( y) A(x,y) A(x,y)等價式等價式蘊涵式蘊涵式 定義定義4-6.1 4-6.1 公式公式A A稱為公式稱為公式A A的的prenex normal forms)prenex normal forms)，如果，如果A A A A，且，且A A形形如如 Q Q1 1x x1 1QQn nx xn nB B其中其中Q Q1 1，Q Qn n為量詞為量詞 或或 ，

24、B B中無量中無量詞，詞，聯(lián)結詞聯(lián)結詞，B B稱為稱為。當。當B B為合取為合取( (析取析取) )范式時，范式時，A A稱為稱為A A的的。 注意：注意：“一般的范式不要求只含一般的范式不要求只含，”，此定，此定義含蓋了義含蓋了定義定義3-6.23-6.2和和定義定義3-6.33-6.3的內容的內容 。4-6 4-6 前束范式前束范式 定義定義4-7.14-7.1 設設A A為為聯(lián)結詞聯(lián)結詞 ，的謂詞的謂詞公式，公式，A A* *為將為將A A中符號中符號，t t，f f， , , 分別換為分別換為，f f，t, t, ， 后所得的公式，那么稱后所得的公式，那么稱A A* *為為A A的的。 定理定理4-6.14-6.1 （） 對對任意任意謂詞公式均可作出其謂詞公式均可作出其前束范式前束范式，進而作出其，進而作出其前束合取范式前束合取范式或或前束析取范式前束析取范式。 證明方法