MTL?謂詞邏輯系統(tǒng)公理化真度的運(yùn)算性質(zhì)研究

王 波, 惠小靜, 魯 星

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

作為非經(jīng)典數(shù)理邏輯的一個(gè)重要分支,模糊邏輯是邏輯系統(tǒng)研究的一個(gè)重要方向.受連續(xù)三角模結(jié)構(gòu)定理的啟發(fā),捷克科學(xué)院院士Petr Hájek于1998年提出基本邏輯的形式系統(tǒng)BL[1],將BL系統(tǒng)弱化就形成了MTL系統(tǒng).該系統(tǒng)是由Esteva 和Godo于2001年提出的[2],許多專家在此基礎(chǔ)上進(jìn)行研究,得到了一些研究成果[3—12].

與命題邏輯MTL系統(tǒng)相對應(yīng)的是謂詞邏輯系統(tǒng)MTL?,謂詞邏輯系統(tǒng)MTL?包含基本命題邏輯系統(tǒng)MTL以及含有量詞的公理.目前,計(jì)量化研究主要是在命題邏輯MTL系統(tǒng)中進(jìn)行的[13—14],對謂詞邏輯系統(tǒng)MTL?進(jìn)行計(jì)量化研究是一個(gè)重要課題.

命題邏輯的計(jì)量化從基本概念的程度化入手引進(jìn)了命題邏輯公式真度的概念,是基于語義的方法建立的,但在謂詞邏輯中其語義理論遠(yuǎn)比命題邏輯復(fù)雜,因此采用語義的方法建立真度的概念難度很大.王國俊在文獻(xiàn)[15]中提供了一種用公理化的方法建立一階邏輯公式的真度理論.本文在此基礎(chǔ)上,結(jié)合謂詞邏輯系統(tǒng)MTL?的相關(guān)公理及定理,研究謂詞邏輯系統(tǒng)MTL?的公理化真度.文中首先介紹了公理化真度的概念,其次介紹了謂詞邏輯系統(tǒng)MTL?;最后，論證了形如((A→B)→(A→C))→(B→C)及(?x)A→B等公式真度計(jì)算的轉(zhuǎn)化方法.

1 預(yù)備知識

文獻(xiàn)[15]采用公理化方法給出了謂詞邏輯公理化真度的概念.該公理化真度具有普適性,在此基礎(chǔ)上相關(guān)理論的展開采用嚴(yán)格的邏輯推理而不再借助語義理論和概率計(jì)算.由于謂詞邏輯的復(fù)雜性,公理化真度是在不含函數(shù)符號的一階閉邏輯公式中展開的.Ф表示全體不含函數(shù)符號的一階閉邏輯公式之集,下面首先對Ф中的公式真度的定義和真度映射τ具有的性質(zhì)進(jìn)行說明,其中A,B,C等表示Ф中的一階邏輯公式.

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

(ⅰ)變元符號:x1,x2,….

(ⅱ)個(gè)體常元符號:a1,a2,….

(ⅵ)全稱量詞符號:?.

定義2[16]設(shè)Ψ是一階語言,則Ψ中的項(xiàng)定義如下:

(ⅰ)變元和Ψ中的個(gè)體常元是項(xiàng).

(ⅲ)Ψ中的項(xiàng)均由(ⅰ)與(ⅱ)的方式生成.

(ⅰ)原子公式是合式公式.

(ⅱ)若A與B是合式公式,則A,A→B與(?x)A也都是合式公式.

(ⅲ)合式公式均由(ⅰ)與(ⅱ)的方式生成.

定義4[16]設(shè)A(xi)是含有變元xi的公式,t是一個(gè)項(xiàng).若下列條件之一滿足，則稱t關(guān)于A(xi)中的xi是自由的:

(ⅰ)xi不是A(xi)中的自由變元；

(ⅱ)xi是A(xi)中的自由變元且t中的變元在A(t)中都是自由變元.

定義5[16]一階語言Ψ中不含自由出現(xiàn)的變元的公式稱為閉公式.

定義6[16]Ψ中的原子公式及其否定稱為文字.設(shè)x1,…,xn是公式A中的全部自由出現(xiàn)的變元,則稱(?x1)…(?xn)A為A的完全閉包,記作clA.

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

(K2) 若A是Ф中的定理,則τ(A)=1；

(K3)τ(A)=1-τ(A),A∈Ф；

(K4)τ(A→B)+τ(A)=τ(B→A)+τ(B),A,B∈Ф；

(K5)τ(cl(A))=1-τ(clA)；

(K6) 在計(jì)算公式的真度時(shí),其中原子公式中的變元可相互替換.

以定義7為基礎(chǔ),文獻(xiàn)[15]中證明了公理化真度具有如下性質(zhì).

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

(ⅰ) 若A是矛盾式,則τ(A)=0；

(ⅱ) 若A與B是邏輯等價(jià),則τ(A)=τ(B)；

(ⅲ) 若τ(A→B)=1,則τ(A)≤τ(B)；

(ⅳ) 若τ(A)≥a,τ(A→B)≥b,則τ(B)≥a+

b-1；

(ⅴ) 若τ(A→B)≥a,τ(B→C)≥b,則τ(A→C)≥a+b-1；

(ⅵ)τ(A→C)≥τ(A→B)+τ(B→C)-1；

(ⅶ)τ(A∨B)+τ(A∧B)=τ(A)+τ(B).

接下來介紹謂詞演算系統(tǒng)MTL?的公理和部分定理.

定義8[3]謂詞演算系統(tǒng)MTL?的公理為MTL的10條公理再加上關(guān)于量詞的公理.

(ⅰ) 命題演算系統(tǒng)MTL的公理:

(MTL1) (A→B)→((B→C)→(A→C))；

(MTL2)A&B→A；

(MTL3)A&B→B&A；

(MTL4)A∧B→A；

(MTL5)A∧B→B∧A；

(MTL6)A&(A→B)→(A∧B)；

(MTL7a) (A→(B→C))→(A&B→C)；

(MTL7b) (A&B→C)→(A→(B→C))；

(MTL8) ((A→B)→C)→(((B→A)→C)→C)；

(MTL9) 0→A.

(ⅱ)帶有量詞的公理:

(?1)(?x)A(x)→A(t),其中項(xiàng)t對于A(x)中的x可替換；

(?1)A(t)→(?x)A(x),其中項(xiàng)t對于A(x)中的x可替換；

(?2)(?x)(A→B)→(A→(?x)B),其中x在A中不自由出現(xiàn)；

(?2)(?x)(A→B)→((?x)A→B),其中x在B中不自由出現(xiàn)；

(?3)(?x)(A∨B)→((?x)A∨B),其中x在B中不自由出現(xiàn).

系統(tǒng)MTL?的推理規(guī)則:

MP規(guī)則[3]: 由A,A→B推出B.

推廣規(guī)則[3]: 由A推出(?x)A.

HS規(guī)則[2]:A→B,B→C可得A→C.

定理1[3]以下公式在MTL?中可證:

(ⅰ)(A→(B→C))→(B→(A→C))；

(ⅱ)A→A；

(ⅲ)(?x)(A∧B)≡((?x)A∧(?x)B)；

(ⅳ) (?x)(C→A)→(C→(?x)A)，其中x在C中不自由出現(xiàn).

(ⅴ) (?x)(A→C)→((?x)A→C)，其中x在C中不自由出現(xiàn).

2 MTL?系統(tǒng)的公理化真度計(jì)算轉(zhuǎn)化方法

本節(jié)將在公理化真度定義7的基礎(chǔ)上結(jié)合謂詞演算系統(tǒng)MTL?,研究MTL?系統(tǒng)中公理化真度,給出了真度計(jì)算的轉(zhuǎn)化公式.以下討論均在Ф中展開,即A,B,C均為不含函數(shù)符號的閉公式.

定理2

τ(((A→B)→(A→C))→(B→C))=

τ(B→C)-τ((A→B)→(A→C))+1.

證明首先證明(B→C)→((A→B)→(A→C))為定理:

(ⅰ)由(MTL1)得(A→B)→((B→C)→(A→C)).

(ⅱ)由定理1(ⅰ)得

((A→B)→((B→C)→(A→C)))→

((B→C)→((A→B)→(A→C))).

(ⅲ)由(ⅰ),(ⅱ)及MP得(B→C)→((A→B)→(A→C)).

由(K2)知τ((B→C)→((A→B)→(A→C)))=1.由(K4)知

τ(((A→B)→(A→C))→(B→C))+

τ((A→B)→(A→C))=

τ((B→C)→((A→B)→(A→C)))+τ(B→C).

所以

τ(((A→B)→(A→C))→(B→C))=

τ(B→C)-τ((A→B)→(A→C))+1.

注1可見,形如((A→B)→(A→C))→(B→C)公式的真度可通過轉(zhuǎn)化為(B→C)與((A→B)→(A→C))的真度進(jìn)行計(jì)算,下面舉例論證.

例1計(jì)算

τ((((?x)A→(?x)A)→((?x)A→

的值.

解由定理2知

τ((((?x)A→(?x)A)→

((?x)A→(?x)A))→

((?x)A→(?x)A))=

τ((?x)A→(?x)A)-

τ(((?x)A→(?x)A)→

((?x)A→(?x)A))+1.

由定理1(ⅲ)知(?x)A→(?x)A是定理. 由(K2)知

τ((?x)A→(?x)A)=1.

(1)

由定理2(ⅲ)知(B→C)→((A→B)→(A→C))為定理,因此,同理可證

((?x)A→(?x)A)→

(((?x)A→(?x)A)→((?x)A→(?x)A))

是定理.由(K2)知

τ(((?x)A→(?x)A)→(((?x)A→

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

由命題1(ⅲ)知

τ((?x)A→(?x)A)≤τ(((?x)A→

(?x)A)→((?x)A→(?x)A)).

由于0≤τ(((?x)A→(?x)A)→((?x)A→(?x)A))≤1，由 (1) 式知τ((?x)A→(?x)A)=1.從而τ(((?x)A→(?x)A)→((?x)A→(?x)A))=1.所以

τ((((?x)A→(?x)A)→

((?x)A→(?x)A))→

((?x)A→(?x)A))=1-1+1=1，

即τ((((?x)A→(?x)A)→((?x)A→(?x)A))→

((?x)A→(?x)A))的取值為1.

定理3τ(A)=τ((?x)A).

證明首先證明A→(?x)A是定理:

(ⅰ) 由定理1(ⅱ)得A→A；

(ⅱ)由(ⅰ)和推廣規(guī)則得(?x)(A→A)；

(ⅲ)由 (?2)得(?x)(A→A)→(A→(?x)A)，其中x在A中不自由出現(xiàn)；

(ⅳ)由(ⅱ),(ⅲ)及MP得A→(?x)A.

由(K2)知τ(A→(?x)A)=1.由命題1(ⅲ)知τ(A)≤τ((?x)A).由公理(?1)及(K2)知τ((?x)A→A)=1.由命題1(ⅲ)知τ((?x)A)≤τ(A).所以τ(A)=τ((?x)A).

定理4τ((?x)((?x)A∨(?x)B))=τ((?x)A∨(?x)B).

證明首先證明(?x)((?x)A∨(?x)B)→(?x)A∨(?x)B為定理.由(?1)得

(?x)((?x)A∨(?x)B)→(?x)A∨(?x)B.

由(K2)知τ((?x)((?x)A∨(?x)B)→(?x)A∨(?x)B)=1.由命題1(ⅲ)知

τ((?x)((?x)A∨(?x)B))≤τ((?x)A∨(?x)B).

接下來證明(?x)A∨(?x)B→(?x)((?x)A∨(?x)B)為定理.由定理3(ⅳ)得

(?x)A∨(?x)B→(?x)((?x)A∨(?x)B).

(2)

(2)式與定理3(ⅳ)中A→(?x)A形式相同.由(K2)知

τ((?x)A∨(?x)B→(?x)((?x)A∨(?x)B))=1.

由命題1(ⅲ)知

τ((?x)A∨(?x)B)≤τ((?x)((?x)A∨(?x)B)).

所以τ((?x)((?x)A∨(?x)B))=τ((?x)A∨(?x)B).

注2由定理1(ⅲ)知τ((?x)(A∧B))=τ((?x)A∧(?x)B).可見交與并的分配對于真度的關(guān)系式二者是有差別的.

定理5τ(A→(?x)B)=τ((?x)A→B).

證明首先證明(A→(?x)B)→(?x)(A→B)為定理.

(ⅰ) 由(?1)得(?x)B→B.

(ⅱ) 由定理2(ⅲ)得

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

(3)

(3)式與定理2(ⅲ)中(B→C)→((A→B)→(A→C))形式相同.

(ⅲ)由(ⅰ),(ⅱ)及MP得(A→(?x)B)→(A→B).

(ⅳ)由定理3(ⅳ)得

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

(4)

(4)式與定理3(ⅳ)中A→(?x)A形式相同.

(ⅴ) 由(ⅲ),(ⅳ)及HS得 (A→(?x)B)→(?x)(A→B).

由(K2)知τ((A→(?x)B)→(?x)(A→B))=1.由命題1(ⅲ)知

τ(A→(?x)B)≤τ((?x)(A→B)).

由(?2)及(K2)知

τ((?x)(A→B)→(A→(?x)B))=1.

由命題1(ⅲ)知

τ((?x)(A→B))≤τ(A→(?x)B).

所以τ(A→(?x)B)=τ((?x)(A→B)).

接下來證明((?x)A→B)→((?x)(A→B))是定理.

(ⅰ)由(?1)得A→(?x)A.

(ⅱ)由(MTL1)得

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

(ⅲ) 由(ⅰ),(ⅱ)及MP 得

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

(ⅳ) 由定理3(ⅳ)得

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

(5)

(5)式與定理3(ⅳ)中A→(?x)A形式相同.

(ⅴ) 由(ⅲ),(ⅳ)及HS 得

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

由(K2)知τ(((?x)A→B)→(?x)(A→B))=1.由命題1(ⅲ)知

τ((?x)A→B)≤τ((?x)(A→B)).

由(?2)及(K2)知τ((?x)(A→B)→((?x)A→B))=1.由命題1(ⅲ)知

τ((?x)(A→B))≤τ((?x)A→B).

所以τ((?x)(A→B))=τ((?x)A→B)，從而τ(A→(?x)B)=τ((?x)A→B).

定理6τ((?x)A→B)=τ(A→(?x)B).

證明首先證明(B→(?x)A)→((?x)(B→A))是定理.

(ⅰ)由定理1(ⅱ)得A→A.

(ⅱ)由(ⅰ)及推廣規(guī)則得(?x)(A→A).

(ⅲ)由(?2)得(?x)(A→A)→((?x)A→A)，其中x在A中不自由出現(xiàn).

(ⅳ) 由(ⅱ),(ⅲ)及MP 得(?x)A→A.

(ⅴ)由定理2(ⅲ)得

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

(6)

(6)式與定理2(ⅲ)中(B→C)→((A→B)→(A→C))形式相同.

(ⅵ) 由(ⅳ),(ⅴ)及MP得

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

(ⅶ) 由(?1)得(B→A)→(?x)(B→A).

(ⅷ)由(ⅵ),(ⅶ)及HS得

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

由(K2)知τ((B→(?x)A)→(?x)(B→A))=1.由命題1(ⅲ)知

τ(B→(?x)A)≤τ((?x)(B→A)).

由定理1(ⅳ)及(K2)知

τ((?x)(B→A)→(B→(?x)A))=1.

由命題1(ⅲ)知

τ((?x)B→A)≤τ(B→(?x)A).

所以τ((?x)(B→A))=τ(B→(?x)A).

接下來證明((?x)A→B)→((?x)(A→B))是定理.

(ⅰ) 由定理3(ⅳ)得

A→(?x)A.

(7)

(7)式與定理3(ⅳ)中A→(?x)A形式相同.

(ⅱ)由(MTL1)得

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

(ⅲ) 由(ⅰ),(ⅱ)及MP得

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

(ⅳ) 由(?1)得

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

(ⅴ) 由(ⅲ),(ⅳ)及HS得

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

由(K2)知τ(((?x)A→B)→(?x)(A→B))=1.由命題1(ⅲ)知

τ((?x)A→B)≤τ((?x)(A→B)).

由定理1(ⅴ)及(K2)知τ((?x)(A→B)→((?x)A→B))=1.由命題1(ⅲ)知τ((?x)(A→B))≤τ((?x)A→B).所以τ((?x)A→B)=τ((?x)(A→B))，從而τ((?x)A→B)=τ(A→(?x)B).

注3定理5和定理6給出了?與?之間真度的相互轉(zhuǎn)化關(guān)系,方便后續(xù)學(xué)者計(jì)算真度.

例2計(jì)算τ(A)+τ(B)的值.

解由(K4)知

τ((?x)A→B)+τ((?x)A)=

τ(B→(?x)A)+τ(B).

由定理5知τ(B→(?x)A)=τ((?x)B→A)，所以

τ((?x)A→B)+τ((?x)A)=

τ((?x)B→A)+τ(B).

由定理6知τ((?x)A→B)=τ(A→(?x)B)，所以

τ(A→(?x)B)+τ((?x)A)=

τ((?x)B→A)+τ(B).

由(K4)知

τ(A→(?x)B)+τ(A)=

τ((?x)B→A)+τ((?x)B)，

所以

τ(A→(?x)B)=

τ((?x)B→A)+τ((?x)B)-τ(A)，

從而

τ((?x)B→A)+τ((?x)B)-τ(A)+

τ((?x)A)=τ((?x)B→A)+τ(B).

3 結(jié)語

本文在文獻(xiàn)[15]的基礎(chǔ)上研究了謂詞演算系統(tǒng)MTL?的公理化真度及其一些運(yùn)算性質(zhì).筆者將在另文中討論以公理化真度為基礎(chǔ)建立邏輯度量空間并展開相容度及發(fā)散度等相關(guān)問題.