1、1,第二篇 數(shù)理邏輯 Mathematics Logic,2,謂詞邏輯 Predicate Logic,3,問題的提出：(命題邏輯的局限性),例：蘇格拉底論斷 前提 “所有的人總是要死的” “蘇格拉底是人” 結(jié)論 “所以蘇格拉底是要死的” 命題邏輯中原子命題不可再分,P,Q,R,PQR,不是有效推理,4,例 1：小張是大學(xué)生 2：小李是大學(xué)生 Q1 ：2大于3 Q2 ：6大于4 命題邏輯無法反映不同原子命題間的內(nèi)在共性 解決問題的方法 分析原子命題，分離其主語和謂語 考慮一般和個(gè)別，全稱和存在,5,3.1謂詞的概念與表示,定義3.1.1 在原子命題中，用來刻劃一個(gè)個(gè)體的性質(zhì)或個(gè)體之間關(guān)系的成分

2、稱為謂詞，刻劃一個(gè)個(gè)體性質(zhì)的詞稱為一元謂詞；刻劃n個(gè)個(gè)體之間關(guān)系的詞稱為n元謂詞 常用大寫英文字母表示 個(gè)體 能夠獨(dú)立存在的事物 通常用小寫英文字母a、b、c、.表示個(gè)體常量 用小寫英文字母x、y、z.表示任何個(gè)體，則稱這些字母為個(gè)體變元,6,例 1 (a) 5 是質(zhì)數(shù) (b) 張明生于北京 (c) 7=32 F(x)：x是質(zhì)數(shù) G(x, y)： x生于y ，a：張明，b：北京 H(x, y, z) ：x=yz,F(5),G(a,b),H(7,3,2),變元的次序很重要,7,謂詞常量（謂詞常元） 一個(gè)字母代表一特定謂詞, 例如F代表“是質(zhì)數(shù)”, 則稱此字母為謂詞常量 謂詞變元 若字母代表任意謂

3、詞, 則稱此字母為謂詞變元 論域 個(gè)體域 謂詞命名式中個(gè)體變元的取值范圍 空集不能作為論域,8,3.2 命題函數(shù)與量詞,謂詞命名式不是命題 若謂詞是常元 個(gè)體詞是常元 謂詞命名式才成為一個(gè)命題 定義3.2.1 由一個(gè)謂詞常量，一些個(gè)體變元組成的表達(dá)式稱為簡單命題函數(shù)，表示為P(x1,x2,xn)。由一個(gè)或若干個(gè)簡單命題函數(shù)以及邏輯聯(lián)結(jié)詞組成的命題形式稱為復(fù)合命題函數(shù)，簡單命題函數(shù)和復(fù)合命題函數(shù)統(tǒng)稱為命題函數(shù) n=0時(shí) 命題變元,9,例 A(x)：x身體好 B(x)：x學(xué)習(xí)好 C(x)：x工作好 如果x身體不好，則x的學(xué)習(xí)與工作都不會好 復(fù)合命題函數(shù) A(x)(B(x)C(x),10,量詞,例

4、“所有的正整數(shù)都是素?cái)?shù)” “有些正整數(shù)是素?cái)?shù)” 假設(shè) 只有兩個(gè)正整數(shù)a和b 個(gè)體域?yàn)閍,b P(x)：x是素?cái)?shù),P(a) P(b),P(a) P(b),11,量詞,定義3.2.2 設(shè)為論域上的一個(gè)一元謂詞，則 命題x(x)的真值為，iff 對上的每一個(gè)個(gè)體a，命題(a)的真值為； 命題x(x)的真值為，iff 在上存在個(gè)體a，使得命題(a)的真值為。,12,全稱量詞,記作 表示“每個(gè)”、“任何一個(gè)”、“一切”、“所有的”、“凡是”、“任意的”等 x讀作“任意x”， “所有x”， “對一切x ” 量詞后邊的個(gè)體變元，指明對哪個(gè)個(gè)體變元量化，稱為量詞后的指導(dǎo)變元 例 所有人都是要死的 D(x)：x

5、是要死的 個(gè)體域：所有人構(gòu)成的集合 x D(x),13,存在量詞,記作 表示“有些”、“一些”、“某些”、“至少一個(gè)”等 x讀作“存在x”，“對某些x”或“至少有一x” 指導(dǎo)變元 例 有些有理數(shù)是整數(shù) (x)：x是整數(shù) 個(gè)體域：有理數(shù)集合 x(x),14,全總個(gè)體域（全總域）,含有量詞的命題的真值與論域有關(guān) 含有量詞的命題的表達(dá)式的形式與論域有關(guān) 全總個(gè)體域 宇宙間所有的個(gè)體聚集在一起所構(gòu)成的集合 約定 除特殊說明外，均使用全總個(gè)體域 對個(gè)體變化的真正取值范圍，用特性謂詞加以限制,15,例,所有的人都是要死的 有的人活百歲以上 D(x)：x是要死的 G(x) ：x活百歲以上 個(gè)體域E為全體人組

6、成的集合 x D(x) x G(x) 全總個(gè)體域 引入特性謂詞 M(x)：x是人 x(M(x) D(x) x (M(x)G(x),16,特性謂詞添加規(guī)則,對全稱量詞, 特性謂詞作為條件式之前件加入 對存在量詞, 特性謂詞作為合取項(xiàng)而加入 例 (a) 沒有不犯錯(cuò)誤的人 F(x)：x犯錯(cuò)誤 M(x)：x是人 x (M(x)F(x) (b) 凡是實(shí)數(shù), 不是大于零就是等于零或小于零 R(x)：x是實(shí)數(shù) L(x, y)：xy E (x, y) ： x = y S(x, y)：x y x(R(x) L(x, 0) E (x, 0) S (x, 0),17,3.3 謂詞演算的合式公式,個(gè)體函數(shù)（函詞） 例

7、 小王比他的父親高 T(x，y)：x比y高 a：小王 b：小王的父親 T(a，b) 無法顯示個(gè)體之間的依賴關(guān)系 定義函詞 f(x)=x的父親 T(a， f(a),18,函詞與謂詞的區(qū)別 函詞中的個(gè)體變元用個(gè)體帶入后的結(jié)果依然是個(gè)體 f(a)=小王的父親 謂詞中的個(gè)體變元用確定的個(gè)體帶入后就變成了命題 M(x)：x是人 M(a)：小王是人 函詞是論域到論域的映射 f : DD 謂詞是從論域到T,F的映射 M : D T,F,19,項(xiàng)和原子公式,定義3.3.1 項(xiàng)(item) 表示個(gè)體 定義 個(gè)體常量是項(xiàng) 個(gè)體變元是項(xiàng) 如果f是一個(gè)n(n1)元函詞，其t1, t2, tn都是項(xiàng)，則f(t1, t2

8、, tn)是項(xiàng) 例 a, b, c x, y, z f (x), g (a, f (y),20,定義3.3.2 原子公式(atom) 定義 若P是一個(gè)n元謂詞，且t1,t2,tn是項(xiàng)，則P(t1,t2,tn)是原子 命題詞也是原子(n=0) 例 P, Q (x), A (x, f (x), B (x, y, a),21,謂詞演算的合式公式(Wff),也叫謂詞公式，簡稱公式 定義3.3.3 (1)原子公式是合式公式 (2)如果A、B是合式公式，則A、(AB)、(AB)、(AB)、(AB)都是合式公式 (3)如果A是合式公式，x是中的任何個(gè)體變元，則x和x也是合式公式 (4)有限次地使用規(guī)則(1)

9、至(3)求得的公式是合式公式 例 P，(PQ)，(Q(x)P)，x(A(x)B(x)，xC(x),22,命題符號化,謂詞邏輯中比較復(fù)雜 命題的符號表達(dá)式與論域有關(guān)系 例：每個(gè)自然數(shù)都是整數(shù) 論域D=N I(x)：x是整數(shù) x I (x) 論域?yàn)槿倐€(gè)體域 特性謂詞N(x)：x是自然數(shù) x(N(x)I(x),23,例：將下列命題符號化,(1)所有大學(xué)生都喜歡一些歌星。 S(x)：x是大學(xué)生，X(x)：x是歌星，L(x,y)：x喜歡y x(S(x)y(X(y)L(x,y) (2)發(fā)光的不都是金子。 P(x)：x發(fā)光，G(x)：x是金子 x(P(x)G(x) 或者x(P(x)G(x) (3)不是所有

10、的自然數(shù)都是偶數(shù)。 N(x)：x是自然數(shù)，E(x)：x是偶數(shù) x(N(x)E(x) 或者x(N(x)E(x),24,(4)某些人對食物過敏 F(x, y)：x對y過敏，M(x)：x是人， G(x)：x是食物 xy(M(x)G(y)F(x,y) (5)每個(gè)人都有些缺點(diǎn) H(x, y)：x有y，M(x)：x是人， S(x)：x是缺點(diǎn) x(M(x) y(S(y)H(x,y) (6)盡管有人聰明, 但未必人人聰明 M(x)：x是人， S(x)：x聰明 x(M(x)S(x)x(M(x)S(x),25,練習(xí)：將下列命題符號化,所有教練員都是運(yùn)動(dòng)員；(J(x)，L(x) 某些運(yùn)動(dòng)員是大學(xué)生；(S(x) 某些

11、教練員是年老的，但是健壯的；(O(x)，V(x) 金教練雖不年老，但不健壯；(j) 不是所有運(yùn)動(dòng)員都是教練員； 某些大學(xué)生運(yùn)動(dòng)員是國家選手；(C(x) 沒有一個(gè)國家選手不是健壯的； 所有老的國家選手都是運(yùn)動(dòng)員； 沒有一位女同志既是國家選手又是家庭婦女；(W(x)，H(x) 有些女同志既是教練員又是國家選手； 所有運(yùn)動(dòng)員都?xì)J佩某些教練員；(A(x, y) 有些大學(xué)生不欽佩運(yùn)動(dòng)員。,26,練習(xí)參考答案,x(J(x)L(x) x(L(x)S(x) x(J(x)O(x)V(x) J(j)O(j)V(j) x(L(x)J(x) 或者 x(L(x)J(x) x(S(x)L(x)C(x) x(C(x)V(x

12、) 或者 x(C(x)V(x) x(C(x)O(x)L(x) x(W(x)C(x)H(x) x(W(x)J(x)C(x) x(L(x)y(J(y)A(x,y) x(S(x)y(L(y)A(x,y),27,幾個(gè)特別的例子,(1) 如果明天下雨，則某些人將被淋濕,不是個(gè)體,定義命題詞P：明天下雨， M(x)：x是人，W(x)：x將被淋濕 P x(M(x) W(x),(2) 有且僅有一個(gè)偶素?cái)?shù),P(x)：x是偶素?cái)?shù) x(P(x), y(P(y)x=y),或者,x(P(x)y(xyP(y),(3) 頂多只有一臺機(jī)器是好的 P(x)：x是好機(jī)器,用符號 !xP(x) 表示有且僅有一個(gè)個(gè)體滿足P,xy(P

13、(x)P(y)x=y),用符號 !xP(x) 表示頂多有一個(gè)個(gè)體滿足P,28,(4) 如果人都愛美，則漂亮衣服有銷路 M(x)：x是人，L(x)：x愛美， C(x)：x是衣服， B(x)：x是漂亮的，S(x)：x有銷路,x(M(x)L(x),x(C(x)B(x) S(x),問題一：前后兩個(gè)x是否指同一個(gè)個(gè)體？ 答：前后兩個(gè)x不是同一個(gè)個(gè)體 問題二：若寫成如下形式是否正確？ x(M(x)L(x) y(C(y)B(y) S(y) 答：是正確的，顯然 x(M(x)L(x) x(C(x)B(x) S(x) x(M(x)L(x) y(C(y)B(y) S(y),29,3.4 變元的約束,量詞的作用域(轄

14、域) 定義：在謂詞公式中，量詞的作用范圍稱之為量詞的作用域，也叫量詞的轄域。 例 xA(x) x的轄域?yàn)锳(x) x(P(x)Q(x)yR(x,y) x的轄域是(P(x)Q(x)yR(x,y) y的轄域?yàn)镽(x,y) xyz(A(x,y)B(x,y,z)C(t),x的轄域,z的轄域,y的轄域,自由變元,30,一般地， 如果量詞后邊只是一個(gè)原子謂詞公式時(shí)，該量詞的轄域就是此原子謂詞公式。 如果量詞后邊是括號，則此括號所表示的區(qū)域就是該量詞的轄域。 如果多個(gè)量詞緊挨著出現(xiàn)，則后邊的量詞及其轄域就是前邊量詞的轄域。,31,約束變元 如果個(gè)體變元x在x或者x的轄域內(nèi)，則稱x在此轄域內(nèi)約束出現(xiàn)，并稱x在

15、此轄域內(nèi)是約束變元 自由變元 如果個(gè)體變元x不在任何量詞的轄域內(nèi)，則稱x是自由出現(xiàn)，并稱x是自由變元 例 x(F(x,y)yP(y)Q(z) F(x,y)中的x和P(y)中的y是約束變元 而F(x,y)中的y和Q(z)中的z是自由變元,32,例：指出下列各公式中的量詞轄域及自由變元和約束變元,xy(P(x)Q(y)zR(z) x的轄域y(P(x)Q(y) y的轄域P(x)Q(y) z的轄域R(z) x(P(x,y)yQ(x,y,z)S(x,z) x的轄域P(x,y)yQ(x,y,z) 其中x是約束變元 y是自由變元 y的轄域Q(x,y,z) 其中y是約束變元 x, z是自由變元 S(x，z)中

16、x，z是自由變元,33,對約束變元和自由變元的幾點(diǎn)說明,約束變元用什么符號表示無關(guān)緊要 xA(x)與yA(y)是一樣的 一個(gè)謂詞公式如果無自由變元，它就表示一個(gè)命題 例：A(x)表示x是個(gè)大學(xué)生 xA(x)或者xA(x)是命題 一個(gè)n元謂詞P(x1,x2,xn)，若在前邊添加k個(gè)量詞，使其中的 k個(gè)個(gè)體變元變成約束變元，則變成n-k元謂詞函數(shù),34,P(x,y,z)表示x+yz 假設(shè)論域是整數(shù)集，xyP(x,y,z)表示？ “任意給定的整數(shù)x，都可以找到整數(shù)y，使得x+yz” 。 令z=1，則xyP(x,y,1)表示？ “任意給定的整數(shù)x，都可以找到整數(shù)y，使得x+y1”,。,例,35,不同個(gè)

17、體以相同的符號出現(xiàn)容易產(chǎn)生混淆 例 x(F(x,y)yP(y)Q(z) 約束變元的換名規(guī)則： 對約束變元可以更改名稱，改名的范圍是：量詞后的指導(dǎo)變元以及該量詞的轄域內(nèi)此個(gè)體變元出現(xiàn)的各處同時(shí)換名。 改名后用的個(gè)體變元名稱，不能與該量詞的轄域內(nèi)的其它變元名稱相同。,約束變元換名,36,x(P(x)Q(x,y)(R(x)A(x) x以兩種形式出現(xiàn) 對x換名 z(P(z)Q(z,y)(R(x)A(x) x(P(x,y)yQ(x,y,z)S(x,y) 對x和y換名 u(P(u,v)vQ(u,v,z)S(x,y) 錯(cuò)誤 u(P(u,y)zQ(u,z,z)S(x,y) 錯(cuò)誤 u(P(u,y)vQ(u,v,

18、z)S(x,y) 正確,例,37,自由變元換名,自由變元也可以換名 此換名叫代入 自由變元的代入規(guī)則： 對謂詞公式中的自由變元可以作代入。代入時(shí)需要對公式中出現(xiàn)該變元的每一處，同時(shí)作代入 代入后的變元名稱要與公式中的其它變元名稱不同,38,例,x(P(x)Q(x,y)(R(x)A(x) 用z代替自由變元x x(P(x)Q(x,y)(R(z)A(z) x(P(x,y)yQ(x,y,z)S(x,z) 用w和t分別代自由變元x和y x(P(x,t)yQ(x,y,z)S(w,z),39,3.5 謂詞公式的解釋,定義3.5.1 對謂詞公式的解釋包括以下幾點(diǎn)： 指定一個(gè)論域D 對A中出現(xiàn)的每一個(gè)n元函數(shù)，

19、指定一個(gè)D上的 n元個(gè)體函數(shù)常量 對A中出現(xiàn)的每一個(gè)n元謂詞，指定一個(gè)D上的n元謂詞常量 對A中出現(xiàn)的每一個(gè)個(gè)體常量及自由變元，指定D中的一個(gè)個(gè)體常量 對A中出現(xiàn)的每一個(gè)命題變元P，指派一個(gè)真值T或F 由此得到一個(gè)命題AI，稱AI的真值為合適公式A在解釋I 下的真值,40,例,取解釋I如下： D=1,2, 定義D上的二元謂詞P真值為 P(1,1): T； P(1,2): F； P(2,1):F； P(2,2): T 則xyP(x,y)和yxP(x,y) 在解釋I下的真值分別為?,41,xyP(x,y),T,T,F,F,T,T,T,42,yxP(x,y),T,F,F,F,F,F,T,43,例,取

20、解釋I如下： D=1,2, 令 a:1, f(1)=2, f(2)=1 定義D上的謂詞P和Q為 P(1): F； P(2): T； Q(1,1):T； Q(1,2):T； Q(2,1):F； Q(2,2): F 求謂詞公式x(P(x)Q(f(x),a)在解釋I下的真值,P(1)Q(f(1),1),P(2)Q(f(2),1),T,T,x(P(x)Q(f(x),a)在解釋I下的真值為T,44,3.6 謂詞公式的永真式,定義 給定謂詞公式A，E是其論域，如果在任何解釋下公式A的真值都為真，則稱公式A在論域E上是永真式。如果不論對什么論域E，都使得公式A為永真式，則稱A為永真式。 例：I(x)：x是整

21、數(shù)，論域E為自然數(shù)集合 I(x)在E上是永真式 I(x) I(x)是與論域無關(guān)的永真式 謂詞公式的永假式 謂詞公式的可滿足式,45,例：試說明以下公式的類型,xA(x)A(y) xA(x)A(y) A(x) (A(x) ：x+6=5) x( A(x) A(x) x (A(x)B(x) xA(x)xB(x) x (A(x)B(x) xA(x) xB(x),永真式,可滿足式,可滿足式,永假式,46,5. x (A(x)B(x) xA(x)xB(x) 解 取解釋I如下: D=1,2,A(1)B(1),A(1) A(2) B(1) B(2),T F F T,T,A(2)B(2),T,x (A(x)B(

22、x),T,x A(x),F,x B(x),F,則在 I 下,x A(x) x B(x),F,所以在 I 下x (A(x)B(x) xA(x)xB(x)的真值為假，該式不是永真式,47,6. x (A(x)B(x) xA(x)xB(x) 解 取解釋I如下: D=1,2,或,x A(x) x B(x),T,x (A(x)B(x),F,所以在 I 下x (A(x)B(x) xA(x)xB(x)的真值為假，該式不是永真式,48,命題演算的推廣,定理3.6.1(代入定理) 設(shè)A是命題邏輯中的永真式，則用謂詞邏輯的合式公式代替A中的某些命題變元得到的代入實(shí)例也是永真式；如果A是永假式，則上述代入實(shí)例也是永

23、假式 例 A(x)A(x)B(x) PPQ x(A(x)B(x)x(A(x)B(x) PQPQ (xA(x)xB(x)xA(x)xB(x) 摩根律,49,量詞與聯(lián)詞的關(guān)系,定理3.6.2 x(x) x(x)； x(x) x(x)。 證明 給定公式x(x)x(x)在論域上的解釋。若x(x)在下為真，即x(x)為假，那么中的每一個(gè)個(gè)體a皆使(a)為假，即(a)為真，所以x(x)為真。另一方面，若x(x)為真，則中的每一個(gè)個(gè)體a皆使(a)為真，即(a)為假，所以x(x)為假，即x(x)為真。 利用的結(jié)論，我們有： x(x) x(x) x(x) x(x),50,例,xyz(x+z=y) xyz(x+z

24、=y) xyz(x+z=y) xy z(x+z=y) xy z(x+zy),51,定理3.6.3 xA(x)Px(A(x)P) xA(x)Px(A(x)P) xA(x)Px(A(x)P) xA(x)Px(x)P) PxA(x)x(PA(x) PxA(x)x(PA(x) xA(x)Px(A(x)P) xA(x)Px(A(x)P) P是不含個(gè)體變元x的謂詞公式,證明式1：(邏輯推證) 一方面，當(dāng)P為F時(shí)， xA(x)Px(A(x)P)xA(x) 另一方面，當(dāng)P為T時(shí)， xA(x)Px(A(x)P)T,量詞轄域的擴(kuò)張和收縮,52,定理3.6.4 x(A(x)B(x)xA(x)xB(x) x(A(x)

25、B(x)xA(x)xB(x) x(A(x)B(x)xA(x)xB(x) xA(x)xB(x)x(A(x)B(x) 證明式1： 個(gè)體域中每一個(gè)體x，使得 A(x)B(x)為真, 等價(jià)于對一切x, A(x)是真并且對一切x, B(x)是真 證明式2：由1得x( A(x) B(x)xA(x)xB(x) 即 x(A(x)B(x) (xA(x)xB(x) 故 x(A(x)B(x) xA(x)xB(x),量詞與和等聯(lián)詞的關(guān)系,53,注意：公式3和4不是等價(jià)公式，而是永真蘊(yùn)含式 例： 給定如下解釋 A(x)： x是奇數(shù) B(x)：x是偶數(shù) 則 xA(x)xB(x)為真 x(A(x)B(x) 為假 所以xA(

26、x)xB(x)不蘊(yùn)含x(A(x)B(x) 或 D=1,2 A(1): T A(2): F B(1): F B(2): T,54,證明式3 x(A(x)B(x)xA(x)xB(x) 證明：假設(shè)前件x(A(x)B(x)為真， 則論域中至少有一個(gè)個(gè)體a，使得 A(a)B(a)為真， 即A(a)和B(a)都為真， 所以有xA(x)以及xB(x)為真，得 xA(x)xB(x)為真 所以 x(A(x)B(x)xA(x)xB(x),55,證明公式4 xA(x)xB(x)x(A(x)B(x) 證明：由3得 x(A(x)B(x)xA(x)xB(x) x(A(x)B(x)xA(x)xB(x) x(A(x)B(x)

27、(xA(x)xB(x) 即xA(x)xB(x)x(A(x)B(x) 公式4得證。 特別要注意蘊(yùn)含式的方向，不要搞錯(cuò),56,xyA(x,y)yxA(x,y) xyA(x,y)yxA(x,y) yxA(x,y)xyA(x,y) xyA(x,y)xyA(x,y) yxA(x,y)xyA(x,y) xyA(x,y)yxA(x,y) yxA(x,y)xyA(x,y) xyA(x,y)yxA(x,y),多個(gè)量詞的量化次序,57,置換定理 設(shè)A(x1, x2, xn) B(x1, x2, , xn), 而A是公式C中的子公式, 將B替換C中之A不必每一處得D, 則CD。 對偶原理 在公式A B或A B中,

28、A , B僅含運(yùn)算符 , 和, 將上式中的全稱量詞與存在量詞互換, 與互換, T和F互換, 則 A* B *, B* A*,58,3.7 謂詞演算的推理理論,謂詞演算中推理的形式結(jié)構(gòu) 推理的形式結(jié)構(gòu)仍為 H1H2Hn C 若H1H2Hn C是永真式，則稱 前提H1，H2，Hn邏輯的推出結(jié)論C， 其中H1，H2，Hn和C都是謂詞公式 謂詞演算中的推理規(guī)則 命題演算中的推理規(guī)則，可在謂詞推理理論中應(yīng)用 P規(guī)則、T規(guī)則、CP規(guī)則 與量詞有關(guān)的規(guī)則,59,全稱示例規(guī)則 US (Universal Specialization),又稱全稱指定規(guī)則 作用：去掉全稱量詞 兩種形式： xA(x)A(y) xA

29、(x)A(c) 使用此規(guī)則時(shí)要注意： （1）y為任意不在A(x)中約束出現(xiàn)的個(gè)體變元； （2）c為任意的個(gè)體常元 例：設(shè)A(x,y):xy 考查xyA(x,y) 可得到結(jié)論yA(z,y) 但不能得出結(jié)論yA(y,y),60,存在示例規(guī)則ES(Existential Specification),又稱存在指定規(guī)則 作用：去掉存在量詞 形式：xA(x)A(c) 使用此規(guī)則時(shí)要注意： （1）c是使A為真的特定個(gè)體常元； （2）c不在A(x)中出現(xiàn) （3）如果A(x)中有其他自由變元出現(xiàn)，且x是隨其他自由變元變化的，那么不能使用此規(guī)則 例：設(shè)A(x,y)：xy，考查如下推理過程是否正確 xyA(x,y

30、) yA(z,y) A(z,c),61,存在推廣規(guī)則EG(Existential Generalization),作用：添加存在量詞 形式： A(c)xA(x) 使用此規(guī)則時(shí)注意： (1) c是個(gè)體域中某個(gè)確定的個(gè)體 (2) 代替c的x不能已在A(c)中出現(xiàn) 例：設(shè)A(x,y)：xy，對xyA(x,y)考查如下推理過程 A(x,c) xA(x,x) 錯(cuò)誤,62,全稱推廣規(guī)則UG(Universal Generalization),作用：添加全稱量詞 形式： A(y)xA(x) 使用此規(guī)則時(shí)注意： (1) y在A(y)中自由出現(xiàn)，且y取任何值時(shí)A均為真 (2) x不在A(y)中約束出現(xiàn) 例：設(shè)A

31、(x,y)：xy，考查如下推理過程 xA(x,y) x xA(x,x) 錯(cuò)誤,63,量詞四規(guī)則的使用限制條件,非常重要 ES, US, EG, UG四條規(guī)則都只有在量詞的作用域是整個(gè)公式的情況下才能使用 例：考察如下推理過程 xP(x)yQ(y) xP(x)Q(c) ES 或 P(z)yQ(y) US 錯(cuò)誤！,64,推理舉例,1.證明蘇格拉底的三段論。 令 M(x):x是人。D(x):x是要死的。a:蘇格拉底。 符號化為： x(M(x)D(x),M(a) D(a) x(M(x)D(x) P M(a)D(a) US M(a) P D(a) T I,65,2.所有自然數(shù)都是整數(shù)。有些數(shù)是自然數(shù)。因

32、此有些數(shù)是整數(shù)。 A(x)：x是自然數(shù)，B(x)：x是整數(shù)。 x(A(x)B(x)， xA(x) xB(x) x(A(x)B(x) P xA(x) P A(c)B(c) US A(c) ES B(c) T I xB(x) EG ,66, x(A(x)B(x) P xA(x) P A(c) ES A(c)B(c) US B(c) T I xB(x) EG,67,3. 不認(rèn)識錯(cuò)誤的人，也不能改正錯(cuò)誤。有些誠實(shí)的人改正了錯(cuò)誤。所以有些誠實(shí)的人是認(rèn)識了錯(cuò)誤的人。 設(shè)A(x):x是認(rèn)識錯(cuò)誤的人。 B(x):x改正了錯(cuò)誤。C(x):x是誠實(shí)的人。 符號化為： x(A(x)B(x)， x(C(x)B(x),

33、 x(C(x)A(x),68,x(A(x)B(x),x(C(x)B(x)x(C(x)A(x) x(C(x)B(x) P C(c)B(c) ES C(c) T I B(c) T I x(A(x)B(x)P A(c)B(c) US A(c) T I A(c) T E C(c)A(c) T I x(C(x)A(x) EG ,69,觀察以下推理過程，指出問題1：,(1) xP(x)xQ(x) P (2) xP(x) T(1)I (3) xQ(x) T(1)I (4) P(c) ES(2) (5) Q(c) ES(3) (6) P(c)Q(c) T(4)(5)I (7) x(P(x)Q(x) EG(6)

34、,滿足P的特定個(gè)體,c能滿足Q？,事實(shí)上xP(x)xQ(x) x(P(x)Q(x)不成立,70,觀察以下推理過程，指出問題2：,設(shè)D(x,y)表示“x可被y 整除” ,個(gè)體域 為 5,7 ,10 ,11 。 因?yàn)镈(5，5)和D(10,5)為真，所以xD(x,5)為真. 因?yàn)镈(7，5)和D(11,5)為假，所以xD(x,5)為假. 有以下推理過程 (1) xD(x,5) P (2) D(z,5) T(1);ES (3) xD(x,5) T(2);UG 因此，xD(x,5)xD(x,5),71,4. 一些病人喜歡所有醫(yī)生。任何病人都不喜歡庸醫(yī)。所以沒有醫(yī)生是庸醫(yī)。 設(shè): P(x):x是病人,

35、D(x):x是醫(yī)生, Q(x):x是庸醫(yī), L(x,y): x喜歡y. 符號化為： x(P(x)y(D(y)L(x,y)， x(P(x)y(Q(y)L(x,y) y(D(y)Q(y),72,x(P(x)y(D(y)L(x,y)，x(P(x)y(Q(y)L(x,y) y(D(y)Q(y) x(P(x)y(D(y)L(x,y) P P(c)y(D(y)L(c,y) ES P(c) T I y(D(y)L(c,y) T I x(P(x)y(Q(y)L(x,y) P P(c)y(Q(y)L(c,y) US y(Q(y)L(c,y) T I D(z)L(c,z) US Q(z)L(c,z) US L(c

36、,z) Q(z) T E D(z)Q(z) T I D(z)Q(z) T E (D(z)Q(z) T E y(D(y)Q(y) UG y(D(y)Q(y) T E,73,練習(xí),x(A(x)B(x),x(B(x)C(x),xC(x)xA(x) (1) x(A(x)B(x) P (2) A(c)B(c) ES (1) (3) x(B(x)C(x) P (4) B(c)C(c) US (3) (5) xC(x) P (6) C(c) US (5) (7) B(c) T (4)(6) I (8) A(c) T (2)(7) I (9) xA(x) EG (8),74,5. x(P(x)Q(x) xP(

37、x)xQ(x) xP(x) P(附加前提) x(P(x)Q(x) P P(c)Q(c) ES P(c) US Q(c) T I xQ(x) EG xP(x)xQ(x) CP,75,用反證法證明5： x(P(x)Q(x) xP(x)xQ(x) (xP(x)xQ(x) P(假設(shè)前提) (xP(x)xQ(x) T E xP(x)xQ(x) T E xP(x) T I xQ(x) T I x(P(x)Q(x) P P(c)Q(c) ES P(c) US Q(c) T I xQ(x) EG xQ(x)xQ(x) T I,76,練習(xí),分別用反證法和附加前提法證明： x(A(x)B(x) xA(x)xB(x

38、) 反證法： (1) (xA(x)xB(x) P(假設(shè)前提) (2) xA(x)xB(x) T E (3) xA(x) T I (4) xB(x) T I (5) xA(x) T(3)E (6) xB(x) T(4)E (7) A(c) ES(5) (8) B(c) US(6) (9) x(A(x)B(x) P (10) A(c)B(c) US(9) (11) B(c) T(7)(10)I (12) B(c) B(c) T(8)(11)I,77,附加前提法： (1) xA(x) P(附加) (2) x(A(x)B(x) P (3) xA(x) T(1)E (4) A(c) ES(3) (5)

39、A(c)B(c) US(2) (6) B(c) T(4)(5)I (7) xB(x) EG(6) (8) xA(x)xB(x) CP (9) xA(x)xB(x) T(8)E,78,用推理證明公式：yxA(x,y)xyA(x,y), yxA(x,y) P xA(x,c) ES A(z,c) US yA(a,y) EG xyA(x,y) UG ,79,推理注意事項(xiàng)：,注意使用ES、US、EG、UG的限制條件 對于同一個(gè)個(gè)體變元，既有帶也有帶的前提，去量詞時(shí)，應(yīng)先去后去，這樣才可以特指同一個(gè)個(gè)體 c 添加和刪去量詞時(shí)，該量詞必須是公式的最左邊的量詞，且此量詞的前邊無任何符號，它的轄域作用到公式末尾

40、,(1)xP(x)yQ(y) P (2) xP(x)Q(b) ES (3) P(a)Q(b) US(2) 錯(cuò)誤的作法,(1) xP(x)yQ(y) P (2)xP(x)yQ(y) T(1) E (3) xP(x)yQ(y) T(2) E (4) xy(P(x)Q(y) T(3) E (5) y(P(a)Q(y) ES(4) (6) P(a)Q(b) ES(4) (7) P(a)Q(b) T(5)E 正確的作法,80,xP(x) P P(c) US 錯(cuò)誤的作法,(1) xP(x) P (2) xP(x) T(1)E (3) P(c) ES (2) 正確的作法,xyP(x,y) P xP(x,c)

41、 ES 錯(cuò)誤的作法,(1) xyP(x,y) P (2) yP(a,y) US(1) 正確的作法,81,3.8 自動(dòng)定理證明*,數(shù)理邏輯為自動(dòng)推理證明奠定了基礎(chǔ) 數(shù)理邏輯的創(chuàng)始人亞里士多德 三段論 大前提、小前提和 結(jié)論三個(gè)部分的論證,亞里士多德,例：凡人都會死（大前提） 蘇格拉底是人（小前提） 所以：蘇格拉底會死（結(jié)論）,82,自動(dòng)證明的提出,笛卡爾,萊布尼茨,笛卡爾、萊布尼茨（17世紀(jì)） 萌發(fā)了用機(jī)械系統(tǒng)實(shí)現(xiàn)定理證明的想法 把一類數(shù)學(xué)問題當(dāng)作一個(gè)整體，建立統(tǒng)一的證明過程，按照規(guī)定的程序步驟機(jī)械地進(jìn)行下去，在有限步驟之后判斷出定理的正確性,83,自動(dòng)證明的發(fā)展,由于傳統(tǒng)的興趣和應(yīng)用的價(jià)值，初

42、等幾何問題的自動(dòng)求解成為數(shù)學(xué)機(jī)械化的研究焦點(diǎn)。,希爾伯特,希爾伯特 20世紀(jì)初，在他的名著幾何基礎(chǔ)中給出了一條可以對一類幾何命題進(jìn)行判定的定理。 希爾伯特對命題的要求太高，當(dāng)時(shí)僅能解決很少的一類幾何定理的機(jī)器證明，卻是歷史上第一個(gè)關(guān)于某類幾何命題的機(jī)械化檢驗(yàn)方法的定理,84,自動(dòng)證明的發(fā)展,塔斯基,塔斯基（波蘭） 1950年，證明了：“一切初等幾何和初等代數(shù)范圍的命題都可以用機(jī)械方法判定” 為幾何定理的機(jī)器證明開拓了一條利用代數(shù)方法的途徑 方法太復(fù)雜，即使用高速計(jì)算機(jī)也證明不了稍難的幾何定理,85,自動(dòng)證明的發(fā)展,艾倫.紐厄爾,紐厄爾,西蒙和肖 1956年, 發(fā)表了論文邏輯理論機(jī)(LTM) 認(rèn)

43、為LTM不僅是計(jì)算機(jī)智力的有力證明，也是人類認(rèn)知本質(zhì)的證明 1957年開發(fā)了最早的AI程序設(shè)計(jì)語言IPL語言 1960年，成功地合作開發(fā)了“通用問題求解系統(tǒng)” GPS (General Problem Solver),赫伯特.西蒙,86,自動(dòng)證明的發(fā)展,王浩,美籍華裔王浩 第一次明確提出“走向數(shù)學(xué)的機(jī)械化” 1959年，采用“王浩算法”用計(jì)算機(jī)證明了羅素 、 懷海德的巨著數(shù)學(xué)原理中的幾百條有關(guān)命題邏輯的定理，僅用了 9 分鐘 宣告了用計(jì)算機(jī)進(jìn)行定理證明的可能性 在1984年首屆自動(dòng)定理證明大會上獲最高獎(jiǎng)“里程碑”獎(jiǎng)。,87,自動(dòng)證明的發(fā)展,1977年，美國年輕的數(shù)學(xué)家阿佩爾等在高速電子計(jì)算機(jī)上耗費(fèi) 1200 小時(shí)的計(jì)算時(shí)間，證明了著名的“四色定理” ，人類百年懸而未決的疑問最終被圓滿解決了。這一成就轟動(dòng)一時(shí)，成為機(jī)器定理證明的一個(gè)典范。,88,屬于中國的自動(dòng)證明方法吳方法,吳文俊 1977年，發(fā)表論文初等幾何判定問題與機(jī)械化證明 1984 年，學(xué)術(shù)專著幾何定理機(jī)器證明的基本原理 1985 年，論文關(guān)于代數(shù)方程組的零點(diǎn)發(fā)表吳文俊消元法 利用中國古典數(shù)學(xué)的成就，提出具有中國特色的自動(dòng)證明方法 2001年榮獲首屆國家科學(xué)技術(shù)最高獎(jiǎng),吳文俊,89,推理是如何進(jìn)行的？,推理過程多種多樣 例1： 如果今天不下雨，我就去你家 今天沒有下雨 例2： 小王