How to write boolean expressions as linear equations

Question

I want to convert a set of boolean expressions to linear equations. In some cases, this is easy. For example, suppose $a, b, c$ $\in$ {0,1}. Then if the boolean expression is: $a$ $\ne$ b, I could use the linear equation $a + b = 1$.

To give a more complicated example, suppose I'm dealing with the boolean expression $a=b$ $\wedge$ $c$. I could describe this expression with: $-1$ $\le$ $2b+2c-4a$ $\le$ $3$.

Does that make sense?

Now how would I convert a=$b$ $\vee$ $c$? Any ideas?

Thanks for considering!

K

Answer 1

You can translate $x \land y$ directly to $x+y=2$, and $x \lor y$ to $1 \le x+y \le 2.$ Also $\lnot x$ can be $x-1 \le 0$. This gives a basis for translation into equations or inequalities.

A simpler version of $a=b \land c$ I found to be $2a=b+c$. (This use of the 2 on the left is because of there being two variables on the right side).

Fiddling around I also found for $a=b \lor c$ the inequality $2a-1 \le b+c \le 2a$, based on using the above inequality for $x \lor y.$

Answer 2

Notice that you have a couple different solutions to consider here:

$a+b+c=0$ is part of your solution set.

Next, if $a=1$ then you'd want at least one of the other two to also be on, so possibly something like:

$2a+b+c\ge3$ would be the other part you'd need so that you cover for (a,b,c) the possibilities (1,1,0), (1,0,1), and (1,1,1).