謂詞公式與翻譯

1、2022-2-1612.3 謂詞公式與翻譯1謂詞公式（合式公式）謂詞公式（合式公式）在給出一階謂詞邏輯中謂詞公式的定義之前，我們首先對所使在給出一階謂詞邏輯中謂詞公式的定義之前，我們首先對所使用的符號作如下約定。用的符號作如下約定。1）個體常量符號：）個體常量符號：a，b，c，ai，bi，ci，（，（i1）；）；2）個體變量符號：）個體變量符號：x，y，z，xi，yi，zi，（，（i1）；）；3）函數符號：）函數符號：f，g，h，fi，gi，hi，（，（i1）；）；4) 謂詞符號：謂詞符號：P，Q，R，Pi，Qi，Ri，（，（i1）；）；5）量詞符號：）量詞符號： x， x，x為任意的個體變量

2、符號；為任意的個體變量符號；6）聯(lián)結詞符號：）聯(lián)結詞符號：，；2022-2-1622.3 謂詞公式與翻譯1謂詞公式（合式公式）謂詞公式（合式公式）定義定義 項項可遞歸地定義如下可遞歸地定義如下1）個體常量是項；）個體常量是項；2）個體變量是項；）個體變量是項；3）若）若f（x1，x2，x3，xn）是任意的）是任意的n元函數，元函數，t1，t2，t3，tn是項，則是項，則f（t1，t2，t3，tn）是項；）是項；4）只有有限次地使用）只有有限次地使用1），），2），），3）所生成的符號串才是項。）所生成的符號串才是項。例如，例如，a，x，f（a），），g（x），），h（a，x），），h（f（a）

3、，），g（x），），f（h（a，x）等都是項。）等都是項。2022-2-1632.3 謂詞公式與翻譯定義定義 若若P（x1，x2，xn）是任意的）是任意的n元謂詞，元謂詞，t1，t2，tn是項，則稱是項，則稱P（t1，t2，t3，tn）為為原子公式。原子公式。例如：原子謂詞公式包括下述形式的各種特例：例如：原子謂詞公式包括下述形式的各種特例：Q,A(x)，A(x,y)，A(f(x)，y)，A(x,y,z)，A(a,y)等等2022-2-1642.3 謂詞公式與翻譯定義定義 一階謂詞邏輯中的一階謂詞邏輯中的謂詞公式（合式公式）謂詞公式（合式公式）的遞的遞歸定義為歸定義為1）原子公式是合式公式；）

4、原子公式是合式公式；2）若）若A是合式公式，則（是合式公式，則（A）是合式公式；）是合式公式；3）若）若A，B是合式公式，則（是合式公式，則（AB），（），（AB），），（AB），（），（A B）是合式公式；）是合式公式；4）若）若A是合式公式，則是合式公式，則 xA， xA是合式公式；是合式公式；只有有限次地使用只有有限次地使用1），），2），），3），），4）所生成的符）所生成的符號串才是合式公式。號串才是合式公式。通常，（通常，（A）的括號可以省略，寫成）的括號可以省略，寫成A，整個公式，整個公式最外層的括號可以省略。最外層的括號可以省略。但是量詞后邊如果有括號則不能省略。但是量詞后邊如

5、果有括號則不能省略。合式公式或謂詞公式可簡稱為公式。合式公式或謂詞公式可簡稱為公式。2022-2-1652.3 謂詞公式與翻譯【例【例1】將下列命題形式化為謂詞邏輯中的命題】將下列命題形式化為謂詞邏輯中的命題: 沒有不犯錯誤的人。沒有不犯錯誤的人。 人總是要犯錯誤的。人總是要犯錯誤的。 解：設解：設F(x)：x犯錯誤，犯錯誤，M(x)：x是人。則上句符是人。則上句符號化為：號化為： (a) ( x)(M(x) F(x) (b) x(M(x)F(x) 【例【例2】盡管有人聰明但未必一切人都聰明?！勘M管有人聰明但未必一切人都聰明。 解：設解：設P(x)：x聰明，聰明，M(x)：x是人。則上句符號是

6、人。則上句符號化為：化為： x(M(x) P(x) ( x(M(x)P(x) 翻譯翻譯：是將自然語言敘述的命題翻譯成謂詞：是將自然語言敘述的命題翻譯成謂詞公式的形式。公式的形式。2022-2-166l 由例可知，對于命題翻譯成謂詞公式時，機動性很大，由于對個體描述性質的刻劃深度不同，就可翻譯成不同形式的謂詞公式。l l例如：這只大紅書柜擺滿了那些古書2.3 謂詞公式與翻譯l 解法1：l設：F(x,y): x擺滿了yl R(x): x是大紅書柜l Q(y): y是古書l a:這只 b:那些l結果：結果：R(a) Q(b) F(a,b)l 解法2：l設：F(x,y): x擺滿了yl A(x): x

7、是書柜l B(x): x是大的l C(x): x是紅的l D(y): y是古老的l E(y): y是圖書l a:這只 b:那些l結果：結果：A(a) B(a) C(a) D(b) E(b) F(a,b)2022-2-1672.3 謂詞公式與翻譯2謂詞公式的解釋謂詞公式的解釋 對于命題公式，只要給出其所含命題變元的一組真對于命題公式，只要給出其所含命題變元的一組真值指派，即一種解釋就可得到該公式的真值。值指派，即一種解釋就可得到該公式的真值。 而謂詞公式的真值，一般情況下，是由而謂詞公式的真值，一般情況下，是由論域論域，個體個體常項常項，量詞量詞，個體變項個體變項，函數函數以及以及謂詞謂詞等確定

8、。對謂詞等確定。對謂詞公式中的各種變項予以特殊的指定，就得到該公式的一公式中的各種變項予以特殊的指定，就得到該公式的一個解釋。下面給出謂詞公式解釋的一般定義。個解釋。下面給出謂詞公式解釋的一般定義。2022-2-1682.3 謂詞公式與翻譯2謂詞公式的解釋謂詞公式的解釋定義定義 謂詞公式的一個解釋謂詞公式的一個解釋I，由下面，由下面4部分組成部分組成1）非空的論域）非空的論域U；2）U中的特定的個體常項；中的特定的個體常項；3）U上特定的函數；上特定的函數；4）U上特定的謂詞。上特定的謂詞。 若將謂詞公式中的個體常項，函數和謂詞分別指定若將謂詞公式中的個體常項，函數和謂詞分別指定為為U中的特定

9、個體常項，中的特定個體常項，U上特定的函數和上特定的函數和U上特定的謂上特定的謂詞，即為該公式在解釋詞，即為該公式在解釋I下的真值。下的真值。2022-2-169【例【例2.2.1】給定解釋】給定解釋I如下如下（1）U =a，b；（2）a = 2；（3）函數）函數f（x）為）為f（a）= b，f（b）= a；（4）謂詞）謂詞 P（x）為）為P（a）= 0，P（b）= 1；Q（x，y）為）為Q（a，a）= 0，Q（a，b）= Q（b，a）= Q（b，b）= 1；L（x，y）為）為L（a，b）=L（b，a）= 0，L（a，a）= L（b，b）= 1。求下列公式在解釋求下列公式在解釋I下的真值下的真

10、值1）P（a） x P(x)；在解釋在解釋I下下P（a） x P(x)= P（a）（P（a）P（b）= 0（01）= 00= 02022-2-1610【例【例2.2.1】給定解釋】給定解釋I如下如下（1）U =a，b；（2）a = 2；（3）函數）函數f（x）為）為f（a）= b，f（b）= a；（4）謂詞）謂詞 P（x）為）為P（a）= 0，P（b）= 1；Q（x，y）為）為Q（a，a）= 0，Q（a，b）= Q（b，a）= Q（b，b）= 1；L（x，y）為）為L（a，b）=L（b，a）= 0，L（a，a）= L（b，b）= 1。求下列公式在解釋求下列公式在解釋I下的真值下的真值2） x（

11、 P（f（x）Q（x，f（x）；）；在解釋在解釋I下下 x（ P（f（x）Q（x，f（x）=（ P（f（a）Q（a，f（a）（ P（f（b）Q（b，f（b）=（ P（b）Q（a，b）（ P（a）Q（b，a）=（ 11）（ 01）= 10= 12022-2-1611【例【例2.2.1】給定解釋】給定解釋I如下如下（1）U =a，b；（2）a = 2；（3）函數）函數f（x）為）為f（a）= b，f（b）= a；（4）謂詞）謂詞 P（x）為）為P（a）= 0，P（b）= 1；Q（x，y）為）為Q（a，a）= 0，Q（a，b）= Q（b，a）= Q（b，b）= 1；L（x，y）為）為L（a，b）=L

12、（b，a）= 0，L（a，a）= L（b，b）= 1。求下列公式在解釋求下列公式在解釋I下的真值下的真值3） x y L（x，y）。）。在解釋在解釋I下下 x y L（x，y）=（ L（a，a）L（a，b）（L（b，a）L（b，b）=（10）（01）=11=12022-2-16122.4 變元的約束1 作用域或轄域作用域或轄域 設設為一個謂詞公式，其中有一部份公式形式為為一個謂詞公式，其中有一部份公式形式為 xP(x)或彐或彐xP(x)。這里、彐后面所跟的。這里、彐后面所跟的x叫做叫做量詞的指量詞的指導變元導變元或或作用變元作用變元，P(x)叫做相應量詞的叫做相應量詞的作用域或轄域。作用域或轄

13、域。2 約束變元和自由變元約束變元和自由變元 約束變元約束變元在謂詞公式在謂詞公式中，中， x或彐或彐x作用域中出現(xiàn)作用域中出現(xiàn)的的x稱為稱為中的中的約束變元約束變元，x亦稱為被相應量詞中的亦稱為被相應量詞中的指導指導變元所約束變元所約束。 自由變元自由變元在在中除去約束變元以外所出現(xiàn)的變元稱作中除去約束變元以外所出現(xiàn)的變元稱作自由變元自由變元。自由變元是不受約束的變元，雖然它有時也。自由變元是不受約束的變元，雖然它有時也在量詞的作用域中出現(xiàn)，但它不受相應量詞中指導變元在量詞的作用域中出現(xiàn)，但它不受相應量詞中指導變元的約束，故我們可把自由變元看作是公式中的參數。的約束，故我們可把自由變元看作是

14、公式中的參數。 2022-2-16132.4 變元的約束 例題例題1 說明以下各式的作用域與變元約束的情況。說明以下各式的作用域與變元約束的情況。 a) x(P(x)Q(x) b) x(P(x)彐彐yR(x,y) c) x y(P(x,y)Q(y,z)彐彐xP(x,y) d) x(P(x)彐彐xQ(x,z)彐彐yR(x,y)Q(x,y)解解 a) x的作用域是的作用域是P(x)Q(x)，x為約束變元。為約束變元。 b) x的作用域是的作用域是(P(x)彐彐yR(x,y), 彐彐y的作用域是的作用域是R(x,y)，x,y都是約束變元都是約束變元. c) x和和 y的作用域是的作用域是(P(x,y

15、)Q(y,z)，其中，其中x,y是約束是約束變元，變元，z是自由變元。彐是自由變元。彐x的作用域是的作用域是P(x,y)，其中，其中x是約束是約束變元，變元，y是自由變元。在整個公式中是自由變元。在整個公式中,x是約束出現(xiàn)，是約束出現(xiàn)，y既是既是約束出現(xiàn)又是自由出現(xiàn)，約束出現(xiàn)又是自由出現(xiàn)，z是自由出現(xiàn)。是自由出現(xiàn)。 d) x的作用域是的作用域是(P(x)彐彐xQ(x,z)(彐彐y)R(x,y)，x和和y都是約束變元，但都是約束變元，但Q(x,z)中的中的x是受彐是受彐x的約束，而不是受的約束，而不是受 x的約束。的約束。Q(x,y)中的中的x,y是自由變元。是自由變元。2022-2-16142

16、.4 變元的約束3 約束變元的換名約束變元的換名 為了避免由于變元的約束與自由同時出現(xiàn)，引起概念為了避免由于變元的約束與自由同時出現(xiàn)，引起概念上的混亂，故可對約束變元進行換名。使得一個變元在一上的混亂，故可對約束變元進行換名。使得一個變元在一個公式中只呈一種形式出現(xiàn)，即呈自由出現(xiàn)或呈約束出現(xiàn)個公式中只呈一種形式出現(xiàn)，即呈自由出現(xiàn)或呈約束出現(xiàn)約束變元的換約束變元的換名規(guī)則名規(guī)則 (1) 對于約束變元可以換名，其更改的變元名稱范圍是量詞對于約束變元可以換名，其更改的變元名稱范圍是量詞中的指導變元，以及該量詞作用域中所出現(xiàn)的該變元，在中的指導變元，以及該量詞作用域中所出現(xiàn)的該變元，在公式的其余部份不

17、變。公式的其余部份不變。 (2) 換名時一定要更改為作用域中沒有出現(xiàn)的變元名稱。換名時一定要更改為作用域中沒有出現(xiàn)的變元名稱。 例題例題 2 對對 x(P(x)R(x,y)Q(x,y)換名。換名。 解解 可換名為：可換名為： z(P(z)R(z,y)Q(x,y)， 但不能改名為：但不能改名為： y(P(y)R(y,y)Q(x,y) 以及以及 z(P(z)R(x,y)Q(x,y)。 因為后兩種更改都將使公式中量詞的約束范圍有所變動。因為后兩種更改都將使公式中量詞的約束范圍有所變動。2022-2-16152.4 變元的約束 4 自由變元的代入自由變元的代入 對于公式中的自由變元，也允許更改，這種更

18、改叫做代對于公式中的自由變元，也允許更改，這種更改叫做代入。自由變元的代入，亦需遵守一定的規(guī)則，這個規(guī)則叫入。自由變元的代入，亦需遵守一定的規(guī)則，這個規(guī)則叫做自由變元的代入規(guī)則，現(xiàn)說明如下：做自由變元的代入規(guī)則，現(xiàn)說明如下： (1) 對于謂詞公式中的自由變元，可以作代入，代入時對于謂詞公式中的自由變元，可以作代入，代入時需對公式中出現(xiàn)該需對公式中出現(xiàn)該自由變元的每一處自由變元的每一處進行。進行。 (2) 用以代入的變元與原公式中所有變元的名稱不能相用以代入的變元與原公式中所有變元的名稱不能相同。同。 例題 3 對彐x(P(y)R(x,y)代入。 解 對y施行代入，經代入后公式為 彐x(P(z)

19、R(x,z) 但是彐x(P(x)R(x,x)與彐x(P(z)R(x,y)這兩種代入都是與規(guī)則不符的。2022-2-16162.5謂詞公式的等價與蘊涵1、謂詞邏輯中常見的等價與蘊含關系、謂詞邏輯中常見的等價與蘊含關系 l謂詞公式的賦值謂詞公式的賦值:l在謂詞公式中常包含命題變元和客體變元，當客體在謂詞公式中常包含命題變元和客體變元，當客體變元由確定的客體所取代，命題變元用確定的命題變元由確定的客體所取代，命題變元用確定的命題所取代時，就稱作對謂詞公式的賦值。一個謂詞公所取代時，就稱作對謂詞公式的賦值。一個謂詞公式經過賦值以后，就成為具有確定真值式經過賦值以后，就成為具有確定真值T或或F的命的命題

20、。題。2022-2-16172.5謂詞公式的等價與蘊涵(1)命題邏輯中等價和蘊含的推廣命題邏輯中等價和蘊含的推廣 l定義定義1: 給定任何兩個謂詞公式給定任何兩個謂詞公式 A 和和 B，設它們有共同的，設它們有共同的個體域個體域E，若對，若對A和和B的任一組變元進行賦值，所得命題的任一組變元進行賦值，所得命題的真值相同，則稱謂詞公式的真值相同，則稱謂詞公式 A 和和 B 在在E上是等價的，并上是等價的，并記作：記作： ABl例如：例如：( x)(P(x)Q(x) ( x)(P(x) Q(x) l xP(x) x Q(x) ( x)P(x) x Q(x)l定義定義2: l設設A為謂詞公式，若在任

21、何解釋下，為謂詞公式，若在任何解釋下，A的真值都為真，則的真值都為真，則稱稱A為為永真式永真式；l若至少存在一種解釋，使若至少存在一種解釋，使A的真值為真，則稱的真值為真，則稱A為為可滿足可滿足式式；l若在任何解釋下，若在任何解釋下，A的真值都為假，則稱的真值都為假，則稱A為為矛盾式矛盾式，矛，矛盾式也稱不可滿足式。盾式也稱不可滿足式。l顯然，永真式是可滿足式。顯然，永真式是可滿足式。2022-2-1618(1)命題邏輯中等價和蘊含的推廣l在命題演算中，任一永真公式，其中同一命題變元，在命題演算中，任一永真公式，其中同一命題變元，用同一公式取代時，其結果也是永真公式。我們可以用同一公式取代時，

22、其結果也是永真公式。我們可以把這個情況推廣到謂詞公式之中，當謂詞演算中的公把這個情況推廣到謂詞公式之中，當謂詞演算中的公式代替命題演算中永真公式的變元時，所得的謂詞公式代替命題演算中永真公式的變元時，所得的謂詞公式即為有效公式，故命題演算中的式即為有效公式，故命題演算中的等價公式表等價公式表和和蘊含蘊含式表式表都可推廣到謂詞演算中使用。都可推廣到謂詞演算中使用。l例如例如 2022-2-16192.5謂詞公式的等價與蘊涵(2)量詞否定的等價關系量詞否定的等價關系l例例1 設設P(x)表示表示x今天來校上課，則今天來校上課，則P(x)表示表示x今天今天沒有來校上課。沒有來校上課。l故不是所有人今

23、天來上課與存在一些人今天沒有來上課在意故不是所有人今天來上課與存在一些人今天沒有來上課在意義上相同，義上相同， 即即l xP(x) 彐彐xP(x)。l又，不是存在一些人今天來上課與所有的人今天都沒有來上又，不是存在一些人今天來上課與所有的人今天都沒有來上課在意義上相同，即課在意義上相同，即l( x)P(x) ( x)P(x)。2022-2-16202.5謂詞公式的等價與蘊涵(2)量詞否定的等價關系量詞否定的等價關系(量詞轉換規(guī)律量詞轉換規(guī)律)l為此我們得到公式：為此我們得到公式：l( x)P(x) ( x)P(x) l( x)P(x) ( x)P(x) l證明證明:設設u=a1,a2,an l

24、 ( x)P(x) l (P(a1)P(a2)P(an) l P(a1)P(a2) P(an) l ( x)P(x)2022-2-16212.5謂詞公式的等價與蘊涵(2)量詞否定的等價關系量詞否定的等價關系(量詞轉換規(guī)律量詞轉換規(guī)律)l為此我們得到公式：為此我們得到公式：l( x)P(x) ( x)P(x) l( x)P(x) ( x)P(x) l證明證明:設設u=a1,a2,an l ( x)P(x) l (P(a1)P(a2)P(an) )l P(a1)P(a2) P(an) l ( x)P(x)2022-2-16222.5謂詞公式的等價與蘊涵(3)量詞轄域的擴張與收縮量詞轄域的擴張與收縮

25、 l量詞的作用域中，常有合取或析取項，如果其中一個為量詞的作用域中，常有合取或析取項，如果其中一個為命題命題，則，則可將可將該命題該命題移至量詞作用域之外。如：移至量詞作用域之外。如：l x(A(x) B) x A(x) B l x(A(x) B) x A(x) B l x(BA(x) B x A(x)l x(A(x) B) x A(x) B l x(A(x) B) x A(x) B l x(BA(x) B x A(x)l這是因為在這是因為在B中不出現(xiàn)約束變元中不出現(xiàn)約束變元x，故它屬于或不屬于量詞的作用，故它屬于或不屬于量詞的作用域均有同等意義。域均有同等意義。 l注意：注意：l上面幾式中，

26、上面幾式中，B中不能出現(xiàn)約束變元中不能出現(xiàn)約束變元x。l x(A(x)B) x A(x) B 不成立不成立()l x(A(x)B) x A(x) B 不成立不成立()2022-2-16232.5謂詞公式的等價與蘊涵l x(A(x)B) x A(x) Bl x(A(x)B) x A(x) Bl x(A(x)B) l x(A(x) B) l x A(x) B l x A(x) B l x A(x) B l同理同理, x(A(x)B) x A(x) B l x(A(x)B) l x(A(x) B) l x A(x) B l x A(x) B l x A(x) B 2022-2-16242.5謂詞公式

27、的等價與蘊涵l當謂詞的變元與量詞的指導變元不同時，亦能有類似于上述的公式。例如l x(P(x)Q(y) xP(x)Q(y)l x( yP(x,y)Q(z) x yP(x,y)Q(z)2022-2-16252.5謂詞公式的等價與蘊涵(4)量詞分配的量詞分配的等價等價關系關系 (量詞分配律量詞分配律)l量詞與命題聯(lián)結詞之間存在不同的結合情況，下面舉例量詞與命題聯(lián)結詞之間存在不同的結合情況，下面舉例說明一些等價公式說明一些等價公式 l x(A(x) B(x) x A(x) x B(x) l x(A(x) B(x) x A(x) x B(x) l證明證明:設設u=a1,a2,an l x(A(x) B

28、(x) l (A(a1) B(a1) (A(a2) B(a2) (A(an) B(an) l (A(a1) (A(a2) A(an) (B(a1) (B(a2) B(an) l x A(x) x B(x) l同理可證同理可證, x(A(x) B(x) x A(x) x B(x)2022-2-16262.5謂詞公式的等價與蘊涵(5)量詞分配的量詞分配的蘊含蘊含關系關系 l量詞與命題聯(lián)結詞之間存在一些不同的結合情況，有量詞與命題聯(lián)結詞之間存在一些不同的結合情況，有些是蘊含公式。些是蘊含公式。l x A(x) x B(x)x(A(x) B(x) l x(A(x) B(x)x A(x) x B(x) l“所有的人都喜歡下棋或者所有的人都喜歡打牌所有的人都喜歡下棋或者所有的人都喜歡打牌”可可推出推出 l“所有的人都喜歡下棋或打牌所有的人都喜歡下棋或打牌”，反之不然。，反之不然。 l“有的人喜歡下棋和打牌有的人喜歡下棋和打牌”可推出可推出 l“有的人喜歡下棋并且有的人喜歡打牌有的人喜歡下棋并且有的人喜歡打牌”，反之不然。，反之不然。2022-2-16272.5謂詞公式的等價與蘊涵(6)多重量詞的