Correctness of DNF representation of XOR I'm trying to show that XOR can be written as a DNF with $2^{n-1}$ terms. 
Note that $\mathrm{XOR}_n(x_1, \dots, x_n) := \oplus_{k=1}^n x_k$, where $\oplus$ is addition in $\mathbf{F}_2$, and $\mathrm{XOR}_n: \mathbf{F}_2^n \to \mathbf{F}_2$. 
Basically, my observation is that $\mathrm{XOR}_n(x)$ is 1 if and only if (as an element of $\{0, 1\}^n \subseteq \mathbf{R}^n$) $x$ has odd sum. Hence we should be able to write 
$\mathrm{XOR}_n(x) = \bigvee_{S \subseteq [n], |S|  \text{ odd}} (\land_{j\in S}~x_j)$, which is the or of $2^{n-1}$ ands, as desired. 
Is that essentially the argument? I couldn't find it anywhere. 
 A: As you said, $XOR(x_1, ..., x_n)=1$ if and only if the number of its parameters assigned to $1$ is odd. However, the conjunctions you're taking are not enough as they do not exclude the possibility of the other variables being one.
For instance, consider the variables $x_1, x_2, x_3$ and $x_4$. The conjunction $x_1 \land x_2 \land x_3$ does not exclude the valuation in which all variables (including $x_4$) are assigned to $1$.
So, what you're looking for, actually, is a disjunction of conjunctions of literals of the following form:
$$x_{i_1}\land \cdots \land x_{i_k} \land \lnot x_{j_1} \land \cdots \land \lnot x_{j_l}$$
such that $x_{i_1},..., x_{i_k}, x_{j_1}, ..., x_{j_l}$ is a permutation of $x_1, ..., x_n$ in which $k$ is odd. As you've noticed, there's no need for all such permutations - you can restrict them to, say, the ones which make the sequences $i_1, ..., i_k$ and $j_1, ..., j_l$ increasing. The number of such permutations is indeed $2^{n-1}$, that is, the number of partitions of $\{i_1, ..., i_n\}$ in two sets the first of which being of odd cardinality.
So the only problem with your construction is the lack of negative literals in the conjunctions. Although, in my opinion, as evident as it may seem, a complete proof would need to go on to establish that if $XOR(x_1, ..., x_n) = 1$ then there's a conjunction in the DNF formula satisfied by the assignment of the variables and if a given assignment of variables satisfies some conjunction in the DNF formula, then the function $XOR$ when applied to such values would also give $1$.
