《離散數(shù)學(xué)》第2章 一階邏輯

第2章一階邏輯2.1一階邏輯的基本概念2.2一階邏輯公式及解釋2.3等值演算和前束范式2.4一階邏輯推理理論2.5例題選解習(xí)題二凡人必有死

蘇格拉底是人

所以，蘇格拉底必死

蘇格拉底三段論:p:凡人必有死q:蘇格拉底是人r:所以，蘇格拉底必死

(p∧q)→r2.1一階邏輯的基本概念首先我們將簡(jiǎn)單命題的結(jié)構(gòu)分解成個(gè)體和謂詞。

個(gè)體（客體）我們討論的對(duì)象?？梢允蔷唧w的，也可以是抽象的。

個(gè)體域（論域）個(gè)體所構(gòu)成的非空集合。

全總個(gè)體域（無(wú)限域）包含宇宙中一切事物的個(gè)體域。

謂詞簡(jiǎn)單命題中，表示一個(gè)個(gè)體的性質(zhì)或多個(gè)個(gè)體間的關(guān)系的詞。之所以稱(chēng)之為謂詞，是因?yàn)橹^詞和個(gè)體詞一起構(gòu)成了簡(jiǎn)單命題中的主謂結(jié)構(gòu)。如：

小王是學(xué)生。

3是素?cái)?shù)。

2整除6。

2加3等于5。上面這些簡(jiǎn)單命題中，小王、2、3、5、6均是個(gè)體，"……是學(xué)生"，"……是素?cái)?shù)"，"……整除……"，"……加……等于……"均是謂詞。前兩個(gè)謂詞描述的是一個(gè)個(gè)體的性質(zhì)，稱(chēng)為一元謂詞；第三個(gè)表示兩個(gè)個(gè)體之間的關(guān)系，稱(chēng)為二元謂詞；第四個(gè)表示三個(gè)個(gè)體之間的關(guān)系，稱(chēng)為三元謂詞。以此類(lèi)推，我們將描述n（n≥2）個(gè)個(gè)體之間關(guān)系的謂詞稱(chēng)為n元謂詞。通常用大寫(xiě)字母F、G、H（可加下標(biāo)）來(lái)表示謂詞。

F表示"……是學(xué)生"；

G表示"……整除……"；

H表示"……加……等于……"。這時(shí)F、G、H表示的是具體的謂詞，稱(chēng)為謂詞常元，否則，稱(chēng)為謂詞變?cè)?。顯然，單獨(dú)的一個(gè)謂詞（即使是謂詞常元）并不能構(gòu)成一個(gè)完整的句子，必須以個(gè)體詞取代"……"方能構(gòu)成一個(gè)句子。通常我們用小寫(xiě)的英文字母a、b、c（可加下標(biāo)）等表示具體的個(gè)體，稱(chēng)為個(gè)體常元。一般地，我們用F（x）表示"x是學(xué)生"，其中的x稱(chēng)為個(gè)體變?cè)ê?jiǎn)稱(chēng)變?cè)?，亦稱(chēng)個(gè)體詞）。類(lèi)似，我們也可用G（x，y）表示"x整除y"。符號(hào)化"小王是學(xué)生"a:小王。F（x）表示"x是學(xué)生"F（a），"小王是學(xué)生"我們稱(chēng)由謂詞符和變?cè)M成的符號(hào)串為命題函數(shù)。之所以稱(chēng)為命題函數(shù)，是因?yàn)槊}函數(shù)不是命題，只有謂詞為常元并將其中的變?cè)跃唧w的個(gè)體后，才能構(gòu)成命題。例如："G（x，y）：x整除y。"并不是命題，但若取a：2，b：6，則G（a，a），G（a，b）以及G（b，a）均是命題，前兩個(gè)是真命題，第三個(gè)是假命題。G（a，a）、G（a，b）等稱(chēng)為0元謂詞，它們不含個(gè)體變?cè)?元謂詞即命題。

【例2.1.1】將下列語(yǔ)句形式化為謂詞邏輯中的命題或命題函數(shù)。

（1）小王是二年級(jí)大學(xué)生。（2）小王是李老師的學(xué)生。（3）如果x≤y且y≤x，則x=y。解（1）令F（x）：x是大學(xué)生；G（x）：x是二年級(jí)的；a：小王。則原句形式化為：

F（a）∧G（a）（2）令F（x，y）：x是y的學(xué)生；a：小王；b：李老師。則原句形式化為：

F（a，b）。（3）令F（x，y）：x≤y；G（x，y）：x=y。式化為：（F（x，y）∧F（y，x））→G（x，y）。前兩句均是命題，第三句因?yàn)楹凶冊(cè)允敲}函數(shù)。但實(shí)際上我們知道，只要將x、y限制在數(shù)的范圍內(nèi)，第三句是定理，是永真的。這就涉及到了個(gè)體域。在簡(jiǎn)單命題中，常有一些表示數(shù)量關(guān)系的詞語(yǔ)，諸如"所有的"、"有一些"等等，用來(lái)表示論域中的全體或部分個(gè)體，在謂詞邏輯中，我們用量詞把它們形式化。

1．全稱(chēng)量詞""

全稱(chēng)量詞用來(lái)表示個(gè)體域中的全體。表自然語(yǔ)言中的"所有的"、"任意的"、"每一個(gè)"等等。如：

"任意偶數(shù)均能被2整除。"

句子可改寫(xiě)成：“在偶數(shù)集合中的任意的x，x能被2整除?！比€(gè)體域?yàn)榕紨?shù)集，用F(x)表示“x能被2整除”，用x表示“任意的x”，則原句形式化為：xF(x)。

2．存在量詞“"

存在量詞用來(lái)表示論域中的部分個(gè)體。表自然語(yǔ)言中的"存在著一些"、"至少有一個(gè)"、"有"等等。如：

"我們班有人會(huì)吸煙。"

句子可改寫(xiě)成："在我們班有一些x，x會(huì)吸煙。"

取個(gè)體域?yàn)椤拔覀儼嗟耐瑢W(xué)”，用G（x）表示“x會(huì)吸煙”，用x表示"有些x"，則原句形式化為：

xG(x)以上形式化過(guò)程中，均指定了個(gè)體域，不同的個(gè)體域，可能導(dǎo)致命題真值的不同。為統(tǒng)一起見(jiàn)，均取個(gè)體域?yàn)槿倐€(gè)體域，為此引入特性謂詞來(lái)限制變?cè)淖兓秶?。【?.1.2】在全總個(gè)體域中形式化下列命題：（1）任意的偶數(shù)均能被2整除。（2）我們班有人吸煙。解（1）引入特性謂詞H（x）：x是偶數(shù)。

"任意的偶數(shù)均能被2整除"的涵義是：全總個(gè)體域中有子集--偶數(shù)集，該子集中的每個(gè)元素均具有一種性質(zhì)，世間萬(wàn)物，只要你屬于這個(gè)子集，你就必然具有這種性質(zhì)，所以是蘊(yùn)含式。特性謂詞以蘊(yùn)含式的前件加入。則原句可形式化為：x（H（x）→F（x））（2）引入特性謂詞W（x）：x是我們班的人。

"我們班有人吸煙"的涵義可以這樣理解：在宇宙間的萬(wàn)物（全總個(gè)體域）中，有一個(gè)子集--我們班，還有另一個(gè)子集--吸煙的人。強(qiáng)調(diào)的是既在我們班，又吸煙的的人，所以是兩個(gè)子集的交集。特性謂詞用合取項(xiàng)加入。則原句可形式化為：

x（W（x）∧G（x））

【例2.1.3】將下列命題形式化為一階邏輯中的命題：（1）沒(méi)有不犯錯(cuò)誤的人。（2）人總是要犯錯(cuò)誤的。解設(shè)M（x）：x是人，F(xiàn)（x）：x犯錯(cuò)誤。則原句形式化為：（1）x（M（x）∧

F（x））（2）x（M（x）→F（x））【例2.1.4】將下列命題形式化為一階邏輯中的命題：（1）所有的病人都相信醫(yī)生。（2）有的病人相信所有的醫(yī)生。（3）有的病人不相信某些醫(yī)生。（4）所有的病人都相信某些醫(yī)生。解設(shè)F（x）：x是病人，G（x）：x是醫(yī)生，H（x，y）：x相信y。（1）本命題的意思是：對(duì)于每一個(gè)x，如果x是病人，那么對(duì)于每一個(gè)y，只要y是醫(yī)生，x就相信y。因此，本命題符號(hào)化為：

x（F（x）→y（G（y）→H（x，y）））或

xy（（F（x）∧G（y））→H（x，y））（2）本命題的意思是：存在著這樣的x，x是病人且對(duì)于每一個(gè)y，只要y是醫(yī)生，x就相信y。因此，本命題符號(hào)化為：

x（F（x）∧y（G（y）→H（x，y））x（F（x）→y（G（y）∧H（x，y））)（3）本命題的意思是：存在著這樣的x和y，x是病人，y是醫(yī)生，x不相信y。因此，本命題符號(hào)化為：

x

y（F（x）∧G（y）∧H（x，y））或

x（F（x）∧y（G（y）∧H（x，y）））（4）本命題的意思是：對(duì)于每個(gè)x，如果x是病人，就存在著醫(yī)生y，使得x相信y。因此，本命題符號(hào)化為：補(bǔ)充：（1）是學(xué)生就得考試。（2）不勞動(dòng)者不得食。（3）有些花很香，但并非所有的花都香。解（1）設(shè)F(x):x是學(xué)生,G(x):x得考試.

（2）設(shè)F(x):x是勞動(dòng)者，G(x):x得到食物。（3）設(shè)F(x):x是花，G(x):x很香

2.2一階邏輯公式及解釋上一節(jié)中我們?cè)谝浑A邏輯中符號(hào)化得到的命題和命題函數(shù)就是一階邏輯公式(謂詞公式)。至此，在一階邏輯中，我們已涉及到以下這些符號(hào)：

(1)個(gè)體變?cè)?hào)：用小寫(xiě)的英文字母x，y，z（或加下標(biāo)）…等表示。

(2)個(gè)體常元符號(hào)：用小寫(xiě)的英文字母a，b，c（或加下標(biāo)）…等表示。

(3)運(yùn)算符號(hào)：用小寫(xiě)的英文字母f，g，h（或加下標(biāo)）…等表示。

(4)謂詞符號(hào)：用大寫(xiě)的英文字母F，G，H（或加下標(biāo)）…等表示。

(5)量詞符號(hào)：，。

(6)聯(lián)結(jié)詞符號(hào)：，∧，∨，→，。

(7)逗號(hào)和圓括號(hào)。一個(gè)符號(hào)化的命題是一串由這些符號(hào)所組成的表達(dá)式，但并不是任意一個(gè)由此類(lèi)符號(hào)組成的表達(dá)式就對(duì)應(yīng)于一個(gè)命題。所以要給出嚴(yán)格的定義。定義2.2.1項(xiàng)

(1)任何一個(gè)個(gè)體變?cè)騻€(gè)體常元是項(xiàng)。

(2)如果f是n元運(yùn)算符，t1，t2，…，tn是項(xiàng)，則f（t1，t2，…，tn）是項(xiàng)。

(3)所有的項(xiàng)由且僅由有限次使用（1）、（2）所生成。例如，x，a，f（x，a），f（g（x，a，b），h（x））均是項(xiàng)，其中h、f和g分別是一元、二元和三元運(yùn)算符。而h（a，b）不是項(xiàng)，因?yàn)閔是一元運(yùn)算符，但h（a，b）中h的后面跟了兩個(gè)項(xiàng)，同樣g（x）也不是項(xiàng)。

定義2.2.2

若F是n元謂詞，t1，t2，…，tn是項(xiàng)，則F（t1，t2，…，tn）是原子公式。由定義可知，原子命題是不含量詞和聯(lián)結(jié)詞的謂詞公式。同命題邏輯中的情況相似，這里也可以用聯(lián)結(jié)詞將原子公式復(fù)合成分子公式。（事實(shí)上我們已經(jīng)這樣做了。）定義2.2.3

一階邏輯中的合式公式（wff）的遞歸定義：（1）原子公式是合式公式。（2）若A是合式公式，則（A）也是合式公式。（3）若A、B均是合式公式，則（A∧B）、（A∨B）、（A→B）和（A

B）也均是合式公式。（4）若F是合式公式，x是個(gè)體變?cè)瑒txF、xF也是合式公式。（5）只有有限次按規(guī)則（1）～（4）構(gòu)成的謂詞公式才是合式公式。在謂詞公式中，形如xA(x)或xA(x)的部分叫做公式的約束部分，其中x稱(chēng)量詞的指導(dǎo)變?cè)ㄗ饔迷紸(x)稱(chēng)量詞的轄域（作用域）。在轄域中，指導(dǎo)變?cè)獂的一切出現(xiàn)稱(chēng)為x在公式中的約束出現(xiàn)，且稱(chēng)x為約束變?cè)ㄊ芰吭~的約束），在公式中除約束變?cè)酝馑霈F(xiàn)的變?cè)Q(chēng)自由出現(xiàn)，且稱(chēng)x為自由變?cè)?/p>

【例2.2.1】考察下列一階公式中每個(gè)量詞的轄域及每個(gè)變?cè)某霈F(xiàn)是約束的或自由的。（1）x（F（x）→yH（x，y））（2）x(F(x)→G(x))∨x(F(x)→H(x))

（3）xF（x）∧G（x）

解（1）全稱(chēng)量詞x的轄域是（F（x）→yH（x，y）），其中x的兩次出現(xiàn)均是約束出現(xiàn)，是約束變?cè)?；存在量詞y的轄域是H（x，y），其中y的出現(xiàn)是約束的，y是約束變?cè)?。?）第一個(gè)全稱(chēng)量詞的轄域是（F（x）→G（x）），其中x的出現(xiàn)均是約束出現(xiàn)，是約束變?cè)?；第二個(gè)全稱(chēng)量詞的轄域是（F（x）→H（x）），其中x的出現(xiàn)均是約束出現(xiàn)，是約束變?cè)＃?）唯一的存在量詞的轄域是F（x），其中x的出現(xiàn)是約束出現(xiàn)，是約束變?cè)?；而x的第三次出現(xiàn)是在G（x）中的出現(xiàn)，是自由出現(xiàn)，第三個(gè)x是自由變?cè)?。由例題可見(jiàn)，在一個(gè)一階邏輯公式中，某個(gè)個(gè)體變?cè)ǚ┑某霈F(xiàn)可以既是約束的，又是自由的，如（3）中的x。另外，同一個(gè)變?cè)ǚ┘词苟际羌s束的，也可能是在不同的量詞轄域中出現(xiàn)，如（2）中的x。為了避免混淆，可對(duì)約束變?cè)M(jìn)行換名，使得一個(gè)變?cè)ǚ┰谝粋€(gè)公式中只以一種形式出現(xiàn)。換名規(guī)則（1）將量詞的作用元及其轄域中所有同符號(hào)的變?cè)靡粋€(gè)新的變?cè)?。?）新的變?cè)窃街兴鶝](méi)有出現(xiàn)的。（3）用（1）、（2）得到的新公式與原公式等值。【例2.2.2】對(duì)公式

x（F（x）→G（x，y））∧H（x，y）換名，下面的幾種做法中哪個(gè)是正確的？（1）z（F（z）→G（z，y））∧H（x，y）（2）y（F（y）→G（y，y））∧H（x，y）（3）z（F（z）→G（x，y））∧H（x，y）解只有（1）是正確的。（2）的換名違反了規(guī)則（2），使得G（x，y）中的y的出現(xiàn)改變了性質(zhì)。（3）的換名違反了規(guī)則（1），使得G（x，y）中的x的出現(xiàn)改變了性質(zhì)。對(duì)公式中自由出現(xiàn)的變?cè)部蓳Q符號(hào)，稱(chēng)為代替，同樣需要遵守下面的規(guī)則：代替規(guī)則（1）將公式中所有同符號(hào)的自由變?cè)眯碌淖冊(cè)鎿Q。（2）新的變?cè)窃街兴鶝](méi)有出現(xiàn)的。（3）用（1）、（2）得到的新公式與原公式等值。

【例2.2.3】對(duì)公式

x（F（x）→G（x，y））∧H（x，y）做代替，下面的幾種做法中哪個(gè)是正確的？（1）x（F（x）→G（x，y））∧H（z，y）（2）x（F（x）→G（x，z））∧H（u，y）（3）z（F（z）→G（x，y））∧H（y，y）定義2.2.4

沒(méi)有自由變?cè)墓椒Q(chēng)為閉式。如例2.2.1中的（1）、（2）兩式均是閉式，而（3）不是閉式。事實(shí)上，僅就個(gè)體變?cè)裕杂勺冊(cè)攀钦嬲淖冊(cè)?，而約束變?cè)辉诒砻嫔鲜亲冊(cè)?，?shí)際上并不是真正意義上的變?cè)?。換言之，含有自由變?cè)墓皆诮忉尯笕允敲}函數(shù)，還需賦值方成命題，而不含自由變?cè)拈]式一旦給出解釋就成了命題。

定義2.2.5

一個(gè)解釋I由以下四部分組成：（1）為個(gè)體域指定一個(gè)非空集合DI。（2）為每個(gè)個(gè)體常元指定一個(gè)個(gè)體。（3）為每個(gè)n元運(yùn)算符指定DI上的一個(gè)n元運(yùn)算。（4）為每個(gè)n元謂詞符指定DI上的一個(gè)n元謂詞。

【例2.2.4】

設(shè)f，g均為二元運(yùn)算符，E，L均為二元謂詞符，給定解釋I如下：個(gè)體域DI為自然數(shù)集合；

f（x，y）=x+y，g（x，y）=x·y，a=0；

E（x，y）：x=y，L（x，y）：x＜y。求下列公式在解釋I下的真值。（1）x

yL（x，y）（2）x(E（f（x，a），x）∧L(g（x，a），a））（3）y（E（x，y）∨L（x，y））（4）E（f（x，a），g（x，a））解(1)式中沒(méi)有自由變?cè)情]式，在解釋I下的意義是：對(duì)于每一個(gè)自然數(shù)x，均存在著自然數(shù)y，使得x＜y。顯然這是一個(gè)真命題。（2）式中也沒(méi)有自由變?cè)?，是閉式，在解釋I下的意義是：對(duì)于每一個(gè)自然數(shù)x，x+0=x并且x·0＜0。0＜0不真，所以這是一個(gè)假命題。（3）式中x是自由變?cè)?，不是閉式，在解釋I下的意義是：對(duì)于每一個(gè)自然數(shù)y，x=y或者x＜y。因?yàn)閤取0時(shí)，原式為真；x取1時(shí)，原式為假，所以這是命題函數(shù)，而非命題。（4）式中x是自由變?cè)?，不是閉式，在解釋I下的意義是：x+0=x·0。因?yàn)閤取0時(shí)，原式為真；x非0時(shí)，原式為假，所以這是命題函數(shù)，而非命題。

如上所言，含有自由變?cè)墓皆诮忉尯笕允敲}函數(shù)，還需賦值方成命題。

定義2.2.6賦值υ是建立在解釋I上的函數(shù)，且有：（1）υ（xi）=

，

即對(duì)自由變?cè)獂i指派一個(gè)DI中的個(gè)體

。（2）υ(f(t1，t2，…，tn))=(υ(t1)，υ（t2），…，υ（tn）），其中fi是I對(duì)f的解釋?zhuān)瑃i（i=1，2，…，n）是項(xiàng)。

【例2.2.5】設(shè)f，g均為二元運(yùn)算符，E，L均為二元謂詞符，給定解釋I及賦值υ如下：個(gè)體域DI為自然數(shù)集合；

f（x，y）=x+y，g（x，y）=x·y，a=0；

E（x，y）：x=y，L（x，y）：x＜y。

υ1（x）=0，υ2（x）=1。求下列公式在解釋I和賦值分別為υ1，υ2下的真值。（1）y（E（x，y）∨L（x，y））（2）E（f（x，a），g（x，a））（3）

xE（g（x，a），a）解(1)式在解釋I及賦值υ1下的含義是：對(duì)于每個(gè)自然數(shù)y，0=y或者0＜y。即0是最小的自然數(shù)，這是真命題。在解釋I及賦值υ2下的含義是：對(duì)于每個(gè)自然數(shù)y，1=y或者1＜y。即1是最小的自然數(shù)，這是假命題。

(2)式在解釋I及賦值υ1下的含義是：0+0=0·0，這是真命題。在解釋I及賦值υ2下的含義是：1+0=1·0，這是假命題。

(3)式中不含自由變?cè)瑹o(wú)需考慮賦值。在解釋I下的意義是：對(duì)于每一個(gè)自然數(shù)x，x·0=0。這是真命題。

在上一節(jié)我們?cè)岬竭^(guò)，當(dāng)個(gè)體域?yàn)橛懈F集DI={a1，a2，…，an}時(shí)：

xF（x）F（a1）∧F（a2）∧…∧F（an）

xG（x）G（a1）∨G（a2）∨…∨G（an）因此，當(dāng)解釋I中的個(gè)體域D為有窮集時(shí)，可先消量詞再求真值。

【例2.2.6】

設(shè)解釋I為：DI={2，3}，f（2）=3，f（3）=2，

F（2，2）=F（2，3）=0，F(xiàn)（3，2）=F（3，3）=1。在I下消去下列公式的量詞并求真值。（1）F（2，f（2））∧F（3，f（3））（2）x

yF（y，x）

（3）x(F(x,f(x))→yF(f(x),f(y)))解（1）式中不含量詞，所以直接求真值。

F（2，f（2））∧F（3，f（3））

F（2，3）∧F（3，2）

0∧10

(2)x

yF（y，x）

x（（F（2，x）∨F（3，x）））

（F（2，2）∨F（3，2））∧（F（2，3）∨F（3，3））

（0∨1）∧（0∨1）

1∧11(3)

x(F(x,f(x))→yF(f(x),f(y)))(F(2,f(2))→yF(f(2),f(y)))∧(F(3,f(3))→yF(f(3),f(y)))

(F(2,f(2))→(F(f(2),f(2))∧F(f(2),f(3))))∧(F(3,f(3))→(F(f(3),f(2))∧F(f(3),f(3))))

(F(2,3)→(F(3,3)∧F(3,2)))∧(F(3,2)→(F(2,3)∧F(2,2)))(0→(1∧1))∧(1→(0∧0))(0→1)∧(1→0)0

定義2.2.7一階邏輯公式的分類(lèi)：永真式（邏輯有效式）在任何解釋I及I的任何賦值下均為真的一階公式；永假式（矛盾式）在任何解釋I及I的任何賦值下均為假的一階公式；可滿足式至少有一種解釋和一種賦值使其為真的一階公式。判定一個(gè)公式A不是永真式，只需找到一個(gè)解釋I和I下的一個(gè)賦值υ，使A在I和υ下為假；判定一個(gè)公式A不是永假式，只需找到一個(gè)解釋I和I下的一個(gè)賦值υ，使A在I和υ下為真；要判定一個(gè)公式A是可滿足式，只需找到一個(gè)解釋I和I下的一個(gè)賦值υ，使A在I和υ下為真，再找到一個(gè)解釋I和I下的一個(gè)賦值υ，使A在I和υ下為假?！纠?.2.7】討論下列公式的類(lèi)型：（1）xF（x）→xF（x）（2）x

G（x）∧xG（x）（3）x

yF（x，y）→yxF（x，y）解（1）公式xF（x）→xF（x）在任何解釋I下的含義是：如果個(gè)體域DI中的每個(gè)元素x均有性質(zhì)F，則DI中的某些元素x必有性質(zhì)F。前件xF（x）為真時(shí)，后件xF（x）永遠(yuǎn)為真，所以公式

xF（x）→xF（x）是永真式。（2）公式x

G（x）∧xG（x）在任何解釋I下的含義是：個(gè)體域DI中的每個(gè)元素x均不具有性質(zhì)G，且DI中的某些元素x具有性質(zhì)G。這是兩個(gè)互相矛盾的命題，不可能同時(shí)成立，所以公式

x

G（x）∧xG（x）是永假式。（3）公式x

yF（x，y）→yxF（x，y）既不是永真式，也不是永假式。由于這是閉式，故無(wú)需考慮賦值，只要給出一個(gè)使其成真的解釋和一個(gè)使其成假的解釋即可。

定義2.2.8

設(shè)A（p1，p2，…，pn）是含命題變?cè)猵1，p2，…，pn的命題公式，B（B1，B2,…，Bn）是以一階公式B1，B2,…，Bn分別代替p1，p2,…，pn在A中的所有出現(xiàn)后得到的一階公式，稱(chēng)B是A的一個(gè)代換實(shí)例。例如，F(xiàn)（x）→G（y），

xF（x）→

yG（y）均是命題公式p→q的代換實(shí)例，也是p的代換實(shí)例。顯然有以下定理。定理2.2.1命題邏輯永真式的任何代換實(shí)例必是一階邏輯的永真式。同樣，命題邏輯永假式的任何代換實(shí)例必是一階邏輯的永假式。證明略。定理2.2.1為我們提供了一大類(lèi)一階邏輯的有效式。因此，判斷一個(gè)一階邏輯公式是否是永真式或永假式，我們既可以用定義2.2.7（如例2.2.7），也可以用其是否是命題邏輯的永真式或永假式的代換實(shí)例來(lái)判斷。

2.3等值演算和前束范式定義2.3.1設(shè)A與B是公式，若A

B是永真式，則稱(chēng)A與B等值，或稱(chēng)A與B邏輯等價(jià)，記作A

B。顯然，A

B當(dāng)且僅當(dāng)在任何解釋I和I中的任意賦值υ下，A與B有相同的真值。即在I和υ下，A為真當(dāng)且僅當(dāng)B為真，或者，A為假當(dāng)且僅當(dāng)B為假。同時(shí)，要證明兩個(gè)公式不等值，只需找到一個(gè)解釋I和I中的一個(gè)賦值υ，使得兩個(gè)公式在I和υ下，一個(gè)為真，另一個(gè)為假。

【例2.3.1】判斷公式F（x）和F（y）是否等值。解F（x）表示"x具有性質(zhì)F"，F(xiàn)（y）表示"y具有性質(zhì)F"，容易看出兩個(gè)意思并不一樣。取解釋I：個(gè)體域D為整數(shù)集，F(xiàn)（x）：x是奇數(shù)，賦值υ（x）=1，υ（y）=2，則在I和υ下，F(xiàn)（x）為真，F(xiàn)（y）為假。因此，F(xiàn)（x）與F（y）不等值。

【例2.3.2】判斷公式x

yF（x,y）與公式

yxF（x，y）是否等值。解直接觀察是不等值的。由于兩個(gè)公式均是閉式，所以只需給出一個(gè)解釋I，使其在I下一個(gè)為真，另一個(gè)為假。取解釋I：D為鞋子的集合，F(xiàn)（x，y）：x與y能配成一雙。則在I下，x

yF（x,y）表示“每一只鞋子均有另一只鞋子能與其配成一雙”是真命題，而公式

yxF（x，y）表示“有這樣的鞋子能與任何一只鞋子配成一雙”是假命題。因此，兩個(gè)公式

x

yF（x,y）與yxF（x，y）不等值。量詞轉(zhuǎn)換律（A（x）是任一一階公式）

xA（x）x

A（x）

（1）

xA（x）

x

A（x）

（2）量詞轄域擴(kuò)縮律（A（x）是任一一階公式，B是任一不含x的一階公式）

xA（x）∧B

x（A（x）∧B）

（1）

xA（x）∨B

x（A（x）∨B）

（2）

xA（x）∧B

x（A（x）∧B）

（3）

xA（x）∨B

x（A（x）∨B）

（4）補(bǔ)充：證明下列兩個(gè)謂詞公式等值證明（1）在任何解釋I和I中的任意賦值υ下，

xA（x）∧B=1當(dāng)且僅當(dāng)xA（x）=1且B=1當(dāng)且僅當(dāng)B=1且對(duì)于DI中的每一個(gè)元素c，A（c）=1當(dāng)且僅當(dāng)對(duì)于DI中的每一個(gè)元素c，A（c）∧B=1當(dāng)且僅當(dāng)x（A（x）∧B）=1（2）在任何解釋I和I中的任意賦值υ下，

xA（x）∨B=0當(dāng)且僅當(dāng)xA（x）=0且B=0當(dāng)且僅當(dāng)B=0且存在DI中的元素c，使得A（c）=0當(dāng)且僅當(dāng)存在DI中的元素c，使得A（c）∨B=0當(dāng)且僅當(dāng)x（A（x）∨B）=0另外，下面的等值式也稱(chēng)作量詞轄域的擴(kuò)縮律。證明（5）（6）、（7）、（8）的證明留給讀者。量詞分配律A（x）、B（x）是任一一階公式）【例2.3.3】證明下列等值式:證明∧(﹁()∨定義2.3.2設(shè)A為一階公式，若A具有如下形式

Q1x1Q2x2…QkxkB

則稱(chēng)A為前束范式。其中Qi（1≤i≤k）是量詞符，xi（1≤i≤k）是變?cè)?，B是不含量詞的公式。在一階邏輯推理中，需要將公式化成前束范式形式，這總是可以辦到的。即任何一個(gè)一階公式均可等值演算成前束范式，化歸過(guò)程如下：（1）消去除、∧、∨之外的聯(lián)結(jié)詞；（2）將否定符移到量詞符后；（3）換名使各變?cè)煌?；?）擴(kuò)大轄域使所有量詞處在最前面。【例2.3.4】將下面公式化成前束范式。解﹁()t﹁

2.4一階邏輯推理理論在一階邏輯中，由前提A1，A2，…，An推出結(jié)論B的形式結(jié)構(gòu)仍然是A1∧A2∧…∧An→B。如果此式是永真式，則稱(chēng)由前提A1，A2，…，An推出結(jié)論B的推理正確，記作A1∧A2∧…∧An

B或者A1，A2，…，AnB，否則稱(chēng)推理不正確。由于謂詞演算是在命題演算的基礎(chǔ)上，進(jìn)一步擴(kuò)大了謂詞與量詞的功能，因此容易想到，命題演算中有關(guān)推理演繹的規(guī)則基本上適用于謂詞演算，即在命題邏輯中的各項(xiàng)推理規(guī)則在一階邏輯推理中仍然適用，當(dāng)然也會(huì)有不少只適用于謂詞演算的概念與規(guī)則。

全稱(chēng)量詞消去規(guī)則（簡(jiǎn)稱(chēng)UI規(guī)則）規(guī)則成立的條件：（1）t是任意個(gè)體變項(xiàng)或常項(xiàng)。（2）A（t）中約束變?cè)獋€(gè)數(shù)與A（x）中約束變?cè)獋€(gè)數(shù)相同。全稱(chēng)量詞引入規(guī)則（簡(jiǎn)稱(chēng)UG規(guī)則）規(guī)則成立的條件：（1）A（t）在任何解釋I及I中對(duì)t的任何賦值下均為真。（2）x不在A（t）中約束出現(xiàn)。存在量詞引入規(guī)則（簡(jiǎn)稱(chēng)EG規(guī)則）規(guī)則成立的條件：（1）c是特定的個(gè)體常元。（2）x不在A（c）中出現(xiàn)。規(guī)則成立的條件：（1）c是使A（c）為真的特定的個(gè)體常元。（2）xA（x）是閉式，且c不在A（x）中出現(xiàn)。特別需要注意的是，使用這些規(guī)則的條件非常重要，如在使用過(guò)程中違反了這些條件就可能導(dǎo)致錯(cuò)誤的結(jié)論。存在量詞消去規(guī)則（簡(jiǎn)稱(chēng)EI規(guī)則）

【例2.4.1】證明推理"所有的自然數(shù)均是實(shí)數(shù)，3是自然數(shù)，因此，3是實(shí)數(shù)。"正確。解設(shè)N（x）：x是自然數(shù)，R（x）：x是實(shí)數(shù)，則推理形式化為：

x（N（x）→R（x）），N（3）R（3）下面進(jìn)行證明。（1）x（N（x）→R（x））前提引入（2）N（3）→R（3）

（1）UI

（3）N（3）

前提引入（4）R（3）（2）（3）假言推理

【例2.4.2】構(gòu)造下面推理的證明：前提x（F（x）→（G（x）∧H（x））），

x（F（x）∧P（x））結(jié)論x（P（x）∧H（x））解（1）x（F（x）→（G（x）∧H（x）））前提引入（2）x（F（x）∧P（x））

前提引入（3）F（c）∧P（c）

(2)EI（4）F（c）→（G（c）∧H（c））

(1)UI（5）F（c）

(3)化簡(jiǎn)（6）G（c）∧H（c）

(4)(5)假言推理（7）P（c）

(3)化簡(jiǎn)（8）H（c）

(6)化簡(jiǎn)（9）P（c）∧H（c）

(7)(8)合取引入（10）x（P（x）∧H（x））

(9)EG

【例2.4.4】設(shè)前提為x

yF（x，y），下面推理是否正確？（1）x

yF（x，y）

前提引入（2）yF（t，y）（1）UI

（3）F（t，c）

（2）EI

（4）xF（x，c）

（3）UG

（5）yxF（x，y）（4）EG解x

yF（x，y）

yxF（x，y）的推理并不正確。取與例2.4.3相同的解釋?zhuān)瑒t由x

yF（x，y）為真，而yxF（x，y）意為"存在著最小實(shí)數(shù)"，是假命題，知推理不正確。之所以出現(xiàn)這樣的錯(cuò)誤，是第（3）步違反了EI規(guī)則成立的條件（2）。

【例2.4.5】構(gòu)造下面推理的證明：前提x（F（x）→G（x））結(jié)論xF（x）→

xG（x）分析本題直接證明很困難，注意到結(jié)論部分是蘊(yùn)涵式，應(yīng)考慮用附加前提證明法。證明（1）x（F（x）→G（x））前提引入（2）xF（x）

附加前提引入（3）F（t）（2）UI（4）F（t）→G（t）

（1）UI（5）G（t）（3）（4）假言推理（6）xG（x）

（5）UG（7）xF（x）→xG（x）

CPP61/【例2.5.6】在謂詞邏輯推理系統(tǒng)中構(gòu)造下面推理的證明：沒(méi)有不守信用的人是可以信賴(lài)的。有些可以信賴(lài)的人是受過(guò)教育的人。因此有些受過(guò)教育的人是守信用的。設(shè)：M(x)：x是人，F(xiàn)(x)：x守信用，G(x)：x可信賴(lài)，

H(x)：x受過(guò)教育。前提：，結(jié)論：課堂練習(xí)：1.將下列公式化成與之等值的前束范式2.符號(hào)化下面語(yǔ)句，并用構(gòu)造證明法證明其推理的正確性。

所有的旅客或者坐頭等艙或者坐經(jīng)濟(jì)艙，每個(gè)旅客當(dāng)且僅當(dāng)他富裕時(shí)坐頭等艙，有些旅客富裕但并非所有的旅客均富裕。因此，有些旅客坐經(jīng)濟(jì)艙。設(shè)F(x):x是旅客，G(x):x坐頭等艙，H(x):x坐經(jīng)濟(jì)艙，S(x):x是富裕的。前提：結(jié)論：2.5例題選解【例2.5.1】在高等數(shù)學(xué)中極限定義為：任給小正數(shù)ε，則存在正數(shù)δ，使得當(dāng)

0＜|x-a|＜ε時(shí)，恒有|f（x）-b|＜δ成立。將上述定義用一階邏輯公式表示。分析因?yàn)楦叩葦?shù)學(xué)中的極限概念是在實(shí)數(shù)范圍內(nèi)給出的，所以不妨設(shè)定個(gè)體域?yàn)閷?shí)數(shù)域。觀察整個(gè)定義，只有一種“小于”關(guān)系，這應(yīng)當(dāng)用一個(gè)二元謂詞表示；而“差的絕對(duì)值”是一個(gè)運(yùn)算，應(yīng)當(dāng)用運(yùn)算符表示。解設(shè)L（x，y）：x＜y，g（x，y）：|x-y|，則定義可表示為：

ε（L（0，ε）→δ（L（0，δ）∧x（（L（0，g（x，a））∧L（g（x，a），δ））→L（g（f（x），b），ε））））

【例2.5.2】在一階邏輯中符號(hào)化自然數(shù)的三條公理。（1）每個(gè)數(shù)都有唯一的一個(gè)數(shù)是它的后繼數(shù)。（2）沒(méi)有一個(gè)數(shù)使0為它的后繼數(shù)。（3）每個(gè)不等于0的數(shù)都有唯一的一個(gè)數(shù)是它的直接先行者。分析在符號(hào)化命題的過(guò)程中，設(shè)定謂詞盡可能少是一個(gè)原則。注意到"x是y的后繼數(shù)"與"y是x的直接先行者"含義相同，所以可用一個(gè)謂詞表示。解設(shè)N（x）：x是自然數(shù)，F(xiàn)（x，y）：x是y的后繼數(shù)，G（x，y）：x=y，則（1）x（N（x）→!y（N（y）∧F（y，x）））（2）x（N（x）∧F（0，x））（3）x（（N（x）∧﹁

G（x，0））

→!y（N（y）∧F（x，y）））

【例2.5.3】將符號(hào)!xF（x）表達(dá)成僅用量詞的形式。分析!xF（x）的意思是：有唯一的x具有性質(zhì)F。即有x具有性質(zhì)F，且若還有y也具有性質(zhì)F，則必有x=y。解

!xF（x）x（F（x）∧y（F（y）→x=y））

【例2.5.4】設(shè)個(gè)體域?yàn)閧a，b，c}，消去下列公式中的量詞。

（1）xF（x）∧yG（y）（2）x

y（F（x）∧G（y））（3）x

y（F（x，y）→G（y））解（1）xF（x）∧

yG（y）

（F(a)∧F(b)∧F(c)）∧（F(a)∨F(b)∨F（c））（2）x

y（F（x）∧G（y））

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

y（F（x，y）→G（y））

y(F(a,y)→G(y))∧y(F(b,y)→G(y))∧y(F(c,y)→G(y))((F(a,a)→G(a))∨(F(a,b)→G(b))∨(F(a,c)→G(c)))∧((F(b,a)→G(a))∨(F(b,b)→G(b))∨(F(b,c)→G(c)))∧((F(b,a)→G(a))∨(F(b,b)→G(b))∨(F(b,c)→G(c)))【例2.5.5】構(gòu)造下面推理的證明：前提xF（x）∨

xG（x）結(jié)論x（F（x）∨G（x））證明（1）xF（x）∨

xG（x）前提引入（2）xy（F（x）∨G（y））（1）置換（3）y（F（t）∨G（y））（2）UI（4）F（t）∨G（t）（3）UI（5）x（F（x）∨G（x））（4）UG習(xí)題二

1．在一階邏輯中將下列命題符號(hào)化。（1）天下烏鴉一般黑。（2）沒(méi)有不散的筵席。（3）閃光的未必是金子。（4）有不是奇數(shù)的素?cái)?shù)。（5）有且僅有一個(gè)偶素?cái)?shù)。（6）貓是動(dòng)物，但并非所有的動(dòng)物都是貓。（7）駱駝都比馬大。（8）有的駱駝比所有的馬都大。（9）所有的駱駝都比某些馬大。（10）有的駱駝比某些馬大。

2．取個(gè)體域?yàn)閷?shí)數(shù)集R，

函數(shù)f在點(diǎn)a處連續(xù)的定義是：f在a點(diǎn)連續(xù)，當(dāng)且僅當(dāng)對(duì)每一個(gè)小正數(shù)ε，都存在正數(shù)δ，使得對(duì)所有的x，若|x-a|＜δ，則|f（x）-f（a）|＜ε。把上述定義用符號(hào)的形式表示。

3．在整數(shù)集中，確定下列命題的真值，運(yùn)算"·"是普通乘法。

（1）x

y（x·y=0）（2）x

y（x·y=1）（3）yx（x·y=1）

（4）yx（x·y=x）

4．給定謂詞如下，試將下列命題譯成自然語(yǔ)言。P（x）：x是素?cái)?shù)。E（x）：x是偶數(shù)。O（x）：x是奇數(shù)。D（x，y）：x整除y。

（1）E（2）∧P（2）（2）x（D（2，x）→E（x））（3）x（E（x）∧D（x，6））（4）x（E（x）→D（2，x））（5）x（E（x）→y（D（x，y）→E（y）））（6）x（O（x）→y（P（y）→D（x，y）））（7）x（P（x）→y（E（y）∧D（x，y）））（8）x（E（x）∧P（x）∧y（E（y）∧P（y）∧x≠y））

5．指出下面公式中的變量是約束的，還是自由的，并指出量詞的轄域。（1）x（F（x）∧G（x））→x（F（x）∧H（x））（2）

xF（x）∧（xG（x）∨（xF（x）→G（x）））（3）x（（F（x）∧G（x，y））→（

xF（x）∧R（x，y，z）））（4）x(yF（x，y，z）

y

xF（x，y，z）6．設(shè)個(gè)體域D={a，b，c}，消去下列各式中的量詞。（1）xF（x）→yF（y）（2）x（F（x）∨

yG（y））（3）

xy（F（x）→G（y））（4）xyF（x，y，z）7．求下列公式在解釋I下的真值。（