How to write boolean expression as linear equations 2

Question

I just posted How to write boolean expressions as linear equations and asked about a simple example. Here's what we know so far:

Suppose a,b,c,d,e ∈ {0,1}.

1. if the boolean expression is: a ≠ b, I could use the linear equation a+b=1.

2. if the boolean expression is: a=b ∧ c. I could describe this expression with: −1 ≤ 2b+2c−4a ≤ 3.

3. if the boolean expression is: a=b ∨ c, we can use the inequality 2a−1 ≤ b+c ≤ 2a. This expression can also be written as: -2 ≤ 2b+2c-4a ≤ 1.

Now suppose I have a more complicated case, say a = (b $\wedge$ c) $\vee$ (d $\wedge$ e).

Any ideas on how to write this as a linear equation? Is there an algorithm one can use to describe many of these expressions?

Thanks,

KBBALL

---

Here are two attempts to translate a = (b ∧ c) ∨ (d ∧ e).

1.

-1 $\le$ $(2b+2c)^3$+$(2d+2e)^3$ -65a $\le$ 63

(As some have pointed out, this solution doesn't count because it's not linear)

2.

0 $\le$ b+c+d+e-2a

b+c-a $\le$ 1

d+e-a $\le$ 1

|b-c| + |d-e| + a $\le$ 2

I think that attempt 2 is correct. And I also think that absolute values are allowed in "linear" equations. What do you think?

Answer 1

It is not always possible to find something like $u\le c_1a_1+\ldots + c_na_n\le v$. Consider (with $n\ge 3$) $$ \neg(a_1\land a_2\land \ldots \land a_n)\land \neg (a_1\land \neg a_2\land\neg a_3\land\ldots \land \neg a_n)\land \neg (\neg a_1\land a_2\land\neg a_3\land\ldots \land \neg a_n)$$ Wlog. the coefficient $c_n$ is $\ge 0$. Then $(1,1,\ldots,1)$ must be cut off by $v$, i.e. $c_1+\ldots +c_n>v$. But replacing a single $1$ with a $0$ must yield an expression in $[u,v]$, hence all $c_i$ are positive. On the other hand, we have $0\in[u,v], c_1\notin [u,v]$, $c_2\notin[u,v]$, $c_1+c_2\in[u,v]$. This is a contradiction because $c_1\in[0,c_1+c_2]$.