# How to represent a 0-valid boolean formula?

I read in these two papers http://www.ccs.neu.edu/home/lieber/courses/csg260/f06/materials/papers/max-sat/p216-schaefer.pdf and http://people.csail.mit.edu/madhu/papers/noneed/fullbook.ps that if we have a boolean formula that is $0-valid$ then (of course) SAT problem is in $\mathcal{P}$ but finding a solution with maximum true literals is $\mathcal{NP}-$hard.

N.B. As defined in the previous papers, a $0-valid$ boolean formula $f$ is a boolean formula $f: \{0, 1\}^n\rightarrow\{0, 1\}$ that satisfies $f(0, \dotsc, 0)=1$.

My question is:

Can I represent a general $0-valid$ boolean formula on the variables $x=\left(x_1, \dotsc, x_n\right)$ by the following one:

$f(x)=\bigwedge\limits_{i=1}^{L}\bigvee\limits_{i\in\mathcal{S}_l}\neg\;x_i$?

Where $L$ is the number of clauses and $\mathcal{S}_l\;\forall\;l\in\{1,\dotsc, L\}$ is a subset of $\{1, \dotsc, n\}$.

• Can you please define what 0-valid means, to make your question self-contained? Are you asking if it can be representing in CNF using only negative literals (no positive literals)? – D.W. Mar 5 '14 at 17:43
• $0-valid$ is defined in the previous mentioned papers as follows: any boolean formula that is satisfied by a $0$ assignment. So if $f(x)$ is a boolean formula of $n$ variables, $f$ is $0-valid$ if $f(0)=1$. – npisinp Mar 5 '14 at 17:58
• I suggest you edit the question to include this. People shouldn't need to read the comments or other links to understand the question. This is not a discussion forum; comments exist only to help you improve your question, and are transient, so important information needs to be in the question, not just in comments. – D.W. Mar 5 '14 at 18:22

The constraints of a $0$-valid formula can be more general. All we know about them is that they are satisfied if all variables are $0$. For example, a constraint could be $x = y$ (i.e. $(x \land y) \lor (\lnot x \land \lnot y)$). Your form is not general enough, since it only considers constraints of the form $\lnot x_1 \lor \dots \lor \lnot x_\ell$.
While your formulation doesn't capture the problem of determining the most positive solution for a $0$-valid CSP, it is equivalent to an even more classical problem, set cover. In particular, your problem is NP-complete.
• But can I say that under the formula that I gave, finding a maximum number of true literals is $\mathcal{NP}-$hard? since it is a conjunction of disjunction of variables (I can asume at least 3 variables per clause). – npisinp Mar 5 '14 at 17:43
No. A formula in the form you propose has the property that it is never satisfied by the all-ones assignment (i.e., an assignment where all variables take the value True), assuming $L>0$. However, there exist non-trivial 0-valid formulas that don't have this property.
For instance, consider the xor $x \oplus y \oplus 1$; this is 0-valid, but is also satisfied by the all-ones assignment, and it is not equivalent to True, thus it cannot be expressed in the form you propose.