《離散數(shù)學(xué)左孝陵版第二章答案》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)左孝陵版第二章答案（64頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、Charter twonwelcome第二章第二章 謂詞邏輯謂詞邏輯n1 謂詞的概念與表示法n2 命題函數(shù)與量詞n3 謂詞公式與翻譯n4 變元的約束n5 謂詞演算的等價式與蘊(yùn)含式n6 前束范式n7 謂詞演算的推理理論1 謂詞的概念與表示法在研究命題邏輯中，原子命題是命題演算中最基本的單位，不再對原子命題進(jìn)行分解，這樣會產(chǎn)生二大缺點(diǎn)：（1）不能研究命題的結(jié)構(gòu)，成分和內(nèi)部邏輯的特征；（2）也不可能表達(dá)二個原子命題所具有的共同特征，甚至在命題邏輯中無法處理一些簡單又常見的推理過程。例：蘇格拉底論證是正確的，但不能用命題邏輯的推理規(guī)則推導(dǎo)出來?！八械娜丝偸且赖摹?A “蘇格拉底是人。 B “所以蘇
2、格拉底是要死的。” C1 謂詞的概念與表示法1.謂詞：謂詞：定義定義：用以刻劃客體的性質(zhì)或關(guān)系的即是謂詞謂詞。 我們可把陳述句分解為二部分：主語（名詞，代詞）和謂語（動詞）。例：張華是學(xué)生，李明是學(xué)生。則可把它表示成：H:表示“是學(xué)生”，j:表示“張華”，m:表示“李明”，則可用下列符號表示上述二個命題：H(j)，H(m)。 H作為“謂詞”（或者謂詞字母）用大寫英文字母表示，j,m為主語，稱為“客體”或稱“個體”。1 謂詞的概念與表示法（1）謂詞填式）謂詞填式：謂詞字母后填以客體所得的式子。 例：H(a, b)（2）若謂詞字母聯(lián)系著一個客體，則稱作一元謂詞一元謂詞；若謂詞字母聯(lián)系著二個客體，則
3、稱作二元謂詞二元謂詞；若謂詞字母聯(lián)系著n個客體，則稱作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ù)。定義定義由一個謂詞字母和一個非空的客體變元的集合所組成的表達(dá)式，稱為簡單命題函數(shù)。2 命題函
4、數(shù)與量詞命題函數(shù)與量詞討論定義：（a）當(dāng)簡單命題函數(shù)僅有一個客體變元時，稱為一元簡單命題函數(shù)；（b）若用任何客體去取代客體變元之后，則命題函數(shù)就變?yōu)槊}；（c）命題函數(shù)中客體變元的取值范圍稱為個體域（論述域）。 例：P(x)表示x是質(zhì)數(shù)。這是一個命題函數(shù)。其值取決于個體域?？梢詫⒚}函數(shù)命題，有兩種方法：2 命題函數(shù)與量詞命題函數(shù)與量詞a)將x取定一個值。如：P(4)，P(5)b)將謂詞量化。如：xP(x)，xP(x)個體域的給定形式有二種：具體給定。如：j, e, t全總個體域任意域：所有的個體從該域中取得。2 命題函數(shù)與量詞命題函數(shù)與量詞2.量詞量詞（1）全稱量詞“”為全稱量詞符號，讀作“
5、對于所有的”，“對任一個”，“對一切”。例：“這里所有的都是蘋果”可寫成： 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）存在量詞“”為存在量詞符號，讀作“存在一個”，“對于一些”，“對于某些”，“至少存在一個”，“這里存在著這樣的”等等?！啊北磉_(dá)式的
6、讀法： x A(x) ：存在一個x,使x是； xA(x) ：存在一個x, 使x不是； x A(x) ：不存在一個x, 使x是； xA(x) ：不存在一個x, 使x不是。2 命題函數(shù)與量詞命題函數(shù)與量詞例：（a）存在一個人； （b）某個人很聰明； （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）量化命題的真值：決定于給定的個體域給定個體域：a1an以a1an中的每一
7、個代入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時稱為零元謂詞公式。定義（謂詞公式的歸納法定義） 原子謂詞公式是謂詞公式； 若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.由于對個體描述性質(zhì)的刻劃深度不同，可翻譯成不同形式的謂詞公式。4變元的約束變元的約束1.轄域：緊接在量詞后面括號內(nèi)的謂詞公式。 例： xP(
9、x) , 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)是一等價的謂詞公式，但是需注意，不能用同一變元去表示同一謂詞公式中的二個變元。例如： yP(y,y)是不正確的。下面介紹約束變元的改名規(guī)則：（a）在改名中要把公式中所有相同的約束變元全部同時改掉；（b）改名時所用的變元符號在量詞轄
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)，則該公式是一個命題。 4變元的約束變元的約束舉例：例1：“沒有不犯錯的人?！苯猓涸O(shè)F(x)為“x犯錯誤”，M(x)為“x是人”（特性謂詞）?？砂?/p>
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.個體域（論述域，客體域）:用特定的集合表示的被約束變元的取值范圍。(1)個體域不同，則表示同一命題的謂詞公式的形式不同。例：“所有的人必死?！绷頓(x)，x是
12、要死的。下面給出不同的個體域來討論：()個體域?yàn)椋喝祟?，則可寫成xD(x)；()個體域?yàn)槿我庥颍ㄈ倐€體域），則人必須首先從任意域中分離出來，設(shè)M(x)，x是人，稱M(x)為特性謂詞。命題可寫成 x(M(x) D(x)4變元的約束變元的約束（2）個體域不同，則表示同一命題的值不同。Q(x): x5-1,0,3-3,6,215,30 xQ(x) T F FxQ(x) T T F（3）對于同一個體域，用不同的量詞時，特性謂詞加入的方法不同。 對于全稱量詞，其特性謂詞以前件的方式加入； 對于存在量詞，其特性謂詞以與的形式加入。4變元的約束變元的約束例：設(shè)個體域?yàn)? 白虎（白貓），黃咪（黃貓），同時令
13、C(x)：x是貓（特性謂詞）；B(x)：x是黑色的；A(x)：x是動物。（）描述命題：“所有的貓都是動物”。 即： 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) 下面分類介紹在謂詞公式中含有量詞的等價式和永真蘊(yùn)含式。 （1）量詞轉(zhuǎn)換律： E25(Q3) xP(x) xP(x) E26(Q4) xP(x) xP(x) 下面證明：設(shè)個體域?yàn)椋?S=a1,a2,an 5謂詞演算的謂詞演算的 等價式與蘊(yùn)含式等價式與蘊(yùn)含式 xP(x) (P(a1) P(a2) P(an) P(a1) P(a2) P(an)xP(x) 下面舉例說明量化命題和非量化命題的差別:否定形式不同例： 否定下列命題： (a)上海是一個小城鎮(zhèn) A(s) (b)每一個自然數(shù)都是偶數(shù) x(N(x)E(x)上述二命題的否定為： (a)上海不是一個小城鎮(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謂詞演算的謂詞演算的 等價式與蘊(yùn)含式等價式與蘊(yùn)含式結(jié)論：對于非量化命題的否定只需將動詞否定，而對于量化命題的否定不但對動詞進(jìn)行否定而且對量詞同時進(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謂詞演算的謂詞演算的 等價式與蘊(yùn)含式等價式與
16、蘊(yùn)含式證明E27(Q6)，設(shè)個體域?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è)個體域?yàn)椋?S=a1,a2,an x(A(x)B) (A(a1)B) (A(an)B) (A(a1) B) (A(an) B) 5謂詞演算的謂詞演算的 等價式與蘊(yùn)含式等價
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謂詞演算的謂詞演算的 等價式與蘊(yùn)含式等價式與蘊(yùn)含式證明E24(Q10)和I19(Q19) ，設(shè)個
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謂詞演算的謂詞演算的 等價式與蘊(yùn)含式等價式與蘊(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是個體域中任一元素5謂詞演算的謂詞演算的 等價式與蘊(yùn)含式等價式與蘊(yùn)含式（5）含有多個量詞的永真式：（）量詞出現(xiàn)的次序直接關(guān)系到命題的含義： “xy”表示：“無論選定一個什么樣的x值總能找到一個y能使x和y” “yx”表示：“只選取一個y值，以致無論怎樣選定一個x，能夠使y和x” 下面列出對應(yīng)的表達(dá)式可以看出其不同處：設(shè)x的個體域?yàn)椋?a1,a2,an ， y的個體域?yàn)椋?b1,b2,bn ，則： xyP(x,y) yP(a1,y) yP(a
20、n,y) 5謂詞演算的謂詞演算的 等價式與蘊(yùn)含式等價式與蘊(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的個體域鞋子，P(x,y):和配成一雙鞋子。 xyP(x,y) T yxP(x,y) F5謂詞演算的謂詞演算的 等價式與蘊(yùn)含式等價式與蘊(yùn)含式（）在含有多個量詞的謂詞公式中, xy, xy的位置是可以改變的,且不影響命題的真值。 例：x,y的個體域?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謂詞演算的謂詞演算的 等價式與蘊(yùn)含式等價式與蘊(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) （）兩個量詞, 所組成的謂詞公式的等價式和永真蘊(yùn)含式（8個） 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謂詞演算的謂詞演算的 等價式與蘊(yùn)含式等價式與蘊(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）謂詞公式的對偶式定義定義 在一個謂詞公式A中（其中不出現(xiàn),詞）把公式A中 , , F, T, , , 變?yōu)楣紸*中 , , T, F, , , 則稱A*是A的對偶式。定理定理 若謂詞公式A B，則A* B* ；若謂詞公式A B ，則B* A* （ 這里A,B有同樣的
23、個體域）。5謂詞演算的謂詞演算的 等價式與蘊(yùn)含式等價式與蘊(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 前束范式前束范式定義定義一個公式，如果量詞均非否定地在全式的開頭，它們的作用域延伸到整個公式的末尾，則稱此公式叫前束范式。例： xyz( Q(x,y) R(z) (前束范式) 定理定理 任何一個謂詞公式均和一個前束范式等價。證明：利用量詞轉(zhuǎn)換把深入到原子謂詞公式前, 利用約束變元的改名規(guī)則， 利用量詞轄域的擴(kuò)張收縮律,把量詞移到全式的最前面，這樣一定可得到等價的前束范式。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)是一個謂詞公式，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(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 謂詞演算的推理理論謂詞演算的推理理論下面分別介紹四個推
26、理規(guī)則（1）全稱指定規(guī)則（US規(guī)則）。如果對個體域中所有客體x, A(x)成立，則對個體域中某個任意客體c， A(c) 成立。該規(guī)則表示成： xA(x) A(c) (x,c個體域) （2）全稱推廣規(guī)則（UG規(guī)則） 如果能夠證明對個體域中每一個客體c，命題A(c) 都成立，則可得到結(jié)論xA(x) 成立。該規(guī)則表示成： A(x) xA(x) 7 謂詞演算的推理理論謂詞演算的推理理論（3）存在指定規(guī)則（ES規(guī)則）如果對于個體域中某些客體A(x)成立，則必有某個特定的客體c，使A(c)成立。該規(guī)則表示成： xA(x) A(c) 例：x的個體域?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ī)則） 如果對個體域中某個特定客體c，有A(c) 成立，則在個體域中，必存在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時一定要是前束范式（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ī)則時，使用一次更改一個變元。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個體域中一個元素 (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ī)則時,要注意嚴(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謂詞演算的推理理論謂詞演算的推理理論例： 二個量詞的推理比較復(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 三個量詞的推理過程更為復(fù)雜第二章小結(jié)學(xué)習(xí)第二章要注意以下幾點(diǎn)：(1)同一個命題在不同個體域內(nèi)可能有不同的符號化形式，同時也可能有不同的真值，因而在將一個命題符號化之前，必須弄清個體域。(2)在將命題符號化時，要特別注意量詞與聯(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)記住主要的等價式。會用約束變元和自由變元換名規(guī)則進(jìn)行等價演算，求出給定公式的前束范式。(4)在謂詞演算的推理證明中，要特別注意US，UG，ES，EG規(guī)則成立的條件。 例題選講例1.符號化下列命題：(1)沒有不犯錯誤的人；(2)發(fā)光的不都是金子；(3)在南京高校學(xué)習(xí)的學(xué)生，未必都是南京籍的學(xué)生。解：(1)設(shè)M(x)： x是人。 Q(x)：x犯錯誤。本題符號化為： 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)
離散數(shù)學(xué)左孝陵版第二章答案
