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

摘要

针对命题逻辑的可判定性中真值表法复杂度高的问题,提出了一种基于命题逻辑联结符号完备性和与或树规则的命题逻辑的可判定性算法。算法首先利用常见的等价公式和与或树规则对命题逻辑的公式进行分解,然后参照分解后的树形结构将公式转换成范式形式,最后对照所得的判别式对命题逻辑公式进行判定。理论证明这种算法相比于具有指数级复杂度的真值表法效率高得多。