第二章一階邏輯

1、掌握掌握:1. n元謂詞、特性謂詞、量詞、命題符號化、元謂詞、特性謂詞、量詞、命題符號化、2.一階語言的組成、項、原子公式、一階公式一階語言的組成、項、原子公式、一階公式、量詞的轄域、約束變元、自由變元。封閉公、量詞的轄域、約束變元、自由變元。封閉公式、解釋與賦值、永真式、永假式、可滿足式式、解釋與賦值、永真式、永假式、可滿足式、重言式、公式類型的判定。、重言式、公式類型的判定。3.等值演算、常用等值式等值演算、常用等值式 4. 前束范式前束范式5.邏輯推論、邏輯推論、關(guān)于量詞的規(guī)則、關(guān)于量詞的規(guī)則、推理的證明推理的證明第二章第二章 一一 階階 邏邏 輯輯個體個體:把所討論的對象稱為把所討論的

2、對象稱為個體。個體。個體域：個體域：所有討論對象組成的集合稱為所有討論對象組成的集合稱為個體域個體域。 個體域可以是有限集合，也可以是無限集個體域可以是有限集合，也可以是無限集合，但不能是空集。合，但不能是空集。 如不特別指出個體域是什么集合，就意味如不特別指出個體域是什么集合，就意味著個體域包含宇宙間一切事物，這個個體域稱著個體域包含宇宙間一切事物，這個個體域稱為為全總個體域全總個體域。2.1 一階邏輯的基本概念一階邏輯的基本概念 個體常項（也稱個體常元，簡稱常元）：個體常項（也稱個體常元，簡稱常元）：個體個體域中一個特定個體的符號。一般用小寫英文字域中一個特定個體的符號。一般用小寫英文字母

3、母a, b, c, d 等表示常元。等表示常元。 個體變項（也稱個體變元，簡稱變元）：個體變項（也稱個體變元，簡稱變元）：泛指泛指個體域中個體的符號。一般用小寫英文字母個體域中個體的符號。一般用小寫英文字母x, y, z 等表示變元。等表示變元。 例例 2是有理數(shù)。是有理數(shù)。 這是一個簡單命題。這是一個簡單命題。 “2”是個體詞是個體詞 “是有理數(shù)是有理數(shù)”是謂詞，它表示個體的性是謂詞，它表示個體的性質(zhì)。質(zhì)。個體詞：個體詞：是表示個體的符號。是表示個體的符號。謂詞：謂詞：用來刻畫個體的性質(zhì)或個體之間的關(guān)用來刻畫個體的性質(zhì)或個體之間的關(guān) 系。一般用大寫英文字母表示謂詞。系。一般用大寫英文字母表示

4、謂詞。 例例 張三比李四高。張三比李四高。 有兩個個體詞：張三，李四有兩個個體詞：張三，李四“比比高高”是謂詞，表示兩個體之間的關(guān)是謂詞，表示兩個體之間的關(guān)系。系。 命題符號化時，要指定個體域，并命題符號化時，要指定個體域，并 用大寫英用大寫英文字母表示謂詞，用小寫英文字母表示個體，文字母表示謂詞，用小寫英文字母表示個體，用小寫英文字母用小寫英文字母f，g，h表示運算。表示運算。 如果需要為一個謂詞提供如果需要為一個謂詞提供n個個體才能使其成個個體才能使其成為命題，則稱該謂詞為為命題，則稱該謂詞為n元謂詞元謂詞。例；例；“是有理數(shù)是有理數(shù)” 是一元謂詞是一元謂詞 “比比高高” 是二元謂詞是二元

5、謂詞令令P表示表示 “是有理數(shù)是有理數(shù)” ，則，則P(x)表示表示“x是有是有理數(shù)理數(shù)” H表示表示“比比高高”， 則則H(x,y)表示表示“x比比y高高” 命題符號化命題符號化例：將下列命題符號化例：將下列命題符號化1） 2是有理數(shù)。是有理數(shù)。 2）張三比李四高。）張三比李四高。3）2與與3之和小于之和小于2與與3之積。之積。解：解： 1）設(shè)個體域：有理數(shù)集。）設(shè)個體域：有理數(shù)集。 P（x）：）：x是有理數(shù)。是有理數(shù)。 a：2 該命題符號化為該命題符號化為P（a） 2）設(shè)個體域：人的集合。）設(shè)個體域：人的集合。 H(x, y)：x比比y高。高。 a：張三：張三 b：李四：李四 該命題符號化為

6、該命題符號化為 H(a, b)3）設(shè)個體域：正整數(shù)集合。）設(shè)個體域：正整數(shù)集合。 f(x, y)=x+y g(x, y)=xy P(x, y)：x小于小于y a：2 b：3該命題符號化為該命題符號化為P( f(a, b), g(a, b) )量詞量詞全稱量詞全稱量詞：用：用 “ ”表示。表示。 對應(yīng)于漢語中的對應(yīng)于漢語中的“一切一切”、“每個每個”、“所有的所有的”、“任意的任意的”等等 。 xF(x) 表示個體域中的每個元素都有性質(zhì)表示個體域中的每個元素都有性質(zhì)F。存在量詞：存在量詞：用用 “ ”表示。表示。 對應(yīng)于漢語中的對應(yīng)于漢語中的“有的有的”、“至少有一個至少有一個”或或“存在存在”

7、等。用符號等。用符號“”“”表示。表示。 xF(x)表示個體域中至少有一個元素有性質(zhì)表示個體域中至少有一個元素有性質(zhì)F。 全稱量詞和存在量詞的意義是由個體域決定全稱量詞和存在量詞的意義是由個體域決定的，改變個體域，全稱量詞和存在量詞的意義的，改變個體域，全稱量詞和存在量詞的意義也隨之改變。也隨之改變。 例：令例：令F(x)：x需要呼吸。需要呼吸。若個體域為人的集合，則若個體域為人的集合，則 xF(x)表示表示 “所有的所有的人都需要呼吸人都需要呼吸”。若個體域為動物的集合，則若個體域為動物的集合，則 xF(x) 表示表示 “所所有的動物都需要呼吸有的動物都需要呼吸”。若個體域為全總個體域，則若

8、個體域為全總個體域，則 xF(x)表示表示 “宇宙宇宙中的所有事物都需要呼吸中的所有事物都需要呼吸”。 對于同一個命題，符號化時可取不同的集合對于同一個命題，符號化時可取不同的集合作為個體域，取的個體域不同，符號化的結(jié)果作為個體域，取的個體域不同，符號化的結(jié)果可能不同?？赡懿煌?。 若需要斷定的是個體域的一個真子集中的元若需要斷定的是個體域的一個真子集中的元素具有某性質(zhì)，則需引進表示個體域的這個真素具有某性質(zhì)，則需引進表示個體域的這個真子集的一元謂詞，我們稱其為子集的一元謂詞，我們稱其為特性謂詞特性謂詞。 若要斷定的是個體域的一個真子集中的若要斷定的是個體域的一個真子集中的每個每個元素元素都有某

9、性質(zhì)，特性謂詞后應(yīng)該用聯(lián)結(jié)詞都有某性質(zhì)，特性謂詞后應(yīng)該用聯(lián)結(jié)詞“” （即（即 對應(yīng)對應(yīng) ）。）。 若要斷定的是個體域的一真子集中若要斷定的是個體域的一真子集中存在元素存在元素有某性質(zhì)，特性謂詞后應(yīng)用聯(lián)結(jié)詞有某性質(zhì)，特性謂詞后應(yīng)用聯(lián)結(jié)詞“ ” （即（即 對應(yīng)對應(yīng) ）例：例：將下列命題符號化。將下列命題符號化。 每個人都有心臟。每個人都有心臟。 有的人吸煙。有的人吸煙。解解 ：若取個體域為人的集合：若取個體域為人的集合 令令 P(x)：x有心臟。有心臟。 則該命題符號化為則該命題符號化為 x P(x) 若取個體域為動物的集合若取個體域為動物的集合 令令 R(x)：x是人，是人， P(x)：x有心臟

10、。有心臟。 則該命題符號化為則該命題符號化為 x(R(x)P(x)。 若取個體域為人的集合若取個體域為人的集合 令令 S(x)：x吸煙吸煙 則該命題符號化為則該命題符號化為 x S(x) 若取個體域為動物的集合若取個體域為動物的集合 令令 R(x)：x是人，是人，S(x)：x吸煙。吸煙。 則該命題符號化為則該命題符號化為 x(R(x) S(x)注：注：若不特別指出，命題符號化均在全總個體若不特別指出，命題符號化均在全總個體 域中。域中。練習(xí)練習(xí)1： 在一階邏輯中將下列命題符號化。在一階邏輯中將下列命題符號化。 有的有理數(shù)是整數(shù)。有的有理數(shù)是整數(shù)。 每個計算機系的學(xué)生都學(xué)離散數(shù)學(xué)。每個計算機系的

11、學(xué)生都學(xué)離散數(shù)學(xué)。 每個人都會犯錯誤。每個人都會犯錯誤。 存在著偶素數(shù)。存在著偶素數(shù)。 在北京工作的人未必都是北京人。在北京工作的人未必都是北京人。 解解 有的有理數(shù)是整數(shù)。有的有理數(shù)是整數(shù)。令令Q(x)：x是有理數(shù)。是有理數(shù)。 P(x)：x是整數(shù)。是整數(shù)。 本命題符號化為本命題符號化為 x (Q(x)P(x)。每個計算機系的學(xué)生都學(xué)離散數(shù)學(xué)。每個計算機系的學(xué)生都學(xué)離散數(shù)學(xué)。令令P(x)：x是計算機系的學(xué)生。是計算機系的學(xué)生。 R(x)：x學(xué)離散數(shù)學(xué)。學(xué)離散數(shù)學(xué)。 本命題符號化為本命題符號化為 x (P(x)R(x)。 每個人都會犯錯誤。每個人都會犯錯誤。 令令 R(x)：x是人。是人。 P(

12、x)：x會犯錯誤。會犯錯誤。本命題符號化為本命題符號化為 x (R(x)P(x)。 存在著偶素數(shù)。存在著偶素數(shù)。 令令E(x)：x是偶數(shù)。是偶數(shù)。P(x)：x是素數(shù)。是素數(shù)。本命題符號化為本命題符號化為 x(E(x)P(x)。 在北京工作的人未必都是北京人。在北京工作的人未必都是北京人。 令令W(x)：x在北京工作。在北京工作。 B(x)：x是北京人。是北京人。本命題符號化為本命題符號化為 x(W(x)B(x)。 練習(xí)練習(xí)2 在一階邏輯中將下列命題符號化。在一階邏輯中將下列命題符號化。 兔子比烏龜跑得快。兔子比烏龜跑得快。 每個人都有自己喜歡的職業(yè)。每個人都有自己喜歡的職業(yè)。 不存在同樣高的兩

13、個人。不存在同樣高的兩個人。 存在最小的自然數(shù)。存在最小的自然數(shù)。解解 兔子比烏龜跑得快。兔子比烏龜跑得快。令令F(x)：x是兔子，是兔子， G(x)：x是烏龜，是烏龜， H(x,y)：x比比y跑得快。跑得快。本命題符號化為本命題符號化為 x(F(x) y(G(y)H(x,y)， 或或 x y(F(x)G(y)H(x,y)。 每個人都有自己喜歡的職業(yè)。每個人都有自己喜歡的職業(yè)。令令 R(x)：x是人，是人，P(x)：x是職業(yè)，是職業(yè)， L(x,y)：x喜歡喜歡y。本命題符號化為本命題符號化為 x(R(x) y(P(y)L(x,y)。不存在同樣高的兩個人。不存在同樣高的兩個人。令令R(x)：x是

14、人，是人，E(x,y)：xy。H(x,y)：x和和y同樣高。同樣高。本命題符號化為本命題符號化為 x y(R(x)R(y)E(x,y)H(x,y)。存在最小的自然數(shù)。存在最小的自然數(shù)。 令令N(x)：x是自然數(shù)。是自然數(shù)。L(x,y)：xy。E(x,y)：xy。 本命題符號化為本命題符號化為 x(N(x) y(N(y)L(x,y)E(x,y)。 一階語言的組成包括一階語言的組成包括:個體變元個體變元：有無限多個，用加或不加正整數(shù)：有無限多個，用加或不加正整數(shù)下標的小寫英文字母下標的小寫英文字母x,y,z,u,v,w等表示。等表示。個體常元個體常元：有無限多個，用加或不加正整數(shù)：有無限多個，用加

15、或不加正整數(shù)下標的小寫英文字母下標的小寫英文字母a,b,c,d等表示。等表示。運算符號運算符號：用加或不加正整數(shù)下標的小寫英：用加或不加正整數(shù)下標的小寫英文字母文字母f,g,h等表示，對于每個正整數(shù)等表示，對于每個正整數(shù)n，有無限，有無限多個多個n元運算符號。元運算符號。2.2 一階語言及其解釋一階語言及其解釋謂詞符號謂詞符號：用加或不加正整數(shù)下標的大寫英：用加或不加正整數(shù)下標的大寫英文字母表示，對于每個正整數(shù)文字母表示，對于每個正整數(shù)n，有無限多個，有無限多個n元謂詞符號。元謂詞符號。量詞符號量詞符號： ， 。聯(lián)結(jié)詞聯(lián)結(jié)詞：， ， ， 。逗號和圓括號逗號和圓括號。定義定義2.1 項項定義如下

16、：定義如下： 個體變元是項；個體變元是項； 個體常元是項；個體常元是項；若若f是是n元運算符號，元運算符號，t1,tn是項，則是項，則f(t1,tn)是項；是項； 只有有限次使用上面三條規(guī)則能夠得到的只有有限次使用上面三條規(guī)則能夠得到的符號串才是項。符號串才是項。 例如，例如，x，a，f(a,x)，g(f(h(b),h(x)，y，g(z,a,b) 都是項都是項 定義定義2.2 若若P是是n元謂詞符號，元謂詞符號， t1,tn是項，則稱是項，則稱P(t1,tn)為為原子公式原子公式。例如，例如，P(x,y) 和和R(f(x,y), a, g(g(b)都是原子公式都是原子公式定義定義2.3 一階公

17、式一階公式定義如下：定義如下： 原子公式是一階公式；原子公式是一階公式； 如果如果A是一階公式，則是一階公式，則(A)是一階公式；是一階公式； 如果如果A和和B是一階公式，則是一階公式，則(AB),(AB),(A B),(AB),(A B)是一階公式；是一階公式； 如果如果A是一階公式，是一階公式，x是變元，則是變元，則 xA和和 xA都是都是一階公式。一階公式。 只有有限次使用上面四條規(guī)則能夠得到的符號串只有有限次使用上面四條規(guī)則能夠得到的符號串才是一階公式。才是一階公式。 例如，例如， zP(z)Q(x,y)， y(P(y)Q(a,y) xP(x)都都是一階公式是一階公式 定義定義2.4

18、設(shè)設(shè) xA為公式，稱為公式，稱 x的該次出現(xiàn)的轄的該次出現(xiàn)的轄域為域為A。 設(shè)設(shè) xA為公式，稱為公式，稱 x的該次出現(xiàn)的轄的該次出現(xiàn)的轄域為域為A?？疾橄旅婀街忻總€量詞的轄域考查下面公式中每個量詞的轄域 y(P(x,y) yR(y) x(P(x,y) yQ(y) 定義定義2.5 設(shè)設(shè)x是任意變元。若是任意變元。若x在公式在公式A中的某次出現(xiàn)是中的某次出現(xiàn)是在在 x或或 x中的出現(xiàn)或是在它們的某次出現(xiàn)的轄域中的中的出現(xiàn)或是在它們的某次出現(xiàn)的轄域中的出現(xiàn)，則稱出現(xiàn)，則稱x在公式在公式A中的該次出現(xiàn)是中的該次出現(xiàn)是約束出現(xiàn)約束出現(xiàn)。若。若x在公式在公式A中的某次出現(xiàn)不是約束出現(xiàn)，則稱其為中的某次

19、出現(xiàn)不是約束出現(xiàn)，則稱其為自由自由出現(xiàn)出現(xiàn)。若。若x在公式在公式A中有約束出現(xiàn)，則稱它為中有約束出現(xiàn)，則稱它為A的的約束約束變元變元。若。若x在公式在公式A中有自由出現(xiàn)，則稱它為中有自由出現(xiàn)，則稱它為A的的自由自由變元變元。例例2.6 指出下列公式中量詞的每次出現(xiàn)的轄域，并指指出下列公式中量詞的每次出現(xiàn)的轄域，并指出變元的每次出現(xiàn)是約束出現(xiàn)，還是自由出現(xiàn)，以及出變元的每次出現(xiàn)是約束出現(xiàn)，還是自由出現(xiàn)，以及公式的約束變元和自由變元。公式的約束變元和自由變元。 x y(R(x,y)L(y,z) xH(x,y) x(P(x)Q(x) xP(x)Q(x) x(P(x) xQ(x)( xP(x)Q(x)

20、 定義定義2.6 沒有自由變元的公式稱為沒有自由變元的公式稱為封閉公式封閉公式，簡稱為簡稱為閉式閉式。例如，例如， x(F(x)G(x)， x yP(x,y)都是閉都是閉式，而式，而 xQ(x)H(x,y)，P(a,y)都不是閉式。都不是閉式。 解釋與賦值解釋與賦值定義定義2.7 一個解釋一個解釋I由以下四部分組成。由以下四部分組成。 一個非空集合一個非空集合DI，被稱為解釋，被稱為解釋I的個體域，稱其中的的個體域，稱其中的元素為個體。元素為個體。 為每個個體常元指定一個個體。為每個個體常元指定一個個體。 為每個為每個n元運算符號指定一個個體域上的元運算符號指定一個個體域上的n元運算。元運算。

21、 為每個為每個n元謂詞符號指定一個個體域上的元謂詞符號指定一個個體域上的n元謂詞。元謂詞。例如，例如， x(F(x)G(x)在給定解釋后才成為命題在給定解釋后才成為命題 定義定義2.8 設(shè)設(shè)I是一個解釋。是一個解釋。I中的一個賦值是一個從變中的一個賦值是一個從變元集到元集到I的個體域的個體域DI的函數(shù)。的函數(shù)。 例如：設(shè)例如：設(shè)f,g是二元運算符號，是二元運算符號，E是二元謂詞符號。是二元謂詞符號。 E(f(x,a),g(x,a)只有給定解釋只有給定解釋I和和I中賦值中賦值v后才構(gòu)成命后才構(gòu)成命題。題。給定解釋給定解釋I和和I中賦值中賦值v如下：如下：個體域個體域DI為自然數(shù)集，為自然數(shù)集，f

22、(x,y)xy， g(x,y)xy， a0，E(x,y): xy， v(x)0。E(f(x,a),g(x,a)在解釋在解釋I及賦值及賦值v下成為真命題：下成為真命題：0000例例2.8 設(shè)設(shè)f,g是二元運算符號，是二元運算符號，E,L是二元謂詞符號。是二元謂詞符號。給定解釋給定解釋I和和I中賦值中賦值v1和和v2如下：如下：個體域個體域DI為自然數(shù)集，為自然數(shù)集，f(x,y)xy， g(x,y)xy， a0，E(x,y): xy， L(x,y): xy，v1 (x)0， v2 (x)1。求下列公式在解釋求下列公式在解釋I下，賦值分別為下，賦值分別為v1和和v2時的真值。時的真值。 E(f(x,

23、a),g(x,a) y(E(x,y)L(x,y) xE(g(x,a),x) x yL(x,y)解解 在解釋在解釋I下，公式下，公式E(f(x,a),g(x,a)的意義是的意義是: x0 x0。 若取賦值為若取賦值為v1，它成為真命題：，它成為真命題：0000。若取賦值為若取賦值為v2，它成為假命題：，它成為假命題：1010。 在解釋在解釋I下，公式下，公式 y(E(x,y)L(x,y)的意義的意義是是:“對于每個自然數(shù)對于每個自然數(shù)y,xyxy”,即即x是最小是最小的自然數(shù)。的自然數(shù)。 若取賦值為若取賦值為v1，它成為真命題：，它成為真命題：0是最小的自然是最小的自然數(shù)。若取賦值為數(shù)。若取賦值

24、為v2，它成為假命題：，它成為假命題：1是最小的是最小的自然數(shù)。自然數(shù)。 xE(g(x,a),x)是閉式，沒有自由變元，不需是閉式，沒有自由變元，不需考慮賦值。在解釋考慮賦值。在解釋I下，它表示命題：下，它表示命題：對于每個自然數(shù)對于每個自然數(shù)x，x0 x。 顯然，這是一個假命題。顯然，這是一個假命題。 x yL(x,y)是閉式，沒有自由變元，不需考是閉式，沒有自由變元，不需考慮賦值。在解釋慮賦值。在解釋I下，它表示命題：下，它表示命題：對于每個自然數(shù)對于每個自然數(shù)x，存在自然數(shù)，存在自然數(shù)y，使得，使得xy。顯然，這是一個真命題。顯然，這是一個真命題。 設(shè)解釋設(shè)解釋I的個體域的個體域DIe1

25、,en，在解釋，在解釋I和和I中賦值中賦值v下，下， xA(x)A(e1)A(en) xA(x)A(e1)A(en) 例例2.9 設(shè)設(shè)f是一元運算符號，是一元運算符號，P是一元謂詞符是一元謂詞符號，號，Q是二元謂詞符號。給定解釋是二元謂詞符號。給定解釋I如下：如下：DI2,3，f(2)3，f(3)2，P(2)1，P(3)0Q(2,2)Q(3,3)1，Q(2,3)Q(3,2)0 求下列閉式在解釋求下列閉式在解釋I下的真值。下的真值。 x(Q(f(x),x)P(x) xQ(x,x) x yQ(x,y) 解解 x(Q(f(x),x)P(x) (Q(f(2),2)P(2)(Q(f(3),3)P(3)

26、(Q(3,2)P(2)(Q(2,3)P(3) (01)(00)1 xQ(x,x)Q(2,2)Q(3,3)111 x yQ(x,y) yQ(2,y) yQ(3,y) (Q(2,2)Q(2,3)(Q(3,2)Q(3,3)(10)(01)1 定義定義2.9 設(shè)設(shè)A是公式，是公式，I是解釋。如果是解釋。如果A在在I和和I中任意中任意賦值下均為真，則稱賦值下均為真，則稱A在在I下為真。如果下為真。如果A在在I和和I中任中任意賦值下均為假，則稱意賦值下均為假，則稱A在在I下為假。下為假。 例例2.10 設(shè)設(shè)f,g,h是二元運算符號，是二元運算符號，E,L是二元謂詞符號。是二元謂詞符號。給定解釋給定解釋I如

27、下：如下：個體域個體域DI為有理數(shù)集，為有理數(shù)集，f(x,y)xy, g(x,y)xy, h(x,y)x2y2, a0, b1,E(x,y): xy, L(x,y): xy。以下公式中哪些在以下公式中哪些在I下為真，哪些在下為真，哪些在I下為假？下為假？ E(f(x,y),g(x,y) E(f(x,x),h(x,a) E(x,a)E(g(y,x),y) 解解 在解釋在解釋I下，公式下，公式E(f(x,y),g(x,y)的意義是：的意義是：xyxy。當。當xy2時，它是真命題；當時，它是真命題；當x1,y0時，時，它是假命題。因此，公式它是假命題。因此，公式E(f(x,y),g(x,y)在解釋在

28、解釋I下既下既不真也不假。不真也不假。 在解釋在解釋I下，公式下，公式E(f(x,x),h(x,a)的意義是：的意義是：xxx202。不管。不管x取什么有理數(shù)為值，它都是真命題。因取什么有理數(shù)為值，它都是真命題。因此，公式此，公式E(f(x,x),h(x,a)在解釋在解釋I下為真。下為真。 在解釋在解釋I下，公式下，公式E(x,a)E(g(y,x),y)的意義是：的意義是：x0yxy。不管。不管x,y取什么有理數(shù)為值，它都是取什么有理數(shù)為值，它都是假命題。因此，公式假命題。因此，公式E(x,a)E(g(y,x),y)在解釋在解釋I下為下為假。假。 定義定義2.10 如果公式如果公式A在任何解釋

29、下均為真，則稱在任何解釋下均為真，則稱A為為永真式永真式，或，或邏輯有效公式邏輯有效公式。 如果公式如果公式A在任何解釋下均為假，則稱在任何解釋下均為假，則稱A為為永假式永假式，或，或矛盾式矛盾式。 如果公式如果公式A在某個解釋在某個解釋I和和I的某個賦值的某個賦值v下下為真，則稱為真，則稱A為為可滿足式可滿足式。 例例2.12 判斷以下公式的類型。判斷以下公式的類型。 xP(x) xP(x) xP(x) xP(x)解解 要使公式要使公式 xP(x) xP(x)在解釋在解釋I下為假，下為假，就要使就要使 xP(x)為真而為真而 xP(x)為假，為假， xP(x)為真為真要求個體域中每個元素都有

30、性質(zhì)要求個體域中每個元素都有性質(zhì)P， xP(x)為假為假要求個體域中每個元素都沒有性質(zhì)要求個體域中每個元素都沒有性質(zhì)P，這兩個，這兩個要求是互相矛盾的，不可能同時滿足。所以，要求是互相矛盾的，不可能同時滿足。所以，公式公式 xP(x) xP(x)是永真式。是永真式。 要使公式要使公式 xP(x) xP(x)在解釋在解釋I下為真，下為真，就要使就要使 xP(x)和和 xP(x)同時為真，而同時為真，而 xP(x)斷定個體域中每個元素都沒有性質(zhì)斷定個體域中每個元素都沒有性質(zhì)P， xP(x)斷斷定個體域中有的元素有性質(zhì)定個體域中有的元素有性質(zhì)P，這兩個要求是，這兩個要求是互相矛盾的，不可能同時滿足。

31、所以，公式互相矛盾的，不可能同時滿足。所以，公式 xP(x) xP(x)是永假式。是永假式。 定義定義2.11 設(shè)設(shè)A是包含命題變元是包含命題變元p1,pn的命題公式，的命題公式，B1,Bn是一階公式，用是一階公式，用B1,Bn分別代替分別代替p1,pn在在A中的所有出現(xiàn)得到的一階公式中的所有出現(xiàn)得到的一階公式B被稱為被稱為A的的代換實例代換實例。 命題邏輯永真式的代換實例稱為重言式命題邏輯永真式的代換實例稱為重言式。 命題邏輯永真式的代換實例是一階邏輯的永真式命題邏輯永真式的代換實例是一階邏輯的永真式，即重言式都是永真式即重言式都是永真式。 永真式未必是重言式永真式未必是重言式。例如，。例如

32、， xP(x) xP(x)是永是永真式，但并不是重言式，因為它只能是真式，但并不是重言式，因為它只能是pq命題公式命題公式的代換實例。的代換實例。 命題邏輯永假式的代換實例是一階邏輯的永假式。命題邏輯永假式的代換實例是一階邏輯的永假式。 例例2.13 判斷以下公式是否是重言式、永真式、永假式。判斷以下公式是否是重言式、永真式、永假式。 (P(x)(Q(x)P(x) xP(x) yP(y) xP(x) xQ(x) xP(x)解解 (P(x)(Q(x)P(x)是永假式，因為它是命題是永假式，因為它是命題邏輯永假式邏輯永假式(p(qp)的代換實例。的代換實例。 xP(x) yP(y)顯然是永真式，因

33、為不管給什么解釋顯然是永真式，因為不管給什么解釋I， xP(x)和和 yP(y)的意義總是一樣的。但是，它不是的意義總是一樣的。但是，它不是重言式，因為如果將重言式，因為如果將 xP(x)和和 yP(y)分別看做命題變元分別看做命題變元p和和q得到的命題公式得到的命題公式pq并不是命題邏輯永真式。并不是命題邏輯永真式。 xP(x) xQ(x) xP(x)是重言式，因為它是命題是重言式，因為它是命題邏輯永真式邏輯永真式pqp的代換實例。的代換實例。 定義定義2.12 設(shè)設(shè)A(t)是用項是用項t代入公式代入公式A(x)中所有自由出現(xiàn)中所有自由出現(xiàn)的的x得到的公式。若得到的公式。若A(t)與與A(x

34、)中變元的約束出現(xiàn)數(shù)相中變元的約束出現(xiàn)數(shù)相同，則稱同，則稱t對于對于A(x)中的中的x是是可代入可代入的；否則稱的；否則稱t對于對于A(x)中的中的x是是不可代入不可代入的。的。 例例2.14 在以下給出的在以下給出的t和和A(x)中，中，t對于對于A(x)中的中的x是否是否是可代入的？是可代入的？ t：f(x,y), A(x)： xP(x,y)P(x,y)。 t：y， A(x)： yP(x,y)。解解 A(t)是是 xP(x,y)P(f(x,y),y)。A(t)和和A(x)中的變中的變元 的 約 束 出 現(xiàn) 數(shù) 均 為元 的 約 束 出 現(xiàn) 數(shù) 均 為 2 。 所 以 ，。 所 以 ， f

35、( x , y ) 對 于對 于 xP(x,y)P(x,y)中的中的x是可代入的。是可代入的。 A(t)是是 yP(y,y)，其中的變元的約束出現(xiàn)數(shù)為，其中的變元的約束出現(xiàn)數(shù)為3，而，而A(x)中的變元的約束出現(xiàn)數(shù)為中的變元的約束出現(xiàn)數(shù)為2。因此，。因此，y對于對于 yP(x,y)中的中的x是不可代入的。是不可代入的。 定義定義2.13 設(shè)設(shè)A和和B是公式。若是公式。若AB是永真式，則稱是永真式，則稱A與與B等值，或稱等值，或稱A與與B邏輯等價，記為邏輯等價，記為A B。例例2.15 判斷公式判斷公式P(x)和和P(y)是否等值。是否等值。 解：解： 取解釋取解釋I如下：如下：個體域個體域DI

36、為正整數(shù)集，為正整數(shù)集，P(x)：x是奇數(shù)，是奇數(shù)，v(x)1,v(y)2。在解釋。在解釋I和賦值和賦值v下，下， P(x)= P(1)表示表示 “1是奇數(shù)是奇數(shù)”，P(y)= P(2)表示表示 “2是奇是奇數(shù)數(shù)”。 P(x) P(y)= P(1) P(2)=10=0因此，因此，P(x)和和P(y)不等值。不等值。 2.3 等等 值值 演演 算算例例2.16 判斷公式判斷公式 x yP(x,y)和和 y xP(x,y)是是否等值。否等值。解解 給定解釋給定解釋I如下：如下： 取個體域取個體域DI為整數(shù)集，為整數(shù)集，P(x,y)：x y。在解釋在解釋I下，公式下，公式 x yP(x,y)表示表示

37、 “對于每個對于每個整數(shù)整數(shù)x，都存在大于等于，都存在大于等于x的整數(shù)的整數(shù)y”，這是真，這是真命題。命題。而公式而公式 y xP(x,y)表示表示 “存在最大的整數(shù)存在最大的整數(shù)”，這是假命題。這是假命題。因此，因此， x yP(x,y)和和 y xP(x,y)不等值。不等值。常用等值式常用等值式 xA(x) xA(x)； xA(x) xA(x) xA(x) yA(y)， xA(x) yA(y) 其中其中y是在是在A(x)中不出現(xiàn)的變元。中不出現(xiàn)的變元。 在本組等值式中，在本組等值式中，x不是公式不是公式B中的自由變元。中的自由變元。 xA(x)Bx(A(x)B)； xA(x)Bx(A(x)

38、B)； xA(x)Bx(A(x)B)； B xA(x) x(BA(x)； xA(x)Bx(A(x)B)； xA(x)Bx(A(x)B)； xA(x)Bx(A(x)B)； B xA(x) x(BA(x)。 xA(x) xB(x) x(A(x)B(x)； xA(x) xB (x) x (A(x)B(x)。例例2.17 通過等值演算證明下列等值式。通過等值演算證明下列等值式。 x(P(x)Q(x) xP(x) xQ(x) xP(x) xP(x) xP(x) xP(x) x y(P(x)Q(y) y x(P(x)Q(y) 解解 x(P(x)Q(x) x(P(x)Q(x) xP(x) xQ(x) xP(

39、x) xQ(x) xP(x) xQ(x) xP(x) xP(x) xP(x) xP(x) xP(x) xP(x) x y(P(x)Q(y)x(P(x) yQ(y) xP(x) yQ(y) y x(P(x)Q(y) y( xP(x)Q(y) xP(x) yQ(y)所以，所以， x y(P(x)Q(y) y x(P(x)Q(y)。 練習(xí)練習(xí)用等值演算證明下面的等值式。用等值演算證明下面的等值式。 x(F(x)G(x) yF(y) zG(z) x(F(x)G(x) x (F(x) G(x) xF(x) x G(x) xF(x) x G(x) xF(x) xG(x) yF(y) zG(z)2.4 前前

40、 束束 范范 式式定義定義2.14 設(shè)設(shè)n是自然數(shù)。若是自然數(shù)。若x1,xn是不同變元，是不同變元，Q1,Qn是是 或或 ，A是不含量詞的公式，則稱是不含量詞的公式，則稱公式公式Q1x1QnxnA為前束范式，并稱為前束范式，并稱Q1x1Qnxn為該前束范式的前束，稱為該前束范式的前束，稱A為該前束范式的母為該前束范式的母式。式。 如如 P(x,y), F(x)G(x) , y uP(y,u), x(F(x) G(x) 都是前束范式都是前束范式 。 x y zP(x,y)Q(u,v)不是前束范式不是前束范式 。定義定義2.15 如果前束范式如果前束范式B與公式與公式A等值，則稱等值，則稱B為為A

41、的前束范式。的前束范式。求一個公式的前束范式步驟如下：求一個公式的前束范式步驟如下：化掉公式中的聯(lián)結(jié)詞化掉公式中的聯(lián)結(jié)詞， 。將公式的約束變元換名，以使得約束變元與將公式的約束變元換名，以使得約束變元與自由變元不重名，并且量詞的各次出現(xiàn)約束不自由變元不重名，并且量詞的各次出現(xiàn)約束不同的變元。同的變元。將量詞移至最外面。將量詞移至最外面。例例2.18 求公式求公式 xP(x,y) yQ(x,y) 的前束范式。的前束范式。解解 xP(x,y) yQ(x,y)( xP(x,y) yQ(x,y)( yQ(x,y) xP(x,y) ( zP(z,y) uQ(x,u)( vQ(x,v) wP(w,y) (

42、 zP(z,y) uQ(x,u)( vQ(x,v) wP(w,y)u( zP(z,y)Q(x,u) v(Q(x,v) wP(w,y)u z(P(z,y)Q(x,u) v w(Q(x,v)P(w,y) u z v w(P(z,y)Q(x,u)(Q(x,v)P(w,y) 練習(xí)：求下面公式的前束范式。練習(xí)：求下面公式的前束范式。 xF(x) xG(x) 解：解： xF(x) xG(x) xF(x) yG(y) x（F(x) yG(y)） x y（F(x) G(y)）2.5 推 理 理 論 定義定義2.16 設(shè)設(shè)A1,An,B是公式，如果是公式，如果A1AnB是永真式，則稱從前提是永真式，則稱從前提A

43、1,An推出結(jié)論推出結(jié)論B推理正確，并稱推理正確，并稱B是是A1,An的邏輯推論，記為的邏輯推論，記為A1An B。AB當且僅當當且僅當AB且且B A。因此，每個。因此，每個等值式就相當于兩個推理定律。等值式就相當于兩個推理定律。 例例2.21 證明：證明： xF(x) xG(x) x(F(x)G(x)。解解 下面給出本題的兩種證明方法。下面給出本題的兩種證明方法。證法一：任取使公式證法一：任取使公式 xF(x) xG(x)為真的解釋為真的解釋I，則則 xF(x)1或或 xG(x)1。對于個體域。對于個體域DI中的每個元中的每個元素素e，F(xiàn)(e)1；或者對于個體域；或者對于個體域DI中的每個元

44、素中的每個元素e，G(e)1。故對于個體域。故對于個體域DI中的每個元素中的每個元素e，F(xiàn)(e)G(e)1。所以。所以 x(F(x)G(x)為真。為真。因此因此 xF(x) xG(x) x(F(x)G(x)。 證法二：任取使公式證法二：任取使公式 x(F(x)G(x)為假的解釋為假的解釋I，則，則存在個體域存在個體域DI中的元素中的元素e，使得，使得F(e)G(e)0，即，即F(e)G(e)0。所以。所以 xF(x) xG(x)0，故，故 xF(x) xG(x)為假。為假。因此因此 xF(x) xG(x) x(F(x)G(x)。 例例2.22 判斷判斷 x(F(x)G(x) xF(x) xG(

45、x)是否成立，并說明理由是否成立，并說明理由 分析：若存在一分析：若存在一解釋，使得在此解釋下，解釋，使得在此解釋下， x(F(x)G(x) 為真而為真而 xF(x) xG(x)為假，為假，則則 x(F(x)G(x) xF(x) xG(x)不成立不成立 令令解釋解釋I如下：個體域為正整數(shù)集，如下：個體域為正整數(shù)集，F(xiàn)(x)：x是是奇數(shù)，奇數(shù)，G(x)：x是偶數(shù)。是偶數(shù)。則則 x(F(x)G(x) 為真而為真而 xF(x) xG(x)為假，為假，因此，因此， x(F(x)G(x) xF(x) xG(x)不成立。不成立。1） 全稱量詞消去規(guī)則（全稱量詞消去規(guī)則（UI） x A(x) A(t)其中其

46、中t是對于公式是對于公式A(x)中的中的x可代入的項。可代入的項。2）全稱量詞引入規(guī)則（）全稱量詞引入規(guī)則（UG） A(x) x A(x)其中其中x不是前提中的自由變元。不是前提中的自由變元。反例見例反例見例2.23反例見例反例見例2.24關(guān)于量詞的規(guī)則關(guān)于量詞的規(guī)則 A(t) x A(x)其中其中t是對于公式是對于公式A(x)中的中的x可代入的項。可代入的項。 4）存在量詞消去規(guī)則（）存在量詞消去規(guī)則（EI） x A(x) x B(x) A(c) B(f(y1,yn)其中其中 x A(x)是閉式，是閉式，c是新常元，是新常元， y1,yn是公式是公式 x B(x)中的所有中的所有自由變元自由

47、變元，f是新是新n元函數(shù)符號。元函數(shù)符號。 3）存在量詞引入規(guī)則（）存在量詞引入規(guī)則（EG）反例見例反例見例2.25 設(shè)前提是設(shè)前提是 x yP(x,y)，結(jié)論是，結(jié)論是 yP(y,y)。以下證明有什么錯誤？以下證明有什么錯誤？(1) x yP(x,y) 前提引入前提引入(2) yP(y,y) (1)UI解解 取個體域為正整數(shù)集，取個體域為正整數(shù)集，P(x,y): xy，則，則 x yP(x,y)為真，而為真，而 yP(y,y)為假。為假。因此因此 x yP(x,y) yP(y,y)不成立。不成立。 這個證明的第二步對全稱量詞消去規(guī)則的使這個證明的第二步對全稱量詞消去規(guī)則的使用是錯誤的，因為用

48、是錯誤的，因為y對于公式對于公式y(tǒng)P(x,y)中的中的x不是不是可代入的?？纱氲?。例例2.23 設(shè)前提是設(shè)前提是F(x)，結(jié)論是，結(jié)論是 xF(x)。以下。以下證明有什么錯誤？證明有什么錯誤？(1) F(x) 前提引入前提引入(2) xF(x) (1)UG解解 取個體域為正整數(shù)集，取個體域為正整數(shù)集，F(xiàn)(x)：x是奇數(shù)，是奇數(shù)，賦值賦值v使使v(x)1，則，則F(x)為真，而為真，而 xF(x)為為假。假。 所以所以F(x) xF(x)不成立。不成立。 這個證明的第二步對全稱量詞引入規(guī)則的這個證明的第二步對全稱量詞引入規(guī)則的使用是錯誤的，因為使用是錯誤的，因為x是前提是前提F(x)中的自由變

49、中的自由變元。元。 例例2.24 設(shè)前提是：設(shè)前提是：G(a), xF(x)；結(jié)論是結(jié)論是 x(F(x)G(x)。以下證明有什么錯誤？。以下證明有什么錯誤？(1) xF(x) 前提引入前提引入(2) F(a) (1)EI(3) G(a) 前提引入前提引入(4) F(a)G(a) (2)(3)合取引入合取引入(5) x(F(x)G(x)(4)EG解解 取個體域為正整數(shù)集，取個體域為正整數(shù)集， F(x)：x是奇數(shù)，是奇數(shù)，G(x)：x是偶數(shù)，是偶數(shù)，a2， 則則G(a)和和 xF(x)均為真，均為真， 而而 x(F(x)G(x)為假，為假， 所以所以 G(a) xF(x) x(F(x)G(x)不成立。不成立。這個證明的第二步對存在量詞消去規(guī)則的使用是錯誤這個證明的第二步對存在量詞消去規(guī)則的使用是錯誤的，因為的，因為a不是新常元，它在前提不是新常元，它在前提G(a)中出現(xiàn)。中出現(xiàn)。例例2.25例例2.27 設(shè)前提是：設(shè)前提