一階邏輯中幾類特殊公式的真度計(jì)算方法

馬 碩，惠小靜，郝 嬌

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

以王國(guó)俊為首的學(xué)者提出了計(jì)量邏輯學(xué)理論［1］，并建立了經(jīng)典邏輯和模糊邏輯中公式真度理論［2-3］。這些理論很快引起了學(xué)術(shù)界的廣泛關(guān)注，以此為基礎(chǔ)大量學(xué)者針對(duì)不同的命題邏輯系統(tǒng)提出了公式真度的概念和基于真度的程度化推理方法［4-10］。不難發(fā)現(xiàn)以上成果都是在各種命題邏輯系統(tǒng)中基于語(yǔ)義方法建立的，由于一階邏輯的語(yǔ)義理論遠(yuǎn)遠(yuǎn)較命題邏輯復(fù)雜，要在謂詞邏輯中從語(yǔ)義途徑建立真度理論并不容易，僅有少數(shù)學(xué)者做出一些嘗試性的研究成果［11-13］。

本文的出發(fā)點(diǎn)是以全體不含函數(shù)符號(hào)的一階閉邏輯公式之集Ф中公式的真度定義和真度映射τ具有的MP規(guī)則和真度運(yùn)算性質(zhì)［14］，以及謂詞邏輯系統(tǒng)￡?的公理［15］為鋪墊，對(duì)BL?的重要擴(kuò)張?ukasiewicz謂詞邏輯系統(tǒng)??中的特殊公式展開(kāi)公理化真度研究。其中￡是基本命題邏輯BL的模式擴(kuò)張，謂詞邏輯系統(tǒng)￡?公理包含：ⅰ）￡中的公理，其中A，B，C為謂詞公式；ⅱ）帶有量詞的公理。從而為之后開(kāi)展相關(guān)研究奠定基礎(chǔ)。

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

下面首先對(duì)Ф中公式真度的定義和真度映射τ具有的性質(zhì)進(jìn)行說(shuō)明，設(shè)Ф表示全體不含函數(shù)符號(hào)的一階閉邏輯公式之集，其中A，B，C等表示Ф中的一階邏輯公式。

定義1.1［14］稱映射τ：Ф→[0，1]為公理化真度映射，若以下條件成立：

（K1）不出現(xiàn)相同謂詞符號(hào)的N個(gè)文字的完全閉包的合取的真度等于

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

（K3）τ(?A)=1-τ(A)，A∈Ф；

（K4）τ（A→B）+τ（A）=τ（B→A）+τ（B），A，B∈Ф；

（K5）τ(cl(?Q))=1-τ(cl Q)；

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

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

命題1.1［14］真度映射τ具有以下性質(zhì)：

?。┤鬉是矛盾式，則τ(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)。

由于?ukasiewicz謂詞邏輯是BL謂詞邏輯的擴(kuò)張，因此下面對(duì)謂詞邏輯的模式擴(kuò)張做一簡(jiǎn)單介紹。

定義1.2［15］設(shè)￡是基本命題邏輯BL的模式擴(kuò)張。謂詞邏輯系統(tǒng)￡?的公理包含以下兩類：

?。曛械墓?，其中A，B，C為謂詞公式：

（BL1）(A→B)→((B→C)→(A→C))；

（BL2）A&B→A；

（BL3）A&B→B&A；

（BL4）A&(A→B)→B&(B→A)；

（BL5a）(A→(B→C))→(A&B→C)；

（BL5b）(A&B→C)→(A→(B→C))；

（BL6）((A→B)→C)→(((B→A)→C)→C)；

ⅱ）帶有量詞的公理：

（?1）(?x)A(x)→A(t)（在A(x)中 可 用t替代x）；

（?1）A(t)→(?x)A(x)（在A(x)中 可 用t替代x）；

（?2）(?x)(B→A)→(B→(?x)A)（x在B中不自由）；

（?2）(?x)(A→B)→((?x)A→B)（x在B中不自由）；

（?3）(?x)(A∨B)→((?x)A∨B)（x在B中不自由）。

系統(tǒng)￡?的推理規(guī)則有以下兩條：

MP規(guī)則：由A，A→B推出B；

推廣規(guī)則：由A推出(?x)A。

下面是對(duì)?ukasiewicz謂詞演算系統(tǒng)中的公理和定理的說(shuō)明。

為了將?ukasiewicz邏輯公理化，只需對(duì)BL的公理增加一個(gè)雙重否定公理：

稱BL+(??)為命題演算系統(tǒng)，簡(jiǎn)稱為?。

定義1.3［15］以下公式為?ukasiewicz公理：

命題1.2［15］ⅰ）?├??A?A；

ⅳ）?├((A→B)→B)→((B→A)→A)。

命題1.3［15］由公理（?1）~（?4）與推理規(guī)則MP構(gòu)成的公理系統(tǒng)記作?′。以下公式是系統(tǒng)?′中的定理：

?。〢→((A→B)→B)；

ⅱ）(A→(B→C))→(B→(A→C))；

ⅲ）A→A；

ⅳ）0→A；

ⅴ）??A→A；

ⅵ）(A→?B)→(B→?A)；

ⅶ）A→??A。

定義1.4［15］在?′中，按如下形式引入新的聯(lián)結(jié)詞，∧，∨和：

2 公理化真度的計(jì)算方法

下面的研究均在Ф中展開(kāi)，即A，B，C均為不含函數(shù)符號(hào)的閉公式。

定理2.1設(shè)A，B是?ukasiewicz中的公式，則有

證明首證(B→?A)→((B→A)→?B)是定理：

由命題1.3的?。┑茅繟→((A→B)→B)，├?A→((?A→?B)→?B)；

由（BL2）得├?(A&B)→((?A→?B)→?B)；

由（BL3）得├?(B&A)→((?A→?B)→?B)；

由命題1.2的ⅱ）、ⅲ）得

再證τ(((B→A)→?B)→(B→?A))=

由（K2）知

由命題1.1的ⅲ）知

由（K4）知

即τ(((B→A)→?B)→(B→?A))=τ(B→?A)-τ((B→A)→?B)+1。得證。

例2.1：求命題1.2的ⅳ）((A→B)→B)→((B→A)→A)中τ(((B→A)→A)→((A→B)→B))的值。

解由命題1.2的ⅳ）知（（A→B）→B）→（（B→A）→A）是定理。

由（K2）得

由（K4）得

即τ(((B→A)→A)→((A→B)→B))=τ((A→B)→B)-τ((B→A)→A)+1。

由定義1.4得τ((A→B)→B)=τ(A∨B)；

同理τ((B→A)→A)=τ(B∨A)。

由命題1.1的ⅶ）得

同理τ(B∨A)=τ(B)+τ(A)-τ(B∧A)。

所以

定理2.2設(shè)A，B，C是?ukasiewicz中的公式，則有

證明首證(?B→(C→A))→(?A→(C→B))是定理：

由命題1.3的ⅱ）得├（A→（B→C））→（B→（A→C）），├(?A→(?B→?C))→(?B→(?A→?C))；

由（?3）得

由命題1.2的ⅲ）得├((C&?B)→A)→((C&?A)→B)；

由（BL3）得├（（?B&C）→A）→（（?A&C）→B）；

由（BL5b）得├(?B→(C→A))→(?A→(C→B))。

再證τ(?B→(C→A))≤(?A→(C→B))：

由（K2）得τ(?B→(C→A))→(?A→(C→B))=1；

由命題1.1的ⅲ）得

定理2.3若A→B為定理，當(dāng)τ(A)≥a，τ(B→A)≤b時(shí)，τ(B)≥a-b+1。

證明由（K2）得τ(A→B)=1；

由（K4）得

τ(A→B)+τ(A)=τ(B→A)+τ(B)；

則τ(B)=τ(A)-τ(B→A)+τ(A→B)≥a-b+1。

例2.2設(shè)A，B，C是?ukasiewicz中的公式，則有τ(B→(A→C))≥a-b+1。

證明由命題1.3的ⅱ）知(A→(B→C))→(B→(A→C))為定理。

由（K2）得

由（K4）得

則τ(B→(A→C))=τ(A→(B→C))-τ((B→(A→C))→(A→(B→C)))+τ((A→(B→C))→(B→(A→C)))。

若τ(A→(B→C))≥a，τ((B→(A→C))→(A→(B→C)))≤b，

則τ(B→(A→C))≥a-b+1。

3 結(jié)語(yǔ)

本文根據(jù)王國(guó)俊提出的Ф中公理化真度定義和真度映射τ具有的性質(zhì)，對(duì)謂詞邏輯系統(tǒng)??幾類特殊公式的真度計(jì)算方法進(jìn)行了研究，將復(fù)雜公式的真度轉(zhuǎn)換為幾個(gè)簡(jiǎn)單公式的真度進(jìn)行運(yùn)算。后續(xù)值得關(guān)注的研究?jī)?nèi)容是公式的相似度、偽距離以及相容度的運(yùn)算性質(zhì)。