第2章謂詞邏輯

1、第2xx謂詞邏輯本章主要內(nèi)容包括謂詞邏輯的基本概念、謂詞邏輯命題的符號(hào)化，謂詞公 式及其真值，謂詞公式的前束范式，重言蘊(yùn)含式與推理規(guī)則等。下面就此作一 簡要介紹。一、謂詞邏輯的基本概念及其符號(hào)化個(gè)體是指可以獨(dú)立存在的客觀實(shí)體，它可以是具體的，也可以是抽象的。具體的特定個(gè)體稱為個(gè)體常量；抽象的、泛指的或在一定范圍內(nèi)變化的個(gè)體稱 為個(gè)體變量，也稱為個(gè)體變?cè)粋€(gè)體變量的取值范圍稱為個(gè)體域(或論域)；在命題中，表示一個(gè)個(gè)體性質(zhì)、特征或多個(gè)個(gè)體之間關(guān)系的成份稱為謂詞；表示具 體性質(zhì)或關(guān)系的謂詞稱為謂詞常量或常謂詞，否則稱為謂詞變量。一般用大寫字母F、G、H等表示謂詞，而用X、Y、Z等表示謂詞變量。表示一

2、個(gè)個(gè)體性質(zhì) 的謂詞稱為一元謂詞：表示多個(gè)個(gè)體之間關(guān)系的謂詞稱為多元謂詞。在命題中除了個(gè)體和謂詞外，有時(shí)還出現(xiàn)表示數(shù)量的詞稱為量詞。我們討論的量詞有兩個(gè)，即存在量詞和全稱量詞。全稱量詞對(duì)應(yīng)于漢語中的每個(gè)”、所有的"、任意的”等，用符號(hào)”表示。存在量詞對(duì)應(yīng)于漢語中的 宥的”、至少有一個(gè)”、存在”等，用符號(hào)“”表示。在個(gè)體域事先給定的情形下，我們只有將個(gè)體域中的每個(gè)具體的個(gè)體代入到F(x)中去確定其真假，才能斷定xF(x)的真假。當(dāng)每一個(gè)個(gè)體都使得 F(x)=1時(shí)，就有 xF(x)=l否則 xF(x)=d對(duì)于 F(x),我們只要發(fā)現(xiàn)個(gè)體域中有(一個(gè) 或多個(gè))個(gè)體使得F(x)=1時(shí)，就有 x

3、F(x)=1;否則(即任何個(gè)體都使得F(x)=O) xF(x)=d在用量詞符號(hào)化命題時(shí)，首先強(qiáng)調(diào)的是個(gè)體域，同一命題在不同的個(gè)體域 內(nèi)可能有不同的符號(hào)化形式，同時(shí)也可能有不同的真值，因此必須先清楚個(gè)體 域，不先確定所考慮的個(gè)體域就不能準(zhǔn)確地表達(dá)原命題的意思。為了解決這一問題，使得符號(hào)化表達(dá)式有確定的含義而不需事先考慮個(gè)體域，我們?cè)诜?hào)化表達(dá)式中增加一個(gè)指出個(gè)體變量的變化范圍的謂詞，這樣就可以不需事先考慮個(gè)體域而能夠準(zhǔn)確地把命題的意思表示出來。這樣我們考慮含有量詞的命題時(shí)，總是在由一切事物構(gòu)成的總體個(gè)體域上考慮問題。當(dāng)符號(hào)化時(shí)，如果命題中含有全稱量詞，則把所增加的指出個(gè)體變化范圍的謂詞（稱為特性

4、謂詞）作為前件，而命題中原有的謂詞作為后件，構(gòu)成一個(gè)蘊(yùn)含式來表示命題的意思：如果命題中含有存在量詞，則用增加的特性謂詞和原命題中的謂詞構(gòu)成的合取式表示命題的意思。在對(duì)給定的自然語言形式的命題進(jìn)行符號(hào)化時(shí)，若是為了確定命題的真值，一般約定在某個(gè)個(gè)體域上進(jìn)行，否則一般在總體個(gè)體域上進(jìn)行，要根據(jù)具體情況而定。若是在總體個(gè)體域上進(jìn)行，則需按上面的說明加上特性謂詞及相應(yīng)的聯(lián)結(jié)詞來表示。二、謂詞公式及其真值定義：設(shè) F 和X 分別為n 元謂詞和n 元謂詞變量，x1， x2， ,xn 是個(gè)體變量，則F（x1， x2， ,xn）和 X（x1， x2， ,xn）都稱為原子公式。定義1謂詞公式是指滿足下列條件的公

5、式:(1)命題公式和原子公式是公式：若A是公式，則 A也是公式：(3)若 A, B 是公式，則(AV B), (AA B), (A-B) (A?B)也是公式：若A是公式，x是個(gè)體變量，則(xAD( xA)也是公式：(5)只有有限次應(yīng)用(1)(4)得到的才是公式。定義2緊跟在 x或x后面并用圓括號(hào)括起來的公式，或者沒有圓括號(hào)括 著的一個(gè)原子公式，稱為相應(yīng)量詞的作用域(或轄域)。把x或?yàn)橹械淖兞拷凶飨鄳?yīng)量詞的指導(dǎo)變量(或指導(dǎo)變?cè)⒆饔米冊(cè)?； 在量詞作用域中出現(xiàn)的與指導(dǎo)變量相同的變量稱為約束變量(或約束變?cè)?；除約束變量外的一切變量稱為自由變量(或自由變?cè)?。在謂詞公式中，自由變量雖然有時(shí)也在量

6、詞的作用域中出現(xiàn)，但不受相應(yīng) 量詞中指導(dǎo)變量的約束，故可把自由變量看作公式中的參數(shù)。另一方面，在謂 詞公式中，一個(gè)變量可以既是約束變量，也是自由變量，后面習(xí)題解析中有相 應(yīng)的習(xí)題。為了避免一個(gè)變量既是自由變量又是約束變量可能引起的混淆，可 對(duì)約束變量改名，使得一個(gè)變量在一個(gè)公式中只呈現(xiàn)一種形式，即僅為自由變 量或僅為約束變量。根據(jù)定義，謂詞公式是一個(gè)關(guān)于自由變量(個(gè)體和命題)、謂詞變量的命題函 數(shù)，其值隨著這些變量的變化而變化。定義3設(shè)A為一謂詞公式，其中含有自由個(gè)體變量 x1, x2, ,x3 / 10l 命題變量P1 P2 , Pm 謂詞公式X1 X2 , Xn,則謂詞公式A可表示成為A(

7、x1 x2 ,xl P1 P2 , Pm X1 X2 , Xn)。如果對(duì)碼，x1 x2 ,xl 分別指定個(gè)體a1 al,對(duì)P1, P2, , Pm分別指定為真值1或0,對(duì)X1, X2, , Xn分別指定常謂詞F1, F2, , Fn,則給公式A作了一組賦值。此時(shí)也稱是對(duì)謂詞公式的一個(gè)解釋。當(dāng)給定 一組賦值后，公式的真值就惟一確定了。定義4如果一謂詞公式在任何賦值下均為真，則該公式稱為重言式（或永真 式、邏輯有效式）；如果任何賦值都使其為假，則該公式稱為矛盾式 （或永假 式）；如果至少有一賦值使其為真，則說公式為可滿足式。有教材也出現(xiàn)了閉式的定義。閉式是指在任何賦值 （或解釋）下，命題的真值 不

8、真即假，不會(huì)發(fā)生真值不確定的情況，也就是說，閉式在任何賦值下均為命 題。設(shè)A, B是謂詞公式，若是重言式，則稱為重言蘊(yùn)含式。重言蘊(yùn)含式A-B,也稱A邏輯蘊(yùn)含B,記作A B,此式稱為邏輯蘊(yùn)含式。若 A?B是重言 式，則稱為重言等價(jià)式，并稱 A和B等值或邏輯等價(jià)，記作A B,此式稱為等 值式或邏輯等價(jià)式。除了由上一章命題邏輯推廣而來的謂詞邏輯等值式外，還有許多謂詞公式 本身特有的等值式（主要與量詞相關(guān)），下面給出一些常見且重要的基本謂詞公式 等值式。定理1設(shè)A(x)是一個(gè)含有個(gè)體變量x的謂詞公式，B是一個(gè)不含自由變量x 的公式，則下面各等值式成立：(1) xA(x) x A(x)(2) xA(x)

9、 x A(x)(3) xA(x)x A(x)(4) xA(x)x A(x)(5) x(A(x)V B) ( xA(x)V B)(6) x(A(x)A B) ( xA(x)A B)(7) x(A(x)V B) ( xA(x)V B)(8) x(A(x)A B) ( xA(x)A B)說明：其中(2)(3)(4)稱為量詞轉(zhuǎn)換律，它說明量詞外面的否定詞可以移至量詞的作用域 內(nèi)，作用域內(nèi)的否定詞也可以移至外面，全稱量詞和存在量詞可以互換：(5)(6)(7)(8)稱為量詞作用域的擴(kuò)張與收縮，它說明了在量詞作用域內(nèi)，如果存在與 量詞約束無關(guān)的公式，在某些情況下，可把這些公式從作用域內(nèi)移出，反之， 亦可移入

10、。定理2設(shè)A(x混一個(gè)含有個(gè)體變量x的謂詞公式，B是一個(gè)不含自由變量 的公式，則下面各等值式成立：(9) x(B-A(x)(B xA(x)(10) x(A(x) - BX xA(x) - B)(11) x(B-A(x)(B xA(x)(12) x(A(x) - BX xA(x) - B)定理3設(shè)A(x), B(x)B是含有個(gè)體變量x的謂詞公式，則下面等值式成立:(13) x(A(x) -B(x"(14) x(A(x)A B(x)(15) x(A(x)V B(x)(16) xA(x)V xB(x)(17) xA(x)A定理4設(shè)A(x,(18) x yA(x,(19) x yA(x,xA

11、(x) 一 xB(x)xA(x)A xB(x)xA(x)V xB(x)x y(A(x)V B(y)x y(A(x)A B(y)xB(x)y)是含有個(gè)體變量x, y的謂詞公式，則y)y xA(x, y)y)y xA(x, y)三、謂詞公式的前束式定理5(約束變量改名規(guī)則)設(shè)人儀柱含有自由變量x而不含有變量y的謂詞 公式，A(y混將A(x)中的自由變量x均改成y后得到的公式。則有：xA(x) yA(y); xA(x) yA(y)改名規(guī)則為：(1)對(duì)約束變量，可以改名。其更改的變量名稱范圍為量詞中的指導(dǎo)變量以 及該量詞作用域中所有出現(xiàn)該變量的地方，公式的其余部分不變。(2)改名時(shí)一定要更改為作用域中

12、沒有出現(xiàn)過的變量名稱。定理6(自由變量改名規(guī)則設(shè)x是A(x, z)中僅自由出現(xiàn)的個(gè)體變量，y不 出現(xiàn)在A (x, z)中，則A(x, z) A(y, z),且zA(x, z)zA(y, z),zA(x, z)zA(y, z)改名規(guī)則(也稱為代入規(guī)則)為：(1)謂詞公式中的自由變量可以更改，更改時(shí)需對(duì)公式中出現(xiàn)該自由變量的 每一處都進(jìn)行更改。(2)用以更改的變量與原公式中所有變量的名稱不能相同。定義5設(shè)B是一個(gè)不含量詞的謂詞公式，i為或。如果公式A 1xlA2x2, nxnB,則41xlA2x2, nxnB稱為公式A的前束范式。當(dāng)n=0時(shí)，有A B, B也稱為A的前束范式定理70束范式存在定理)

13、任意一個(gè)謂詞公式A都存在與它等值的前束范 式。說明：謂詞公式的前束范式并不一定惟一，所以不能象命題公式的主范式那樣直 接用于解決問題，它只是將謂詞公式形式的范圍縮小了一點(diǎn)，能夠給研究工作 提供一定的方便。四、重言蘊(yùn)含式與推理規(guī)則定理8設(shè)A(x), B(x)t勻?yàn)楹凶杂勺兞?，x的任意的謂詞公式，則有(20) xA(x)V xB(x) x(A(x) V B(x)(21) x(A(x)A B(x)xA(x)AxB(x)(22) x(A(x) -B(x)xA(x)-xB(x)(23) x(A(x) -B(x)xA(x)-xB(x)(24) x(A(x)?B(x)xA(x)?xB(x)定理9設(shè)A(x)

14、為含有自由變量x的任意的謂詞公式，則有(25) xA(x) A(x)(26)A(x) xA(x)(27)xA(x) xA(x)定理10 設(shè) A(x,y)為含有自由變量x, y的任意的謂詞公式，則有(28)yA(x,y)y yA(x,y)(29)yA(x,y)y xA(x,y)(30)yA(x,y)x yA(x,y)(31)yA(x,y)xA(x, x)(30)xA(x, x)yA(x, y)在推理過程中，上面給出的一些等值式和重言蘊(yùn)含式可以作為推理依據(jù)使用，并分別將推理過程中使用的等值式和重言蘊(yùn)含式分別稱為E規(guī)則和I規(guī)則。除此之外，常用的一些推理規(guī)則還有：(1)前提引入規(guī)則：也稱為P規(guī)則，即前提在推理過程中隨時(shí)可引入使用。.(2)結(jié)論引用規(guī)則：也稱為T規(guī)則，即在推理過程中產(chǎn)生的中間結(jié)論可以作為后面推理的前提 使用。(3)全稱量詞規(guī)定規(guī)則(US):