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

ON DECIDABILITY AND NP-COMPLETENESS FOR TERNARY LOGIC

本文建立了一种三值逻辑——中介逻辑的三值语义,证明了其命题演算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.