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

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

2、格拉底是要死的。” C1 謂詞的概念與表示法1.謂詞：謂詞：定義定義：用以刻劃客體的性質(zhì)或關(guān)系的即是謂詞謂詞。 我們可把陳述句分解為二部分：主語（名詞，代詞）和謂語（動(dòng)詞）。例：張華是學(xué)生，李明是學(xué)生。則可把它表示成：H:表示“是學(xué)生”，j:表示“張華”，m:表示“李明”，則可用下列符號(hào)表示上述二個(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ù)與量詞命題函數(shù)與量詞1. 命題函數(shù)命題函數(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 命題函

4、數(shù)與量詞命題函數(shù)與量詞討論定義：（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ù)與量詞命題函數(shù)與量詞a)將x取定一個(gè)值。如：P(4)，P(5)b)將謂詞量化。如：xP(x)，xP(x)個(gè)體域的給定形式有二種：具體給定。如：j, e, t全總個(gè)體域任意域：所有的個(gè)體從該域中取得。2 命題函數(shù)與量詞命題函數(shù)與量詞2.量詞量詞（1）全稱量詞“”為全稱量詞符號(hào)，讀作“

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

6、讀法： x A(x) ：存在一個(gè)x,使x是； xA(x) ：存在一個(gè)x, 使x不是； x A(x) ：不存在一個(gè)x, 使x是； xA(x) ：不存在一個(gè)x, 使x不是。2 命題函數(shù)與量詞命題函數(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中的每一

7、個(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：試將蘇格拉底論證符號(hào)化：“所有的人總是要死的。因?yàn)樘K格拉底是人，所以蘇格拉底是要死的?！苯猓涸O(shè)M(x)：x是人；D(x)：x是要死的； M(s)：蘇格拉底是人；D(s)：蘇格拉底是要死的。3謂詞公式與翻譯謂詞公式與翻譯寫成符號(hào)形式： x(M(x) D(x)， M(s) D(s)2.由于對個(gè)體描述性質(zhì)的刻劃深度不同，可翻譯成不同形式的謂詞公式。4變元的約束變元的約束1.轄域：緊接在量詞后面括號(hào)內(nèi)的謂詞公式。 例： xP(

9、x) , x(P(x) Q(x) 。 若量詞后括號(hào)內(nèi)為原子謂詞公式，則括號(hào)可以省去。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í)所用的變元符號(hào)在量詞轄

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ī)則：代入規(guī)則：對公式中的自由變元的更改叫做代入。 (a)對公式中出現(xiàn)該自由變元的每一處進(jìn)行代入， (b)用以代入的變元與原公式中所有變元的名稱不能相同。4變元的約束變元的約束6.個(gè)體域（論述域，客體域）:用特定的集合表示的被約束變元的取值范圍。(1)個(gè)體域不同，則表示同一命題的謂詞公式的形式不同。例：“所有的人必死?！绷頓(x)，x是

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

13、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）則為假命題了。 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 TT4變元的約束變元的約束7.量詞對變元的約束，往往與量詞的次序有關(guān)。例： yx(xy-2)表示任何y均有x，使得x3 ,則可寫出： xP(x)P(0) P(1) P(i) xP(x) P(0)P(1)

14、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,an 5謂詞演算的謂詞演算的 等價(jià)式與蘊(yùn)含式等價(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ù)不是偶

15、數(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à)式與蘊(yùn)含式結(jié)論：對于非量化命題的否定只需將動(dòng)詞否定，而對于量化命題的否定不但對動(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)含式等價(jià)式與

16、蘊(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) 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)含式等價(jià)

17、式與蘊(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 (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)含式等價(jià)式與蘊(yùn)含式證明E24(Q10)和I19(Q19) ，設(shè)個(gè)

18、體域?yàn)椋?S=a1,a2,anE24(Q10) x(A(x)B(x) (A(a1)B(a1) . (A(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)含式等價(jià)式與蘊(yùn)含式 (A(a1) B(a1) (A(an) B(an) x(A(x) B(x) x(A(x) B(x)（4）

19、量詞的添加和除去的永真蘊(yùn)含式 Q1 xP(x) P(y) Q2 P(y) xP(x) Q5 xP(x) xP(x) xP P xP P (P為不含x變元）Y是個(gè)體域中任一元素5謂詞演算的謂詞演算的 等價(jià)式與蘊(yùn)含式等價(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(a

20、n,y) 5謂詞演算的謂詞演算的 等價(jià)式與蘊(yùn)含式等價(jià)式與蘊(yùn)含式 (P(a1, b1) P(a1, 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) F5謂詞演算的謂詞演算的 等價(jià)式與蘊(yùn)含式等價(jià)式與蘊(yùn)含式（）在含有多個(gè)量詞的謂詞公式中, xy, xy的位置是可以改變的,且不影響命題的真值。 例：x,y的個(gè)體域?yàn)镹=0,1,2，則 xyP(x,y) yP(0,y) y

21、P(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) P(1,1) P(i,1) ) xP(x,0) xP(x,1) xP(x,j) yxP(x,y) 5謂詞演算的謂詞演算的 等價(jià)式與蘊(yùn)含式等價(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)

22、 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)含式等價(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* （ 這里A,B有同樣的

23、個(gè)體域）。5謂詞演算的謂詞演算的 等價(jià)式與蘊(yùn)含式等價(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 前束范式前束范式例：

24、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)里而不會(huì)產(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(y,z),這里y也仍為自由變元；

25、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é)歸結(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 謂詞演算的推理理論謂詞演算的推理理論下面分別介紹四個(gè)推

26、理規(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):x是偶數(shù)，Q(x): x是奇數(shù)。 xP

27、(x) xQ(x) T 但P(c) Q(c) F7 謂詞演算的推理理論謂詞演算的推理理論（4）存在推廣規(guī)則（EG規(guī)則） 如果對個(gè)體域中某個(gè)特定客體c，有A(c) 成立，則在個(gè)體域中，必存在x，使A(x)成立。該規(guī)則表示成： A(c) xA(x) 2 推論規(guī)則及使用說明推論規(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ī)則可用相同變元 xP(x

28、) 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) H(c) ES(3) x(H(x)M(x) P(4

29、) 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) P 7謂詞演算的推理理論謂詞演算的推理理論 (5) P(c) US (6

30、) 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) P7謂詞演算的推理理論謂詞演算的推理理論(3) P(a)Q(a)US(4) P(a)T(5) x P(x)UG在使用US,ES,UG,EG這四條規(guī)則時(shí),要注意嚴(yán)格按照它們的規(guī)定去使用。7謂詞演算的推理理論謂詞演算的推理理論書中例4證明：(1)x(y(S(x,y)M(y)z(

31、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,c) M(c) US(11)(13)S(b,c) M(c) T(12)(14) S(b,c) M(c) T(13)(15)y(S

32、(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) x(P(x)Q(x) R(x) P (5) x(P(x)Q(x) R(x) T7謂詞演算的推理理論謂詞演算的推理理論(6) P(w)Q(w) R(w)US(7) R(w)

33、 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) US7謂詞演算的推理理論謂詞演算的推理理論(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í)也可能有不同的真值，因而在將一個(gè)命題符號(hào)化之前，必須弄清個(gè)體域。(2)在將命題符號(hào)化時(shí)，要特別注意量詞與聯(lián)結(jié)詞的搭配。經(jīng)常的情況是全稱量詞與蘊(yùn)含詞搭配，存在量詞與合取詞搭配

34、。因此有下面兩種形式的公式：x(A(x) B(x) x(A(x) B(x) 而 x(A(x) B(x) x(A(x) B(x) 第二章小結(jié)與，與的含義完全不同。(3)記住主要的等價(jià)式。會(huì)用約束變元和自由變元換名規(guī)則進(jìn)行等價(jià)演算，求出給定公式的前束范式。(4)在謂詞演算的推理證明中，要特別注意US，UG，ES，EG規(guī)則成立的條件。 例題選講例1.符號(hào)化下列命題：(1)沒有不犯錯(cuò)誤的人；(2)發(fā)光的不都是金子；(3)在南京高校學(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)：

35、 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)(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，5P111，5P184(c)，6，7(a),(b)P231，2，6，8(c),(d)P292，3P391，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)，4P726，7P751(b)(c)P791(a)(d)，2(a)，3(b)