I would like to define a pseudo-boolean function $f$ such that $f(x) = 0$ for all logically valid combinations of $x\in{0,1}$ and $f(x) > 0$ for all logically invalid combinations of $x\in{0,1}$.

Suppose I have the following constraint where $x_i \in {0,1}$:

$x_1 + x_2 + x_3 \leq 2$

$x_1$ $x_2$ $x_3$ Valid
0 0 0 Yes
0 0 1 Yes
0 1 0 Yes
0 1 1 Yes
1 0 0 Yes
1 0 1 Yes
1 1 0 Yes
1 1 1 No

After binary expansion, it becomes quite trivial to see that the case $\{1,1,1\}$ is the only case that causes an invalid result. As such, $f = x_1 \land x_2 \land x_3$ is an appropriate pseudo boolean function.

Is there an efficient way to reach this conclusion without a binary expansion?

Alternatively, I can surmise that the "invalid" cases are:

$x_1 + x_2 + x_3 > 1$

Since we are dealing with binary values, this is equivalent to:

$x_1 + x_2 + x_3 \geq 2$

That looks a little bit closer to $x_1 \land x_2 \land x_3$, but I'm still not sure...

  • $\begingroup$ You're asking for an efficient way to do something, which presumably means you're asking for an efficient algorithm. What are the inputs to the algorithm? Presumably some kind of specification of a constraint. But what kinds of constraints are allowed? Only a single linear constraint? A conjunction of multiple linear constraints? Something more general? $\endgroup$
    – D.W.
    Feb 16, 2022 at 7:11
  • $\begingroup$ I suggest you read up on en.wikipedia.org/wiki/Tseytin_transformation, en.wikipedia.org/wiki/Adder_(electronics), cs.stackexchange.com/q/82033/755 $\endgroup$
    – D.W.
    Feb 16, 2022 at 7:13


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.