現(xiàn)代邏輯謂詞邏輯

1、第五章 非形式的一階謂詞邏輯本章和下一章都屬于現(xiàn)代謂詞邏輯。這一章主要介紹一階謂詞邏輯的基本概念、形式結(jié)構(gòu)和語義，是一階謂詞演算的理論基礎(chǔ)。§ 1 從傳統(tǒng)謂詞邏輯到現(xiàn)代謂詞邏輯傳統(tǒng)謂詞邏輯主要是研究性質(zhì)命題及其推理( 以三段論為核心 ) 的邏輯。在傳統(tǒng)謂詞邏輯中，所有的命題都是僅僅具有如下 四種形式的命題：A 所有的S都是PE-所有的S都不是PI 有些 S 是 PO-有些S不是P至于具有“這個(gè)S是P和“這個(gè)S不是P之形式的命題 則被籠統(tǒng)地處理成相應(yīng)的 A命題和E命題。無疑，對于可以分析 成這種形式的命題來說，傳統(tǒng)謂詞邏輯中的方法很有實(shí)用性。但這種分析方法同時(shí)也存在著很大的局限性和過于

2、籠統(tǒng)化。試看如下命題：(1) 張三比李四年紀(jì)大。(2) 上海位于南京和杭州之間。(3) 有的提案得到了所有議員的歡迎。它們和具有上述A、 E、 I 、 0 四種形式的命題有著明顯的區(qū)別，稱為關(guān)系命題，即表達(dá)個(gè)體對象之間是否具有某種關(guān)系。由這些命題構(gòu)成的推理稱為關(guān)系推理。例如：張三比李四年紀(jì)大，李四比王五的年紀(jì)大所以，張三此王五的年紀(jì)大。直觀上看，這個(gè)推理是有效的，并且其有效性正在于命題的內(nèi)部結(jié)構(gòu)。類似這個(gè)推理的關(guān)系推理顯然應(yīng)該成為著重分析命題內(nèi)在邏輯結(jié)構(gòu)的謂詞邏輯的研究對象。但關(guān)系命題和關(guān)系推理都超出了傳統(tǒng)謂詞邏輯力所能及的范圍。傳統(tǒng)謂詞邏輯僅僅研究性質(zhì)命題； 而且僅僅研究三段論或是對性質(zhì)命題

3、的形式稍作變化的推理。盡管傳統(tǒng)謂詞邏輯也屬于謂詞邏輯，但它對謂詞的研究極其有限。謂詞有多種類型。有一元、二元乃至多元謂詞，有一階、二階乃至高階謂詞。一元謂詞是表示一個(gè)個(gè)體對象的性質(zhì)的謂詞， 二元及二元以上的謂詞則是表示兩個(gè)或兩個(gè)以上的個(gè)體對象之間的關(guān)系的謂詞。傳統(tǒng)謂詞邏輯所研究的性質(zhì)命題是只包含一元謂詞的命題，三段論也僅是關(guān)于一元謂詞的邏輯理論。對于包含二元及二元以上的謂詞的關(guān)系命題及其相關(guān)的關(guān)系推理形式，傳統(tǒng)謂詞邏輯完全沒有研究。其根本原因在于傳統(tǒng)謂詞邏輯的理論體系根本無法表達(dá)這類命題和推理。自傳統(tǒng)謂詞邏輯產(chǎn)生以來， 早就有邏輯學(xué)家意識到了這一問題，并且做了大量的工作企圖去彌補(bǔ)這一缺陷（可參

4、閱一些論及關(guān)系命題和關(guān)系推理的以傳統(tǒng)邏輯為主的邏輯教材或著作） 。但事實(shí)證明，凡是在傳統(tǒng)謂詞邏輯理論框架內(nèi)去解決這一問題，都是不會取得令人滿意的結(jié)果的； 而對于現(xiàn)代謂詞邏輯來說，解決這一問題是一件輕而易舉的事。 關(guān)系命題及其推理是現(xiàn)代謂詞邏輯的最基本內(nèi)容，在其理論體系中， 關(guān)系命題及其推理與性質(zhì)命題及其推理并無實(shí)質(zhì)性的區(qū)別，僅僅是包含不同的謂詞而已。謂詞邏輯重在研究量詞的邏輯性質(zhì)。傳統(tǒng)謂詞邏輯把量詞歸結(jié)為“所有”和“有些”，并進(jìn)而把命題歸結(jié)為全稱命題和特稱命題， 而對于日常語言中經(jīng)常出現(xiàn)的單稱命題基本上是回避。為了不致使其理論產(chǎn)生矛盾，對量詞理論采取了種種限制，例如規(guī)定被量詞約束的詞項(xiàng)不能是空

5、類等。在現(xiàn)代謂詞邏輯中，一切詞項(xiàng)都可以是空類，邏輯應(yīng)該盡量滿足一切可能性，只有這樣才具有普遍應(yīng)用性。傳統(tǒng)邏輯采取“限制”的辦法從根本上說是不得已的。實(shí)際上，如果取消這一限制，傳統(tǒng)謂詞邏輯理論除了極少的一部分外，基本上都是無效的。因此，這種理論就不具備任何完整性。更為重要的是，量詞是和謂詞的元數(shù)相關(guān)的。一個(gè)僅含有一元謂詞的命題是一種最簡單的情形，是謂詞邏輯所研究的最基本命題。對于包含多元謂詞的命題，情況馬上變得復(fù)雜起來。因?yàn)榱吭~的某些邏輯性質(zhì)，只有在量詞同時(shí)出現(xiàn)的場合下才充分顯示出來，也只有在這種情況下，才能體現(xiàn)出量詞的重要意義。由于傳統(tǒng)謂詞邏輯完全沒有研究包含多元謂詞和多重量詞的關(guān)系邏輯， 在

6、傳統(tǒng)邏輯的框架內(nèi)就不可能揭示出量詞的重要邏輯性質(zhì)和規(guī)律。這使得傳統(tǒng)謂詞邏輯的內(nèi)容貧乏，應(yīng)用范圍狹窄。造成傳統(tǒng)謂詞邏輯的局限性和缺陷的根本原因在于其研究工具。 傳統(tǒng)謂詞邏輯主要是用自然語言建立起來的邏輯理論，即使后來的一些邏輯學(xué)家引入了許多現(xiàn)代邏輯符號也不能從根本上解決問題，因?yàn)檫@些符號在相當(dāng)大的程度上是對傳統(tǒng)邏輯所使用的自然語言的一種縮寫，其本意不是并且實(shí)際結(jié)果也不能使邏輯理論尤其是推理系統(tǒng)化、嚴(yán)格化。邏輯和數(shù)學(xué)一樣，作為一門工具性的科學(xué)，其本身的語言和理論應(yīng)該相當(dāng)精確而嚴(yán)格，不能有任何歧義。而自然語言具有不可克服的歧義性和多義性，用自然語言極易混淆不同的邏輯關(guān)系，如“是”這個(gè)詞項(xiàng)，在不同的命

7、題中可以表達(dá)許多不同的邏輯關(guān)系。自然語言不僅不能精確地表述各種邏輯形式和邏輯規(guī)律，而且也不能構(gòu)造邏輯演算。后者在現(xiàn)代邏輯理論中已被證明是多么的重要，離開了邏輯演算的邏輯理論是很難想象的?，F(xiàn)代謂詞邏輯克服了傳統(tǒng)謂詞邏輯的局限性， 因?yàn)樗到y(tǒng)地使用了不會產(chǎn)生任何歧義的符號，尤其是表達(dá)個(gè)體變元、謂詞變元和量詞的符號，并在此基礎(chǔ)上應(yīng)用了形式化方法， 因而就可以把性質(zhì)命題、關(guān)系命題及其推理納入謂詞邏輯的統(tǒng)一體系之中，構(gòu)造嚴(yán)密而精確的謂詞演算。現(xiàn)代謂詞邏輯把傳統(tǒng)謂詞邏輯的研究對象作為自己研究對象的一部分，運(yùn)用現(xiàn)代邏輯的工具重新去描述傳統(tǒng)謂詞邏輯理論。從考察推理的邏輯形式以確定推理的有效性這一點(diǎn)正是邏輯理論

8、的核心所在的角度看，現(xiàn)代謂詞邏輯可以取代傳統(tǒng)謂詞邏輯。除了作為邏輯發(fā)展史中的一種邏輯理論的價(jià)值外，傳統(tǒng)謂詞邏輯的存在意義也僅僅在于它比較直觀，符合人們的日常思維習(xí)慣。現(xiàn)代謂詞邏輯是現(xiàn)代邏輯最基本的邏輯理論。它把命題邏輯作為自己的子系統(tǒng)，或者說， 現(xiàn)代謂詞邏輯是命題邏輯理論一致性的擴(kuò)充。但為了研究的方便，我們把命題邏輯作為一個(gè)獨(dú)立的系統(tǒng)，在第二、三章首先介紹，而在謂詞邏輯中則系統(tǒng)地研究量詞理論。 現(xiàn)代謂詞邏輯可分為一階謂詞邏輯和高階謂詞邏輯。一階謂詞邏輯是只研究一階謂詞（ 即僅指稱個(gè)體對象的性質(zhì)或個(gè)體對象之間的關(guān)系，而不指稱個(gè)體對象的性質(zhì)的性質(zhì)、性質(zhì)之間的關(guān)系或個(gè)體對象之間的關(guān)系的關(guān)系、關(guān)系的性

9、質(zhì)的謂詞） 和個(gè)體量詞 （ 即只約束個(gè)體對象，而不約束個(gè)體對象的性質(zhì)或個(gè)體對象之間的關(guān)系的量詞）的謂詞邏輯，又稱狹義謂詞邏輯，是現(xiàn)代謂詞邏輯中研究得最徹底最成熟的邏輯理論。由于高階謂詞邏輯最終可以化歸為一階謂詞邏輯。所以我們在本書中也只介紹一階謂詞邏輯。2 命題的一階謂詞邏輯分析一階謂詞邏輯主要研究量化命題。本節(jié)在運(yùn)用一階謂詞邏輯語言著重分析量化命題的同時(shí)，也分析不含量詞的原子命題，并對這些命題進(jìn)行符號化。首先引入幾個(gè)基本概念。一、個(gè)體詞、個(gè)體函數(shù)詞、謂詞考察下面一組命題或命題函數(shù):(1)3 是質(zhì)數(shù)。(2) 約翰的父親是英國人。(3) 所有的 x 都是化合物。(4) 張三與李四是同學(xué)。(5)

10、上海在杭州與北京之間。其中， “ 3”、 “約翰” 、 “ x”、 “張三” 、 “李四” 、 “上?！?、 “杭州” 、 “北京”表示的都是個(gè)體對象。在現(xiàn)代謂詞邏輯中，用來指稱這些個(gè)體對象的符號稱為個(gè)體詞。個(gè)體詞又分為個(gè)體變元( 或個(gè)體變項(xiàng) ) 和個(gè)體常元( 或個(gè)體常項(xiàng)) 。個(gè)體常元指稱某一確定的具體對象，例如指稱個(gè)體對象“3”、 “約翰” 、 “張三” 、 “李四” 、 “上?！?、 “杭州” 、 “北京”的個(gè)體詞就是個(gè)體常元。個(gè)體變元指稱某一個(gè)體對象類中任意的個(gè)體，如例 (3)中的“x”，其中的個(gè)體對象類是個(gè)體的取值范圍，稱為論域或個(gè)體域。個(gè)體常元一般用a，b, c,來表示，個(gè)體變元?jiǎng)t用

11、 x, y, z來表示。我們注意到，例 (2) 與例 (1) 是有差別的。例 (1) 的主項(xiàng) ( 為表述的方便，借用傳統(tǒng)謂詞邏輯“主項(xiàng)”這一概念 ) 是某個(gè)確定的個(gè)體對象本身，而例(2) 的主項(xiàng)盡管也是某個(gè)確定的個(gè)體對象，但它是由另一個(gè)確定的對象通過某種關(guān)系確定下來的，這種關(guān)系就是函數(shù)關(guān)系。如該例中的“的父親"o再如“ 2的平方是偶數(shù)”中的主項(xiàng)也是由個(gè)體對象“2”通過函數(shù)關(guān)系”的平方”來確定的。由于這種函數(shù)的定義域是個(gè)體對象，值域也是個(gè)體對象，因此，指稱這種函數(shù)關(guān)系的符號就稱為個(gè)體函數(shù)詞，簡稱函數(shù)詞。個(gè)體函數(shù)詞代表的是一種對個(gè)體對象的運(yùn)算，實(shí)質(zhì)上起的是個(gè)體詞的作用。在前述的例子中，

12、“約翰的父親”指稱的是個(gè)體常元，“ 2 的平方”指稱的也是個(gè)體常元“4”。因此，可以把個(gè)體函數(shù)詞作為一種特殊的個(gè)體詞。謂詞是指稱對象（ 在一階謂詞中是個(gè)體對象） 所具有的性質(zhì)或?qū)ο笾g所具有的關(guān)系的符號。謂詞可以分為謂詞常元（ 或謂詞常項(xiàng) ） 和謂詞變元（ 或謂詞變項(xiàng)） 。表示某一確定論域中的特定的性質(zhì)或關(guān)系的謂詞稱為謂詞常元，如前例中的“是質(zhì)數(shù)”、 “是英國人”、“是化合物”、“是同學(xué)”、“在之間”。不表示某一確定論域中的特定性質(zhì)或關(guān)系的謂詞稱為謂詞變元。謂詞變元一般用符號F, G, H來表示。根據(jù)謂詞指稱的個(gè)體對象的數(shù)目（稱為元數(shù) ） ，可以把謂詞分為一元謂詞、二元謂詞，n元謂詞。一元謂詞

13、只指稱一個(gè)個(gè)體對象，顯然表達(dá)的就是個(gè)體對象的性質(zhì)，如“是質(zhì)數(shù)” 、 “是英國人”、 “是化合物”就是一元謂詞。二元謂詞指稱兩個(gè)個(gè)體對象，表達(dá)的是其間的關(guān)系，如“是同學(xué)”。三元謂詞表達(dá)的是三個(gè)個(gè)體對象之間的關(guān)系，如“在之間"o謂詞的元數(shù)可以明確地標(biāo)示出來，如F1表示F是一元謂詞，G2表示G是二元謂詞，等等。二、量詞量詞是謂詞邏輯中最重要的研究對象。謂詞邏輯也因之稱為量詞邏輯。量詞是構(gòu)成簡單命題的成分。簡單命題分為不含有量詞（ 僅含有個(gè)體詞或函數(shù)詞、謂詞 ） 的原子命題和含有量詞的量化命題。原子命題是謂詞邏輯中最簡單的命題，而謂詞邏輯的邏輯特征主要通過量化命題顯示出來，因此謂詞邏輯所研究

14、的簡單命題主要是量化命題。量詞是表示被其約束的對象的數(shù)量的邏輯符號。依據(jù)它所指的是某對象類中的所有對象還是至少一個(gè)對象，量詞可分為全稱量詞和存在量詞。全稱量詞用“ ”表示，自然語言中的“所有”“凡”、 “任一個(gè)”、 “每一個(gè)”、 “一切”等都表示全稱量詞。其準(zhǔn)確含義是“對任一來說"o存在量詞用“ ”表示，自然語言中的“有些”、 “有的” 、 “至少有些”等表示的都是存在量詞。其準(zhǔn)確含義是“至少存在一個(gè)”。根據(jù)量詞所約束的對象是個(gè)體詞還是謂詞，可以把量詞分為一階量詞、二階量詞以至高階量詞。 一階量詞是只約束個(gè)體詞的量詞，即這種量詞所限制的只是個(gè)體對象。一階謂詞邏輯只研究一階量詞。二階量

15、詞所約束的是一階謂詞，三階量詞所約束的是二階謂詞，依此類推，它們都是高階謂詞邏輯的研究對象。有了個(gè)體詞、個(gè)體函數(shù)詞、一階謂詞、一階量詞等概念和符號， 就可以對命題進(jìn)行邏輯分析和符號化。根據(jù)是否含有量詞可以把命題分為量化命題和原子命題。根據(jù)命題的復(fù)雜度又可把命題又可以分為簡單命題和復(fù)合命題。下面將按這兩種標(biāo)準(zhǔn)，對命題進(jìn)行符號化。三、原子命題的符號化原子命題可以分為簡單原子命題和復(fù)合原子命題。1. 簡單原子命題的符號化簡單原子命題是不含有量詞的簡單命題。下列命題都是簡單原子命題：(1)3 是質(zhì)數(shù)?？煞柣癁椋篎(a) 。(2) 張三與李四是同學(xué)?？煞柣癁椋篏(a， b) 。(3) 上海在杭州與北

16、京之間?？煞柣癁椋篐(a， b， c) 。(4) 約翰的父親是英國人?？煞柣癁?F(f(a)。以上簡單原子命題符號化后的表達(dá)式稱為簡單原子命題形式，簡稱簡單原子式。簡單原子式也可以是簡單原子命題函數(shù)( 關(guān)于命題與命題函數(shù)之區(qū)別將在后面詳述) 的邏輯形式。例如:(1)x 等于 y 與 3 之和?？煞柣癁椋篐(x， y， a)。(2)x是化合物?？煞柣癁椋篎(x)H(x, y, a)與F(x)也都是簡單原子式。2. 復(fù)合原子命題的符號化復(fù)合原子命題是由聯(lián)結(jié)詞和簡單原子命題構(gòu)成的復(fù)合命題。復(fù)合原子命題或復(fù)合原子命題函數(shù)符號化后的表達(dá)式稱為復(fù)合原子式。考慮以下命題( 函數(shù) ):(l)x 不是有

17、理數(shù)。可符號化為：F(x)。(2) 亞里士多德既是哲學(xué)家，又是邏輯學(xué)家?？煞柣癁镕(a)A G(a)。(3)或者甲是被告，或者乙是被告?？煞柣癁椋篎(a)VF(b),(4) 如果 x 能被 2 整除，那么y 也能被 2 整除?？煞柣癁?H(x , a)f H(y, a)。(5) 張三尊敬李四，當(dāng)且僅當(dāng)李四也尊敬張三?？煞柣癁?:H(a， b) ?H(b， a)。符號化后的這五個(gè)表達(dá)式是最基本的復(fù)合原子式，它們均分別只含有二個(gè)聯(lián)結(jié)詞。由復(fù)合原子式通過聯(lián)結(jié)詞可構(gòu)成多重復(fù)合原子式。例如:(6)F(x)VF(x)(7)F(x)-(G(y) - F(x)A G(y)(8)F(x)AG(y)-(F

18、(x)?G(y)都是多重復(fù)合原子式。"四、量化命題的符號化1. 量化命題和量化式含有量詞的命題稱為量化命題。量化命題( 或命題函數(shù)) 符號化后的表達(dá)式稱為量化命題形式。簡稱量化式。量化式可以分為基本重化式和復(fù)合量化式?；玖炕绞莾H由量詞和簡單原子式構(gòu)成的命題形式。例如，以下命題形式都是基本量化式:(1) xF(x)(2) yG(y)(3) x yH(x，y)(4) x yH(x，y)(5) x yH(x，y)(6) x yH(x， y)復(fù)合量化式是由量詞和復(fù)合命題形式組成的命題形式。例如，下列命題形式均是復(fù)合量化式，(1) xF(x)(2) xF(x)(3) x(F(x) ? (y

19、)(4) y (AA B)(5) x(A 7 B)(6) xAV yB2. 對傳統(tǒng)謂詞邏輯A、 E、 I 、 0 四種命題的符號化一階謂詞邏輯對A、E、 I 、 0 四種命題的符號化與傳統(tǒng)謂詞 邏輯有著根本的區(qū)別。首先考慮A命題。例如：(1) 所有的金屬都是導(dǎo)電的?，F(xiàn)代謂詞邏輯對A命題有兩種符號化的方法。方法一 : 先設(shè)定個(gè)體域( 論域 ) ， 然后再符號化。( 1) 的個(gè)體域是金屬，在此前提下，用F 表示謂詞“是導(dǎo)電的”則 (1) 可符號化為 :xF(x) 。方法一存在若明顯的缺陷。不同的命題必須設(shè)定不同的個(gè)體域，這使得個(gè)體詞是事先帶著某種確定的意義作為命題形式的個(gè)體變元， 從而就使量化式反

20、映不出同類命題形式的共性。更有甚者，當(dāng)一個(gè)命題形式中須要用到多個(gè)個(gè)體變項(xiàng)時(shí)，每一個(gè)體變項(xiàng)的論域都必須規(guī)定，這極易引起混亂。因此，方法一不具有普遍應(yīng)用性?，F(xiàn)代謂詞過輯一般應(yīng)用方法二：把性質(zhì)命題的主項(xiàng)也用謂詞表示出來，從而使個(gè)體域反映在謂詞之中。應(yīng)用方法二，( 1) 可以分析為：對任一個(gè)體而言，如果它是金屬，那么它是導(dǎo)電的?？梢苑柣癁椋簒(S(x) - P(x) o該復(fù)合量化式具有普遍應(yīng)用性，其中個(gè)體變項(xiàng)x 的論域是一切事物，當(dāng)對S與P作不同的解釋時(shí)，就可以得到任何A命題。E 命題的符號化類似于A命題。例如：(2) 所有的共產(chǎn)黨員都不是有神論者。可以分析為：對任一個(gè)體而言，如果它是共產(chǎn)黨員，那么

21、它不是有神論者。符號化為:x(S(x) 7P(x) o再看 I 命題。例如：(3) 有些天鵝是黑色的?？梢苑治鰹椋辽俅嬖谝粋€(gè)個(gè)體，它是天鵝并且是黑色的。符號化為 :x(S(x) A P(x) o我們把 I 命題分析成上述的合取式，而不是像全稱命題一樣，分析成蘊(yùn)涵式：x(S(x) -P(x)。因?yàn)槿暨@樣，就會使一假的命題可能成為真命題。例如：有些人是神仙。這是一個(gè)假命題。若分析為蘊(yùn)涵式 x(S(x) -P(x),表示“至少存在一個(gè)體，如果它是人，那么它是神仙”。該量化式可變形為x(S(x) VP(x),它表示“至少存在一個(gè)體，它或者不是人，或者是神仙”，這等于說“或者存在一個(gè)不是人的個(gè)體，或者

22、存在一個(gè)是神仙的個(gè)體?！?因?yàn)閤(S(x) V P(x) ? ( xS(x) VxP(x) ， 我們將在以后證明這一等值式是成立的。)最后這個(gè)選言命題很容易滿足，是一真命題。這意味著“有些人是神仙”也是真命題。因此，I 命題不可用蘊(yùn)涵式來表示。當(dāng)用合取式表示時(shí)，能夠保持與原命題相同的真值。與此相反，全稱命題不可分析為合取式。例如， x(S(x) 一P(x)表示任何是S的東西都是P,而x(S(x) A P(x)表示任何 東西都既是S,又是P。二者含義差別極大。只有前者才是諸如“所有金屬都是導(dǎo)電的”等 A命題的正確符號化。同樣，E命題也不能符號化為x(S(x) AP(x),而應(yīng)是 x(S(x) -

23、P(x) o0 命題與 I 命題一樣，其命題形式也是分析成合取式。例如 :(4) 有些天體不是行星?？梢苑治鰹椋?“至少存在一個(gè)體，它是天體，并且不是行星”。符號化為 :x(S(x) AP(x) o至此，可以把傳統(tǒng)謂詞邏輯與現(xiàn)代謂詞邏輯對四種基本性質(zhì)命題符號化的不同方法比較一下：所有 S 都是 P: SAP x(S(x) -P(x)所有 S 都不是 P：SEP;x(S(x) -P(x)有些 S是 P:SIP ; x(S(x) A P(x)有些 S 不是 P:SOR x(S(x) AP(x)兩者的根本區(qū)別在于現(xiàn)代謂詞邏輯引入了個(gè)體詞和量詞，從而豐富了量化理論。通過個(gè)體詞(x) 分別與主項(xiàng)(S)

24、和謂詞 (P) 之間的屬于關(guān)系，可以精確地描述S和P之間的關(guān)系，從而確定性質(zhì)命題的邏輯形式。全稱量詞和存在量詞的引入使得可以對任意的命題形式進(jìn)行量化表達(dá)，從而克服了傳統(tǒng)謂詞邏輯只能對主項(xiàng)(S)作出量化表達(dá)的局限性。用量化的蘊(yùn)涵式和量化的合取式分別表示全稱命題形式和特稱命題形式充分顯示了這兩種命題形式的 嚴(yán)格區(qū)別。四種基本性質(zhì)命題在一階謂詞邏輯中的邏輯形式都是復(fù)合量化式。3. 帶量詞的關(guān)系命題的符號化在原子命題的符號化中，已經(jīng)考察了諸如“張三與李四是同學(xué)” 這樣的不帶量詞的關(guān)系命題。接下來分析含有一個(gè)或一個(gè)以上量詞的關(guān)系命題。例 (1) ： 每一事物影響有些事物。若用個(gè)體詞x 表示影響其他事物的

25、事物，用個(gè)體詞y 表示被其他事物影響的事物。用謂詞H 表示“影響”這一關(guān)系，則 (1) 可以理解為：對任一個(gè)體x而言，都存在一個(gè)體y,x與y有H關(guān)系?？梢苑柣癁椋?1' ) x yH(x, y)。例(2) ：有些事物影響每一事物?？梢岳斫鉃椋褐辽儆幸粋€(gè)體x,對任一個(gè)體y而言，x與y有H關(guān)系?？梢苑柣癁?(2' ) x yH(x, y)o例 (3): 任一事物影響任一事物。它可以理解為:對任一個(gè)體x, y而言，x與y都有H關(guān)系。可以符號化為：(3) x yH(x, y)。例 (4) ，有些事物影響有些事物。可以理解為:至少存在一個(gè)體x,至少存在一個(gè)體y,x與y有H關(guān)系可以符號

26、化為：(4' ) x yH(x, y)(1')-(4 ')都是含有兩個(gè)量詞和一個(gè)由二元謂詞構(gòu)成的簡單原子式的命題形式。它們都是基本量化式。下面考察更為復(fù)雜的例子。例 (5) ：有些人尊重所有人。這個(gè)命題中的個(gè)體詞是“人”，它不同于例(1)-(4) 的個(gè)體詞“事物”。前者須要用謂詞定義，而后者是指稱任何個(gè)體，因而無須用謂詞定義。(5) 可以理解為：至少存在一個(gè)體x， x 是人，并且對任一個(gè)體y 而言，如果y 是人， 則 x 尊重y。 若用謂詞F 表示 “是人” ， 用謂詞 H 表示 “尊重” ，則本命題可符號化為。(5' ) x (F(x) A y(F(y) -H

27、(x, y)。例 (6): 每個(gè)人都尊重有些人。這個(gè)命題可理解為:對任一個(gè)體x 而言，如果x 是人，則至少存在一個(gè)體y， y是人，并且x尊重y?？煞柣癁椋?6' ) x(F(x) - y(F(y) AH(x, y)。例 (7) ，沒有液體能溶解所有的東西，但有些東西能被所有的液體溶解。它可以理解為：并非至少存在一個(gè)體x， x 是液體，并且x 能溶解所有的y；并且，至少存在一個(gè)體y,對任一個(gè)體x而言，如果x是液體， 則x能溶解y。若用謂詞F表示“是液體”，用謂詞H表示“溶解” ，則 (7) 可符號化為:(7' ) x(F(x) AH(x, y) A y x(F (x)-H(x,

28、 y)(7) 也可以理解為:并非至少存在一個(gè)體x， x 是液體，并且x 能溶解所有的y；并且， 對任一個(gè)體x 而言， 如果 x 是液體， 則至少存在一個(gè)體y，x能溶解y?？梢苑柣癁椋?7' ) x(F(x) AH(x, y)A x (F(x) - yH(x, y)(7')與(7')在形式上雖有所不同，但實(shí)際上是等值的。(1')-(7 ')以及(7 ')都是復(fù)合量化式。由于這類命題形式是由多個(gè)量詞、謂詞和聯(lián)結(jié)詞構(gòu)成的，最能反映量詞的邏輯性質(zhì)，因而是一階謂詞邏輯所研究的最主要的命題形式。從以上對性質(zhì)命題和關(guān)系命題的分析可知，一階謂詞邏輯把“關(guān)系”看

29、作是與“性質(zhì)”類似的謂詞，二者的區(qū)別僅僅在于表達(dá)“性質(zhì)”的謂詞是一元的，而表達(dá)“關(guān)系”的謂詞是二元的或二元以上的。這種統(tǒng)一性在接下來的一階謂詞演算中得到了更充分的反映。S3 一階謂詞語言的語法和語義還增加了謂詞邏輯一階謂詞語言簡稱一階語言。它是命題邏輯形式語言一致 性的擴(kuò)充。除了包含有命題邏輯形式語言外，17特有的個(gè)體詞、個(gè)體函數(shù)詞、謂詞和量詞?，F(xiàn)代謂詞邏輯迄今已發(fā)展出了許多等價(jià)或不等價(jià)的一階語言。本書將介紹一種最常用的一階語言一一Li語言。一階語言Li,包括帶等詞的和不帶等詞的兩種。 為求語言的簡潔性，在不破壞理論的系統(tǒng)性和嚴(yán)格性的前提下，本章將略去帶等詞的謂詞邏輯。一階語言Li 包括語法和

30、語義兩部分。一、Li的語法L i 的語法由初始符號、項(xiàng)形成規(guī)則、合式公式形成規(guī)則和定義四部分構(gòu)成，合稱Li 的形式語言。1. 初始符號(1) 個(gè)體變元Xi (用x, y, z, xi, yi, zi,表示)；(2) 個(gè)體常元ai(用a, b,c,ai,bi,ci,表示)；(3)n元謂詞變元Fin(用F,G,H,Fi,G,T,表示)；(4)n元函數(shù)變元九”(用£,g,h,fi,gi,hi,表示)；(5) 命題變元P(用p, q,r,pi,qi,ri,表示)；(6) 量詞：；(7) 聯(lián)結(jié)詞：;(8) 技術(shù)性符號(輔助符號):( ， ) ， ， ( 即左右括號和逗號)。L i 中只有以上八

31、類符號，其中個(gè)體常元和函數(shù)變元可以沒有。Li的任意表達(dá)式都是由初始符號按一定規(guī)則組合而成的符號串。在各種符號串中，我們感興趣的是項(xiàng)和合式公式。2. 項(xiàng)形成規(guī)則(1)任意Li的個(gè)體變元Xi是項(xiàng)；(2) 任意L1 的個(gè)體常元ai 是項(xiàng)；(3)若fn是Li的n元函數(shù)變元，ti, t2,，tn是Li的項(xiàng)，貝 U fn(t 1, t2,，tn)是項(xiàng)；(4)只有按(1)-(3)的規(guī)則而形成的符號串才是Li的項(xiàng)。例如，令f, g分別是一元函數(shù)變元和二元函數(shù)變元，x, a分別是個(gè)體變元和個(gè)體常元，則X， a 是項(xiàng)；f( X) ， f(a) 是項(xiàng)， g(X ，a) ， g(f ( x) ， f(a) 等都是項(xiàng)。

32、3. 合式公式形成規(guī)則合式公式簡稱公式。Li 的公式按以下規(guī)則形成，(1) 任意命題變元pi 是公式；(2)若Fn是一 n元謂詞符號，ti, t2,，tn是項(xiàng)，則Fn(ti, t2,，tn)是公式；(3)若A是公式，則A是公式；(4)若A、B都是公式，則 A- B是公式；(5)若A是公式，x是個(gè)體變元，則xA是公式；(6)Li的所有公式只按-(5)規(guī)則形成。Li 的公式是命題邏輯公式的擴(kuò)充，凡命題邏輯的公式都是Li的公式。4. 定義Li語言中，只有、一兩種聯(lián)結(jié)詞和一個(gè)量詞。但可以通過定義把常用的V、八、？等聯(lián)結(jié)詞和 量詞引入Li,凡包括這i21些聯(lián)結(jié)詞或量詞的公式都稱為L1 的定義公式。定義如

33、下：(l)A VB=dfA B,記作 DU(2)A A B=df(AB),記作 D八。(3)A?B=df (A- B) A ( B7 A),記作 D。(4) xA=dfxA,記作 D o今后將不對Li的公式和定義公式作嚴(yán)格區(qū)分，Li的定義公式可直接作為公式。5. 量詞和聯(lián)結(jié)詞的轄域量詞的轄域即量詞的作用范圍。一個(gè)量詞的轄域是這個(gè)量詞右邊最短的公式，換句話說，若 xB是A的子公式，則稱B為緊 接其左邊的x在A中的轄域；若xB是A的子公式，則稱B為 緊接其左邊的x在A中的轄域。例如：(1) xF(x) - G(x)(2) x(F(x) AG(y)-F(x)(3) x( yF(y) -G(x)公式

34、(i) 中， x 的轄域?yàn)镕(x) 。公式 (2) 中， x 的轄域是F(x) AG(x)。公式(3)中，x的轄域?yàn)閥F(x) - G(x) , y的轄 域?yàn)镕( y) 。聯(lián)結(jié)詞的轄域即聯(lián)結(jié)詞的作用范圍?？啥x為：若 B是A 的子公式，則稱B為緊接其左邊的在 A中的轄域；若B-C是 A的子公式，則稱 B和C為BC中的一在A中的轄域，其中B 為左轄域，C為右轄域。6. 自由變元與約束變元這里的變元是指個(gè)體變元。一個(gè)變元在公式中的出現(xiàn)有兩種不同情形: 自由出現(xiàn)和約束出現(xiàn)。凡量化變元( 指緊接量詞右邊的第一個(gè)個(gè)體變元) 或在量詞的轄域內(nèi)出現(xiàn)的與量化變元相同的變元均為約束變元，否則為自由變元。一個(gè)變元

35、作為約束變元在某公式中出現(xiàn)稱為約束出現(xiàn)，否則為自由出現(xiàn)。一變元在其公式中約束出現(xiàn)稱該變元在公式中是約束的，否則為自由的。在公式 “ F(y) - x y (F(y) -G(x) ”中，y的第一次出現(xiàn)是自由的，第二、 三次出現(xiàn)是約束的。x 的兩次出現(xiàn)都是約束的，是約束變元。量化變元不必出現(xiàn)在量詞的轄域之內(nèi)，因而存在著空約束。對Li的任意公式A中的任意變元x是否是自由變元或約束變元，也可以采用以下的歸納定義:(1) 若人=口，則A中既沒有自由變元，也沒有約束變元。(2) 若A=F(ti, t2,，tn),則x在A中的每一出現(xiàn)都是自由的。(3) 若人=B,則x在A中的某一特定出現(xiàn)是自由的，當(dāng)且僅當(dāng)x

36、 的這一出現(xiàn)在B 中是自由的。(4) 若人=4C,則x在A中的某一特定出現(xiàn)是自由的，當(dāng)且僅當(dāng)x 的這一出現(xiàn)在B 或 C 中是自由的。(5) 若人=xB,則x在A中的每一出現(xiàn)都是約束的。若A= yB, x是B中的變元，并且x中y,那么x在A中的某一特定出現(xiàn)是自 由的，當(dāng)且僅當(dāng)x 的這一出現(xiàn)在B 中也是自由的。任一個(gè)體變元在一公式中既可自由出現(xiàn)，也可約束出現(xiàn)。一個(gè)不含有任何自由變元的公式稱為閉公式，而至少含有一個(gè)自由變元的公式稱為開公式。閉公式與開公式的邏輯意義是不同的。以下兩個(gè)公式：(l)H(x ， y)(2) x(F(x) - G(x, a)公式 (1) 中的x， y 都是自由變元。所以(1)

37、 是開公式。而(2) 中的 x 是約束變元，a 是個(gè)體常元，所以(2) 是閉公式。令(1) 的個(gè)體域是“數(shù)”，把H解釋為關(guān)系，則H(x, y)表示“x>y”。顯然H(x， y) 是其假不定的，它取決于對x,y 的賦值。若指定x為5, y為3,則H(x, y)為真,若指定x為3, y為5,則H(x, y) 為假。同樣，令(2) 的個(gè)體域也是“數(shù)”，把 F 解釋為“偶數(shù)”，指定a=2,把G解釋為“被2整除”關(guān)系，則表示"所有的偶 數(shù)都能被2 整除” ，這是一個(gè)真命題。一般地，開公式經(jīng)過解釋后還不是命題，而是命題函數(shù)，其真假是不確定的。閉公式經(jīng)過解釋后成為命題，非真即假。反之，一命題

38、函數(shù)符號化之后的公 式是一個(gè)開公式，而命題符號化之后的公式都是閉公式。二、Li的語義任何一個(gè)語法系統(tǒng)在未得到某種語義之前都只是純符號組合串， 只有經(jīng)過某種語義解釋，才能成為該語義系統(tǒng)的語法系統(tǒng)，并判定其真假，確定其他的邏輯性質(zhì)。對Li的語義解釋分為兩個(gè) 部分，一個(gè)是語義模型，另一個(gè)是真值語義解釋。2i1 .L1的語義模型定義 3.1 語義模型是指能使一種語言的公式集都為真的解釋。Li的語義模型是一個(gè)由個(gè)體對象類和關(guān)系所組成的代數(shù)結(jié)構(gòu)I ， I 由如下部分構(gòu)成：(1) 一個(gè)非空集D,稱為I的個(gè)體域或論域，D中的元素稱為I 的個(gè)體。(2) 一個(gè)函項(xiàng)，對Li中的每個(gè)謂詞符號F,都指定D中的一 個(gè)關(guān)系

39、F。如果F是一 n(n)2)元謂詞符號，那么F1是D中的一 n 元關(guān)系；如果F 是一元謂詞符號，那么FI 是 D 中的一個(gè)子類。(3) 一個(gè)函項(xiàng)，對Li 中的每個(gè)函數(shù)符號f ，都指定D 中的一個(gè)運(yùn)算f1。如果f是一 n元函數(shù)符號，那么f1是D中的一 n元運(yùn) 算。(4) 一個(gè)函項(xiàng)，對Li中的每個(gè)個(gè)體常元符號 a,都指定D中的一個(gè)個(gè)體aI。由以上部分組成的代數(shù)結(jié)構(gòu)I 就是Li 的語義模型。2 .L i的真值語義解釋L i 的真值語義解釋就是在語義模型I 的基礎(chǔ)上，對 Li 的項(xiàng)和公式進(jìn)行賦值，使之獲得真值語義。L 1的一個(gè)賦值是由一個(gè)語義模型I和I中一個(gè)指派函數(shù)B所組成的有序二元組 v, v= (

40、I, B)。v對Li的每一個(gè)體變元x指 派I的個(gè)體域D中的一個(gè)元素為值，記作B (x),即v(x)= B (x)； 對每一函數(shù)符f,指派I中一 n元運(yùn)算fI為值，即v(f)=f I;對每一謂詞符號F,指派I中一 n元關(guān)系F1為值，即v(F尸F(xiàn)1;對 每一個(gè)體常元a,指派I的個(gè)體域D中一個(gè)體a1為值，即v(a尸a ： I 的個(gè)體域D 也稱之為v 的個(gè)體域。定義3.2任意Li的項(xiàng)t在賦值v下的值v(t)可定義如下：(1) 若t是一 Li的個(gè)體變元x,則令v(x)= B (x);(2) 若t是一 Li的個(gè)體常元a,則令v(a)=a 1 ；(3) 若f是一 Li的n元函數(shù)符，11, t2,，tn是Li

41、的項(xiàng)，則 令 v(f(t i, t2,，tn)=f I(v(t i), v(t 2),，v(t n)。定義3.3任意Li的公式A在賦值v下的值v(A)可定義為：(1) 如果A是F(ti, t2,，tn), F是Li的一 n元謂詞符，t i , t 2,，t n是項(xiàng)，則1 ，若 v(t i),v(t 2),，v(t n) Gv(F),V(F(t i, t2,，tn)=0, 否則。(2) 如果A是B,則1 ，若 v(B)=0 ，v( B)=0, 否則。(3) 如果A=B C,則1 ，若 v(B)=0 或 v(c)=i ，v(Bc尸0，否則。(4) 如果A= xB,則1 ,若對每一 ai(aiG D

42、),都有 v(B(x/a i)=1 ,v( xB)=0 ，否則。對 (4) 作一說明。xB 的值為 1，當(dāng)且僅當(dāng)把論域D 中任意個(gè)體ai賦給B中的x,都有v(B)=1 ,即v(B(x/a i)=1 ;若x不在B 中出現(xiàn)，則v( xB)=1 當(dāng)且僅當(dāng)v( B)=1 。例如，公式xF(x)表示“所有x都是F”，設(shè)其論域?yàn)镈,則對任意個(gè)體a G D,若 v(F(a i)=1 ,則 xF (x)的值必為 1,即 v( xF (x)=1 。對公式 xF(y)(x 不同于 y) 而言，由于x 不在 F(y) 中出現(xiàn)，故當(dāng)v(F(y)=1 時(shí)，必有xF(y) 也取值為1 ，反之亦然。3.L1的普遍有效式、可

43、滿足式、不可滿足式如果一個(gè)賦值v,使得公式A取真值為1,即v(A)=1 ,則 稱賦值v滿足公式A,記作v卜A。賦值v滿足公式集F,當(dāng)且僅 當(dāng)對任意AG r,都有v卜A,記作v kro經(jīng)過賦值后的L1 的公式有三種可能情況: 普遍有效式、可滿足式和不可滿足式一個(gè)公式A是普遍有效式，當(dāng)且僅當(dāng)它為每一特定的賦值vi 所滿足，即用任一特定的命題替代其中的命題變項(xiàng)，用任一特定的個(gè)體詞替代其中的個(gè)體變元和個(gè)體常元，用任一特定的謂詞、函效詞替代其中的謂詞變元、函數(shù)變元，其結(jié)果總是真的?；蛘哒f， 一個(gè)公式是普遍有效式，當(dāng)且僅當(dāng)任一解釋都使之取值為真。若A是普遍有效的，記作Vi kA,簡記為kA。傳統(tǒng)邏輯中的同

44、一律、矛盾律和排中律在表示為現(xiàn)代謂詞邏輯公式后，分別是：(1) x(F(x) - F(x)(2) x(F(x) AF(x)(3) x(F(x) VF(x)可以看出，以上三個(gè)公式都是普遍有效式，所以它們被作為邏輯規(guī)律。一個(gè)公式A是可滿足式，當(dāng)且僅當(dāng)至少存在一個(gè)賦值Vx,使A取值為真。記作Vx卜4例如公式 xF(x)就是可滿足式，當(dāng)確 定個(gè)體城為“自然界的事物”，把 F 解釋為“運(yùn)動變化”時(shí)，公式就是真的。一個(gè)公式A是不可滿足式，當(dāng)且僅當(dāng)不存在任何賦值，使 A 取值為真。記作 Vi|中A。例如x(F(x) AF(x)就是不可滿足 式。從以上定義可知，公式 A是普遍有效式，當(dāng)且僅當(dāng)A是不可滿足式。普

45、遍有效式和不可滿足式之間的關(guān)系類似于命題邏輯中重言式和不可滿足式之間的關(guān)系。這里需要說明重言式與普遍有效式之間的關(guān)系。在命題邏輯中，我們討論了重言式。由謂詞邏輯是命題邏輯的擴(kuò)充，在命題邏輯中取值為真的公式在謂詞邏輯中也應(yīng)是真的，因此， 凡命題邏輯中的重言式都是謂詞邏輯中的普遍有效式，簡言之， 若公式A是重言式，則A是普遍有效式。但反之則不必然成立。因?yàn)橹匮允绞峭ㄟ^真值賦值確定的，而普遍有效式是通過賦值確定的。賦值與真值賦值之間的關(guān)系密切，但兩者也存在著很大的區(qū)別。賦值需要一個(gè)結(jié)構(gòu)模型I和一個(gè)指派B ,而真值賦值就是1或0。任一賦值都會導(dǎo)出一個(gè)真值賦值，即經(jīng)過語義解釋后的公式都是有真假的，但并非

46、每一真值賦值都是由于某個(gè)賦值而引出。請看公式：xF(x) f xF(x)這是一個(gè)普遍有效式，在任何賦值下都是永真的。但當(dāng)對 xF(x)賦以真值真，對xF(x) 賦以真值假時(shí)，它就是假的。因而不是重言式。3. 邏輯后承公式A是公式集r的邏輯后承，當(dāng)且僅當(dāng)對每一賦值v,如果v卜，則v卜A,記作r卜Ao若只有一個(gè)公式 B,則B A 是普遍有效式，即卜B-A若r是空的公式集，則 A是普遍有效 式。邏輯后承與重言后承的關(guān)系類似普遍有效式與重言式的關(guān)系：若A是r的重言后承，則 A必是r的邏輯后承，但反之不必然成立。例如xF( x) 是xF( x) 的邏輯后承，但不是重言后承。下面引入邏輯等值的概念。對于任

47、意 L1的公式A和B, A邏 輯等值于B,當(dāng)且僅當(dāng)A卜B,并且B kA,記作A Bo若A和B 是重言等值的，則 A與B是邏輯等值的，反之則不必然成立。4 代入和字母變易代入和字母變易是一階謂詞邏輯的兩種基本的語義推理方法。一、代入在命題邏輯中，我們討論了重言式代入定理和代入規(guī)則，即對一個(gè)重言式中的命題變元作代入后，可以得到另一個(gè)重言式。重言式代入定理和代入規(guī)則在謂詞邏輯中同樣適用。本章將在此基礎(chǔ)上， 著重討論另一種代入規(guī)則對一階謂詞邏輯項(xiàng)和公式中的自由變元作代入，從而得到新的項(xiàng)和公式。對一個(gè)普遍有效式中的自由變元作代入，所得的公式仍然是一個(gè)普遍有效式。但與命題邏輯不同，謂詞邏輯中的代入規(guī)則適用

48、于任何含有自由變元的公式或項(xiàng)。1. 對項(xiàng)中自由變元的代入對項(xiàng)中自由變元的代入可定義為：定義4.1 令s和t是Li的嘰s(x)表示x是項(xiàng)s中的自由 變元， s(x/t) 表示用 t 去替換 x 在 s 中的每一出現(xiàn)而得到的新項(xiàng)。則 s(x/t) 包括如下三種情形:(l)s是個(gè)體變元。此時(shí)分兩種情況，若 s=x,則s(x/t尸t;若 s=y， y 是不同于x 的變元，則s(x/t)=y 。(2)s是個(gè)體常元。設(shè)s=a,則s(x/t尸a 。(3)s 是f(s 1, S2,，sn),其中f是一 n元函數(shù)符，si, S2,Sn 都是項(xiàng)。s(x/t)=f(s 1, (x/t) , S2(x/t),，Sn(

49、x/t)。下面討論對s(x/t) 的賦值。 設(shè)有一賦值v， v(s(x/t) 是說，在把 s 中的 x 替換成 t 后， 再用 v 對 s 進(jìn)行賦值。例如， 設(shè) s=f(x) ，則 v(s(x/t)=v(f(t)=v(f)(v(t)。為了便于書寫，以下也可把 V(v(t)寫成 fv(t v),把 v(s(x/t) 寫成 s(x/t) vo定理 4.1 設(shè) s 和 t 是項(xiàng)， x 是一個(gè)體變元，v 是一賦值，則(為書寫方便，以下tv用u來表示) s(x/t)v=sv( x/u) 。為了證明本定理，首先來討論賦值v(x/t) 。 v(x/t) 除了對 x指派 t 為值時(shí)， 與 v 完全一致。也就是

50、說，除了對個(gè)體變元x 外，v(x/t) 與 v 對其他個(gè)體變元、個(gè)體常元、函數(shù)變元以及謂詞變元賦以完全相同的值。如果-個(gè)項(xiàng)s(或公式A)中沒有個(gè)體變元x, 則 sv (x/t) =sv, v(x/t)(A)=v(A)。賦值 v(x/x v)對 x 指派 xv為值，因此，顯然有v(x/x v) 即是v。以下證明定理4.1 。證明用歸納法，施歸納于項(xiàng)s 的結(jié)構(gòu) :(l)s 是一個(gè)體變元，此時(shí)有兩種情況。設(shè)s=x， 則 s(x/t)=t ，故 s(x/t) v=tvo 而 s(x/t) v=xv (x/u)o 所以，當(dāng) s=x 時(shí)，s(x/t)v=sv( x/u ) 。 設(shè)s=y， y 是不同于x

51、的個(gè)體變元，則 s(x/t)=y ， 故 s(x/t) v=yvo 而 Sv (x/u)=yv (x/u)=y vo 所以，當(dāng) s=y 時(shí)，s(x/t) v=sv(2)s是一個(gè)體常元。設(shè) s=a,則 s(x/t尸a ,故 s(x/t) v=av。而 sv (x/u)=* " =a vo 所以 s(x/t)v=sv (x/u)。(3)s 是f(s i, S2,，Sn),其中f是一 n元函數(shù)符，si, S2,，Sn 都是項(xiàng)。據(jù)定義，S(x/t)=f(S i(x/t) , S2(x/t),，Sn(x/t)s(x/t) v=fv(Si(x/t) v, S2(x/t)v,s1(x/t)vv(

52、x/u )=Siv v ( x/u )S2(x/t) =S2s(x/t) v=fv(Si(x/t) v, S2(x/t)v,=fv(x/u )v( x/u )v( x/u )( Si ， S2=(f (Si, S2,，Sn)v ( x/u )= SSn(x/t)v) 。根據(jù)歸納假設(shè)，Sn(x/t)v=Snv( x/u) 。所以Sn(x/t)v)v ( x/u )Sn )v( x/u )綜合 (i) 、 ( 2) 、 (3) ，定理 4.i 成立。2. 對公式中自由變元的代入一個(gè)體變元在公式中可自由出現(xiàn)，也可約束出現(xiàn)。代入只對公式中自由變元施行。用一個(gè)項(xiàng) t去對一個(gè)公式A中自由變元x 作代入的條

53、件是:t須對x在A中的每一出現(xiàn)都作代入，并且 t 對 A 中的 x 而言是自由的，否則代入就是不正確的。所謂t 對 A中的x是自由的，就是說用t去替換x在A中的每一出現(xiàn)，必須 沒有改變x 自由變元的身份，代入后的t 在原來 x 出現(xiàn)的每一位置都是自由的。特別地，若t是一常項(xiàng)a,則t對A中任意自由31變元都是自由的。例如，公式 x(F(x) -G (z),可以用y去代入其中的z 而得到x(F(x) -G(y),二者的含義完全相同，這種代入是正 確的。但是，不可以用x去代入其中的z,因?yàn)閤對z而言不是自由的，當(dāng)用x去替換z而得到x(F(x) -G(x)時(shí)，原來G(z) 中的 z 是自由的，而在代入

54、后的公式中被量詞約束了，因此，這 種代入是錯(cuò)誤的。定義4.2 用項(xiàng)t去代入公式A中的x而得到的新公式記作 A(x/t) ，可定義如下：(1) 如果A是原子公式F(Si, S2,，Sn),則t對A中的x 而言是自由的，A(x/t)=F(s i(x/t) , S2(x/t)，Sn(x/t)o(2) 如果A=B,則t對A中的x而言是自由的，當(dāng)且僅當(dāng)t對 B 中的 x 而言是自由的。若t 對 B 中的 x 而言是自由的，則A(x/t)=(B)(x/t尸 (B(x/t)。(3) 如果A=BC,則t對A中的x而言是自由的，當(dāng)且僅當(dāng) t對B和C中的x而言都是自由的。若t對B和C中的x而言都 是自由的，則 A(x/t)=(B f C)(x/t尸B(x/t)C(x/t)。(4) 如果A= yB,那么t對A中的x而言是自由的，當(dāng)且僅當(dāng)滿足下列條件之一:A中的x不是自由的。A中的x是自由的(此時(shí)顯然有x中y),并且t對于B中的 x 是自由的，y 不在 t 中出現(xiàn)。若 是 情 形 ， 則 A(x/t)=A