離散數(shù)學(xué)左孝陵版第二章答案.ppt

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

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

2、拉底是要死的?！?C,1 謂詞的概念與表示法,1.謂詞： 定義：用以刻劃客體的性質(zhì)或關(guān)系的即是謂詞。 我們可把陳述句分解為二部分： 主語(yǔ)（名詞，代詞）和謂語(yǔ)（動(dòng)詞）。 例：張華是學(xué)生，李明是學(xué)生。則可把它表示成： H:表示“是學(xué)生”，j:表示“張華”，m:表示“李明”，則可用下列符號(hào)表示上述二個(gè)命題：H(j)，H(m)。 H作為“謂詞”（或者謂詞字母）用大寫英文字母表示，j,m為主語(yǔ)，稱為“客體”或稱“個(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è)腕w變?cè)?，則C(x)表示“x總是要死的”，則稱C(x)為命題函數(shù)。 定義由一個(gè)謂詞字母和一個(gè)非空的客體變?cè)募纤M成的表達(dá)式，稱為簡(jiǎn)單命題函數(shù)。,2 命題函數(shù)與量詞,討論定義：（a）當(dāng)簡(jiǎn)單命題函數(shù)僅

4、有一個(gè)客體變?cè)獣r(shí)，稱為一元簡(jiǎn)單命題函數(shù)；（b）若用任何客體去取代客體變?cè)?，則命題函數(shù)就變?yōu)槊}；（c）命題函數(shù)中客體變?cè)娜≈捣秶Q為個(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）全稱量詞“”為全稱量詞符號(hào)，讀作“對(duì)于所有的”，“對(duì)任一個(gè)”，“對(duì)一切”。例：“這里所有的都是蘋

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

6、一個(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以a1an中的每一個(gè)代入xP(x)P(a1) P(an) xQ(x)Q(a1) Q(a

7、n),3謂詞公式與翻譯,1.謂詞公式原子謂詞公式：不出現(xiàn)命題聯(lián)結(jié)詞和量詞的謂詞命名式稱為原子謂詞公式，并用P(x1xn)來表示。（P稱為n元謂詞， x1xn稱為客體變?cè)?，?dāng)n=0時(shí)稱為零元謂詞公式。 定義（謂詞公式的歸納法定義） 原子謂詞公式是謂詞公式； 若A是謂詞公式，則A也是謂詞公式； 若A, B都是謂詞公式，則(AB),(AB),(AB),(AB)都是謂詞公式； 若A是謂詞公式，x是任何變?cè)?，則xA, xA也都是謂詞公式；,3謂詞公式與翻譯,只有按-所求得的那些公式才是謂詞公式（謂詞公式又簡(jiǎn)稱“公式”）。 例1：任何整數(shù)或是正的，或是負(fù)的。解：設(shè)：I(x): x是整數(shù)； R1(x)：x

8、是正數(shù)；R2(x)：x是負(fù)數(shù)。 此句可寫成：x(I(x)(R1(x) R2(x) )。 例2：試將蘇格拉底論證符號(hào)化：“所有的人總是要死的。因?yàn)樘K格拉底是人，所以蘇格拉底是要死的。”解：設(shè)M(x)：x是人；D(x)：x是要死的； M(s)：蘇格拉底是人；D(s)：蘇格拉底是要死的。,3謂詞公式與翻譯,寫成符號(hào)形式： x(M(x) D(x)， M(s) D(s) 2.由于對(duì)個(gè)體描述性質(zhì)的刻劃深度不同，可翻譯成不同形式的謂詞公式。,4變?cè)募s束,1.轄域：緊接在量詞后面括號(hào)內(nèi)的謂詞公式。 例： xP(x) , x(P(x) Q(x) 。 若量詞后括號(hào)內(nèi)為原子謂詞公式，則括號(hào)可以省去。 2.自由變?cè)?/p>

9、與約束變?cè)s束變?cè)涸诹吭~的轄域內(nèi)，且與量詞下標(biāo)相同的變?cè)?自由變?cè)寒?dāng)且僅當(dāng)不受量詞的約束。 例： xP(x,y) , x(P(x) y(P(x,y) 。,4變?cè)募s束,3.約束變?cè)母拿?guī)則任何謂詞公式對(duì)約束變?cè)梢愿拿?我們認(rèn)為xP(x,y)和zP(z,y)是一等價(jià)的謂詞公式，但是需注意，不能用同一變?cè)ケ硎就恢^詞公式中的二個(gè)變?cè)?。例如?yP(y,y)是不正確的。 下面介紹約束變?cè)母拿?guī)則：（a）在改名中要把公式中所有相同的約束變?cè)客瑫r(shí)改掉；（b）改名時(shí)所用的變?cè)?hào)在量詞轄域內(nèi)未出現(xiàn)的。,4變?cè)募s束,例： xP(x) yR(x,y)可改寫成xP(x) zR(x,z) ，

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

11、是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ī)則：對(duì)公式中的自由變?cè)母慕凶龃搿?(a)對(duì)公式中出現(xiàn)該自由變?cè)拿恳惶庍M(jìn)行代入， (b)用以代入的變?cè)c原公式中所有變?cè)拿Q不能相同。,4變?cè)募s束,6.個(gè)體域（論述域，客體域）:用特定的集合表示的被約束變?cè)娜≈捣秶?(1)個(gè)體域不同，則表示同一命題的謂詞公式的形式不同。例：“所有的人必死?！绷頓(x)，x是要死的。 下面給出不同的個(gè)體域來討論： ()個(gè)體域?yàn)椋喝祟悾?則可寫成xD(x)； ()個(gè)體域?yàn)槿我庥颍ㄈ倐€(gè)體域）

12、，則人必須首先從任意域中分離出來， 設(shè)M(x)，x是人，稱M(x)為特性謂詞。命題可寫成 x(M(x) D(x),4變?cè)募s束,（2）個(gè)體域不同，則表示同一命題的值不同。Q(x): x5,（3）對(duì)于同一個(gè)體域，用不同的量詞時(shí)，特性謂詞加入的方法不同。 對(duì)于全稱量詞，其特性謂詞以前件的方式加入； 對(duì)于存在量詞，其特性謂詞以與的形式加入。,4變?cè)募s束,例：設(shè)個(gè)體域?yàn)? 白虎（白貓），黃咪（黃貓）， 同時(shí)令C(x)：x是貓（特性謂詞）；B(x)：x是黑色的；A(x)：x是動(dòng)物。 （）描述命題：“所有的貓都是動(dòng)物”。 即： x(C(x) A(x)（T）（真命題） 寫成x(C(x) A(x) （F）則

13、為假命題了。 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變?cè)募s束,7.量詞對(duì)變?cè)募s束，往往與量詞的次序有關(guān)。 例： yx(xy-2)表示任何y均有x，使得xy-2。,5謂詞演算的 等價(jià)式與蘊(yùn)含式,基本定義 定義A，B為二個(gè)謂詞公式，E為它們共同個(gè)體域，若對(duì)A和B的任一組變?cè)M(jìn)行賦值，使得A和B的值相同，則稱A和B遍及E是互為等價(jià)的，記為AB或 A,E,B,定義給定謂詞公式A，E是A的個(gè)體域。若給A中客體變?cè)概蒃中的每一個(gè)客體名稱

14、所得命題的值均為真，則稱A在E中是永真的。若E為任意域則稱A是永真的。,5謂詞演算的 等價(jià)式與蘊(yùn)含式,定義給定謂詞公式A，E是A的個(gè)體域。若給A中客體變?cè)概蒃中每一個(gè)客體名稱，在E中存在一些客體名稱，使得指派后的真值為“T”，則A稱是可滿足的。 定義若給A中客體變?cè)概蓚€(gè)體域中任一客體名稱，使命題的值均為“F”，則稱A是永假的。 1.不含量詞的謂詞公式的永真式 : 只要用原子謂詞公式去代命題公式的永真式中的原子命題變?cè)?，則在第一章中永真蘊(yùn)含式和等價(jià)公式均可變成謂詞演算中的永真式：,5謂詞演算的 等價(jià)式與蘊(yùn)含式,命題邏輯 謂詞邏輯 (x)(x) (x)(x)(x) . . . . (x)(x)

15、 (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) A(a2) A(an) xA(x) A(a1)A(a2) A(an) 上例說明： 若個(gè)體域是有限的，則可省掉量詞。 若個(gè)體域是無(wú)限的，則可將上述概念推廣從而省去量詞，不過要注意這是由無(wú)限項(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) 下面分

16、類介紹在謂詞公式中含有量詞的等價(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,an,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

17、(x) x(N(x)E(x) x (N(x) E(x),5謂詞演算的 等價(jià)式與蘊(yùn)含式,結(jié)論：對(duì)于非量化命題的否定只需將動(dòng)詞否定，而對(duì)于量化命題的否定不但對(duì)動(dòng)詞進(jìn)行否定而且對(duì)量詞同時(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為不含有變?cè)娜魏沃^詞公式,5謂詞演算的 等價(jià)式與蘊(yùn)含式,證明E27(Q6)，設(shè)個(gè)體域?yàn)椋?S=a1,a2,an xA(x)

18、P(A(a1) A(a2) A(an) P (A(a1)P)(A(a2)P) (A(an) P ) x(A(x) P) E30 (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

19、（3）量詞分配律 E24(Q10) x(A(x)B(x) xA(x) xB(x) E23 (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

20、(an)B(an) (A(a1) A(an) (B(a1) 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 xP(x) xP(x) x

21、P P xP P (P為不含x變?cè)?Y是個(gè)體域中任一元素,5謂詞演算的 等價(jià)式與蘊(yùn)含式,（5）含有多個(gè)量詞的永真式：（）量詞出現(xiàn)的次序直接關(guān)系到命題的含義： “xy”表示：“無(wú)論選定一個(gè)什么樣的x值總能找到一個(gè)y能使x和y” “yx”表示：“只選取一個(gè)y值，以致無(wú)論怎樣選定一個(gè)x，能夠使y和x” 下面列出對(duì)應(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(a1, bn) (P(an, b1) P(an, bn) yxP(x

22、,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) ) (P(i,0) P(i,1) P(i,j) ) (P(0,0) P(1,0) P(i,0) ) (P(0,1)

23、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à)式和永真蘊(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)

24、xyP(x,y) yxP(x,y) yxP(x,y) xyP(x,y) xyP(x,y) yxP(x,y) （6）謂詞公式的對(duì)偶式 定義 在一個(gè)謂詞公式A中（其中不出現(xiàn),詞）把公式A中 , , F, T, , , 變?yōu)楣紸*中 , , T, F, , , 則稱A*是A的對(duì)偶式。 定理 若謂詞公式A B，則A* B* ；若謂詞公式A B ，則B* A* （ 這里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è)公式，如果量詞均非否定

25、地在全式的開頭，它們的作用域延伸到整個(gè)公式的末尾，則稱此公式叫前束范式。 例： xyz( Q(x,y) R(z) (前束范式) 定理 任何一個(gè)謂詞公式均和一個(gè)前束范式等價(jià)。證明：利用量詞轉(zhuǎn)換把深入到原子謂詞公式前, 利用約束變?cè)母拿?guī)則， 利用量詞轄域的擴(kuò)張收縮律,把量詞移到全式的最前面，這樣一定可得到等價(jià)的前束范式。,6 前束范式,例： 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.含有量詞的特殊永真式 定

26、義 設(shè)A(x)是一個(gè)謂詞公式，x是其中的自由變?cè)?，若把y代入到A(x)里而不會(huì)產(chǎn)生變?cè)男碌募s束出現(xiàn)，則稱A(x)對(duì)于y是自由的。 例：下面A(x)對(duì)于y是自由的： A(x) zP(z) Q(x,z),這里x為自由變?cè)?若用y去取代A(x)中的x, A(y) zP(z) Q(y,z),這里y也仍為自由變?cè)?7 謂詞演算的推理理論,下面A(x)對(duì)于y不是自由的： A(x) y(S(x) S(y), x為自由變?cè)?若用y代入A(x)的x中去得： A(y) y(S(y) S(y) ，y變?yōu)榧s束變?cè)耍a(chǎn)生了新的約束出現(xiàn)。 如有必要代入y，則應(yīng)先將式中的約束變?cè)獃改名。 z(S(x)S(z)然后代

27、入y z(S(y)S(z)y仍為自由變?cè)?歸結(jié)： 判定A(x)對(duì)于y是自由的，只要看公式A(x)中y, y的轄域內(nèi)有沒有x的自由出現(xiàn)就行：若有x的自由出現(xiàn)則A(x)對(duì)于y不是自由的，若無(wú)的x自由出現(xiàn)則一定可以肯定A(x)對(duì)于y是自由的。,7 謂詞演算的推理理論,下面分別介紹四個(gè)推理規(guī)則 （1）全稱指定規(guī)則（US規(guī)則）。如果對(duì)個(gè)體域中所有客體x, A(x)成立，則對(duì)個(gè)體域中某個(gè)任意客體c， A(c) 成立。該規(guī)則表示成： xA(x) A(c) (x,c個(gè)體域) （2）全稱推廣規(guī)則（UG規(guī)則） 如果能夠證明對(duì)個(gè)體域中每一個(gè)客體c，命題A(c) 都成立，則可得到結(jié)論xA(x) 成立。該規(guī)則表示成：

28、 A(x) xA(x),7 謂詞演算的推理理論,（3）存在指定規(guī)則（ES規(guī)則）如果對(duì)于個(gè)體域中某些客體A(x)成立，則必有某個(gè)特定的客體c，使A(c)成立。該規(guī)則表示成： xA(x) A(c) 例：x的個(gè)體域?yàn)镮=整數(shù)，P(x):x是偶數(shù)，Q(x): x是奇數(shù)。 xP(x) xQ(x) T 但 P(c) Q(c) F,7 謂詞演算的推理理論,（4）存在推廣規(guī)則（EG規(guī)則） 如果對(duì)個(gè)體域中某個(gè)特定客體c，有A(c) 成立，則在個(gè)體域中，必存在x，使A(x)成立。該規(guī)則表示成： A(c) xA(x) 2 推論規(guī)則及使用說明 命題邏輯中的P,T,CP規(guī)則和簡(jiǎn)接證明法，都可以引用到謂詞邏輯的推論規(guī)則中

29、來，不過要注意對(duì)量詞做適當(dāng)處理， 其方法是：用US,ES在推導(dǎo)中去掉量詞，用UG,EG使結(jié)論量化。,7謂詞演算的推理理論,規(guī)則使用說明：（1）在使用ES,US時(shí)一定要是前束范式（2）推導(dǎo)中連續(xù)使用US規(guī)則可用相同變?cè)?xP(x) P(y), xQ(x) Q(y), （3）推導(dǎo)中既ES用，又用US， 則必須先用ES ，后用US方可取相同變?cè)粗恍小?xP(x) P(y) xQ(x) Q(y) （4）推導(dǎo)中連續(xù)使用ES規(guī)則時(shí)，使用一次更改一個(gè)變?cè)?7謂詞演算的推理理論,例：證明蘇格拉底論證x(M(x)D(x)M(s) D(s) (1) M(s) P (2) x(M(x)D(x) P (3)

30、M(s)D(s) US (4) D(s) T 例：證： x(H(x)M(x) , xH(x) xM(x),7謂詞演算的推理理論,(1) xH(x) P (2) 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)

31、Q(x), xP(x) xQ(x) (1) xQ(x) 假設(shè)前提 (2) xQ(x) T (3) Q(c)US (4) xP(x) 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

32、 P(x)UG 在使用US,ES,UG,EG這四條規(guī)則時(shí),要注意嚴(yán)格按照它們的規(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

33、,y) M(y)T(10) (12)(S(b,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)

34、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)可能有不同的符號(hào)化形式，同時(shí)也可能

35、有不同的真值，因而在將一個(gè)命題符號(hào)化之前，必須弄清個(gè)體域。 (2)在將命題符號(hào)化時(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à)式。會(huì)用約束變?cè)妥杂勺冊(cè)獡Q名規(guī)則進(jìn)行等價(jià)演算，求出給定公式的前束范式。 (4)在謂詞演算的推理證明中，要特別注意US，UG，ES，EG規(guī)則成立的條件。,例題選講,例1.符號(hào)化下列命題： (1)沒有不犯錯(cuò)誤的人； (2)發(fā)光的不都是金子； (3

36、)在南京高校學(xué)習(xí)的學(xué)生，未必都是南京籍的學(xué)生。 解： (1)設(shè)M(x)： x是人。 Q(x)：x犯錯(cuò)誤。 本題符號(hào)化為： 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(x)：x是南京籍的人。 則(x)(S(x)L(x)H(x)G(x) S(x),例題選講,例2.寫出x(F(x)G(x

37、)(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),