# Convert a Boolean expression to a linear expression?

Suppose we have a Boolean expression $$(\neg x_{1}\wedge\neg x_{2})\vee\left(\neg x_{1}\wedge\neg x_{3}\right),$$ which we need to be true. Is there a method to convert this to a linear expression of the form $$a_1x_1+a_2x_2+a_3x_3<1,$$ $$x_1,x_2,x_3\in\{0,1\}$$where $a_1,a_2,a_3$ are real constants. Such that the Boolean expression is satisfied iff the integer linear expression is satisfied. The question is how to find $a_1,a_2,a_3$ uniquely? There is a method to convert later linear expression into the Boolean expression but we need other way around.

Thanks a lot.

You may take

$$f(x_1,x_2,x_3)=(1+\varepsilon)x_1+(1-\varepsilon)(x_2+x_3)$$

where $\varepsilon \in (0,\frac{1}{2})$ is a constant.

When $(x_1,x_2,x_3)$ satisfies your condition, one has $f(x_1,x_2,x_3) \leq 1-\varepsilon$.

When $(x_1,x_2,x_3)$ does not satisfy your condition, one has $f(x_1,x_2,x_3) \geq 2(1-\varepsilon)$.

Note that there is no “uniqueness”.

• Thanks a lot. we were going for uniqueness but I guess it can't be done. – triomphe Dec 1 '13 at 15:04

One approach to get a system of linear constraints is to rewrite the logical proposition in conjunctive normal form and then read off the linear constraints: \begin{align} &(\neg x_1 \wedge \neg x_2) \vee (\neg x_1 \wedge \neg x_3) \\ &\neg x_1 \bigwedge (\neg x_2 \vee \neg x_3) \\ &(1 - x_1 \ge 1) \bigwedge (1 - x_2 + 1 - x_3 \ge 1) \\ &(x_1 \le 0) \bigwedge (x_2 + x_3 \le 1) \\ \end{align}