一种三值逻辑的NP完全问题与判定问题  

ON DECIDABILITY AND NP-COMPLETENESS FOR TERNARY LOGIC

作　　者：李祥[1] 

机构地区：[1]贵州大学计算机科学系

出　　处：《计算机学报》1990年第8期561-568,共8页Chinese Journal of Computers

摘　　要：本文建立了一种三值逻辑——中介逻辑的三值语义,证明了其命题演算MP与MP的可满足问题是NP完全的且其谓词演算(带或不带等词)MF,MF与ME的判定问题是算法不可解的。We present a ternary semantic analysis for the axiomatic ternary logic called Medium Logic. The satisfiability problem on the ternary propositional logic MP(MP*) is NP-complete and the decision problem on the ternary predicate logic MF(MF*, ME*) is unsolvable.

关 键 词：三值逻辑 NP完全问题 数理逻辑 

分 类 号：O141[理学—数学]