二值命题逻辑的无损求解  

Lossless Solving of Two-Valued Propositional Logic

作　　者：唐益明[1,2] 刘晓平[1] 

机构地区：[1]合肥工业大学计算机与信息学院情感计算与先进智能机器安徽省重点实验室,合肥230009 [2]合肥工业大学信息与通信工程博士后科研流动站,合肥230009

出　　处：《计算机学报》2013年第5期1097-1114,共18页Chinese Journal of Computers

基　　金：国家"八六三"高技术研究发展计划项目基金(2012AA011103);国家自然科学基金(61203077;61105076;61070124;41076120;60890075);中国博士后科学基金(2012M521218);中央高校基本科研业务费专项资金(2012HGQC0011;2012HGCX0001;2012HGBZ0639)资助~~

摘　　要：针对协同问题求解、协同设计等诸多领域中存在逻辑冲突的共性问题,从二值命题逻辑理论出发,研究面向冲突的无损求解(即初始解空间获取)问题.首先,提出简单合取式的扩充和Wh-析取范式等概念,在此基础上定义初始解空间,并通过提出的有效扩充概念得到初始解空间的简化表示——最简解空间,探讨了两类解空间的关系及各自的计算方法.其次,构造生成序列来辅助公式的析取化,从泛代数的角度定义了Wh-代数;提出了指数矩阵,并籍此给出了Wh-代数的等价表现形式,通过引入扩展指数矩阵构造出扩展Wh-代数.最后证明了扩展Wh-代数中的展开定理和逻辑简化定理,给出基于有效扩充的直接无损求解算法,并与提出的其他相关算法进行了对比,结果表明该算法较为理想.该研究对于协同问题求解等领域有着重要的推动作用.Aiming at the common problem that there exist conflicts in many fields such as collab- orative problem-solving, collaborative design and so on, the lossless solving for conflicts （i. e. ac- quiring initial solving spaces） is investigated from the viewpoint of two-valued propositional logic. To begin with, the strict definition of initial solving spaces is brought forward based on intro- duced extensions and Wh-disjunctive normal forms, and simplest solving spaces are proposed as the simplified representation of initial solving spaces following proposed concept of effective ex- tensions, before obtaining the relationship of such two solving spaces and respective computing methods. Furthermore, generated sequences are constructed in aid of converting formulas to dis- junctive normal forms, and, following defined Wh-algebras from the point of view of universal algebras and given equivalence representation of Wh-algebras based on proposed exponent matri- xes, extended Wh-algebras are constructed with introduced extended exponent matrixes. At last, after proving the expanding theorem and logical simplifying theorem in extended Wh-algebras, the algorithm of direct lossless solving based on effective extension is put forward as an ideal algorithm comparing with other proposed related algorithms. Such works would be beneficial to improve the development of related fields including collaborative problem-solving and so on.

关 键 词：协同计算 冲突 二值命题逻辑 无损求解 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]