Como dijiste, $XOR(x_1, ..., x_n)=1$ si y solo si la cantidad de sus parámetros asignados a $1$ es impar. Sin embargo, las conjunciones que estás tomando no son suficientes ya que no excluyen la posibilidad de que los otros variables también sean uno.
Por ejemplo, considera las variables $x_1, x_2, x_3$ y $x_4$. La conjunción $x_1 \land x_2 \land x_3$ no excluye la valuación en la que todas las variables (incluyendo $x_4$) están asignadas a $1$.
Entonces, lo que estás buscando, en realidad, es una disyunción de conjunciones de literales de la siguiente forma:
$$x_{i_1}\land \cdots \land x_{i_k} \land \lnot x_{j_1} \land \cdots \land \lnot x_{j_l}$$
tal que $x_{i_1},..., x_{i_k}, x_{j_1}, ..., x_{j_l}$ es una permutación de $x_1, ..., x_n$ en la que $k$ es impar. Como has notado, no es necesario considerar todas esas permutaciones - puedes restringirlas a, por ejemplo, aquellas que hacen que las secuencias $i_1, ..., i_k$ y $j_1, ..., j_l$ sean crecientes. El número de tales permutaciones es de hecho $2^{n-1}$, es decir, el número de particiones de $\{i_1, ..., i_n\}$ en dos conjuntos, uno de los cuales tiene cardinalidad impar.
Entonces, el único problema con tu construcción es la falta de literales negativos en las conjunciones. Aunque, en mi opinión, por muy evidente que parezca, una prueba completa necesitaría establecer que si $XOR(x_1, ..., x_n) = 1$ entonces hay una conjunción en la fórmula DNF satisfecha por la asignación de las variables y si una determinada asignación de variables satisface alguna conjunción en la fórmula DNF, entonces la función $XOR$ cuando se aplica a esos valores también daría $1$.
