1.8 謂詞演算的推理規(guī)則

1、第一章 數(shù)理邏輯 1.1 命題 1.2 重言式1.3 1.4 聯(lián)結(jié)詞的擴(kuò)充與歸約1.5 推理規(guī)則和證明方法1.6 謂詞和量詞1.7 謂詞演算的永真公式1.8 謂詞演算的推理規(guī)則1.8 謂詞演算的推理規(guī)則1. 術(shù)語“A(x)對y是自由的”的意義2. 全稱指定規(guī)則US3. 存在指定規(guī)則ES 4. 存在推廣規(guī)則EG5. 全稱推廣規(guī)則UG6. 謂詞演算推理規(guī)則應(yīng)用舉例7. 討論題謂詞演算的推理方法可視為命題演算推理方法的擴(kuò)張。所以命題演算中的推理規(guī)則，如P規(guī)則、T規(guī)則和CP規(guī)則等亦可在謂詞的推理理論中應(yīng)用。在謂詞演算的推理中，某些前提或結(jié)論會受到量詞的限制，為了使用這些等價式和永真蘊(yùn)含式，必須有消去或

2、添加量詞的規(guī)則。術(shù)語A(x)對y是自由的的意義：在A(x)中x不出現(xiàn)在y或y的轄域中。考察下列(以x為主要個體變元的)謂詞公式: B(x)yP(y)Q(x); C(x)yP(x,y)Q(x,y).則B(x)對y是自由的；而C(x)對y是不自由的。對B(x)可用代入規(guī)則，以y代x得到B(y)。而對C(x)則不能這樣做，因代入后原P(x,y)中的x由自由變元變成了約束變元。1、術(shù)語A(x)對y是自由的的意義2 全稱指定規(guī)則US全稱指定規(guī)則 (Universal Specification)，記為US。 這個規(guī)則是刪除全稱量詞。這里A(x)是謂詞，y是論域中某個任意的客體。例如，設(shè)論域是全人類，A(

3、x)表示“x總是要死的”，那么xA(x)表示“所有人總是要死的”，若y表示“蘇格拉底”，則可以得出結(jié)論A(y)，即“蘇格拉底總是要死的”。條件：A(x)對于y必須是自由的反例：令論述域?yàn)檎麛?shù)集合；A(x)y(x-y=1)，則A(x)對y是不自由的。并且全稱指定規(guī)則：xA(x)A(y)不是有效的！因?yàn)樵谶@個指派下，xA(x)xy(x-y=1)為真而A(y)y(y-y=1)卻為假。3 存在指定規(guī)則ES存在指定規(guī)則 (Existential Specification)，記為ES。 這個規(guī)則是刪除存在量詞。這里y是論域中的某些客體。條件: y不是任何給定的前提和居先的推導(dǎo)步驟中的自由變元, 也不是居

4、先的推導(dǎo)步驟中由于使用本規(guī)則而引入的表面自由變元。為滿足這一條件, 通常使用規(guī)則ES時, 就選用前邊未曾用過的字母作為公式中的y。 (舉例如下頁)例如，設(shè)xA(x)和xB(x)都真，則對某些c和某些d，可以斷定A(c)B(d)為真，但卻不能斷定A(c)B(c)為真或A(d)B(d)為真。 A(x)對于y必須是自由的。反例：令論述域?yàn)檎麛?shù)集合；A(x)y(x-y=1)，則A(x)對y是不自由的。并且存在指定規(guī)則：xA(x)A(y)不是有效的！因?yàn)樵谶@個指派下，xA(x)xy(x-y=1)為真，而A(y)y(y-y=1)卻為假。4 存在推廣規(guī)則EG存在推廣規(guī)則 (Existential Gener

5、alization)，記為EG。這個規(guī)則是添加存在量詞，其中y是論域中的一個客體。該規(guī)則是顯然成立的。因若對論域中的某些客體y，A(y)為真，則在該論域中，xA(x)必為真。條件： A(y)對x是自由的。注：用x取代y時， A(y)不能已有x. （反例）5 全稱推廣規(guī)則UG全稱推廣規(guī)則 (Universal Generalization)，記為UG。這個規(guī)則是添加全稱量詞規(guī)則，其用意在于對命題量化。如果能夠證明對論域中的每一個客體c斷言A(x)成立，則應(yīng)有xA(x)。使用本規(guī)則時，必須能夠證明對論域中的每一個可能的x，A(x)為真。條件: 在推出A(x)的前提中，x都必須不是自由的；且A(x)

6、中的x不是由使用ES而引入的。 在居先的步驟中，如果使用US而求得之x是自由的，那么在后繼步驟中，使用ES而引入的任何新變元都沒有在A(x)中自由出現(xiàn)。條件的前半句是反映“中沒有x的自由出現(xiàn)”這一要求，其作用是使A(x)對任意x都真；后半句的作用相同。條件是說在使用US引出自由變元x之后，不能讓由使用ES而引入的新變元在A(x)中自由出現(xiàn)，如果有這種情況，就不能使用UG規(guī)則。這是因?yàn)镋S引入的新變元是表面的自由變元，A(x)不是對新變元的一切值都可證明。觀察下述推理過程: 第(4)步是錯誤的, P(c, d)不符合條件的后半句話, 不能引用UG。如果沒有這個限制就會錯誤地證明: 而這一式前面已

7、指明它是不成立的。6 推理規(guī)則應(yīng)用舉例例1 證明蘇格拉底三段論： x(M(x)D(x)M(s)D(s)，其中 M(x)：x是人。D(x)：x是要死的。s：蘇格拉底。證: x(M(x)D(x) P M(s)D(s) US,T1 M(s) P D(s) T2,3,I例2 證明或否定以下論證。 (a) 每個大學(xué)教師都是知識分子，有些知識分子有怪脾氣，所以有些大學(xué)教師有怪脾氣。解 設(shè)T(x): x是大學(xué)教師，N(x): x是知識分子，H(x): x有怪脾氣。 這個論證是 這個論證是無效的，要證明無效，只需找出一種解釋說明上式， 即 非永真即可。 現(xiàn)取論述域?yàn)檎麛?shù)，T(x)：x=1，N(x)：x是奇數(shù)，

8、H(x)：x是質(zhì)數(shù)。則x(T(x)N(x)是真， x(N(x)H(x)是真，但x(T(x)H(x)是假，故非永真式。這個論證是有效的，證明如下：解 設(shè)P(x)：x是松樹，Q(x)：x是針葉樹，R(x)：x是冬季落葉的樹。 這個論證是 (b) 每一松樹都是針葉樹，每一冬季落葉的樹都非針葉樹，所以，每一冬季落葉的樹都非松樹。例3 證明：x(C(x)W(x)R(x) x(C(x)Q(x) x(Q(x)R(x)證: x (C(x)Q(x) P C(a)Q(a) ES,T1 x(C(x)W(x)R(x) P C(a)W(a)R(a) US,T3 C(a) T2,I W(a)R(a) T4,5,I Q(a

9、) T2,I R(a) T6,I Q(a)R(a) T7,8,I x(Q(x)R(x) T9,EG注意，推導(dǎo)中第、步和第、步的次序不能顛倒。例4 證明: x(P(x)Q(x) xP(x)xQ(x)證法1: 把(x)P(x)(x)Q(x)作為假設(shè)前提。 (xP(x)xQ(x) P xP(x) xQ(x) T1,E xP(x) T2,I x P(x) T3,E xQ(x) T2,I x Q(x) T5,E P(c) T4,ES Q(c) T6,US P(c)Q(c) T7,8,I (P(c)Q(c) T9,E x(P(x)Q(x) P P(c)Q(c) US (P(c)Q(c)(P(c)Q(c)

10、T10,12,矛盾例4 證明: x(P(x)Q(x) xP(x)xQ(x)證法2: 原式可改寫為 x(P(x)Q(x) xP(x)xQ(x)可用CP規(guī)則轉(zhuǎn)化為證明: x(P(x)Q(x)xP(x) xQ(x) x(P(x) P(附加前提) xP(x) T1,E P(c) T2,ES x(P(x)Q(x) P P(c)Q(c) T4,US Q(c) T3,5,I xQ(x) EG例5 每個喜歡步行的人不喜歡坐汽車。每個人或者喜歡坐汽車或者喜歡騎自行車。有的人不喜歡騎自行車，因而有的人不喜歡步行。(論述域是人類)7 討論題例 任何人違反交通規(guī)則，就要受到罰款。因此，如果沒有罰款，則沒有人違反交通規(guī)

11、則。解：設(shè)S(x,y): “x違反y?！?x的論域?yàn)椤叭祟悺?M(y): “y是交通規(guī)則?！?P(z): “z是罰款?！?R(x,z): “x受到z?！惫是疤崾牵?x(y(S(x,y)M(y)z(P(z)R(x,z)結(jié)論是：zP(z)xy(S(x,y)M(y)注：xy(S(x,y)M(y)表示，“任意x違反了任何y，則y不是交通規(guī)則”。即沒有人違反交通規(guī)則。提出的問題：下面的證明是否嚴(yán)格？下證x (y(S(x,y)M(y)z(P(z)R(x,z) zP(z)xy(S(x,y)M(y) x (y(S(x,y)M(y)z(P(z)R(x,z) P y(S(b,y)M(y)z(P(z)R(b,z) US,T1 zP(z) P(附加前提) zP(z) T3,E P(a) T4,US P(a)R(b,a)