一階邏輯中不含相同謂詞符號公式的真度研究

王 波，惠小靜，魯 星

(延安大學 數學與計算機科學學院，陜西 延安 716000)

數理邏輯的特點在于形式化和符號化，它和計算數學有截然不同的風格，前者注重形式推理，而后者注重數值計算；前者強調嚴格論證而后者允許近似求解。文獻[1]利用語義的方法提出了命題邏輯中的計量邏輯理論;文獻[2-7]將命題邏輯中計量邏輯理論進行了推廣;文獻[8-9]在模糊邏輯命題演算形式系統L的基礎上,討論了相應的謂詞演算理論;文獻[10-14]對謂詞邏輯公式真度概念作了簡單介紹;文獻[15]在謂詞邏輯系統中首次建立了公理化真度理論。

邏輯演算理論分為語義理論和語構理論,語義理論強調程度化,語構理論強調形式化。文獻[1]在二值命題演算中從基本概念的程度化入手,引入了二值命題公式真度的概念。命題邏輯中是基于語義的方法建立的真度,但是在謂詞邏輯中語義理論遠比命題邏輯復雜;因此,通過語義方法建立真度的概念難度很大。王國俊[15]通過概率計算給出了文字的完全閉包及其合取的真度值,在此基礎上建立了謂詞邏輯中公理化的真度理論。

本文論證了文字完全閉包對于析取運算具有分配性;文獻[15]中給出了不含相同謂詞符號廣義合取式的真度計算公式,以及合取范式的真度計算公式,但沒有證明，文中給出了2個計算公式的論證過程并舉例說明;最后,對文獻[15]中2個公式的等價性作了說明。

1 預備知識

首先,對謂詞邏輯中一些基本概念進行了介紹;其次,對φ(全體不含函數符號的一階閉邏輯公式之集)中公式真度的定義和真度映射τ具有的性質進行了說明。

定義1[1]一階語言由以下符號組成：

(1)變元符號:x1,x2,…。

(2)個體常元符號:a1,a2,…。

(6)全稱量詞符號:?。

定義3[1]Ψ中的原子公式及其否定叫做文字。

定義4[1]設A(p1,…,pn)∈F(S)((S=p1,p2,…(p1表示簡單命題)),F(S)是S生成的(→)型的自由代數)，則當A分別具有形式(Q11∧…∧Q1n)∨…∨(Qm1∧…∧Qmn)或(Q11∨…∨Q1n)∧…∧(Qm1∨…∨Qmn)時,稱A為析取范式或合取范式,這里Qij=Pj或Qij=Pj(j=1,…n;i=1,…m),在謂詞邏輯中Pj是原子公式。

定義5[1]設x1,…,xn是公式A中的全部自由出現的變元,則稱(?x1)…(?xn)A為A的完全閉包,記作clA。

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

(2)若α是φ中的定理，則τ(α)=1。

(3)τ(α)=1-τ(α)，α∈φ。

(4)τ(α→β)+τ(α)=τ(β→α)+τ(β)，α，β∈φ。

(5)τ(clQ)=1-τ(clQ)。

(6)在計算公式真度時,其中原子公式的變元可以相互替換。

定義7[15]設α，β∈φ,令ξ(α,β)=τ((α→β)∧(β→α)),稱ξ(α,β)為α與β之間的相似度。

命題1[15]真度映射τ具有以下性質:

(1)若α是矛盾式，則τ(α)=0。

(2)若α與β邏輯等價，則τ(α)=τ(β)。

(3)若τ(α→β)≤1，則τ(α)≤τ(β)。

(4)若τ(α)≥a,τ(α→β)≥b,則τ(β)≥a+b-1。

(5)若τ(α→β)≥a,τ(β→γ)≥b，則τ(α→γ)≥a+b-1。

(6)τ(α→γ)≥τ(α→β)+τ(β→γ)-1。

(7)τ(α∨β)+τ(α∧β)=τ(α)+τ(β)。

命題2[1](?xi)A→(?xi)A是邏輯有效公式。

命題3[1]設A是一階語言Ψ中的公式,則(?x1)(?x2)A≈(?x2)(?x1)A。(≈表示邏輯等價)

命題4[1](?xi)(A∧B)=(?xi)A∧(?xi)B。

2 一階邏輯公式中不含相同謂詞符號真度理論

王國俊[15]給出了不含相同謂詞符號廣義合取式的真度計算公式,以及合取范式的真度計算公式,但沒有證明。本節給出了2個計算公式的論證過程并舉例說明,以及對文獻[15]中部分細節進行了說明。A,B,C,D均為不含函數符號且不含量詞的公式。

引理1[1](?xi)(A→B)≈(A→(?xi)B),變元xi不在公式A中自由出現。

(?xi)(A→B)≈(A→(?xi)B),變元xi不在公式A中自由出現。

(?xi)(A→B)≈((?xi)A→B),變元xi不在公式B中自由出現。

(?xi)(A→B)≈((?xi)A→B),變元xi不在公式B中自由出現。

命題6完全閉包對于析取運算具有分配性，即clA∨clB≈cl(A∨B)。

證明clA∨clB=(?x1)…(?xn)A∨(?y1)…(?yn)B

≈(?x1)…(?xn)(A)→(?y1)…(?yn)B

≈(?y1)…(?yn)((?x1)…(?xn)(A)→B)

(變元yi不在公式A中自由出現)

≈(?x1)…(?xn)(?y1)…(?yn)((A)→B)

(變元xi不在公式B中自由出現)

≈(?x1)…(?xn)(?y1)…(?yn)(A∨B)

≈cl(A∨B)

命題7設S=∧{Ai1∨…Aiki|i=1,…,n|,這里Aij(i=1,…,n;j=1,…,ki)是不含相同謂詞符號的文字,則

證明∧{Ai1∨…∨Aiki}不含相同謂詞符號,對于不同的i,ki可能不同,故∧{Ai1∨…∨Aiki}是廣義合取式。

用數學歸納法進行證明:

i=1時,顯然成立。

當i=2時，即

S=(A11∨…∨A1k1)∧(A21∨…∨A2k2)

記

α=(A11∨…∨A1k1),β=(A21∨…∨A2k2)

由命題1和命題4知

τ(clS)=τ(clα)+τ(clβ)-τ(clα∨clβ)

即i=2時成立。

當i=3時,即

S=(A11∨…∨A1k1)∧(A21∨…∨A2k2)∧(A31∨…∨A3k3)

記

α1=(A11∨…∨A1k1)

β1=(A21∨…∨A2k2)

η1=(A31∨…∨A3k3)

由命題4知

τ(clS)=τ(clα1∧clβ1∧clη1)

由命題1知

τ(clS)=τ(clα1∧clβ1)+τ(clη1)-τ((clα1∧clβ1)∨clη1)

情形1:將(clα1∧clβ1)∨clη1的真度轉化為(clα1∨clη1)∧(clβ1∨clη1),記B=(α1∧β1)∨η1，(Ai1∨…∨Aiki)為1組, 由命題6知

τ(clB)=τ((clα1∧clβ1)∨clη1)

τ(clB)=τ((clα1∨clη1)∧(clβ1∨clη1))

=τ(clα1∨clη1)+τ(clβ1∨clη1)-τ(clα1∨clβ1∨clη1)

情形2:上述得到了2組相交與1組相并時的結果,后面的歸納中需要用這個結論。

τ(clS)=τ(clα1∧clβ1)+τ(clη1)-τ(clB)

即i=3時成立。

分析:根據2組相交與1組相并的結果推廣到n-1組相交與1組相并。

記C=(((A11∨…∨A1k1)∧…∧(An-11∨…∨An-1kn-1))∨(An1∨…∨Ankn)),即

成立。

當i=n+1時, 即

S=((A11∨…∨A1k1)∧…∧(An1∨…∨Ankn))∧(An+11∨…∨An+1kn+1)

τ(clS)=τ(cl((A11∨…∨A1k1)∧…∧

(An1∨…∨Ankn)))+

τ(cl(An+11∨…∨An+1kn+1))-

τ(cl((A11∨…∨A1k1)∧…∧

(An1∨…∨Ankn))∨

cl(An+11∨…∨A1kn+1))

τ(cl((A11∨…∨A1k1)∧…∧

(An1∨…∨Ankn))∨

cl(An+11∨…∨An+1kn+1))

當n組相交與1組相并時, 記

D=(((A11∨…∨A1k1)∧…∧(An1∨…∨

Ankn))∨(An+11∨…∨An+1kn+1))

D=(((A11∨…∨A1k1)∧…∧(An-11∨…∨

An-1kn-1)∧(An1∨…∨Ankn))∨

(An+11∨…∨An+1kn+1))

τ(clD)=τ(cl((A11∨…∨A1k1)∧…∧

(An1∨…∨Ankn))∨

cl(An+11∨…∨An+1kn+1))

τ(clD)=τ((cl(A11∨…∨A1k1)∧…∧

cl(An-11∨…∨An-1kn-1)∨

cl(An+11∨…∨An+1kn+1))∧

(cl(An1∨…∨Ankn)∨

cl(An+11∨…∨An+1kn+1)))

記

α2=(cl(A11∨…∨A1k1)∧…∧

cl(An-11∨…∨An-1kn-1)∨

cl(An+11∨…∨An+1kn+1))

β2=(cl(An1∨…∨Ankn)∨cl(An+11∨…∨An+1kn+1))

τ(clD)=τ(α2∧β2)

=τ(α2)+τ(β2)-τ(α2∨β2)

因此

τ(cl((A11∨…∨A1k1)∧…∧(An1∨…∨Ankn))∨cl(An+11∨…∨An+1kn+1))

分析:上述計算當n組相交與1組相并時，用到了n-1組相交與1組相并時的結果，所以

綜上所述,命題得證。

例1計算α=cl(C1∨C2…∨Cn)∧cl(D1∨D2∨…∨Dm)的真度,其中C1,C2,…,Cn和D1,D2,…,Dm是不含相同謂詞符號的文字,并計算當n=4,m=3時,α的真度。

解α≈β=cl((C1∨C2∨…Cn)∧

(D1∨D2∨…Dm))

根據命題7,得

σ=n+m,δ=(2n-1)(2m-1)

所以

命題7中,每個組合中相并的文字個數不相同,那么當命題7中每個組合相并的文字個數相同時,就有命題8。

證明根據命題7,得

例2計算α=cl(A1∨…∨A5)∧(B1∨…∨B5)∧(C1∨…∨C5)的真度,其中(A1,…,A5),(B1,…,B5),(C1,…,C5)是不含相同謂詞符號的文字。

解因為每個組合中相并的文字個數相同,所以根據命題8,得k=5,n=3。

證明R=(Q11∧…∧Q1k)∨…∨(Qm1∧…∧Qmk),其中Qij為文字。

用數學歸納法證明:

m=1時,顯然成立。

當m=2時,R=(Q11∧…∧Q1k)∨(Q21∧…∧Q2k), 記

A=(Q11∧…∧Q1k)

B=(Q21∧…∧Q2k)

則

τ(clR)=τ((clA)∨(clB))

=τ(clA)+τ(clB)-τ(cl(A∧B))

分析:由于A∧B=(Q11∧…∧Q1k∧Q21∧…∧Q2k)中必含原子公式Q及其否定Q,故A∧B為矛盾式，所以τ(cl(A∧B))=0。故

故m=2時成立。

假設當m=n時成立。此時

當m=n+1時,有

令

C=(Q11∧…∧Q1k)∨…∨

D=(Qn+11∧…∧Qn+1k)

則

τ(clR)=τ(clC∨clD)

=τ(clC)+τ(clD)-τ(cl(C∧D))

分析:由于

C∧D=((Q11∧…∧Q1k)∨…∨(Qn1∧…∧Qnk))∧

中必含原子公式Q及其否定Q,所以

τ(cl(C∧D))=0

故

τ(clR)

即

所以命題得證。

分析:命題9與命題8形式上看起來非常相似,但其實它們有很大的差別。命題8中要求文字中不含有相同的謂詞符號,而在命題9中則要求文字含有相同的謂詞符號(因為命題9是合取范式,范式具有很強的條件)。

引理2[16](量詞轄域擴縮律)A(x)是任一一階公式,B是任一不含自由變量x的一階公式。

(1)?(x)A(x)∧B≈?(x)(A(x)∧B)。

(2)?(x)A(x)∨B≈?(x)(A(x)∨B)。

(3)?(x)A(x)∧B≈?(x)(A(x)∧B)。

(4)?(x)A(x)∨B≈?(x)(A(x)∨B)。

命題10設A和B是不同的一元謂詞符號，令

α=(?x)A(x)→(?y)B(y)

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

則α與β是邏輯等價的。

證明(?x)A(x)→(?y)B(y)

(A中不含自由變量y)

(B中不含自由變量x)

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

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

即α≈β。

例3設A和B是不同的一元謂詞符號，令α=(?x)A(x),β=(?y)B(y)，求ξ(α,β)。

解ξ(α,β)=τ((α→β)∧(β→α))

=τ(((?x)A(x)→(?y)B(y))∧((?y)B(y)→(?x)A(x)))

=τ(((?x)(?y)(A(x)→B(y)))∧((?x)(?y)(B(y)→A(x))))

=τ(cl((A(x)→B(y))∧(B(y)→A(x))))

=τ(cl((A(x)∨B(y))∧

=τ(cl((A(x)∨B(y))∧

(A(x)∨B(y))))

命題11設公式為?(x)A(x)∧?(x)(A(x))，則它是矛盾式。

證明?(x)A(x)∧?(x)A(x)

因為?(x)A(x)→?(x)A(x)是邏輯有效的,所以是定理,從而(?(x)A(x)→?(x)A(x))是矛盾式。

3 結語

在不含函數符號的一階閉邏輯公式中,本文討論真度的可計算性問題,依據不出現相同謂詞符號文字的完全閉包的合取真度,證明了一階閉邏輯公式中不含相同謂詞符號真度的可計算性公式。如何將本文的結果進一步推廣到允許含有函數符號的情形是下一步進行的研究課題,值得關注。