第二章謂詞邏輯(1)

1、第二章第二章 一階邏輯一階邏輯(1/2) 在命題邏輯中，命題是最基本的單位，對簡單在命題邏輯中，命題是最基本的單位，對簡單命題不再進(jìn)行分解，并且不考慮命題之間的內(nèi)在聯(lián)命題不再進(jìn)行分解，并且不考慮命題之間的內(nèi)在聯(lián)系和數(shù)量關(guān)系系和數(shù)量關(guān)系.因而命題邏輯具有局限性，甚至無法因而命題邏輯具有局限性，甚至無法判斷一些簡單而常見的推理判斷一些簡單而常見的推理.考慮下面的推理考慮下面的推理: 凡偶數(shù)都能被凡偶數(shù)都能被2整除；整除；6是偶數(shù)是偶數(shù).所以，所以，6能被能被2整除整除.這個(gè)推理是我們公認(rèn)的數(shù)學(xué)推理中的真命題，但是在這個(gè)推理是我們公認(rèn)的數(shù)學(xué)推理中的真命題，但是在命題邏輯中卻無法判斷它的正確性命題邏輯

2、中卻無法判斷它的正確性.因?yàn)樵诿}邏輯因?yàn)樵诿}邏輯中只能將推理中出現(xiàn)的三個(gè)簡單命題依次符號(hào)化為中只能將推理中出現(xiàn)的三個(gè)簡單命題依次符號(hào)化為p，q，r，將推理的形式結(jié)構(gòu)符號(hào)化為，將推理的形式結(jié)構(gòu)符號(hào)化為 (pq)r 由于上式不是由于上式不是重言式重言式，所以不能由它判斷推理的正確，所以不能由它判斷推理的正確性性.2.1 一階邏輯的符號(hào)化一階邏輯的符號(hào)化 個(gè)體詞，謂詞和量詞是一階邏輯命題符號(hào)個(gè)體詞，謂詞和量詞是一階邏輯命題符號(hào)化的三個(gè)基本要素化的三個(gè)基本要素.下面討論這三個(gè)要素下面討論這三個(gè)要素 一、個(gè)體詞一、個(gè)體詞 個(gè)體詞個(gè)體詞是指所研究對象中可以獨(dú)立存在的具是指所研究對象中可以獨(dú)立存在的具體

3、的體的 或抽象的客體或抽象的客體. 例如例如:小王，小李，中國，小王，小李，中國，3等都可以作為等都可以作為個(gè)體詞個(gè)體詞. 將表示具體或特定的客體的個(gè)體詞稱作個(gè)體將表示具體或特定的客體的個(gè)體詞稱作個(gè)體常項(xiàng)，一般用小寫英文字母常項(xiàng)，一般用小寫英文字母a，b，c表示；表示；而將表示抽象或泛指的個(gè)體詞稱為個(gè)體變項(xiàng)，而將表示抽象或泛指的個(gè)體詞稱為個(gè)體變項(xiàng)，常用常用x，y，z表示表示.稱個(gè)體變項(xiàng)的取值范圍為稱個(gè)體變項(xiàng)的取值范圍為個(gè)體域個(gè)體域(或稱論域或稱論域) 個(gè)體域可以是個(gè)體域可以是有窮集合有窮集合，例如，例如，1，2，3，a，b，c，d，a，b，c，x，y，z，；也可；也可以是以是無窮集合無窮集合，

4、例如，自然數(shù)集合，例如，自然數(shù)集合 N=0，1，2，實(shí)數(shù)集合，實(shí)數(shù)集合R=x|x是實(shí)數(shù)是實(shí)數(shù). 有一個(gè)特殊的個(gè)體域，它是由宇宙間一切事物有一個(gè)特殊的個(gè)體域，它是由宇宙間一切事物組成的，稱它為組成的，稱它為全總個(gè)體域全總個(gè)體域.本課件在論述或推本課件在論述或推理中如沒有指明所采用的個(gè)體域，都是使用全理中如沒有指明所采用的個(gè)體域，都是使用全總個(gè)體域總個(gè)體域.二、謂詞二、謂詞 謂詞謂詞是用來刻畫個(gè)體詞性質(zhì)及個(gè)體詞之是用來刻畫個(gè)體詞性質(zhì)及個(gè)體詞之間相互關(guān)系的詞間相互關(guān)系的詞. .考慮下面四個(gè)命題考慮下面四個(gè)命題(或命題公式或命題公式): (1) 是無理數(shù)是無理數(shù). (2)x是有理數(shù)是有理數(shù). (3)小

5、王與小李同歲小王與小李同歲. (4)x與與y具有關(guān)系具有關(guān)系L. 2在在(2)中，中，x是個(gè)體變項(xiàng)，是個(gè)體變項(xiàng)，“是有理數(shù)是有理數(shù)”是謂詞，記是謂詞，記為為G，用，用G(x)表示表示(2)中命題中命題.在在(3)中，小王，小李都是個(gè)體常項(xiàng)，中，小王，小李都是個(gè)體常項(xiàng)，“與與同歲同歲”是謂詞，記為是謂詞，記為H，則，則(3)中命題符號(hào)化形式為中命題符號(hào)化形式為H(a,b)，其中，其中，a:小王，小王，b:小李小李. 在在(4)中，中，x，y為兩個(gè)個(gè)體變項(xiàng)，謂詞為為兩個(gè)個(gè)體變項(xiàng)，謂詞為L，(4)的符的符號(hào)化形式為號(hào)化形式為L(x, y). 在在(1)中，中， 是個(gè)體常項(xiàng)，是個(gè)體常項(xiàng)，“是無理數(shù)是無

6、理數(shù)”是謂詞，記是謂詞，記為為F，并用，并用F( )表示表示(1)中命題中命題. 22 同個(gè)體詞一樣，謂詞也有常項(xiàng)和變項(xiàng)之分同個(gè)體詞一樣，謂詞也有常項(xiàng)和變項(xiàng)之分.表表示具體性質(zhì)或關(guān)系的謂詞稱為示具體性質(zhì)或關(guān)系的謂詞稱為謂詞常項(xiàng)謂詞常項(xiàng)，表，表示抽象的、泛指的性質(zhì)或關(guān)系的謂詞稱為示抽象的、泛指的性質(zhì)或關(guān)系的謂詞稱為謂謂詞變項(xiàng)詞變項(xiàng).無論是謂詞常項(xiàng)或變項(xiàng)都用大寫英無論是謂詞常項(xiàng)或變項(xiàng)都用大寫英文字母文字母F，G，H，表示，可根據(jù)上下文區(qū)表示，可根據(jù)上下文區(qū)分分. 在上面四個(gè)命題中，在上面四個(gè)命題中，(1)，(2)，(3)中謂詞中謂詞F，G，H是常項(xiàng)，而是常項(xiàng)，而(4)中謂詞中謂詞L是變項(xiàng)是變項(xiàng).

7、一般的，用一般的，用F(a)表示個(gè)體常項(xiàng)表示個(gè)體常項(xiàng)a具有性質(zhì)具有性質(zhì)F (F是謂詞常項(xiàng)或謂詞變項(xiàng)是謂詞常項(xiàng)或謂詞變項(xiàng))，用，用F(x)表示個(gè)體變表示個(gè)體變項(xiàng)項(xiàng)x具有性質(zhì)具有性質(zhì)F.而用而用F(a，b)表示個(gè)體常項(xiàng)表示個(gè)體常項(xiàng)a，b具有關(guān)系具有關(guān)系F，用，用F(x , y)表示個(gè)體變項(xiàng)表示個(gè)體變項(xiàng)x，y具有具有關(guān)系關(guān)系F. 更一般的，用更一般的，用P(x1,x2,xn)表示含表示含n(n1)個(gè)命個(gè)命題變項(xiàng)的題變項(xiàng)的n元謂詞元謂詞.n=1時(shí)，時(shí)，P(x1)表示表示x1具有性質(zhì)具有性質(zhì)P；n2時(shí)，時(shí)，P(x1,x2,xn)表示表示x1,x2,xn具有關(guān)系具有關(guān)系P.實(shí)質(zhì)上，實(shí)質(zhì)上，n元謂詞元謂詞P

8、(x1,x2,xn)可以看成以個(gè)可以看成以個(gè)體域?yàn)槎x域，以體域?yàn)槎x域，以0,1為值域的為值域的n元函數(shù)或關(guān)元函數(shù)或關(guān)系系.它不是命題它不是命題.要想使它成為命題，必須用謂詞要想使它成為命題，必須用謂詞常項(xiàng)取代常項(xiàng)取代P，用個(gè)體常項(xiàng)，用個(gè)體常項(xiàng)a1,a2,an取代取代x1,x2,xn，得，得P(a1,a2,an)是命題是命題. 有時(shí)候?qū)⒉粠€(gè)體變項(xiàng)的謂詞稱為有時(shí)候?qū)⒉粠€(gè)體變項(xiàng)的謂詞稱為0元元謂詞，例如，謂詞，例如，F(xiàn)(a)，G(a,b)，P(a1,a2,an)等等都是都是0元謂詞元謂詞.當(dāng)當(dāng)F，G，P為謂詞常項(xiàng)時(shí)，為謂詞常項(xiàng)時(shí)，0元謂詞為命題元謂詞為命題.這樣一來，命題邏輯中的命這樣一來，

9、命題邏輯中的命題均可以表示成題均可以表示成0元謂詞，因而可以將命題元謂詞，因而可以將命題看成特殊的謂詞看成特殊的謂詞. 例例2.1.1 將下列命題在一階邏輯中用將下列命題在一階邏輯中用0元謂詞符號(hào)化，元謂詞符號(hào)化，并討論它們的真值并討論它們的真值: (1)只有只有2是素?cái)?shù)，是素?cái)?shù)，4才是素?cái)?shù)才是素?cái)?shù). (2)如果如果5大于大于4，則，則4大于大于6. 解解: (1)設(shè)一元謂詞設(shè)一元謂詞F(x):x是素?cái)?shù)，是素?cái)?shù)，a:2，b:4. (1)中命題符號(hào)化為中命題符號(hào)化為0元謂詞的蘊(yùn)涵式元謂詞的蘊(yùn)涵式: F(b)F(a) 由于此蘊(yùn)涵前件為假，所以由于此蘊(yùn)涵前件為假，所以(1)中命題為真中命題為真. (

10、2)如果如果5大于大于4，則，則4大于大于6. (2) 設(shè)二元謂詞設(shè)二元謂詞G(x，y):x大于大于y，a:4，b:5，c:6.G(b,a)，G(a,c)是兩個(gè)是兩個(gè)0元謂詞，把元謂詞，把(2)中中命題符號(hào)化為命題符號(hào)化為 G(b,a)G(a,c) 由于由于G(b,a)為真，而為真，而G(a,c)為假，所以為假，所以(2)中中命題為假命題為假. 三、量詞三、量詞 (1) 全稱量詞全稱量詞 (2) 存在量詞存在量詞 (1) 全稱量詞全稱量詞 日常生活和數(shù)學(xué)中所用的日常生活和數(shù)學(xué)中所用的“一切的一切的”，“所所有的有的”，“每一個(gè)每一個(gè)”，“任意的任意的”，“凡凡”，“都都”等詞可統(tǒng)稱為全稱量詞，

11、將它們符號(hào)等詞可統(tǒng)稱為全稱量詞，將它們符號(hào)化為化為“ ”.并用并用 x， y等表示個(gè)體域里的等表示個(gè)體域里的所有個(gè)體，而用所有個(gè)體，而用 xF(x)， yG(y)等分別表示個(gè)體域里所有個(gè)等分別表示個(gè)體域里所有個(gè)體都有性質(zhì)體都有性質(zhì)F和都有性質(zhì)和都有性質(zhì)G. (2) 存在量詞存在量詞 日常生活和數(shù)學(xué)中所用的日常生活和數(shù)學(xué)中所用的“存在存在”，“有一有一個(gè)個(gè)”，“有的有的”，“至少有一個(gè)至少有一個(gè)”等詞統(tǒng)稱為等詞統(tǒng)稱為存在量詞，將它們都符號(hào)化為存在量詞，將它們都符號(hào)化為“ ”.并用并用 x， y等表示個(gè)體域里有的個(gè)體，而用等表示個(gè)體域里有的個(gè)體，而用 xF(x)， yG(y)等分別表示個(gè)體域里存在

12、個(gè)體具有性質(zhì)等分別表示個(gè)體域里存在個(gè)體具有性質(zhì)F和存在個(gè)體具有性質(zhì)和存在個(gè)體具有性質(zhì)G等等. 四、一階邏輯命題符號(hào)化四、一階邏輯命題符號(hào)化 例例3.1.2 在個(gè)體域分別限制為在個(gè)體域分別限制為(a)和和(b)條件時(shí)，條件時(shí)，將下面兩個(gè)命題符號(hào)化將下面兩個(gè)命題符號(hào)化: (1) 凡人都呼吸凡人都呼吸. (2) 有的人用左手寫字有的人用左手寫字. 其中其中:(a)個(gè)體域個(gè)體域D1為人類集合；為人類集合； (b)個(gè)體域個(gè)體域D2為全總個(gè)體域?yàn)槿倐€(gè)體域. 解解: (a)令令F(x):x呼吸呼吸.G(x):x用左手寫字用左手寫字.(1) 在在D1中除了人外，再無別的東西，中除了人外，再無別的東西，因而因

13、而“凡人都呼吸凡人都呼吸”應(yīng)符號(hào)化為應(yīng)符號(hào)化為 xF(x) (2.1)(2) 在在D1中的有些個(gè)體中的有些個(gè)體(人人)用左手寫字，用左手寫字，因而因而“有的人用左手寫字有的人用左手寫字”符號(hào)化為符號(hào)化為 xG(x) (2.2) (b) D2中除了有人外，還有萬物，因而在中除了有人外，還有萬物，因而在 (1)，(2)符號(hào)化時(shí)，必須考慮將人分離出來符號(hào)化時(shí)，必須考慮將人分離出來令令M(x):x是人是人. 在在D2中，中，(1)，(2)可以分別重述如下可以分別重述如下: (1)對于宇宙間一切事物而言，如果事物是對于宇宙間一切事物而言，如果事物是人，則他要呼吸人，則他要呼吸. (2)在宇宙間存在著用左

14、手寫字的人在宇宙間存在著用左手寫字的人. 特性謂詞特性謂詞(1)，(2)的符號(hào)化形式分別為的符號(hào)化形式分別為 x(M(x)F(x) (2.3) 和和 x(M(x)G(x) (2.4) 其中其中F(x)與與G(x)的含義同的含義同(a)中中. 問問: (a)能否將能否將(1)符號(hào)化為符號(hào)化為 x(M(x)F(x)？ (b)能否將能否將(2)符號(hào)化為符號(hào)化為 x(M(x)G(x)？ 否否例例2.1.3 在個(gè)體域限制為在個(gè)體域限制為(a)和和(b)條件時(shí)，將下條件時(shí)，將下列命題符號(hào)化列命題符號(hào)化: (1) 對于任意的對于任意的x，均有，均有x2-3x+2=(x-1)(x-2). (2) 存在存在x，

15、使得，使得x+5=3. 其中其中: (a)個(gè)體域個(gè)體域D1=N(N為自然數(shù)集合為自然數(shù)集合) (b)個(gè)體域個(gè)體域D2=R(R為實(shí)數(shù)集合為實(shí)數(shù)集合) (b) 在在D2內(nèi)，內(nèi)，(1)和和(2)的符號(hào)化形式還是的符號(hào)化形式還是(4.7)式和式和(4.8)式，式，(1)依然是真命題，而此時(shí)依然是真命題，而此時(shí)(2)也是真命題也是真命題.解解: (a)令令F(x): -3x+2=(x-1)(x-2)， G(x): x+5=3.命題命題(1)的符號(hào)化形式為的符號(hào)化形式為 xF(x) (2.5) 命題命題(2)的符號(hào)化形式為的符號(hào)化形式為 xG(x) (2.6) 顯然顯然(1)為真命題；而為真命題；而(2)

16、為假命題，因?yàn)闉榧倜}，因?yàn)镹不不含負(fù)數(shù)含負(fù)數(shù).2x 1. 在不同個(gè)體域內(nèi)，同一個(gè)命題的符號(hào)在不同個(gè)體域內(nèi)，同一個(gè)命題的符號(hào)化形式可能不同，也可能相同化形式可能不同，也可能相同. 2. 同一個(gè)命題，在不同個(gè)體域中的真值同一個(gè)命題，在不同個(gè)體域中的真值也可能不同也可能不同. 從例從例2.1.2和例和例2.1.3可以看出以下兩點(diǎn)可以看出以下兩點(diǎn): 例例2.1.4 將下列命題符號(hào)化，并討論真值將下列命題符號(hào)化，并討論真值. (1)所有的人都長著黑頭發(fā)所有的人都長著黑頭發(fā). (2)有的人登上過月球有的人登上過月球. (3)沒有人登上過木星沒有人登上過木星. (4)在美國留學(xué)的學(xué)生未必都是亞洲人在美國留

17、學(xué)的學(xué)生未必都是亞洲人. 解解 :令令M(x):x為人為人. (1)令令F(x):x長著黑頭發(fā)長著黑頭發(fā).命題命題(1)符號(hào)化為符號(hào)化為 設(shè)設(shè)a是是1969年登上月球完成阿波羅計(jì)劃的一年登上月球完成阿波羅計(jì)劃的一個(gè)美國人，則個(gè)美國人，則M(a)G(a)為真，所以為真，所以(2.8)表表示的命題為真示的命題為真. 設(shè)設(shè)a為某個(gè)金發(fā)姑娘，則為某個(gè)金發(fā)姑娘，則M(a)為真，而為真，而F(a)為假，所以為假，所以M(a)F(a)為假，故為假，故(2.7)所表所表示的命題為假示的命題為假. (2)令令G(x):x登上過月球登上過月球. 命題命題(2)的符號(hào)化形式的符號(hào)化形式 為為 x(M(x)F(x)

18、(2.7) x(M(x)G(x) (2.8) (4)令令F(x):x是在美國留學(xué)的學(xué)生，是在美國留學(xué)的學(xué)生，G(x):x是亞洲是亞洲人人.命題命題(4)符號(hào)化形式為符號(hào)化形式為 x(F(x)G(x) (2.10) 這個(gè)命題也為真這個(gè)命題也為真. (3)令令H(x):x登上過木星登上過木星.命題命題(3)符號(hào)化形式為符號(hào)化形式為 x(M(x)H(x) (2.9) 到目前為止，對于任何一個(gè)人到目前為止，對于任何一個(gè)人(含已經(jīng)去世的人含已經(jīng)去世的人)都還沒有登上過木星，所以對任何人都還沒有登上過木星，所以對任何人a，M(a)H(a)均為假，因而均為假，因而 x(M(x)H(x)為假，為假，所以所以(

19、2.9)表示的命題為真表示的命題為真.例例2.1.5 將下列命題符號(hào)化將下列命題符號(hào)化: (1) 兔子比烏龜跑得快兔子比烏龜跑得快. (2) 有的兔子比所有的烏龜跑得快有的兔子比所有的烏龜跑得快. (3) 并不是所有的兔子都比烏龜跑得快并不是所有的兔子都比烏龜跑得快. (4) 不存在跑得同樣快的兩只兔子不存在跑得同樣快的兩只兔子. 解解: 令令F(x):x是兔子，是兔子，G(y):y是烏龜，是烏龜，H(x,y):x比比y跑得快，跑得快，L(x,y):x與與y跑得一樣快跑得一樣快.這這4個(gè)命題個(gè)命題分別符號(hào)化為分別符號(hào)化為 x y(F(x)G(y)H(x,y) (2.11) x(F(x) y(G

20、(y)H(x,y) (2.12) x y(F(x)G(y)H(x,y) (2.13) x y(F(x)F(y)L(x,y) (2.14) 注意注意 1. 一般說來，多個(gè)量詞出現(xiàn)時(shí)，它們的順序不一般說來，多個(gè)量詞出現(xiàn)時(shí)，它們的順序不能隨意調(diào)換能隨意調(diào)換. 例如，考慮個(gè)體域?yàn)閷?shí)數(shù)集，例如，考慮個(gè)體域?yàn)閷?shí)數(shù)集，H(x，y)表示表示x+y=10，則命題，則命題“對于任意的對于任意的x，都存在，都存在y，使得使得x+y=10”的符號(hào)化形式為的符號(hào)化形式為 x y H(x, y) (2.15) 給命題顯然為真命題給命題顯然為真命題.但是如果改變兩個(gè)量但是如果改變兩個(gè)量詞的順序，得詞的順序，得 y x H(

21、x, y) (2.16) (4.18)已經(jīng)不表示原命題，而且它所表示的已經(jīng)不表示原命題，而且它所表示的命題是假命題命題是假命題.2. 有些命題的符號(hào)化形式可不止一種有些命題的符號(hào)化形式可不止一種.例如，在例如，在例例2.1.5中，中，(3)還可以符號(hào)化為還可以符號(hào)化為 x y(F(x)G(y)H(x,y) (2.17) (4)還可以符號(hào)化為還可以符號(hào)化為 x y(F(x)F(y)L(x,y) (2.18) 這樣，（這樣，（2.1.3）和）和(2.17)都是都是(3)的符號(hào)化形式，的符號(hào)化形式，（2.1.4）與）與(2.18)都是都是(4)的符號(hào)化形式，它們的符號(hào)化形式，它們都是正確的都是正確的

22、(下一節(jié)可以證明下一節(jié)可以證明(2.13)和和(2.17)是是等值的，等值的，(2.14)和和(2.18)是等值的是等值的). 2.2 一階邏輯公式及解釋一階邏輯公式及解釋 一、一階語言一、一階語言 定義定義2.2.1 一階語言一階語言 的字母表定義如下的字母表定義如下: (1)個(gè)體常項(xiàng)個(gè)體常項(xiàng):a, b, c,ai, bi, ci，i1 (2)個(gè)體變項(xiàng)個(gè)體變項(xiàng):x, y, z,，xi, yi, zi，i1 (3)函數(shù)符號(hào)函數(shù)符號(hào):f, g, h,fi, gi, hi，i1 (4)謂詞符號(hào)謂詞符號(hào):F, G, H,Fi, Gi, Hi，i1 (5)量詞符號(hào)量詞符號(hào): (6)聯(lián)結(jié)詞符號(hào)聯(lián)結(jié)詞符號(hào)

23、:, (7)括號(hào)與逗號(hào)括號(hào)與逗號(hào):(,),，,定義定義2.2.2 項(xiàng)的定義如下項(xiàng)的定義如下: (1)個(gè)體常項(xiàng)和個(gè)體變項(xiàng)是項(xiàng)個(gè)體常項(xiàng)和個(gè)體變項(xiàng)是項(xiàng). (2)若若f(x1 , x2 , xn)是任意的是任意的n元函數(shù)，元函數(shù)，t1 , t2 , tn是任意的是任意的n個(gè)項(xiàng)個(gè)項(xiàng),則則f( t1, t2 , tn)是項(xiàng)是項(xiàng). (3)所有的項(xiàng)都是有限次使用所有的項(xiàng)都是有限次使用(1)，(2)得到得到的的. 定義定義2.2.3 設(shè)設(shè)R ( x1 , x2 , , xn )是任意是任意n元謂詞，元謂詞， t1,t2,tn是任意的是任意的n個(gè)項(xiàng)，則稱個(gè)項(xiàng)，則稱R(t1 , t2 , tn)是是原子公式原子公式

24、. 例例2.1.5中的中的1元謂詞元謂詞F(x)，G(x)，2元謂詞元謂詞H(x,y)，L(x,y)等都是原子公式等都是原子公式.(1)原子公式是合式公式原子公式是合式公式. 定義定義2.2.4 的合式公式定義如下的合式公式定義如下:(2)若若A是合式公式，則是合式公式，則(A)也是合式公式也是合式公式. (5)只有有限次的應(yīng)用只有有限次的應(yīng)用(1)(4)構(gòu)成的符號(hào)串構(gòu)成的符號(hào)串才是合式公式才是合式公式. 合式公式也稱為謂詞公式，簡稱公式合式公式也稱為謂詞公式，簡稱公式. (3)若若A，B是合式公式，則是合式公式，則(AB)，(AB)，(AB)，(A B)也是合式公式也是合式公式. (4)若若

25、A是合式公式，則是合式公式，則 xA，xA也是合式公式也是合式公式. 二、自由與約束 定義2.2.5 在公式 xA和 xA中，稱x為指導(dǎo)變元，A為相應(yīng)量詞的轄域.在 x和 x的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn).A中不是約束出現(xiàn)的其他變項(xiàng)均稱為是自由出現(xiàn)的. 例例2.2.6 指出下列各公式中的指導(dǎo)變元，各量詞指出下列各公式中的指導(dǎo)變元，各量詞的轄域，自由出現(xiàn)以及約束出現(xiàn)的個(gè)體變項(xiàng)的轄域，自由出現(xiàn)以及約束出現(xiàn)的個(gè)體變項(xiàng): (1) x(F(x,y)G(x,z) (2.19) (2) x(F(x)G(y) y（H(x)L(x,y,z)(2.20)解解: (1)x是指導(dǎo)變元是指導(dǎo)變元.量詞量詞 的轄域

26、的轄域A=(F(x,y)G(x,z)，在，在A中，中，x是約束出現(xiàn)的是約束出現(xiàn)的.而且約束出現(xiàn)兩次，而且約束出現(xiàn)兩次，y和和z均為自由出現(xiàn)的，均為自由出現(xiàn)的，而且各自由出現(xiàn)一次而且各自由出現(xiàn)一次. (2)公式中含有兩個(gè)量詞，前件上的量詞公式中含有兩個(gè)量詞，前件上的量詞 的的指導(dǎo)變元為指導(dǎo)變元為x， 的轄域的轄域A=(F(x)G(y)，其中，其中x是約束出現(xiàn)的，是約束出現(xiàn)的，y是自由出現(xiàn)的是自由出現(xiàn)的.后件中的量詞后件中的量詞 的指導(dǎo)變元為的指導(dǎo)變元為y， 的轄域的轄域(H(x)L(x,y,z)，其中其中y是約束出現(xiàn)的，是約束出現(xiàn)的，x，z均為自由出現(xiàn)的均為自由出現(xiàn)的.在在整個(gè)公式中，整個(gè)公式中

27、，x約束出現(xiàn)一次，自由出現(xiàn)約束出現(xiàn)一次，自由出現(xiàn)2次，次，y自由出現(xiàn)一次，約束出現(xiàn)一次，自由出現(xiàn)一次，約束出現(xiàn)一次，z只自由出現(xiàn)只自由出現(xiàn)一次一次.三、閉公式三、閉公式 定義定義2.2.6 設(shè)設(shè)A是任意的公式，若是任意的公式，若A中不含有自中不含有自由出現(xiàn)的個(gè)體變項(xiàng)，則稱由出現(xiàn)的個(gè)體變項(xiàng)，則稱A為封閉的公式，為封閉的公式，簡稱閉式簡稱閉式. 如如: x(F(x) G(x), x y(F(x) G(x,y) 為閉為閉 式式而而 x(F(x) G(x,y), z yL(x,y,z) 不是閉式不是閉式. 四、一階公式的解釋四、一階公式的解釋 定義定義2.2.7 I的解釋由下面的解釋由下面4部分組成部

28、分組成: (a)非空個(gè)體域非空個(gè)體域D; (b)D中一些特定元素的集合中一些特定元素的集合; (c)D上特定函數(shù)集合上特定函數(shù)集合; (d)D上特定謂詞的集合上特定謂詞的集合. 例例2.2.7給定解釋給定解釋I如下如下:1)D=2.3;2)D中特定元中特定元a=2;3)函數(shù)函數(shù)f(x)為為f(2)=3,f(3)=2;4)謂詞謂詞F(x)為為 F(2)=0,F(3)=1 G(x,y)為為 G(i,j)=1,i,j=2,3 L(x,y)為為L(2,2)=L(3,3)=0,L(2,3)=L(3,2)=0在解釋在解釋I下下,求下列各式的真值求下列各式的真值.(1) x(F(x) G(x,a)(2) x

29、(F(f(x) G(x,f(x)(3) x yL(x,y) (F(2) G(2,2) (F(3) G(3,2) (0 1) (1 1) 0 (F(f(2) G(2,f(2) (F(f(3) G(3,f(3) 1 (L(2,2) L(2,3) (L(3,2) L(3,3) 0 例例2.2.8給定解釋給定解釋N如下如下:1)個(gè)體域?yàn)樽匀粩?shù)集個(gè)體域?yàn)樽匀粩?shù)集DN2) DN中特定元中特定元a=03) DN上特定函數(shù)上特定函數(shù)f(x,y)=x+y,g(x,y)=xy4) DN上特定謂詞上特定謂詞F(x,y):x=y.在解釋在解釋N下下,下面哪些公式為真下面哪些公式為真,哪些為假哪些為假? (1) xF(

30、g(x,a),x)x(x0=x) 為假命題為假命題(2) x y (F(f(x,a),y) F(f(y,a),x) x y(x+0=y y+0=x) 為真為真命題命題 (3) x y z F(f(x,y),z) x y z (x+y=z) 為為真命題真命題 (4) x y F(f(x,y),g(x,y) x y (x+y=xy)為為假命題假命題(5) F(f(x,y),f(y,z)x+y=y+z ,真值真值不能確定不能確定定理定理2.2.1 封閉的公式在任封閉的公式在任何解釋下都變成命題何解釋下都變成命題. 五、一階公式的分類五、一階公式的分類定義定義2.2.8 設(shè)設(shè)A為一個(gè)公式，若為一個(gè)公式

31、，若A在任何解釋下在任何解釋下均為真，則稱均為真，則稱A為永真式為永真式(或稱邏輯有效式或稱邏輯有效式).若若A在任何解釋下均為假，則稱在任何解釋下均為假，則稱A為矛盾式為矛盾式(或永假式或永假式).若至少存在一個(gè)解釋使若至少存在一個(gè)解釋使A為真，為真，則稱則稱A為可滿足式為可滿足式.定義定義2.2.9 設(shè)設(shè)A0是含有命題變項(xiàng)是含有命題變項(xiàng)p1, p2 , pn的的命題公式，命題公式，A1, A2, , An是是n個(gè)謂詞公式，用個(gè)謂詞公式，用Ai(1in)處處代替處處代替A0中的中的pi，所得公式，所得公式A稱稱為為A0的代換實(shí)例的代換實(shí)例. 定理定理2.2.2 重言式的代換實(shí)例都是永真式，矛重言式的代換實(shí)例都是永真式，矛盾式的代換實(shí)例都是矛盾式盾式的代換實(shí)例