離散數(shù)學(xué)課件第2章

1、2.1 一階邏輯的基本概念2.2 一階邏輯公式及解釋2.3 等值演算和前束范式2.4 一階邏輯推理理論2.5 進(jìn)制例題選解習(xí)題二,第二篇 集合論,在命題邏輯中，我們把命題分析到簡單命題為止，而簡單命題是不再進(jìn)行分析的基本元素，因此，當(dāng)推理涉及到簡單命題的結(jié)構(gòu)時，命題邏輯對此是無能為力的。例如下面的推理：　　所有的自然數(shù)都是實數(shù)，3是自然數(shù)。所以，3是實數(shù)。根據(jù)數(shù)學(xué)方面的知識，我們知道這個推理是正確的

2、。然而，在命題邏輯中，這個推理的正確性是無法證明的，這是因為上述推理中的三句話均是簡單命題，且各不相同，如果把它們形式化為命題邏輯中的公式，以p表“所有的自然數(shù)都是實數(shù)”，以q表“3是自然數(shù)”，以r表“3是實數(shù)”，則推理可以寫為：　　　　　　　　　　　(p∧q)r,而(p∧q)→r是一個可滿足式，可知這個推理無法在命題邏輯推理理論中得到證明。另外，命題“所有的自然數(shù)都是實數(shù)”事實上隱含著“0是實數(shù)”，“1是實數(shù)”，“2是實數(shù)”，…，

3、等無窮多個命題，單用一個p表示，很難體現(xiàn)這些?！　∫虼?，為了能夠進(jìn)一步深入地研究推理，需要對簡單命題做進(jìn)一步的分析，將簡單命題的結(jié)構(gòu)分解為個體詞、謂詞、量詞等，并討論它們與推理之間的關(guān)系，這一部分的內(nèi)容稱為一階邏輯(謂詞邏輯)。,,首先我們將簡單命題的結(jié)構(gòu)分解成個體和謂詞?！　€體(客體)我們討論的對象?？梢允蔷唧w的，也可以是抽象的?！　€體域(論域)個體所構(gòu)成的非空集合。　　全總個體域(無限域)包含宇宙中一切事物的個體域。謂

4、詞簡單命題中，表示一個個體的性質(zhì)或多個個體間的關(guān)系的詞。 　　之所以稱之為謂詞，是因為謂詞和個體詞一起構(gòu)成了簡單命題中的主謂結(jié)構(gòu)。如：　　小王是學(xué)生。　　3是素數(shù)。　　2整除6?！　?位于2與5之間。,2.1一階邏輯的基本概念,上面這些簡單命題中，小王、2、3、5、6均是個體，“……是學(xué)生”，“……是素數(shù)”，“……整除……”，“……位于……與……之間”均是謂詞。前兩個謂詞描述的是一個個體的性質(zhì)，稱為一元謂詞； 第三個表示兩個個

5、體之間的關(guān)系，稱為二元謂詞； 第四個表示三個個體之間的關(guān)系，稱為三元謂詞。以此類推，我們將描述n(n≥2)個個體之間關(guān)系的謂詞稱為n元謂詞。通常用大寫字母F、G、H(可加下標(biāo))來表示謂詞。如：　　F表示“……是學(xué)生”； 　　G表示“……整除……”； 　　H表示“……位于……與……之間”。,這時F、G、H表示的是具體的謂詞，稱為謂詞常元，否則，稱為謂詞變元。顯然，單獨(dú)的一個謂詞(即使是謂詞常元)并不能構(gòu)成一個完整的句子，必須以個體詞

6、取代“……”方能構(gòu)成一個句子。通常我們用小寫的英文字母a、b、c(可加下標(biāo))等表示個體。這樣，“小王是學(xué)生”可符號化為F(a)，其中a表示小王。若用b表示小李，則F(b)就表示“小李是學(xué)生”。若用c1表示2，用c2表示6，則G(c1，c2)就表示“2整除6”。,這里，a、b、c1、c2均是具體的個體，稱為個體常元。一般我們用F(x)表示“x是學(xué)生”，其中的x稱為個體變元(簡稱變元，亦稱個體詞)。類似地，我們也可用G(x，y)表示“x整除

7、y”?！　∥覀兎Q由謂詞符和變元符組成的符號串為命題函數(shù)。之所以稱為命題函數(shù)，是因為命題函數(shù)不是命題，只有謂詞為常元并將其中的變元代以具體的個體后，才能構(gòu)成命題。例如：“G(x，y)：x整除y?！?并不是命題，但若取a：2，b：6，則G(a，a)，G(a，b)以及G(b，a)均是命題，前兩個是真命題，第三個是假命題。G(a，a)、G(a，b)等稱為0元謂詞，它們不含個體變元，0元謂詞即命題。,注意　　 (1) 多元謂詞中變元的順序不

8、同，表示的意義也不同。如G(x，y)表“x整除y”，而G(y，x)表“y整除x”?！　?2) 在謂詞邏輯中，、∧、∨、→、仍是聯(lián)結(jié)詞，其含義和用法與命題邏輯中的相同?！　　纠?.1.1】將下列語句形式化為謂詞邏輯中的命題或　　命題函數(shù)?！　?1) 小王是二年級大學(xué)生?！　?2) 小王是李老師的學(xué)生?！　?3) 如果x≤y且y≤x，則x=y。,解　　(1) 令F(x)：x是大學(xué)生；G(x)：x是二年級的； a：小王。則原句

9、形式化為：　　　　　　　　　　　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),前兩句在確知“小王”和“李老師”之后均是命題，第三句因為含有變元所以是命題函數(shù)。但實際上我們知道，只要將x、y限制在數(shù)的范圍內(nèi)，第三句

10、是一個數(shù)學(xué)定理，是真命題，這就涉及到了個體域，在這個個體域中命題函數(shù)是真的，在那個個體域中又有可能是假的，這就需要對變量作“量化”。例如，“x2-4=0”這句話不能確定其真?zhèn)?，因為我們不知道x的取值。如果在這句話之前加上“當(dāng)x=1時”或者“對于x ∈{-2，2}”或者“對某個整數(shù)x”，則它就變成了一個真值確定的數(shù)學(xué)命題(第一句為假，后兩句為真)。,事實上，在一般的簡單命題中，常有一些表示數(shù)量的詞語，諸如“所有的”、“有一些”等等，用來表

11、示謂詞中的變量取自論域中的全體或部分個體，例如下面的兩個陳述句：　　“對所有的x∈D，論斷F(x)為真。”　　“對某些x∈D，論斷F(x)為真。”　　在謂詞邏輯中，我們用量詞把它們形式化。,1． 全稱量詞 “”　　全稱量詞用來表示個體域中的全體。表自然語言中的“所有的”、“任意的”、“每一個”等等。如：“任意偶數(shù)均能被2整除?！薄　【渥涌筛膶懗桑骸霸谂紨?shù)集合中的任意的x，x能被2整除?！薄　∪€體域為偶數(shù)集，用F(x)

12、表示“x能被2整除”，用x表示“任意的x”，則原句形式化為：xF(x)。,注意xF(x)表示的是“在個體域中，任意的x均有F(x)這個性質(zhì)”，這是一個可以確定真值的命題。當(dāng)個體域D為有窮集時：　xF(x)的真值為1，當(dāng)且僅當(dāng)對于每一個x∈D，均有F(x)真值為1；　xF(x)的真值為0，當(dāng)且僅當(dāng)至少有一個x0∈D，使得F(x0)真值為0。例如：“此次考試全班每個人都通過了”形式化為xF(x)，其中，論域：全班的每個人；

13、 F(x)：x通過了考試。此命題是否為真？ 只需拿來成績冊，看“張三、李四……通過否？”，若以a1表“張三”，即求F(a1)的真值，若以a2表“李四”，則求F(a2)的真值…… 顯然，當(dāng)且僅當(dāng)F(a1)、F(a2)……的真值均為1時，xF(x)的真值為1，而若有一個ai，使得F(ai)的真值為0，xF(x)的真值就為0。亦即：　　　　　　　xF(x)F(a1)∧F(a2)∧…∧F(an),2． 存在量詞 “”　　存在量詞

14、用來表示論域中的部分個體。表自然語言中的“存在著一些”、“至少有一個”、“有”等等。如：　　“我們班有人會吸煙?！薄　【渥涌筛膶懗桑骸霸谖覀儼嘤幸恍﹛，x會吸煙?！薄　∪€體域為“我們班的同學(xué)”，用G(x)表示“x會吸煙”，用x表示“有些x”，則原句形式化為：xG(x)。,注意　xG(x)表示的是“在個體域中，至少有一個x具有G(x)這個性質(zhì)”，這是一個可以確定真值的命題。當(dāng)個體域D為有窮集時，不妨設(shè)D={a1，a2，…，a

15、n}：　xG(x)的真值為0，當(dāng)且僅當(dāng)對于每一個x∈D，均有G(x)真值為0；　　xG(x)的真值為1，當(dāng)且僅當(dāng)至少有一個x0∈D，均有G(x0)真值為1。,所以　　　　　xG(x)G(a1)∨G(a2)∨…∨G(an)　　另外，在數(shù)學(xué)中經(jīng)常要用到“存在唯一的”這樣的詞，它的符號化表示是“!”?！　≡谝陨系男问交^程中，我們均指定了個體域，這是必須的。因為不同的個體域，可能導(dǎo)致命題真值的不同，如：xG(x)是“有人

16、會吸煙”的形式化，當(dāng)個體域為“我們班”時，xG(x)的真值可能是假的，但當(dāng)個體域為“我們學(xué)?！睍r，真值就可能是真的了。 　　為了統(tǒng)一起見，除非另作說明，我們均取個體域為全總個體域，這時由于個體的選取范圍是一切事物，因此我們引入特性謂詞來限制變元的變化范圍。,【例2.1.2】在全總個體域中形式化下列命題：　　(1) 任意的偶數(shù)均能被2整除?！　?2) 我們班有人吸煙?！　〗狻　?(1) 引入特性謂詞H(x)：x是偶數(shù)?！　　?/p>

17、任意的偶數(shù)均能被2整除”的含義是：全總個體域中有子集——偶數(shù)集，該子集中的每個元素均具有一種性質(zhì)，世間萬物，只要你屬于這個子集，你就必然具有這種性質(zhì)，所以是蘊(yùn)含式。特性謂詞以蘊(yùn)含式的前件加入。則原句可形式化為：　　　　　　　　　　x(H(x)→F(x)),(2) 引入特性謂詞W(x)：x是我們班的人?！　　拔覀儼嘤腥宋鼰煛钡暮x可以這樣理解：在宇宙間的萬物(全總個體域)中，有一個子集——我們班，還有另一個子集——吸煙的人。強(qiáng)

18、調(diào)的是既在我們班，又吸煙的人，所以是兩個子集的交集。特性謂詞用合取項加入。則原句可形式化為：　　　　　　　　x(W(x)∧G(x)),【例2.1.3】將下列命題形式化為一階邏輯中的命題：　　(1) 沒有不犯錯誤的人?！　?2) 人總是要犯錯誤的?！　〗狻≡O(shè)M(x)：x是人，F(xiàn)(x)：x犯錯誤。則原句形式化為： 　(1)x(M(x)∧F(x))　 (2) 　x(M(x)→F(x)),【例2.1.4】將下列命題形式

19、化為一階邏輯中的命題：　　(1) 所有的病人都相信醫(yī)生?！　?2) 有的病人相信所有的醫(yī)生?！　?3) 有的病人不相信某些醫(yī)生。　　(4) 所有的病人都相信某些醫(yī)生。　　解　設(shè)F(x)：x是病人，G(x)：x是醫(yī)生，H(x，y)：x相信y?！　?1) 本命題的意思是：對于每一個x，如果x是病人，那么對于每一個y，只要y是醫(yī)生，x就相信y。因此，本命題符號化為：　　　　　　　　x(F(x)→y(G(y)→H(x，y)))

20、,或　　　　xy((F(x)∧G(y))→H(x，y))　　(2) 本命題的意思是：存在著這樣的x，x是病人且對于每一個y，只要y是醫(yī)生，x就相信y。 因此，本命題符號化為：　　　　　　　x(F(x)∧y(G(y)→H(x，y)))　　(3) 本命題的意思是：存在著這樣的x和y，x是病人，y是醫(yī)生，x不相信y。因此，本命題符號化為：　　　　　　xy(F(x)∧G(y)∧　H(x，y))或　　　　　x(F(x)∧

21、y (G(y)∧H(x，y))),(4) 本命題的意思是：對于每個x，如果x是病人，就存在著醫(yī)生y，使得x相信y。因此，本命題符號化為：　　　　x(F(x)→y(G(y)∧H(x，y)))　　【例2.1.5】將下列命題形式化為一階邏輯中的命題：　　(1) 任意一個整數(shù)x，均有另一個整數(shù)y，使得x+y等于0?！　?2) 存在這樣的實數(shù)x，它與任何實數(shù)y的乘積均為y。,解　　(1) 設(shè)Z(x)：x是整數(shù)，E(x，y)：x=y

22、，f(x，y)=x+y。則原句形式化為：　　　　　　　x(Z(x)→y(Z(y)∧E(f(x，y)，0)))　　(2) 設(shè)R(x)：x是實數(shù)，E(x，y)：x=y，g(x，y)=xy。則原句形式化為：　　x(R(x)∧y(R(y)→E(g(x，y)，y)))　　注意　在這兩個命題中，“x是整數(shù)”和“x是實數(shù)”均表一個個體的性質(zhì)，所以是一元謂詞，“和等于0”、“乘積為y”均表兩個個體間的關(guān)系，所以是二元謂詞。,但是，“x

23、+y”和“x與y的乘積”是兩個數(shù)之間的運(yùn)算，嚴(yán)格來講不是二元謂詞，我們用二元函數(shù)f(x，y)、g(x，y)表之，因此，運(yùn)算符也是一階邏輯中的符號 。不過，需要指出的是，“x與y的和為z”有時也可用一個三元謂詞F(x，y，z)來表示?！　×硗猓谝浑A邏輯中，量詞符號、總是與一個個體變元符共同出現(xiàn)，如x，y，…，x，y稱為相應(yīng)量詞的指導(dǎo)變元。,,上一節(jié)中我們在一階邏輯中符號化得到的命題和命題函數(shù)就是一階邏輯公式(謂詞公式)。至此，

24、在一階邏輯中，我們已涉及到以下這些符號：　　(1) 個體變元符號：用小寫的英文字母x，y，z(或加下標(biāo))…表示?！　?2) 個體常元符號：用小寫的英文字母a，b，c(或加下標(biāo))…表示?！　?3) 運(yùn)算符號：用小寫的英文字母f，g，h(或加下標(biāo))…表示?！　?4) 謂詞符號：用大寫的英文字母F，G，H(或加下標(biāo))…表示?！　?5) 量詞符號：，。　　(6) 聯(lián)結(jié)詞符號：，∧，∨，→，?！　?7) 逗號和圓括號。,2.

25、2一階邏輯公式及解釋,一個符號化的命題是一串由這些符號所組成的表達(dá)式，但并不是任意一個由此類符號組成的表達(dá)式就對應(yīng)于一個命題。所以要給出嚴(yán)格的定義?！　《x2.2.1項的定義：　　(1) 任何一個個體變元或個體常元是項?！　?2) 如果f是n元運(yùn)算符，t1，t2，…，tn是項，則f(t1，t2，…，tn)是項?！　?3) 所有的項由且僅由有限次使用(1)、(2)所生成。,例如，x，a，f(x，a)，f(g(x，a，b)，h(x

26、))均是項，其中h、f和g分別是一元、二元和三元運(yùn)算符。而h(a，b)不是項，因為h是一元運(yùn)算符，但h(a，b)中h的后面跟了兩個項，同樣g(x)也不是項(理由請讀者自己考慮)?！　《x2.2.2若F是n元謂詞，t1，t2，…，tn是項，則F(t1，t2，…，tn)是原子公式?！　∮啥x可知，原子命題是不含量詞和聯(lián)結(jié)詞的謂詞公式。同命題邏輯中的情況相似，這里也可以用聯(lián)結(jié)詞將原子公式復(fù)合成分子公式。(事實上我們已經(jīng)這樣做了。),定義2

27、.2.3一階邏輯中的合式公式(wff)的遞歸定義：　　(1) 原子公式是合式公式?！　?2) 若A是合式公式，則(A)也是合式公式?！　?3) 若A、B均是合式公式，則(A∧B)、(A∨B)、(A→B)和(AB)也均是合式公式?！　?4) 若A是合式公式，x是個體變元，則xA、xA也是合式公式。　　(5) 只有有限次按規(guī)則(1)～(4)構(gòu)成的謂詞公式才是合式公式?！　∽⒂嘘P(guān)謂詞邏輯中合式公式的括號省略方法與命題邏輯相

28、同。,在謂詞公式中，形如xA(x)或xA(x)的部分叫做公式的x約束部分，其中的x稱量詞的指導(dǎo)變元(作用元)，而公式A(x)稱為量詞的轄域(作用域)。換言之，量詞的轄域乃是鄰接其后的公式。　　注意這里的公式A(x)泛指任意的謂詞公式，且除非轄域部分是原子公式，否則應(yīng)在公式的兩側(cè)加入圓括號?！　≡谳犛蛑兄笇?dǎo)變元x的一切出現(xiàn)稱為x在公式中的約束出現(xiàn)，且稱x為約束變元(它受量詞的約束)，在公式中除約束變元以外所出現(xiàn)的變元稱自由出現(xiàn)，

29、且稱x為自由變元。,【例 2.2.1】考察下列一階公式中每個量詞的轄域及每個變元的出現(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)　　(4) x(F(x)→xG(x，y))　　解　　(1) 全稱量詞x的轄域是(F(x)→yH(x，y))，其中x的兩次出現(xiàn)均是約束出現(xiàn)，是約束變元； 存在量詞y的轄域

30、是H(x，y)，其中y的出現(xiàn)是約束的，y是約束變元。,(2) 第一個全稱量詞x的轄域是(F(x)→G(x))，其中x的出現(xiàn)均是約束出現(xiàn)，是約束變元； 第二個全稱量詞x的轄域是(F(x)→H(x))，其中x的出現(xiàn)均是約束出現(xiàn)，是約束變元?！　?3) 唯一的存在量詞x的轄域是F(x)，其中x的出現(xiàn)是約束出現(xiàn)，是約束變元； 而x的第三次出現(xiàn)是在G(x)中的出現(xiàn)，是自由出現(xiàn)，第三個x是自由變元。 　　(4) 第一個全稱量詞x的轄

31、域是(F(x)→xG(x，y))，其中F(x)中的x是受其約束的出現(xiàn)，是約束變元； 第二個存在量詞x的轄域是G(x，y)，其中x的出現(xiàn)是受其約束的出現(xiàn)，是約束變元，y是自由變元。,由例題可見，在一個一階邏輯公式中，某個個體變元(符)的出現(xiàn)可以既是約束的，又是自由的，如(3)中的x。另外，同一個變元(符)即使都是約束的，也可能是在不同的量詞轄域中出現(xiàn)，如(2)、(4)中的x。為了避免混淆，可對約束變元進(jìn)行換名，使得一個變元(符)在一個

32、公式中只以一種形式出現(xiàn)。并使每個量詞的作用元不同。這樣做時需遵守下　　面的規(guī)則：　　換名規(guī)則　　(1) 將量詞的作用元及其轄域中所有受其約束的同符號的變元用一個新的變元符替換?！　?2) 新的變元符是原公式中所沒有出現(xiàn)的?！　?3) 用(1)、(2)得到的新公式與原公式等值。,【例2.2.3】對公式x(F(x)→G(x，y))∧H(x，y)做代替，下面的幾種做法中哪個是正確的？　　(1)　x(F(x)→G(x，y))∧H(

33、z，y)　　(2)　x(F(x)→G(x，z))∧H(u，y)　　(3)　z(F(z)→G(x，y))∧H(y，y)　　只有(1)是正確的，請讀者自己做出分析。　　定義2.2.4沒有自由變元的公式稱為閉式。　　如例2.2.1中的(1)、(2)兩式均是閉式，而公式(3)、(4)不是閉式。事實上，僅就個體變元而言，自由變元才是真正的變元，而約束變元只在表面上是變元，實際上并不是真正意義上的變元。換言之，含有自由變元的公式在解釋

34、后仍是命題函數(shù)，還需賦值方成命題，而不含自由變元的閉式一旦給出解釋就成了命題。,定義2.2.5一個解釋I由以下四部分組成：　　(1) 為個體域指定一個非空集合DI?！　?2) 為每個個體常元指定一個個體?！　?3) 為每個n元運(yùn)算符指定DI上的一個n元運(yùn)算?！　?4) 為每個n元謂詞符指定DI上的一個n元謂詞?！　‘?dāng)解釋I的個體域D為無窮集合時，我們可以通過讀取公式的含義來獲取真值。　　【例2.2.4】設(shè)f，g均為二元運(yùn)算符

35、，E，L均為二元謂詞符，給定解釋I如下：　　個體域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y L(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))　　解　公式

36、(1)中沒有自由變元，是閉式，在解釋I下的意義是：對于每一個自然數(shù)x，均存在著自然數(shù)y，使得x＜y。顯然這是一個真命題。,公式(2)中也沒有自由變元，是閉式，在解釋I下的意義是：對于每一個自然數(shù)x，x+0=x并且x·0＜0。因為0＜0不真，所以這是一個假命題?！　」?3)中x是自由變元，不是閉式，在解釋I下的意義是：對于每一個自然數(shù)y，x=y 或者x＜y。因為x取0時，原式為真； x取1時，原式為假，所以這是命題函數(shù)，而非

37、命題?！　」?4)中x是自由變元，不是閉式，在解釋I下的意義是：x+0=x·0。因為x取0時，原式為真； x非0時，原式為假，所以這是命題函數(shù)，而非命題。　　如上所言，含有自由變元的公式在解釋后仍是命題函數(shù)，還需賦值方成命題。,定義2.2.6賦值υ是建立在解釋I上的函數(shù)，且有：　　(1) υ(xi)=i，即對自由變元xi指派一個DI中的個體i?！　?2) υ(f(t1，t2，…，tn))=fi(υ(t1)，υ(t2)

38、，…，υ(tn))，其中fi是I對f的解釋，ti(i=1，2，…，n)是項。,,【例2.2.5】設(shè)f，g均為二元運(yùn)算符，E，L均為二元謂詞符，給定解釋I及賦值υ如下：　　個體域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?！　∏笙铝泄皆诮忉孖和賦值分別為υ1，υ2下的真值?！　?1) y(E(

39、x，y)∨L(x，y))　　(2) E(f(x，a)，g(x，a))　　(3) xE(g(x，a)，a),解公式(1)在解釋I及賦值υ1下的含義是：對于每個自然數(shù)y，0=y 或者0＜y。即0是最小的自然數(shù)，這是真命題。在解釋I及賦值υ2下的含義是：對于每個自然數(shù)y，1=y 或者1＜y。即1是最小的自然數(shù)，這是假命題?！　」?2)在解釋I及賦值υ1下的含義是：0+0=0·0，這是真命題。在解釋I及賦值υ2下的含義是：1

40、+0=1·0，這是假命題。　　公式(3)中不含自由變元，無需考慮賦值。在解釋I下的意義是：對于每一個自然數(shù)x， x·0=0。 這是真命題。,在上一節(jié)我們曾提到過，當(dāng)個體域為有窮集DI={a1，a2，…，an}時：xF(x)F(a1)∧F(a2)∧…∧F(an)xG(x)G(a1)∨G(a2)∨…∨G(an)　　因此，當(dāng)解釋I中的個體域D為有窮集時，可先消量詞再求真值?！　　纠?.2.6】設(shè)解釋I為

41、：DI={2，3}，f(2)=3，f(3)=2，F(xiàn)(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) 式中不含量詞，所以直接求真值?！　　(2，f(2))∧F(3，f(3))　　F(2，3)∧F(3，2)　　

42、0∧1　　0　　(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∧1　　1,(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))→(

43、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) 1∧0 0,定義2.2.7一階邏輯公式的分類：　　永真式(邏輯有效式)在

44、任何解釋I及I的任何賦值下均為真的一階公式；永假式(矛盾式)在任何解釋I及I的任何賦值下均為假的一階公式； 可滿足式至少有一種解釋和一種賦值使其為真的一階公式?！　∮啥x可知，要判定一個公式A不是永真式，只需找到一個解釋I和I下的一個賦值υ，使A在I和υ下為假； 要判定一個公式A不是永假式，只需找到一個解釋I和I下的一個賦值υ，使A在I和υ下為真；要判定一個公式A是非永真的可滿足式，只需找到一個解釋I和I下的一個賦值υ，使A在I和υ

45、下為真，再找到一個解釋I和I下的一個賦值υ，使A在I和υ下為假。,【例2.2.7】討論下列公式的類型：　　(1) xF(x)→xF(x)　　(2) xG(x)∧xG(x)　　(3) xyF(x，y)→yxF(x，y)　　解　　(1) 公式xF(x)→xF(x)在任何解釋I下的含義是：如果個體域DI中的每個元素x均有性質(zhì)F，則DI中的某些元素x必有性質(zhì)F。前件xF(x)為真時，后件xF(x)永遠(yuǎn)為真，所

46、以公式x F(x)→x F(x)是永真式。,(2) 公式xG(x)∧x G(x)在任何解釋I下的含義是：個體域DI中的每個元素x均不具有性質(zhì)G，且DI中的某些元素x具有性質(zhì)G。這是兩個互相矛盾的命題，不可能同時成立，所以公式x　G(x)∧x G(x)是永假式?！　?3) 公式xyF(x，y)→yxF(x，y)既不是永真式，也不是永假式。由于這是閉式，故無需考慮賦值，只要給出一個使其成真的解釋和一個使其成假的解釋即

47、可。,① 給定解釋I1：DI1為自然數(shù)集，F(xiàn)(x，y)：x＜y。此時公式的前件xyF(x，y)表示“對于每個自然數(shù)x，均有自然數(shù)y比x大”是真命題，而后件yxF(x，y)表示“存在著自然數(shù)y比每個自然數(shù)x均大”是假命題。因此，I1是使xyF(x，y)→yxF(x，y)為假的解釋。　?、?給定解釋I2：DI2為自然數(shù)集，F(xiàn)(x，y)：x＞y。此時公式的前件xyF(x，y)表示“對于每個自然數(shù)x，均有自然數(shù)y比x小”

48、是假命題(x為0時，y不存在)，因此，I2是使xyF(x，y)→yxF(x，y)為真的解釋。,定義2.2.8　設(shè)A(p1，p2，…，pn)是含命題變元p1，p2，…，pn的命題公式，B(B1，B2，…，Bn)是以一階公式B1，B2，…，Bn分別代替p1，p2，…，pn在A中的所有出現(xiàn)后得到的一階公式，稱B是A的一個代換實例?！　±?，F(xiàn)(x)→G(y)，xF(x)→yG(y)均是命題公式p→q的代換實例，也是p的代換實例。

49、顯然有以下定理。,定理2.2.1　命題邏輯永真式的任何代換實例必是一階邏輯的永真式?！?同樣，命題邏輯永假式的任何代換實例必是一階邏輯的永假式。　　證明略?！　《ɡ?.2.1為我們提供了一大類一階邏輯的有效式。因此，判斷一個一階邏輯公式是否是永真式或永假式，我們既可以用定義2.2.7(如例2.2.7)，也可以用其是否是命題邏輯的永真式或永假式的代換實例來判斷。,例如，由等值定律可知，例2.2.7中的(2)　x　G(x)∧x G(

50、x)實質(zhì)上是命題邏輯永假式p∧p的代換實例，所以是永假式。又如，作為命題邏輯永真式 p∨p的代換實例，(xF(x)→G(y))∨(xF(x)→G(y))是永真式。至此，由第一章的每一個命題邏輯等值式，我們可以得到相應(yīng)的一階邏輯等值式。但是請注意，一階邏輯的永真式未必是命題邏輯永真式的代換實例，如由例2.2.7可知，xF(x)→xF(x)是永真式，但它只是命題公式p→q或p的代換實例，而非命題邏輯永真式的代換實例。 另外，一

51、般來說，含自由變元的非閉式只有在作為命題邏輯永真式(永假式)的代換實例時，才能成為一階邏輯中的永真式(永假式)。,,定義2.3.1　　設(shè)A與B是一階公式，若AB是永真式，則稱A與B等值， 或稱A與B邏輯等價，記作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為假。同時，要證明兩個公式不等值，只需找到一個解釋I和I中的一個賦值υ，使得兩個

52、公式在I和υ下，一個為真，另一個為假。,2.3　等值演算和前束范式,【例2.3.1】 判斷公式xF(x，y)→(G(x)∨zF(z，y))的類型。 　解　根據(jù)換名規(guī)則知，xF(x，y)→(G(x)∨zF(z，y))zF(z，y)→(G(x)∨zF(z，y))。而右式是命題永真式p→(q∨p)的代換實例，所以，此公式是永真式?！　　纠?.3.2】判斷公式xyF(x,y)與公式yxF(x，y)是否等值。,解　直接

53、觀察是不等值的。由于兩個公式均是閉式，所以只需給出一個解釋I，使其在I下一個為真，另一個為假。取解釋I：D為鞋子的集合，F(xiàn)(x，y)：x與y能配成一雙。則在I下，xyF(x,y)表示“每一只鞋子均有另一只鞋子能與其配成一雙”是真命題，而公式yxF(x，y)表示“有這樣的鞋子能與任何一只鞋子配成一雙”是假命題。因此，兩個公式xyF(x,y)與yxF(x，y)不等值?！　≡谏弦还?jié)中我們提到，通過代換實例可以得到一大類永真式

54、，從而得到一大類等值式?！　±?，雙重否定律，由pp 知pp是永真式，則其代換實例xF(x)F(x)是永真式，故(x)xF(x)。這樣，由第一章中的等值式可得一階邏輯中的等值式。再用置換法則可做一階邏輯中的等值演算，下面我們給出一階邏輯中關(guān)于量詞的等值式。,量詞轉(zhuǎn)換律(A(x)是任一一階公式)　　(1)xA(x)xA(x)

55、　　(2)xA(x)x　A(x) 　　證明　(1) 在任何解釋I下，xA(x)表示“在個體域D中，并非所有的　都具有性質(zhì)A”，xA(x)表示“在個體域D中，至少有一個x不具有性質(zhì)A”，兩個命題的含義是一樣的，因此它們同真或同假，它們是等值的。,(2) 證明留給讀者。證畢　　注意此定律又稱量詞否定等值式，但否定的不只是量詞，而是被量化了的整個命題。

56、當(dāng)個體域取有窮集時，采取消量詞的方法，得到的就是德·摩根律。　　量詞轄域擴(kuò)縮律(A(x)是任一一階公式，B是任一不含自由變量x的一階公式)　　(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) xA(x)

57、∨Bx(A(x)∨B),證明　　(1) 在任何解釋I和I中的任意賦值υ下，　　　xA(x)∧B=1　　當(dāng)且僅當(dāng)xA(x)=1且B=1　　當(dāng)且僅當(dāng)B=1 且 對于DI中的每一個元素c，A(c)=1　　當(dāng)且僅當(dāng)對于DI中的每一個元素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

58、且 存在DI中的元素c，使得A(c)=0　　當(dāng)且僅當(dāng)存在DI中的元素c，使得A(c)∨B=0　　當(dāng)且僅當(dāng)x(A(x)∨B)=0,(3) xA(x)∧B (xA(x)∧B)  　　　( (xA(x)∧B))　　　　 (xA(x)∨B) 　　(xA(x)∨B )　　　 (x(A(x)∨B))　　 (x (A(x)∧B))　 x(A(x)∧B)　　 (4) 證

59、明留給讀者?！　　　　　∽C畢　　另外，下面的等值式也稱作量詞轄域的擴(kuò)縮律?！　?5) xA(x)→Bx(A(x)→B)(5)　　(6) B→xA(x)x(B→A(x)) (6)　　(7) xA(x)→Bx(A(x)→B)(7)　　(8) B→xA(x)x(B→A(x)) (8),證明　只證第(5)式: xA(x)→BxA(x)∨B　

60、　　　 xA(x)∨B  x(A(x)∨B)  x(A(x)→B)　　(6)、(7)、(8)的證明留給讀者?！　　∽C畢　　量詞分配律(A(x)、B(x)是任一一階公式)　　(1) x(A(x)∧B(x))xA(x)∧xB(x) 　　(2) x(A(x)∨B(x

61、))xA(x)∨xB(x),證明　　(1) 在任何解釋I和I中的任意賦值υ下，　　　x(A(x)∧B(x))=1　　當(dāng)且僅當(dāng)對于DI中的每一個元素c，A(c)∧B(c)=1　　當(dāng)且僅當(dāng)對于DI中的每一個元素c，A(c)=1 且 B(c)=1　　當(dāng)且僅當(dāng)xA(x)=1 且xB(x)=1　　當(dāng)且僅當(dāng)xA(x)∧xB(x)=1,(2) x(A(x)∨B(x))  (x(A(x)∨B(x)))　　　　

62、　　　　　　　　 (x (A(x)∨B(x))) 　　 (x(A(x)∧B(x))) 　　  (xA(x)∧xB(x)) 　　 (x A(x)∧x B(x))

63、 　　xA(x)∨xB(x) 證畢　　注意　雖然一般情況下，∧與∨是滿足對偶律的，但在量詞分配律上對偶定理并不成立。即　　x(A(x)∨B(x))/ xA(x)∨xB(x)　　x(A(x)∧B(x))/ xA(x)∧xB(x)　　證明　給定解釋I： DI為自然數(shù)集，A(x)為x是奇數(shù)，B(x

64、)為x是偶數(shù)。,在I下，x(A(x)∨B(x))意為“所有的自然數(shù)，或是奇數(shù)，或是偶數(shù)”，是真命題，xA(x)∨xB(x)意為“所有的自然數(shù)是奇數(shù)，或者所有的自然數(shù)是偶數(shù)”，是假命題。因此，x(A(x)∨B(x))與xA(x)∨xB(x)不等值。而x(A(x)∧B(x))意為“存在著自然數(shù)x，x既是奇數(shù)又是偶數(shù)”，顯然這是一個假命題，xA(x)∧xB(x)意為“有自然數(shù)是奇數(shù)并且也有自然數(shù)是偶數(shù)”，是真命題，因此，

65、xA(x)∧xB(x)與x(A(x)∧B(x))不等值。,證畢,【例2.3.3】證明下列等值式:　　(1)x(F(x)→G(x))x(F(x)∧G(x))　　(2)xy(F(x)∧G(y)∧H(x,y))　　x　　　　　y((F(x)∧G(y))→H(x,y))　　證明　　(1) x(F(x)→G(x))　　　 　　x(F(x)→G(x))　　　　　　 　　x(F(x)∨G(x))

66、　　　 x(F(x)∧G(x)),(2) 　xy(F(x)∧G(y)∧H(x,y))　　　xy(F(x)∧G(y)∧H(x,y))　　xy((F(x)∧G(y))∨H(x,y))　　xy((F(x)∧G(y))→H(x,y))　　　　　　　　　　　　　　　　　　　　證畢　　在命題邏輯中，我們介紹過析取范式和合取范式，利用它們可將命題公式表示為統(tǒng)一的形式，為我們討論問題提供了方便。下面我們介紹

67、一階邏輯中的范式概念——前束范式。,定義2.3.2　設(shè)A為一階公式，若A具有如下形式　　　　　Q1x1Q2x2…QkxkB　　則稱A為前束范式。其中Qi(1≤i≤k)是量詞符或，xi(1≤i≤k)是變元符，B是不含量詞的公式?！　±?，x(F(x)∧G(x))，xy((F(x)∧G(y))→H(x,y))等公式均是前束范式。 xy(F(x)∧G(y)∧　H(x,y))，x(F(x)→y(G(y)∧H

68、(x，y))，xy(F(x)∨G(y))→H(x，y，z)等都不是前束范式。,在一階邏輯推理中，需要將公式化成前束范式形式，這總是可以辦到的。即任何一個一階公式均可等值演算成前束范式，化歸過程如下：　　(1) 消去除、∧、∨之外的聯(lián)結(jié)詞；　　(2) 將否定符移到量詞符后；　　(3) 換名使各變元不同名；　　(4) 擴(kuò)大轄域使所有量詞處在最前面?！　≌f明1化歸過程需遵守置換規(guī)則和換名規(guī)則(也可用代替規(guī)則)?！　≌f明2過

69、程(1)是為了方便地使用量詞轄域擴(kuò)縮律(1)～(4)，當(dāng)然也可以直接使用量詞轄域擴(kuò)縮律(5)～(8)。由此可知，公式的前束范式形式并不唯一。,【例2.3.4】　將下面公式化成前束范式。　　(1) x(F(x)∨yG(y，z)→zH(x，z))　　(2)x(F(x)→y(F(y)→F(f(x，y))))∧y(G(x，y)→F(y))解　　(1) x(F(x)∨yG(y，z)→zH(x，z))　　　x