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

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

2、 B “所以蘇格拉底是要死的。” C,1 謂詞的概念與表示法,1.謂詞： 定義：用以刻劃客體的性質(zhì)或關系的即是謂詞。 我們可把陳述句分解為二部分： 主語（名詞，代詞）和謂語（動詞）。 例：張華是學生，李明是學生。則可把它表示成： H:表示“是學生”，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ù)與量詞,1. 命題函數(shù) 客體在謂詞表達式中可以是任意的名詞。例：C“總是要死的。” j：張三；t：老虎；e：桌子。 則C(j), C(t), C(e)均表達了命題。 在上面的例子中，C：表示“總是要死的”；x：表示變元（客體變元），則C(x)表示“x總是要死的”，則稱C(x)為命題函數(shù)。 定義由一個謂詞字母和一個非空的客體變元的集合所組成的表達式，稱為簡單命題函數(shù)。,2 命題函數(shù)與

4、量詞,討論定義：（a）當簡單命題函數(shù)僅有一個客體變元時，稱為一元簡單命題函數(shù)；（b）若用任何客體去取代客體變元之后，則命題函數(shù)就變?yōu)槊}；（c）命題函數(shù)中客體變元的取值范圍稱為個體域（論述域）。 例：P(x)表示x是質(zhì)數(shù)。這是一個命題函數(shù)。 其值取決于個體域。 可以將命題函數(shù)命題，有兩種方法：,2 命題函數(shù)與量詞,a)將x取定一個值。如：P(4)，P(5) b)將謂詞量化。如：xP(x)，xP(x) 個體域的給定形式有二種： 具體給定。 如：j, e, t 全總個體域任意域：所有的個體從該域中取得。,2 命題函數(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ù)與量詞,例：將“對于所有的x和任何的y，如果x高于y，那么y不高于x”寫成命題表達形式。解： x y(G(x,y) G(y,x)) G(x,y)：x高于y （2）存在量詞“”為存在量詞符號，讀作“存在一個”，“對于一些”，“對于某些”，“至少存在一個”，“這里存在著這樣的”等等。 “”表達式的讀法： x A(x

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

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

8、。 例1：任何整數(shù)或是正的，或是負的。解：設：I(x): x是整數(shù)； R1(x)：x是正數(shù)；R2(x)：x是負數(shù)。 此句可寫成：x(I(x)(R1(x) R2(x) )。 例2：試將蘇格拉底論證符號化：“所有的人總是要死的。因為蘇格拉底是人，所以蘇格拉底是要死的。”解：設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(x)

9、, x(P(x) Q(x)) 。 若量詞后括號內(nèi)為原子謂詞公式，則括號可以省去。 2.自由變元與約束變元約束變元：在量詞的轄域內(nèi)，且與量詞下標相同的變元。 自由變元：當且僅當不受量詞的約束。 例： xP(x,y) , x(P(x) y(P(x,y)) 。,4變元的約束,3.約束變元的改名規(guī)則任何謂詞公式對約束變元可以改名。 我們認為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：“沒有不犯錯的人。”解：設F(x)為“x犯錯誤”，M(x)為“x是人”（特性謂詞）。 可把

11、此命題寫成： (x(M(x) F(x))) x(M(x)F(x)) 例2：“x是y的外祖父” “x是z的父親且z是y的母親”設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)該自由變元的每一處進行代入， (b)用以代入的變元與原公式中所有變元的名稱不能相同。,4變元的約束,6.個體域（論述域，客體域）:用特定的集合表示的被約束變元的取值范圍。 (1)個體域不同，則表示同一命題的謂詞公式的形式不同。例：“所有的人必死?！绷?/p>

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

13、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 TT,4變元的約束,7.量詞對變元的約束，往往與量詞的次序有關。 例： yx(x

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

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

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

17、n,5謂詞演算的 等價式與蘊含式,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ù)不是偶數(shù) x(N(x)E(x))x(N(x)E(x)) x(N(x)E(x)) x (N(x) E(x)),5謂詞演算的 等價式與蘊含式,結論：對于非量化命題的否定只需將動詞否定，而對于量化命題的否定

18、不但對動詞進行否定而且對量詞同時進行否定，其方法是： x的否定變?yōu)閤 ， x的否定變?yōu)閤 。 （2） 量詞轄域的擴張及其收縮律 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謂詞演算的 等價式與蘊含式,證明E27(Q6)，設個體域為： 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) ，設個體域為： S=a1,a2,an x(A(x)B) (A(a1)B) (A(an)B) (A(a1) B) (A(an) B),5謂詞演算的 等價式與蘊含式, (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謂詞演算的 等價式與蘊含式,證明E24(Q10)和I19(Q19) ，設個體域為： 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謂詞演算的 等價式與蘊含式, (A(a1) B(a1)) (A(an) B(an)) x(A(x) B(x)) x(A(x) B(x)) （4）量詞的添加和除去的永真蘊含式 Q1 xP(x) P(y) Q2 P(y) xP(x) Q5

22、 xP(x) xP(x) xP P xP P (P為不含x變元）,,Y是個體域中任一元素,5謂詞演算的 等價式與蘊含式,（5）含有多個量詞的永真式：（）量詞出現(xiàn)的次序直接關系到命題的含義： “xy”表示：“無論選定一個什么樣的x值總能找到一個y能使x和y” “yx”表示：“只選取一個y值，以致無論怎樣選定一個x，能夠使y和x” 下面列出對應的表達式可以看出其不同處：設x的個體域為： a1,a2,an ， y的個體域為： b1,b2,bn ，則： xyP(x,y) yP(a1,y) yP(an,y),5謂詞演算的 等價式與蘊含式, (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的個體域鞋子，P(x,y):和配成一雙鞋子。 xyP(x,y) T yxP(x,y) F,5謂詞演算的 等價式與蘊含式,（）在含有多個量詞的謂詞公式中, xy, xy的位置是可以改變的,且不影響命題的真值。 例：x,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謂詞演算的 等價式與蘊含式,同樣： xyP(x,y) yxP(x,y) （）量詞轉換律的推廣應用:把深入到謂詞公式前面去的方法。 xyzP(x,y,z) x yzP(x,y,z) xyzP(x,y,z) xyzP(x,y,z) （）兩個量詞, 所組成的謂詞公式的等價式和永真

25、蘊含式（8個） 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謂詞演算的 等價式與蘊含式,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*

26、 （ 這里A,B有同樣的個體域）。,5謂詞演算的 等價式與蘊含式,例： 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)) (前束范式) 定理 任何一個謂詞公式均和一個前束范式等價。證明：利用量詞轉換把深入到原子謂詞公式前, 利用約束變元的改名規(guī)則， 利用量詞轄域的擴張收縮律,把量詞移到全式的最前面，這樣一定可得到等價的前束范式。,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.含有量詞的特殊永真式 定義 設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(

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改名。 z(S(x)S(z))然后代入y z(S(y)S(z))y仍為自由變元。 歸結： 判定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、論,下面分別介紹四個推理規(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) 都成立，則可得到結論xA(x) 成立。該規(guī)則表示成： A(x) xA(x),7 謂詞演算的推理理論,（3）存在指定規(guī)則（ES規(guī)則）如果對于個體域中某些客體A(x)成立，則必有某個特定的客體c，使A(c)成立。該規(guī)則表示成： xA(x) A(c) 例：x的個體域為I=整數(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ī)則） 如果對個體域中某個特定客體c，有A(c) 成立，則在個體域中，必存在x，使A(x)成立。該規(guī)則表示成： A(c) xA(x) 2 推論規(guī)則及使用說明 命題邏輯中的P,T,CP規(guī)則和簡接證明法，都可以引用到謂詞邏輯的推論規(guī)則中來，不過要注意對量詞做適當處理， 其方法是：用US,ES在推導中去掉量詞，用UG,EG使結論量化。,7謂詞演算的推理理論,規(guī)則使用說明：（1）在使用ES,US時一定要是前束范式（2）推導中連續(xù)使用US規(guī)則可用相同

31、變元 xP(x) P(y), xQ(x) Q(y), （3）推導中既ES用，又用US， 則必須先用ES ，后用US方可取相同變元，反之不行。 xP(x) P(y) xQ(x) Q(y) （4）推導中連續(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

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) 假設前提 (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 例：下列結論能否從前提中推出： x (P(x)Q(x)) , Q(a) x P(x) a為x個體域中一個元素 (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ī)則時,要注意嚴格按

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謂詞演算的推理理論,例： 二個量詞的推理比較復雜： 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 三個量詞的推理過程更為復雜,第二章小結,學習第二章要注意以下幾點： (1)同一個命題在不同個體域內(nèi)

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

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