I am trying to solve this problem and I am really struggling.
A monotone boolean formula is a formula in propositional logic where all the literals are positive. For example,
$\qquad (x_1 \lor x_2) \land (x_1 \lor x_3) \land (x_3 \lor x_4 \lor x_5)$
is a monotone boolean function. On the other hand, something like
$\qquad (x_1 \lor x_2 \lor x_3) \land (\neg x_1 \lor x_3) \land (\neg x_1 \lor x_5)$
is not a monotone boolean function.
How can I prove NP-completeness for this problem:
Determine whether a monotone boolean function is satisfiable if $k$ variables or fewer are set to $1$?
Clearly, all the variables could just be set to be positive, and that's trivial, so that is why there is the restraint of $k$ positively set variables.
I have tried a reduction from SAT to monotone boolean formula. One thing I have tried is to substitute a dummy variable in for every negative literal. For example, I tried replacing $\neg x_1$ with $z_1$, and then I tried forcing $x_1$ and $z_1$ to be different values. I haven't quite been able to get this to work though.