《離散數(shù)學(xué)左孝陵版第二章答案.ppt》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)左孝陵版第二章答案.ppt（64頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、Charter two,welcome,第二章 謂詞邏輯,1 謂詞的概念與表示法 2 命題函數(shù)與量詞 3 謂詞公式與翻譯 4 變元的約束 5 謂詞演算的等價(jià)式與蘊(yùn)含式 6 前束范式 7 謂詞演算的推理理論,1 謂詞的概念與表示法,在研究命題邏輯中， 原子命題是命題演算中最基本的單位，不再對原子命題進(jìn)行分解， 這樣會產(chǎn)生二大缺點(diǎn)：（1）不能研究命題的結(jié)構(gòu)，成分和內(nèi)部邏輯的特征；（2）也不可能表達(dá)二個(gè)原子命題所具有的共同特征，甚至在命題邏輯中無法處理一些簡單又常見的推理過程。 例：蘇格拉底論證是正確的，但不能用命題邏輯的推理規(guī)則推導(dǎo)出來?！八械娜丝偸且赖摹? A “蘇格拉底是人。

2、 B “所以蘇格拉底是要死的?！? C,1 謂詞的概念與表示法,1.謂詞： 定義：用以刻劃客體的性質(zhì)或關(guān)系的即是謂詞。 我們可把陳述句分解為二部分： 主語（名詞，代詞）和謂語（動(dòng)詞）。 例：張華是學(xué)生，李明是學(xué)生。則可把它表示成： H:表示“是學(xué)生”，j:表示“張華”，m:表示“李明”，則可用下列符號表示上述二個(gè)命題：H(j)，H(m)。 H作為“謂詞”（或者謂詞字母）用大寫英文字母表示，j,m為主語，稱為“客體”或稱“個(gè)體”。,1 謂詞的概念與表示法,（1）謂詞填式：謂詞字母后填以客體所得的式子。 例：H(a, b) （2）若謂詞字母聯(lián)系著一個(gè)客體，則稱作一元謂詞；若謂詞字母聯(lián)系著二個(gè)客

3、體，則稱作二元謂詞；若謂詞字母聯(lián)系著n個(gè)客體，則稱作n元謂詞。 （3）客體的次序必須是有規(guī)定的。例：河南省北接河北省。 n L b寫成二元謂詞為：L(n,b)，但不能寫成L(b,n) 。,2 命題函數(shù)與量詞,1. 命題函數(shù) 客體在謂詞表達(dá)式中可以是任意的名詞。例：C“總是要死的?！? j：張三；t：老虎；e：桌子。 則C(j), C(t), C(e)均表達(dá)了命題。 在上面的例子中，C：表示“總是要死的”；x：表示變元（客體變元），則C(x)表示“x總是要死的”，則稱C(x)為命題函數(shù)。 定義由一個(gè)謂詞字母和一個(gè)非空的客體變元的集合所組成的表達(dá)式，稱為簡單命題函數(shù)。,2 命題函數(shù)與

4、量詞,討論定義：（a）當(dāng)簡單命題函數(shù)僅有一個(gè)客體變元時(shí)，稱為一元簡單命題函數(shù)；（b）若用任何客體去取代客體變元之后，則命題函數(shù)就變?yōu)槊}；（c）命題函數(shù)中客體變元的取值范圍稱為個(gè)體域（論述域）。 例：P(x)表示x是質(zhì)數(shù)。這是一個(gè)命題函數(shù)。 其值取決于個(gè)體域。 可以將命題函數(shù)命題，有兩種方法：,2 命題函數(shù)與量詞,a)將x取定一個(gè)值。如：P(4)，P(5) b)將謂詞量化。如：xP(x)，xP(x) 個(gè)體域的給定形式有二種： 具體給定。 如：j, e, t 全總個(gè)體域任意域：所有的個(gè)體從該域中取得。,2 命題函數(shù)與量詞,2.量詞 （1）全稱量詞“”為全稱量詞符號，讀作“對于所有的”，“對任一個(gè)

5、”，“對一切”。例：“這里所有的都是蘋果” 可寫成： xA(x)或(x)A(x) 幾種形式的讀法： xP(x)： “對所有的x，x是”； xP(x) ： “對所有x，x不是”； xP(x) ： “并不是對所有的x，x是”； xP(x) ： “并不是所有的x，x不是”。,2 命題函數(shù)與量詞,例：將“對于所有的x和任何的y，如果x高于y，那么y不高于x”寫成命題表達(dá)形式。解： x y(G(x,y) G(y,x)) G(x,y)：x高于y （2）存在量詞“”為存在量詞符號，讀作“存在一個(gè)”，“對于一些”，“對于某些”，“至少存在一個(gè)”，“這里存在著這樣的”等等。 “”表達(dá)式的讀法： x A(x

6、) ：存在一個(gè)x,使x是； xA(x) ：存在一個(gè)x, 使x不是； x A(x) ：不存在一個(gè)x, 使x是； xA(x) ：不存在一個(gè)x, 使x不是。,2 命題函數(shù)與量詞,例：（a）存在一個(gè)人； （b）某個(gè)人很聰明； （c）某些實(shí)數(shù)是有理數(shù) 將（a）,（b）,（c）寫成命題。 解：規(guī)定：M(x)：x是人；C(x)：x是很聰明； R1(x)：x是實(shí)數(shù)(特性謂詞) R2(x)：x是有理數(shù)。 則 （a） x M(x) ； （b） x (M(x) C(x))； （c） x (R1(x) R2(x)) 。 （3）量化命題的真值：決定于給定的個(gè)體域 給定個(gè)體域：a1an以a

7、1an中的每一個(gè)代入xP(x)P(a1) P(an) xQ(x)Q(a1) Q(an),3謂詞公式與翻譯,1.謂詞公式原子謂詞公式：不出現(xiàn)命題聯(lián)結(jié)詞和量詞的謂詞命名式稱為原子謂詞公式，并用P(x1xn)來表示。（P稱為n元謂詞， x1xn稱為客體變元），當(dāng)n=0時(shí)稱為零元謂詞公式。 定義（謂詞公式的歸納法定義） 原子謂詞公式是謂詞公式； 若A是謂詞公式，則A也是謂詞公式； 若A, B都是謂詞公式，則(AB),(AB),(AB),(AB)都是謂詞公式； 若A是謂詞公式，x是任何變元，則xA, xA也都是謂詞公式；,3謂詞公式與翻譯,只有按-所求得的那些公式才是謂詞公式（謂詞公式又簡稱“公式”）

8、。 例1：任何整數(shù)或是正的，或是負(fù)的。解：設(shè)：I(x): x是整數(shù)； R1(x)：x是正數(shù)；R2(x)：x是負(fù)數(shù)。 此句可寫成：x(I(x)(R1(x) R2(x) )。 例2：試將蘇格拉底論證符號化：“所有的人總是要死的。因?yàn)樘K格拉底是人，所以蘇格拉底是要死的?！苯猓涸O(shè)M(x)：x是人；D(x)：x是要死的； M(s)：蘇格拉底是人；D(s)：蘇格拉底是要死的。,3謂詞公式與翻譯,寫成符號形式： x(M(x) D(x))， M(s) D(s) 2.由于對個(gè)體描述性質(zhì)的刻劃深度不同，可翻譯成不同形式的謂詞公式。,4變元的約束,1.轄域：緊接在量詞后面括號內(nèi)的謂詞公式。 例： xP(x)

9、, x(P(x) Q(x)) 。 若量詞后括號內(nèi)為原子謂詞公式，則括號可以省去。 2.自由變元與約束變元約束變元：在量詞的轄域內(nèi)，且與量詞下標(biāo)相同的變元。 自由變元：當(dāng)且僅當(dāng)不受量詞的約束。 例： xP(x,y) , x(P(x) y(P(x,y)) 。,4變元的約束,3.約束變元的改名規(guī)則任何謂詞公式對約束變元可以改名。 我們認(rèn)為xP(x,y)和zP(z,y)是一等價(jià)的謂詞公式，但是需注意，不能用同一變元去表示同一謂詞公式中的二個(gè)變元。例如： yP(y,y)是不正確的。 下面介紹約束變元的改名規(guī)則：（a）在改名中要把公式中所有相同的約束變元全部同時(shí)改掉；（b）改名時(shí)所用的變元符號在量詞轄域

10、內(nèi)未出現(xiàn)的。,4變元的約束,例： xP(x) yR(x,y)可改寫成xP(x) zR(x,z) ，但不能改成xP(x) xR(x,x) ， xR(x,x)中前面的x原為自由變元，現(xiàn)在變?yōu)榧s束變元了。 4.區(qū)別是命題還是命題函數(shù)的方法（a）若在謂詞公式中出現(xiàn)有自由變元，則該公式為命題函數(shù)；（b）若在謂詞公式中的變元均為約束出現(xiàn)，則該公式為命題。 例： xP(x,y,z)是二元謂詞， yxP(x,y,z)是一元謂詞， 而謂詞公式中如果沒有自由變元出現(xiàn)，則該公式是一個(gè)命題。,4變元的約束,舉例： 例1：“沒有不犯錯(cuò)的人?！苯猓涸O(shè)F(x)為“x犯錯(cuò)誤”，M(x)為“x是人”（特性謂詞）。 可把

11、此命題寫成： (x(M(x) F(x))) x(M(x)F(x)) 例2：“x是y的外祖父” “x是z的父親且z是y的母親”設(shè)P(z)：z是人；F(x,z)：x是z的父親；M(z,y)：z是y的母親。則謂詞公式可寫成：z(P(z) F(x,z) M(z,y)) 。 5.代入規(guī)則：對公式中的自由變元的更改叫做代入。 (a)對公式中出現(xiàn)該自由變元的每一處進(jìn)行代入， (b)用以代入的變元與原公式中所有變元的名稱不能相同。,4變元的約束,6.個(gè)體域（論述域，客體域）:用特定的集合表示的被約束變元的取值范圍。 (1)個(gè)體域不同，則表示同一命題的謂詞公式的形式不同。例：“所有的人必死?！绷?/p>

12、D(x)，x是要死的。 下面給出不同的個(gè)體域來討論： ()個(gè)體域?yàn)椋喝祟悾?則可寫成xD(x)； ()個(gè)體域?yàn)槿我庥颍ㄈ倐€(gè)體域），則人必須首先從任意域中分離出來， 設(shè)M(x)，x是人，稱M(x)為特性謂詞。命題可寫成 x(M(x) D(x)),4變元的約束,（2）個(gè)體域不同，則表示同一命題的值不同。Q(x): x<5,（3）對于同一個(gè)體域，用不同的量詞時(shí)，特性謂詞加入的方法不同。 對于全稱量詞，其特性謂詞以前件的方式加入； 對于存在量詞，其特性謂詞以與的形式加入。,4變元的約束,例：設(shè)個(gè)體域?yàn)? 白虎（白貓），黃咪（黃貓），，， 同時(shí)令C(x)：x是貓（特性謂詞）；B(x)：

13、x是黑色的；A(x)：x是動(dòng)物。 （）描述命題：“所有的貓都是動(dòng)物”。 即： x(C(x) A(x))（T）（真命題） 寫成x(C(x) A(x)) （F）則為假命題了。 x(C(x) A(x))TT T TT x(C(x) A(x)) TT F FF （）描述命題：“一些貓是黑色的” 。 x(C(x) B(x)) FF F F F 而 x(C(x) B(x))F F T TT,4變元的約束,7.量詞對變元的約束，往往與量詞的次序有關(guān)。 例： yx(x

14、若對A和B的任一組變元進(jìn)行賦值，使得A和B的值相同，則稱A和B遍及E是互為等價(jià)的，記為AB或 A,E,,B,定義給定謂詞公式A，E是A的個(gè)體域。若給A中客體變元指派E中的每一個(gè)客體名稱所得命題的值均為真，則稱A在E中是永真的。若E為任意域則稱A是永真的。,5謂詞演算的 等價(jià)式與蘊(yùn)含式,定義給定謂詞公式A，E是A的個(gè)體域。若給A中客體變元指派E中每一個(gè)客體名稱，在E中存在一些客體名稱，使得指派后的真值為“T”，則A稱是可滿足的。 定義若給A中客體變元指派個(gè)體域中任一客體名稱，使命題的值均為“F”，則稱A是永假的。 1.不含量詞的謂詞公式的永真式 : 只要用原子謂詞公式去代命題公式的永真

15、式中的原子命題變元，則在第一章中永真蘊(yùn)含式和等價(jià)公式均可變成謂詞演算中的永真式：,5謂詞演算的 等價(jià)式與蘊(yùn)含式,命題邏輯 謂詞邏輯 (x)(x) (x)(x)(x) . . . . (x)(x) (x) (x) (x)(x)(x) (x)(x) (x) . . . . . .,5謂詞演算的 等價(jià)式與蘊(yùn)含式,2.含有量詞的等價(jià)式和永真蘊(yùn)含式 設(shè)個(gè)體域?yàn)椋篠=a1,a2,an，我們有： xA(x)A(a1)

16、 A(a2) A(an) xA(x) A(a1)A(a2) A(an) 上例說明： 若個(gè)體域是有限的，則可省掉量詞。 若個(gè)體域是無限的，則可將上述概念推廣從而省去量詞，不過要注意這是由無限項(xiàng)組成的命題。,5謂詞演算的 等價(jià)式與蘊(yùn)含式,例：設(shè)個(gè)體域?yàn)椋篘=0,1,2， P(x)表示：x3 ,則可寫出： xP(x)P(0) P(1) P(i) xP(x) P(0)P(1) P(i) 下面分類介紹在謂詞公式中含有量詞的等價(jià)式和永真蘊(yùn)含式。 （1）量詞轉(zhuǎn)換律： E25(Q3) xP(x) xP(x) E26(Q4) xP(x) xP(x) 下面證明：設(shè)個(gè)體域?yàn)椋?S=a1,a2,a

17、n,5謂詞演算的 等價(jià)式與蘊(yùn)含式,xP(x) (P(a1) P(a2) P(an)) P(a1) P(a2) P(an)xP(x) 下面舉例說明量化命題和非量化命題的差別:否定形式不同例： 否定下列命題： (a)上海是一個(gè)小城鎮(zhèn) A(s) (b)每一個(gè)自然數(shù)都是偶數(shù) x(N(x)E(x)) 上述二命題的否定為： (a)上海不是一個(gè)小城鎮(zhèn) A(s) (b)有一些自然數(shù)不是偶數(shù) x(N(x)E(x))x(N(x)E(x)) x(N(x)E(x)) x (N(x) E(x)),5謂詞演算的 等價(jià)式與蘊(yùn)含式,結(jié)論：對于非量化命題的否定只需將動(dòng)詞否定，而對于量化命題的否定

18、不但對動(dòng)詞進(jìn)行否定而且對量詞同時(shí)進(jìn)行否定，其方法是： x的否定變?yōu)閤 ， x的否定變?yōu)閤 。 （2） 量詞轄域的擴(kuò)張及其收縮律 E27(Q6) xA(x) P x(A(x) P) (Q7) xA(x) P x(A(x) P) E28(Q9) xA(x) P x(A(x) P) (Q8) xA(x) P x(A(x) P) P為不含有變元的任何謂詞公式,5謂詞演算的 等價(jià)式與蘊(yùn)含式,證明E27(Q6)，設(shè)個(gè)體域?yàn)椋?S=a1,a2,an xA(x) P(A(a1) A(a2) A(an)) P (A(a1)P)(A(a2)P) (A(an) P ) x(A(x) P) E

19、30 (Q14) xA(x)B x(A(x)B) E31 (Q15) xA(x)B x(A(x)B) E32(Q16) AxB(x) x(AB (x)) E33 (Q17) A x B(x) x(AB (x)) 證明E30 (Q14) ，設(shè)個(gè)體域?yàn)椋?S=a1,a2,an x(A(x)B) (A(a1)B) (A(an)B) (A(a1) B) (A(an) B),5謂詞演算的 等價(jià)式與蘊(yùn)含式, (A(a1) A(an)) B x A(x) B x(A(x) B) xA(x)B （3）量詞分配律 E24(Q10) x(A(x)B(x)) xA(x) xB(x) E23

20、(Q11) x (A(x) B(x)) xA(x) xB(x) I18(Q12) x (A(x) B(x)) xA(x) xB(x) I17(Q13) xA(x) xB(x) x(A(x) B(x)) E29(Q18) x (A(x) B(x)) xA(x) xB(x) I19(Q19) xA(x) xB(x) x(A(x) B(x)),5謂詞演算的 等價(jià)式與蘊(yùn)含式,證明E24(Q10)和I19(Q19) ，設(shè)個(gè)體域?yàn)椋?S=a1,a2,an E24(Q10) x(A(x)B(x)) (A(a1)B(a1)) . (A(an)B(an)) (A(a1) A(an)) (B(a1)

21、 B(an)) xA(x) x B(x) I19(Q19) xA(x) xB(x) xA(x) xB(x) xA(x) xB(x) (A(a1) A(an)) (B(a1) B(an)) (A(a1) B(a1)) (A(a1) B(an)) (A(an) B(a1)) (A(an) B(an)),5謂詞演算的 等價(jià)式與蘊(yùn)含式, (A(a1) B(a1)) (A(an) B(an)) x(A(x) B(x)) x(A(x) B(x)) （4）量詞的添加和除去的永真蘊(yùn)含式 Q1 xP(x) P(y) Q2 P(y) xP(x) Q5

22、 xP(x) xP(x) xP P xP P (P為不含x變元）,,Y是個(gè)體域中任一元素,5謂詞演算的 等價(jià)式與蘊(yùn)含式,（5）含有多個(gè)量詞的永真式：（）量詞出現(xiàn)的次序直接關(guān)系到命題的含義： “xy”表示：“無論選定一個(gè)什么樣的x值總能找到一個(gè)y能使x和y” “yx”表示：“只選取一個(gè)y值，以致無論怎樣選定一個(gè)x，能夠使y和x” 下面列出對應(yīng)的表達(dá)式可以看出其不同處：設(shè)x的個(gè)體域?yàn)椋?a1,a2,an ， y的個(gè)體域?yàn)椋?b1,b2,bn ，則： xyP(x,y) yP(a1,y) yP(an,y),5謂詞演算的 等價(jià)式與蘊(yùn)含式, (P(a1, b1) P(a

23、1, bn)) (P(an, b1) P(an, bn)) yxP(x,y) xP(x, b1) xP(x, bn) (P(a1, b1) P(an, b1)) (P(a1, bn) P(an, bn)) 例：x,y的個(gè)體域鞋子，P(x,y):和配成一雙鞋子。 xyP(x,y) T yxP(x,y) F,5謂詞演算的 等價(jià)式與蘊(yùn)含式,（）在含有多個(gè)量詞的謂詞公式中, xy, xy的位置是可以改變的,且不影響命題的真值。 例：x,y的個(gè)體域?yàn)镹=0,1,2，則 xyP(x,y) yP(0,y) yP(i,y) (P(0,0) P(0,1) P(0,j) )

24、 (P(i,0) P(i,1) P(i,j) ) (P(0,0) P(1,0) P(i,0) ) (P(0,1) P(1,1) P(i,1) ) xP(x,0) xP(x,1) xP(x,j) yxP(x,y),5謂詞演算的 等價(jià)式與蘊(yùn)含式,同樣： xyP(x,y) yxP(x,y) （）量詞轉(zhuǎn)換律的推廣應(yīng)用:把深入到謂詞公式前面去的方法。 xyzP(x,y,z) x yzP(x,y,z) xyzP(x,y,z) xyzP(x,y,z) （）兩個(gè)量詞, 所組成的謂詞公式的等價(jià)式和永真

25、蘊(yùn)含式（8個(gè)） xyP(x,y) yxP(x,y) xyP(x,y) yxP(x,y) yxP(x,y) xyP(x,y) yxP(x,y) xyP(x,y),5謂詞演算的 等價(jià)式與蘊(yùn)含式,xyP(x,y) yxP(x,y) xyP(x,y) yxP(x,y) yxP(x,y) xyP(x,y) xyP(x,y) yxP(x,y) （6）謂詞公式的對偶式 定義 在一個(gè)謂詞公式A中（其中不出現(xiàn),詞）把公式A中 , , F, T, , , 變?yōu)楣紸*中 , , T, F, , , 則稱A*是A的對偶式。 定理 若謂詞公式A B，則A* B* ；若謂詞公式A B ，則B* A*

26、 （ 這里A,B有同樣的個(gè)體域）。,5謂詞演算的 等價(jià)式與蘊(yùn)含式,例： I17(Q13) xA(x) xB(x) x(A(x)B(x)) I18(Q12) xA(x) xB(x) x(A(x) B(x)),6 前束范式,定義一個(gè)公式，如果量詞均非否定地在全式的開頭，它們的作用域延伸到整個(gè)公式的末尾，則稱此公式叫前束范式。 例： xyz( Q(x,y) R(z)) (前束范式) 定理 任何一個(gè)謂詞公式均和一個(gè)前束范式等價(jià)。證明：利用量詞轉(zhuǎn)換把深入到原子謂詞公式前, 利用約束變元的改名規(guī)則， 利用量詞轄域的擴(kuò)張收縮律,把量詞移到全式的最前面，這樣一定可得到等價(jià)的前束范式。,6

27、前束范式,例： xP(x) R(x) yP(y) R(x) y(P(y) R(x)) 例：把xP(x) xQ(x) 變成前束范式。xP(x) xQ(x) xP(x)xQ(x) xP(x) xQ(x) x(P(x) Q(x)),7謂詞演算的推理理論,1.含有量詞的特殊永真式 定義 設(shè)A(x)是一個(gè)謂詞公式，x是其中的自由變元，若把y代入到A(x)里而不會產(chǎn)生變元的新的約束出現(xiàn)，則稱A(x)對于y是自由的。 例：下面A(x)對于y是自由的： A(x) zP(z) Q(x,z),這里x為自由變元,若用y去取代A(x)中的x, A(y) zP(z) Q(

28、y,z),這里y也仍為自由變元；,7 謂詞演算的推理理論,下面A(x)對于y不是自由的： A(x) y(S(x) S(y)), x為自由變元， 若用y代入A(x)的x中去得： A(y) y(S(y) S(y)) ，y變?yōu)榧s束變元了，產(chǎn)生了新的約束出現(xiàn)。 如有必要代入y，則應(yīng)先將式中的約束變元y改名。 z(S(x)S(z))然后代入y z(S(y)S(z))y仍為自由變元。 歸結(jié)： 判定A(x)對于y是自由的，只要看公式A(x)中y, y的轄域內(nèi)有沒有x的自由出現(xiàn)就行：若有x的自由出現(xiàn)則A(x)對于y不是自由的，若無的x自由出現(xiàn)則一定可以肯定A(x)對于y是自由的。,7 謂詞演算的推理理

29、論,下面分別介紹四個(gè)推理規(guī)則 （1）全稱指定規(guī)則（US規(guī)則）。如果對個(gè)體域中所有客體x, A(x)成立，則對個(gè)體域中某個(gè)任意客體c， A(c) 成立。該規(guī)則表示成： xA(x) A(c) (x,c個(gè)體域) （2）全稱推廣規(guī)則（UG規(guī)則） 如果能夠證明對個(gè)體域中每一個(gè)客體c，命題A(c) 都成立，則可得到結(jié)論xA(x) 成立。該規(guī)則表示成： A(x) xA(x),7 謂詞演算的推理理論,（3）存在指定規(guī)則（ES規(guī)則）如果對于個(gè)體域中某些客體A(x)成立，則必有某個(gè)特定的客體c，使A(c)成立。該規(guī)則表示成： xA(x) A(c) 例：x的個(gè)體域?yàn)镮=整數(shù)，P(x)

30、:x是偶數(shù)，Q(x): x是奇數(shù)。 xP(x) xQ(x) T 但 P(c) Q(c) F,7 謂詞演算的推理理論,（4）存在推廣規(guī)則（EG規(guī)則） 如果對個(gè)體域中某個(gè)特定客體c，有A(c) 成立，則在個(gè)體域中，必存在x，使A(x)成立。該規(guī)則表示成： A(c) xA(x) 2 推論規(guī)則及使用說明 命題邏輯中的P,T,CP規(guī)則和簡接證明法，都可以引用到謂詞邏輯的推論規(guī)則中來，不過要注意對量詞做適當(dāng)處理， 其方法是：用US,ES在推導(dǎo)中去掉量詞，用UG,EG使結(jié)論量化。,7謂詞演算的推理理論,規(guī)則使用說明：（1）在使用ES,US時(shí)一定要是前束范式（2）推導(dǎo)中連續(xù)使用US規(guī)則可用相同

31、變元 xP(x) P(y), xQ(x) Q(y), （3）推導(dǎo)中既ES用，又用US， 則必須先用ES ，后用US方可取相同變元，反之不行。 xP(x) P(y) xQ(x) Q(y) （4）推導(dǎo)中連續(xù)使用ES規(guī)則時(shí)，使用一次更改一個(gè)變元。,7謂詞演算的推理理論,例：證明蘇格拉底論證x(M(x)D(x))M(s) D(s) (1) M(s) P (2) x(M(x)D(x)) P (3) M(s)D(s) US (4) D(s) T 例：證： x(H(x)M(x)) , xH(x) xM(x),7謂詞演算的推理理論,(1) xH(x) P (2

32、) H(c) ES (3) x(H(x)M(x)) P (4) H(c) M(c)US (5) M(c)T (6) xM(x) EG 例：證: x (P(x)Q(x)) x P(x) xQ(x) (1) x P(x)引入前件 (2) x (P(x)Q(x)) P (3)P(c) Q(c)ES,7謂詞演算的推理理論,(4) P(c) US (5) Q(c) T (6) xQ(x) EG (7) x P(x)xQ(x) CP 例：證明： x(P(x)Q(x)), xP(x) xQ(x) (1) xQ(x) 假設(shè)前提 (2) xQ(x) T (3) Q(c)US (4) xP(x

33、) P,7謂詞演算的推理理論,(5) P(c) US (6) P(c)Q(c) T (7) x(P(x)Q(x)) UG (8) x(P(x)Q(x)) P (9) x(P(x)Q(x)) x(P(x)Q(x)) T (10) F 例：下列結(jié)論能否從前提中推出： x (P(x)Q(x)) , Q(a) x P(x) a為x個(gè)體域中一個(gè)元素 (1) Q(a) P (2) x (P(x)Q(x)) P,7謂詞演算的推理理論,(3) P(a)Q(a)US (4) P(a)T (5) x P(x)UG 在使用US,ES,UG,EG這四條規(guī)則時(shí),要注意嚴(yán)格按

34、照它們的規(guī)定去使用。,7謂詞演算的推理理論,書中例4證明： (1)x(y(S(x,y)M(y))z(P(z)R(x,z))P (2)y(S(b,y) M(y))z(P(z)R(b,z))US(1) (3)(z)P(z)附加前提 (4)z(P(z))T(3) (5)P(a) US(4) (6)P(a)R(b,a) T(5) (7)(P(a)R(b,a)) T(6) (8)z(P(z)R(b,z)) UG(7) (9)z(P(z)R(b,z)) T(8),7謂詞演算的推理理論,(10)y(S(b,y) M(y))T(2)(9) (11)y(S(b,y) M(y))T(10) (12)(S(b

35、,c) M(c)) US(11) (13)S(b,c) M(c) T(12) (14) S(b,c) M(c) T(13) (15)y(S(b,y) M(y)) UG(14) (16)xy(S(x,y) M(y)) UG(15) (17) (z)P(z) xy(S(x,y) M(y)) CP(3)(16),7謂詞演算的推理理論,例： 二個(gè)量詞的推理比較復(fù)雜： xP(x) x(P(x)Q(x) R(x)) , xP(x), xQ(x) x y(R(x) R(y)) (1) xP(x) P (2) P(w) ES (3) P(w) Q(w) T (4) xP(x)

36、x(P(x)Q(x) R(x)) P (5) x(P(x)Q(x) R(x)) T,7謂詞演算的推理理論,(6) P(w)Q(w) R(w)US (7) R(w) T (8) xR(x) EG (9) xQ(x) P (10) Q(z) ES (11) P(z) Q(z) T (12) P(z)Q(z) R(z) US,7謂詞演算的推理理論,(13) R(z) T (14) yR(y) EG (15) xR(x) yR(y)T (16) x y(R(x) R(y))T 三個(gè)量詞的推理過程更為復(fù)雜,第二章小結(jié),學(xué)習(xí)第二章要注意以下幾點(diǎn)： (1)同一個(gè)命題在不同個(gè)體域內(nèi)

37、可能有不同的符號化形式，同時(shí)也可能有不同的真值，因而在將一個(gè)命題符號化之前，必須弄清個(gè)體域。 (2)在將命題符號化時(shí)，要特別注意量詞與聯(lián)結(jié)詞的搭配。經(jīng)常的情況是全稱量詞與蘊(yùn)含詞搭配，存在量詞與合取詞搭配。因此有下面兩種形式的公式： x(A(x) B(x)) x(A(x) B(x)) 而 x(A(x) B(x)) x(A(x) B(x)) ,第二章小結(jié),與，與的含義完全不同。 (3)記住主要的等價(jià)式。會用約束變元和自由變元換名規(guī)則進(jìn)行等價(jià)演算，求出給定公式的前束范式。 (4)在謂詞演算的推理證明中，要特別注意US，UG，ES，EG規(guī)則成立的條件。,例題選講,例1.符號

38、化下列命題： (1)沒有不犯錯(cuò)誤的人； (2)發(fā)光的不都是金子； (3)在南京高校學(xué)習(xí)的學(xué)生，未必都是南京籍的學(xué)生。 解： (1)設(shè)M(x)： x是人。 Q(x)：x犯錯(cuò)誤。 本題符號化為： x(M(x)Q(x)) 或者： (x)(M(x)Q(x)) (2)設(shè)L(x)： x是發(fā)光的東西。G(x)：x是金子。 x(L(x)G(x)) 或 x(L(x)G(x)),例題選講,(3)設(shè)S(x)：x是南京高校學(xué)習(xí)的學(xué)生。 F(x)：x是南京籍的學(xué)生。 則 x(S(x)F(x)) 本題也可加深刻劃：S(x)：x是學(xué)生。L(x)：x在學(xué)習(xí)。 H(x)：x在南京高校。 G(

39、x)：x是南京籍的人。 則(x)(S(x)L(x)H(x)G(x) S(x)),例題選講,例2.寫出x(F(x)G(x))(xF(x) xG(x))的前束范式。 解：原式 x(F(x)G(x))((x)F(x) (x)G(x)) (x)(F(x)G(x)) ((x)F(x) (x)G(x)) (x)((F(x) G(x)) G(x)) (x) F(x) (x)((F(x) G(x)) (x) F(x) (x)((F(x) G(x)) (y) F(y) (x) (y) (F(x) G(x) F(y)),作業(yè),P8 1，5 P111，5 P184(c)，6，7(a),(b) P231，2，6，8(c),(d) P292，3 P391，2(b)，3(b)，4(c),(f)，5(b) P461(a),(b)，2(a)，4(a) P591(d)(g)(h)， 2(d)(i)(l) P621(f)(g)，5,作業(yè),P651(c)，2(c)，4 P726，7 P751(b)(c) P791(a)(d)，2(a)，3(b),