二值命題邏輯中邏輯理論的計量化及應用

李 駿，王菊花

蘭州理工大學 理學院，蘭州 730050

二值命題邏輯中邏輯理論的計量化及應用

李 駿，王菊花

蘭州理工大學 理學院，蘭州 730050

1 引言

數理邏輯的特點在于形式化與符號化，它和計算數學有著截然不同的風格：前者注重形式推理而后者重視數值計算；前者強調嚴格論證而后者允許近似求解。邏輯推理方法在諸如定理的自動證明、知識推理、邏輯程序設計等多個領域得到了廣泛的應用[1-2]，數值計算則似乎是遠離形式推理的完全不同的方法。為填補這一鴻溝，王國俊教授等將程度化思想引入到數理邏輯之中建立起了計量邏輯學的基本理論[3-6]，如今已在包括Lukasiewicz和R0系統在內的各種命題邏輯系統中構造出了相應的邏輯度量空間，從而將近似推理引入到素以嚴格的形式化推理為特征的各種命題邏輯系統中（可參看文獻[7-12]）。

在計量邏輯學中，除了對單個公式進行計量化研究之外，學者們對理論自身的性質也十分關注，比如：文獻[13-16]研究了理論的相容性和發散性等性質，并借助理論的發散度提出了理論的相容度概念，以此來區分不同理論相容程度的大小，進而達到區分不同理論好壞程度的目的。另外，在命題邏輯中經常要研究從某個命題之集Γ（即，理論）到另一個命題A的推演，即，從前提信息之集Γ推出某個結論A來。但是在現實推理中，可能所獲取的信息不足以將A作為理論Γ的邏輯結論推出來，這時就需考察理論Γ在多大程度上能推出結論 A來，即研究從理論Γ出發的近似推理，這也就涉及理論Γ本身的好壞問題，如果能夠給出一個評判理論Γ本身可靠程度的直接方法（或指標），這將為展開從前提信息集Γ出發的近似推理提供直接的依據。文獻[17]首次在命題邏輯系統中引入了理論Γ的真度概念來刻畫理論的可靠程度，但那里是把理論Γ的全體邏輯結論真度的下確界值作為理論Γ的真度，這種方法首先損失了理論Γ的結論中真度值較大的那些結論提供的信息；其次，這種方法借助了理論Γ本身以外的東西（即Γ的結論）來定義理論Γ的真度是不盡合理的，因為當理論Γ本身不可靠時，它的邏輯結論就更加不可靠；第三，當理論Γ退化為只含一個公式（比如：B）時，在多值邏輯中，按文獻[17]中的方法計算出的理論Γ的真度并不等于公式B的真度。因此，給出一個能克服以上缺陷的評判理論可靠程度的新方法，是有價值的研究課題。

本文在二值命題邏輯系統L中，首先借助勢為2的均勻概率測度空間的無窮乘積，通過計算理論Γ的全體模型占整個賦值空間的測度來定義理論Γ的真度，該定義是文獻[3]中公式真度定義的自然推廣，即：當理論Γ退化為只含一個公式（比如：B）時，理論Γ的真度就等于公式B的真度。其次，利用理論的真度定義了理論與理論之間的相似度和偽距離，并給出理論的真度在近似推理及其在描述理論的發散度、相容度等方面的應用。值得指出的是：當理論退化為單個公式時，本文關于理論所建立的計量化結果正是文獻[3]中相應的結果。

2 預備知識

設S={p1，p2，…}，F(S)是由S生成的(﹁，→)型自由代數。S中的元叫原子命題，F(S)中的元稱為公式（或命題）。在L={0,1}中規定：﹁0=1，﹁1=0，a→b=0當且僅當a=1且b=0，則{0，1}成為一個(﹁，→)型代數。稱(﹁，→)型同態v∶F(S)→{0，1}為F(S)的一個賦值。以Ω記F(S)上全體賦值之集。

定義1[5]設 A∈F(S)，若?v∈Ω，v(A)=1，則稱 A為重言式，記為：╞A；若?v∈Ω，v(A)=0，則稱 A為矛盾式；若?v∈Ω，都有v(A)=v(B)，則稱 A與B邏輯等價，記作：A≈B。

定義2[5]若Γ?F(S)，則稱Γ為理論。設 A∈F(S)，則從理論Γ到 A的一個推演是一個有限的公式序列A1，A2，…，Am，其中，Am=A，且?i≤m，Ai是公理或者Ai∈Γ或者存在 j，k＜i，使得 Ai是由 Aj和 Ak運用MP規則而得到的結果，稱A為Γ-結論，記作：Γ├A，m叫作從Γ到A的推演長度，進一步，若Γ=Φ（空集），則稱A為定理，簡記為：├A。

下文以0-記任一矛盾式，以D(Γ)來記全體Γ-結論之集，以T記全體理論之集，即

D(Γ)={A|A∈F(S)，且Γ├A}，T={Γ|Γ?F(S)}

設 Γ∈T，若 0-∈D(Γ)，則稱 Γ是不相容的理論。另外，若Γ只含一個公式A，即Γ={A}，則將Γ簡記為：Γ=A。

定義3設?！蔜，v∶F(S)→{0，1}是賦值，若?Ai∈Γ，都有v(Ai)=1，則稱v是Γ的模型，記為v|=?；騰(Γ)=1；若v不是Γ的模型，則簡記為v(Γ)=0；如果對每個v∈Ω，均有v|=Γ，則稱Γ是完全相容的，簡記為|=Γ；若每個v∈Ω，都有v(Γ)=0，則稱Γ是完全不相容的。

定義4設Γ1，Γ2∈T，如果對每個v∈Ω，均有v(Γ1)= v(Γ2)，則稱Γ1與Γ2邏輯等價，記作：Γ1≈Γ2。

注1顯然，當Γ1與Γ2都退化為只含單個公式時，理論之間的邏輯等價概念正是公式之間邏輯等價的概念。

定理1設?！蔜，則Γ是完全相容的當且僅當Γ全由定理組成。

證明 設Γ是完全相容的，則?v∈Ω，?A∈Γ，都有v(A)=1，從而?A∈Γ，A都是重言式，由完備性定理知?A∈Γ，A都是定理；反過來，若?A∈Γ，A都是定理，則A都是重言式，從而?v∈Ω都有v(A)=1成立，即?v∈Ω，均有v|=Γ，因此Γ是完全相容的。

3 理論的真度

定義7[3]設v∈Ω，記v(pk)=vk(k=1，2，…)，則無窮維向量v={v1，v2，…}∈X，這里X由定義6確定。反之，設v={v1，v2，…}∈X，則由v唯一確定Ω中的一個賦值v，這里v(pk)=vk(k=1，2，…)。令φ(v)=v，則φ∶Ω→X是從Ω到X的一一的滿射，稱φ為Ω的測度化映射。

定義8設?！蔜，令

稱τ(Γ)為理論Γ的真度。

（2）由于在實際推理中，推理的前提信息之集（即理論Γ）通常都是有限集，Γ中的公式用到的原子公式自然只有有限多個。因此下文中若無聲明，都假定構成理論Γ的公式中只用到有限多個原子公式。

（3）定義8中，若Γ={B}，B∈F(S)，則有

式（4）右邊正是文獻[3]中公式B真度的定義式，即τ({B})= τ(B)?？梢姳疚乃o出的理論的真度定義是公式真度定義的自然推廣。

下面的引理是文獻[5]中已給出的本文即將用到的幾個結果：

引理1[1]設A、B∈F(S)，則

（1）A是重言式當且僅當τ(A)=1，A是矛盾式當且僅當τ(A)=0。

（2）若A≈B，則τ(A)=τ(B)。

（3）若├A→B，則τ(A)≤τ(B)。

（4）τ(﹁A)=1-τ(A)。

（5）τ(B)≥τ(A)+τ(A→B)-1。

定理2設 Γ∈T，若 Γ={A1，A2，…，An}是有限理論，則τ(Γ)=τ(A1∧A2∧…∧An)；若Γ={A1，A2，…，Ak，…}是無窮理論，則τ(Γ)=τ(A1∧A2∧…∧An)。

證明 設Γ={A1，A2，…，An}是有限理論，則由定義8和注解2知：

定理3設Γ∈T，則

（1）τ(Γ)=1當且僅當Γ為完全相容理論。

（2）τ(Γ)=0當且僅當Γ為完全不相容的理論。

證明（1）若Γ是完全相容理論，則由定理1知Γ全由定理組成，從而?v∈Ω，?Ai∈Γ，都有v(Ai)=1，因此?v∈Ω，都有v|=Γ，故{v∈X|φ(v)=v，v∈Ω，且v|=Γ}=X，從而

反過來，若τ(Γ)=1，假設Γ不是完全相容的理論，則有 v∈Ω 使 v|=Γ不成立，設 pi1，pi2，…，pin是構成 Γ所用到的全體原子公式，令v(pik)=vik(k=1，2，…，n)。則(vi1，vi2，…，vin)?E，這里 E由注2給出。因為 μi1({vi1})× μi2({vi2})×…×μin({vin})=，所以(μi1×μi2×…×μin)(E)≤1-。從而由定義5和定義8知μ([Γ])≠1，從而τ(Γ)≠1，矛盾！因此，Γ為完全相容理論。

（2）設 Γ為完全不相容的理論，則 ?v∈Ω，都有v|=Γ不成立，從而[Γ]=?（空集），故τ(Γ)=μ(?)=0。

反過來，假設Γ不是完全不相容理論，則有v∈Ω使v|=Γ成立。設 pi1，pi2，…，pin是構成Γ所用到的全體原子公式，令v(pik)=vik(k=1，2，…，n)。則(vi1，vi2，…，vin)∈E，這里 E由式（3）確定。因為 μi1({vi1})×μi2({vi2})×…× μin({vin})=所以 (μi1×μi2×…×μin)(E)≥。從而由式（1）及式（3）知μ([Γ])≠0，故τ(Γ)≠0，矛盾！因此，Γ為完全不相容理論。

定理4設Γ1，Γ2∈T，若Γ1≈Γ2，則τ(Γ1)=τ(Γ2)。

證明 因為Γ1≈Γ2，所以?v∈Ω，有v(Γ1)=v(Γ2)，即?v∈Ω，v|=Γ1當且僅當 v|=Γ2，所以 [Γ1]=[Γ2]，從而τ(Γ1)=τ(Γ2)。

4 理論真度的應用

本章將給出理論的真度在描述理論的發散度和相容度等方面的一些應用，先給出文獻[5]中已有的一些結果。

首先，若A∈D(Γ)，則可取B為任意一個定理（當然有 B∈D(Γ)），此時由 (A→B)∧(B→A)≈A，從而τ((A→B)∧(B→A))=τ(A)知

其次，?A，B∈D(Γ)，由A→(B→A)和B→(A→B)是公理可知A→B∈D(Γ)，且B→A∈D(Γ)，從而(A→B)∧(B→A)∈D(Γ)，故

由式（11）和式（12）知式（10）成立，從而式（9）成立。

定理6設Γ∈T，則div(Γ)=1-τ(Γ)。

證明 若Γ={A1,A2,…,An}是有限理論，則?A∈D(Γ)，由├(A1∧A2∧…∧An→A)，從而由 τ(A1∧A2∧…∧An)≤τ(A)知

從而由定理3和定理5可知div(Γ)=1-τ(Γ)。若Γ= {A1，A2，…，Ak，…}是無窮理論，則對任意的自然數n，A1∧A2∧…∧An∈D(Γ)，令

則數列{yn}單調遞減且有下界0，從而數列{yn}極限τ(A1∧A2∧…∧An)存在，因此

注3文獻[5]中關于一般的理論給出了刻畫其相容程度的η-相容度，將本文定理6中發散度的簡化公式代入η-相容度的表達式中就可得到簡化的η-相容度計算公式。

定理8設Γ∈T，若τ(Γ)=α，則?B∈Γ，都有τ(B)≥α。

證明 若Γ={A1,A2,…,An}是有限理論，則由定理3知τ(Γ)=τ(A1∧A2∧…∧An)，又?Ai∈Γ，由├A1∧A2∧…∧An→Ai和引理1（3）可知τ(Ai)≥τ(Γ)=α，結論成立。

若 Γ={A1，A2，…，Ak，…}是無窮理論，由定理1知τ(Γ)=τ(A1∧A2∧…∧An)。 又 ?An∈Γ ，由├A1∧A2∧…∧An→An知 τ(A1∧A2∧…∧An)≤τ(An)，令 yn= τ(A1∧A2∧…∧An)，由數列 {yn}單調遞減且 τ(Γ)=τ(A1∧A2∧…∧An)知τ(An)≥τ(Γ)=α，從而結論對無窮理論也成立。

定理9設?！蔜 ，α＞0，τ(Γ)=α，A是Γ的長度為n的結論，則

這里，un是斐波那契數列的第n項，即

且有u1=u2=1，un+un+1=un+2，n=1，2，…。

證明 采用數學歸納法來證明。

當n=1時，因為A為公理或A∈Γ所以由引理1（1）和定理7知τ(A)≥α，又式（13）右端un(α-1)+1=α-1+ 1=α，因此式（13）成立。設n≤k時式（13）成立，A是Γ的長度為k+1的推論，推演序列為A1，A2，…，Ak，A。不妨設 A?Γ，A也不是公理，則有i≤k，j≤k，使得 A是由Ai和Aj通過運用MP規則而得的結果，由歸納假設得：

不妨設i＜j，則 j≤k，i≤k-1，注意到(α-1)≤0，從而由引理1（5）可得：即式（13）當n=k+1時也成立，定理得證。

注4由定理9知，若推理的前提信息之集Γ的真度為α，則其推理長度為n的邏輯結論的真度不小于un(α-1)+1，比如：若τ(Γ)=1，則對任意的n，Γ的推演長度為n的邏輯結論的真度均為1；若τ(Γ)≥0.99，則Γ的推演長度為6的邏輯結論的真度均不小于0.92。

5 結束語

本文在二值命題邏輯系統中，借助勢為2的均勻概率測度空間的無窮乘積，通過計算理論Γ的全體模型占整個賦值空間的測度定義了理論Γ的真度，并給出理論的真度在描述理論的發散度、相容度等方面的應用，值得指出的是：當理論退化為單個公式時，本文關于理論所建立的計量化結果正是文獻[3]中相應的結果。關于如何將本文結果推廣到多值以至于連續值命題邏輯系統，將另文討論。

[1]Rosser J B，Turquette A R.Many-valued logic[M].Amsterdam：[s.n.]，1952.

[2]Ying M S.A logic for approximate reasoning[J].Journal of Symbolic，1994，59：830-837.

[3]Wang G J，Fu L，Song J S.Theory of truth degrees of propositions in two-valued logic[J].Sci China Ser A-Math，2002，45：1106-1116.

[4]Wang G J，Zhou H J.Quantitative logic[J].Information Sciences，2009，179（3）.

[5]王國俊.數理邏輯引論與歸結原理[M].2版.北京：科學出版社，2006.

[6]王國俊，宋建社.命題邏輯中的程度化方法[M].電子學報，2006，34（2）：252-257.

[7]Wang G J，Hui X J.Randomization of classical inference patterns and its application[J].Science in China：Ser F，2007，50（6）：867-877.

[8]Zhou H J.Borel probabilistic and quantitative logic[J].Science China Information Sciences，2010，53：1-12.

[9]Li J，Wang G J.Theory of truth degrees in logic system[J].Science in China：Ser E，2006，36（6）：631-643.

[10]李駿，鄧富喜.n值S-MTL命題邏輯系統中公式真度的統一理論[J].電子學報，2011，39（8）：1864-1868.

[11]王國俊，李璧鏡.Lukasiweicz n值命題邏輯中公式的真度理論和極限定理[J].中國科學 E輯：信息科學，2005，35（6）：561-569.

[12]李駿，王國俊.基于支持度理論的廣義MP問題的形式化解[J].電子學報，2008，36（11）：2190-2194.

[13]Zhou X N，Wang G J.Consistency degrees of theories in some systems of propositional fuzzy logic[J].Fuzzy Sets and Systems，2005，152：321-331.

[14]Wang G J，Zhang W X.Consistency degrees of finite theories in Lukasiewicz propositional fuzzy logic[J].Fuzzy Sets and Systems，2005，149（2）：275-284.

[15]Zhou H J，Wang G J.A new consistency index based on deduction theorems in several logic systems[J].Fuzzy Sets and Systems，2006，157（3）：427-443.

[16]Wang G J，She Y H.Topological description of divergency and consistency of two-valued propositional theories[J].Acta Mathematica Sinica：Chinese Series，2007，50（4）：841-850.

[17]王國俊，高香妮.命題邏輯系統中理論的真度概念及其應用[J].陜西師范大學學報：自然科學版，2009，37（5）：1-6.

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

LI Jun,WANG Juhua

School of Science,Lanzhou University of Technology,Lanzhou 730050,China

By means of infinite product of uniformly distributed probability spaces of cardinal 2,this paper introduces the concept of truth degree of a logical theoryΓby computing the measure of all models ofΓin the valuation spaces.Simplified methods to compute the divergent degree and the consistent degree of a logical theory are given and the expression to estimate the truth degree of logical conclusions from the truth degree of its premise set is obtained.

quantitative logic;logical theory;truth degree of logical theory;consistency degree

在二值命題邏輯系統中，利用勢為2的均勻概率測度空間的無窮乘積，通過計算理論Γ的全體模型占整個賦值空間的測度定義了理論Γ的真度，進而利用理論的真度簡化了理論的發散度和相容度的計算公式，給出了由推理的前提集的真度估計其邏輯結論真度的表達式。

計量邏輯學；邏輯理論；理論的真度；相容度

A

O141.1

10.3778/j.issn.1002-8331.1301-0205

LI Jun,WANG Juhua.Quantification of logic theory in two-valued propositional logic and its applications.Computer Engineering and Applications,2014,50（24）：42-46.

國家自然科學基金（No.11261032）；蘭州理工大學博士基金資助項目。

李駿（1972—），男，博士，副教授，碩士研究生導師，研究領域：非經典數理邏輯、不確定性推理；王菊花（1987—），女，碩士研究生，研究領域：不確定性推理。

2013-01-21

2013-04-22

1002-8331（2014）24-0042-05

CNKI網絡優先出版：2013-05-21，http∶//www.cnki.net/kcms/detail/11.2127.TP.20130521.1027.004.html