2 RESULTS IN NEGATION-FREE LOGIC

Negation-free propositional logic (or first-order logic) is clearly le ss expressive than the corresponding full system with negation. Howeve r, we present two complexity results for logic without negation that a re no different from those for the original system. First, the problem of determining logical implication between sentences composed solely of conjunctions and disjunctions is shown to be as difficult as that b etween arbitrary sentences. Second, we show that the problem of determ ining a minimum satisfying assignment for a propositional formula in n egation-free conjunctive normal form, even with no more than two disju ncts per clause, is NP-complete. We also show that unless P = NP, no p olynomial time approximation scheme can exist for this problem.