Two results in negation-free logic (Q1324497): Difference between revisions

The problem of derivability of logical implications between sentences in classical propositional or predicate logic is reduced to the same problem for the negation-free fragment. So this problem for negation-free logic is co-NP-complete in the propositional case and is undecidable in the predicate case. The problem of determining a minimum satisfying assignment for a propositional formula in a negation-free conjunctive normal form, even with no more than two disjuncts per clause, is also NP- complete.