第二章謂詞邏輯

離散數(shù)學DiscreteMathematics倪子偉ComputerScienceDepartmentXiamenUniversitwni@在命題演算中,簡單命題作為基本研究單位,對它不再進行分解。不考慮命題之間的內(nèi)在聯(lián)系,只考慮一個命題的真假。這樣就忽略了命題豐富的內(nèi)涵。有時甚至無法判斷一些簡單而又常見的推理。如典型的邏輯三段論:例凡人都是要死的。 p

Socrates是人。 q 所以Socrates是要死的。 r則p∧q

r表示這個推理。直觀上看,推理正確,r是前題p和q的有效結論。但推理的形式結構不是重言式,這反映了命題邏輯的局限性。第二章

一階謂詞(predicate)邏輯原因是只將p,q,r看成獨立的命題,不考慮其內(nèi)在聯(lián)系。不能對簡單命題自身的內(nèi)部特征作進一步的分析,

無法揭示前提和結論在形式結構方面的聯(lián)系,因此就不可能認識到這種推理的形式和規(guī)律,這就使得命題邏輯的適用面比較狹窄。例熊貓是動物。p 長頸鹿是動物。q它們是兩個簡單命題,只能用兩個不同的符號來表示,但這樣的符號不能揭示這兩個命題的共性。因此,將命題演算擴展成一階謂詞演算,對簡單命題的成分、結構和簡單命題間的共同特性等作進一步的分析,這正是一階謂詞邏輯所要研究的內(nèi)容。在一階邏輯中,簡單命題被分解為個體詞(主語)與謂詞(謂語)兩部分。一.謂詞、個體詞和個體域定義可以獨立存在的客體稱為個體(individual)。個體可以是一個具體的事物,或是一個抽象的概念。例計算機、熊貓、圍棋、自然數(shù)、定理、思想、愛國主義等都可以充當個體詞。表示具體的、特指的個體詞,稱為個體常項,常用小寫字母a,b,c…來表示。表示抽象的、泛指的、或在一定范圍內(nèi)變化的個體詞,稱為個體變項,常用小寫字母x,y,z…來表示?！?.1一階First-order邏輯的基本概念稱個體變項的取值范圍為個體域(Domain)或論域。個體域可以是有窮集合或無窮集合。最大的個體域是包含宇宙全體事物的個體域,稱為全總個體域。本書若無特別聲明時,個體域均指全總個體域。陳述句是由主語和謂語兩部分組成,主語通常是個體。定義用來刻劃一個個體的性質(zhì)或多個個體之間關系的詞稱為謂詞。謂詞常用大寫字母F,G,H,…來表示。稱表示有具體性質(zhì)或關系的謂詞,稱為謂詞常項,

否則稱為謂詞變項。謂詞都用F,G,H,…表示,根據(jù)上下文的具體情況確定是謂詞變項還是常項。謂詞中包含個體的數(shù)目稱為謂詞的元數(shù)。含n(n≥1)個個體的謂詞稱為n元謂詞。一元謂詞是描述個體性質(zhì)的,n(n≥2)元謂詞刻畫個體之間“關系”的。用P(x1,x2,…,xn)抽象地表示n(n≥1)元謂詞,它是以個體域為定義域,以{0,1}為值域的n元函數(shù),它不是命題。第一章的邏輯聯(lián)結詞均是謂詞。例將下列命題符號化:(1)熊貓是動物。(2)上海位于南京與杭州之間。(3)2是偶數(shù)且是素數(shù)。解(1)A(x):x是動物,這里x是個體變項,它可在動物范圍內(nèi)任意取值。b:熊貓,b是個體常項, 則命題可符號化為A(b)或A(熊貓)。(2)B(x,y,z):x位于y與z之間。A:上海,b:南京,c:杭州,則命題可符號化為B(a,b,c)或為B(上海,南京,杭州)。(3)E(x):x是偶數(shù),P(x):x是素數(shù),a:2,則命題可符號化為E(a)∧P(a)或E(2)∧P(2)。一般地,一個由n個個體和n元謂詞所組成的命題 可表示為P(a1,a2,…,an),其中 P表示n元謂詞,a1,a2,…,an分別表示n個個體。a1,a2,…,an的排列次序通常是重要的。

例中

B(a,b,c)不同于B(b,a,c)。例中A(x),B(x,y,z),E(x)實際上是個體變項x,y,z的簡單函數(shù),它們均以{0,1}為值域。由有限個簡單命題函數(shù)以及邏輯聯(lián)結詞組成的命題形式稱為復合命題函數(shù),仍以{0,1}為值域。簡單命題函數(shù)和復合命題函數(shù)統(tǒng)稱為命題函數(shù)。例(P(x)∨Q(y,z))R(x,z)是命題函數(shù)。將不帶個體變項的謂詞稱為0元謂詞。命題邏輯中的命題常項與變項都可用0元謂詞表示,因而可把命題看作是謂詞的特殊情況。命題邏輯中的連結詞、等值式、推理定律等均可在一階邏輯中使用,只是要注意謂詞邏輯的特殊性就是了。例

L(a,b)為0元謂詞。當L仍為變項時,它仍為命題變項。

一旦L的意義明確后,它就變成命題了。現(xiàn)在考慮如下形式的命題在一階邏輯中符號化的問題: (1)所有的活人都呼吸。

(2)有的人吸煙。在以上兩個命題中,除了有個體詞和謂詞外,還有表示數(shù)量的詞(所有的,有的)。在命題中分析出個體和謂詞后,仍不足以表達邏輯三段論和日常生活中的各種問題。問題在于“所有的”和“有些”這種全稱量詞和特稱量詞還沒有分析出來,因此必須引入量詞。定義稱表示數(shù)量的詞為量詞(quantifier)。量詞分為兩種:(1)

全稱(universal)量詞“”對應常用語言中的“所有”、“任意”、“一切”、“每一個”等。 x表示對個體域中的所有個體,x稱為全稱性變項, xF(x)表示個體域里所有個體都有性質(zhì)F。(2)

存在(existence)量詞“”對應常用語言中的“存在著”、“有一個”、“有些”、“至少存在一個”等。

x表示存在個體域中的個體,x稱為存在性變項, xA(x)表示存在著個體域中的個體具有性質(zhì)A。量詞也可看作是對個體詞所附加約束的詞?？紤]前面兩個命題的符號化問題。使用量詞將命題符號化后真值與所用個體域有關。

(I)個體域為人類集合D。

(1)符號化為:xF(x),其中F(x):x要呼吸。命題為真。(2)符號化為:xG(x):其中G(x):x吸煙。命題為真。本個體域只有人而無其他事物,以上兩個命題均討論人的性質(zhì),所以命題符號化形式很簡單。(II)個體域為全總個體域D’。若將(1)仍符號化為:xF(x)的形式,其涵義變成了“宇宙間的一切事物都要呼吸”,這與原命題不是一回事。若將(2)仍符號化為:xG(x)的形式,表示“宇宙間有的事物吸煙”,也沒有表達有的人吸煙。在D’中要想將(1),(2)正確符號化,必須將人從中分離出來,就要引入新的謂詞,稱這樣的謂詞為特性謂詞。而對個體變化的真正取值范圍,用特性謂詞加以限制。這里特性謂詞M(x):x是人。在個體域D’的情況下,F(x)與G(x)的涵義同(I)。

(1)與(2)可作如下敘述:(1)對宇宙間的一切事物,如果它是人,則它要呼吸。

(2)在宇宙間存在會吸煙的人。則(1)應符號化為x(M(x)F(x))。仍為真命題。對全稱量詞后的特性謂詞應作為蘊涵式的前件;

或前、后件同真,或前件假(x非人時)。蘊含式總是真。(2)應符號化為x(M(x)∧G(x))。仍為真命題。對存在量詞后的特性謂詞應作為合取式的一項。若對全稱量詞的特性謂詞作為合取而加入,就會將各種個體不加區(qū)分地混為一體,從而得出不正確的結論。在一階邏輯中,使用量詞時應注意下列要點:(1)在不同的個體域中,命題符號化的形式可能不同,命題的真值也可能會改變。(2)如果個體域未做聲明,一律使用全總個體域。(3)多個量詞同時出現(xiàn)時,不能隨意顛倒它們的順序,否則后會改變原命題的含義。(4)在引入特性謂詞后,全稱量詞后特性謂詞為蘊涵式,存在量詞后的特性謂詞應作為合取式。(5)個體域和謂詞的涵義確定后,n元謂詞要轉化為命題至少需要n個量詞。量詞本身并不是一個獨立的邏輯概念,當個體域是有限集時,它可以用聯(lián)結詞替代。設個體域D={a1,a2,…,an},則包含有全稱量詞的謂詞公式xA(x)表示a1有性質(zhì)A,a2有性質(zhì)A,…,an有性質(zhì)A。因此

xA(x)A(a1)∧A(a2)∧…∧A(an)因為A(ai)(i=

1,2,…,n)中都沒有個體變項,也沒有量詞,所以這一合取式實際上是命題演算中的命題公式。當個體域為有限集時,全稱量詞可看作是合取聯(lián)結詞的推廣。存在量詞的謂詞公式xA(x)表示a1有性質(zhì)A, 或者a2有性質(zhì)A，…,或者an有性質(zhì)A。因此

xA(x)A(a1)∨A(a2)∨…∨A(an)。當個體域為有限集時,存在量詞可看作是析取聯(lián)結詞的推廣。當個體域為有限時,實際上是將一階謂詞的公式轉化為命題公式,即量詞可以省略。注意當個體域為無限時,則不能轉化。當個體域為無限時,全稱量詞“相當于”無限個合取聯(lián)結詞的作用,一般說來,這時的謂詞公式不能轉換成命題公式。當個體域為無限時,存在量詞“相當于”無限個析取聯(lián)結詞的作用,這時的謂詞公式一般也不能轉換成命題公式如果一個謂詞公式中包含有多個量詞,則可以從里到外地用上述方法將量詞逐個消去,因而使公式轉換成命題演算中的命題公式。但當個體域中元素很多,甚至為無限集時,此法就變得不實際甚至不可能了。為了說明量詞與否定聯(lián)結詞關系,我們約定, 出現(xiàn)在量詞之前的否定,不是否定該量詞,

而是否定被量化了的整個命題。在§2.3中我們將進一步研究量詞轉化律。例我為人人,人人為我。解設S(x,y):x為y服務,用i表示我。命題表示為:

xS(i,x)∧xS(x,i)例勇敢者未必都是成功者。解設B(x):x勇敢,S(x):x是成功者。命題表示為:

x(B(x)S(x))或x(B(x)∧S(x))例并非一切勞動都能用機器代替。解設L(x):x是一種勞動,M(x):x是一種機器,

R(x,y):x被y代替。命題表示為:

x(L(x)

y(M(y)∧R(x,y)))在引入個體詞、謂詞和量詞后,數(shù)學上的所有概念和定理都可以表示為謂詞邏輯的命題, 因而可以用數(shù)理邏輯中的方法來研究數(shù)學的內(nèi)容。例數(shù)學分析中函數(shù)f(x)在點a連續(xù)的定義為: 對任意的>0,存在一個>0,使得對所有x,

若|x–a|<,則|f(x)–f(a)|<,符號化此定義。解令R(x):x是實數(shù),G(x,y):x大于y。

((R()∧G(,0))

(R()∧G(,0)∧

x((R(x)∧G(,|x–a|))G(,|f(x)–f(a)|))))。有了謂詞的概念和符號表示,就可以更深刻地刻劃周圍的事物。任一命題都可以通過引入具有相應含義的謂詞(個體詞視為常項)來表示, 或認為一個命題是沒有個體變項的零元謂詞。謂詞邏輯是命題邏輯的推廣, 命題邏輯是謂詞邏輯的特殊情形。從而命題邏輯的很多概念和規(guī)則,都可推廣到謂詞邏輯中延用。然而,在謂詞邏輯中出現(xiàn)了個體變項、謂詞和量詞等新概念,給我們的討論帶來復雜性,尤其是個體域常是無限的,這加大了處理難度。一個簡單又深刻的例子是:命題邏輯里,一個公式不難判斷它是否是重言式,因為總可以用真值表進行判斷。但在謂詞邏輯里,就沒有一般的能行算法,來判斷任一公式是否普遍有效(或重言)。1936年Turing證明了:當個體域D是無限集時,對于一階邏輯,(公式的重言性和矛盾性的)判定問題是不可解的。困難就在于D是無限集以及對謂詞設定的任意性.然而,并不排除謂詞公式有子類(如命題邏輯)是可判定的。為使符號化更為準確和規(guī)范地進行謂詞演算和推理,在本節(jié)給出一階邏輯合適公式的概念。為此先給出本書在一階邏輯部分所用的字母表。定義2.1字母表定義如下:

(1)個體常項:a,b,c,…,ai,bi,ci,…,i≥1;

(2)個體變項:x,y,z,…,xi,yi,zi,…,i≥1;(3)函數(shù)符號:f,g,h,…,fi,gi,hi,…,i≥1;

(4)謂詞符號:F,G,H,…,Fi,Gi,Hi,…,i≥1;

(5)量詞符號:,;

(6)聯(lián)結詞符號:,∧,∨,,;

(7)括號與逗號:(,),,?！?.2一階謂詞公式及解釋定義2.2

項的遞歸定義:(1)個體常項和變項是項。(2)若(x1,x2,…,xn)是任意的n元函數(shù),t1,t2,…,tn是

任意的n個項,則(t1,t2,…,tn)是項。(3)只有有限次地應用(1),(2)形成的符號串才是項。▋根據(jù)定義,常項,變項以及由它們生成的各種函數(shù)及復合函數(shù)都叫做項。例

a,b,x,y,z,f(x,y)=xy,g(x,y)=x2+y2,h(x,y)=2xy都是項。

f(x,g(x,y))=x(x2+y2),g(f(x,y),h(x,y))=x2y2+(2xy)2等也都是項。定義2.3

設R(x1,x2,…,xn)是任意的n元謂詞,t1,t2,…,tn是任意的n個項,則稱R(t1,t2,…,tn)是原子公式。▋1元謂詞F(x),G(y),2元謂詞H(x,y)等都是原子公式。有了原子公式就能定義合式公式了。

定義2.4合式公式也稱謂詞公式,簡稱公式的遞歸定義:(1)原子公式是合式公式(Well

formedformula,

WFF)。(2)若A是合式公式,則(A)也是合式公式。(3)若A,B是合式公式,則(A∨B)、(A∧B)、(A

B)、(A

B)也是合式公式。

(4)若A是合式公式,則xA和xA也是合式公式。(5)只有有限次地應用(1)-(4)形成的符號串才是合式公式.謂詞公式是由原子謂詞公式、命題聯(lián)接詞、量詞以及圓括號按照上述規(guī)則組成的一個符號串。我們本章討論的是一階謂詞邏輯,限定量詞僅作用于個體變項,不允許量詞作用于命題變項、謂詞變項和函數(shù)變項,也不討論謂詞的謂詞(二階)。個體變項有自由free變項和約束bound變項之分。定義2.5

在公式xA(x)和xA(x)中,稱x為指導變項,A為相應量詞的轄域(scope)。

在x和x的轄域中,

x的所有出現(xiàn)都稱為約束(bound)出現(xiàn),

A中不是約束出現(xiàn)的其它變項均稱為是自由出現(xiàn)的。▋公式中約束出現(xiàn)的變項是約束變項,自由(free)出現(xiàn)的變項是自由變項。 可把自由變項看作是公式中的參數(shù)。若量詞后有括號,在括號內(nèi)的公式即為此量詞的轄域。若量詞后無括號,則量詞后最短的公式為此量詞的轄域從約束變項的概念可以看出,P(x1,x2,…,an)是

n元謂詞,它有n個相互獨立的自由變項, 若對其中k個變項進行約束,則成為n–k元謂詞。定義2.6

設A為任意一公式,若A中無自由出現(xiàn)的個體變項,

則稱A是封閉的公式,

簡稱閉式。例

xP(x,y,z)是二元謂詞,

xyQ(x,y,z)是一元謂詞。例x(x

<

88∧x是奇數(shù)),是閉式, 個體變項x是約束變項。這已經(jīng)不是一個命題函數(shù),而是一個命題。它相當于說“存在有小于88的奇數(shù)”,這是一個真命題。例y(如果y是辣椒,則y是紅的),是閉式,個體變項y是約束變項。這也不是一個命題函數(shù),而是一個命題。對于其中的個體變項不需要再作代替,它的含義是確定的,它斷定“一切辣椒都是紅的”, 這當然是一個假命題。xy(F(x)∧G(y)

H(x,y))是閉式。而F(x)∧G(y),

F(x)y

(G(y)

H(x,y))等都不是閉式要想使含n(n≥1)個自由出現(xiàn)的個體變項的公式變成閉式,

至少要加n個量詞。

例

要使(F(x)G(x,y)∧L(x,y,z))成為閉式,可加3個量詞,如x(F(x)y(G(x,y)∧z

L(x,y,z)))就已成為閉式。例(1)xP(x)∧Q(y),公式中的個體變項x是約束變項,

y是自由變項,的轄域是P(x)。(2)x(A(x)∨yB(x,y)),

x的轄域是A(x)∨yB(x,y),

y的轄域是B(x,y);

x和y兩者的所有出現(xiàn)都是約束出現(xiàn)。(3)x(A(x)B(x)),

x的轄域是A(x)B(x), x的所有出現(xiàn)都是約束出現(xiàn)。(4)xA(x)B(x),

x的轄域是A(x),

x在B(x)中是自由出現(xiàn)。注意區(qū)別(3)和(4)。有時同一個個體變項在同一個公式中,既有約束出現(xiàn)又有自由出現(xiàn)。為避免混淆,使一個變項在同一個公式中不同時是約束的又是自由出現(xiàn)的,可采用下面兩條規(guī)則任一個公式的約束變項的符號是無關緊要的。對約束變項進行換名(replacement)時須遵守如下的

換名原則:將公式A中某量詞轄域中,某約束變項的所有出現(xiàn)及相應的指導變項,改成該量詞轄域中未曾出現(xiàn)過的個體變項符號(最好是公式中未曾出現(xiàn)過的符號),

A中其余部分不變,

則所得公式A’與A等值。對公式中自由變項的更改叫做代替(substitution)。代替規(guī)則:將公式A中某自由出現(xiàn)的個體變項的所有出現(xiàn),用A中未曾出現(xiàn)過的個體變項符號代替,

A中其余部分不變,

則所得公式A’與A等值。(1)對于謂詞公式中的自由變項,可以代替,代替時須對該自由變項的所有出現(xiàn)同時進行代替。(2)代替時所選用的變項符號與原公式中所有變項的符號不能相同。下表列出了換名規(guī)則與代替規(guī)則的主要區(qū)別:區(qū)別表

換名規(guī)則 代替規(guī)則 對象

約束變項 自由變項 范圍

一個量詞及其轄域內(nèi)

整個公式 結果 只能換名為另一變項,可以代以另一變項。

不能換名為個體常項,

還可代入個體常項, 換名后公式的含義 公式由具有普遍意

不變。 義變成僅對該個體

常項有意義。

例6.2.4x(Q(x)R(x,y))∨zP(x,z)解用約束變項的換名規(guī)則得: u(Q(u)R(u,y))∨zP(x,z); 或用自由變項得代替規(guī)則得: x(Q(x)R(x,y))∨zP(u,z)。 但下面的改名都是不對的。(1)u(Q(u)R(x,y))∨zP(x,z)(2)x(Q(u)R(x,u))∨zP(x,z)(3)u(Q(u)R(u,y))∨zP(u,z)(4)y(Q(y)R(y,y))∨zP(x,z)當多個量詞連續(xù)出現(xiàn),它們之間無括號分隔時,約定從左到右的次序讀出。后面的量詞在前面量詞的轄域之中,且量詞對變項的約束與量詞的次序有關。 注意:詞的次序不能顛倒,否則將與原命題意義不符。例yx(x

<

(y–2)),x,y的個體域為實數(shù)集。

y的轄域為x(x

<

(y–2)),

x的轄域為x

<

(y–2)。

表示任何實數(shù)y均存在有實數(shù)x,x

<

y

–

2,是真命題。將量詞次序改為xy(x

<

(y–2)),表示存在一個實數(shù)x,對任何實數(shù)y均有x<y–2,是假命題一般情況下,一個一階邏輯公式中含有個體常項、變項(自由出現(xiàn)的或約束出現(xiàn)的),函數(shù)的常項、變項,謂詞的常項、變項等。若對各種變項都 指定特殊的常項去代替,就構成公式的一個解釋, 有時使其成為命題,有確定的真值。定義2.7謂詞公式A的每一個解釋I由下面4部分組成:(1)非空的個體域D;

(2)D中一部分特定元素

(用來解釋個體變項);(3)D上一些特定函數(shù)(用來解釋出現(xiàn)的函數(shù)變項);

(4)D上一些特定謂詞(用來解釋謂詞變項)。例xy(F(x)∧F(y)∧G(x,y)

H(f(x,y),g(x,y))), 這是一個一階邏輯中的合式公式,沒有什么意義。但當我們給這個符號串一個解釋,

使它就具有惟一的真值,變成一個命題了。解釋1

個體域D:全總個體域;F(x):x是實數(shù);G(x):xy;H(x,y):x>y;f(x,y)=x2+y2;g(x,y)=2xy.在解釋1下,本公式涵義為:對于任意的x,y,若x是實數(shù),y是實數(shù),并且xy,則x2+y2>2xy。這是真命題。解釋2只將H(x,y)改為x<y,其他情況同解釋1,則得到的命題為假命題。

1.有的公式在具體的解釋中真值確定,即變成了命題。有的公式在某些解釋中真值仍然不能確定,仍不是命題。

2.

閉式(不包含自由變項)在任何解釋中都成為命題。閉式中每個個體變項都受量詞的約束,因而在具體解釋中總表達一個意義確定的語句,即真命題或假命題。3.

不是閉式的公式在某一解釋中,可能成為命題;也可能不能成為命題。例x(P(x)∨Q(x)),

解釋:

個體域是{1,2},P(x):x=1,Q(x):x=2, 求公式的真值。解

x(P(x)∨Q(x))

(P(1)∨Q(1))∧(P(2)∨Q(2))

但P(1)為1,Q(1)為0,P(2)為0,Q(2)為1。 所以x(x=1∨x=2)

(1∨0)∧(0∨1)

1例G(x,y)是二元謂詞,

解釋:指定D為實數(shù)域,G(x,y)表示“x大于y”, 則G有了確定的含義,但還不是命題。如再指定為3.14156,e為2.71828, 則G(,e)就是命題“3.14156大于2.71828”,其真值為1。例S(x)表示x2+1=0,若x的個體域為實數(shù),則這是一個矛盾式。若x的個體域為復數(shù),則除了S(i)和S(–i)是真值為1的命題外,其余情形均為真值為0的命題。例若個體域為{a,b,c},消去xP(x)∨xP(x)中的量詞:解

xP(x)∨xP(x) (P(a)∧P(b)∧P(c))∨(P(a)∧P(b)∧P(c))例設個體域為{0,1},將x(yF(x,y)∨G(x)) 轉換成不含量詞的形式:解

x(yF(x,y)∨G(x))

x((F(x,0)∧F(x,1))∨G(x))

((F(0,0)∧F(0,1))∨G(0))∨((F(1,0)∧F(1,1))∨G(1))同在命題邏輯一樣,在一階邏輯中也將公式分類為:定義2.8

設A為一公式,若A在任何解釋下都為真,

則稱A為永真式(或稱邏輯有效式)。如果A在任何解釋下都是假的,則稱A為矛盾式(或稱永假式)。若至少存在著一種解釋使A為真,則稱A是可滿足式.▋永真式一定是可滿足式,但反之不然。一般情況下,由于公式的復雜性和解釋的多樣性,到目前為止,還沒有一個可行的算法,用來判斷某一公式是可滿足的,還是不可滿足的(矛盾式)。/*Open定義2.9

設A0是含命題變項p1,p2,…,pn的命題公式,A1,A2,…,An是n個謂詞公式,用Ai(1≤i≤n)處處代替A0中的pi,所得的公式A稱為A0的代換實例。例

F(x)G(x),xF(x)yG(y)等是pq的代換實例;F(x,y)∧xG(x),xF(x)∧yG(y)等都可以 作為p∧q的代換實例。可以證明,重言式的代換實例均為永真式,

而矛盾式的代換實例均為矛盾式。例2.9

判斷下列公式中,哪些是永真式,哪些是矛盾式?(1)xF(x)(xyG(y)xF(x)),

解:

這是p(qp)的代換實例,

而p(qp)p∨(q∨p)

1

所以(1)是永真式。(2)((xF(x)∨yG(y))∧yG(y))

xF(x),解:

這是(p∨q)∧qp的代換實例,

由I5析取三段論可知,(p∨q)∧qp是重言式,

所以(2)是永真式。

(3)(F(x)G(x,y))∧G(x,y),解:

這是(pq)∧q的代換實例,

(pq)∧q(p∨q)∧pp∧q∧q

0. 所以(3)是矛盾式。(4)(xF(x)∨xF(x))

(yG(y)∨yG(y)).解:

這是(p∨p)

(q∨q)的代換實例, (p∨p)

(q∨q)111是重言式,

所以(4)是永真式。對于不是重言式和矛盾式的代換實例,判斷它們是否為永真式或矛盾,確實不是易事。對特殊簡單公式可判斷例2.10

討論下面公式的類型:A:xF(x)xF(x),

證:設I為任意一個解釋,其個體域為D。若bD,使得F(b)為假, 則前件xF(x)為假,A為真。若xD,F(x)均為真, 則前件xF(x)和后件xF(x)都為真,從而A也為真。由I的任意性,所以A是永真式。例2.10

討論下面公式的類型:B:xyF(x,y)xyF(x,y),證:取解釋I如下:個體域為自然數(shù)集N,F(x,y):x≤y。在I下,

B的前、后件(令x=0)均為真,所以B不會是矛盾式。再取解釋II如下:個體域為自然數(shù)集N,F(x,y):x=

y。在II下,

B的前件為真,后件為假,故B假,這又說明B不會是永真式。綜上所述,B是非永真式的可滿足式。與命題邏輯一樣,在一階邏輯的演算及推理過程中,一些重要的永真等價式起著很重要的作用定義2.10

設A,B是一階邏輯中任意二公式, 若A

B是永真式,則稱A和B是等值的,記作AB,稱AB為等值式。

▋定義設A,B是一階邏輯中任意二公式, 若A

B1,則稱A蘊含B,記作AB。

▋當個體域是有限集合的時候,原則上來說,可以用真值表法來驗證一個公式是否為永真公式,

或者驗證兩個公式是否等值?！?.3一階邏輯等值式與前束范式包含有量詞而不包含自由變項的謂詞公式, 實際上也是命題演算的公式。由于重言式的代換實例都是永真式,第一章P10和P24的24個等值式的代換實例都是一階邏輯中的等值式。因此對命題演算中的所有重言式, 若將其中每一個命題變項分別用這些公式去作代入, 便可得到謂詞演算中的永真公式。例在P∨P和(PQ)(P∨Q), 若用xP(x)代替P,用xQ(x)代替Q,得到永真公式:

xP(x)∨xP(x), (xP(x)

xQ(x))(xP(x)∨xQ(x))。

下面給出一階邏輯中一些基本的等值式。

其中的A(x),B(x)均為有x自由出現(xiàn)的任意公式。

1.

在有限個體域D={a1,a2,…,an}中消去量詞等值式全稱量詞可看作是合取聯(lián)結詞的推廣。存在量詞可看作是析取聯(lián)結詞的推廣。

(1)

xA(x)A(a1)∧A(a2)∧…∧A(an)(2)xA(x)A(a1)∨A(a2)∨…∨A(an)。

2.

量詞否定等值式(量詞轉換律):反映量詞的特性以及量詞與聯(lián)結詞之間的關系。

(3)

xA(x)

xA(x)

/*與對偶

(4)xA(x)

xA(x)

當個體域為有限集D={a1,a2,…,an}, 量詞轉換律證明如下:Proof:

xA(x)

(A(a1)∧A(a2)∧…∧A(an))

A(a1)∨A(a2)∨…∨A(an)

xA(x)Proof:

xA(x)

(A(a1)∨A(a2)∨…∨A(an))

A(a1)∧A(a2)∧…∧A(an)

xA(x)對于無窮個體域,可作語義解釋如下:如果x

A(x)為真, 則可以把x

A(x)理解成“命題xA(x)是假的”, 而它與“存在某些x,A(x)不是真的”意思等價。 即xA(x)

xA(x)。類似地,如果x

A(x)為真,則x

A(x)表示 “至少存在一個x,能使A(x)為真”這個命題為假。 它等價于“不存在任何一個x能使A(x)為真”, 或者“對于所有的x,A(x)是假的”。即 xA(x)

xA(x)量詞轉換律說明:(1)在謂詞演算中只要有一個量詞就夠了。(2)量詞前面的否定符號可深入至量詞轄域內(nèi), 但與此同時必須將存在量詞和全稱量詞作對換。其他常見的等值關系式和蘊含關系式列于下表中, 各式中的B表示任意一個不含有約束變項x的公式。

3.量詞轄域收縮與擴張律,B中不含有約束變項x:(5-1)x(A(x)∨B)

xA(x)∨B /*∨可交換(5-2)x(A(x)∧B)

xA(x)∧B /*∧可交換(5-3)x(A(x)B)

xA(x)B(5-4)x(BA(x))B

xA(x)(6-1)x(A(x)∨B)

xA(x)∨B /*∨可交換

(6-2)

x(A(x)∧B)

xA(x)∧B /*∧可交換

(6-3)x(A(x)B)

xA(x)B(6-4)x(BA(x))B

xA(x)例2.13以5-2前的公式為基礎證明5-3和5-4證5-3

x(A(x)B)

x(A(x)∨B) /*E12蘊含等值式

xA(x)∨B /*公式5-1轄域收縮

xA(x)∨B /*量詞否定轉換

xA(x)B /*E12蘊含等值式證5-4

x(BA(x))

x(B∨A(x) /*E12蘊含等值式

B∨xA(x) /*公式5-1轄域收縮

B

xA(x) /*E12蘊含等值式同理可證6-3和6-4

4.量詞分配等值式(7)

x(A(x)∧B(x))

xA(x)∧xB(x)(8)x(A(x)∨B(x))

xA(x)∨xB(x)5.量詞分配蘊涵律P53 (9)

xA(x)∨xB(x)

x((A(x)∨B(x))(10)

x(A(x)∧B(x))

xA(x)∧xB(x)注意:

x(A(x)∨B(x))

xA(x)∨xB(x) xA(x)∧xB(x)

x(A(x)∧B(x))

不能對∨分配,不能對∧分配。(11)x(A(x)B(x))

xA(x)

xB(x)(12)x(A(x)B(x))

xA(x)

xB(x)例設個體域為自然數(shù)集合N,

O(x)表示“x是奇數(shù)”,E(x)表示“x是偶數(shù)”。(1)x(O(x)∨E(x))的涵義為: 任意的自然數(shù)不是奇數(shù)就是偶數(shù),這是真命題。(2)而xO(x)∨xE(x)的涵義為:所有的自然數(shù)都是奇數(shù)或所有的自然數(shù)都是偶數(shù),這是假命題。xA(x)∨xB(x)

x((A(x)∨B(x))(3)xO(x)∧xE(x)的涵義為:存在奇數(shù)的自然數(shù), 也存在偶數(shù)的自然數(shù),這是真命題。(4)而x(O(x)∧E(x))的涵義為:要求存在一個自然數(shù), 它既是奇數(shù),同時又是偶數(shù),這是假命題。 x(A(x)∧B(x))

xA(x)∧xB(x)例2.11設個體域為D={a,b,c},消去下列公式中的量詞:(2)x(F(x)∧G(y));解

x(F(x)∧G(y))

xF(x)∧G(y)/*先將量詞轄域收縮

(F(a)∨F(b)∨F(c))∧G(y)(3)x(F(x)

yG(y));解x(F(x)

yG(y))

xF(x)

yG(y)/*

先將量詞轄域收縮(5-3)

(F(a)∨F(b)∨F(c))

G(a)∨G(b)∨G(c))和基本的等值關系式和蘊涵關系式表

E21

x(A(x)B)

xA(x)

B E22

x(A(x)B)

xA(x)

B E23

x(AB(x))A

xB(x) E24

x(AB(x))A

xB(x) E25

x(A(x)B(x))

xA(x)

xB(x) I13

xA(x)

xB(x)

x(A(x)B(x)) I14

x(A(x)B(x))

xA(x)

xB(x)例證明E25

x(A(x)B(x))

xA(x)

xB(x)證明

x(A(x)B(x))

x(A(x)∨B(x))

xA(x)∨xB(x)(8)

xA(x)∨xB(x)

xA(x)

xB(x)若A不含有個體變項,則 xAA; xAA。在謂詞公式中,若有多個量詞,那么量詞的次序直接關系到命題的意義。兩個例外,即相同量詞間的次序是可以任意交換的:

E26

xyA(x,y)

yxA(x,y) E27xyA(x,y)

yxA(x,y)“對于所有的x和所有的y,A(x,y)均成立”與 “對于所有的y和所有的x,A(x,y)均成立” 其含義是完全相同的,故E26正確。類似地,E27正確。例設個體域為鞋子集合,S(x,y)表示:“x與y成雙”。yxA(x,y)表示:“存在一只鞋子,它與每只鞋都成雙”,這顯然是假命題。xyA(x,y)表示:“每只鞋都可找到一只鞋與之成雙”,這是真命題。此例子說明改變不同量詞間的位置往往改變了命題的題意,下面不同量詞間的次序是不可隨意交換的。 由定義可知下面I22~I27的正確性。

I22

xyA(x,y)

yxA(x,y) I23

yxA(x,y)

xyA(x,y) I24

xyA(x,y)

yxA(x,y) I25

yxA(x,y)

xyA(x,y) I26

yxA(x,y)

xyA(x,y) I27

xyA(x,y)yxA(x,y)。例I26由“有些動物為所有人喜歡。” 必可知“每個人喜歡一些動物?！盜26

正確反之,“每個人喜歡一些動物?！盜26的逆命題不成立。 不一定能有“有些動物為所有人喜歡?！倍x設A是不含聯(lián)結詞和的謂詞公式,則在其中

以聯(lián)結詞∧,∨分別代換∨,∧, 以量詞,分別代換,, 以常量0,1分別代換1,0 后所得的公式稱為A的對偶公式,記作AD。例A=yx(P(x,y)∧Q(x,y))∨1 AD=yx(P(x,y)∨Q(x,y))∧0定理(對偶原理)設A,B是兩個不含聯(lián)結詞和的謂詞公式,若AB,則ADBD

。定義2.11

設A為一謂詞公式,若A具有如下形式

Q1x1Q2x2…QkxkB則稱A為前束范式(prenexform)。

其中,Qi(1≤i≤k)為或,B為不含量詞的謂詞公式。即公式的所有量詞均非否定地出現(xiàn)在公式的最前面,且它們的轄域一直延伸到公式的末尾。例(1)x

(F(x)

y

(G(y)∧H(x,y)))不是前束范式;

(2)x(F(x)

y

(G(y)

H(x,y,z)))不是前束范式;(3)xyz((P(x,y)∧(Q(x)))(R(y,z)∨(Q(x));(4)xyz(P(x)Q(y)∧R(x,z))

(3),(4)都是前束范式定理任一謂詞公式都可以化成為與之等值的前束范式。證明

構造性算法步驟如下:1.消去聯(lián)結詞,。/*1和3的次序可交換2.將聯(lián)結詞向內(nèi)深入,使之只作用于原子公式。3.利用換名或代替規(guī)則使所有約束變項的符號均不同,并且自由變項與約束變項的符號也不同。4.利用量詞轄域的擴張和收縮律或量詞分配等值式,

將所有量詞以在公式中出現(xiàn)的順序移到公式最前面,

擴大量詞的轄域至整個公式。▋但前束范式的形式可能不是惟一的。例求公式B:(xP(x,y)

yQ(y))

xR(x,y)的前束范式解

B(xP(x,

t)

yQ(y))

xR(x,

t)

/*自由代替(xP(x,

t)

yQ(y))

zR(z,

t)

/*約束換名(xP(x,t)∨yQ(y))∨zR(z,t)/*消去聯(lián)結詞

(xP(x,t)∧yQ(y))∨zR(z,t)/*向內(nèi)深入

xP(x,t)∧yQ(y)∨zR(z,t) /*量詞轉換xyz(P(x,t)∧Q(y))∨R(z,t))

/*量詞轄域擴張例求公式A:(xP(x)∨yQ(y))

xR(x)的前束范式。解

A

(xP(x)∨yQ(y))∨xR(x)

/*消去聯(lián)結詞

xP(x)∧yQ(y)∨xR(x)

/*向內(nèi)深入

xP(x)∧yQ(y)∨zR(z)

/*量詞轉換,換名

xyz(P(x)∧Q(y)∨R(z))

/*量詞轄域擴張

例2.14求(1)xF(x)∧xG(x)的前束范式。/*不惟一解1

原式

xF(x)∧xG(x)

/*量詞轉換

x(F(x)∧G(x))/*(7)量詞分配解2

原式

xF(x)∧xG(x)

/*量詞轉換

xF(x)∧yG(y)

/*約束換名

xy(F(x)∧G(y))

/*量詞轄域擴張例2.14求(2)xF(x)∨xG(x)的前束范式。/*不惟一解

xF(x)∨xG(x)

xF(x)∨x

G(x)

/*量詞轉換

xF(x)∧yG(y)

/*約束換名

x

(F(x)∧yG(y))

/*令擴張5-2B=yG(y)

xy(F(x)∧G(y))

/*令擴張5-2B=F(x)例2.14求(4)xF(x)

xG(x)的前束范式。解

xF(x)xG(x)

xF(x)

yG(y)

/*約束換名

x

(F(x)

yG(y))

/*擴張6-3令B=yG(y)

xy

(F(x)

G(y))

/*擴張6-4令B=F(x)例2.14求(5)xF(x)

xG(x)的前束范式。解

xF(x)

xG(x)

y

F(y)

xG(x)

/*約束換名

y

(F(y)

xG(x))

/*擴張5-3令B=xG(x)

yx

(F(x)∧G(y))

/*令擴張5-4B=F(x)例2.14求(6)xF(x)

yG(y)的前束范式。解

xF(x)yG(y)

/*(4)的第二步

x

(F(x)

yG(y))

/*擴張6-3令B=yG(y)

xy

(F(x)

G(y))

/*擴張6-4令B=F(x)

求(7)(xF(x,y)

yG(y))

xH(x,y)的前束范式。解 (xF(x,y)

yG(y))

xH(x,y)

(xF(x,y)

tG(t))

wH(w,y)

/*約束換名

xt

(F(x,y)

G(t))

wH(w,y)

/*本例(6)

x(t

(F(x,y)

G(t))

wH(w,y))

/*5-3

xtw

(F(x,y)

G(t))

H(w,y))

/*本例(5)

求(8)(xF(x,y)∨yG(x,y))∧zH(x,y,z)的前束范式。解(xF(x,y)∨yG(x,y))∧zH(x,y,z)

(xF(x,t)∨yG(x,y))∧zH(x,t,z)

/*自由代替

(xF(x,t)∨yG(w,y))∧zH(w,t,z)

/*自由代替

x(F(x,t)∨yG(w,y))∧zH(w,t,z)

/*5-1

xy(F(x,t)∨G(w,y))∧zH(w,t,z)

/*5-1

x(y(F(x,t)∨G(w,y))∧zH(w,t,z))/*5-2

x(yz((F(x,t)∨G(w,y))∧H(w,t,z))/*本例(3)

xyz((F(x,t)∨G(w,y))∧H(w,t,z)/*5-2前束范式的優(yōu)點在于它的量詞全部集中在公式的前面,此部分稱為公式的首標。而公式的其余部分可看作是一個不含量詞的謂詞公式,它被稱為公式的尾部。在求給定謂詞公式的前束范式時,對量詞的左移的次序沒有機械地規(guī)定,對于尾部也沒有進一步的要求,

因此一個公式的前束范式可以不唯一;由于在謂詞邏輯中的判定問題無解,因此前束范式并不象命題邏輯中的范式那樣能解決判定問題。前束范式只是使公式的形式比較整齊規(guī)范,為判定工作提供一些方便。定義設謂詞公式A是一前束范式,若A的尾部具有形式:(A11∨A12∨…∨A1n1)∧...∧(Am1∨Am2∨…∨Amnm) (*)

其中Aij是原子謂詞公式或其否定,

則稱A是前束合取范式;

若A的尾部具有形式：(A11∧A12∧…∧A1n1)∨...∨(Am1∧Am2∧…∧Amnm)(**)

則稱A是前束析取范式。例xyz((P(x,y)∨R(x,z))∧(Q(y,z)∨P(x,y))) 是前束合取范式;

xzy(S(x,z)∨(P(x,y)∧Q(y,z)))是前束析取范式。定理每個謂詞公式A均可以變換為與它等值的前束合取范式和前束析取范式。證明將一個公式化為前束合取范式或前束析取范式時,只需在前面求前束范式的(1)~(4)四個步驟基礎上, 再增加下面步驟:(5)利用分配律將公式化為 前束合取范式或前束析取范式。例將A:x(P(x)

Q(x,y))

(xR(x)∧zS(z)) 化為前束合取范式和前束析取范式。解(1)消去聯(lián)結詞,：

A

x((P(x)

Q(x,y))∧(Q(x,y)

P(x)))

(xR(x)∧zS(z))

x((P(x)∨Q(x,y))∧(Q(x,y)∨P(x)))

∨(xR(x)∧zS(z)) (2)將聯(lián)結詞深入至原子謂詞公式：

A

x((P(x)∨Q(x,y))∨(Q(x,y)∨P(x))) ∨(xR(x)∧zS(z))

x(P(x)∧Q(x,y))∨(Q(x,y)∧P(x))) ∨(xR(x)∧zS(z))

(3)換名:

A

x((P(x)∧Q(x,y))∨(Q(x,y)∧P(x))) ∨(tR(t)∧zS(z))

(4)將量詞提到公式前：

A

x((P(x)∧Q(x,y))∨(Q(x,y)∧P(x)))∨tz(R(t)∧S(z))

xtz((P(x)∧Q(x,y))∨(Q(x,y)∧P(x))∨(R(t))∧S(z))) 至此,已得A的前束析取范式。(5)利用分配律化其為前束合取范式：A

xtz(((P(x)∨Q(x,y))∧(Q(x,y)∨P(x)) ∨(R(t))∧S(z)))

xtz(((P(x)∨(Q(x,y)∨R(t)) ∧(Q(x,y)∨P(x)∨S(z)) ∧(Q(x,y)∨P(x))∨R(t)) ∧(Q(x,y)∨P(x))∨S(z)))例求等價于x(P(x)y(zQ(x,y)zR(y,x)))的前束合取范式和前束析取范式：解

x(P(x)y(zQ(x,y)

zR(y,x))

x(P(x)∨y(Q(x,y)

R(y,x))

xy(P(x)∨Q(x,y)∨R(y,x)) 至此,已得前束合取范式,/*1個合取范式由主范式性質(zhì)可得前束析取范式

xy((P(x)∧Q(x,y)∧R(y,x))∨(P(x)∧Q(x,y)∧R(y,x))∨(P(x)∧Q(x,y)∧R(y,x))∨(P(x)∧Q(x,y)∧R(y,x))∨(P(x)∧Q(x,y)∧R(y,x))∨(P(x)∧Q(x,y)∧R(y,x))∨(P(x)∧Q(x,y)∧R(y,x))) /*7個析取范式二.斯柯林范式前束合(析)取范式的優(yōu)點在于它的量詞全部集中在公式的首部,公式其余部分實際上是一個命題演算公式,這就為謂詞公式提供了一種規(guī)范的形式,從而將公式形式的范圍縮小,給研究工作提供了一定的方便。但前束范式的不足之處是首標中比較雜亂無章,

全稱量詞與存在量詞無一定的排列規(guī)則。下面我們再引入前束詞都是某種特定類型量詞的斯柯林(Skolem)范式。定義首標中不含存在量詞的前束范式稱為斯柯林范式。定理 每個謂詞公式A均可以變換為 與它等值的斯柯林范式。證明由定理6.4.1知,任一謂詞公式A均可以變換為與它等值的前束范式,因此可假定公式A已是前束范式: A

Q1x1Q2x2…QnxnG(x1,x2,…xn) 其中首標Qixi為xi或xi(1≤i≤n),公式G中不含量詞?，F(xiàn)可進行如下的斯柯林變換消去首標中的存在量詞：1.若xk(1≤k≤n)左邊沒有全稱量詞,則取不在G中出現(xiàn)過的個體常項c替換G中所有的xk,并刪除首標中的xk。

2.若xk(1≤k≤n)左邊有全稱量詞 xs1,xs2,