0

In the most part of the text books on Mixed Integer Linear programming, one can find that

$P_1$ XOR $P_2$ XOR ... XOR $P_n$ can be transposed in

$p_1 + p_2 + ... + p_n = 1$ where each $p_i$ is a boolean variable associated to the propositions $P_i$.

This is done without any demonstration. This is intuitively evident and through the Normal conjunctive form easy to demonstrate for $n= 2$. But astonishingly, I am not able to demonstrate this for $n \geq 3$.

For instance here is what append with 3 propositions :

$P_1$ XOR $P_2$ XOR $P_3$ can be put in Conjunctive Normal Form as

$(\neg P_1 \vee \neg P_2 \vee P_3) \wedge (\neg P_1 \vee P_2 \vee \neg P_3) \wedge (P_1 \vee \neg P_2 \vee \neg P_3) \wedge (P_1 \vee P_2 \vee P_3)$

and transform as the following set of inequalities

$\begin{array}{l}(1-p1) + (1-p2) + p3 \geq 1\\ (1-p1) + p2 + (1-p3) \geq 1\\ p1 + (1-p2) + (1-p3) \geq 1\\ p1+p2+p3 \geq 1 \end{array}$

To obtain the desired result, from the 3 first equations one must deduce that

$p_1+p_2+p_3 \leq 1$

but obviously I do not know how to obtain this. Could some one help me.

In all cases thanks

cyrille.piatecki
  • 111
  • 3
  • Not clear... are the $p_i$ and the $P_i$ the same variables ? are they booleans ? If so, we have $n$ cases mutually exclusive (XOR) and exactly one of them is TRUE. Thus, we have a sum of $n$ booleans with $n-1$ of them FALSE ($0$) and one TRUE ($1$). – Mauro ALLEGRANZA Jan 22 '19 at 14:34
  • Mauro, you were true. I have corrected the question. My problem is not to know if the formula is true. It is. The problem is to show this through the standard CNF conversion to boolean expressions – cyrille.piatecki Jan 22 '19 at 15:37

0 Answers0