1、經(jīng)典謂詞（一階）邏輯,蘇格拉底三段論 所有人都是要死的。 蘇格拉底是人。 蘇格拉底是要死。 命題邏輯的局限性 不能分析原子命題內(nèi)部的結(jié)構(gòu)形式。 在謂詞邏輯中，對原子命題的結(jié)構(gòu)進行進一步分析 謂詞 個體 量詞 在一階邏輯中，邏輯形式由聯(lián)結(jié)詞、謂詞、個體、量詞共同決定,一階語言L,一階語言L 是經(jīng)典謂詞（一階）邏輯的形式語言 一階語言L 是符號的集合 個體符號：a b c 關(guān)系符號：F G H 特別的， 函數(shù)符號：f g h 自由變元符號：u v w 約束變元符號：x y z 聯(lián)結(jié)符號： 量詞符號： 標(biāo)點符號：（ ， ） 注意：在一階語言中沒有命題符號。 一階語言L 的含義本質(zhì)上不涉及語義，而只有

2、語法。,表達式,表達式： L 中有限個符號組成的字符串 表達式的長度：表達式中的符號數(shù)目 空表達式：長度為0的表達式，記為 表達式相等：U=V iff 表達式U和V中符號依次相同 表達式U和V依次并列形成新的表達式UV，且 若表達式U=W1VW2，則V是U的段。若V是U的段且V和U不相等，則V是U的真段。 初始段、結(jié)尾段、真初始段、真結(jié)尾段,Term(L )的歸納定義,Term(L )的定義 i） a，uTerm(L ) ii）若t1， t2， ，tnTerm(L )，且f為n元函數(shù)符號，則f (t1， t2， ，tn )Term(L ) iii）t是能由有限次應(yīng)用i）ii）形成的表達式 if

3、f tTerm(L ) 不含自由變元的項被稱為閉項。 t表示項。 Term(L )的歸納證明原理。,項的結(jié)構(gòu),定理： Term(L )中的項具有以下三種形式之一：個體符號，自由變元符號， f (t1， t2， ，tn )，其中f為n元函數(shù)符號；且項具有的形式是唯一的。 定理：若t是f (t1， t2， ，tn )的段，則t=f (t1， t2， ，tn )或t為ti（i=1，2，n）的段。,Atom(L )的定義,Atom(L )的定義 L 的表達式是Atom(L )的元素，當(dāng)且僅當(dāng)它為下列情況之一： i） F(t1， t2， ，tn) ，其中F為n元關(guān)系符號， t1， t2， ，tn Ter

4、m(L )。 ii）(t1， t2)，其中為相等關(guān)系符號，t1，t2Term(L )。,Form(L )的歸納定義（一）,合式公式集Form(L ) i） Atom(L )Form(L ) ii）若AForm(L )，則(A)Form(L ) iii）若A，BForm(L )，則(A*B)Form(L )。其中*表示，中的任何一個 iv）若A(u)Form(L )，且x不在A(u)中出現(xiàn)，則xA(x)， xA(x) Form(L ) v）A是能由有限次應(yīng)用i）iv）形成的表達式 iff AForm(L ),Form(L )的歸納定義（二）,不含自由變元的公式被稱為閉公式或語句，Sent(L )

5、表示所有語句構(gòu)成的集合。 含有某個約束變元而不含它的量詞的表達式被稱為擬公式。 擬公式不是公式。 A，B，C表示公式、擬公式。,Form(L )的歸納證明原理,定理：設(shè)R是一個性質(zhì)，若 i）對于任何pAtom(L )，R(p)； ii）對于任何AForm(L )，若R(A)，則R(A)； iii）對于任何A，BForm(L )，若R(A)且R(B)，則R(A*B) 。其中*表示，中的任何一個； iv）對于任何A(u)Form(L )，若R(A(u)，且x不在A(u)中出現(xiàn)，則R(xA(x)， R(xA(x)。 則對于任何AForm(L )，R(A)。,公式結(jié)構(gòu),定理：L 的每一公式恰好具有以下

6、8種形式之一：原子公式， (A)， (AB)， (AB)， (AB)，(AB)， xA(x)， xA(x) ；并且在各種情形，公式所具有的那種形式是唯一的。,公式的語法分類,原子公式 復(fù)合公式 否定式 合取式 析取式 蘊含式 等值式 全稱式 存在式,轄域,若(A)是C的段，則稱A為它左方的在C中的轄域 若(A*B)是C的段，則稱A和B分別為它們之間的*在C中的左轄域和右轄域。其中*表示，中的任何一個 若xA(x)或xA(x)是B的段，則稱A(x)為x或x在B中的轄域 定理：任何A中的任何（如果有）有唯一的轄域；任何A中的任何*（如果有）有唯一的左轄域和右轄域；任何A中的任何x或x （如果有）有

7、唯一的轄域 定理：若A是(B)的段，則A= (B)或A是B的段；若A是(B*C)的段，則A= (B*C)或A是B的段或A是C的段；若 A是xB(x)或xB(x)的段，則A=xB(x)或xB(x)，或A是B(x)的段。,形式可推演,用表示任何公式集，即Form(L ) 。 A可以記為，A。 可以記為，。 若=A1, A2, A3, ，則可以記為A1, A2, A3, 。 A表示A由形式可推演（形式可證明）的。其中， 為前提，A為結(jié)論。 不是L 中符號。 A不是公式。 AB表示“AB并且BA”，并稱A和B是語法等值的。,一階邏輯的推演規(guī)則（一）,共11+6條，A，B，C為公式 (Ref) AA (

8、+)若A， 則， A (-)若， A B， ， A B， 則A (-)若AB， A， 則B (+)若，AB， 則AB (-)若AB， 則A， B (+)若A ， B ， 則AB,(-)若，AC， ，BC， 則，ABC (+)若A ， 則AB， BA ( -)若A B， A， 則B 若A B， B， 則A ( +)若，AB， ，BA， 則A B,一階邏輯的推演規(guī)則（二）,(-)若xA(x)， 則A(t) (+)若A(u) ，u不在中出現(xiàn)， 則xA(x) (-)若， A(u) B，u不在，B中出現(xiàn)， 則， xA(x) B (+)若A(t)， 則xA(x) ，其中A(x)是在A(t)中把t的某些（不

9、一定全部）出現(xiàn)替換成x而得。 (-)若A(t1)， t1t2， 則A(t2) ，其中A(t2)是在A(t1)中把t1的某些（不一定全部）出現(xiàn)替換成t2而得。 (+)u u,形式推演的定義,A是在一階邏輯中由形式可推演（形式可證明）的，記為A，當(dāng)且僅當(dāng)A能有限次使用一階邏輯中形式推演規(guī)則生成。 這是一個歸納定義。關(guān)于歸納證明。 一個有限序列1A1，2A2，nAn被稱為nAn的形式證明。其中， kAk（1kn）由使用某一推演規(guī)則而生成。,證明： xA(x)x(A(x),證： 先證xA(x)x(A(x)。 (1) A(u) A(u) u不在A(x)中出現(xiàn) (Ref) (2) A(u) x(A(x)

10、(+)(1) (3) x(A(x)，A(u) x(A(x) (+)(2) (4) x(A(x)，A(u) x(A(x) () (5) x(A(x) A(u) ( -)(3)(4) (6) x(A(x) xA(x) (+)(5) (7) xA(x)，x(A(x) xA(x) (+)(6) (8) xA(x)，x(A(x) xA(x) () (9) xA(x)x(A(x) ( -)(7)(8),再證x(A(x) xA(x)。,(1) xA(x) xA(x) (Ref) (2) xA(x) A(u) u不在A(x)中出現(xiàn) (-)(1) (3) A(u) ，xA(x) A(u) (+)(2) (4)

11、A(u) ，xA(x) A(u) () (5) A(u) xA(x) (+)(3)(4) (6) x(A(x) xA(x) (-)(5),證明： x(A(x)B(x) xA(x)xB(x),證： (1) x(A(x)B(x) x(A(x)B(x) (Ref) (2) x(A(x)B(x) A(u)B(u) (-)(1) u不在A(x)和B(x)中出現(xiàn) (3) x(A(x)B(x)，xA(x) A(u)B(u) (+)(2) (4) x(A(x)B(x)，xA(x) xA(x) () (5) x(A(x)B(x)，xA(x) A(u) (-)(4) (6) x(A(x)B(x)，xA(x) B(

12、u) (-)(3)(5) (7) x(A(x)B(x)，xA(x) xB(x) (+)(6) (8) x(A(x)B(x) xA(x)xB(x) (+)(7),證明： x(A(x)B(x) xA(x) xB(x),證： (1) x(A(x)B(x) x(A(x)B(x) (Ref) (2) x(A(x)B(x) A(u)B(u) (-)(1) u不在A(x)和B(x)中出現(xiàn) (3) x(A(x)B(x)，A(u) A(u)B(u) (+)(2) (4) x(A(x)B(x)，A(u) A(u) () (5) x(A(x)B(x)，A(u) B(u) (-)(3)(4) (6) x(A(x)B(

13、x)，A(u) xB(x) (+)(5) (7) x(A(x)B(x)，xA(x) xB(x) (-)(6) (8) x(A(x)B(x) xA(x) xB(x) (+)(7),證明： x(A(x)B(x)， x(B(x)C(x) x(A(x)C(x),證： (1) x(A(x)B(x) x(A(x)B(x) (Ref) (2) x(A(x)B(x) A(u)B(u) (-)(1) u不在A(x)、B(x)和C(x)中出現(xiàn) (3) x(A(x)B(x)，x(B(x)C(x)，A(u) A(u)B(u) (+)(2) (4) x(A(x)B(x)，x(B(x)C(x)，A(u) A(u) ()

14、(5) x(A(x)B(x)，x(B(x)C(x)，A(u) B(u) (-)(3)(4) (6) x(A(x)B(x)，x(B(x)C(x)，A(u) x(B(x)C(x) () (7) x(A(x)B(x)，x(B(x)C(x)，A(u) B(u)C(u) (-)(6) (8) x(A(x)B(x)，x(B(x)C(x)，A(u) C(u) (-)(5)(7) (9) x(A(x)B(x)，x(B(x)C(x) A(u)C(u) (+)(8) (10) x(A(x)B(x)，x(B(x)C(x) x(A(x)C(x) (+)(9),證明：AxB(x) x(AB(x) 。x不在A中出現(xiàn)。 證

15、：先證AxB(x) x(AB(x) 。 (1) AxB(x)，A AxB(x) () (2) AxB(x)，A A () (3) AxB(x)，A xB(x) (-)(1)(2) (4) AxB(x)，A B(u) (-)(3) u不在A和B(x)中出現(xiàn) (5) AxB(x) AB(u) (+)(4) (6) AxB(x) x(AB(x) (+)(5),再證x(AB(x) AxB(x) 。 (1)x(AB(x)，A x(AB(x) () (2)x(AB(x)，A AB(u) (-)(1) u不在A和B(x)中出現(xiàn) (3)x(AB(x)，A A () (4)x(AB(x)，A B(u) (-)(

16、2)(3) (5)x(AB(x)，A xB(x) (+)(4) (6)x(AB(x) AxB(x) (+)(5),證明： A(t1)，t1 t2A(t2) 證： (1) A(t1)，t1 t2 A(t1) () (2) A(t1)，t1 t2 t1 t2 () (3) A(t1)，t1 t2 A(t2) (-)(1)(2),證明： t t 證： (1) u u (+) (2) x(x x) (+)(1) (3) t t (-)(2),證明： t1 t2 t2 t1 證： (1) t1 t1 (已證) (2) t1 t2 t1 t1 (+)(1) (3) t1 t2 t1 t2 (Ref) (4

17、) t1 t2 t2 t1 (-)(2)(3),證明： A(t) x(x tA(x) 證：先證A(t) x(x tA(x) (1) A(t)，u t A(t) () u不在A(t)中出現(xiàn)。 (2) A(t)，u t u t () (3) u t t u (已證) (4) A(t)，u t t u (Tr)(2)(3) (5) A(t)，u t A(u) (-)(1)(4) (6) A(t) u t A(u) (+)(5) (7) A(t) x(x t A(x) (+)(6),再證x(x tA(x) A(t) (1) x(x tA(x)x(x tA(x) (Ref) (2) x(x tA(x)

18、t t A(t) (-)(1) (3) t t (+) (4) x(x tA(x) t t (+)(3) (5) x(x tA(x) A(t) (-)(2)(4),語義（一）,論域（個體域） 問題所討論的對象集稱為論域，記為D。論域中的對象稱為個體。 全總個體域：包含一切對象的集合，它是特殊的個體域。 個體符號 論域D中的個體常元 n元函數(shù)符號f f：DnD,語義（二）,n元關(guān)系符號F FDn 自由變元符號 取值范圍為論域D的個體變元 量詞 xF(x)：對于所有xD，F(xiàn)(x)。 xF(x)：存在xD，使得F(x)。 約束變元 被量詞量化的變元。 受限制量詞 量詞的范圍由原來的論域被限制為論域的

19、某個子集。,語義（三）,閉項代表論域D中的個體常元；非閉項代表個體變元。 含n個不同自由變元符號的公式稱為論域D上的n元命題函數(shù)： Dn1，0 閉公式是0元命題函數(shù)，是命題。,語義（四）,對于一階語言L 的賦值包括一個論域D和一個函數(shù)v。v以所有的個體符號、關(guān)系符號、函數(shù)符號、自由變元符號構(gòu)成的集合為定義域，且將v(a)，v(F)，v()，v(f)，v(u)記為av，F(xiàn)v，v ，fv，uv，其中a為個體符號，F(xiàn)為n元關(guān)系符號，f為m元函數(shù)符號，u為自由變元符號 則i） av， uvD ii） FvDn iii）v =|x D iv）fv： Dm D,語義（五）,項t在賦值v下的值，記為tv。其

20、定義為： i） av， uvD ii） (f (t1， t2， ，tn )v=fv(t1v， t2v， ，tnv ) ，其中t1， t2， ，tnTerm(L ) 定理：設(shè)v是論域D上的一個賦值，且t Term(L )，則tv D。,語義（六）,公式A在賦值v下的值，記為Av。其定義為： (i)若Fv，(F (t1， t2， ，tn )v=1；否則， (F (t1， t2， ，tn )v=0。 (ii)若Av=0， 則(A)v=1；否則，(A)v=0。 (iii)若Av=Bv=1， 則(AB)v=1；否則，(AB)v=0。 (iv)若Av=Bv=0， 則(AB)v=0；否則，(AB)v=1。

21、(v)若Av=1并且Bv=0， 則(AB)v=0；否則，(AB)v=1。 (vi)若Av=Bv， 則(AB)v=1；否則，(AB)v=0。 (vii)u代入x，由A(x)得到A(u)，且u不在A(x)中出現(xiàn)。若對于任何D，A(u)v(u/)=1，則(xA(x) )v=1；否則， (xA(x) )v=0。 (viii)u代入x，由A(x)得到A(u)，且u不在A(x)中出現(xiàn)。若存在D，使得A(u)v(u/)=1，則(xA(x) )v=1， 否則，(xA(x) )v=0。 定理：設(shè)v是論域D上的一個賦值，且A Form(L )，則Av 1，0。,公式的語義分類,若對于所有B，Bv=1，則v=1；否則， v=0。 是可滿足的，當(dāng)且僅當(dāng)存在賦值v，使得v=1。特別的，若A 是可滿足的，則稱A為可滿足式。 A是有效的，當(dāng)且僅當(dāng)對于任何的賦值v， Av=1。,邏輯推論,設(shè)Form(L )，AForm(L )。A是的邏輯推論，記作A， 當(dāng)且僅當(dāng)對于任何賦值v，v=1蘊涵Av=1（ Av=0蘊涵 v=0）。 A表示A為有效公式。 不是L 中符號。 A不是公式。 AB表示“AB并且BA”，并稱A和B是邏輯等值的。,證明：x(A(x) xA(x)。 證： 對于任何論域D上的賦值v， 若(x(A(x)v=1。 即， u代入x，由A(x)得到A(u)，且