0
$\begingroup$

In the decision problem, I set all variables to true and see if the formula is satisfiable.

My question is because I do not understand how there can be multiple solutions, though all variables are true.

$\endgroup$
2
$\begingroup$

Satisfiability problems are about making the formula true, not necessarily the variables. Counting satisfiability problems ask how many different assignments to the variables make the formula true.

In $\#\text{Monotone-2SAT}$, the formula is in 2-CNF (conjunctive normal form with at most two literals per clause) and is monotone (there are no negations). So, certainly, making all the variables true satisfies the formula, but there are plenty of other ways. Just consider the formula $x\lor y$, which is monotone and in 2-CNF. It has three satisfying assignments.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.