命题逻辑系统L_n中公式集上的真度函数

2010，46（36） 1 引言 对于F（S）中的一个公式 A，可以从语义上通过赋值判断 A是否“恒真”或“恒假”，即，如果对每个赋值 v，v(A)= 1恒成 立，则称 A是重言式；如果对每个赋值 v，v(A)= 0恒成立，则 称 A是矛盾式。而对于一个命题逻辑系统而言，绝大多数公式 既非重言式又非矛盾式，关于这些公式优劣的评价，文献[1-8] 都是从语义的角度入手将重言式的概念程度化，提出了公 式的真度、相似度、伪距离等概念，建立了逻辑度量空间，进 而在命题逻辑系统中建立了一套完整的近似推理框架，文 献[9]对这方面的研究成果作了系统总结，并建立了计量逻 辑学理论。众所周知，逻辑演算理论包含有语义理论和语 构理论两大部分，对于好的逻辑系统，这两个部分可通过完 备性定理和谐地统一起来。那么，能否从语构的角度给出 逻辑公式的程度化，从而为计量逻辑的发展开辟新的道 路？文献[10]在二值命题逻辑系统 L中提出了公式的真度 理论，给出了逻辑公式的语构程度化方法。本文把这种方 法推广到 n值Lukasiewicz命题逻辑系统中，进一步丰富了计 量逻辑学理论。 2 预备知识 形式系统 Ln是由公式集 F(S)、公理集和推理规则 MP三 个部分构成。这里 S = { }p1p2 是原子公式集，F(S)是由 S 生成的 ( )Ø® 型自由代数，其中，Ø是一元连接词，®是二元 连接词。设 ABÎ F(S)，在 F(S)中引入新的逻辑连接词如下： （1）A Ú B = ( )A® B ® BA Ù B =Ø( )ØA ÚØB （2）A⊗ B =Ø( )A®ØB AÅB =Ø( )ØA⊗ØB （3）A º B = ( )A® B ⊗ ( )B® A 另外，可归纳地定义 Am和 mA( )mÎNm ³ 2 如下： A2 = A⊗ AAm = Am - 1⊗ A2A = AÅAmA = ( )m - 1 AÅA n值Lukasiewicz命题逻辑系统Ln的公理由以下形式的公 式组成： （Lu1）A Ú B = A® ( )B® A （Lu2）A® B® ( )( )B®C ® ( )A®C （Lu3）( )( )A® B ® B ® ( )( )B® A ® A （Lu4）( )ØA®ØB ® ( )B® A 命题逻辑系统Ln中公式集上的真度函数 马丽娜 1，刘 烁 2，王国俊 1 MA Li-na1，LIU Shuo2，WANG Guo-jun1 1.陕西师范大学 数学与信息科学学院，西安 710062 2.第四军医大学 生物医学工程系，西安 710032 1.College of Mathematics and Information Science，Shaanxi Normal University，Xi’an 710062，China 2.Faculty of Biomedical Engineering，The Fourth Military Medical University，Xi’an 710032，China E-mail：malina@snnu.edu.cn MA Li-na，LIU Shuo，WANG Guo-jun.Truth degree function on set of formulas in propositional logic system Ln.Com- puter Engineering and Applications，2010，46（36）：37-39. Abstract：The purpose of this paper is to give an axiomatic definition of truth degree function on the set of formulas in n-valued Lukasiewicz propositional logic system and some properties of truth degree function are proved.The conceptions of similarity de- gree among formulas and a pseudo-metric on the set of formulas are defined by means of the concept of truth degree function. The logic metric space is built and a possible framework for approximate reasoning from the syntactical view is proposed. Key words：truth degree function；similarity degree；pseudo-metric；logic metric space 摘 要：在n值Lukasiewicz命题逻辑系统中引入了公式集F（S）上真度函数的公理化定义，给出了真度函数的若干重要性质，利用 真度函数从形式上定义了相似度和伪距离，建立了逻辑度量空间，为从语构的角度展开近似推理提供了一种可能的框架。 关键词：真度函数；相似度；伪距离；逻辑度量空间 DOI：10.3778/j.issn.1002-8331.2010.36.010 文章编号：1002-8331（2010）36-0037-03 文献标识码：Ａ 中图分类号：O142 基金项目：国家自然科学基金（the National Natural Science Foundation of China under Grant No.10771129）。 作者简介：马丽娜（1980-），女，博士研究生，讲师，研究方向：不确定性推理；刘烁（1979-），男，助教，研究方向：生物数学，非经典数理逻辑；王国俊 （1935-），男，博士生导师，教授，研究方向：不确定性推理，非经典数理逻辑等。 收稿日期：2010-07-20 修回日期：2010-10-19 Computer Engineering and Applications计算机工程与应用 37 Computer Engineering and Applications计算机工程与应用2010，46（36） （Lu5）( )n - 2 A º ( )n - 1 A （Lu6）( )kAk - 1 n - 1 º ( )n - 1 Ak这里 k = 23n - 3且 k 不能整除 n - 2。 系统 Ln中只有一条推理规则：MP规则，即从 A和 A® B 推出 B。 设 ΓÍ F(S)AÎ F(S)，从 Γ 到 A的一个推理是一个有限 的公式序列 A1A2Am其中 Am = A且 "i £mAi是公理或 AiÎ Γ ，或存在 jk < i使得 Ai是由 Aj和 Ak 运用 MP规则而 得到的结果。称 A为 Γ－结论，记作 Γ | -A。下面以 D( )Γ 来 记全体 Γ－结论之集。 3 F（S）上的真度函数 定义 3.1 在 n 值 Lukasiewicz 命题逻辑系统 Ln中，设 τ*:F ( )S ®[01]这里[0，1]是MV单位区间，如果 （L1）τ*（Lui）=1，这里（Lui）（i=1，2，…，6）是Ln中的公理。 （L2）τ*( )ØA = 1 - τ*( )A （L3）τ*( )B ³ τ*( )A + τ*( )A® B - 1 （L4）τ*( )A Ú B + τ*( )A Ù B = τ*( )A + τ*( )B 则称 τ*为 F ( )S 上的一个真度函数。 例3.2（1）设 v是一个赋值，则 v是定义3.1意义下的真度 函数。 （2）设 τ:F ( )S ®[01]定义如下[3]： τn( )A = 1nmåi = 1 n - 1 i n - 1 | || | || Aˉ -1æè öø i n - 1 其中 A = A( )p1p2pm 是 Ln中含有 m个原子命题的合式公 式，Aˉ( )x1x2xm 是由 A诱导的真函数，则 τn是定义 3.1意 义下的真度函数。 下面给出真度函数的若干性质。 命题3.3（1）若 | -A则 τ*( )A = 1。 （2）若 A是可驳公式，则 τ*( )A = 0。 （3）若 A® B是定理，则 τ*( )A £ τ*( )B 。 （4）若 A与 B可证等价，则 τ*( )A = τ*( )B 。 （5）τ*( )B £ τ*( )A® B £ τ*( )A ® τ*( )B 。 （6）τ*( )A⊗ B £ τ*( )A Ù B £ min{ }τ*( )A τ*( )B £max{τ*( )A  }τ*( )B £ τ*( )A Ú B £ τ*( )AÅB 。 （7）设 αβÎ [0，1]，若 τ*( )A ³ ατ*( )A® B ³ β则 τ*( )B ³ α + β - 1。 （8）设 αβÎ [0，1]，若 τ*( )A® B ³ ατ*( )B®C ³ β 则 τ*( )A®C ³ α + β - 1。 （9）设 αβÎ [0，1]，若 τ*( )A® B ³ ατ*( )A®C ³ β 则 τ*( )A® B ÙC ³ α + β - 1。 （10）若 | -A则 τ*( )A® B + τ*( )A = τ*( )B® A + τ*( )B 。 （11）τ*(A Ú B ÚC)= τ*(A)+ τ*(B)+ τ*(C)- τ*(A Ù B)- τ*(A Ù C)- τ*( )B ÙC + τ*( )A Ù B ÙC 。 证明（1）因为定理是从公理出发利用 MP规则得到的， 所以由（L1）和（L3）知（1）成立。 （2）若 A是可驳公式则 | -ØA由（L2）和性质（1）即得（2）。 （3）由（L3）即得 τ*( )A £ τ*( )B 。 （4）若 A与 B可证等价，则 A® B和 B® A都是定理，从 而由（3）知 τ*( )A £ τ*( )B 且 τ*( )B £ τ*( )A 所以 τ*( )A = τ*( )B 。 （5）因为 B® ( )A® B 是定理，所以由（3）知 τ*( )B £ τ*( )A® B  进一步地，有 τ*( )A ® τ*( )B ³ 1® τ*( )A® B 即 τ*( )A® B £ τ*( )A ® τ*( )B 。 （6）由于( )A⊗ B ® ( )A Ù B A Ù B® AA Ù B® BA® A Ú BB® A Ú B( )A Ú B ® ( )AÅB 都是定理以及（3）知（6）成立。 （7）由（L3）即得。 （8）因为 ( )A® B ® ( )( )B®C ® ( )A®C 是定理，所以 τ*( )( )A® B ® ( )( )B®C ® ( )A®C = 1由（7）及 τ*( )A® B ³ α 得 τ*( )( )B®C ® ( )A®C ³ α再由（7）及 τ*( )B®C ³ β 得到 τ*( )A®C ³ α + β - 1。 （9）因为 ( )A® B Ù ( )A®C 与 A® B ÙC 可证等价，所以 τ*( )( )A® B Ù ( )A®C = τ*( )A® B ÙC 由（L4）知结论成立。 （10）若 A是定理，则由（5）得 τ*( )B £ τ*( )A® B £ τ*( )A ® τ*( )B £ τ*( )B ，因此 τ*( )A® B = τ*( )B 。又由 A® ( )B® A 是定 理得 τ*( )A £ τ*( )B® A 即 τ*( )B® A = 1因此 τ*( )A® B + τ*( )A = τ*( )B® A + τ*( )B 。 （11）由 τ*( )A Ú B ÚC = τ*( )A Ú ( )B ÚC 以 及（L4）可 得 τ*( )A Ú B ÚC = τ*( )A + τ*( )B ÚC - τ*( )A Ù ( )B ÚC ，再 由 A Ù ( )B ÚC 和 ( )A Ù B Ú ( )A ÙC 是可证等价的以及（4）、（L4）可知 （11）成立。 4 逻辑度量空间 基于真度函数，可以引入公式间的相似度及伪距离，进而 建立相应的逻辑度量空间。 定义4.1 设 ABÎ F(S)称 ξτ*( )AB = τ*((A® B)Ù (B® A)) 为公式 A与 B间的相似度，特别地，当 ξτ*( )AB = 1时称 A与 B是相似的，记作 A  B。 命题4.2 设 ABCÎ F(S)则 （1）ξτ*( )AB = ξτ*( )BA 。 （2）若 A与 B可证等价，则 ξτ*( )AB = 1。 （3）ξτ*( )AB + ξτ*( )BC £ ξτ*( )AC + 1。 证明（1）和（2）是显然的，下面只证（3）。 因为 ( )A® B Ú ( )B® A 是 Ln中的定理，所以 ξτ*( )AB = τ*( )( )A® B Ù ( )B® A = τ*( )A® B + τ*( )B® A - 1 同 理 有 ξτ*( )BC = τ*( )B®C + τ*( )C® B - 1 ξτ*( )AC = τ*( )A®C + τ*( )C® A - 1则由命题3.3（8）知， τ*( )A®C ³ τ*( )A® B + τ*( )B®C - 1 τ*( )C® A ³ τ*( )C® B + τ*( )B® A - 1 因此有 1 + ξτ*( )AC ³ 1 + ξτ*( )AB + 1 + ξτ*( )BC - 2 = ξτ*( )AB + ξτ*( )BC 由命题4.2容易得到下面的推论： 推理4.3 相似关系 是公式集上的等价关系。 命题4.4 设 ABA′B′Î F(S)若 ξτ*(AA′)³ αξτ*(BB′)³ β 则 ξτ*(A® BA′ ® B′)³ α + β - 1。 38 2010，46（36） 证 明 由 (A′ ® A)® ((A® B)® (A′ ® B)) 和 (A® A′)® ((A′ ® B)® (A® B)) 都是 Ln中的定理以及命题 3.3（3）知 τ*(A′ ® A) £ τ*((A® B)® (A′ ® B)) ，τ*(A® A′)£ τ*((A′ ® B)® (A® B))，从而有 ξτ*(A® BA′ ® B)³ ξτ*(AA′)³ α。类似地由 ξτ*(BB′)³ β可证得 ξτ*(A′ ® BA′ ® B′)³ ξτ*(BB′)³ β。由命题 4.2（3）知结论成立。 命题 4.5（1）令 ρτ*( )AB = 1 - ξτ*( )AB 则 ρτ* 是 F(S)上 的伪距离，称 (F(S)ρτ*)为逻辑度量空间。 （2）在逻辑度量空间 (F(S)ρτ*)中，逻辑连接词 Ø、Ú和® 都是连续的。 证明（1）设 ABCÎ F(S)首先有 ρτ*( )AA = 1 - ξτ*( )AA = 0其次由命题4.2（1）知 ρτ*( )AB = ρτ*( )BA 成立；最后，由命题 4.2（3）知 ρτ*( )AC = 1 - ξτ*( )AC £ 1 - (ξτ*( )AB + ξτ*( )BC - 1)= ρτ*( )AB + ρτ*( )BC ，可见 ρτ*的确是 F(S)上的伪距离。 （2）设 ABÎ F(S)ε > 0且 ρτ*(AB)< ε则 ρτ*(ØAØB)= 1 - ξτ*(ØAØB)= 1 - τ*((ØA®ØB)Ù (ØB®ØA))= 1 - τ*((B® A)Ù (A® B))= 1 - ξτ*( )AB = ρτ*( )AB < ε,因此Ø关于 ρτ*是连续的。 下面证明蕴涵连接词®的连续性。设 ABA′B′Î F(S) 且 ρτ*(AA′)£ ε2ρτ*(BB ′)£ ε 2 那么 ξτ*(AA′)³ 1 - ε2ξτ*(BB ′)³ 1 - ε 2 于是由命题4.4可得ξτ*(A® BA′ ® B′)³ æè öø1 - ε 2 + æè öø1 - ε 2 - 1 = 1 - ε即 ρτ*(A® BA′ ® B′)£ ε这就证得了®的连续性。 最后证明 Ú 关于 ρτ* 也是连续的。设 ABB′Î F(S)且 ρτ*(BB′)£ ε则 ξτ*( )BB′ > 1 - ε，由 (B® B′)® (A Ú B® A Ú B′)(B′ ® B)® (A Ú B′ ® A Ú B) 都是 Ln中的定理可得 (B® B′)Ù (B′ ® B)® (A Ú B® A Ú B′)Ù (A Ú B′ ® A Ú B)也是定理，由命题3.3（3）知 τ*((B® B′)Ù (B′ ® B))£ τ*((A Ú B® A Ú B′)Ù (A Ú B′ ® A Ú B)) 因此 ξτ*(A Ú BA Ú B′)³ ξτ*(BB′)> 1 - ε即 ρτ*(A Ú BA Ú B′)< ε 可见 Ú关于 ρτ*也是连续的。 推论4.6 在逻辑度量空间 (F(S)ρτ*)中，逻辑连接词 Å、⊗ 和 Ù都是连续的。 证明 由于 Å、⊗和 Ù都可以由 Ø、Ú和®来表示，所以 由 Ø、Ú和®的连续性知 Å、⊗和 Ù关于 ρτ*也是连续的。 参考文献： [1] 王国俊，傅丽，宋建社.二值命题逻辑中命题的真度理论[J].中国科 学：A辑，2001，31（11）：998-1008. [2] 李骏，黎锁平，夏亚峰.Lukasiewicz n值命题逻辑中命题的真度理 论[J].数学学报，2004，47（4）：769-780. [3] 王国俊，李璧镜.Lukasiewicz n值命题逻辑中公式的真度理论和 极限定理[J].中国科学：E辑，2005，35（6）：561-569. [4] 李骏，王国俊.逻辑系统中命题的真度理论[J].中国科学：E辑， 2006，36（6）：631-643. [5] 王国俊，秦晓燕，周湘南.一类二值谓词逻辑中公式的准真度理 论[J].陕西师范大学学报：自然科学版，2005，33（1）：1-6. [6] 韩邦合，王国俊.二值逻辑中命题的条件真度理论[J].模糊系统与 数学，2007，21（4）：9-15. [7] 王国俊，王伟.逻辑度量空间[J].数学学报，2001，44（1）：159-168. [8] Wang Guojun，Leung Y.Integrated semantics and logic metric spaces[J].Fuzzy Sets and Systems，2003，136（1）：71-91. [9] Wang Guojun，Zhou Hongjun.Quantitative logic[J].Information Sci- ence，2009，179（3）：226-247. [10] 张东晓，李立峰.二值命题逻辑公式的语构程度化方法[J].电子学 报，2008，36（2）：325－330. [11] Pavelka J.On fuzzy logic（I，II，III）[J].Zeitschr f Math Logik und Grundlagen d Math，1979，25. [12] 王国俊.数理逻辑引论与归结原理[M].2版.北京：科学出版社， 2006：219-236. [13] 李骏.计量逻辑学和程度化知识推理[D].西安：陕西师范大学， 2008. [14] 周红军.概率计量逻辑学[D].西安：陕西师范大学，2009. （上接36页） 5 结束语 遗传算法的研究主要集繁殖算子的改进，缺乏对历代群 体进化规律的充分利用，而自适应算子的提出能够很好地解 决这个问题。初步测试的结果表明，在采用相同参数的条件 下，自适应遗传算法具有更高的优化效率。自适应算子的主 要不足是，其中后验概率的计算复杂度随变量数量的增加成 指数速度增长，但是面对变量不多的优化问题，自适应遗传算 法依然是比较好的选择。 参考文献： [1] Camara M，Ortega J，De-Toro F.A single front genetic algo- rithm for parallel multi-objective optimization in dynamic envi- ronments[J].Ncurocomputing，2009，72：3570-3579. [2] Mukhopadhyay A，Maulik U，Bandyopadhyay S.Multi-objective genetic algorithm-based fuzzy clustering of categorical attri- butes[J].IEEE Transaction on Evolutionary Computation，2009， 13（5）：991-1005. [3] Kim K，Jeong I J.Flow shop scheduling with no-wait flexible lot streaming using an adaptive genetic algorithm[J].The Inter- national Journal of Advanced Manufacturing Technology，2009， 44（11/12）：1181-1190. [4] Wang Y M，Yin H L，Wane J.Genetic algorithm with new encod- ing scheme for job shop scheduling[J].The International Journal of Advanced Manufacturing Technology，2009，44（9/10）：977-984. [5] 邝航宇，金晶，苏勇.自适应遗传算法交叉变异算子的改进[J].计算 机工程与应用，2006，42（12）：93-96. [6] 武妍，冯钊.一种基于混沌搜索的自适应入侵遗传算法[J].计算机 应用，2008，28（1）：101-103. [7] 耿汝年，须文波.基于自适应选择遗传算法的任务调度与分配[J]. 计算机工程，2008，34（3）：43-45. [8] 杨新武，刘椿年.遗传算法中自适应的比例选择策略[J].计算机工 程与应用，2007，43（20）：25-27. [9] 聂冲，王维平，赵雯，等.基于学习算子的自学习遗传算法设计[J]. 计算机仿真，2006，23（9）：168-171. [10] Zhou Y R.Runtime analysis of an ant colony optimization al- gorithm for TSP instances[J].IEEE Transaction on Evolutionary Computation，2009，13（5）：1083-1092. 马丽娜，刘 烁，王国俊：命题逻辑系统Ln中公式集上的真度函数 39