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ī)則US 3. 存在指定規(guī)則ES 4. 存在推廣規(guī)則EG 5. 全稱推廣規(guī)則UG 6. 謂詞演算推理規(guī)則應(yīng)用舉例 7. 討論題,謂詞演算的推理方法可視為命題演算推理方法的擴(kuò)張。所以命題演算中的推理規(guī)則，如P規(guī)則、T規(guī)則和CP規(guī)則等亦可在謂詞的推理理論中應(yīng)用。 在謂詞演算的推理中，某些前提或結(jié)論會受到量詞的限制，為了使用這

2、些等價式和永真蘊(yùn)含式，必須有消去或添加量詞的規(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

3、是論域中某個任意的客體。 例如，設(shè)論域是全人類，A(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是論域中的某些客體。,

4、條件: y不是任何給定的前提和居先的推導(dǎo)步驟中的自由變元, 也不是居先的推導(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

5、)卻為假。,4 存在推廣規(guī)則EG,存在推廣規(guī)則 (Existential Generalization)，記為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ī)則時，必須能夠證明對論域

6、中的每一個可能的x，A(x)為真。,條件: 在推出A(x)的前提中，x都必須不是自由的；且A(x)中的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)步是錯誤的

7、, P(c, d)不符合條件的后半句話, 不能引用UG。如果沒有這個限制就會錯誤地證明:,而這一式前面已指明它是不成立的。,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有怪脾氣。 這個論證是,這個論證是無效的

8、，要證明無效，只需找出一種解釋說明上式， 即,非永真即可。 現(xiàn)取論述域?yàn)檎麛?shù)，T(x)：x=1，N(x)：x是奇數(shù)，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(

9、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) 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)

10、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) 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 每個喜歡步行的人不喜歡坐汽車。每個人或者喜歡坐汽車或者喜歡騎自行車。有的人

11、不喜歡騎自行車，因而有的人不喜歡步行。(論述域是人類),7 討論題,例 任何人違反交通規(guī)則，就要受到罰款。因此，如果沒有罰款，則沒有人違反交通規(guī)則。 解：設(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)