謂詞邏輯中公理化真度的若干評(píng)注

馬 碩， 惠小靜， 郝 嬌

(延安大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,陜西 延安 716000)

21世紀(jì)初王國(guó)俊教授在經(jīng)典二值命題邏輯中引入了公式真度的概念，為命題的近似推理提供了一種可能的框架[1—2].緊接著建立了計(jì)量邏輯學(xué)理論[3—4]，從語義上對(duì)邏輯概念進(jìn)行了程度化研究，將數(shù)值計(jì)算融入數(shù)理邏輯中并建立符號(hào)語言與數(shù)值計(jì)算之間的橋梁.這種理論一經(jīng)提出便受到廣泛關(guān)注，在多值命題邏輯的各種系統(tǒng)中提出了不同公式的真度概念，研究了公式間的相似度與偽距離的性質(zhì)，提出了邏輯理論的發(fā)散度與相容度并討論了它們的應(yīng)用[5—11].但目前對(duì)謂詞邏輯系統(tǒng)的研究較少，部分學(xué)者對(duì)謂詞邏輯只做了嘗試性研究[12—15]，在全體不含函數(shù)符號(hào)的一階閉邏輯公式集Φ中建立了公理化的真度理論，并在真度理論的基礎(chǔ)上引入Φ中公式之間相似度和偽距離的概念及計(jì)算方法.

不難發(fā)現(xiàn)在命題邏輯系統(tǒng)中，從真度角度判斷一個(gè)公式是否為定理或矛盾式較容易.在謂詞邏輯系統(tǒng)中，又該如何判斷一個(gè)公式為定理或矛盾式呢？本文對(duì)此進(jìn)行了進(jìn)一步的討論，根據(jù)一階謂詞邏輯中公理化真度的定義[15]對(duì)文中列舉的公式的真度進(jìn)行了計(jì)算，根據(jù)偽距離的定義討論了在具體真度下偽距離的性質(zhì),得出了真度為1的公式與廣義定理及定理之間的關(guān)系，同時(shí)分析了真度為0的公式與廣義矛盾式及矛盾式之間的異同.

1 預(yù)備知識(shí)

定義1[15]稱映射τ:Φ→[0,1]為公理化真度映射，若以下條件成立：

(K2)若α是Φ中的定理，則τ(α)=1.

(K3)τ(α)=1-τ(α),α∈Φ.

(K4)τ(α→β)+τ(α)=τ(β→α)+τ(β),α,

β∈Φ.

(K5)τ(cl(Q))=1-τ(clQ).

(K6)在計(jì)算公式的真度時(shí)原公式中的變?cè)梢韵嗷ヌ鎿Q.

當(dāng)α∈Φ時(shí)，稱τ(α)為α的公理化真度，簡(jiǎn)稱為α的τ-真度或真度.

定義2[15]設(shè)α,β∈Φ，令ξ(α,β)=τ((α→β)∧(β→α))，稱ξ(α,β)為α與β之間的相似度.

命題1[15]設(shè)α,β,γ∈Φ，則下列命題成立：

(ⅰ)ξ(α,β)=ξ(β,α).

(ⅱ)若α與β邏輯等價(jià)，則ξ(α,β)=1.

(ⅲ)ξ(α,β)=τ(α→β)+τ(β→α)-1.

(ⅳ)ξ(α,β)=1+τ(α∧β)-τ(α∨β).

(ⅴ)ξ(α,β)+ξ(α,β)=1.

(ⅵ)ξ(α,β)+ξ(β,γ)≤ξ(α,γ)+1.

定義3[15]設(shè)α,β∈Φ，令ρ(α,β)=1-ξ(α,β)，稱ρ(α,β)為α與β之間的偽距離.

命題2[15]設(shè)α,β,γ∈Φ，則下列命題成立：

(ⅰ)ρ是φ上的偽距離，但不是距離.

(ⅱ)ρ(α,β)+ρ(α,β)=1.

(ⅲ)ρ(α,β)=τ(α∨β)-τ(α∧β).

定義4[15]設(shè)α∈φ，若τ(α)=1，則稱α為廣義定理；若τ(α)=0，則稱α為廣義矛盾式.

定義5[3]稱一階語言L中的公式A為邏輯有效的，若對(duì)L的每個(gè)解釋I均有I╞A.稱A為矛盾式，若對(duì)L的每個(gè)解釋I╞A，即對(duì)L的每個(gè)解釋I以及L在I中的每個(gè)賦值ν，ν不滿足A.

定義6[3]設(shè)L是一階語言,I是L的一個(gè)解釋,v和v′是L在I中的2個(gè)賦值.若v與v′滿足條件：當(dāng)j≠i時(shí)v(xj)=v′(xj),j=1,2,…，則稱賦值v與v′是i-等價(jià)的.

2 定理及矛盾式的真度特征

定理1若對(duì)任意α,β∈D(Γ),有[ρ(α,β)]=0,則取α為定理時(shí)，對(duì)任意β∈D(Γ)，β不是廣義矛盾式.

證明因?yàn)閇ρ(α,β)]=0，所以ρ(α,β)<1.

ρ(α,β)=1-ξ(α,β)=

1-[1+(τ(α∧β)-τ(α∨β))]=

τ(α∨β)-τ(α∧β)=

τ(α)+τ(β)-τ(α∧β)-

(τ(α)+τ(β)-τ(α∨β))=-τ(β)+1.

由ρ(α,β)<1得-τ(β)+1<1，τ(β)>0，即τ(β)≠0.所以取α為定理時(shí)，對(duì)任意β∈D(Γ)，β不是廣義矛盾式.

定理2真度等于1的公式是廣義定理，但不一定是定理.

證明設(shè)α=(?x)(?y)(A(x)→A(y))，先證明α是真度等于1的公式.由定義1中(K6)知τ(α)=τ((?x)(A(x)→A(x)))=1，所以α是廣義定理.

再證α不是定理.令γ=(?x)A(x)∨(?x)A(x)，α與γ邏輯等價(jià)，只需證明γ不是定理，就能證明α不是定理.

設(shè)賦值v滿足γ，即v滿足(?x)A(x)或(?x)A(x)，從而v不滿足(?x)A(x)且(?x)A(x).有以下2種情況：①v滿足(?x)A(x)，v不滿足(?x)A(x)；②v滿足(?x)A(x)，v不滿足(?x)A(x).

由定義6知，存在與v是i-等價(jià)的賦值v′滿足A(x)，即v′不滿足A(x)，從而v不滿足(?x)A(x).因此，當(dāng)v滿足γ時(shí)，v滿足(?x)A(x)與v不滿足(?x)A(x)不能同時(shí)成立，所以v不滿足γ.從而證明γ不是定理，即α也不是定理.

例1設(shè)λ=(?x)(?y)((A(x)∨A(x))→(A(y)∧A(y)))，則λ是廣義定理但不是定理.

證明先證明λ是真度等于1的公式.由定義1中(K6)知

τ(λ)=τ((?x)((A(x)∨A(x))→

(A(x)∧A(x))))=1，

所以λ是廣義定理.

再證λ不是定理.令γ=(?x)A(x)∨(?x)A(x)，只需證明λ與γ邏輯等價(jià)，就能通過γ不是定理得出λ不是定理.

λ=(?x)(?y)((A(x)∨A(x))→

(A(y)∧A(y)))≈

(?x)(?y)(A(x)→A(y))≈

(?x)A(x)→(?x)A(x)=γ.

即λ與γ邏輯等價(jià).由于γ不是定理，所以λ不是定理.

引理1(換名規(guī)則)[12]

(Ⅰ)將量詞的作用元及其轄域中所有受約束的同符號(hào)的變?cè)靡粋€(gè)新的變?cè)鎿Q.

(Ⅱ)新的變?cè)窃街袥]有出現(xiàn)的.

(Ⅲ)由(Ⅰ)、(Ⅱ)得到的新公式與原公式等值.

引理2[3]設(shè)變?cè)獂i不在公式A中自由出現(xiàn)，則

(?xi)(A→B)～(A→(?xi)B)，

(?xi)(A→B)～(A→(?xi)B).

設(shè)變?cè)獂i不在公式B中自由出現(xiàn)，則

(?xi)(A→B)～((?xi)A→B)，

(?xi)(A→B)～((?xi)A→B).

引理3(量詞轄域擴(kuò)縮律)[12]A(x)是任意一階公式，B是任一不含自由變量x的一階公式.

(Ⅰ)?xA(x)∧B??x(A(x)∧B).

(Ⅱ)?xA(x)∨B??x(A(x)∨B).

(Ⅲ)?xA(x)∧B??x(A(x)∧B).

(Ⅳ)?xA(x)∨B??x(A(x)∨B).

(Ⅴ)?xA(x)→B??x(A(x)→B).

(Ⅵ)B→?xA(x)??x(B→A(x)).

(Ⅶ)?xA(x)→B??x(A(x)→B).

(Ⅷ)B→?xA(x)??x(B→A(x)).

定理3真度等于0的公式是廣義矛盾式，但不一定是矛盾式.

證明設(shè)β=(?x)(?y)(A(x)→A(y))，先證明β是真度等于0的公式.由定義1中(K6)知τ(β)=τ((?x)(A(x)→A(x)))=0，所以β是廣義矛盾式.

再證β不是矛盾式.令η=(?x)A(x)∧(?x)A(x)，β與η邏輯等價(jià)，只需證明η不是矛盾式，就能證明β不是矛盾式.

η=(?x)A(x)∧(?x)A(x)≈

(?x)A(x)∧(?y)A(y)≈

(?x)((?y)A(y)∧A(x))≈

(?x)(?y)(A(x)∧A(y))≈

(?x)(?y)(A(x)∨A(y))≈

(?x)(?y)(A(x)→A(y))=β，

即β與η邏輯等價(jià).

設(shè)賦值v不滿足η，即v不滿足(?x)A(x)或(?x)A(x)，從而滿足(?x)A(x)且(?x)A(x).有以下2種情況：①v不滿足(?x)A(x)，v滿足(?x)A(x)；②v不滿足(?x)A(x)，v滿足(?x)A(x).

由定義6知，與vi-等價(jià)的賦值v′不滿足A(x)，即v′滿足A(x)，從而v滿足(?x)A(x).因此，當(dāng)v不滿足η時(shí)，v不滿足(?x)A(x)與v滿足(?x)A(x)不能同時(shí)成立，所以v滿足η.從而證明η不是矛盾式，即β也不是矛盾式.

例2設(shè)μ=(?x)(?y)((A(x)∨A(x))→(A(y)∧A(y)))，則μ是廣義矛盾式，但不一定是矛盾式.

證明先證明μ是真度等于0的公式.由定義1中(K6)知

τ(μ)=τ((?x)((A(x)∨A(x))→

(A(x)∧A(x))))=0，

所以μ是廣義矛盾式.

再證μ不是矛盾式.令η=(?x)A(x)∧(?x)A(x)，只需證明μ與η邏輯等價(jià)，就能通過η不是矛盾式得出μ不是矛盾式.

μ=(?x)(?y)((A(x)∨A(x))→

(A(y)∧A(y)))≈

(?x)(?y)(A(x)→A(y))≈

(?x)A(x)∧(?x)A(x)=η，

即μ與η邏輯等價(jià).由于η不是矛盾式，所以μ不是矛盾式.

3 結(jié)語

本文在不含函數(shù)符號(hào)的一階謂詞邏輯中計(jì)算了公式的真度，討論了偽距離的性質(zhì).然后運(yùn)用賦值法對(duì)一階謂詞公式進(jìn)行了研究，判斷出一階謂詞邏輯公式是否為定理，是否為矛盾式.后續(xù)值得關(guān)注的研究?jī)?nèi)容是如何將本文的結(jié)果推廣到允許含有函數(shù)符號(hào)的情形.