高級(jí)數(shù)理邏輯第4講

4一階謂詞邏輯4.1一階謂詞邏輯的基本概念世界的描述能力是有限的。所有自然數(shù)都大于它的素?cái)?shù)AVx(A(x)>3y(P(x,y)^Q(y)))2100是自然數(shù)BA(2100)是一個(gè)原子命題、二三句同樣是原子命題。而這些原子命題之間無(wú)法建立關(guān)聯(lián)關(guān)系。然而上述推理是正確的，是現(xiàn)實(shí)中存在的現(xiàn)象。一階謂詞邏輯解決了上述問(wèn)題，能夠?qū)υ用}進(jìn)行分割和更細(xì)致的研究工作。階謂詞里被稱為的函詞(函數(shù))。F(x,y)=x*yQ(y),P(x,y)::x<y謂詞定義：謂詞表示個(gè)體性質(zhì)和關(guān)系的語(yǔ)言成分。它附帶放置對(duì)象的空位，只相反為謂詞填式。謂詞后面的空位個(gè)數(shù)為謂詞的元數(shù)。謂詞是一個(gè)體域上的n函詞定義：函詞是表示某種操作的語(yǔ)言成份。用于在給定的個(gè)體基礎(chǔ)上，產(chǎn)生新的個(gè)體對(duì)象。與謂詞一樣，函詞具有空位的概念。函詞后面空位的個(gè)數(shù)為函變?cè)鹤冊(cè)梢杂脕?lái)表示個(gè)體域上的任意個(gè)體，是不確定的。(2)對(duì)所有z，x，y?x=x?yQ(x*Z,Z*x)二元謂詞表示乘法交換率Q(x,z)=1*2=2*3Q(f(x,y),f(y,x))=Q(f(1,2),f(2,1))=1XYPxyPXY)約束變?cè)杭s束變?cè)⒉皇菍?shí)際意義的變?cè)?數(shù)學(xué)意義上的變?cè)?。約束變?cè)菫楸磉_(dá)某種想的輔助符號(hào)。自由變?cè)c約束變?cè)膶?duì)比：可代入不可改名舉例說(shuō)明：采用上例。約束變?cè)豢纱肟筛拿鐚?duì)于下面的命題：謂詞邏輯引入了量詞的概念。VxQ(X2)=~3x~Q(X2)VzVy(Q(z*y,y*z))VxP(x)VyP(y+1)；P大于0，x論域是自然數(shù),VxVy(P(x)>P(y+1))Vx(P(x)P(x+1));P大于0，x論域是實(shí)數(shù).全稱量詞：VxP(x)中的V稱為全稱量詞，Vx中的x稱為V的指導(dǎo)變?cè)?；Vx(A(x))-->B(x)3x(A>B)>Cx=1,A(1)>B(1)A(1)>B(1)3xA>B{1,2,3}===~(~(A(1)^A(2)^A(3)))=1P(x,y)\~(~A(1)v~A(2)v~A(3))=~~A(1)&~~A(2)&~~A(3)5.VxVyA╞│VyVxAVx3yA(x,y)f(x)3yVxA(x,y)Vx(A(x)>A(x+z))VxA(x)>A(x+z)VxA(x)VVxB(x)=Vx(A(x)VB(x);A(1)^A(2)^A(3)B(1)^B(2)^B(3)====VxVy(A(x)VB(y))=Vx(A(x)VB(x))例如：所有實(shí)數(shù)的平方是非負(fù)的-3是實(shí)數(shù)-3的平方是非負(fù)的Vx(R(x)P(x2))R(-3)P((-3)2)4.2一階形式系統(tǒng)(FSFC)回顧形式系統(tǒng)的構(gòu)成，主要有語(yǔ)言部分和推理部分構(gòu)成。語(yǔ)言部分是一階語(yǔ)言。一階語(yǔ)言可以從以下幾個(gè)方面定義：符號(hào)表、項(xiàng)集、公式集等三個(gè)部分。函詞符號(hào)：f(1),f(1),f(1),…(一元函詞)123f(n),f(n),f(n),…(n元函詞)123謂詞符號(hào)：123123量詞：技術(shù)符：(,)(一元謂詞)(n元謂詞)(1)變?cè)统Ｔ豁?xiàng)； (2)對(duì)于任意正整數(shù)n和函數(shù)f(n)，如果t........tn為項(xiàng)1(3)除有限次使用(1)(2)得到外，沒(méi)有任何項(xiàng)。{a,x,f()}={a,x,fn(a),fn(x)}由定義可知，項(xiàng)集是遞歸定義的、是可判定的。(1)對(duì)于任意正整數(shù)n，如果t1.......n為項(xiàng)，那稱Pn(t1.......tn)為公式，并為原ABAABxA式；(3)公式都是有限次使用(1)(2)得到的，除此之外無(wú)其他公式。閉項(xiàng)：不含自由變?cè)捻?xiàng)f(a,a)，閉公式：不含自由變?cè)墓絍x(P(a,x)－>B(x))A(x)=1,0;;;,VxA(x);轄域：公式A稱為量詞Vx(3x)的轄域，如果Vx(3x)與A相鄰，且A的任何真截?cái)嗖皇枪郊s束出現(xiàn)：在公式A中，變?cè)獂的某個(gè)出現(xiàn)叫做約束出現(xiàn)，如果x為V(x)的指導(dǎo)變?cè)蛟赩x，3x的轄域內(nèi)。否則為自由出現(xiàn)VxP(x)P(x)=VyP(y)>~P2(x1)1121可代入性：稱項(xiàng)t是對(duì)A中自由變?cè)獂可代入的；如果A中項(xiàng)x的任何自由出現(xiàn)都不在Vy(3y)的轄域內(nèi)，這里y是t中的任意自由變?cè)yVxVzP(x,z)VyP(x,f+1)VyA(x,y)t=y+1;zVA=VyP(x1+z,z)VxP(x,y)q(y)aaVyP(x,z)VyP(x,f+1)VyP(z+1,z)::::VyP(y+x+1,y+x){(z+1)/x,(y+x)/z}tt…t12n11n1,2,n代換為項(xiàng)t。這與下面的逐步代入是不同的：nttt12nAPvv可以寫為P(v,v)，那么v2>v1,v3>v212((Av1)v2=P(2)vv=P(v,v)vv33333vvvv23232,2ww稱為真子公式。是合理的112rP(x)VxP(x)＝P1(x)>VyP2(y)2P(x)VyP(y)12Vx(P(x)VyP(y))12VxA(x)-->A(x)(VxVy(P(x)P(y)))(P(x)P(y))1212.公式性質(zhì)和項(xiàng)的性質(zhì)(遞歸集合)，可以用歸納證明(根據(jù)公式和項(xiàng)定義過(guò)程來(lái)證12niiiA的全稱化(generalizations)，其中1i,i,…in。公式VvVv,…,VvA稱22r12n推理部分包含：公理集合和推理規(guī)則集合。A1(A(BA))(VxP(x)(B(y)VzP(z)))A2(A(BC))((AB)(AC))A3(AB)(BA)A5Vx(AB)(VxAVxB)A6AVxA(x在A中無(wú)自由出現(xiàn)==無(wú)出現(xiàn))分離規(guī)則B1對(duì)約束出現(xiàn)變量不改變意義，例如：對(duì)于公式VxP(x)與Vx(VxP(x))具有同4.3一階謂詞演算利用公理和推理規(guī)則進(jìn)行推理演算，與命題系統(tǒng)類似，但更為復(fù)雜。對(duì)于演繹結(jié)果、證明序列等概念與形式系統(tǒng)和命題形式系統(tǒng)完全相同。在此不在重復(fù)。Vx3(y)P(x)3yP(z)vv是A，因此VvAAVxA-->A;(VvAA)(AVvA)VvAAAVvAB=A(x)-->A(x)==13x(A(x)-->A(x))=0B=~A(x)-->A(x)==0,Vx(~A(x)-->A(x))=1(1)公理3(2)公理4 (3)r(2)(1)1、命題形式系統(tǒng)中的重言式是FSFC的定理：即存在證明序列，由公理和推理規(guī)則得inmAAiAj。假設(shè)Ai=AjA。則├VxA。123lAVxAVxA對(duì)證明序列長(zhǎng)度歸納證明。(1)AVxA(2)A(3)VxArmp(1,2)假設(shè)l<n時(shí)，定理成立；當(dāng)l=n時(shí)，分成以下集中情況：(1)VxAi(2)Vx(AA)in(3)├Vx(AA)(VxAVxA)inin(4)VxAVxAin納假設(shè)納假設(shè)(2，3)(5)VxA(1，4)n所以有：├VxA。由此定理成立。(1)├AB(3)(AB)((AB)A))(4)(AB)A(5)├A納假設(shè)納假設(shè)為重言式(1，3)(2,4)的指導(dǎo)變?cè)拖鄳?yīng)的約束變?cè)?如果有)都改為另一個(gè)相同名字的變?cè)蟮玫降墓絍xP(x,y)>ExP(x,z)(1)VxA(x)前提(2)VxA(x)A(t)(3)A(t).全稱(V)引入規(guī)則：如果├A(t)，t不在中出現(xiàn)，則├VxA(x)。存在(3)銷去規(guī)則：設(shè)為FSFC的任意公式集合，A,B為公式。變?cè)獂A(1)-->3xA(x)(1)├AB(2)(AB)(BA)(3)├BA演繹定理重言式演繹定理2、例：利用改名原理證明：對(duì)FSFC中任意公式A，變?cè)獂，y，VxVyA├VyAx。yVxVyP(x,y)>VyP(y,y)VyPyy(1)VxVyA已知(2)VxVzAy將y改名為z改名原理z(3)VxVzAyVz((Ay)x)zzyz可代入)。(4)z(Ay)xzy(5)z(Ay)x((Ay)x)zzyzyy(5)yAxy3、例：證明存在(3)銷去規(guī)則。(1)|-AB(2)(AB)(BA)(3)|-(BA)(4)