一种命题逻辑的可判定性算法  

An algorithm of propositional logic′s decision

作　　者：程昆[1] 高佳乐[1] 

机构地区：[1]云南师范大学信息学院,云南昆明650092

出　　处：《微型机与应用》2013年第24期76-77,81,共3页Microcomputer & Its Applications

摘　　要：针对命题逻辑的可判定性中真值表法复杂度高的问题,提出了一种基于命题逻辑联结符号完备性和与或树规则的命题逻辑的可判定性算法。算法首先利用常见的等价公式和与或树规则对命题逻辑的公式进行分解,然后参照分解后的树形结构将公式转换成范式形式,最后对照所得的判别式对命题逻辑公式进行判定。理论证明这种算法相比于具有指数级复杂度的真值表法效率高得多。The paper gives a lot of basic knowledge of propositional logic , then proves the completeness of the logic′s join operator . By using the known equivalent formula and AND/OR tree , it translates the formula into normal form and decides the for-mula of propositional logic . Compared with Truth table , the algorithm largely improves the efficiency in the decision problem .

关 键 词：命题逻辑 归纳定义 完备性 与或树 可判定性 

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