How to write boolean expression as linear equations 2 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}. 


*

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

*if the boolean expression is: a=b ∧ c. I could describe this expression with: −1 ≤ 2b+2c−4a ≤ 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?
 A: 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]$.
A: Rewrite the logical proposition in conjunctive normal form and read off the linear constraints:
\begin{align}
& a \iff (b \wedge c) \vee (d \wedge e) \\
& \left(a \implies (b \wedge c) \vee (d \wedge e)\right) \bigwedge \left((b \wedge c) \vee (d \wedge e) \implies a\right)\\
& \left(\neg a \vee ((b \wedge c) \vee (d \wedge e))\right) \bigwedge \left(\neg((b \wedge c) \vee (d \wedge e)) \vee a\right)\\
& \left(\neg a \vee ((b \vee d) \wedge (b \vee e) \wedge (c \vee d) \wedge (c \vee e))\right) \bigwedge \left((\neg(b \wedge c) \wedge \neg(d \wedge e)) \vee a\right)\\
& \left((\neg a \vee b \vee d) \wedge (\neg a \vee b \vee e) \wedge (\neg a \vee c \vee d) \wedge (\neg a \vee c \vee e))\right) \bigwedge \left((\neg b \vee \neg c) \wedge (\neg d \vee \neg e)) \vee a\right)\\
& (\neg a \vee b \vee d) \bigwedge (\neg a \vee b \vee e) \bigwedge (\neg a \vee c \vee d) \bigwedge (\neg a \vee c \vee e) \bigwedge (\neg b \vee \neg c \vee a) \bigwedge (\neg d \vee \neg e \vee a)\\
& (1- a + b + d \ge 1) \bigwedge (1- a + b + e \ge 1) \bigwedge (1- a + c + d \ge 1) \bigwedge (1- a + c + e \ge 1) \bigwedge (1- b + 1- c + a \ge 1) \bigwedge (1- d + 1- e + a \ge 1)\\
& (a \le b + d) \bigwedge (a \le b + e) \bigwedge (a \le c + d) \bigwedge (a \le c + e) \bigwedge (a \ge b+c-1) \bigwedge (a \ge d+e-1)
\end{align}
