摘要
针对命题逻辑的可判定性中真值表法复杂度高的问题,提出了一种基于命题逻辑联结符号完备性和与或树规则的命题逻辑的可判定性算法。算法首先利用常见的等价公式和与或树规则对命题逻辑的公式进行分解,然后参照分解后的树形结构将公式转换成范式形式,最后对照所得的判别式对命题逻辑公式进行判定。理论证明这种算法相比于具有指数级复杂度的真值表法效率高得多。
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 .
出处
《微型机与应用》
2013年第24期76-77,81,共3页
Microcomputer & Its Applications
关键词
命题逻辑
归纳定义
完备性
与或树
可判定性
propositional logic
inductive definition
completeness
AND/OR tree
decision
