第二章一階邏輯

1、2.1 一階邏輯的基本概念一階邏輯的基本概念2.2 一階邏輯合式公式及解釋一階邏輯合式公式及解釋2.3 一階邏輯等值式一階邏輯等值式 在命題邏輯中在命題邏輯中,我們把原子命題作為基本我們把原子命題作為基本研究單位研究單位,對原子命題不再進(jìn)行分解對原子命題不再進(jìn)行分解,只有復(fù)只有復(fù)合命題才可以分解合命題才可以分解,揭示了一些有效的推理揭示了一些有效的推理過程過程. 但是進(jìn)一步研究發(fā)現(xiàn)，僅有命題邏輯但是進(jìn)一步研究發(fā)現(xiàn)，僅有命題邏輯是無法把一些常見的推理形式包括進(jìn)去是無法把一些常見的推理形式包括進(jìn)去. 例如例如2.1一階邏輯的基本概念一階邏輯的基本概念l形式邏輯的一般格式就是三段論。l例：蘇格拉底三

2、段論：所有的人都是要死的，蘇格拉底是人，所以，蘇格拉底是要死的。（1）凡人都是要死的；）凡人都是要死的；（2）蘇格拉底是人；）蘇格拉底是人；（3）所以蘇格拉底是要死的。）所以蘇格拉底是要死的。p：凡人都是要死的；：凡人都是要死的；q：蘇格拉底是人：蘇格拉底是人;r：所以蘇格拉底是要死的。：所以蘇格拉底是要死的。(pq)r（前提）（前提）（前提）（前提）（結(jié)論）（結(jié)論）蘇格拉底三段論蘇格拉底三段論這不是重言式這不是重言式(110),即即 r 不是前提不是前提p, q的有效結(jié)論的有效結(jié)論. 這反映了命題邏輯的局限性這反映了命題邏輯的局限性,其原因是把本來有內(nèi)在其原因是把本來有內(nèi)在聯(lián)系的命題聯(lián)系的命

3、題p, q, r, 視為獨(dú)立的命題。視為獨(dú)立的命題。原因：命題邏輯不考慮命題之間的內(nèi)在聯(lián)系原因：命題邏輯不考慮命題之間的內(nèi)在聯(lián)系 和數(shù)量關(guān)系。和數(shù)量關(guān)系。 要反映這種內(nèi)在聯(lián)系，就要對命題邏要反映這種內(nèi)在聯(lián)系，就要對命題邏輯進(jìn)行分析輯進(jìn)行分析, ,分析出其中的個體詞、謂詞和分析出其中的個體詞、謂詞和量詞，再研究它們之間的邏輯關(guān)系，總結(jié)出量詞，再研究它們之間的邏輯關(guān)系，總結(jié)出正確的推理形式和規(guī)則，這就是一階正確的推理形式和規(guī)則，這就是一階( (謂詞謂詞) )邏輯的研究內(nèi)容。邏輯的研究內(nèi)容。 辦法：將命題再次細(xì)分。辦法：將命題再次細(xì)分。2.1一階邏輯的基本概念一階邏輯的基本概念 解決這個問題的方法：

4、 在表示命題時，既表示出主語，也表示出謂語，就可以解決上述問題。這就提出了謂詞的概念(謂詞是用來刻劃個體詞的性質(zhì)或事物之間的關(guān)系的詞,謂詞S(x)相當(dāng)于一個函數(shù)).2.1.1 個體、謂詞和命題函數(shù)在謂詞邏輯中，將原子命題分解為謂詞和個體兩部分。1、定義：在原子命題中，所描述的對象稱為個體；用以描述個體的性質(zhì)或個體間關(guān)系的部分，稱為謂詞。2.1一階邏輯的基本概念例例2.12.1：分析下列個命題中的個體和謂詞：分析下列個命題中的個體和謂詞l 是無理數(shù)。是無理數(shù)。l張三與李四同在信息技術(shù)學(xué)院。張三與李四同在信息技術(shù)學(xué)院。l x與與y的和等于的和等于z（x，y，z是確定的數(shù)）。是確定的數(shù)）。l 的平方

5、是非負(fù)的。的平方是非負(fù)的。l所有的實(shí)數(shù)的平方都是非負(fù)的。所有的實(shí)數(shù)的平方都是非負(fù)的。l有一個比有一個比21000大的素數(shù)。大的素數(shù)。（1）是無理數(shù)。解： 個體：（代表圓周率） 謂詞：是無理數(shù)，表示“”的性質(zhì)。（2）張三與李四同在信息技術(shù)學(xué)院。解：個體：張三，李四 謂詞： 與同在信息技術(shù)學(xué)院 表示“張三”與“李四”之間的關(guān)系。 個體：李四謂詞：張三與 同在信息技術(shù)學(xué)院表示“李四”的性質(zhì)。個體：張三謂詞： 與李四同在信息技術(shù)學(xué)院，表示“張三”的性質(zhì)。（3 3）x x 與與 y y 的和等于的和等于 z z （x x，y y，z z是確定的數(shù)）是確定的數(shù)）個體：個體： x x、 y y、 z z謂詞

6、：謂詞： 與與的和等于的和等于個體：個體： x x、 z z謂詞：謂詞： 與與y y的和等于的和等于個體：個體： y y謂詞：謂詞： x x與與的和等于的和等于z z 謂詞可以單個個體的性質(zhì)，也可以表示二個個體詞之間的關(guān)系或性質(zhì)，分別稱為一元謂詞和二元謂詞。表示n個個體間的關(guān)系或性質(zhì)的謂詞稱為n元謂詞 （4） 的平方是非負(fù)的。 解：個體： 謂詞： 的平方是非負(fù)的個體： 的平方謂詞： 是非負(fù)的（5）所有的實(shí)數(shù)的平方都是非負(fù)的。個體：每一個實(shí)數(shù)謂詞： 的平方是非負(fù)的（6）有一個比21000大的素數(shù)。個體：一個素數(shù)謂詞： 比21000大“所有”是什么？量詞：所有“有一個有一個”是什么？是什么？ 量詞

7、：有一個量詞：有一個2.1.1 2.1.1 個體與個體變元基本概念個體與個體變元基本概念個體：能夠獨(dú)立存在的事物，稱之為個體，也稱之為客體。它可以是具體的，也可以是抽象的事物。通常用小寫英文字母a、b、c、.表示。例如，小張、小李、8、a、杭州、社會主義等等都是個體。個體變項：用小寫英文字母x、y、z.表示任何個體詞，則稱這些字母為個體變項。注意：個體變項本身不是個體。2.1.2 謂詞 定義：一個大寫英文字母后邊有括號，括號內(nèi)是若干個個體變項，用以表示個體的屬性或者個體之間的關(guān)系，稱之為謂詞。如果括號內(nèi)有n個個體變項，稱該謂詞為n元謂詞。 一般地 P(x1,x2,xn) 是n元謂詞。（1）張三

8、是個大學(xué)生解： 個體：張三謂詞：是個大學(xué)生。若 用 P 表示謂詞： “ 是個大學(xué)生 ” ; a 表示個體： “ 張三 ” 。則上述命題可表示為P（a）。同理：“李四是個大學(xué)生”， 若b表示個體“李四”，則該命題可表示為P（b）。 對于給定的命題，當(dāng)用表示其個體的小寫字母和表示其謂詞的大寫字母來表示時，規(guī)定將小寫字母寫在大寫字母右側(cè)的（ ）內(nèi)。例2.2 用謂詞表示下列命題（2）陳強(qiáng)與陳佩斯是父子解：a 表示：陳強(qiáng)b 表示：陳佩斯若用 Q 表示二元謂詞： 與 是父子則上述命題可表示為Q（a，b）。又如，若用 R 表示三元謂詞 “位于與之間”，則命題 “杭州位于南京和上海之間” 如何表示？a：杭州，

9、b：南京，c：上海，則上述命題可表示為R（a，b，c）。 2.1.3 2.1.3 命題函數(shù)命題函數(shù) 謂詞本身并不是命題，只有謂詞的括號內(nèi)填入足夠謂詞本身并不是命題，只有謂詞的括號內(nèi)填入足夠的個體，才變成命題。的個體，才變成命題。設(shè)設(shè) H(x) H(x) 是謂詞是謂詞 表示表示 x x “能夠到達(dá)山頂能夠到達(dá)山頂” ， l l 表示個體李四，表示個體李四， t t 表示老虎，表示老虎， c c 表示汽車，表示汽車， 那么那么H H（l l），）， H H（t t），）， H H（c c），等分別表示各），等分別表示各個不同的命題：但它們有一個共同的形式，個不同的命題：但它們有一個共同的形式，即即

10、 H H（x x） 當(dāng)當(dāng) x x 分別取分別取 l l、 t t、 c c 時時就表示就表示“李四能夠到達(dá)山頂李四能夠到達(dá)山頂”，“老虎能夠到達(dá)山老虎能夠到達(dá)山頂頂”，“汽車能夠到達(dá)山頂汽車能夠到達(dá)山頂”。可見可見, ,在謂詞的括號內(nèi)填入不同的內(nèi)容在謂詞的括號內(nèi)填入不同的內(nèi)容, ,就得到不同就得到不同的命題，故謂詞相當(dāng)于一個函數(shù)，的命題，故謂詞相當(dāng)于一個函數(shù)，稱之為命題函數(shù)。稱之為命題函數(shù)。n n元謂詞元謂詞P(x1,x2,P(x1,x2,xn),xn)稱之為稱之為簡單命題函數(shù)簡單命題函數(shù)。規(guī)定：當(dāng)命題函數(shù)規(guī)定：當(dāng)命題函數(shù)P(x1,x2,P(x1,x2,xn),xn)中中 n=0 n=0 時，

11、即時，即0 0元謂詞，表示不含有客體變元的謂詞，它本身就是元謂詞，表示不含有客體變元的謂詞，它本身就是一個命題變元。一個命題變元。將若干個簡單命題函數(shù)用邏輯聯(lián)結(jié)詞聯(lián)結(jié)起將若干個簡單命題函數(shù)用邏輯聯(lián)結(jié)詞聯(lián)結(jié)起來，構(gòu)成的表達(dá)式，稱之為復(fù)合命題函數(shù)。來，構(gòu)成的表達(dá)式，稱之為復(fù)合命題函數(shù)。簡單命題函數(shù)與復(fù)合命題函數(shù)統(tǒng)稱為命題函數(shù)。簡單命題函數(shù)與復(fù)合命題函數(shù)統(tǒng)稱為命題函數(shù)。例如例如: : 給定簡單命題函數(shù)：給定簡單命題函數(shù)： A(x)A(x)：x x身體好，身體好， B(x)B(x)：x x學(xué)習(xí)好，學(xué)習(xí)好， C(x)C(x)：x x工作好，工作好， 復(fù)合命題函數(shù)復(fù)合命題函數(shù) A(x)(A(x)( B(x

12、)B(x) C(x)C(x) 表示如果表示如果x x身體不好，則身體不好，則x x的學(xué)習(xí)與工作的學(xué)習(xí)與工作 都不會好。都不會好。 再如，若L(x,y) 表示“x 小于y”， 那么L(2 ,3) 表示了一個真命題：“2小于3” 而 L(5,1) 表示了一個假命題：“5小于1” 又如 A(x,y,z)表示一個關(guān)系“x 加上 y 等于z” 則 A(3,2,5）表示了真命題 “3+2=5”， 而A(1,2,4）表示了一個假命題“1+2=4”。 可以看出： H(x),L(x,y),A(x,y,z)本身不是一個命題， 只有當(dāng)變元 x，y，z等取特定的客體時， 才確定了一個命題。 設(shè)設(shè)N N（x x）：）：

13、“x x是負(fù)數(shù)是負(fù)數(shù)”,E(x),E(x)：“ x x是整數(shù)是整數(shù) ” 則復(fù)合命題函數(shù)則復(fù)合命題函數(shù) N N（x x） E E（x x）表示：）表示：“x x是負(fù)整數(shù)是負(fù)整數(shù)” N N（x x） E E（x x）表示：）表示： “ x x 是非負(fù)整數(shù)是非負(fù)整數(shù) ” 通常通常, ,對于一個命題函數(shù)對于一個命題函數(shù) Q Q（x x，y y） 若若 Q Q（x x，y y）：）：表示表示“ x x 比比 y y 重重 ”，當(dāng)，當(dāng) x x ，y y 指人或物時，它是一個命題，但若指人或物時，它是一個命題，但若x x ，y y 指指實(shí)數(shù)時，實(shí)數(shù)時， Q Q（x x，y y）就不是一個命題。）就不是一個命

14、題。 命題函數(shù)不是一個命題，只有個體變元取命題函數(shù)不是一個命題，只有個體變元取特定名稱時，才能成為一個命題。但是個體變特定名稱時，才能成為一個命題。但是個體變元在那些范圍內(nèi)取特定的值，對是否成為命題元在那些范圍內(nèi)取特定的值，對是否成為命題及命題的真值即有影響。及命題的真值即有影響。 比如比如: :設(shè)設(shè)R R（x x）：）：“ x x 是大學(xué)生是大學(xué)生”，對，對x x的取值情的取值情況況: :l如果如果 x x 的討論范圍為浙江中醫(yī)藥大學(xué)里班級中的的討論范圍為浙江中醫(yī)藥大學(xué)里班級中的學(xué)生，則學(xué)生，則R R（x x）是永真式。）是永真式。l如果如果 x x 的討論范圍為杭州長河高級中學(xué)里班級中的討

15、論范圍為杭州長河高級中學(xué)里班級中的學(xué)生，則的學(xué)生，則R R（x x）是永假式。）是永假式。l如果如果 x x 的討論范圍為一個劇院中的觀眾，觀眾中的討論范圍為一個劇院中的觀眾，觀眾中有大學(xué)生也有非大學(xué)生，那么對于某些觀眾，有大學(xué)生也有非大學(xué)生，那么對于某些觀眾，R R（x x）為真，對于另一些觀眾，為真，對于另一些觀眾，R R（x x）為假。）為假。命題函數(shù)確定為命題，與個體變元的論述范圍命題函數(shù)確定為命題，與個體變元的論述范圍有關(guān)。有關(guān)。 再如再如 令令G(x，y)： “x高于高于y”，于是，于是，G(x，y)是一個二元謂詞是一個二元謂詞。將將x代以個體代以個體 “張三張三”，y代以個體代以

16、個體 “李四李四”，則則G(張三，李四張三，李四)就是命題就是命題： “張三高于李張三高于李四四”。隨便將。隨便將x，y代以確定的個體，由代以確定的個體，由G(x，y)都能得到一個命題。都能得到一個命題?？梢?，可見，G(x，y)不是命題，而是一個命題函數(shù)不是命題，而是一個命題函數(shù)即謂詞即謂詞。2.1.4 論域(個體域) 定義：在命題函數(shù)中個體變項的取值范圍，稱之為論域，也稱之為個體域。 例如 S(x):x是大學(xué)生，論域是:人類。 G(x,y)：xy， 論域是:實(shí)數(shù)。 論域是一個集合。l定義：由所有個體構(gòu)成的論域，稱之為全總個體域。它是個“最大”的論域。l約定:對于一個命題函數(shù)，如果沒有給定論域

17、，則假定該論域是全總個體域。例例2.4 用謂詞用謂詞(命題函數(shù)命題函數(shù))將下列命題符號化：將下列命題符號化：(1) 丘華和李兵都是學(xué)生；丘華和李兵都是學(xué)生；(2) 2既是偶數(shù)又是素數(shù)；既是偶數(shù)又是素數(shù)；(3) 如果張華比黎明高，黎明比王宏高，則張華比王如果張華比黎明高，黎明比王宏高，則張華比王 宏高。宏高。解解 (1) 設(shè)個體域是人的集合。設(shè)個體域是人的集合。 P(x)：:x是學(xué)生。是學(xué)生。a：丘華丘華b：黎兵黎兵該命題符號化為該命題符號化為P(a) P(b)(2) 2既是偶數(shù)又是素數(shù)；既是偶數(shù)又是素數(shù)； 設(shè)個體域為正整數(shù)集合設(shè)個體域為正整數(shù)集合N。F(x)：x是偶數(shù)，是偶數(shù)，G(x)：x是素

18、數(shù)是素數(shù) a：2該命題符號化為該命題符號化為F(a) G(a)(3) 如果張華比黎明高，黎明比王宏高，則張如果張華比黎明高，黎明比王宏高，則張 華比王宏高。華比王宏高。 設(shè)個體域是人的集合。設(shè)個體域是人的集合。 L(x,y)：x比比y高。高。 a：張華張華 b：黎明黎明 c：王宏王宏 該命題符號化為該命題符號化為L(a,b) L(b,c)L(a,c)2.1.5 量詞例如：有些人是大學(xué)生。 所有事物都是發(fā)展變化的?！坝行?“所有的”,就是對客體量化的詞。量詞：在命題中表示對客體數(shù)量化的詞。定義了兩種量詞： (1).存在量詞：記作，表示“有些”、“一些”、“某些”、“至少一個”等。 (2).全稱

19、量詞：記作，表示“每個”、“任何一個”、“一切”、“所有的”、“凡是”、“任意的”等。 考察下面兩個例子考察下面兩個例子 ( (它們均以整數(shù)作為其個體域它們均以整數(shù)作為其個體域) ) (x+1) (x+1)2 2=x=x2 2+2x+1+2x+1 x+6=5 x+6=5 對于對于任何整數(shù)代入后等式總是成立。用符號任何整數(shù)代入后等式總是成立。用符號“ x x”表示表示“對所有對所有x x”，則則可表示為可表示為 x(x(x+1)(x+1)2 2=x=x2 2+2x+1)+2x+1)但但則不然，只存在一個整數(shù)（則不然，只存在一個整數(shù)（-1-1）代入后才使）代入后才使等式成立號等式成立號“ x x

20、”表示表示“存在某些存在某些x x”, , 則則 可表示為可表示為 x x（ x+6=5x+6=5）（1）所有大學(xué)生都熱愛祖國；）所有大學(xué)生都熱愛祖國； （2）每個自然數(shù)都是實(shí)數(shù)；）每個自然數(shù)都是實(shí)數(shù)；解：解：（1）令）令 S（x）：）：x 是大學(xué)生，是大學(xué)生， L（x）：）：x熱愛祖國熱愛祖國 x（S（x） L（x）（2）令）令 N（x）：）：x 是自然數(shù)，是自然數(shù)， R（x）：）：x 是實(shí)數(shù)是實(shí)數(shù) x（N（x） R（x）（1）有些人是聰明的。）有些人是聰明的。（2）并非一切數(shù)都大于）并非一切數(shù)都大于0。解：解：（1）令）令M（x）：）：x是人，是人， N（x）：）：x是聰明的是聰明的 x（

21、M（ x ） N（ x ） （2）令）令I(lǐng)（x） ：x 是數(shù)（實(shí)數(shù)域），是數(shù)（實(shí)數(shù)域）， R（x）：）：x 是大于零的數(shù)。是大于零的數(shù)。 （ x （ I（x） R （x） x（I（x） R （x）dx)x(fbadx)x(f特別注意：特別注意：謂詞前加上了量詞，稱為謂詞的量謂詞前加上了量詞，稱為謂詞的量化?；Ｈ粢粋€謂詞中所有個體變元都量化了，則若一個謂詞中所有個體變元都量化了，則該謂詞就變成了命題。該謂詞就變成了命題。這是因為在謂詞被量化這是因為在謂詞被量化后，可以在整個個體域中考慮命題的真值了。后，可以在整個個體域中考慮命題的真值了。這如同數(shù)學(xué)中的函數(shù)這如同數(shù)學(xué)中的函數(shù)f(x)，的值是不的

22、值是不確定的，但確定的，但 可確定其值?？纱_定其值。（1）分析命題中表示性質(zhì)和關(guān)系的謂詞，要分）分析命題中表示性質(zhì)和關(guān)系的謂詞，要分別符號化為一元和別符號化為一元和n(n 2)元謂詞。元謂詞。（2）根據(jù)命題的實(shí)際意義選用）根據(jù)命題的實(shí)際意義選用 或或 。（3）一般來說，當(dāng)多個量詞同時出現(xiàn)時，它們）一般來說，當(dāng)多個量詞同時出現(xiàn)時，它們的順的順 序不能隨意調(diào)換。如：序不能隨意調(diào)換。如： 在實(shí)數(shù)域上用在實(shí)數(shù)域上用L(x, y)表示表示x+y=10命題為：命題為： 對于任意的對于任意的x, 都存在都存在y使得使得 x+y=10。 可符號化為：可符號化為： x yL(x,y) 真值為真值為1。 若調(diào)換順

23、序后為：若調(diào)換順序后為： y xL(x,y) 真值為真值為0。（4）有些命題的符號化形式不止一種。）有些命題的符號化形式不止一種。至此，至此，下列推理即可解決：下列推理即可解決： 凡是人都是凡是人都是 要死的。要死的。 蘇格拉底是人。蘇格拉底是人。 蘇格拉底是要死的。蘇格拉底是要死的。設(shè)：設(shè)：M(x):x是人。是人。D(x):x 是要死的。是要死的。a:蘇格拉蘇格拉底。則符號化為：底。則符號化為： x(M(x)x(M(x)D(x)(x) M(a) M(a) D(a) D(a)定義定義2.1 一階語言的字母表定義如下：一階語言的字母表定義如下：（1）個體常項：表示具體的或特定的個體的詞）個體常項

24、：表示具體的或特定的個體的詞 常用常用a , b , c , ai , bi , ci，i 1.1.（2）個體變項：表示抽象的或泛指個體的詞個體變項：表示抽象的或泛指個體的詞 常用常用x , y , z , xi , yi , zi，i 1.1.（3）函數(shù)符號：函數(shù)符號：f , g , h , fi , gi , hi，i 1.1.（4）謂詞符號：謂詞符號：F, G , H,Fi , Gi , Hi，i 1.1.（5）量詞符號：量詞符號： ， . .（6）聯(lián)結(jié)詞符號：）聯(lián)結(jié)詞符號： ，. .（7）括號與逗號：）括號與逗號： （，），（，），. .定義定義2.2一階語言一階語言項項的定義如下：的

25、定義如下：(1) 個體常項和個體變項是項個體常項和個體變項是項(2) 若若f(x1 , x2 , xn ) 是任意的是任意的n元函數(shù)元函數(shù), t1 , t2 , tn 是任意的是任意的n個項，則個項，則f(t1 , t2 , tn )是項。是項。(3) 所有的項都是有限次使用所有的項都是有限次使用 (1), (2) 得到的。得到的。定義定義2.3 若若R(x1, , x2 , xn )是任意的是任意的n元謂詞元謂詞, t1 , t2 , tn 是項，則稱是項，則稱R(t1 , t2 , tn ) 為為原子公式原子公式。 有了項的定義，函數(shù)的概念就可用來表示個有了項的定義，函數(shù)的概念就可用來表示

26、個體常元和個體變元。體常元和個體變元。例如，令例如，令f(x,y)表示表示x+y，謂詞謂詞N(x)表示表示x是自然是自然數(shù)，那么數(shù)，那么f(2,3)表示個體自然數(shù)表示個體自然數(shù)5，而，而N(f(2,3)表表示示5是自然數(shù)。是自然數(shù)。 這里函數(shù)是就廣義而言的這里函數(shù)是就廣義而言的例如例如P(x):x是教授，是教授，f(x):x的父親，的父親，c:張強(qiáng)，那么張強(qiáng)，那么P(f(c)便是表示便是表示“張強(qiáng)的父親是教授張強(qiáng)的父親是教授”這一命題。這一命題。 函數(shù)的使用給謂詞表示帶來很大方便。函數(shù)的使用給謂詞表示帶來很大方便。例如，用謂詞表示命題：例如，用謂詞表示命題：對任意整數(shù)對任意整數(shù) x，x2-1=

27、(x+1)(x-1)是恒等式。是恒等式。令令 I(x):x是整數(shù)，是整數(shù)， f(x)=x2-1，g(x)=(x+1)(x-1)，E(x,y):x=y，則該命題可表示成：則該命題可表示成： ( x)(I(x)E(f(x),g(x)。定義謂詞邏輯公式（簡稱公式）定義謂詞邏輯公式（簡稱公式）（1 1）原子公式是公式）原子公式是公式（2 2）如果）如果A A，B B是公式，則（是公式，則（ A A），（），（ABAB），）， （ABAB），（），（A AB B），（），（A AB B）是公式；）是公式；（3 3）如）如A A為公式，為公式，x x為個體變元，則（為個體變元，則（ x xA A），），

28、（ x xA A）為公式；）為公式；（4 4）公式由且僅由有限次使用（）公式由且僅由有限次使用（1 1），（），（2 2），（），（3 3） 而得。而得。注：量詞后面若有括號，則不能省略。注：量詞后面若有括號，則不能省略。例例2.9 將下列命題表示為謂詞公式將下列命題表示為謂詞公式（1）所有正數(shù)均可開平方）所有正數(shù)均可開平方 （2）有些人是大學(xué)生）有些人是大學(xué)生 ( 3) ( 3)貓必捕鼠貓必捕鼠解：解：（1） 設(shè)設(shè) P（x）：）： x是正數(shù)；是正數(shù)； Q（x）：）： x 可開平方可開平方則命題（則命題（1）可表示為：）可表示為： x（P（x） Q（x）（2） 設(shè)設(shè) R（x）：）：x是人，是人

29、， S（x）：）： x是大學(xué)生，是大學(xué)生，則命題（則命題（2）可表示為：）可表示為： x（R（x）S（x） ( 3 ) ( 3 ) 貓必捕鼠貓必捕鼠解：解：(3)(3) 設(shè)設(shè) C C（x x）：）：“x x是貓是貓”， R R（y y）：）：“y y是鼠是鼠”， A A（ x x，y y）：）：“ x x捕捕y y ”，則語句可表示為：則語句可表示為： x x y y（C C（x x）R R（y y） A A（x x，y y）凡是與某一范圍有關(guān)的對象應(yīng)用量詞來描述。凡是與某一范圍有關(guān)的對象應(yīng)用量詞來描述。 例2.10 用謂詞表示下列語句(1) 沒有最大的自然數(shù)解：設(shè)N（x）：x是自然數(shù)，G（

30、x，y）：“x大于y”， 則 語句可表示為：x( N( x )y( N( y )G(y,x)另一種表示：B（x）：x是最大，則 x（N（x）B（x）可以嗎？(2)(2)并非每個實(shí)數(shù)都是有理數(shù)。并非每個實(shí)數(shù)都是有理數(shù)。 R R（x x）,Q,Q（x x） 解：解： （ x x（R R（x x） Q Q（x x） (3) (3) 沒有不犯錯誤的人。沒有不犯錯誤的人。 F F（x x）,M,M（x x） 解：解： （ x x（ F F（x x） M M（x x）(4)(4)盡管有人聰明，但未必一切人都聰明。盡管有人聰明，但未必一切人都聰明。 M M（x x）,x,x是人是人, P, P（x x）,x

31、,x聰明聰明 解：解： x x( (（M(M(x x）P(P(x x）一、約束變元、與自由變元與指導(dǎo)變元、轄域一、約束變元、與自由變元與指導(dǎo)變元、轄域 在一個謂詞公式中，形如在一個謂詞公式中，形如 x A（x） 或或 x A（x） 的那一部分稱為公式的約束部分，的那一部分稱為公式的約束部分， 在公式在公式 x A（x） 和和 x A（x）中稱）中稱x為指導(dǎo)變元為指導(dǎo)變元 而而A（x）稱為量詞（）稱為量詞（ x或或 x）的作用域或轄域。）的作用域或轄域。 在作用域中在作用域中 x 的任一出現(xiàn)，稱為的任一出現(xiàn)，稱為 x 在公式中的約在公式中的約束出現(xiàn)，束出現(xiàn)，x 稱為約束變元。若在公式中的出現(xiàn)不是

32、約稱為約束變元。若在公式中的出現(xiàn)不是約束出現(xiàn)，則稱束出現(xiàn)，則稱x的出現(xiàn)為自由出現(xiàn)，自由出現(xiàn)的變元的出現(xiàn)為自由出現(xiàn)，自由出現(xiàn)的變元稱為自由變元。稱為自由變元。l x x（P P（x x） y Qy Q（x x，y y）l x Hx H（x x）L L（x x，y y）l x x y y（P P（x x，y y）Q Q（y y，z z） x Rx R（x x、y y）說明：說明：（1 1）若量詞后有括號，則括號內(nèi)的子公式就是該量詞）若量詞后有括號，則括號內(nèi)的子公式就是該量詞的轄域；的轄域；（2 2）若量詞后無括號，則與量詞鄰接的子公式為該量）若量詞后無括號，則與量詞鄰接的子公式為該量詞的轄域；詞的

33、轄域；例例2.11 2.11 指出下列公式的轄域和變元約束的情況指出下列公式的轄域和變元約束的情況1. x（P（x） y Q（x，y）解：解： x 的轄域是（的轄域是（P（x） y Q（x，y），對于），對于x的的轄域而言，轄域而言，x的所有出現(xiàn)均為約束出現(xiàn)，故它是約的所有出現(xiàn)均為約束出現(xiàn)，故它是約束變元。束變元。 y 的轄域是的轄域是Q（x，y），對于），對于 y 的轄域而言，的轄域而言，y 的的出現(xiàn)為約束出現(xiàn)，故它是約束變元。出現(xiàn)為約束出現(xiàn)，故它是約束變元。例例2.11 2.11 指出下列公式的轄域和變元約束的情況指出下列公式的轄域和變元約束的情況 變元的轄域?qū)嶋H上是可嵌套的，例如：公式變

34、元的轄域?qū)嶋H上是可嵌套的，例如：公式 x（F（x）x（G（x）F（x） 其中量詞其中量詞 x 的轄域為：的轄域為：（F（x）x（G（x）F（x），），而量詞而量詞 x 的轄域為：（的轄域為：（G（x）F（x）。）。實(shí)際上在子公式（實(shí)際上在子公式（G（x）F（x）中的）中的 x 被量詞被量詞 x 約束，而不是被量詞約束，而不是被量詞 x 約束。約束。實(shí)際上，上述公式等價于：實(shí)際上，上述公式等價于： x（F（x）y（G（y）F（y）在使用謂詞邏輯公式符號化命題時，要小心地選擇變元，在使用謂詞邏輯公式符號化命題時，要小心地選擇變元，以使得到的公式滿足上述兩個條件。以使得到的公式滿足上述兩個條件。2.

35、 x H（x）L（x，y）解：解： x 的轄域是的轄域是H（x）,x 是約束出現(xiàn)是約束出現(xiàn),故故 x 為約束變元為約束變元在在L（x，y）中）中 x，y 均為自由出現(xiàn)，均為自由出現(xiàn)，故對于整個公式來說，故對于整個公式來說，x 既為約束變元，又為既為約束變元，又為自由變元，自由變元，y為自由變元。為自由變元。 例例2.11 2.11 指出下列公式的轄域和變元約束的情況指出下列公式的轄域和變元約束的情況3.3. x x y y（P P（x x，y y）Q Q（y y，z z） x Rx R（x x、y y）解：解： x x y y 的轄域均為（的轄域均為（P P（x x，y y）Q Q（y y，z

36、 z），其中，），其中，x x、y y均為約束出現(xiàn)，故是約束變元，均為約束出現(xiàn)，故是約束變元，z z是自由變元。是自由變元。 x x的轄域為的轄域為R R（x x、y y），），x x為約束出現(xiàn)，故是約束變元，為約束出現(xiàn)，故是約束變元，y y為自由出現(xiàn)，故是自由變元。為自由出現(xiàn)，故是自由變元。在整個公式中，在整個公式中，x x是約束變元，是約束變元，y y既是約束變元，既是約束變元，又是自由變元，又是自由變元，z z是自由變元。是自由變元。例例2.11 2.11 指出下列公式的轄域和變元約束的情況指出下列公式的轄域和變元約束的情況換名規(guī)則換名規(guī)則 設(shè)設(shè)A A是一公式，將是一公式，將A A中某個

37、轄域中中某個轄域中約束變項約束變項的的所有出現(xiàn)及相應(yīng)的所有出現(xiàn)及相應(yīng)的指導(dǎo)變元指導(dǎo)變元，改成該量詞轄域中，改成該量詞轄域中未曾出現(xiàn)的某個個體變項符號，公式中其它部分未曾出現(xiàn)的某個個體變項符號，公式中其它部分不變，設(shè)所得公式為不變，設(shè)所得公式為A,A,則則 A A A A。代替規(guī)則代替規(guī)則 設(shè)設(shè)A A是一公式，將是一公式，將A A中某個中某個自由出現(xiàn)自由出現(xiàn)的個體變的個體變項所有出現(xiàn)用項所有出現(xiàn)用A A中未曾出現(xiàn)的個體變項符號代替中未曾出現(xiàn)的個體變項符號代替，A A中其它部分不變，設(shè)所得公式為中其它部分不變，設(shè)所得公式為A,A,則則 A A A A。 注意：注意：在一公式中，有的個體變元既可以在

38、一公式中，有的個體變元既可以是約束出現(xiàn)，又可以是自由出現(xiàn)，這就容易產(chǎn)是約束出現(xiàn)，又可以是自由出現(xiàn)，這就容易產(chǎn)生混淆。為了避免混淆，采用下面兩個規(guī)則：生混淆。為了避免混淆，采用下面兩個規(guī)則：約束約束出現(xiàn)用換出現(xiàn)用換名規(guī)則，將量詞轄域中某個約名規(guī)則，將量詞轄域中某個約束出現(xiàn)的個體變元及相應(yīng)指導(dǎo)變元，改成本轄束出現(xiàn)的個體變元及相應(yīng)指導(dǎo)變元，改成本轄域中未曾出現(xiàn)過的個體變元，其余不變。域中未曾出現(xiàn)過的個體變元，其余不變。例例 x F(x)x F(x)G(x,y) (G(x,y) (換名規(guī)則換名規(guī)則, ,將約束出現(xiàn)將約束出現(xiàn) z zF(F(z z)G(x,y) )G(x,y) 的的x x改成改成z)z)

39、 自由變元代入規(guī)則，對某自由出現(xiàn)的個自由變元代入規(guī)則，對某自由出現(xiàn)的個體變元可用個體常元或用與原子公式中所有個體變元可用個體常元或用與原子公式中所有個體變元不同的個體變元去代入，且處處代入。體變元不同的個體變元去代入，且處處代入。例例 x F(x)G(x,y) (代替規(guī)則代替規(guī)則,將自由出現(xiàn)將自由出現(xiàn) x F(x)G(z,y) 的的x改成改成z)換名規(guī)則換名規(guī)則是替換約束變項及相應(yīng)的指導(dǎo)變元。是替換約束變項及相應(yīng)的指導(dǎo)變元。代替規(guī)則代替規(guī)則是代替自由出現(xiàn)的個體變項是代替自由出現(xiàn)的個體變項例例 x x y(R(x,y)L(y,z)y(R(x,y)L(y,z) x H(x,y) x H(x,y)

40、x x y(R(x,y)L(y,z)y(R(x,y)L(y,z) t tH(H(t t,y),y) ( (換名規(guī)則換名規(guī)則t)t) x x y(R(x,y)L(y,z)y(R(x,y)L(y,z) t t H( H(t t,w) ,w) ( (代替規(guī)則代替規(guī)則 w)w) 該公式中，該公式中， 不存在既是不存在既是約束出現(xiàn)約束出現(xiàn)， 又是又是自由出現(xiàn)自由出現(xiàn)的個體變項。的個體變項。公式解釋公式解釋 一般情況下，一階邏輯公式含有：一般情況下，一階邏輯公式含有：個體常元、個體常元、個體變元（約束變元或自由變元）、函數(shù)變個體變元（約束變元或自由變元）、函數(shù)變元、謂詞變元等，元、謂詞變元等，對各種變元用

41、指定的特殊對各種變元用指定的特殊常元去代替，就構(gòu)成了一個公式的解釋。當(dāng)常元去代替，就構(gòu)成了一個公式的解釋。當(dāng)然在給定的解釋下，可以對多個公式進(jìn)行解然在給定的解釋下，可以對多個公式進(jìn)行解釋。下面給出解釋的一般定義。釋。下面給出解釋的一般定義。帶量詞的公式在論域內(nèi)的展開式帶量詞的公式在論域內(nèi)的展開式 例例2.12 2.12 令令A(yù)(x)A(x)：表示：表示x x是整數(shù)是整數(shù),B(x),B(x)：表示：表示x x是奇數(shù)，是奇數(shù)， 設(shè)論域是設(shè)論域是1,2,3,4,51,2,3,4,5， 謂詞公式謂詞公式 xA(x)xA(x) 表示論域內(nèi)所有的客體都是整數(shù)表示論域內(nèi)所有的客體都是整數(shù) 顯然公式顯然公式

42、xA(x)xA(x)的真值為真，因為的真值為真，因為 A(1)A(1)、A(2)A(2)、A(3)A(3)、A(4)A(4)、A(5)A(5)都為真都為真 于是有于是有 xA(x)xA(x)A(1)A(2)A(3)A(4)A(5)A(1)A(2)A(3)A(4)A(5)帶量詞的公式在論域內(nèi)的展開式帶量詞的公式在論域內(nèi)的展開式 例例2.11 2.11 令令A(yù)(x)A(x)：表示：表示x x是整數(shù)，是整數(shù)， B(x) B(x)：表示：表示x x是奇數(shù)，是奇數(shù)， 設(shè)論域是設(shè)論域是1,2,3,4,51,2,3,4,5， 謂詞公式謂詞公式 xB(x)xB(x) 表示論域內(nèi)有些客體是奇數(shù)，表示論域內(nèi)有些客

43、體是奇數(shù)， 顯然公式顯然公式 xB(x)xB(x)的真值也為真，因為的真值也為真，因為 B(1)B(1)、B(3)B(3)、B(5)B(5)的真值為真，的真值為真， 于是有于是有 xB(x)xB(x)B(1)B(1)B(2)B(2)B(3)B(3)B(4)B(4)B(5)B(5) 一般地，設(shè)論域為一般地，設(shè)論域為aa1 1,a,a2 2,.,a,.,an n ，則，則 1. 1. xA(x)xA(x)A(a1)A(a2).A(an)A(a1)A(a2).A(an) 2. 2. xB(x)xB(x)B(a1)B(a2).B(an)B(a1)B(a2).B(an)定義定義2.7 一個解釋一個解釋

44、I 由下列由下列4部分組成：部分組成：(1) 非空個體域非空個體域DI。( 2 ) DI中 一 些 特 定 元 素 的 集 合中 一 些 特 定 元 素 的 集 合a1,a2,ai,.(3) DI上特定函數(shù)集合上特定函數(shù)集合fin|i,n 1.(4) DI上特定謂詞的集合上特定謂詞的集合Fin|i,n 1.所謂一個解釋不外乎指定個體域、個體域所謂一個解釋不外乎指定個體域、個體域中一些特定的元素、特定的函數(shù)和謂詞等中一些特定的元素、特定的函數(shù)和謂詞等例例2.12：給定解釋給定解釋I如下：求下列各式的真值如下：求下列各式的真值(1) DI=2,3；(2) DI中的特定元素中的特定元素 a =2；(

45、3) DI上的函數(shù)上的函數(shù)f(x)為為f(2)=3, f(3)=2;(4) DI上的謂詞上的謂詞F(x)為為F(2)=0, F(3)=1;. G(x, y)為為G(i, j)=1 i, j=2, 3 G(2, 3)= G(3, 2)= G(2, 2)= 1, G(3, 3)=1; L(x, y)為為L(2, 2)=L(3, 3)=1, L(2, 3)= L(3, 2)= 0; (1) x(F(x)G(x,a) 解解 x(F(x)G(x,a) (F(2)G(2,2)(F(3)G(3,2) ( 0 1)(11) 0例例2.12：給定解釋給定解釋I如下：求下列各式的真值如下：求下列各式的真值(1)

46、DI=2,3；(2) DI中的特定元素中的特定元素 a =2；(3) DI上的函數(shù)上的函數(shù)f(x)為為f(2)=3, f(3)=2;(4) DI上的謂詞上的謂詞F(x)為為F(2)=0, F(3)=1;. G(x,y)為為G(i, j)=1 i,j=2,3 G(2,3)= G(3,2)= G(2, 2)= 1, G(3,3)=1; L(x,y)為為L(2,2)=L(3,3)=1, L(2,3)= L(3,2)= 0; (2) x(F(f(x)G(x,f(x) x (F(f(x) G(x,f(x) (F(f(2)G(2,f(2)(F(f(3)G(3,f(3) ( 11)(01) 1例例2.12：

47、給定解釋給定解釋I如下：求下列各式的真值如下：求下列各式的真值(1) DI=2,3；(2) DI中的特定元素中的特定元素 a =2；(3) DI上的函數(shù)上的函數(shù)f(x)為為f(2)=3, f(3)=2;(4) DI上的謂詞上的謂詞F(x)為為F(2)=0, F(3)=1;. G(x,y)為為G(i, j)=1 i,j=2,3 G(2,3)= G(3,2)=1, G(3,3)=1; L(x,y)為為L(2,2)=L(3,3)=1, L(2,3)= L(3,2)= 0;解解 (3) x x yL(x,y)yL(x,y) ( ( y(L(2 ,y) (y(L(2 ,y) ( yL(3,y)yL(3,

48、y) ( (L(2,2)L(2,3)L(2,2)L(2,3)( (L(3,2)L(3,3)L(3,2)L(3,3) 1 111 1 1 規(guī)律：規(guī)律： 用用 用用 公式類型公式類型 若一公式在任何解釋下都是真的，稱若一公式在任何解釋下都是真的，稱 該公式為邏輯有效的，或永真的。該公式為邏輯有效的，或永真的。 若一公式在任何解釋下都是假的，稱若一公式在任何解釋下都是假的，稱 該公式為矛盾式，或永假式。該公式為矛盾式，或永假式。 若一公式至少存在一個解釋使其為真若一公式至少存在一個解釋使其為真 ，稱該公式為可滿足式。，稱該公式為可滿足式。 與命題公式中分類一樣，與命題公式中分類一樣， 謂詞公式也分為

49、三種類型，謂詞公式也分為三種類型， 即即 邏輯有效式（或重言式）、邏輯有效式（或重言式）、 矛盾式（或永假式）矛盾式（或永假式） 可滿足式。可滿足式。例例2.13：給定解釋給定解釋N如下：如下：(1) 個體域為自然數(shù)集合個體域為自然數(shù)集合DN；(2) DN中的特定元素中的特定元素 a =0；(3) DN上的函數(shù)上的函數(shù)f(x,y)=x+y,g(x,y)=xy;(4) DN上的謂詞上的謂詞F(x,y)為為x=y;在解釋在解釋N下下,下面哪些公式為真？哪些公式為假？下面哪些公式為真？哪些公式為假？(1) xF(g(x,a),x);xF(g(x,a),x);(2) x x y(F(f(x,a),y)

50、y(F(f(x,a),y)F(f(y,a),x)F(f(y,a),x) ；(3) x x y y zF(f(x,y),z)zF(f(x,y),z);(4) x x yF(f(x,y),g(x,y)yF(f(x,y),g(x,y);(5) F(f(x,y),f(y,z)F(f(x,y),f(y,z);例例2.13：給定解釋給定解釋N如下：如下：(1) 個體域為自然數(shù)集合個體域為自然數(shù)集合DN；(2) DN中的特定元素中的特定元素 a =0；(3) DN上的函數(shù)上的函數(shù) f(x, y)= x+y, g(x, y)= xy;(4) DN上的謂詞上的謂詞F(x, y)為為 x=y;在解釋在解釋N下下,

51、公式分別化為：公式分別化為：(1) xF(g(x,a),x) xF(g(x,a),x) x F(g(x,0),x)x F(g(x,0),x) x F(xx F(x 0,x)0,x) x(0=x) x(0=x) 這是假命題這是假命題例例2.13：給定解釋給定解釋N如下：如下：(1) 個體域為自然數(shù)集合個體域為自然數(shù)集合DN；(2) DN中的特定元素中的特定元素 a =0；(3) DN上的函數(shù)上的函數(shù) f(x, y)=x+y, g(x, y)=xy;(4) DN上的謂詞上的謂詞F(x,y)為為x=y;在解釋在解釋N下下,公式分別化為：公式分別化為：(2) x x y(F(f(x,a),y)y(F(

52、f(x,a),y)F(f(y,a),x)F(f(y,a),x) x x y(F(x+0,y)y(F(x+0,y)F(y+0,x)F(y+0,x) x x y(x+0=yy(x+0=yy+0=x)y+0=x) x x y(x=yy(x=yy=x) y=x) 這是真命題這是真命題例例2.13：給定解釋給定解釋N如下：如下：(1) 個體域為自然數(shù)集合個體域為自然數(shù)集合DN；(2) DN中的特定元素中的特定元素 a =0；(3) DN上的函數(shù)上的函數(shù) f(x,y)=x+y, g(x,y)=xy;(4) DN上的謂詞上的謂詞F(x,y)為為x=y;在解釋在解釋N下下,公式分別化為：公式分別化為：(3)

53、x y z(F(f(x,y),z) x y z(F(f(x,y),z) x y z(F(x+y,z) x y z(x+y=z) 這是真命題這是真命題 例例2.13：給定解釋給定解釋N如下：如下：(1) 個體域為自然數(shù)集合個體域為自然數(shù)集合DN；(2) DN中的特定元素中的特定元素 a =0；(3) DN上的函數(shù)上的函數(shù) f(x,y)=x+y, g(x,y)=xy;(4) DN上的謂詞上的謂詞 F(x,y) 為為 x = y;解解(4) x x yF(f(x,y),g(x,y)yF(f(x,y),g(x,y) x x yF(x+y,xyF(x+y,x y)y) x x y(x+y=xy(x+y=

54、x y) y) 這是假命題這是假命題(5) F(f(x,y),f(y,z) F(x+y,y+z) 它的真值不確定它的真值不確定 x+y=y+z 因而不是命題因而不是命題 定義定義2.8 設(shè)設(shè)A為一公式為一公式,若若A在任何解釋下均為在任何解釋下均為真則稱真則稱A為永真式為永真式(邏輯有效式邏輯有效式)。若。若A在任何在任何解釋下均為假解釋下均為假,則稱則稱A為矛盾式為矛盾式(永假式永假式)。若。若至少存在一個解釋使至少存在一個解釋使A為真，則稱為真，則稱A為可滿為可滿足式。足式。 在一階邏輯里面，由于公式的復(fù)雜性和解在一階邏輯里面，由于公式的復(fù)雜性和解釋的多樣性，迄今為止還沒有一種能判斷任釋的

55、多樣性，迄今為止還沒有一種能判斷任意一個公式是否可滿足的或不可滿足的算法。意一個公式是否可滿足的或不可滿足的算法。定義定義2.9 設(shè)設(shè)A0是含是含p1 ,p2 ,pn 命題變項的命命題變項的命題公式，題公式，A1 ,A2 ,An 是是n個謂詞公式，用個謂詞公式，用Ai (1 i n)處處代替處處代替A0 中的中的pi ，所得公所得公式式A稱為稱為A0 的代換實(shí)例。的代換實(shí)例。 重言式的代換實(shí)例都是永真式，矛盾重言式的代換實(shí)例都是永真式，矛盾式的代換實(shí)例都是矛盾式。式的代換實(shí)例都是矛盾式。如：如：F(x) G(x) xF(x)xG(x)等都是等都是 p q 的代換實(shí)例的代換實(shí)例例例2.14 判斷

56、下列公式的類型判斷下列公式的類型1. ( xF(x) y G(y) yG(y)xF(x)2. ( xF(x) xF(x)( yG(y) yG(y)解：解：1. (pq ) q p 永真式永真式2. (p p) (q q) 矛盾式矛盾式例例2.15 判斷下列各公式的類型。判斷下列各公式的類型。(1) F(x,y) (G(x,y) F(x,y) 代換實(shí)例代換實(shí)例 p (q p) 重言式重言式(2) x (F(x) F(x) y(G(y) G(y) ) 蘊(yùn)涵式前件蘊(yùn)涵式前件 x (F(x) F(x) 為為1， 蘊(yùn)涵式后件蘊(yùn)涵式后件 y(G(y) G(y) )為為0， 所以為矛盾式。所以為矛盾式。(3

57、) x y(P(x,y) P(x,y) ) 令個體域為實(shí)數(shù)集令個體域為實(shí)數(shù)集,因為對實(shí)數(shù)集中任取一組因為對實(shí)數(shù)集中任取一組x, y公公式式 P(x,y) P(x,y) 總是假，所以總是假，所以 x y(P(x,y) P(x,y) ) 為矛盾式。為矛盾式。(4) ( ( x F(x) y Gy G(y) y Gy G(y) 代換實(shí)例代換實(shí)例 (p q) q 矛盾式矛盾式(5) x y F(x,y) x y F(x,y) 取解釋取解釋I為為: 個體域是整數(shù)集個體域是整數(shù)集Z，F(xiàn)(x,y) : x=10+y 則則 x y y F(x,y) x y y F(x,y) 前件前件 x y y (x=10+

58、y) 為真為真 后件后件 x y y(x=10+y) 為假為假 所以蘊(yùn)涵式為假，為矛盾式所以蘊(yùn)涵式為假，為矛盾式(5) x y y F(x,y) x y y F(x,y) 取解釋取解釋I為為: 個體域是自然數(shù)個體域是自然數(shù)N， F(x,y):x y。 x y y F(x,y) x y yF(x,y) 前件前件 x y y (x y ) 為真為真 后件后件 x y y(x y ) 為真為真 所以蘊(yùn)涵式為真所以蘊(yùn)涵式為真, 為重言式為重言式(5) x y y F(x,y) x y y F(x,y) 取解釋取解釋I為為: 個體域是自然數(shù)個體域是自然數(shù)N， F(x,y): x y 。 x y y F(

59、x,y) x y yF(x,y) 前件前件 x y y ( x y ) 為假為假 后件后件 x y y(x y ) 為假為假 所以蘊(yùn)涵式真所以蘊(yùn)涵式真, 為重言式為重言式 綜上所述綜上所述 (5)中公式在不同的解釋下真值不同中公式在不同的解釋下真值不同, 可見可見 x y y F(x,y) x y y F(x,y) 是非邏輯有效式的可滿足式。見是非邏輯有效式的可滿足式。見P45例例2.9（5）例例2.16 2.16 給定解釋給定解釋I I 如下如下: : (a) 個體域個體域 D=N (b) (c) (d) 謂詞謂詞說明下列公式在說明下列公式在 I 下的涵義下的涵義,并討論真值并討論真值 (1

60、) xF(g(x,a),x)2axyyxgyxyxf),(,),(yxyxF: ),( x(2x=x) 假命題假命題(2) x y(F(f(x,a),y)F(f(y,a),x) x y(x+2=yy+2=x) 假命題假命題(3) x y zF(f(x,y),z)兩點(diǎn)說明兩點(diǎn)說明:5個小題都是閉式個小題都是閉式,在在I下全是命題下全是命題(3)與與(5)說明，量詞順序不能隨意改變說明，量詞順序不能隨意改變 (5) x y zF(f(y,z),x) x y z (y+z=x) 假命題假命題(4) xF(f(x,x),g(x,x) x(2x=x2) 真命題真命題 x y z (x+y=z) 真命題真