# Is there an efficient way to generate a pseudo-boolean function from a linear constraint?

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...

• 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?
– D.W.
Feb 16, 2022 at 7:11
• – D.W.
Feb 16, 2022 at 7:13