一階邏輯公式相對真度的計算形式

秦曉燕，徐 揚

1.山西師范大學數學與計算機科學學院，山西臨汾041004

2.西南交通大學智能控制開發(fā)中心，成都610031

一階邏輯公式相對真度的計算形式

秦曉燕1，2，徐 揚2

1.山西師范大學數學與計算機科學學院，山西臨汾041004

2.西南交通大學智能控制開發(fā)中心，成都610031

對二值謂詞邏輯中一階公式關于有限解釋的相對真度定義進行了簡化，給出其計算形式。指出一階非閉邏輯公式的相對真度只與其中自由出現(xiàn)的變元有關，而非只與其中的自由變元有關；證明可以增加公式中出現(xiàn)的變元個數，而不會改變公式的相對真度，從而可以依據相對真度的計算形式橫向研究公式間的相對真度問題。

相對真度；有限解釋；自由出現(xiàn)變元；計量謂詞邏輯

1 引言

人工智能是研究如何使計算機模擬人的思維過程和智能行為的學科，其中普遍采用的是精確的、形式化的邏輯推理方法。但是，本質上來講，人腦的思維模式和推理方法是帶有不確定性的近似推理，而不是精確化的推理。因此，近年來程度化的推理越來越受到人們的關注。關于計量邏輯的研究是其中一個重要的研究方向。計量邏輯[2]的內容分五部分：邏輯公式的真度理論、邏輯公式間的相似度理論、邏輯度量空間、近似推理理論以及理論的相容度理論，其中邏輯公式的真度理論是整個計量邏輯理論的奠基石。另一方面，計量邏輯由計量命題邏輯與計量謂詞邏輯組成，其中計量命題邏輯已得到深入而系統(tǒng)的大量研究成果（比如，文[2-12]），但計量謂詞邏輯卻只有零星成果[13-17]。

實際上，由于一階邏輯中解釋的復雜性，現(xiàn)有的關于計量謂詞邏輯的研究成果也都是在解釋域有限的局限下得到的[13-17]。除文獻[13]以語構角度提出一階公式的公理化真度外，文獻[14-17]均以語義角度出發(fā)，基于公式在有限解釋下的相對真度出發(fā)展開研究，并且相對真度的定義都是以測度形式給出的。本文首先給出有限解釋下一階公式相對真度的計算定義形式，簡化了其計算過程與證明過程。接著，證明了賦值是否滿足公式完全取決于其在公式中自由出現(xiàn)的變元上的賦值，而非文獻[1]中所指出的“由賦值在自由變元上的賦值決定”。最后，證明了可以適當增加公式中出現(xiàn)的變元個數而不改變其相對真度，從而更好地證明關于相對真度的一些性質，為進一步研究一階公式的各種真度理論提供更為堅實的理論基礎。

2 預備知識

設L是不含函數符號的一階語言（這是合理的，在文獻[18]中證明了這種語言的一般性），M=(M，(rP)P，(mc)c)是L的一個解釋，其中M是一個非空集合，稱為解釋M的論域，rP是與謂詞符號P對應的上M的關系，mc是與個體常元c對應的M中的元。L在M中的賦值v：T→M是從L的項集T到M的一個映射，且滿足v(c)=mc，v(x)∈M，其中c為個體常元，x為變元，且?t∈T，t為個體常元或變元。在公式(?xi)A中，A叫做?xi的轄域。這時公式A中若有變元xi，則該xi叫約束變元。又，?xi中的xi也叫約束變元。不是約束變元的變元叫自由變元。

在本文中，記全體謂詞公式之集為F，全體L在M中的賦值之集為ΩM。又，記全體變元集為S，記全體論域為非空有限集的解釋之類為Mf，且?v∈ΩM，若v滿足公式A，記為‖‖AM，v=1，否則記為‖‖AM，v=0。記非空有限論域M的勢為|M|。

其中m=1，2，…。μ被稱為{μn}∞n=1的無限積，概率測度空間(X，A，μ)稱為概率測度空間{(Xn，An，μn)}∞n=1的笛卡爾乘積，簡記為X。

設M=(M，(rP)P，(mc)c)∈Mf，令Xn=M，μn是Xn上的均勻分布概率測度，即μ(X)=1，μ(?)=0，μ(F)=nnnn這里F?Xn(n=1，2，…)。又因為M有限，所以任一Mm的子集都可測(m=1，2，…)。由定理2.1，在XM==M∞上存在{的無限積測度μM，并且對任一Mm的子集E，其測度μM(E)均可通過式（1）來計算(m=1，2，…)。另外，由于個體常元在解釋M下的值固定，即對任意一階語言L在解釋M中的賦值v，v(c)=mc固定不變，故L在M中的賦值v完全v由在變元集S={x1，x2，…}上的限制v|S而定。因此設v∈ΩM，v(xk)=vk(k=1，2，…)，則有唯一的v=(v1，v2，…，vn，…)∈XM與之對應；反過來，若v=(v1，v2，…，vn，…)∈XM，則存在唯一的v∈ΩM，使得v(xk)=vk(k=1，2，…)。因此在ΩM與XM之間存在一一對應φ，其中φ(v)=v。

定義2.2[14]設M∈Mf，A∈F。定義[A]M與τM(A)如下：

[A]M={v∈XM|v∈ΩM，‖A‖M，v=1}

則稱τM(A)為公式A關于解釋M的相對真度。

命題2.3[14]設M∈Mf，A，B∈F。則

（i）0≤τM() A≤1；

（ii）τM(?A)=1-τM(A)；

（iii）若A～B，則τM(A)=τM(B)。

3 相對真度的計算定義形式

在定義2.2中，一階公式關于有限解釋的相對真度是以測度形式給出的，而且其中的測度是均勻概率測度，即對任意集合F?XM，則μM(F)=。所以，可以直接給出它的數值計算形式，這樣，會使一階公式關于有限解釋的相對真度的實際計算與相關命題證明更加簡捷明了。事實上，對于某一個具體的一階公式A，其中出現(xiàn)的變元是有限的，假設為x1，x2，…，xk(k=1，2，…)，那么在某個已知有限解釋M下，對任意賦值v∈ΩM，v是否滿足公式A完全由v對A上出現(xiàn)的所有變元的賦值決定。所以，式（2）中的[A]M可以更具體的定義為：[A]M={(v(x1),v(x2),…,v(xk))∈Mk|,v∈ΩM,‖‖AM，v=1}（3）

因此，若公式A中所有出現(xiàn)的變元為x1，x2，…，xk，則按照定義2.2，

也就是如下的公式關于有限解釋的數值計算形式：

定義3.1設M∈Mf，A∈F，且A中出現(xiàn)的變元共有k個。定義τM(A)如下：

其中[A]M定義為式（3），則稱τM(A)為公式A關于解釋M的相對真度。

注3.1由式（4），公式A關于有限解釋M的相對真度只與其中出現(xiàn)的謂詞符號與個體常元的解釋，以及A中出現(xiàn)的變元有關。但是，值得注意的是，它與變元的符號并沒有關系。也就是說，若x在公式A中出現(xiàn)，則將x換為不在A中出現(xiàn)的y后，公式A關于解釋M的相對真度不變。當然，這種變換只是保持其真度不變，而并不能使得變換前后的公式邏輯等價。

例3.1設L是一階語言，它有一個個體常元c，一個一元謂詞符號Q。M=(M，{rQ}，{mc})是一階語言L的一個解釋，其中M是一個非空有限集。現(xiàn)有B=Q(x)→(?x) Q(x)∈F，計算τM(B)。

解：公式B中只有一個變元x。

注意到，在解釋M下，對任意賦值v∈ΩM，‖(?x)Q(x)‖M，v=1當且僅當rQ=M。因此，有：

若rQ=M，則對任意賦值v∈ΩM，‖Q(x)‖M，v=1，且‖(?x)Q(x)‖M，v=1，從而，[B]M=M-?=M；

若rQ≠M，則對任意賦值v∈ΩM，均有‖(?x)Q(x)‖M，v=0，從而，[B]M=M-rQ。

由式（4），公式B關于解釋M的相對真度τM(B)為：

容易證明

命題3.1設M∈Mf，A，B∈F。A與B中出現(xiàn)的變元相同，且個數為k(k=1，2，…)。

（i）A是關于解釋M的真公式當且僅當[A]M=Mk；A是關于解釋M的假公式當且僅當[A]M=?；

（ii）若A是閉公式，則要么[A]M=Mk，要么[A]M=?；

（iii）若A與B邏輯等價，則[A]M=[B]M；

（iv）[?A]M=Mk-[A]M，[A∧B]M=[A]M∩[B]M，[A∨B]M=[A]M∪[B]M。

前面說到，對某個具體的一階公式A而言，在某個有限解釋M下，賦值v∈ΩM是否滿足公式A完全由v對A中出現(xiàn)的變元的賦值決定。實際上，可以更精確地說，v是否滿足公式A完全由v對A上自由出現(xiàn)的變元的賦值決定。在文獻[1]中有命題3.2.25：

“設L是一階語言，M是L的一個解釋，A∈F，v與w是L在M中的兩個賦值。如果對A中的每個自由變元xi都有v(xi)=w(xi)，則v滿足A當且僅當w滿足A?！?/p>

但是，這個命題是錯誤的?？梢耘e出一個反例來說明。設A=P(x，y)→(?x)Q(x)，解釋M下：論域M={0，1，2}，rP={(a，b)|a＜b}，rQ={a|a＞0}。顯然公式A中只有一個自由變元y，而變元x不是自由變元，但在A中自由出現(xiàn)1次。取解釋M下的兩個賦值v與w，使得v(y)= w(y)=1，并且v(x)=2，w(x)=0，則顯然有‖P(x，y)‖M，v=0，且‖P(x，y)‖M，w=1，而‖(?x)Q(x)‖M，v=‖(?x)Q(x)‖M，w=0。所以‖‖AM，v=1，但是‖‖AM，v=0。即：雖然v與w在A中每個自由變元的值都相等，但v與w并不同時滿足A。

記A=B→C，B，C中的自由變元之集分別為FA，F(xiàn)B，F(xiàn)C，則顯然應該有FA?FB∪FC。文獻[1]中命題3.2.25的證明錯誤之處就在于，誤認為FA=FB∪FC。比如，A=P(x，y)→(?x)Q(x)，其中B=P(x，y)，C=(?x)Q(x)，顯然，F(xiàn)A={y}，F(xiàn)B={x，y}，F(xiàn)C=?。所以FA?FB∪FC，而不是FA=FB∪FC。

具體來說，在文獻[1]命題3.2.25的證明中有：“（ii）設A是B→C且已證明v滿足B當且僅當w滿足B，v滿足C當且僅當w滿足C，則仍易推出v滿足A當且僅當w滿足A?！边@一步是不能成立的。由于只是歸納總結了：“若對公式B中的自由變元，總有v=w()，則v滿足B當且僅當w滿足B；若公式C中的自由變元，總有v()=w()，則v滿足C當且僅當w滿足C?！庇捎趝}?{}∪{}，所以雖然對所有，v()=w()，但并不能保證v與w一定同時滿足v()=w()與v()=w()，也就不能得出“已證v滿足B當且僅當w滿足B，v滿足C當且僅當w滿足C”的結論了。因此也就不能繼續(xù)下面的歸納推理了。

實際上，只要將命題3.2.25中的“自由變元”都改為“自由出現(xiàn)的變元”，那么命題的證明過程就不會中斷了。因為若分別記A，B，C中自由出現(xiàn)的變元之集為GA，GB，GC，則顯然有GA=GB∪GC。那么若對所有∈GA，總有v()=w()，就可以推出對所有∈GB與∈GC，總有v()=w()與v()=w()。從而“已證v滿足B當且僅當w滿足B，v滿足C當且僅當w滿足C”。因此，正確的結論應該是：

命題3.2設L是一階語言，M是L的一個解釋，A∈F，v與w是L在M中的兩個賦值。如果對A中的每個自由出現(xiàn)的變元xi都有v(xi)=w(xi)，則v滿足A當且僅當w滿足A。

因此，若公式A不是閉公式，其中自由出現(xiàn)的變元為xi1，xi2，…，xir(r=1，2，…)，令

那么式（4）就變成：

例3.2設L是一階語言，它有兩個個體常元a1，a2，一個二元謂詞符號P。設L的解釋M為：

現(xiàn)有公式A為(?x1)(P(x1，x2)→P(x2，x1))，計算τM(A)。

解：公式A中只有一個自由出現(xiàn)的變元x2，并且在解釋M下，對任意賦值v∈ΩM，‖P(x1，x2)‖M，v=1-‖P(x2，x1)‖M，v。所以由式（5），

因此，由式（6）得，

由定義3.1，可以看到公式關于有限解釋的相對真度只與其中出現(xiàn)的變元有關。但是如果遇到研究兩個或兩個以上不同公式的真度的性質時，每個公式出現(xiàn)中的變元個數不同卻成為運用相對真度計算形式的一個障礙。如果對每個公式變形，使得所有公式中出現(xiàn)的變元相同，但其相對真度不變，那么就可以利用相對真度的計算形式去研究相對真度的性質了。更進一步，如果對任一公式，都可以適當增加其中出現(xiàn)的變元，但不改變其相對真度，就可以實現(xiàn)所有公式出現(xiàn)的變元相同而各自相對真度不變的想法了。事實上，有如下定理：

定理3.1設M∈Mf，A∈F，且A中出現(xiàn)的變元為x1，x2，…，xk，則存在A′∈F，A′中出現(xiàn)的變元為x1，x2，…，xk，y1，y2，…，yl，且A′～A，從而τM(A')=τM(A)。

證明令A0=?(P(y1，y2，…，yl)→P(y1，y2，…，yl))，A′=A∨A0，則顯然A′～A，且A′中出現(xiàn)的變元為x1，x2，…，xk，y1，y2，…，yl。因為A′～A，由命題2.1（iii），τM(A′)=τM(A)。

注3.2通過定理3.1，可以將公式A變形為與之邏輯等價，相對真度不變，卻出現(xiàn)更多變元的A′。更進一步，由于A′～A，所以在其他所有涉及公式A的邏輯公式（如A→B，?A，(?x)A等）的相對真度也不會改變。也就是說，在研究公式的相對真度的時候，可以不改變公式的相對真度而隨意增加公式中出現(xiàn)的變元個數。因此，當研究兩個或兩個以上的公式的相對真度的時候，完全可以假設各自獨立的公式出現(xiàn)的變元是相同的，從而橫向研究公式間的相對真度的關系了。

由例3.1與例3.2看到，利用相對真度的計算定義形式來計算公式關于有限解釋的相對真度時，其計算過程很簡單。其實，計算定義形式不止在計算公式的相對真度時表現(xiàn)出其優(yōu)越性，在證明某些關于相對真度的相關命題時，相較于其測度定義形式，更加直觀簡捷。

下面利用相對真度的計算形式來證明相對真度的一些簡單性質，從中可以看到這種新的定義形式在證明關于相對真度的相關命題時的優(yōu)越性。

命題3.3設M∈Mf，A，B∈F。

（ii）τM(A∨B)≥max{τM(A)，τM(B)}。

證明只需證明（i），（ii）同理可證。根據注3.2，假設A與B中出現(xiàn)的變元相同，均為x1，x2，…，xk，則A∧B中出現(xiàn)的變元亦為x1，x2，…，xk。由命題3.1（iv）與定義3.1，

下面記F1為所有不含量詞，且沒有重復出現(xiàn)的謂詞符號或變元符號的一階公式之集。

定理3.2設A∧B∈F1，則對任一有限解釋M=(M，(rP)P，(mc)c)∈Mf，總有τM(A∧B)=τM(A)τM(B)。

證明設公式A中所有出現(xiàn)的變元為x1，x2，…，xr，公式B中所有出現(xiàn)的變元為y1，y2，…，ys，其中r，s=1，2，…。那么根據定義3.1，

因為A∧B∈F1，所以A∧B中所有出現(xiàn)的變元為x1，x2，…，xr，y1，y2，…，ys，且它們互不相同。對任一解釋M=(M，(rP)P，(mc)c)∈Mf，由于公式A與B中沒有共同的謂詞符號或變元符號，因此‖‖AM，v與‖‖BM，v的值互不影響。由式（3），

根據定義3.1與式（7），

推論3.1設A1∧A2∧…∧Am∈F1，若M=(M，(rP)P，(mc)c)∈Mf，則總有τM(A1∧A2∧…∧Am)=τM(A1)τM(A2)…τM(Am)。

定理3.3設A∨B∈F1，則對任一有限解釋M= (M，(rP)P，(mc)c)∈Mf，總有τM(A∨B)=τM(A)+τM(B)-τM(A∧B)。

證明顯然，如果A∨B∈F1，那么也一定有A∧B∈F1。因此，由命題2.1與定理3.1，對任一有限解釋M=(M，(rP)P，(mc)c)∈Mf，

4 結束語

本文給出了一階公式關于有限解釋的相對真度的計算定義形式，舉例說明這一新的定義形式在相對真度的計算和證明過程中較之測度定義形式更為直觀簡便；指出一階公式的相對真度只與其中出現(xiàn)的變元有關，特別地，一階非閉公式的相對真度只與其中自由出現(xiàn)的變元有關，而非文獻[1]中指出的“與所有自由變元有關”；證明不改變公式的相對真度前提下，可以適當增加公式中自由出現(xiàn)的變元個數，以便橫向研究公式間的真度問題。一階公式相對真度作為計量謂詞邏輯理論的奠基石，對它的計算定義形式的研究，是一件非常有意義的事情。

[1]王國俊.數理邏輯引論與歸結原理[M].北京：科學出版社，2003：55-56.

[2]Wang G J，Zhou H J.Quantitative logic（I）[J].Information Sciences，2009，179：226-247.

[3]王國俊.非經典數理邏輯與近似推理[M].2版.北京：科學出版社，2008.

[4]王國俊，傅麗，宋建社.二值命題邏輯中命題的真度理論[J].中國科學：A輯，2001，31（11）：998-1008.

[5]Wang G J，Leung Yi.Integrated semantics and logic metric spaces[J].Fuzzy Sets and Systems，2003，136（1）：71-91.

[6]Hui X J，Wang G J.Randomized study on classical reasoning mode and its application[J].Science in China（Ser.E），2007，37（6）：801-812.

[7]韓邦合，李永明.計量邏輯學中的近似推理[J].模糊系統(tǒng)與數學，2010，24：1-7.

[8]周紅軍，王國俊.Borel型概率計量邏輯[J].中國科學：信息科學，2011，41（11）：1328-1342.

[9]Jun Li，Yan Zhou.A Quantitative method of n-valued G?del propositional logic[J].Procedia Environmental Sciences，2012，12：583-589.

[10]折延宏，賀小麗.粗糙邏輯的計量化研究[J].計算機工程與應用，2012，48（14）：44-50.

[11]婁妍，馮飛，左衛(wèi)兵.Lukasiewiczn值命題邏輯中公式的條件隨機真度[J].計算機工程與應用，2012，48（33）：63-67.

[12]She Yanhong.On the rough consistency measures of logic theories and approximate reasoning in rough logic[J].International Journal of Approximate Reasoning，2014，55：486-499.

[13]王國俊.一類一階邏輯公式中的公理化真度理論及其應用[J].中國科學：信息科學，2012，42（5）：648-662.

[14]王國俊，秦曉燕，周湘南.一類二值謂詞邏輯中公式的準真度理論[J].陜西師范大學學報：自然科學版，2005，33（1）：1-6.

[15]Qin Xiaoyan，Liu Yi，Xu Yang.Theory of approximate reasoning in two-valued predicate logic based on the quasi-truth degrees[J].Journal of Donghua University，2012，29（1）：23-27.

[16]秦曉燕，徐揚，劉熠.二值謂詞邏輯中公式的向量真度[J].模式識別與人工智能，2013，26（8）：740-744.

[17]Wang Guojun，Qin Xiaoyan，Zhou Xiangnan.An intrinsic fuzzy set on the universe of discourse of predicate formulas[J].Fuzzy Sets and Systems，2006，157：3145-3158.

[18]Hajek P.Metamathematics of fuzzy logic[M].London：Kluwer Academic Publishers，1998.

[19]Halmos P R.Measure theory[M].New York：Springer Verlag，1974.

QIN Xiaoyan1,XU Yang2

1.College of Mathematics and Computer Science,Shanxi Normal University,Linfen,Shanxi 041004,China
2.Intelligent Control Development Center,Southwest Jiaotong University,Chengdu 610031,China

The simplified computational definition of the relative satisfiability degrees of first-order formulae in a finite interpretation is proposed.It is pointed out that the relative satisfiability degree of a nonclosed first-order formula is just related to the free-occurred variables in the formula,not the free variables occurred in the formula；and it is proved that the relative satisfiability degree of a first-order formula can be unchanged although the amount of the variables occurring in the formula is increased,so that the matter of the relative satisfiablity degrees among formulae can be transversely studied according to the computational definition of the relative satisfiability degrees of first-order formulae.

relative satisfiablity degree；finite interpretation；free-occurred variables；quantitative predicate logic

A

O141

10.3778/j.issn.1002-8331.1504-0102

QIN Xiaoyan,XU Yang.Computing definition of relative satisfiability degrees of first-order formulae.Computer Engineering and Applications,2015,51（16）：6-10.

國家自然科學基金（No.61175055）；四川省科技支撐計劃（No.2011FZ0051）；工業(yè)和信息化部無線電管理局（No.[2011]146）；中國通信學會（No.[2011]051）。

秦曉燕（1981—），女，博士研究生，講師，研究領域為不確定性推理；徐揚（1956—），男，博士生導師，教授，研究領域為不確定性推理。E-mail：lisaqin1981@126.com

2015-04-12

2015-06-16

1002-8331（2015）16-0006-05